Pour obtenir une clé
d'essai remplissez le formulaire ci-dessous
Demandez des tariffs
Nouvelle licence
Renouvellement de licence
--Sélectionnez la devise--
USD
EUR
RUB
* En cliquant sur ce bouton, vous acceptez notre politique de confidentialité

Free PVS-Studio license for Microsoft MVP specialists
To get the licence for your open-source project, please fill out this form
** En cliquant sur ce bouton, vous acceptez notre politique de confidentialité.

I am interested to try it on the platforms:
** En cliquant sur ce bouton, vous acceptez notre politique de confidentialité.

Votre message a été envoyé.

Nous vous répondrons à


Si vous n'avez toujours pas reçu de réponse, vérifiez votre dossier
Spam/Junk et cliquez sur le bouton "Not Spam".
De cette façon, vous ne manquerez la réponse de notre équipe.

>
>
>
Catastrophic backtracking error in regu…

Catastrophic backtracking error in regular expressions

07 Oct 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
Nous utilisons des cookies pour améliorer votre expérience de navigation. En savoir plus
Accepter