Re: Qscan in NSE: qscan.nse

[Brandon Enright <bmenrigh () ucsd edu>]

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

On Fri, 9 Apr 2010 01:26:58 +0000
Brandon Enright <bmenrigh () ucsd edu> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Thu, 8 Apr 2010 23:51:08 +0000
> Brandon Enright <bmenrigh () ucsd edu> wrote:
> [...]
> > QScan currently sends slowly and measures latency carefully one at a
> > time.  What if, instead it just blasted a constant stream of probes
> > at many ports at once and used statistics of large numbers rather
> > than "being careful" to factor out measurement jitter to classify
> > ports?
> >
> > If the stddev is large then a larger N counteracts that.  We could
> > probably blast a large N worth of packets at ports much faster and
> > get just as good (if not better) a confidence interval than we
> > currently do by going slow to keep N small and the stddev small.
> >
> > I guess what I'm saying is, if we send 10 probes carefully we get
> > one confidence interval.  If we sends 100 probes very fast we get
> > another. I *think* 100 will trump 10 even if the 100 are sent in
> > less time than the 10.
>
> Put more concretely, a normal confidence interval is:
>
> {mu - z[a/2] * (sigma/sqrt(n)), mu + z[a/2] * (sigma/sqrt(n))}
>
> Since mu and z[a/2] is the same on both sides for a given port and
> confidence interval, what matters is the sigma/sqrt(n)
>
> If that term increases the interval increases and vice versa.
>
> So, if we go from n = 10 to n = 100, sigma can increase by 3.1x.  We
> also wouldn't need to bother with a t-dist with a larger n.
>
> So the question then becomes:
>
> Can we send 100+ probes quickly to many ports in parallel much
> faster than the time it currently takes us to send 10 probes serially
> while not increasing our measured stddev more than 3.1x?  I think the
> answer is yes.  I think the time needed is quite a bit less too.
>
> If this idea is worth considering we need to take data to see what
> happens to the stddev when qscanning quickly.
>
> Doug, I'm interested in your thoughts.  Feel free to tell me why I'm
> being stupid :-)
>
> Brandon


Please forgive me for replying to myself (once again!).

I decided to test my idea of probing faster.  My results are very
promising.

I tested the following way.  First I sent 10 packets at 1pps to an open
port, roughly like qscan.  I then sent 100 packets at 10pps which takes
the same amount of time.  I then sent 100 packets at 100pps for 10x
time savings.

First, I did scanme.insecure.org on port 80.  Here are those results:


$ time sudo hping scanme.insecure.org -p 80 -S -i 1 -c 10 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      10.0000
Min:    13.5000
Max:    13.9000
Avg:    13.6600
Sum:    136.6000
Var:    0.0249
StdDev: 0.1578
95% confidence interval for mean: [13.0402, 14.2798]

real    0m9.026s
user    0m0.009s
sys     0m0.006s


$ time sudo hping scanme.insecure.org -p 80 -S -i u100000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      99.0000
Min:    13.3000
Max:    14.1000
Avg:    13.6596
Sum:    1352.3000
Var:    0.0249
StdDev: 0.1577
95% confidence interval for mean: [13.4626, 13.8566]

real    0m9.932s
user    0m0.011s
sys     0m0.010s


$ time sudo hping scanme.insecure.org -p 80 -S -i u10000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      99.0000
Min:    13.3000
Max:    15.7000
Avg:    13.6707
Sum:    1353.4000
Var:    0.0674
StdDev: 0.2596
95% confidence interval for mean: [13.4737, 13.8677]

real    0m1.022s
user    0m0.007s
sys     0m0.014s


As you can see, increasing the probes from 10 to 100 improves the
confidence interval much more than sending fast hurts it.


Then I tried a host witch MUCH higher latency (baidu.cn):


$ time sudo hping 61.135.163.94 -p 80 -S -i 1 -c 10 2>&1 | egrep 'len=.*rtt' | sed -r 's/^.*rtt=([0-9.]+).*$/\1/g' | 
./conf_int.pl 
N:      10.0000
Min:    210.6000
Max:    211.6000
Avg:    210.9600
Sum:    2109.6000
Var:    0.0804
StdDev: 0.2836
95% confidence interval for mean: [210.3402, 211.5798]

real    0m9.223s
user    0m0.004s
sys     0m0.011s


$ time sudo hping 61.135.163.94 -p 80 -S -i u100000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      99.0000
Min:    210.7000
Max:    213.2000
Avg:    211.0596
Sum:    20894.9000
Var:    0.1398
StdDev: 0.3739
95% confidence interval for mean: [210.8626, 211.2566]

real    0m10.128s
user    0m0.010s
sys     0m0.015s


