[Brasil-PM] você confia na ordem das chaves de um hash?
Carlos Costa
crncosta em gmail.com
Quinta Dezembro 6 01:25:53 PST 2012
Breno++ # Claro e objetivo. Muito obrigado! =)
( )s
Carlos.
2012/12/6 Marcio Ferreira <marciodesouzaferreira em gmail.com>
> breno++ while each() != keys()
>
> parabéns post!
>
> []s,
>
> Marcio Ferreira
> skype: marcio.ferreir4
> (21) 8365-7768
>
>
>
> 2012/12/6 breno <breno em rio.pm.org>
>
>> (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
>>
>
>
> _______________________________________________
> Brasil-PM mailing list
> Brasil-PM em pm.org
> http://mail.pm.org/mailman/listinfo/brasil-pm
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/brasil-pm/attachments/20121206/da8b4b59/attachment-0001.html>
Mais detalhes sobre a lista de discussão Brasil-PM