Regex catastrophic backtracking

When iteratively developing a regex some bad things may sneak in there. I found out the hard way about "runaway regular expressions" by messing up quantifiers. I didn't notice the problem initially because all my test cases matched. However, this problem typically occurs because it takes too long to figure out a regex does not match a certain string.

Simple example of bad regex from here (x+x+)+y.

This example nicely shows why it can be difficult to identify the problem here (although the nested quantifiers are definitely a red flag). The goal is to match cases like xxxxxxxxxxy:

  1. x+ matches all x's
  2. but then the second x+ fails, because we require at least one more x to match
  3. backtrack one step, first x+ matches xxxxxxxxx, the second matches x
  4. (..)+ is satisfied because the group matched once.
  5. y matches the "y". Done.

However, there is a problem when the "y" is missing from the string.

If you try this regex on a 10x string in RegexBuddy’s debugger, it’ll take 2558 steps to figure out the final y is missing. For an 11x string, it needs 5118 steps. For 12, it takes 10238 steps. Clearly we have an exponential complexity of O(2^n) here. At 19x the debugger bows out because it won't show more than one million steps.

I'm testing this problematic regex over at www.regex101.com and it seems that some engines know how to recognize this problem and return a match, whereas other timeout. The Python engine recognizes a no-match on a long string of x's immediately (0 steps, 0.0ms) which is also maybe why I didn't notice this problem in my own application, since I was building it in Python. Golang also does OK with a no match in 7ms. All Java or JavaScript related engines time out.

For the record, a better regex would be: xx+y or x{2,}y.

Avoid nested quantifiers

  1. Avoid nested quantifiers

Nested quantifiers are repeated or alternated tokens inside a group that is itself repeated or alternated. These almost always lead to catastrophic backtracking.

  1. If you use nested quantifiers, make sure the alternatives in a repeated group are mutually exclusive:

About the only situation where they don’t is when the start of each alternative inside the group is not optional, and mutually exclusive with the start of all the other alternatives, and mutually exclusive with the token that follows it (inside its alternative inside the group). E.g. (a+b+|c+d+)+y is safe. If anything fails, the regex engine will backtrack through the whole regex, but it will do so linearly. The reason is that all the tokens are mutually exclusive. None of them can match any characters matched by any of the others. So the match attempt at each backtracking position will fail, causing the regex engine to backtrack linearly. If you test this on aaaabbbbccccdddd, RegexBuddy needs only 13 steps rather than millions of steps to figure it out.

That is, use contrast.

Some engines can recognize that components are mutually exclusive and make quantifiers possessive automatically (cf. point 3).

  1. Tell the regex engine not to backtrack in cases where it is clear y will not be found

This can be done with a possessive quantifier:

(x+x+)++y

This will essentially tell the regex engine not to backtrack at all if the "y" isn't found:

  1. Match the x's
  2. Try to match "y"
  3. If this fails, we do not backtrack because we know there is no "y" in the part matches by (x+x+)+; otherwise that match would have failed.

You can think of a possessive quantifier as imposing an "all or nothing" deal. So the main point of possessive quantifiers is to make your regex fail faster by making the + throw away all its backtracking positions. (This made me think whether fail faster could be a motto or management principle of sorts).

Note that possessive quantifiers can change the matching if it does require on backtracking. Minimal example on test string "abc"x: ".*" with the greedy wildcard will match, but with the possessive wildcard ".*+" not!

A possessive quantifier is syntactic sugar for an atomic group:

(?>(x+x+)+)y

Notice the difference with the non-capturing group (?: ).

Okay... but unfortunately possessive quantifiers and atomic groups are not available in all engines! I mostly work in Python and Python does not have it implemented, which is a bummer.

What if the regex engine doesn't have possessive quantifiers or atomic groups?

Python native regex engine import re does not support possessive quantifiers, but

The regex module does support possessive quantifiers and atomic groups, so I could consider just switching to that. I find this a bit unhandy because online regex testers afaik only contain the default Python regex engine.

If we have an atomic group (?>...) this can (TODO verify this) be simulated by using a lookahead, capturing it, and then using a backreference to it, as such: (?=(...))\1.

Why does this behave just like an atomic group?

The lookahead (?=...) is called a lookahead assertion because it matches the pattern without consuming it and apparently without the backtracking. We need the backreference because in this we do want to match the group we found in the lookahead.

Python also supports named groups, which may be handier if you have a lot of capturing groups (the meaning of \1 may change during regex development).

(?=(...))\1 then becomes (?=(?P<name>...))(?P=name).

To fix the example with the nested quantifiers we started with, we can thus do (?=(x+x+)+)\1y or (?=(x+x+)+)\1y

Problem I encountered

My offending regex looked something like this:

((?:(voorwaardelijk|proeftijd|niet)[^.\n\r;]*)?((?:gevangenis|detentie|hechtenis|taakstraf|geldboete|vordering)\w*)[^0-9\n\r.;]*(?:\[\w+(?: \d+)?\])?[^0-9\n\r.;]+(?:(?:(\d+) +(?:\(\w+\) +)?((?:dag|maand|jar|jaar|ur|uur)[a-zA-Z]*))?[a-zA-Z ]*(?:(\d+) +(?:\(\w+\) +)?((?:dag|maand|jar|jaar|ur|uur)[a-zA-Z]*))|([\d.,-]+\seuro|€\s?[\d.,-]+))(?:[^.\n\r;]*(voorwaardelijk|proeftijd|niet))?)

I designed this regex to work for phrases like "veroordeelt de verdachte tot een gevangenisstraf voor de duur van 2 jaar en 6 (zes) maanden". All my test cases matched and although the regex was quiet long, I considered my problem solved. I didn't notice the problem with catastrophic backtracking, because this mainly occurs when something does not match and the quantifiers go wild.

In all my test cases, we first have an indication of the punishment (e.g. "gevangenistraf") and then an indication of duration. In the failing test case however, we have that indication of duration before the punishment. The regex will keep looking for the start of the time, like "3 (drie) maanden" but if it isn't there the call stack will explode.

"Beveelt dat een gedeelte, groot 3 (drie) maanden, van deze gevangenisstraf niet tenuitvoergelegd zal worden, tenzij later anders wordt gelast."

I think the problem is in the "connector":

connector = r'(?:\w*[^0-9\n\r.]+){1,2}'  # old version
connector = r'[^0-9\n\r.;]*(?:\[\w+(?: \d+)?\])?[^0-9\n\r.;]+'

Possible solution without using atomic groups: do a positive lookahead for the "number" part. Only match "gevangenistraf" when the number part follows.

Links

  • https://www.regular-expressions.info/catastrophic.html
  • Also: https://www.regular-expressions.info/atomic.html
  • Also: https://www.regular-expressions.info/possessive.html
  • Python re does not support possessive quantifiers or atomic groups, but they can be emulated
  • https://stackoverflow.com/questions/13577372/do-python-regular-expressions-have-an-equivalent-to-rubys-atomic-grouping
  • https://stackoverflow.com/questions/44458122/alternative-to-possessive-quantifier-in-python