OS Detection CPU Performance Issues

[fyodor]

As Nmap's OS detection system has expanded over the years, to the point it now has more than 5,600 fingerprints, some of the algorithms are not scaling as well as they could be and performance has bogged down in some cases. We received a report recently with CPU graphs showing that OS detection seemed to be by far the most CPU intensive part of their scan. @dmiller-nmap has at least partially addressed this already, but I'm creating this issue to publicly document it and the fix.

[fyodor]

I'm leaving this open in case Dan is working on other improvements to this as well, but here are some notes he sent with an initial fix:

a) The CPU usage increases during OS fingerprinting because of the work of comparing each observation fingerprint with each print in the database, which currently contains 5600+ fingerprints of 119 tests each.

b) The time during which no packets are being sent appears to correspond with the fingerprint matching CPU spike. During this phase, Nmap is not doing any network task, but is instead processing results and outputting them.

The period immediately before this shows relatively little network utilization, which is because of the more conservative timing settings that OS scanning uses; if a probe is dropped, the entire fingerprint must be reattempted, so we have less tolerance for network drops than during port scan. Still, we are always open to opportunities to improve performance, so we will look into improving throughput during OS scanning.

Finally, in response to this report I profiled Nmap during an OS detection scan and found that nearly half the CPU time was being spent in one function, expr_match(), which is used to match an observed value with one from the database. I found I was able to considerably improve this function by removing unused functionality and avoiding a string copy operation, which reduced overall CPU time spent on OS matching by 50%. Other improvements may occur prior to next release, but for now, this change can be seen here: df1874c