New traceroute algorithm, or how to ping and traceroute 110 hosts in under 15 seconds

[David Fifield <david () bamsoftware com>]

Hi all,

I reported some cases where a traceroute could be very slow in
http://seclists.org/nmap-dev/2009/q3/0425.html. Fyodor asked me to try
to make it faster. There's a branch where a new faster traceroute is
almost done.

svn co --username guest --password "" svn://svn.insecure.org/nmap-exp/david/nmap-traceroute
cd nmap-traceroute
./configure && make
./nmap -n -sP -PE scanme.nmap.org/24 --traceroute
# See "256 IP addresses (110 hosts up) scanned in 11.12 seconds"

This traceroute is faster in every case I've tested, though it is still
based fundamentally on the backwards-tracing algorithm implemented by
Eddie Bell. Instead of there being one special reference trace, all
traces are treated equally, and they are merged into a tree structure as
common nodes are found. This results in fewer probes being sent. Also,
probes are parallelized within each host, not just across all hosts.
(The parallelism can result in more packets for small-scale scans
because the probes often shoot past the target.)

Here are some timing results with three trials each for the old and new
algorithms.

nmap -n -sP -PE --traceroute -v scanme.nmap.org/24
Old traceroute      78.99 s  1961 packets sent
                    49.13 s  1957 packets sent
                    89.64 s  1974 packets sent
New traceroute      13.04 s  1598 packets sent
                    11.32 s  1584 packets sent
                    14.16 s  1602 packets sent

nmap -n -sP -PN --traceroute -v scanme.nmap.org
Old traceroute       0.66 s    19 packets sent
                     0.66 s    19 packets sent
                     0.68 s    19 packets sent
New traceroute       0.22 s    26 packets sent
                     0.22 s    26 packets sent
                     0.23 s    26 packets sent

nmap -sP -PN --traceroute -v google.com yahoo.com wikipedia.org
Old traceroute       1.58 s    48 packets sent
                     1.34 s    48 packets sent
                    21.21 s    47 packets sent
New traceroute       3.51 s    56 packets sent
                     0.74 s    54 packets sent
                     3.49 s    57 packets sent

Name resolution of traceroute hops is also faster because duplicate
addresses are culled before passing them to the resolver.

The new algorithm also avoids taking a very long time when the target
doesn't respond to the traceroute probe. Before it was changed to give
up on such targets, the old traceroute could take over 30 minutes to
trace one of them.

nmap -n -sP -PN --traceroute -v microsoft.com
Old traceroute      100.11 s   10 packets sent, no hops found
                    100.12 s   10 packets sent, no hops found
                    100.12 s   10 packets sent, no hops found
New traceroute        6.20 s   64 packets sent, 13 hops found
                      6.21 s   62 packets sent, 13 hops found
                      6.16 s   64 packets sent, 13 hops found

Please test the branch in your usual traceroute scenarios. I think
you'll be happy with the speed but I have a few more ideas to make it
even faster. The parallelism could be increased or made dynamic;
currently it's hardcoded at 10. The count could bail out after five or
so timed-out hops instead of going all the way up to 30. The distance
estimation could be improved; currently it always starts with a TTL of
10, counts down to 1, then counts up again from 11.

David Fifield

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