Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Randomizing Hash Implementation?

by saintmike (Vicar)
on Apr 09, 2005 at 23:45 UTC ( #446319=perlquestion: print w/replies, xml ) Need Help??

saintmike has asked for the wisdom of the Perl Monks concerning the following question:

Venerable monks, someone just told me that their perl (v5.8.1-RC3/darwin) stored hashes differently between different invocations of a program. Now, while we certainly can't rely on the 'order' in which hash entries are stored, I was assuming (until now) that the 'order' was at least consistent.

But it turns out that multiple calls to

$ perl -e '%a=(1=>"a",2=>"b",3=>"c"); print %a,"\n"'
produce different output on this platform, like this:
2b3c1a 3c1a2b ...
Does anybody know if there's a random generator in the hash algorithm of some perl implementations?

Replies are listed 'Best First'.
Re: Randomizing Hash Implementation?
by tilly (Archbishop) on Apr 10, 2005 at 00:06 UTC
    Yes, there is a random variable that is set on each iteration in recent Perls which causes the hashing algorithm to change. This is a response to a possible denial of service attack on Perl-based applications.

    The basis of the attack is that while on average adding n entries to a hash is O(n), if you encounter the wrong data set it is O(n*n). If you know the hashing algorithm that someone is using you may therefore be able to feed them data that will cause them to use up a surprising amount of CPU time. This makes denial of service attacks easier.

    But now there is no way to predict exactly what hashing algorithm you'll face, making it impossible to construct a dataset that reliably causes Perl to run into this problem.

Re: Randomizing Hash Implementation?
by dave_the_m (Monsignor) on Apr 10, 2005 at 00:10 UTC
    Further to Tilly's description, you can get the old behaviour back by setting an environment variable, eg
    PERL_HASH_SEED=0 perl ...
    Handy for benchmarking or debugging.

    Dave.

Re: Randomizing Hash Implementation?
by nobull (Friar) on Apr 10, 2005 at 00:15 UTC
    Venerable monks, someone just told me that their perl (v5.8.1-RC3/darwin) stored hashes differently between different invocations of a program.
    Yes, this is to avoid denial of service attacks based on deliberately feeding a Perl pathological data.
    Does anybody know if there's a random generator in the hash algorithm of some perl implementations?
    Yes, people who compulsively read the the release notes. :-)
Re: Randomizing Hash Implementation?
by tlm (Prior) on Apr 10, 2005 at 00:11 UTC

    That's curious. Here's a shot in the dark: What happens if you srand( 0 ) before populating the hash? (I'm surrounded by Linux boxes, so I can't test myself.)

    the lowliest monk

Re: Randomizing Hash Implementation?
by Anonymous Monk on Apr 10, 2005 at 01:30 UTC
    assuming
    keys HASH Returns a list consisting of all the keys of the named hash. (In scalar context, returns the number of keys.) The keys are returned in an apparently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be the same order as either the "values" or "each" function produces (given that the hash has not been modified). Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons (see "Algorithmic Complexity Attacks" in perlsec).
      It's only assuming if one doesn't verify one's assumptions. The OP clearly did that, so noone was made an ass.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://446319]
Approved by chas
Front-paged by tlm
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (5)
As of 2023-02-05 13:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (31 votes). Check out past polls.

    Notices?