[PATCH] Mass rDNS performance

[jah <jah () zadkiel plus com>]

Hello Nmappers,

Following on from the previous discussion on this topic [1][2][3][4]
where it was found that Nmap's reverse dns resolution sent two or three
times more requests than target IPs to be resolved, I've attached a new
patch for nmap_dns.cc with several changes which I'll describe here.


    Statistics

Added counters for some extra response types which will be properly
handled (rather than skipped) and reordered the stats output.  This,
from the comments in nmap_mass_rdns():

#:  Number of DNS servers used
DR: DRopped IPs (no valid responses were received)
OK: Number of fully reverse resolved queries
NX: Number of confirmations of 'No such reverse domain eXists'
SF: Number of IPs that got 'Server Failures'
RF: Number of IPs that got 'Request reFused'
NI: Number of IPs that got 'Not Implemented'
NA: Number of IPs that got a referral (No error and no Answer)
TR: Total number of Responses
TO: Total number of timed-Out requests
TX: Total number of transmissions necessary. The number of domains is
ideal, higher is worse
CN: Total number of successful resolutions of CNAME labels.

e.g.  [#: 2,
DR: 73, OK: 263, NX: 688, SF: 96, RF: 0, NI: 0, NA: 2, TR: 1049, TO: 97,
TX: 1146, CN: 1]

The stats added are: RF, NI, NA, TO and TX.
TR currently represents total transmissions, but this change will cause
it to reflect total responses instead.

The reordering was done to make it a little easier to see the
relationship between each of the stats and to better determine how the
nameservers are responding:

DR + OK + NX == The number of IPs to be resolved.
OK + NX + SF + RF + NI + NA == TR (total responses)
TR + TO == TX (total transmissions)

If, for example, TR+TO does not add-up to TX then it's clear that we're
getting responses that we are ignoring for some reason.  Possibly that
we're not handling some kind of valid response or that there's some evil
trickery going on.


    Capacity

The patch changes the starting and minimum values for the number of
requests outstanding ("capacity") at a given dns server.  This is now 2
requests, down from 10 in current nmap.

Increases in capacity for a server occur whenever we get a valid
response from it and are done like this:

tpserv->capacity += (k / floor(tpserv->capacity));

where k == CAPACITY_STEP == 1 (for good responses, see later)
This produces a nice steady increase which is fast enough (in my
opinion) to reach a capacity suitable for speedy resolution, but not so
fast as to exceed that capacity by too much - which can cause delays as
we wait for requests that were dropped.

Decreases are simply a single decrement every time a request times-out. 
This is a good balance between decreasing enough to recover from
occasions where the optimum capacity is exceeded and not decreasing so
much as to fall very much below the optimum capacity.
Decreases are only made when a timed-out request is detected and there
are no additional decreases when a server has failed to resolve a
request at every attempt (as the current nmap does).

As an example of the difference this can make to both speed and accuracy
of resolution, this is a scan of 4096 hosts with the current nmap (but
with updated stat output) and nmap with the changes to capacity:

- control: 41.45s  [#: 3,
DR: 120, OK: 3960, NX: 16, SF: 0, RF: 0, NI: 0, NA: 0, TR: 3976, TO:
3584, TX: 7560, CN: 0]
- capacity: 23.28s  [#: 3,
DR: 0, OK: 4080, NX: 16, SF: 0, RF: 0, NI: 0, NA: 0, TR: 4096, TO: 257,
TX: 4353, CN: 0]

The result isn't always this good and under certain conditions, in terms
of speed, it's worse, but this example serves to illustrate what's
possible  This result is mainly due to not sending so aggressively that
large numbers of requests time-out (more than three thousand in this
case). As a consequence, more responses are received and there's less
waiting for requests to time-out at the end of the reverse resolution
phase of a scan.


    Response Types

More response types are treated as a valid response rather than, as
happens at the moment, ignoring those responses and allowing the
requests to time-out.  This is important because capacity for a server
is decreased whenever a request times-out and there are three response
types that the current nmap will ignore and impose a penalty on any
servers that respond with them:

Request Refused (stat RF)
Request Type Not Implemented (stat NI) and
Referral to Authoritative Nameservers (stat NA)

These are now handled such that capacity is increased when these
responses are received, the requests are not retried at that same server
and the request goes into a queue for the next server if one is
available, otherwise it's dropped.  Capacity increases for these
responses are at half the rate of OK and NX responses.  This helps to
reduce the number of requests sent to servers that respond with these
types in favour of those that respond positively.

I mentioned in my last post on this topic [4] that Server Failure
responses are currently treated in a similar way to responses that are
ignored except that capacity is decreased when such responses are
received and that the request is artificially timed-out rather than
waiting until it's real time-out time (if you know what I mean).  Server
failures are now handled in the same way as the above three response
types except that no capacity change results.  It's unclear (to me)
exactly what causes Server Failure responses and from observation I
guess that different dns implementations dish them out for different
reasons (for example, a resolver might respond with SERVFAIL if requests
it sends aren't responded to quickly enough or because there's a problem
upstream, whereas an authoritative nameserver might respond in this way
because of some mis-configuration).  This uncertainty as to what might
be wrong is the reason I've opted not to increase or decrease capacity
for server failure responses.

