Re: RFC: patch to skip some service matches

[David Fifield <david () bamsoftware com>]

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/