To get a trial key
fill out the form below
Team license
Enterprise license
** By clicking this button you agree to our Privacy Policy statement

Request our prices
New License
License Renewal
--Select currency--
USD
EUR
RUB
* By clicking this button you agree to our Privacy Policy statement

Free PVS-Studio license for Microsoft MVP specialists
** By clicking this button you agree to our Privacy Policy statement

To get the licence for your open-source project, please fill out this form
** By clicking this button you agree to our Privacy Policy statement

I am interested to try it on the platforms:
** By clicking this button you agree to our Privacy Policy statement

Message submitted.

Your message has been sent. We will email you at


If you haven't received our response, please do the following:
check your Spam/Junk folder and click the "Not Spam" button for our message.
This way, you won't miss messages from our team in the future.

>
>
>
Catastrophic backtracking error in regu…

Catastrophic backtracking error in regular expressions

Oct 07 2022

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:

CatastrophicBacktrackingError/image1.png

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:

CatastrophicBacktrackingError/image2.png

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).

Latest articles:

Poll:

Comments (0)

Next comments
Unicorn with delicious cookie
Our website uses cookies to enhance your browsing experience.
Accept