segunda-feira, 8 de outubro de 2018

Começando com um mea culpa, infelizmente eu sou responsável por boa parte dessa merda toda. Na década de 90 eu tinha website e fanzine digital, ajudei a criar a cultura brasileira na internet. No começo do século eu trabalhava criando dispositivos de inclusão digital, e depois eu fui desenvolvedor do Orkut, a rede social que ensinou os brasileiros a usar a internet.
Eu fiz tudo isso na inocência, achava de verdade que a internet iria trazer mais informação a todos, e que isso melhoraria o mundo. Hoje vejo que fui ingênuo, subestimei o papel da falsa informação e de como a internet permitiu a manipulação de massa de um jeito muito mais eficiente.
Mas se me permitem, eu acho que sei onde a coisa deu errado e tenho uma sugestão para melhorar. Eu acho que o foco do problema é o *broadcast privado*.
Broadcast nunca fui problema na internet. As pessoas mandavam mensagens em lista de discussão, postavam em comunidade do orkut, e nesses meios o fake news nunca teve esse poder que tem hoje.
O que mudou é que hoje em dia você pode fazer broadcast para grupos fechados (tipo o zap da família). Isso foi o game changer. Quando você postava na lista de discussão ou na comunidade do orkut, você estava aberto à contestação, se você posta X, alguém sempre pode postar não-X logo abaixo. Em termos de evidência acumulada, as coisas se cancelam.
Mas o zap da família é diferente porque é uma rede de contatos confiáveis. Você confia nos seus parentes. Quando chega uma mensagem nesse grupo, você tende a confiar por default na mensagem porque você confia em quem mandou, e essa confiança no emissor transfere para a mensagem.
Aí você forma uma rede de confiança. Não importa que o emissor original seja um bandido na cadeia, escrevendo de um celular que entrou na cela enfiado no cu. Se a mensagem dele passar de grupo em grupo, ela vai ganhando confiança ao longo do trajeto, porque cada broadcast privado aumenta a confiança dela. A confiança vem do caminho, não do conteúdo.
A solução fácil para isso seria banir broadcast privado. Não pode mais ter grupo de zap, ou pelo menos não pode ter botão de share para grupo privado: se você quiser repassar, vai ter que reescrever. Aumentando a fricção no processo de share, a mensagem falsa tem mais dificuldade de propagar.
Outra solução seria fazer tracking da confiança da mensagem. Eu não faço idéia de como implementar isso, mas cada mensagem teria que ter um score que medisse a confiança da origem. Uma mensagem que transitou inalterada de uma fonte primária teria score alto, uma mensagem enviada por celular tirado do cu teria score baixo.
Mas eu não sei se nenhuma dessas alternativas é economicamente viável, dado que os times que implementam esses apps medem sucesso baseado em quantidade de shares. Se alguém tiver uma idéia melhor para atacar o problema eu agradeço.


quinta-feira, 13 de setembro de 2018

Programar computadores para mim é mais que uma atividade, é um estilo de vida. Praticamente tudo que eu faço gira em torno disso. Meu trabalho é programar computadores, nas horas vagas eu programo computadores por hobby, até minha esposa eu conheci numa comunidade de computadores.
E quem me ensinou a programar computadores foi meu pai. Quando eu era bem pequeno, nós programávamos BASIC usando papel e lápis. Nos fins de semana ele me levava para o trabalho dele, onde eu treinava nos computadores da empresa. E depois de um tempo nós conseguimos comprar um TK90X que foi o meu primeiro computador.
Estava aqui pensando que meu pai tem muito em comum com o Prometheus da lenda. Prometheus deu a vida aos humanos a partir do barro, e depois roubou a chama do conhecimento para a humanidade. Foi isso que meu pai fez, me deu a vida e o conhecimento da programação. Todo o resto que eu fiz veio disso.
Após roubar a chama do conhecimento, Prometheus foi preso em uma montanha, onde toda noite uma águia comia um pedaço de seu fígado. Infelizmente, meu pai também teve isso em comum com ele. Mas, ao invés de uma águia, foi um câncer que comeu o fígado do meu pai. Desses que crescem muito rápido, e não tem remédio nem Hércules que segure.
Hoje meu pai faleceu. Obrigado por tudo pai, você foi um Titã.


terça-feira, 20 de março de 2018

O Sloane publicou uma sequência que eu inventei no OEIS! A sequência é "a quantidade de caminhos de n passos feitos por um rei que começa no canto de um tabuleiro de xadrez infinto". O link é https://oeis.org/A300665

A história da sequência é assim: a gente sabe que o melhor método para resolver puzzles é o exact cover, mas ele só funciona para puzzles tipo sudoku (cada quadrado pode ter só um número), e não funciona em puzzles tipo akari (cada quadrado pode estar iluminado por mais de uma lâmpada).

