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