[PATCH] Save space/time: completedHosts "lifetimes"

[Kris Katterjohn <katterjohn () gmail com>]

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

Hey everyone,

I've been thinking about the completedHosts list used in ultra_scan.  It's
used to hold the hosts which have completed in case a late reply comes.

But if you're doing a larger scan that ends up being quite slow overall, but
with hosts completing throughout, keeping these completed hosts wastes quite a
lot of space.  An example of this situation is a no-ping SYN scan with a large
hostgroup (so a single ultra_scan run is slow).  And there's also the fact
that this list can be traversed (after incompleteHosts) when searching to see
if a received packet is for us or not.  When doing a large scan, Nmap doesn't
have a very strict pcap filter, so there is a potential for the oft traversal
of this large list for essentially no gain.

It doesn't even need to be that massive of a scan to have completed hosts
waiting for a while in this list.  I tested with -T3 and -T4, and had hosts
completing throughout the ultra_scan run.  Any completed hosts would be
sitting for a long time using the slower timing options.

So I propose (patch attached) limiting the lifetime of these hosts to the
standard TCP MSL (two minutes).  This should be ample time for any late
replies, especially since this is after the normal wait period (which is why
the host is classified as "completed").  I would like a shorter time, but I
think this value is a good median for making sure there's more than enough
time for a reply, and still removing hosts from the list often.  I make sure
not to remove a host if it's the one used for port-scan pings, since I don't
think anything stops it from entering this list.

Since one issue is traversing this large list a lot, I have it set to only run
through the list to remove hosts every 1/2 the lifetime, which would be once a
minute per my patch.  And the further along in the scan these traversals
occur, the smaller this list will likely be compared to the list currently
traversed.

This seems to work great in my testing, with a lot of hosts being removed from
the list long before the ultra_scan run is over.  But I'm certainly not a
master of the ultra_scan code, so a subtle bug could have snuck it.  Or a more
obvious one I just haven't run into.  Or maybe there is another reason all of
these hosts are kept around the whole time that I'm not seeing.

So if you could test the patch out and let me know how it goes (especially if
it causes problems), I'd appreciate it.

Thanks,
Kris Katterjohn

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBSNGV6/9K37xXYl36AQLN7xAApuRxUnwPLlCvi7Y2zQMV4WaWvm/AHf1o
3oOrDaFqM08DMqtlBqeB7CpOw8MCkkXMjjdaSVUuP5RicG4+pltFqGIkMy4GQO0E
mRgR1SJe04XtcggciEtUgi8h8R0ddnK2ivilMkW6sbJKk+HSwRmKjoQ6WuX9mewe
PmutvzQYQNaOjB+OdWCPOO1LC5VB5BcWX0Ic/Bw7kRy+FiZAlP+3t2ou3DYCglta
pfIHNIbbrV6AcTKonPDAQlsUAvtAM8o4NI0jc9/L7Zj/yb0vNW1lTuc3mPxJaROa
6OdG583CDcnak8Ev/7q4OcZpZWisOgvYUjM0WdLi/gRpsazTGC4ThLB4gwQUm1N/
fayLXm2NlHTkPpFmYUX/5wZzwu8ACc9NF5CPl4hWfk5Zyrq5juZWhmQR/OhRAVLw
mEDunZbWg0wWhXyQFY/ebYm0cQAtsrwdcPggIxODhAHOTomNuCAhKsJxzKbJpFZI
Lp9OPHVq2lVTCNhiSsz/igdcAAK3fiERmLzFnHbfeqGapv921hBaWmG7SU4d5Hub
Z7C1Kio0InpVGydnIB6ZERwfMVT/G0I93G1+/yn9qZoPouOr/FwVadXMIdUnGS41
M2UbPnn+FX+iGDGbjSyAi6TC8WFFyTSVk3UP9b0yrYrUPJheI+9eaU++DIfAMjCr
y9vr1t8l5xA=
=HrAr
-----END PGP SIGNATURE-----