These changes to response handling can result in serious improvements in
total time for resolution when such responses are seen.  This is because
a) we're not waiting for requests to time-out when we shouldn't be and
b) we're not retrying requests at the same server when we get these
responses.

More often than not, this means that when we're waiting for a request to
time-out it's because we really didn't get a response.

An example.  This is another scan against 4096 targets with current
nmap, nmap with capacity changes and nmap with both capacity and
response handling changes:

- control: 2665.05s  [#: 2,
DR: 4096, OK: 0, NX: 0, SF: 0, RF: 0, NI: 0, NA: 0, TR: 0, TO: 16384,
TX: 16384, CN: 0]
- capacity: 13312.30s  [#: 2,
DR: 4096, OK: 0, NX: 0, SF: 0, RF: 0, NI: 0, NA: 0, TR: 0, TO: 16384,
TX: 16384, CN: 0]
- responses: 117.88s  [#: 2,
DR: 4096, OK: 0, NX: 0, SF: 0, RF: 0, NI: 0, NA: 8192, TR: 8192, TO: 9,
TX: 8201, CN: 0]

Current nmap tried each request twice at each of two servers (16384). 
The time-out periods when using 2 servers are 2.5s for the first request
sent and 4s for the second so that's 6.5s per request, per server. 
Requests are effectively sent to all servers concurrently so we can say
6.5s per request.  A minimum number of outstanding requests in
maintained (and we never get above minimum because of a lack of
responses) so we can say the total time for resolution for current nmap
under these circumstances is 6.5s * 4096 IPs / 10 == 2662.4 seconds
which is near as dammit to the 2665.05s actually taken.
Nmap with capacity changes is five times slower because we've reduced
starting and minimum capacity by a factor of 5 and that result took
nearly 3 and a quarter hours to obtain.
When we deal with the responses correctly only half the number of
requests need to be sent (no retries at the same server) and capacity is
increased after every response, resulting in a resolution time of less
than 2 minutes.  Note that the stats show 8192 responses which I dubbed
"No error, no Answer" and were actually glue records which referred to
nameservers that are authoritative for the zone.

