A rede dos pacotes do Debian GNU/Linux

A dissertação de mestrado “Análise da Estrutura da Rede de Pacotes do Sistema Operacional Debian GNU/Linux”, de Orahcio F. de Sousa está pronta. O trabalho foi realizado sob a orientação minha e do Márcio Argollo de Menezes. A defesa pública será realizada dia 14 de abril, às 13:00, no Instituto de Física da UFF.

O trabalho foi possível porque as informações do projeto Debian estão facilmente disponíveis na rede. O que fizemos foi pegar a lista de pacotes e dependências e montar uma rede (grafo direcionado). A partir desta rede, procuramos medir várias quantidades, tais como os pacotes mais fundamentais do projeto, pacotes em que um bug afetaria um número grande de pacotes que mede, de certa forma, a robustez do projeto, descobrimos comunidades de pacotes, e outros resultados interessantes (pelo menos para a gente). A figura acima é um deles: o gráfico maior é uma representação log-log do número de pacotes que são dependências de outros. O gráfico mostra que a situação mais provável é que o pacote seja um pacote final,isto é, não é dependência de ninguém. O mais interessante é que a figura é uma reta no gráfico log-log, o que significa que muitos pacotes são dependências de poucos, mas poucos pacotes são fundamentais e afetam muitos outros. Isto torna a rede robusta a bugs aleatórios mas frágil para ataques direcionados: em termos leigos, se alguém maliciosamente modificasse um pacote deb, provavelmente só afetaria o próprio pacote e uns poucos outros, mas se maliciosamente mudasse a libc6, praticamente tornaria o sistema instável. O gráfico menor não é uma lei de potência como o anterior, mas uma exponencial e representa quase que o inverso da anterior: quantas dependências um pacote tem. Sendo exponencial significa que existe um número típico (20) para o número de dependências. A parte de comunidades também é interessante, podendo inclusive sugerir os pacotes que deveriam ser tratados por um time de desenvolvedores. Na nossa análise, conseguimos encontrar um número muito pequeno de empacotamento cíclico (A depende de B que depende de C mas C depende de A), isto é, pacotes que não são instaláveis a não ser em conjunto com outros (e este número diminui a cada release).

Este não é o primeiro trabalho sobre o Debian, nem o primeiro de físicos. Em Empirical Tests of Zipf's law Mechanism In Open Source Linux Distribution, Mairlatt e outros usaram a evolução da rede de pacotes Debian para testar um modelo de crescimento que dá origem à lei de Zipf. Um caso famoso da lei de Zipf é a frequência das palavras em qualquer linguagem: é um curva exatamente como as das dependências que mostrei acima, uma lei de potência ou cauda longa. Outro caso é a distribuição de tamanhos de firmas, que também segue a lei de Zipf. Em Do scale-free regulatory networks allow more expression than random ones?, Fortuna e Melian usaram da rede de pacotes para simular uma rede reguladora de genes e mostrou que esta estrutura é mais eficiente que uma rede aleatória.

Para quem quiser ler, a dissertação do Orahcio está disponível aqui. Uma versão preliminar e mais enxuta vai sair no Journal of Computational Interdisciplinary Sciences e o draft está disponível aqui. Quando escrevemos o artigo, o Lenny ainda era a “testing”. Tivemos que rodar novamente os programas para a Lenny como estável. Estou disponibilizando as referências aqui pois não dava para fazer um trabalho sobre Debian e não deixar público!