Re: Review: Angry IP Scanner

[Brandon Enright <bmenrigh () ucsd edu>]

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

On Fri, 6 Jun 2008 00:28:31 -0700 or thereabouts doug () hcsw org wrote:

> On Fri, Jun 06, 2008 at 02:05:52AM +0000 or thereabouts, Brandon
> Enright wrote:
> > I'm not aware of any generic algorithm, method, or technique that
> > could generate numbers in some arbitrary set of ranges without
> > duplicates that is both fast and memory efficient.
>
> Out-of-core sorting. Here's what I do if I need a random ordering of
> 10+ million records:
>
> cat input | perl -ne 'print int(rand()*99999999)." $_"' | sort -n |
> perl -ne 's/^\d+ // and print' > output
>
> I call it the frax0r-shuffle (tm) patentz pending all rights
> reserved ;)
>
> Doug
>
> PS. There are ways of pipelining operations in and improving disk
> IO but I think I've given the script kidz too much info already.

Hi Doug,

Creative.  I'd say though that prepending a random number to your
target list to sort isn't memory efficient.  Even if Gnu sort is good
about sorting in chunks, you still need your entire list to be sorted
stored somewhere.

The problem I was getting at is this:

Say you wanted to scan 5000 random IPs from:

a.b.0.0/16
c.d.e.0/24

Note that I don't intend the /24 get 1/2 of the scans, I mean it
should get 1/256 of the target IPs.  It may be reasonable to randomly
sort 65536+256 IPs and then pick from the top.  It wouldn't be
reasonable though if you wanted to scan 5000 out of 10.0.0.0/8.

Even if duplicates were fine, I can't think of a very clean way to
generate numbers uniformly in a set of ranges like that.  There is a
clean solution if the ranges are on nice power-of-two boundaries like
the example above but random IPs in uglier ranges like:

a.b.40-64.d
e.f.g.1-254

Start to get rather messy.

One way to do it would be to limit to one specified range at a time and
allow for a bit mask (CIDR would be optional short-hand).

a.b.0.0/255.255.0.0 (a /16)

Or a messier but just as easy to implement range:
64.55.123.77/255.7.128.255

We /could/ solve this and implement it but we'd be taking care of a
pretty rare edge-case.  -sL and random sorting is probably best despite
its drawbacks.

Brandon

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

iEYEARECAAYFAkhI8W8ACgkQqaGPzAsl94K1OACeLIW0rjAbBy7IcwRtI78czsR+
05cAniUHqNBUDLxDsfdoWkXlKuOnysH1
=rki1
-----END PGP SIGNATURE-----

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