I had some thoughts about other ways to handle some of the
aforementioned response types:
I think it's unlikely that, generally, we'll see many Not Implemented
responses for PTR requests, but I suppose it is possible if a user
specified --dns-servers on the command line.  I wondered if it might be
a good idea to stop making requests at such a server (after X number of
NI responses), but in the end I decided a) if the user specifies a dns
server, they want us to damn well try the requests there (or else!) and
b) it might be more useful to see that a number of NI responses were
received.
Similarly, a user might specify a server which refers us to
authoritative nameservers for the target IPs specified and I thought it
might be a good idea to parse such responses and a) alert the user to
the referred-to servers, b) make requests at the referred-to servers if
they happen to be ones the user specified (or drop the requests if they
weren't).  I think it unlikely that this response type would be received
from the resolvers in use by the user's machine - so this case is most
likely to happen if the user specified the servers on the commandline
and, again, we ought to do as we're told - hence the reason I didn't
implement any of these ideas.

Whilst trying to resolve a group of IPs belonging to an army dot mil
domain I got an interesting bunch of responses.  The responses passed a
test for those that might contain an error, but they did not and so the
responses were ignored, leaving the requests to time-out, increasing
time for resolution significantly and causing a discrepancy between
TR+TO and TX.  The test checks the fourth byte of the dns response:

// Check that the zero field is all zeros and there is no error condition.
// We don't care if recursion is available or not since we might be querying
// an authoritative DNS server.
if (buf[3] != 0x80 && buf[3] != 0) {

and then compares buf[3] & 0xF against a series of error codes.  Where
there's no match, the response is ignored.
In these particular responses, the DNSSEC AD bit (section 6.1 of
RFC2535) was set and buf[3] was equal to 0xA0.  I was going to add
detection for these, but section 2 "Setting of AD bit" of RFC3655 states:
"The AD bit MUST only be set if DNSSEC records have been requested via
the DO bit [RFC3225] and relevant SIG records are returned."
and so, as we haven't set the DO bit in the request, the response
contravenes the RFC.  I'm unsure whether we should handle these kinds of
(should/dare I call them) mis-configurations and for the moment, have
elected to continue to ignore them.


    Distribution of requests over the available servers

In the current nmap, the number of times a request is tried at a single
server is dependent on the number of available servers:
1 available server - 3 tries
2 or more servers - 2 tries at each.
When a request times-out, that request is retried at the same server
until all tries have been used for that server and then the request will
be put into a queue for another server - the request may be tried at a
maximum of three servers.

Given that the aggressiveness of request sending has been dramatically
reduced, I think that it's now far less likely that a request fails to
elicit a response from a server due to the rate at which requests are
sent and more likely that the requests are being filtered or ignored or
the server is servicing more requests than it can cope with.  It seems
sensible then, to try the request at a different server before retrying
at the same one.

This change attempts to do this in a way which favours more responsive
servers over ones that are less so, as follows:
Each request stores a std::map where the keys are server hostnames and
the values are the remaining number of times that the request may be
tried at the corresponding server.
When deciding which server to try next, we iterate over the list of
servers and sum the ratios of good responses to transmissions for each
server at which there are tries remaining.  Good responses are OK or
NX.  Then the mean of these ratios is calculated and assigned to
"responsiveness_mean".  Next, starting at the current server (the one
just tried) we iterate over the list again (wrapping back round to the
start if necessary) and select the first server at which there are tries
remaining and that has a ratio of good responses to transmissions equal
or greater to responsiveness_mean.  This allows us to step over less
responsive servers when there are more responsive ones available and
means that we spend less time waiting for unresponsive servers.

This bit of debug output (now removed from the code) illustrates the
process:

try next server: current server x.23.242.204 and mean responsiveness is
0.60 (sum 1.80 servs 3)
try next server: TESTING x.33.150.193, tries remaining is 1,
responsiveness is 0.00
try next server: TESTING x.33.148.205, tries remaining is 1,
responsiveness is 0.89
try next server: will try at x.33.148.205, responsiveness is 0.89

Here there were four dns servers.  x.23.242.204 had already been tried
and x.33.150.193 was skipped because its responsiveness value of 0 was
less than the mean of 0.6 (it actually ignored every request).

Later on though, there were still some requests that had been tried
everywhere except the unresponsive server and still had not been
resolved - as we can't be sure that we definitely won't get a response,
we have no choice but to try:

try next server: current server x.33.148.205 and mean responsiveness is
0.00 (sum 0.00 servs 1)
try next server: TESTING x.33.146.204, tries remaining is 0,
responsiveness is 0.96
try next server: TESTING x.23.242.204, tries remaining is 0,
responsiveness is 0.94
try next server: TESTING x.33.150.193, tries remaining is 1,
responsiveness is 0.00
try next server: will try at x.33.150.193, responsiveness is 0.00

In this particular test, only 23 out of 4096 requests were tried at the
unresponsive server and only 5 of those were requests that had failed
elsewhere - the total time taken was reduced by a quarter (10s).

Three caveats:
If there's only one server left at which we're allowed to try, then we
have to try there.
If there's only two servers and one of them is the one we just tried
then we pretty much always want to try at the other - unless it's much
less responsive in which case we'll try the same one again.
responsiveness_mean is capped at 0.9 so that we always try the next
server in the list if it's adequately responsive (rather than skipping
over a near perfectly responsive one).

A related change is that this patch does away with the maximum of 3
servers at which to try a request.  Instead, we'll try them all if
necessary, but if there are three or more servers available, we'll try
once per request at each.  However, if (when using 3 or more servers) a
request times-out, we'll give that request one last chance at the same
server if only 10% or less requests have timed-out at that server.
I think this is a sensible approach which improves the likelihood that
we'll get a response from one of the servers available to us.  In
current Nmap there's the possibility (an edge case, no doubt) that we
didn't try the one server that could resolve our IP because we already
tried at three servers.

These changes to distribution of requests can help enormously when
servers respond with messages other than those that resolve our IP or
inform of No Such Name and they can also help to take advantage of more
reliable servers and talk less to misbehaving ones.


    Unresponsive Servers

At the start of resolution, a list of requests (1 per target IP) is
generated - named new_reqs.  A request is popped off this list right
before being sent down the wire and if that request doesn't get
resolved, it's pushed onto a to_process list for whichever server it
will be sent to next.  When sending requests to a server, its to_process
list is favoured over new_reqs - thus, new_reqs slowly empties and we
can be sure that when it's empty resolution has been attempted for every
target IP.
Servers from which we haven't had a single response will never get a
capacity increase and will remain at CAPACITY_MIN.  Toward the end of
resolution, when new_reqs is empty, any servers from which we haven't
had a single response have their capacity artificially raised to
TURBO_CAPACITY (10).  This helps to clear the to_process queues of such
servers a little faster and reduce the time we spend waiting for these
queues to empty.  We don't do this any earlier than when new_reqs is
empty as increasing capacity prematurely would permit more new_reqs to
be sent to unresponsive servers when they could have instead been sent
to more responsive ones.


    Results

Rather than post rows of test results and extend this already lengthy
post much further, I've posted a some results at [5] which highlight the
differences that these changes will make.  Not posting them here also
means they'll be a little easier to read.


Finally, whilst I'd like to see these changes integrated into nmap as
soon as possible, I think that it would be a good idea if they got some
wider testing.  I've done an awful lot of testing myself and I'm
confident that they're sound improvements, but given that we may be
close to the end of beta testing for the next version of Nmap, I would
advocate maybe merging the changes after release and having the Summer
to see if they suit a wider user-base.
Naturally, I welcome any comments/suggestions about any of the proposed
changes!

Regards,

jah


[1] - http://seclists.org/nmap-dev/2009/q1/0088.html
[2] - http://seclists.org/nmap-dev/2009/q1/0089.html
[3] - http://seclists.org/nmap-dev/2009/q1/0154.html
[4] - http://seclists.org/nmap-dev/2009/q1/0158.html
[5] - http://jahboite.co.uk/files/nmap/rdns_tweak_results.html

--- nmap_dns.cc.orig    2009-03-15 21:48:28.750000000 +0000
+++ nmap_dns.cc 2009-03-18 16:01:10.421875000 +0000
@@ -159,8 +159,8 @@
 
 #include <stdlib.h>
 #include <limits.h>
+#include <map>
 #include <list>
-#include <vector>
 #include <algorithm>
 
 #include "nmap.h"
@@ -183,45 +183,40 @@
 // A batch of num_targets hosts is passed to nmap_mass_rdns():
 //   void nmap_mass_rdns(Target **targets, int num_targets)
 //
-// mass_dns sends out CAPACITY_MIN of these hosts to the DNS
+// mass_dns sends out CAPACITY_START of these hosts to the DNS
 // servers detected, alternating in sequence.
 
-// When a request is fulfilled (either a resolved domain, NXDomain,
-// or confirmed ServFail) CAPACITY_UP_STEP is added to the current
-// capacity of the server the request was found by.
+// When a request is fulfilled (a resolved domain, NXDomain,
+// Request Refused or other valid response) the current capacity of the
+// server the request was found by is increased by CAPACITY_STEP/capacity.
 
-// When a request times out and retries on the same server,
-// the server's capacity is scaled by CAPACITY_MINOR_DOWN_STEP.
-
-// When a request times out and moves to the next server in
-// sequence, the server's capacity is scaled by CAPACITY_MAJOR_DOWN_STEP.
+// When a request times out the server's capacity is reduced by
+// CAPACITY_STEP and the request is passed to the next available server.
 
 // mass_dns tries to maintain the current number of "outstanding
 // queries" on each server to that of its current capacity. The
-// packet is dropped if it cycles through all specified DNS
+// request is dropped if it cycles through all specified DNS
 // servers.
 
 
 // Since multiple DNS servers can be specified, different sequences
-// of timers are maintained. These are the various retransmission
-// intervals for each server before we move on to the next DNS server:
+// of timers are maintained. These are the various read timeout
+// periods for each request attempt at a given server:
 
 // In milliseconds
 // Each row MUST be terminated with -1
 static int read_timeouts[][4] = {
   { 4000, 4000, 5000, -1 }, // 1 server
   { 2500, 4000,   -1, -1 }, // 2 servers
-  { 2500, 3000,   -1, -1 }, // 3+ servers
+  { 2500,     -1, -1, -1 }, // 3+ servers
 };
 
-#define CAPACITY_MIN 10
-#define CAPACITY_MAX 200
-#define CAPACITY_UP_STEP 2
-#define CAPACITY_MINOR_DOWN_SCALE 0.9
-#define CAPACITY_MAJOR_DOWN_SCALE 0.7
+#define CAPACITY_MIN    2
+#define CAPACITY_MAX  200
+#define CAPACITY_STEP   1
+#define CAPACITY_START  2
+#define CAPACITY_TURBO 10
 
-// Each request will try to resolve on at most this many servers:
-#define SERVERS_TO_TRY 3
 
 
 //------------------- Other Parameters ---------------------
@@ -256,20 +251,22 @@
   nsock_iod nsd;
   int connected;
   int reqs_on_wire;
-  int capacity;
+  int reqs_responses;
+  int reqs_poor_responses;
+  int reqs_transmissions;
+  double capacity;
+  int capacity_min;
   int write_busy;
   std::list<request *> to_process;
-  std::list<request *> in_process;
+  std::list<request *> in_process;
 };
 
 struct request_s {
   Target *targ;
   struct timeval timeout;
-  int tries;
-  int servers_tried;
-  dns_server *first_server;
   dns_server *curr_server;
   u16 id;
+  std::map<char*, int> tries_remain;
 };
 
 struct host_elem_s {
@@ -290,9 +287,10 @@
 /* The DNS cache, not just for entries from /etc/hosts. */
 static std::list<host_elem *> etchosts[HASH_TABLE_SIZE];
 
-static int stat_actual, stat_ok, stat_nx, stat_sf, stat_trans, stat_dropped, stat_cname;
+static int stat_actual, stat_dropped, stat_ok, stat_nx, stat_sf, stat_rf, stat_ni, stat_na, stat_resp, stat_to, 
stat_trans, stat_cname;
 static struct timeval starttv;
 static int read_timeout_index;
+static int tries_per_server;
 static u16 id_counter;
 
 static int firstrun=1;
@@ -308,6 +306,7 @@
 #define ACTION_FINISHED 0
 #define ACTION_CNAME_LIST 1
 #define ACTION_TIMEOUT 2
+#define ACTION_NEXT_SERVER 3
 
 //------------------- Misc code --------------------- 
 
@@ -318,16 +317,22 @@
   memcpy(&now, nsock_gettimeofday(), sizeof(struct timeval));
 
   if (o.debugging && (tp%SUMMARY_DELAY == 0))
-    log_write(LOG_STDOUT, "mass_rdns: %.2fs %d/%d [#: %lu, OK: %d, NX: %d, DR: %d, SF: %d, TR: %d]\n",
+    log_write(LOG_STDOUT, "mass_rdns: %.2fs %d/%d [#: %lu, DR: %d, OK: %d, NX: %d, SF: %d, RF: %d, NI: %d, NA: %d, TR: 
%d, TO: %d, TX: %d]\n",
                     TIMEVAL_MSEC_SUBTRACT(now, starttv) / 1000.0,
                     tp, stat_actual,
-                    (unsigned long) servs.size(), stat_ok, stat_nx, stat_dropped, stat_sf, stat_trans);
+                    (unsigned long) servs.size(), stat_dropped, stat_ok, stat_nx, stat_sf, stat_rf, stat_ni, stat_na, 
stat_resp, stat_to, stat_trans);
 }
 
 static void check_capacities(dns_server *tpserv) {
-  if (tpserv->capacity < CAPACITY_MIN) tpserv->capacity = CAPACITY_MIN;
+
+  // Increase to CAPACITY_TURBO minimum capacity if dns server is unresponsive.
+  if (tpserv->reqs_responses == 0 && new_reqs.empty()) tpserv->capacity_min = MIN( CAPACITY_TURBO, 
tpserv->capacity_min +1 );
+  else tpserv->capacity_min = CAPACITY_MIN;
+  
+  // Enforce capacity limits
+  if (tpserv->capacity < tpserv->capacity_min) tpserv->capacity = (double) tpserv->capacity_min;
   if (tpserv->capacity > CAPACITY_MAX) tpserv->capacity = CAPACITY_MAX;
-  if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "CAPACITY <%s> = %d\n", tpserv->hostname, 
tpserv->capacity);
+  if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "CAPACITY <%s> = %d\n", tpserv->hostname, (int) 
tpserv->capacity);
 }
 
 // Closes all nsis created in connect_dns_servers()
