Re: [PATCH] Add the ability to generate quality random IPs without any duplicates

[Brandon Enright <bmenrigh () ucsd edu>]

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

On Tue, 8 Sep 2009 17:09:38 -0700
Fyodor <fyodor () insecure org> wrote:

> On Wed, Sep 02, 2009 at 02:30:21AM +0000, Brandon Enright wrote:
> > This change was committed in r15396.  I included better
> > documentation and links than in my original patch.
>
> Thanks, it is working well (no duplicates) in my testing.

Excellent.  I spent a lot of time thinking about how to do it so I'm
glad it works ;-)

> > I was going to boast that this generator is slightly faster than RC4
> > and while that's true, ip_is_reserved() is so slow the majority of
> > the time isn't being spent in the generator.  I've been thinking of
> > ways to optimize ip_is_reserved() to make it much faster and still
> > maintainable.  If I come up with something good I'll send a patch.
>
> On my system, "nmap -sL -n -iR 1000000" generates and prints more than
> 75,000 IPs per second.  So IP generation (even with ip_is_reserved) is
> already so fast as to be essentially immaterial for any scans.  We
> need to optimize the slow parts of Nmap.  But if improving
> ip_is_reserved makes is cleaner and easier to maintain, and improves
> speed as a side effect, I'm all for it.
>
> This technique might be useful for improving the port randomization
> code, though I'm also not sure if that time is ever material to
> performance.  It would take the longest with a -p- scan.
>
> Cheers,
> -F

I take my slander of ip_is_reserved() back.  I thought that the
slowness was due to that routine.  Turns out, most of the slowness has
to do with the internal processing of a target and printing the
results.  75k IPs is pretty fast taking that into account.

Here's the benchmarks:

With Nmap as it is right now I get 151k IP/s:

$ time ./nmap -iR 10000000 -sL -n -oN - > /dev/null

real    1m6.336s
user    1m1.382s
sys     0m2.096s


If I take out is_ip_reserved() I get 161k IP/s.  This isn't actually a
measurable speedup because the generator needs to be called 25% less
without the reserved check:

$ time ./nmap -iR 10000000 -sL -n -oN - > /dev/null

real    1m2.688s
user    1m0.780s
sys     0m1.892s


But, if I make Nmap cycle the generator for each IP it returns (4.2B
IPs) then I get 186M IP/s:

$ time ./nmap -iR 1 -sL -n -oN - > /dev/null

real    0m23.948s
user    0m23.639s
sys     0m0.036s


I feel bad because Patrick privately sent me a new implementation of
ip_is_reserved() that uses a lookup table.  In thinking about it, the
long case statement we have in the routine will be turned into a jmp
lookup table by GCC which is mostly the same thing as Patrick's patch.

So long story short, we don't (and shouldn't!) change anything.  It's
fast right now.  Hopefully Patrick isn't too miffed...

Brandon

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.11 (GNU/Linux)

iEYEARECAAYFAkqm+cYACgkQqaGPzAsl94KaSgCgg4Qvxxcq3/cWvm6pA9/ntlm+
48UAoKZ8wdhaO6kXGuuvMzEZr8dq1dwS
=I7tm
-----END PGP SIGNATURE-----

_______________________________________________
Sent through the nmap-dev mailing list
http://cgi.insecure.org/mailman/listinfo/nmap-dev
Archived at http://SecLists.Org