Combatendo a censura com algoritmos

Mohammad Mahdian * (tradução: Tiago Madeira)

Mãos algemadas digitando num teclado de computador

Os levantes recentes no Oriente Médio demonstraram a eficácia da internet em ajudar ativistas políticos e sociais a organizarem protestos, disseminarem informações para o público e enviarem notícias de prisões e repressões ao restante do mundo. Ameaçados por esse paradigma, regimes totalitários tentaram controlar e monitorar o acesso de seus cidadãos à web, desenvolvendo ou adquirindo tecnologias de censura e de vigilância da internet. Ao mesmo tempo, uma variedade de ferramentas de violação desses filtros foi desenvolvida para ajudar os usuários a contornarem o filtro da internet acessando sites bloqueados através de intermediários não-bloqueados (os chamados proxies). O artigo de Dan Boneh (Recent Ideas for Circumventing Internet Filtering) dá um ótimo resumo sobre novas e velhas técnicas para construir essas ferramentas.

No coração de todos os métodos de violação existe o seguinte dilema: Para fazer a ferramenta disponível ao público, os endereços de proxy precisam ser comunicados para os usuários. Isso, no entanto, permite que as autoridades obtenham esses endereços (fingindo serem usuários legítimos) e aí bloqueiem todo o tráfego nesses endereços específicos. Ter vários proxies de curta duração alivia o problema, mas a questão permanece: Existe algum método algorítmico esperto para distribuir proxies que diminua o número de proxies necessários para fornecer acesso à internet sem filtro?

O problema de distribuição de proxy

Vamos começar definindo um modelo teórico simples para este problema. Nós gostaríamos de distribuir um conjunto de m proxies para uma população de n usuários: k deles são adversários (agentes da censura) e o restante (n-k) são usuários legítimos. Nós não sabemos as identidades dos adversários, mas podemos assumir que k << n. Na verdade, para simplicidade, pense em k como uma constante, enquanto n cresce ao infinito.

Se um proxy é dado a um adversário, ele pode comprometer o proxy, tornando-o inutilizável para os outros usuários. Uma vez que um proxy é comprometido, nós ficamos sabendo e podemos distribuir outros proxies para os usuários afetados. Nossa meta é garantir que todo usuário legítimo tenha pelo menos um proxy não-comprometido. A questão é: qual é o menor m com o qual conseguimos fornecer essa garantia?

Claramente, o problema pode ser resolvido com n proxies dando pra cada usuário um proxy diferente. Na verdade, podemos fazer muito melhor usando um algoritmo de busca binária: Comece dividindo os usuários em duas caixas e dê pra cada caixa o seu proxy. Uma vez que um proxy é comprometido, divida sua caixa correspondente pela metade e dê para cada uma das metades um proxy. Continue fazendo isso enquanto existe apenas um usuário na caixa. É fácil ver que esse método usa no máximo O(log(n)) proxies. Uma divisão cuidadosa dos usuários em caixas rende uma solução com no máximo k(1+log2(n/k))k(1+log_2(n/k)) proxies.

Podemos resolver o problema com menos de O(log(n)) proxies? Talvez surpreendentemente, nós podemos fazer um pouco melhor. Há um algoritmo randomizado de distribuição de proxies que usa no máximo O(log(n)/loglog(n)) proxies. Um argumento simples de entropia mostra que isso é assintoticamente ótimo para um k constante.

Distribuição de proxies via redes de confiança

Uma forma comum de construir uma base de usuários num país sob censura é através de relações pessoais de confiança. O sistema começa com poucos usuários confiáveis e então cada usuário confiável pode convidar novos usuários em quem ele confia para o sistema. Dessa forma, o conjunto de usuários cresce como uma rede de confiança: uma árvore enraizada na qual o conjunto de usuários confiáveis inicial é filho da raiz e arestas indicam relações de confiança.