Index: scan_engine.cc
===================================================================
--- scan_engine.cc      (revision 10219)
+++ scan_engine.cc      (working copy)
@@ -494,6 +494,7 @@
   void retransmitBench();
   
   bool completed(); /* Whether or not the scan of this Target has completed */
+  struct timeval completiontime; /* When this Target completed */
 
   /* This function provides the proper cwnd and ccthresh to use.  It
      may differ from versions in timing member var because when no
@@ -604,7 +605,8 @@
      NULL. */
   HostScanStats *nextIncompleteHost();
   /* Removes any hosts that have completed their scans from the incompleteHosts
-     list.  Returns the number of hosts removed. */
+     list, and remove any hosts from completedHosts which have exceeded their
+     lifetime.  Returns the number of hosts removed. */
   int removeCompletedHosts();
   /* Find a HostScanStats by its IP address in the incomplete and completed
      lists.  Returns NULL if none are found. */
@@ -641,6 +643,10 @@
      completed. We keep them around because sometimes responses come back very
      late, after we consider a host completed. */
   list<HostScanStats *> completedHosts;
+  /* How long (in msecs) we keep a host in completedHosts */
+  unsigned int completedHostLifetime;
+  /* The last time we went through completedHosts to remove hosts */
+  struct timeval lastCompletedHostRemoval;
 
   ScanProgressMeter *SPM;
   PacketRateMeter send_rate_meter;
@@ -1083,6 +1089,7 @@
   numprobes_sent = 0;
   numpings_sent = 0;
   numprobes_replied_to = 0;
+  memset(&completiontime, 0, sizeof(completiontime));
   init_ultra_timing_vals(&timing, TIMING_HOST, 1, &(USI->perf), &USI->now);
   bench_tryno = 0;
   memset(&sdn, 0, sizeof(sdn));
@@ -1482,6 +1489,10 @@
 
   init_perf_values(&perf);
 
+  /* Keep a completed host around for a standard TCP MSL (2 min) */
+  completedHostLifetime = 120000;
+  memset(&lastCompletedHostRemoval, 0, sizeof(lastCompletedHostRemoval));
+
   for(targetno = 0; targetno < Targets.size(); targetno++) {
     if (Targets[targetno]->timedOut(&now)) {
       num_timedout++;
@@ -1678,12 +1689,33 @@
 }
 
   /* Removes any hosts that have completed their scans from the incompleteHosts
-     list.  Returns the number of hosts removed. */
+     list, and remove any hosts from completedHosts which have exceeded their
+     lifetime.  Returns the number of hosts removed. */
 int UltraScanInfo::removeCompletedHosts() {
   list<HostScanStats *>::iterator hostI, nxt;
   HostScanStats *hss = NULL;
   int hostsRemoved = 0;
   bool timedout = false;
+
+  /* We don't want to run this all of the time */
+  if ((unsigned) TIMEVAL_MSEC_SUBTRACT(now, lastCompletedHostRemoval) > completedHostLifetime / 2) {
+    for (hostI = completedHosts.begin(); hostI != completedHosts.end(); hostI = nxt) {
+      nxt = hostI;
+      nxt++;
+      hss = (*hostI);
+
+      /* Keep it if it's our port scan ping host */
+      if (hss == gstats->pinghost)
+        continue;
+
+      if ((unsigned) TIMEVAL_MSEC_SUBTRACT(now, hss->completiontime) > completedHostLifetime) {
+        completedHosts.erase(hostI);
+        hostsRemoved++;
+      }
+    }
+    lastCompletedHostRemoval = now;
+  }
+
   for(hostI = incompleteHosts.begin(); hostI != incompleteHosts.end();
       hostI = nxt) {
     nxt = hostI;
@@ -1722,6 +1754,7 @@
             log_write(LOG_PLAIN, "* %s\n", probespec2ascii((probespec *) (*iter)->pspec(), tmpbuf, sizeof(tmpbuf)));
         }
       }
+      hss->completiontime = now;
       completedHosts.push_front(hss);
       incompleteHosts.erase(hostI);
       hostsRemoved++;


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