Re: [RFC] PCRE MATCHLIMIT and the use of greedy quantifiers (-sV scans)

[Brandon Enright <bmenrigh () ucsd edu>]

On Mon, 6 Apr 2009 06:38:17 +0000
doug () hcsw org wrote:

> On Fri, Apr 03, 2009 at 08:53:26PM +0000 or thereabouts, Brandon
> Enright wrote:
> > > I think we can make the following substitution on all s modifier
> > > match lines (untested):
> > >
> > > s/[.][*]([\]r[\]n|[\]n)*?[.][*]/.*/g
> >
> > I agree but I'd suggest a few modifications.
> >
> > First) we need to make sure your first [.] isn't preceded by a \
> > (easy with negative look-behind).
>
> Aha! Good one. That's very true.
>
> > Second) in most cases the content trailing
> > the .* is still in the header and not in the body.  Lazy
> > quantification with .*? should be generally faster because it won't
> > consume the whole string and then slowly back off.  I'd propose
> > changing to .*? in the case that the trailing content is still in
> > the header and .* when the trailing content is in the body.
>
> I'm not that concerned with this especially if the strings are unique
> enough but there's no harm here either.
>
> > If you're okay with me going through by hand and replacing .*\r?\n.*
> > with .* or .*? I'll get started right away.  There are about 50
> > matches that need work.
>
> Sounds great, thank you. If you like I will take a quick look at the
> patch but I'm sure I don't need to because you will do it fine.
>
> Best,
>
> Doug

Thanks again for your comments on this, Doug.  I ran into a couple of
special cases but they aren't interesting enough to reproduce here.
r12911 has my changes.  I've included the log below.

Brandon


r12911 log:
Handled all of our stray uses of .*\r\n.* and variations like .*\n.*\n
by collapsing them to a single .* and making sure that the DOTALL
(PCRE s modifier) is set on the match.  This should dramatically cut
down on cases where MATCHLIMIT is returned.  See
http://seclists.org/nmap-dev/2009/q2/0086.html for a discussion.  I
chose to only use .* in this patch even though .*? will be faster in
some cases.  I felt the speed benefit of .*? did not outweigh the
relative obscurity of lazy quantifiers.  I have some ideas on how
audit matches for performance and some ideas on optimizations that can
be done.  .*? and friends will have wait.

Attachment: signature.asc
Description:

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