$ time sudo hping 61.135.163.94 -p 80 -S -i u10000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      99.0000
Min:    210.6000
Max:    211.4000
Avg:    210.9960
Sum:    20888.6000
Var:    0.0322
StdDev: 0.1795
95% confidence interval for mean: [210.7990, 211.1929]

real    0m1.218s
user    0m0.005s
sys     0m0.014s


Again, sending 100 probes really fast gives better data than 10 probes slowly.

Next I decided to flood scanme.insecure.org with 10k pps to port 25 and
simultaneously run the same test as before to port 80:


bmenrigh@gamma ~ $ sudo hping scanme.insecure.org -p 25 -S -i u100
[...]
- --- scanme.insecure.org hping statistic ---
924772 packets tramitted, 924378 packets received, 1% packet loss
round-trip min/avg/max = 13.2/14.1/26.7 ms


$ time sudo hping scanme.insecure.org -p 80 -S -i 1 -c 10 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      10.0000
Min:    13.5000
Max:    15.7000
Avg:    13.7900
Sum:    137.9000
Var:    0.4588
StdDev: 0.6773
95% confidence interval for mean: [13.1702, 14.4098]

real    0m9.033s
user    0m0.032s
sys     0m0.168s


$ time sudo hping scanme.insecure.org -p 80 -S -i u100000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      99.0000
Min:    13.4000
Max:    17.5000
Avg:    13.7030
Sum:    1356.6000
Var:    0.1740
StdDev: 0.4171
95% confidence interval for mean: [13.5060, 13.9000]

real    0m9.937s
user    0m0.039s
sys     0m0.190s


$ time sudo hping scanme.insecure.org -p 80 -S -i u10000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      99.0000
Min:    13.4000
Max:    14.5000
Avg:    13.6667
Sum:    1353.0000
Var:    0.0229
StdDev: 0.1512
95% confidence interval for mean: [13.4697, 13.8637]

real    0m1.021s
user    0m0.012s
sys     0m0.031s


The 10k pps flood does not appear to change the results in any way.

Finally, Fyodor didn't want me to send 100k pps to his machine so I
volunteered Google:


$ sudo hping 66.102.7.104 -p 443 -S -i u10
[...]
3415452 packets tramitted, 1489892 packets received, 57% packet loss
round-trip min/avg/max = 0.0/4.1/12.9 ms


$ time sudo hping 66.102.7.104 -p 80 -S -i 1 -c 10 2>&1 | egrep 'len=.*rtt' | sed -r 's/^.*rtt=([0-9.]+).*$/\1/g' | 
./conf_int.pl 
N:      9.0000
Min:    5.9000
Max:    36.1000
Avg:    20.3667
Sum:    183.3000
Var:    116.7525
StdDev: 10.8052
95% confidence interval for mean: [19.7133, 21.0200]

real    0m10.036s
user    0m0.133s
sys     0m1.080s


$ time sudo hping 66.102.7.104 -p 80 -S -i u100000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 
's/^.*rtt=([0-9.]+).*$/\1/g' | ./conf_int.pl 
N:      91.0000
Min:    5.3000
Max:    499.6000
Avg:    35.1593
Sum:    3199.5000
Var:    7357.2638
StdDev: 85.7745
95% confidence interval for mean: [34.9539, 35.3648]

real    0m10.988s
user    0m0.125s
sys     0m1.205s


$ time sudo hping 66.102.7.104 -p 80 -S -i u10000 -c 100 2>&1 | egrep 'len=.*rtt' | sed -r 's/^.*rtt=([0-9.]+).*$/\1/g' 
| ./conf_int.pl 
N:      99.0000
Min:    5.2000
Max:    967.0000
Avg:    67.3515
Sum:    6667.8000
Var:    23326.6680
StdDev: 152.7307
95% confidence interval for mean: [67.1545, 67.5485]

real    0m2.064s
user    0m0.024s
sys     0m0.245s


Note that each test here had packet loss and got worse the faster it
went.  Clearly there is a rate at which we hurt results.  We shouldn't
send 100k pps with Qscan...  Testing against scanme.insecure.org though
shows that at least on some hosts, we can go really fast without
hurting our results -- we might even help them with more probes.

I have attached my conf_int.pl script.  If somebody else has a box
doing DNAT they want to test I'd love to see what happens using the
above methodology.

Brandon

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

iEYEARECAAYFAkvGZIEACgkQqaGPzAsl94LwowCgvWrdWLZ1vZ8fnTRXNSHP8dg9
dQ0An36LouKOP5WHh2Dqg+/eMWOF57zw
=3J76
-----END PGP SIGNATURE-----

Attachment: conf_int.pl
Description:

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