Nmap Development mailing list archives
Re: RFC: patch to skip some service matches
From: David Fifield <david () bamsoftware com>
Date: Wed, 24 Aug 2016 10:23:40 -0600
On Wed, Aug 24, 2016 at 12:20:37AM -0500, Daniel Miller wrote:
List, I've spent probably too much time today enhancing Nmap's service matching system to try to reduce CPU time spent in regular expression matching. Unfortunately, I can't tell whether it has improved anything yet, so I'm asking for help testing. Since this is a CPU-time enhancement, it would only affect scans which are CPU-bound. For this reason, I've CC'd Tudor and Brandon, as their GSoC project resulted in speedups of certain large scans due to algorithmic improvements, and I hope they can test. The change involves inspecting each match line in nmap-service-probes to see if it is part of a contiguous group of match lines that will only ever match a string starting with a given single byte. Already, this means we are targeting only the very fastest match lines, so chances are good there won't be noticeable improvement. The first such match in a group will link to the last one (by index) so that the entire group can be skipped if the first match fails because of an incorrect initial byte. There are groups of hundreds of such contiguous match lines in a few places: FTP matches starting with "2", SSH matches starting with "S", and HTTP matches starting with "H" for instance.
I've thought about this problem too. I'm intrigued by the Rust "RegexSet" API: https://doc.rust-lang.org/regex/regex/struct.RegexSet.html "A regex set corresponds to the union of two or more regular expressions... it will also report *which* regular expressions in the set match." A RegexSet feels like the "right" way to do our kind of matching. But I haven't found an equivalent API in PCRE, or in any library other than Rust's. It presumably requires the RE engine to use a linear-time matching algorithm (as in https://swtch.com/~rsc/regexp/regexp1.html) so that matching the union of many REs will be faster than matching each one individually in turn--the NFA implementation would do your first-byte optimization implicitly. You could cobble together a poor man's RegexSet using binary search. First, construct an RE that is the union of all the REs in the set: re_1|re_2|re_3|...|re_n If it fails to match, then none of the component REs matches. Otherwise, split the set into two halves and see if either of them matches: re_1|re_2|...|re_{n/2} re_{n/2+1}|re_{n/2+2}|...|re_n Continue recursing, preferring leftmost matches, until you get to a single RE that matches. This way you only need log(n) match operations instead of n. But: it'll only be faster if PCRE applies some optimization such that matching a large union is not basically equivalent to trying each component RE in turn. _______________________________________________ Sent through the dev mailing list https://nmap.org/mailman/listinfo/dev Archived at http://seclists.org/nmap-dev/
Current thread:
- RFC: patch to skip some service matches Daniel Miller (Aug 23)
- Re: RFC: patch to skip some service matches David Fifield (Aug 24)
- Re: RFC: patch to skip some service matches Daniel Miller (Aug 24)
- Re: RFC: patch to skip some service matches David Fifield (Aug 24)
- Re: RFC: patch to skip some service matches Daniel Miller (Aug 24)
- Re: RFC: patch to skip some service matches David Fifield (Aug 24)