[Python-Dev] Algoritmic Complexity Attack on Python

[Tim Peters]

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

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
).


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.