[Brasil-PM] você confia na ordem das chaves de um hash?
Andre Carneiro
andregarciacarneiro em gmail.com
Quinta Dezembro 6 02:30:46 PST 2012
Breno++ #servindo muito bem a comunidade, como sempre!
Obrigado Breno!
2012/12/6 Carlos Costa <crncosta em gmail.com>
> 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
>>
>
>
> _______________________________________________
> Brasil-PM mailing list
> Brasil-PM em pm.org
> http://mail.pm.org/mailman/listinfo/brasil-pm
>
--
André Garcia Carneiro
Software Engineer
(11)982907780
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/brasil-pm/attachments/20121206/ee0a15f8/attachment-0001.html>
Mais detalhes sobre a lista de discussão Brasil-PM