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.