|Perl Language Reference Manual|
by Larry Wall and others
Paperback (6"x9"), 724 pages
RRP £29.95 ($39.95)
Sales of this book support The Perl Foundation! Get a printed copy>>>
22.2.9 Algorithmic Complexity Attacks
Certain internal algorithms used in the implementation of Perl can be attacked by choosing the input carefully to consume large amounts of either time or space or both. This can lead into the so-called Denial of Service (DoS) attacks.
- Hash Function - the algorithm used to "order" hash elements has been changed several times during the development of Perl, mainly to be reasonably fast. In Perl 5.8.1 also the security aspect was taken into account. In Perls before 5.8.1 one could rather easily generate data that as hash keys would cause Perl to consume large amounts of time because internal structure of hashes would badly degenerate. In Perl 5.8.1 the hash function is randomly perturbed by a pseudorandom seed which makes generating such naughty hash keys harder. See for more information. In Perl 5.8.1 the random perturbation was done by default, but as of 5.8.2 it is only used on individual hashes if the internals detect the insertion of pathological data. If one wants for some reason emulate the old behaviour (and expose oneself to DoS attacks) one can set the environment variable PERL_HASH_SEED to zero to disable the protection (or any other integer to force a known perturbation, rather than random). One possible reason for wanting to emulate the old behaviour is that in the new behaviour consecutive runs of Perl will order hash keys differently, which may confuse some applications (like Data::Dumper: the outputs of two different runs are no longer identical). Perl has never guaranteed any ordering of the hash keys, and the ordering has already changed several times during the lifetime of Perl 5. Also, the ordering of hash keys has always been, and continues to be, affected by the insertion order. Also note that while the order of the hash elements might be randomised, this "pseudoordering" should not be used for applications like shuffling a list randomly (use List::Util::shuffle() for that, see List::Util, a standard core module since Perl 5.8.0; or the CPAN module Algorithm::Numerical::Shuffle), or for generating permutations (use e.g. the CPAN modules Algorithm::Permute or Algorithm::FastPermute), or for any cryptographic applications.
- Regular expressions - Perl's regular expression engine is so called NFA (Non-deterministic Finite Automaton), which among other things means that it can rather easily consume large amounts of both time and space if the regular expression may match in several ways. Careful crafting of the regular expressions can help but quite often there really isn't much one can do (the book "Mastering Regular Expressions" is required reading, see "Obtaining and Learning about Perl" (perlfaq2) in the Perl FAQ). Running out of space manifests itself by Perl running out of memory.
- Sorting - the quicksort algorithm used in Perls before 5.8.0 to implement the sort() function is very easy to trick into misbehaving so that it consumes a lot of time. Starting from Perl 5.8.0 a different sorting algorithm, mergesort, is used by default. Mergesort cannot misbehave on any input.
See http://www.cs.rice.edu/~scrosby/hash/ for more information, and any computer science textbook on algorithmic complexity.
|ISBN 9781906966027||Perl Language Reference Manual||See the print edition|