Usar uma rede de confiança dificulta que um adversário se infiltre na base de usuários. No entanto, o problema é que uma vez que a rede é infiltrada, o adversário pode convidar novos adversários para a rede. Para levar isso em conta, nós modificamos a formulação do problema como segue: em vez de exigir que um pequeno número de usuários seja adversário, nós assumimos que um pequeno número de usuários e todos os seus descendentes na rede são adversários. Uma forma alternativa de formular esse problema é considerar redes de confiança capacitadas e assumir que o menor corte da raiz para todos os adversários é no máximo um pequeno número k.

O problema de distribuição de proxy em redes de confiança está ainda sem solução em geral. Temos resultados parciais para pequenos k e no caso capacitado. Os algoritmos são não-triviais e precisam olhar para a estrutura da rede de confiança.

Conclusão

O objetivo desse exercício era convencer o leitor de que existe um problema teórico interessante e desafiante no âmago das tecnologias de violação de censura. Modelos e algoritmos para esse problema estão muito próximos dos que são usados na prática e, logo, há potencial para pesquisa nessa área que pode ter um impacto real nas vidas de milhões de pessoas vivendo sob opressão.


* Mohammad Mahdian é um pesquisador senior do Yahoo Research Lab em Santa Clara, CA. É bacharel em Engenharia da Computação pela Universidade de Tecnologia de Sharif, mestre em Ciência da Computação pela Universidade de Toronto e PhD em Matemática pelo MIT. Seus interesses de pesquisa atuais incluem projeto de algoritmos, economia algorítmica e aplicações em publicidade online e redes sociais.

Capa da XRDS

Este texto foi publicado em inglês na última edição da XRDS (revista da ACM para estudantes), cujo tema é Ciência da Computação a serviço da democracia. No site do autor, há o artigo “Fighting censorship with algorithms” completo em PDF disponível para download gratuito. Ainda não li, mas parece interessante.

Liberdade controlada

Google e China

Colocam na nossa cabeça que o nosso mundo é perfeito e que só em contos de fada existem pessoas más, dizem que só na China existe ditadura, dizem que aqui somos livres… Temos que abrir os olhos!

Isso foi o que eu comentei no primeiro post do Mal Vicioso no dia 02 de dezembro de 2006.

Vivemos numa ilusão que recebe o nome de democracia = poder do povo. A atitude tomada pela justiça brasileira de bloquear o Youtube nos faz perceber como o nosso mundo é dominado e como não somos livres. É a prova de que existe o Grande Irmão ou é a volta da ditadura.

Logo do YouTube

Por causa de uma modelo, bloquearam um site inteiro aqui no Brasil… Uma modelo que foi filmada na Europa fez com que bloqueassem um site estado-unidense aqui no Brasil. Dá pra entender? Falou bem o Cardoso, que sugere que o Brasil siga o exemplo do Iraque em relação ao vídeo de execução do Saddam Hussein:

[nossa justiça] não foi atrás de quem postou o (supostamente) ilegal vídeo da cicarelli. Não foi atrás de quem filmou, não foi atrás do canal de tv que exibiu o mesmo. Céus, conseguiram ser mais covardes que a RIAA, que processa garotinhas de 12 anos. Sequer foram atrás dos adolescentes que subiram o vídeo para o YouTube, Google Video e outros.

Acharam melhor matar o mensageiro.

E o pior é que isso não serviu pra nada. Encontrar outros locais com o vídeo da Cicarelli é muito fácil. Entrar no Youtube também não é impossível.

O que eu pergunto à justiça brasileira, à Cicarelli e ao “especialista” que sugeriu fechar o Youtube é: pra quê?

Só pode ser jogada de marketing da modelo, como já disse o Ataliba. Assim ela voltou a aparecer. Agora que ela já tá satisfeita, a BrasilTelecom poderia fazer o favor de reabrir o Youtube?

Esse controle de acesso à internet é ridículo. A internet é o que é porque é livre. Achei que já havíamos passado dessa fase de ditadura, de censura, de controle… mas parece que ainda não. Não sei como a nossa justiça é capaz de bloquear o Youtube, não sei como várias empresas no mundo desenvolvem e implementam DRM e o pior de tudo: não sei como a gente vê tudo isso e permanece calado.

© 2005–2020 Tiago Madeira