[Python-Dev] Algoritmic Complexity Attack on Python

[Scott A Crosby]

On Sat, 31 May 2003 09:17:16 -0400, "Phillip J. Eby" <pje@telecommunity.com> writes:

> At 05:02 PM 5/30/03 -0500, Scott A Crosby wrote:

> But based on the discussion so far, I'm not sure I see how this attack
> would produce an effect that was dramatically disproportionate to the
> amount of data transmitted.

I apologize for not having this available earlier, but a corrected
file of 10,000 inputs is now available and shows the behavior I
claimed. (Someone else independently reimplemented the attack and has
sent me a corrected set for python.) With 10,000 inputs, python
requires 19 seconds to process instead of .2 seconds. A file of half
the size requires 4 seconds, showing the quadratic behavior, as with
the case of perl. (Benchmarked on a P2-450) I thus predict that twice
the inputs would take about 80 seconds.

I can only guess what python applications might experience an
interesting impact from this, so I'll be silent. However, here are the
concrete benchmarks.

Scott