@@ -368,14 +373,14 @@
   for(servI = servs.begin(); servI != servs.end(); servI++) {
     tpserv = *servI;
 
-    if (tpserv->write_busy == 0 && tpserv->reqs_on_wire < tpserv->capacity) {
+    if (tpserv->write_busy == 0 && tpserv->reqs_on_wire < floor(tpserv->capacity)) {
       tpreq = NULL;
       if (!tpserv->to_process.empty()) {
         tpreq = tpserv->to_process.front();
         tpserv->to_process.pop_front();
       } else if (!new_reqs.empty()) {
         tpreq = new_reqs.front();
-        tpreq->first_server = tpreq->curr_server = tpserv;
+        tpreq->curr_server = tpserv;
         new_reqs.pop_front();
       }
 
@@ -407,6 +412,7 @@
   int plen=0;
   u32 ip;
   struct timeval now, timeout;
+  int trynum;
 
   ip = (u32) ntohl(req->targ->v4host().s_addr);
   packet[0] = (req->id >> 8) & 0xFF;
@@ -426,16 +432,95 @@
 
   req->curr_server->write_busy = 1;
   req->curr_server->reqs_on_wire++;
-
+  req->curr_server->reqs_transmissions++;
+  
+  trynum = req->tries_remain[req->curr_server->hostname];
+  if (trynum == -1) trynum = 1;
   memcpy(&now, nsock_gettimeofday(), sizeof(struct timeval));
-  TIMEVAL_MSEC_ADD(timeout, now, read_timeouts[read_timeout_index][req->tries]);
+  TIMEVAL_MSEC_ADD( timeout, now, read_timeouts[read_timeout_index][ (tries_per_server - trynum) ] );
   memcpy(&req->timeout, &timeout, sizeof(struct timeval));
 
-  req->tries++;
+  req->tries_remain[req->curr_server->hostname]--;
 
   nsock_write(dnspool, req->curr_server->nsd, write_evt_handler, WRITE_TIMEOUT, req, packet, plen);
 }
 
+
+// returns true if none of the values in the tries_remain map for this request are > 0
+// or the "last-chance" value of -1, that is, we've exhausted all attempts at resolution
+// for this request
+static bool drop_this_request(request* tpreq){
+  std::map<char*, int>::iterator trI;
+
+  for (trI = tpreq->tries_remain.begin(); trI != tpreq->tries_remain.end(); trI++){
+    if (trI->second > 0 || trI->second == -1) return false;
+  }
+  return true;
+}
+
+
+// find another server at which to try a timed-out request and push the request
+// onto its to_process queue - failing that just drop the request.
+static void try_next_server(dns_server * tpserv, request* tpreq) {
+  std::list<dns_server *>::iterator servI;
+  std::list<dns_server *>::iterator curr_servI;
+  int avail_srvs = 0;
+  double responsiveness_sum = 0;
+  double responsiveness_mean = 0;
+  double serv_responsiveness = 0;
+
+  if ( !drop_this_request(tpreq) ) {
+
+    // calculate the mean ratio of good responses to transmissions for any servers we're able to send to.
+    for ( servI = servs.begin(); servI != servs.end(); servI++ ) {
+      
+      if ( tpserv == *servI ) curr_servI = servI; // get iter to current server while we're at it
+      
+      if ( tpreq->tries_remain[(*servI)->hostname] > 0 || tpreq->tries_remain[(*servI)->hostname] == -1 ) {
+        avail_srvs++;
+        if ( (*servI)->reqs_transmissions > CAPACITY_START )
+          responsiveness_sum += ((double) ((*servI)->reqs_responses - (*servI)->reqs_poor_responses)) / 
(*servI)->reqs_transmissions;
+        else
+               // an advantage is given to servers where we haven't yet sent requests,
+               // or only sent a couple and not had time to get a response
+               responsiveness_sum += 1;
+      }
+    }
+  
+    if ( avail_srvs == 2 ) responsiveness_mean = MIN( 0.5, responsiveness_sum / avail_srvs ); // force next server 
unless it's highly unresponsive
+    else if ( avail_srvs > 2 ) responsiveness_mean = MIN( 0.9, responsiveness_sum / avail_srvs ); // if the next 
server is 90% responsive, it's good enough
+    
+    servI = curr_servI;
+    bool complete = 0;
+  
+    // push request into queue of an available server that is at least as responsive as the mean
+    while ( !complete ) {
+      
+      if (++servI == servs.end()) servI = servs.begin(); // wrap around
+      if (servI == curr_servI) complete = 1;             // just in case we try to loop endlessly
+      
+      if ((*servI)->reqs_transmissions > CAPACITY_START )
+        serv_responsiveness = ((double)((*servI)->reqs_responses - (*servI)->reqs_poor_responses)) / 
(*servI)->reqs_transmissions;
+      else
+        serv_responsiveness = 1;  // advantage if we haven't sent many requests
+      
+      if ( (tpreq->tries_remain[(*servI)->hostname] > 0 || tpreq->tries_remain[(*servI)->hostname] == -1) && 
serv_responsiveness >= responsiveness_mean ) {
+        tpreq->curr_server = *servI;
+        (*servI)->to_process.push_back(tpreq);
+        return;
+      }
+    }
+  }
+
+  // **** We've already tried all servers... give up
+  if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: *DR*OPPING <%s>\n", 
tpreq->targ->targetipstr());
+  total_reqs--;
+  stat_dropped++;
+  output_summary();
+  delete tpreq;
+  return;
+}
+
 // Processes DNS packets that have timed out
 // Returns time until next read timeout
 static int deal_with_timedout_reads() {
@@ -467,48 +552,22 @@
       if (tp > 0 && tp < min_timeout) min_timeout = tp;
 
       if (tp <= 0) {
-        tpserv->capacity = (int) (tpserv->capacity * CAPACITY_MINOR_DOWN_SCALE);
-        check_capacities(tpserv);
-        tpserv->in_process.erase(reqI);
-        tpserv->reqs_on_wire--;
-
-        // If we've tried this server enough times, move to the next one
-        if (read_timeouts[read_timeout_index][tpreq->tries] == -1) {
-          tpserv->capacity = (int) (tpserv->capacity * CAPACITY_MAJOR_DOWN_SCALE);
-          check_capacities(tpserv);
-
-          servItemp = servI;
-          servItemp++;
-
-          if (servItemp == servs.end()) servItemp = servs.begin();
-
-          tpreq->curr_server = *servItemp;
-          tpreq->tries = 0;
-          tpreq->servers_tried++;
-
-          if (tpreq->curr_server == tpreq->first_server || tpreq->servers_tried == SERVERS_TO_TRY) {
-            // Either give up on the IP
-            // or, for maximum reliability, put the server back into processing
-            // Note it's possible that this will never terminate.
-            // FIXME: Find a good compromise
-
-            // **** We've already tried all servers... give up
-            if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: *DR*OPPING <%s>\n", 
tpreq->targ->targetipstr());
-
-            output_summary();
-            stat_dropped++;
-            total_reqs--;
-            delete tpreq;
-
-            // **** OR We start at the back of this server's queue
-            //(*servItemp)->to_process.push_back(tpreq);
-          } else {
-            (*servItemp)->to_process.push_back(tpreq);
-          }
-        } else {
-          tpserv->to_process.push_back(tpreq);
+        stat_to++;
+        tpserv->capacity -= (double) CAPACITY_STEP;
+        check_capacities(tpserv);
+        tpserv->in_process.erase(reqI);
+        tpserv->reqs_on_wire--;
+
+        // If we are allowed only 1 attempt at each server and it's a generally responsive server, it might
+        // be worth tying just once more.  We'll make tries_remain for this server -1 ("one last chance") and
+        // test for this value in try_next_server. -1 allows us to avoid getting into a never-ending loop
+        // without keeping a count (we would have to keep count if we just set the value back to 1)
+        if ( tries_per_server == 1 && tpreq->tries_remain[tpserv->hostname] == 0 &&
+        (double) tpserv->reqs_responses / tpserv->reqs_transmissions >= 0.9 ) {
+          tpreq->tries_remain[tpserv->hostname]--;
         }
-
+        // Try the next server
+        try_next_server( tpserv, tpreq );
     }
 
     } while (nextI != tpserv->in_process.end());
@@ -540,25 +599,42 @@
         if (ia != 0 && tpreq->targ->v4host().s_addr != ia)
           continue;
 
-        if (action == ACTION_CNAME_LIST || action == ACTION_FINISHED) {
-        tpserv->capacity += CAPACITY_UP_STEP;
-        check_capacities(tpserv);
-
-        if (result) {
-          tpreq->targ->setHostName(result);
-          addto_etchosts(tpreq->targ->v4hostip()->s_addr, result);
+        tpserv->reqs_responses++;
+        // reset capacity after artificially increasing using CAPACITY_MIN++ in
+        // check_capacities() - we finally got a response from this server
+        if (tpserv->reqs_responses == 1 && tpserv->capacity > CAPACITY_START) tpserv->capacity = CAPACITY_START;
+
+        if (action == ACTION_CNAME_LIST || action == ACTION_FINISHED || action == ACTION_NEXT_SERVER) {
+          
+          // capacity increase rate for SF,RF,NA responses is half that for OK and NX
+          double k = (action == ACTION_CNAME_LIST || action == ACTION_FINISHED) ? CAPACITY_STEP : 0.5 * CAPACITY_STEP;
+          
+          tpserv->capacity += (k / floor(tpserv->capacity));
+          check_capacities(tpserv);
         }
 
-        tpserv->in_process.remove(tpreq);
-        tpserv->reqs_on_wire--;
+        if (action == ACTION_CNAME_LIST || action == ACTION_FINISHED) {
+
+          if (result) {
+            tpreq->targ->setHostName(result);
+            addto_etchosts(tpreq->targ->v4hostip()->s_addr, result);
+          }
 
-        total_reqs--;
+          tpserv->in_process.remove(tpreq);
+          tpserv->reqs_on_wire--;
+          total_reqs--;
 
           if (action == ACTION_CNAME_LIST) cname_reqs.push_back(tpreq);
           if (action == ACTION_FINISHED) delete tpreq;
+        
         } else {
-          memcpy(&tpreq->timeout, nsock_gettimeofday(), sizeof(struct timeval));
-          deal_with_timedout_reads();
+          // had a SERVFAIL, REFUSED, NOT IMPLEMENTED or referral, don't retry this
+          // request at this server
+          tpreq->tries_remain[tpserv->hostname] = 0;
+          tpserv->reqs_poor_responses++;
+          tpserv->in_process.remove(tpreq);
+          tpserv->reqs_on_wire--;
+          try_next_server(tpserv, tpreq);
         }
 
         do_possible_writes();
@@ -678,6 +754,8 @@
     return;
   }
 
+  stat_resp++;
+  
   buf = (unsigned char *) nse_readbuf(evt, &buflen);
 
   // Size of header is 12, and we must have additional data as well
@@ -695,6 +773,8 @@
   if (buf[3] != 0x80 && buf[3] != 0) {
     if ((buf[3] & 0xF) == 2) errcode = 2;
     else if ((buf[3] & 0xF) == 3) errcode = 3;
+    else if ((buf[3] & 0xF) == 4) errcode = 4;
+    else if ((buf[3] & 0xF) == 5) errcode = 5;
     else return;
   }
 
@@ -702,24 +782,50 @@
   answers = buf[7] + (buf[6] << 8);
 
   // With a normal resolution, we should have 1+ queries and 1+ answers.
-  // If the domain doesn't resolve (NXDOMAIN or SERVFAIL) we should have
-  // 1+ queries and 0 answers:
-  if (errcode) {
+  // If the domain doesn't resolve (NXDOMAIN, SERVFAIL or zero answers) we
+  // should have 1+ queries and 0 answers.
+  // A referral will have 0 answers and errcode 0:
+  if (errcode || (answers <= 0 && errcode == 0)) {
     int found;
+    int action;
+
+    switch (errcode){
+      case 3:
+        action = ACTION_FINISHED;
+        break;
+      case 2:
+        action = ACTION_TIMEOUT;
+        break;
+      default:
+        action = ACTION_NEXT_SERVER;
+    }
 
     // NXDomain means we're finished (doesn't exist for sure)
     // but SERVFAIL might just mean a server timeout
-    found = process_result(0, NULL, errcode == 3 ? ACTION_FINISHED : ACTION_TIMEOUT, packet_id);
-
-    if (errcode == 2 && found) {
-      if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: SERVFAIL <id = %d>\n", packet_id);
-      stat_sf++;
-    } else if (errcode == 3 && found) {
-      if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: NXDOMAIN <id = %d>\n", packet_id);
+    found = process_result(0, NULL, action, packet_id);
+    if (found) {
+      switch (errcode) {
+        case 0:
+          stat_na++;
+          break;
+        case 2:
+          stat_sf++;
+          if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: SERVFAIL <id = %d>\n", packet_id);
+          break;
+        case 3:
+          stat_nx++;
+          if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: NXDOMAIN <id = %d>\n", packet_id);
+          break;
+        case 4:
+          stat_ni++;
+          break;
+        case 5:
+          stat_rf++;
+          break;
+      }  
       output_summary();
-      stat_nx++;
-  }
-
+    }
+    
     return;
   }
 
@@ -768,8 +874,8 @@
 
       if (process_result(ia.s_addr, outbuf, ACTION_FINISHED, packet_id)) {
         if (o.debugging >= TRACE_DEBUG_LEVEL) log_write(LOG_STDOUT, "mass_rdns: OK MATCHED <%s> to <%s>\n", 
inet_ntoa(ia), outbuf);
-        output_summary();
         stat_ok++;
+        output_summary();
       }
     } else if (atype == 5 && aclass == 1) {
       // TYPE 5 is CNAME
@@ -866,8 +972,12 @@
     if (o.ipoptionslen)
       nsi_set_ipoptions(s->nsd, o.ipoptions, o.ipoptionslen);
     s->reqs_on_wire = 0;
-    s->capacity = CAPACITY_MIN;
+    s->capacity = CAPACITY_START;
     s->write_busy = 0;
+    s->reqs_responses = 0;
+    s->reqs_poor_responses = 0;
+    s->reqs_transmissions = 0;
+    s->capacity_min = CAPACITY_MIN;
 
     nsock_connect_udp(dnspool, s->nsd, connect_evt_handler, NULL, (struct sockaddr *) &s->addr, sizeof(struct 
sockaddr), 53);
     nsock_read(dnspool, s->nsd, read_evt_handler, -1, NULL);
@@ -1162,6 +1272,12 @@
   total_reqs = 0;
   id_counter = get_random_u16();
 
+  read_timeout_index = MIN(sizeof(read_timeouts)/sizeof(read_timeouts[0]), servs.size()) - 1;
+
+  tries_per_server = 0;
+  while ( read_timeouts[read_timeout_index][tries_per_server] != -1 ) tries_per_server++;
+    
+
   // Set up the request structure
   for(hostI = targets; hostI < targets+num_targets; hostI++) {
     if (!((*hostI)->flags & HOST_UP) && !o.resolve_all) continue;
@@ -1175,10 +1291,12 @@
 
     tpreq = new request;
     tpreq->targ = *hostI;
-    tpreq->tries = 0;
-    tpreq->servers_tried = 0;
     tpreq->id = id_counter++;
 
+    std::list<dns_server *>::iterator srvI;
+    for ( srvI = servs.begin(); srvI != servs.end(); srvI++ )
+      tpreq->tries_remain[(*srvI)->hostname] = tries_per_server;
+
     new_reqs.push_back(tpreq);
 
     stat_actual++;
@@ -1199,8 +1317,6 @@
 
   cname_reqs.clear();
 
-  read_timeout_index = MIN(sizeof(read_timeouts)/sizeof(read_timeouts[0]), servs.size()) - 1;
-
   Snprintf(spmobuf, sizeof(spmobuf), "Parallel DNS resolution of %d host%s.", num_targets, num_targets-1 ? "s" : "");
   SPM = new ScanProgressMeter(spmobuf);
 
@@ -1315,7 +1431,7 @@
 
   gettimeofday(&starttv, NULL);
 
-  stat_actual = stat_ok = stat_nx = stat_sf = stat_trans = stat_dropped = stat_cname = 0;
+  stat_actual = stat_dropped = stat_ok = stat_nx = stat_sf = stat_rf = stat_ni = stat_na = stat_resp = stat_to = 
stat_trans = stat_cname = 0;
 
   // mass_dns only supports IPv4.
   if (o.mass_dns && o.af() == AF_INET)
@@ -1329,14 +1445,20 @@
     if (o.debugging || o.verbose >= 3) {
       if (o.mass_dns && o.af() == AF_INET) {
        // #:  Number of DNS servers used
+       // DR: DRopped IPs (no valid responses were received)
        // OK: Number of fully reverse resolved queries
        // NX: Number of confirmations of 'No such reverse domain eXists'
-       // DR: Dropped IPs (no valid responses were received)
-       // SF: Number of IPs that got 'Server Failure's
-       // TR: Total number of transmissions necessary. The number of domains is ideal, higher is worse
-       log_write(LOG_STDOUT, "DNS resolution of %d IPs took %.2fs. Mode: Async [#: %lu, OK: %d, NX: %d, DR: %d, SF: 
%d, TR: %d, CN: %d]\n",
+       // SF: Number of IPs that got 'Server Failures'
+       // RF: Number of IPs that got 'Request reFused'
+       // NI: Number of IPs that got 'Not Implemented'
+       // NA: Number of IPs that got a referral (No error and no Answer)
+       // TR: Total number of Responses
+       // TO: Total number of timed-Out requests
+       // TX: Total number of transmissions necessary. The number of domains is ideal, higher is worse
+       // CN: Total number of successful resolutions of CNAME labels.
+       log_write(LOG_STDOUT, "DNS resolution of %d IPs took %.2fs. Mode: Async [#: %lu, DR: %d, OK: %d, NX: %d, SF: 
%d, RF: %d, NI: %d, NA: %d, TR: %d, TO: %d, TX: %d, CN: %d]\n",
                  stat_actual, TIMEVAL_MSEC_SUBTRACT(now, starttv) / 1000.0,
-                 (unsigned long) servs.size(), stat_ok, stat_nx, stat_dropped, stat_sf, stat_trans, stat_cname);
+                 (unsigned long) servs.size(), stat_dropped, stat_ok, stat_nx, stat_sf, stat_rf, stat_ni, stat_na, 
stat_resp, stat_to, stat_trans, stat_cname);
       } else {
        log_write(LOG_STDOUT, "DNS resolution of %d IPs took %.2fs. Mode: System [OK: %d, ??: %d]\n",
                  stat_actual, TIMEVAL_MSEC_SUBTRACT(now, starttv) / 1000.0,


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