Subject: Complexity of :matches ?

From: Michael Haardt <[email-masked]>
Date: Mon, 11 Jul 2005 12:48:37 +0200

Hello,

I just had a user using a wildcard pattern that took a large amount of
CPU time.  Now that this particular problem is solved, I wonder about
":matches".

Does anybody know the complexity order of recognising wildcard patterns,
which are a subset of regular expressions? Is giving users control of
patterns to be matched a security risk?

Michael

---

From: Ned Freed <[email-masked]>
Date: Mon, 11 Jul 2005 08:15:21 -0700 (PDT)

> which are a subset of regular expressions?

The complexity of a naive implementation of greedy glob-matching is pretty
clearly O(M*N**K), where N is the length of the target string, M is the length
of the pattern, and K is the number of *'s present in the pattern, and it is
pretty easy to construct inputs that will exhibit worse-case behavior - all you
need is lots of *'s in a pattern that never matches.

Using a  non-greedy approach makes it much harder to construct inputs that will
take a long time to process, especially if you also do some simple
optimizations like collapsing strings of repeated *'s. In practice this seems
to avoid many of the more common problems, such as when users specify an
argument to :matches that only makes sense to give to :contains, such as
"******** ATTENTION ********".

However, I do not know if simply using an optimized non-greedy approach
actually reduces the computational complexity to something less than O(M*N**K)
for extremely pathological cases. If it doesn't, my guess is that there's some
sort of dynamic programming trick that can get the complexity down to O(N*M) or
something similar. I haven't tried to find such a trick, mostly because we've
never encountered a pathological case when using optimized non-greedy matching
that would make it relevant.

In any case, the computational complexity of glob-style matches is clearly less
than that of regexp, which is hardly surprising given that regexps require
a NFA. This is why we disable regexp support by default in our implementation.

Perhaps it makes sense to recommend a non-greedy approach in the security
considerations section of the base specification? Allowing implementations to
limit the number of *'s they allog in glob-style patterns might also make
sense, if only to catch cases where users used :matches when they intended to
use :contains.

				Ned

P.S. I'm curious what pattern you encountered that took a long time. Mind
sharing it?

---

From: Tim Showalter <[email-masked]>
Date: Mon, 11 Jul 2005 12:50:49 -0700

> for extremely pathological cases.

I had a implementation (wasn't Sieve, but had * and ? and worked the 
same way) that was only O(M^N), that is, the number of stars didn't 
matter.  Barring pathological cases that reduce the match to O(N^2), I 
believe this algorithm is Θ(N).  It's possible to be actually O(M+N) if 
you use Boyer-Moore.

The algorithm I used was just essentially this.
- ? can be handled trivially.
- if the pattern doesn't begin with *
   - handle that leader
- find the next string between stars
   - search for string between the stars
   - search returns a location of that substring
   - no match -> return false
   - we have a match; from now on, search only
     from the location of that match forward
- if the pattern doesn't end with *
   - handle that trailer

That is, for with a pattern like *a*b*c* is three strings, search for 
each of which can be found in best-case O(N) time.  If we search for 'a' 
first and find the first match at position 10, we start searching for 
'b' at position 11.  For a pattern like a*b*c*d*e, we do the same thing 
after making sure the string starts with a and ends with e.

The pathological case for this, like string comparison, is only, uh, 
O((M+N)^2) or so, and then only if you're using naive string comparisons 
(which my implementation did).

Since I'm not sure that I've gotten my point across, let me make a more 
straightforward statement.  If you're doing globbing, and you don't care 
if it's greedy or not, and you're doing recursion, then you're doing 
something wrong.  Finding one match is something that can be done in 
roughly linear time.  Recursion is only necessary for finding the "best" 
match which is not something that's in the base Sieve spec.

I think that this implements right-to-left greedy matching, that is, 
completely ungreedy matching.  If you wanted greedy matching, you might 
be able to get it by doing the search backwards.  I'm real sure that I 
can't prove this.

Tim