Defensive programming

[Tim Peters]

[Robin Becker]
> This recently slashdotted paper
>
>
http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html
>
> suggests that many common algorithms (including perl hashing) are
> open to low input DoS attack.
>
> I know that the Timbot and other python 'bots are pretty smart, but
> are there python algorithms that suffer the same vulnerabilities?

Sure.  All dict implementations (hash tables) have O(N**2) worst-case
behavior, over a sequence of N inserts and/or lookups, provoked by a
sufficiently nasty set of N keys.  If an app can't bear that, then it
shouldn't use dicts (or hash tables in Perl, or any similar facility in any
other language).  This isn't news.  What's interesting in the paper is that
some apps that should know better were caught doing this.

> Regular expression matching seems like a pretty easy target for
> some devilish inputs.

Absolutely, yes.  I've corresponded with Scott Crosby about this, and he's
added an example to his web page.  A better link than the paper is this link
to his page discussing the paper:

    http://www.cs.rice.edu/~scrosby/hash/

Someone looking to cause trouble should have an easier time exploiting
widespread non-defensive regexps.