[Python-Dev] Algoritmic Complexity Attack on Python

[Scott A Crosby]

On Thu, 29 May 2003 21:54:20 -0400, Tim Peters <tim.one@comcast.net> writes:

> I've got one meta-comment here:
> 
> [Scott A Crosby]
> > Hello. We have analyzed this software to determine its vulnerability
> > to a new class of DoS attacks that related to a recent paper. ''Denial
> > of Service via Algorithmic Complexity Attacks.''
> 
> I don't think this is new.  For example, a much simpler kind of attack is to
> exploit the way backtracking regexp engines work -- it's easy to find regexp
> + target_string combos that take time exponential in the sum of the lengths
> of the input strings.  It's not so easy to recognize such a pair when it's
> handed to you.  In Python, exploiting unbounded-int arithmetic is another
> way to soak up eons of CPU with few characters, e.g.
> 
>     10**10**10
> 

These ways require me having the ability to feed a program, an
expression, or a regular expression into the victim's python
interpreter.

The attack I discuss only require that it hash some arbitrary input by
the attacker, so these attacks apply in many more cases.

> will suck up all your CPU *and* all your RAM.  Another easy way is to study
> a system's C qsort() implementation, and provoke it into quadratic-time
> behavior (BTW, McIlroy wrote a cool paper on this in '98:
> 
>     http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

This is a very cool paper in exactly the same vein as ours. Thanks.

> I'm uninterested in trying to "do something" about these.  If
> resource-hogging is a serious potential problem in some context, then
> resource limitation is an operating system's job, and any use of Python (or
> Perl, etc) in such a context should be under the watchful eyes of OS
> subsystems that track actual resource usage.

I disagree. Changing the hash function eliminates these attacks on
hash tables.

Scott