[Brasil-PM] você confia na ordem das chaves de um hash?
Gabriel Andrade
gabiruh em gmail.com
Quinta Dezembro 6 04:57:44 PST 2012
+
+
++breno++
+
+
On Dec 6, 2012, at 1:39 AM, breno <breno em rio.pm.org> wrote:
> (do original em:
> http://onionstand.blogspot.com.br/2012/12/are-you-relying-on-hash-keys-being.html)
>
> tl;dr
> ------
>
> Se você pretende eventualmente migrar para o 5.18, faça isso *agora*:
>
> 1. Instale o 5.17.6 (você usa perlbrew[1], certo?);
> 2. Experimente seus módulos e aplicativos nele (você tem testes, certo?);
> 3. Se alguma coisa quebrar, é porque provavelmente algo está
> dependendo dos valores de keys(), values() ou each() estarem em um
> ordem particular. Você realmente não deveria estar fazendo isso, então
> use sort() ou coisa que o valha nesses valores :)
> 4. Se algum módulo do CPAN que você usa falhar no 5.17.6,
> certifique-se de que o autor está ciente e preparando um patch;
> 5. Divulgue!
>
>
>
> Sobre Hashes e Segurança
> ======================
>
> O "core team" do Perl 5 sempre coloca segurança como uma de suas
> maiores prioridades. Para termos noção, no final de 2011 um ataque de
> negação de serviços remoto explorando complexidade
> algorítmica[2][3][4][5] foi descoberto em importantes implementações
> de linguagens como PHP, Ruby, Python, Java, até mesmo JavaScript. Essa
> vulnerabilidade havia sido corrigida no Perl 5 desde... 2003.
>
>
> Isso foi antes. E agora?
> ==================
>
> Ainda pensando em segurança, Yves Orton fez algumas mudanças
> importantes nas últimas semanas, mudanças que vão entrar no perl
> 5.18.0. Entre outras coisas[6], temos:
>
> * Introdução de múltiplas funções de hashing para escolher na hora
> de compilar o perl. Entre as opções estão Murmur-32[7], SDBM[8],
> DJB2[9], SipHash[10], SuperFast[11], e uma versão melhorada do
> original One-at-a-time;
>
> * Eliminação do antigo mecanismo HvREHASH, substituído por uma
> semente aleatória de hash por processo.
>
> Otimizações à parte, a possibilidade de trocar de função de hash
> facilmente é importante pois, caso, por um motivo qualquer, a função
> atual seja considerada vulnerável a ataques, você não precisa esperar
> até que o "core team" do Perl - ou seu fornecedor/sistema - lance uma
> versão corrigida: basta recompilar seu perl escolhendo outra função.
>
> A parte importante, no entanto, é a semente de hash ser aleatória por
> processo. Até então, o perl usava uma semente de hash que não era lá
> grande coisa, semente essa que era definida durante a compilação.
> Todos os hashes usam essa semente e, quando um ataque de colisões é
> detectado, um "rehash" era executado, em que todos os elementos do
> hash teriam seu valor recalculado, com todas as consequências
> esperadas em termos de desempenho e memória. Claro que, quando muitas
> colisões aconteciam, o rehash mudava para uma semente aleatória.
>
> Agora, após essa última modificação, todos os processos usarão
> garantidamente uma semente aleatória.
>
> Essa aleatoriedade da semente dos hashes deve tornar o perl ainda mais
> robusto contra ataques de complexidade, e com código mais simples. No
> entanto, como você pode ter previsto, há um efeito colateral a essa
> mudança: a ordem das chaves de um hash mudam com bem mais frequência
> do que antes.
>
>
> Legal! Mas, o que isso significa pro meu código?
> ======================================
>
> Conforme escrito no perlsec[12] desde a versão 5.8.1 do perl (aquela
> de 2003), Perl nunca garantiu qualquer ordenação das chaves de um
> hash, e de fato essa ordenação já mudou algumas vezes ao longo da
> história. O problema, porém, é que muitos desenvolvedores acabam sem
> querer dependendo da ordenação de hashes, ou ao menos de alguma ordem
> aleatória mas constante, simplesmente porque aquela ordem em
> particular funcionava em seus ambientes. Isso que é bug sutil!
>
> Pode não ser o seu caso, mas é bom ter certeza. Andreas König, Father
> Chrysostomos e o resto dos P5P/CPANTesters se deram ao trabalho de
> testar diversas das principais distribuições que estão no CPAN[13] e
> avisar aos autores sempre que um teste falhava ao executar a versão
> nova do perl. Mas eles não podem fazer isso com todos os módulos, e
> ainda tem o *seu* código pra testar também.
>
> Você sabe, aquele código da sua aplicação. Código que você não botou no CPAN.
>
> Estranhamente, parece que na maioria dos casos encontrados no CPAN os
> problemas estavam nos testes, testes que esperam que keys() estejam em
> uma ordem em particular. A função keys() garante apenas que os valores
> retornados estarão na mesma ordem que as funções values() e
> each()[14], e mesmo isso só é garantido para o mesmo processo, então
> certifique-se de que não esteja dando tiros no pé.
>
>
>
> Mentira! Meu código é perfeito, vocês é que quebraram o Perl!
> ================================================
>
> Então, não exatamente. Como disse antes, é um bug muito sutil, um que
> pode estar afetando seu código em produção neste exato momento, ainda
> que apenas em alguns cenários específicos, e por isso mesmo ser muito
> difícil de reproduzir e depurar. Não acredita? Há um experimento muito
> simples que você pode fazer em seu perl do sistema:
>
> Primeiro, vamos criar um one-liner simples que cria 15 pares
> chave/valor, e imprime eles na tela:
>
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 6, 11, 3, 7, 9, 12, 2, 15, 14, 8, 1, 4, 13, 10, 5
>
> Você pode ter recebido na sua tela uma ordem diferente (recebeu?), mas
> você provavelmente vai ganhar a mesma ordem não importa quantas vezes
> você executar:
>
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 6, 11, 3, 7, 9, 12, 2, 15, 14, 8, 1, 4, 13, 10, 5
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 6, 11, 3, 7, 9, 12, 2, 15, 14, 8, 1, 4, 13, 10, 5
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 6, 11, 3, 7, 9, 12, 2, 15, 14, 8, 1, 4, 13, 10, 5
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 6, 11, 3, 7, 9, 12, 2, 15, 14, 8, 1, 4, 13, 10, 5
>> ...
>
> Mas o que acontece se o seu código adicionar uma 16a chave por engano
> e, ao perceber o erro, remover a chave logo depois? Ainda teremos 15
> chaves, as mesmas 15 chaves de antes, então é claro que os valores
> estarão na mesma ordem de antes, certo? CERTO? Errado:
>
>> perl -E 'local $,=q[, ]; $hash{$_}=$_ for 1..15; $hash{16}=16;
> delete $hash{16}; say keys %hash'
> 11, 7, 2, 1, 13, 6, 3, 9, 12, 14, 15, 8, 4, 10, 5
>
> Isso pode acontecer em qualquer lugar, como ao reutilizar uma variável de hash:
>
> sub init { ( 1=>1, 2=>2, 3=>3, 4=>4, 5=>5 ) }
>
> my %hash = init();
> say "original: " . join ', ' => keys %hash;
> $hash{$_} = $_ for 6..100;
>
> %hash = init(); # restaura valores originais
> say "original? " . join ', ' => keys %hash;
>
> Isso é o que eu recebo como saída no meu bom e velho 5.14.3:
>
> original: 4, 1, 3, 2, 5
> original? 2, 1, 3, 4, 5
>
> Como podemos ver, trata-se de um problema real e que pode estar
> espreitando em um canto obscuro do seu código neste exato momento. O
> que o patch do Yves faz é simplesmente expor o problema de forma mais
> explícita para você. Isso é uma coisa boa, porque, além da segurança
> extra, você vai conseguir identificar código quebrado muito mais
> facilmente. Se você tentar o one-liner original acima no 5.17.6, você
> vai receber uma ordem de chaves diferente a cada execução:
>
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 1, 5, 15, 12, 6, 4, 10, 9, 3, 13, 7, 14, 11, 2, 8
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 5, 11, 7, 3, 15, 6, 12, 2, 13, 9, 8, 14, 10, 1, 4
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 2, 15, 14, 13, 5, 1, 9, 10, 3, 11, 6, 8, 12, 4, 7
>> perl -E 'local $,=q[, ]; $hash{$_} = $_ for 1..15; say keys %hash'
> 8, 2, 14, 10, 1, 9, 4, 3, 6, 15, 5, 13, 7, 12, 11
>
>
>
> Então... acho que meu código está quebrado.
> ===================================
>
> Não se preocupe, a solução costuma ser fácil! Procure pelo teste que
> falha e verifique se o que quer que esteja sendo testado chama keys(),
> values() ou each() em algum lugar. Você provavelmente quer rodar o
> sort() nesses valores para garantir a ordem, ou modificar seu
> algoritmo para algo mais determinístico.
>
>
>
> Sabe o que que é, eu não tenho lá muitos testes... O que fazer?
> =================================================
>
> Procure por chamadas a keys(), values() ou each() no seu código, e
> certifique-se que eles não dependem da ordem dos elementos retornado.
> Tudo bem fazer algo como:
>
> my @keys = keys %hash;
> my @values = values %hash;
> say "hash key $keys[3] vale $values[3]";
>
> porque, como vimos antes, keys() e values() vão sempre usar a mesma
> ordem para o mesmo processo, qualquer que seja essa ordem. O código
> abaixo, no entanto, está errado:
>
> if ($keys[0] eq 'alguma_chave') {
> ...
> }
>
> simplesmente porque não há qualquer garantia da ordem na lista
> retornada por keys(). Por outro lado, o código acima teria funcionado
> perfeitamente se o valor retornado estivesse ordenado, fazendo algo
> como:
>
> my @keys = sort keys %hash;
>
>
>
> Uso indireto
> =========
>
> Infelizmente, seu código não está seguro simplesmente porque você não
> usa essas funções (ou ordena elas corretamente). Algumas vezes nós
> recebemos listas de valores de módulos de terceiros, e essas listas
> podem estar afetadas pelo problema. Por isso, procure por listas
> populadas por funções externas e veja se você depende que os valores
> recebidos estejam em uma ordem particular. Por exemplo, você pode ter
> código assim:
>
> my ($nome, $idade, $grau) = Algum::Modulo->new->get_list( 'algum_usuario' );
>
> E, só dentro de Algum::Modulo, você encontrar o suspeito:
>
> sub get_list {
> my ($self, $username) = @_;
> return values $self->{data}{$username};
> }
>
> Faça um teste que falha para essa função, envie a correção, repita :)
>
>
> Calce as Sandálias da Humildade
> ==========================
>
> Achar que você é imune, que esse tipo de erro é coisa de amador ou que
> só acontece no código do vizinho não é saudável. Mesmo módulos
> estáveis e consagrados como DBI, LWP, DBIx::Class e Catalyst::Runtime
> foram vítimas do problema de uma forma ou de outra. Felizmente,
> módulos como esses possuem uma comunidade muito forte e engajada, e as
> correções ou já estão no CPAN ou chegarão lá a qualquer momento.
>
>
>
> Odiei a mudança! Mudem de volta!
> ===========================
>
> Olha, vai ser difícil isso acontecer. Lembre-se: aleatoriedade nos
> hashes é uma coisa boa! Por favor dê uma outra olhada nas seções acima
> e tente corrigir seu código. Se precisar de ajuda, peça nos lugares de
> sempre, como nas listas (como essa!), no IRC - hoje em dia até
> Facebook tem grupos de Perl!
>
> Mas se você realmente precisa do comportamento anterior (sabe-se lá
> por quê), você pode simplesmente continuar no 5.16 ou tentar compilar
> o perl definindo o PERL_HASH_FUNC_ONE_AT_A_TIME_OLD pra simular o
> algoritmo velho, mas de qualquer forma o mecanismo de rehashing foi
> embora, então especificar seu próprio valor de semente no
> PERL_HASH_SEED é provavelmente o mais perto que vai chegar :)
>
> Agradecimentos especiais a todos do P5P por seu esforço contínuo em
> nos manter à salvo!
>
>
>
> Referências:
> ==========
>
> [1] - http://perlbrew.pl
> [2] - http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf
> [3] - http://www.nruns.com/_downloads/advisory28122011.pdf
> [4] - http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf
> [5] - http://media.ccc.de/browse/congress/2011/28c3-4680-en-effective_dos_attacks_against_web_application_platforms.html
> [6] - http://perl5.git.perl.org/perl.git/commit/7dc8663964c66a698d31bbdc8e8abed69bddeec3
> [7] - http://code.google.com/p/smhasher/wiki/MurmurHash3
> [8] - http://www.cse.yorku.ca/~oz/hash.html
> [9] - http://www.cse.yorku.ca/~oz/hash.html
> [10] - https://www.131002.net/siphash/
> [11] - http://www.azillionmonkeys.com/qed/hash.html
> [12] - http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks
> [13] - https://rt.perl.org/rt3/Public/Bug/Display.html?id=115908
> [14] - http://perldoc.perl.org/functions/keys.html
> _______________________________________________
> Brasil-PM mailing list
> Brasil-PM em pm.org
> http://mail.pm.org/mailman/listinfo/brasil-pm
Mais detalhes sobre a lista de discussão Brasil-PM