Catastrophic backtracking error in regular expressions

The catastrophic backtracking error occurs when you're checking a string of a certain length against a vulnerable regular expression. As a result of this error, the regular expression evaluation time grows exponentially, depending on the length of the input string.

In regular expressions, catastrophic backtracking becomes possible because their evaluation algorithm is of the naïve nature.

This evaluation algorithm is considered naïve because it has to check all cases when a string may fit a template. Only then can the algorithm conclude there are no matches.

If there is an extremely large number of strings that may fit a template, then checking all possible matches takes an unreasonably large amount of time. If there are no matches, this is the catastrophic backtracking error.

The table below shows a few possible matches of the 'xxxxy' string with the '(x+)+y' template:

Processing the 'xxxxy' string with the '(x+)+y' regular expression causes no issues since the string fully matches the template and contains few characters.

However, if you, for example, delete the 'y' character and increase the number of 'x' characters by 6 times, the evaluation time of the regular expression greatly increases.

You can see the correlation between the evaluation time of the '(x+)+y' regular expression and the length of an input string of the 'xx....xx' type on the graph below:

A regular expression is vulnerable to the catastrophic backtracking error if it meets the following criteria:

• There are two subexpressions: one of them is included into the other, one of the following quantifiers is applied to each subexpression: '*', '+', '*?', '+?', '{...}'. In the example above, the 'x+' subexpression is included into '(x+)+'.
• There is a string that can possibly be matched with both subexpressions (the 'xxxx' string may fit both the 'x+' and '(x+)+' templates).

244

0

0

0

SHARE

We can email you a selection of our best articles once a month