-----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-----
_______________________________________________
Dailydave mailing list
Dailydave_at_lists.immunitysec.com
http://lists.immunitysec.com/mailman/listinfo/dailydave
Received on Apr 01 2008
Intro
