[Dailydave] Why you care about this sort of Python bug.

[Dave Aitel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

As many people noticed, this is it. Essentially the following line is 
equivalent with strdup(data+1024).
~            data=data[1024:]

Below you can see an exponential increase in time...
$ time python /tmp/test.py 1000
user    0m0.019s

$ time python /tmp/test.py 10000
user    0m0.043s

$ time python /tmp/test.py 100000
user    0m2.251s

$ time python /tmp/test.py 1000000
user    6m45.435s

Code for test.py:
import sys
count=int(sys.argv[1])
data="A"*count
for i in xrange(len(data)):
~   data=data[1:]

Urls to review, although there's no "one document" that really sums this up.
http://www.skymind.com/~ocrow/python_string/
http://wiki.python.org/moin/PythonSpeed/PerformanceTips

For example, in Python 2.5: 'string += another_string' or "string = 
string + anotherstring" is O(1) thanks to some optimization.

This, on the other hand, is exponential:

dave at ubuntu:~$ cat /tmp/test2.py
import sys
count=int(sys.argv[1])
data=""
datas=[]
for i in xrange(count):
~   data2=data #temporary variable
~   data=data2+"A"


Why do you care? Because these bugs can get quite complex. Often you 
have your "strdup()-like" operation inside a function which is inside a 
loop. And when your IDS is running Lua and an attacker forces this path, 
this means a CPU-exhaustion bug (and lots of missed packets). If you're 
running a remote scanner against someone, this means you get tar-pitted 
when you hit their malicious server.

- -dave
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFH8qT8tehAhL0gheoRAtLdAKCDEmyeR2pCFhuqMhIA5AdrW+3a4wCfSHv3
fMs+URI/fOuk5opQGYD+z4s=
=YDY8
-----END PGP SIGNATURE-----