Nmap Development mailing list archives
[RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans)
From: Brandon Enright <bmenrigh () ucsd edu>
Date: Thu, 2 Apr 2009 23:09:57 +0000
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Doug, Developers, In scanning the thousands of services on our network I regularly run into the following error: Warning: Hit PCRE_ERROR_MATCHLIMIT when probing for service http with the regex '^HTTP/1\.0 \d\d\d .*\r\n.*\r\n\r\n.*\t<title>Strongdc\+\+ webserver - Login Page</title>\t' There are a number match lines that trigger this, here are a couple more examples: Warning: Hit PCRE_ERROR_MATCHLIMIT when probing for service http with the regex '^HTTP/1\.0 \d\d\d .*\n.*Server: ADSM_HTTP/([\d.]+)\nContent-type: text/html\n\n<HEAD>\n<TITLE>\nServer Administration\n</TITLE>\n\n<META NAME=\"IBMproduct\" CONTENT=\"ADSM\">\n<META NAME=\"IBMproductVersion\" CONTENT=\"([\d.]+)\">.*Storage Management Server for AIX' Warning: Hit PCRE_ERROR_MATCHLIMIT when probing for service http with the regex '^HTTP/1\.0 \d\d\d .*\n.*Server: ADSM_HTTP/([\d.]+)\r?\n.*<TITLE>\nServer Administration\n</TITLE>.*<META NAME=\"IBMproductVersion\" CONTENT=\"([\d.]+)\">.*<TITLE>\nAdministrator Login\n</TITLE>.*Storage Management Server for Windows' The issue is in the construction of the match over/poorly using the greedy quantifier ".*" as in: "HTTP/1\.0 \d\d\d .*\n.*Server:" The problem arises when matching against services that have a large number of partial matches between the .* constructs that force the engine to backtrack too much while trying to match. In all the cases I've run into this issue I've been able to fix the match by using atomic grouping and lazy quantification. Here is a match diff: * -match http m|^HTTP/1\.0 \d\d\d .*\n.*Server: ADSM_HTTP/([\d.]+)\r?\n.*<TITLE>\nServer ...snip... * +match http m|^HTTP/1\.0 \d\d\d (?>.*?\n).*Server: ADSM_HTTP/([\d.]+)\r?\n.*<TITLE>\nServer ...snip... By changing ".*\n.*" to "(?>.*?\n).*" the match will still work properly but the atomic group can not be backtracked on to cause a MATCHLIMIT error. Note that the first greed quantifier must be made lazy or there are cases where it could consume a \n to farther in the string and won't match properly because it needs to be backtracked and can't be. Rather than fix the handful of these that happen to come up in my scans, I got to thinking about how to recognize one of the patterns that makes these problems. Essentially, any simple string between two .* clauses that can appear in many places in output can cause excessive backtracking. This command will find a list of candidates for this "bad" pattern: $ cat nmap-service-probes | perl -ne 'print $1, "\n" if ($_ =~ /((?!<\\)\.\*[^.*]{0,10}\.\*)/)' In looking through that list, it seems that \r\n and variations on it are the most common problem construction we have: $ cat nmap-service-probes | perl -ne 'print $_ if ($_ =~ m/(?!<\\)\.\*((\\r)?\\n)+\.\*/)' We do have one ".*.*": match http m|^HTTP/1\.0 200 OK\r\n.*<TITLE>Main Menu \[[\w-_.]+\]</TITLE>.*.*<A title=\"Return to Main Menu\" HREF=\"/\">TivoWebPlus</A>|s p/TiveWebPlus Project httpd/ d/media device/ The fix I propose is to change all cases of ".*<newline variations>.*" into "(?>.*?<newline variation>).*" This isn't going to fix ALL of our MATCHLIMIT problems but it should go a long way towards making the problem better. Comments welcome, Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.10 (GNU/Linux) iEYEARECAAYFAknVRcwACgkQqaGPzAsl94IEIQCfa3jJgZ6193FwtmblYQKOYSsZ xJkAnitjzLns5hcwz3w1oiko6SLCHlrN =EGvC -----END PGP SIGNATURE----- _______________________________________________ Sent through the nmap-dev mailing list http://cgi.insecure.org/mailman/listinfo/nmap-dev Archived at http://SecLists.Org
Current thread:
- [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) Brandon Enright (Apr 02)
- Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) doug (Apr 02)
- Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) Brandon Enright (Apr 03)
- Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) doug (Apr 05)
- Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) Brandon Enright (Apr 07)
- Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) Brandon Enright (Apr 03)
- Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans) doug (Apr 02)