Mas no começo do ano o Knuth publicou uma variação do exact cover que funciona com todos os puzzles, de fato, funciona com qualquer problema que possa ser descrito como constraint programming.

É claro que a primeira coisa que passou pela minha cabeça foi: "serve para o Torto Reverso?" (*) Quer dizer, é claro que serve, mas é um bom algoritmo na prática? Antes de codificar, eu resolvi estimar qual seria o tamanho da matriz de cover, e de cabeça ela tem que ser mais ou menos da ordem do número de caminhos que um rei por fazer no tabuleiro de xadrez (já que os movimentos do rei são os mesmos movimentos do torto reverso).

Usar os métodos do post de ontem (**) não funciona porque os caminhos não podem repetir casas. Então tem que ser a força bruta mesmo. Fiz um scriptinho em python e damn, a(7)=60215, isso não vai convergir nunca, a matriz é muito grande.

De curiosidade, eu peguei a sequência e coloquei no OEIS para ver se tinha assintótico, e uepa! ninguém tinha calculado essa sequência ainda! Fiz uma implementação em Mathematica para conferir as contas e submeti a sequência.

O povo do OEIS adorou, mas achou pouco. Com o python eu consigo ir até a(12) só e eles queriam mais. Então eu apelei e reimplementei em C++, aí deu para ir até a(15). Mesmo com a cpu em 100% não dá para ir muito além.

Mas eu não me preciso me limitar a 100% de cpu né? Reimplementei em Go e usando 800% de cpu eu consegui o a(16). Depois eu reparei as sequencias são simétricas em relação ao eixo de 45 graus, então só preciso calcular metade delas. Aí cheguei no a(17). Depois disso todas as minhas heurísticas falharam, mas eu ainda não desisti. (Quer dizer, é só deixar o computador ligado uma semana direto que eu pego mais números, mas eu queria um jeito que dê para computar rapidamente).

(*) Se você não conhece o torto reverso, o prêmio ainda não teve ganhadores -> http://blog.ricbit.com/2011/05/torto-reverso.html
(**) Se você perdeu o post de ontem sobre otimização em grafos, ainda dá tempo -> http://blog.ricbit.com/2018/03/a-marcha-dos-lemmings.html

quinta-feira, 4 de janeiro de 2018

Estava lendo agora sobre a vulnerabilidade nova que estão exploitando, e é bem legal!

Funciona assim: primeiro você executa um código desse jeito:

If (bigvalue < a.length) { value = a[bigvalue]; }

Se bigvalue for um valor maior que o tamanho do array, voce faria uma leitura fora de bounds, o que te permitiria ler qualquer valor da memória. Mas isso não deveria acontecer, por dois motivos: primeiro o if garante que você nunca executa aquele trecho; segundo mesmo que permitisse a cpu iria estourar um page fault porque você não tem permissão de ler aquele endereço.

SÓ QUE sua cpu tem execução especulativa. Se o a.length estiver fora do cache, a cpu precisa esperar uns 100 ciclos até o valor chegar. Para não ficar parada, ela sai executando o interior do if, e descarta essa execução quando o valor chega.

Em princípio isso não deveria ser acessível para o usuário, mas olha a pegadinha: como ele executou especulativamente o if, então agora o a[bigvalue] está no cache!

Agora você pode usar o seguinte código:

If (bigvalue < a.length) { value = a[bigvalue];
If (value&1 > 0) { x = a[100]; } else { x= a[200];}
}

Você controla o array a, então suponha que você forçou o array inteiro para fora do cache. Quando você executar esse código, a cpu vai tentar ler o a.length e travar (já que está fora do cache). Ela vai tentar executar especulativamente o if interno, e ela consegue (nesse ponto o a[bigvalue] está no cache e a cpu está executando especulativamente, então não checa as permissões). Dependendo do bit 0 do a[bigvalue] ela vai tentar ler o a[100] ou o a[200]. Eventualmente o valor de a.length chega e a cpu rebobina tudo porque o primeiro if falhou.

Agora vem a malandragem, você mede o tempo que leva para ler a[100] e a[200]. Só um deles foi parar no cache, aquele que ler mais rápido indica qual o valor do bit 0 de a[bigvalue]! Você acabou de ler um bit que não tinha permissão! Repete isso para os outros bits e você consegue ler qualquer valor da memória, até a senha do banco que está no outro tab do seu browser!

Para matar isso é fácil, só desligar o cache na bios. Mas aí seu computador de 2018 vai ficar mais lento que 386 rodando Windows 10, então ninguém vai fazer isso. Sacada muito boa, kudos para quem inventou a técnica.