[Brasil-PM] você confia na ordem das chaves de um hash?
breno
breno em rio.pm.org
Quarta Dezembro 5 20:39:13 PST 2012
(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
Mais detalhes sobre a lista de discussão Brasil-PM