Worst Case Analysis for Regular Expressions

Question

Are there any tools that will take a particular regular expression and return the worst case scenario in terms of the number of operations required for a certain number of characters that the regular expression is matched against?

So for example, given a (f|a)oo.*[ ]baz, how many steps might the engine possibly go though through to match 100 characters?

I would also be interested if there is a tool that can take a bunch of text samples and show the average operations for each run.

I realize this will depend a lot on the engine used and the implementation -- but I am ignorant as to how common this is. So if it is common for many languages (making my question too vague) I would be particularly interested in Perl and Python.

Excellent question! Obviously it will depend on the regex. It's well-known that pure regexes (even like the `(x+x+)+y` example referenced below) admit a pure finite-state machine automata, but that common regex libraries actually implement those with backtracking, in large part to support fancy stuff like context. A tool like you describe would be great at catching http://en.wikipedia.org/wiki/Regular_expression_Denial_of_Service_-_ReDoS — Raph Levien, Jan 19 '11 at 02:57

score 21 · Answer 1 · edited Jul 08 '11 at 23:27

21

Regexbuddy's debugger shows how many steps engine would take to conclude match or not on a given sample. More information on catastrophic backtracking and debugging regular expressions.

catastrophic backtracking shown in RegexBuddy

PS: It is not free but they offer a 3-month money-back guarantee.

edited Jul 08 '11 at 23:27

Jeff Atwood

63,320
48
150
153

answered Jan 19 '11 at 02:35

Himanshu

1,989
16
12

1

I was playing with that -- Jeff has been a fan of it: http://www.codinghorror.com/blog/2004/07/my-buddy-regex.html . But I was thinking a little bit more programmatic and geared toward optimization -- if that makes sense. – Kyle Brandt Jan 19 '11 at 14:27

score 10 · Answer 2 · answered Jul 08 '11 at 23:20

Note that it depends on the engine. While regex theory is based on straight automata theory, most of the engines are not strict translations of those theories. For this reason, for instance, some engines incur in exponential time while strict NFA processing would not.

score 7 · Answer 3 · edited May 23 '17 at 12:14

7

You might get what you're looking for something like using re.compile with re.DEBUG. See this excellent answer from the Python Hidden Features Community wiki for an extensive explanation.

edited May 23 '17 at 12:14

Community

1
1

answered Jul 08 '11 at 23:23

Yahel

37,023
22
103
153

Worst Case Analysis for Regular Expressions

3 Answers3