[Python-Dev] Algoritmic Complexity Attack on Python (original) (raw)

Scott A Crosby scrosby@cs.rice.edu
29 May 2003 21:19:57 -0500

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 + targetstring 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. 101010

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