Dailydave mailing list archives
Why you care about this sort of Python bug.
From: Dave Aitel <dave () immunityinc com>
Date: Tue, 01 Apr 2008 17:11:24 -0400
-----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@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----- _______________________________________________ Dailydave mailing list Dailydave () lists immunitysec com http://lists.immunitysec.com/mailman/listinfo/dailydave
Current thread:
- Why you care about this sort of Python bug. Dave Aitel (Apr 01)
- Re: Why you care about this sort of Python bug. Imri Goldberg (Apr 02)
- Re: Why you care about this sort of Python bug. Michel Arboi (Apr 03)
- Re: Why you care about this sort of Python bug. Florian Weimer (Apr 07)
- Re: Why you care about this sort of Python bug. Michel Arboi (Apr 07)
- Re: Why you care about this sort of Python bug. Michel Arboi (Apr 03)
- Re: Why you care about this sort of Python bug. Imri Goldberg (Apr 02)