Retour arrière catastrophique

Le retour arrière catastrophique est un phénomène dans les expressions régulières où le moteur prend un temps excessif pour évaluer certains motifs, entraînant une dégradation significative des performances — parfois des secondes, des minutes, voire une durée infinie. Cela se produit car le moteur essaie de faire correspondre des parties de la chaîne de nombreuses façons différentes avant d'abandonner, et le nombre de combinaisons explorées croît de façon exponentielle avec la longueur de l'entrée.

Cette page explique ce qui déclenche le problème, comment reconnaître un motif dangereux et les techniques concrètes pour réécrire une regex afin qu'elle reste rapide. Elle suppose que vous êtes à l'aise avec les quantificateurs et la différence entre la correspondance greedy et lazy.

Pourquoi c'est important : Une seule regex lente appliquée à une entrée fournie par l'utilisateur constitue un véritable vecteur de déni de service (souvent appelé « ReDoS »). Un attaquant n'a qu'à envoyer une courte chaîne conçue pour maximiser le retour arrière afin de bloquer la boucle d'événements de Node.js.

Qu'est-ce qui provoque le retour arrière catastrophique ?

Le retour arrière catastrophique se produit généralement avec des quantificateurs imbriqués — un quantificateur à l'intérieur d'un groupe qui est lui-même quantifié, comme (a+)+. Le danger apparaît quand deux parties du motif peuvent correspondre aux mêmes caractères, ce qui donne au moteur de nombreuses façons superposées de diviser l'entrée. Quand la correspondance échoue finalement, le moteur doit essayer toutes ces divisions avant de pouvoir conclure qu'aucune ne correspond. Voici l'exemple classique :

Si cela ne prend pas beaucoup de temps sur votre ordinateur, vous pouvez ajouter un autre caractère a à str. Alors pourquoi cela prend-il autant de temps ? Analysons-le. Le motif /^(a+)+$/ se compose de :

• ^ qui affirme la position au début de la chaîne.
• (a+) qui correspond à un ou plusieurs caractères a.
• + qui permet au groupe précédent (a+) de se répéter une ou plusieurs fois.
• $ qui affirme la position à la fin de la chaîne.

Voici maintenant le processus de correspondance :

1. Correspondance initiale : Le moteur commence au début de la chaîne (^).
2. Correspondance du premier groupe : Le moteur fait correspondre le premier a+, consommant tous les caractères a (aaa...).
3. Quantificateur externe : Le + externe permet au moteur de répéter le groupe (a+).

Quand le moteur atteint le point d'exclamation (!), il ne peut pas le faire correspondre au motif, ce qui entraîne l'échec de la correspondance. C'est alors que le retour arrière commence :

1. Tentative de retour arrière : Le moteur revient en arrière pour diviser à plusieurs reprises les caractères a correspondants entre les quantificateurs a+ interne et + externe. Il réévalue chaque division pour voir si une partition différente peut faire correspondre le motif jusqu'à la fin de la chaîne.
2. Croissance exponentielle : Ce processus de retour arrière peut croître de façon exponentielle car le moteur essaie toutes les façons possibles de partitionner la chaîne de caractères a en différents groupes qui pourraient potentiellement correspondre à (a+)+.

Pour une chaîne de n caractères a, le a+ interne et le + externe peuvent diviser ces caractères en groupes de roughly 2^(n-1) façons différentes. Quand le ! en fin de chaîne fait échouer la correspondance, le moteur doit toutes les essayer. C'est pourquoi ajouter un seul a supplémentaire à l'entrée double approximativement le temps d'exécution — la marque distinctive de l'explosion exponentielle. La correspondance ci-dessous réussit rapidement car il n'y a pas de queue en échec pour forcer une exploration complète :

La leçon : le retour arrière catastrophique ne frappe que lorsqu'un motif peut correspondre de nombreuses façons et que la correspondance globale finit par échouer. Une entrée en échec soigneusement construite est exactement ce qu'un attaquant envoie.

Identifier les motifs sujets au retour arrière catastrophique

Comme liste de vérification rapide, un motif est à risque lorsqu'il présente ces trois caractéristiques : une répétition à l'intérieur d'une autre répétition, portant sur des caractères qui se chevauchent. Les signaux d'alarme courants :

• Quantificateurs imbriqués, par exemple (a+)+, (\d*)*, (\w+)*.
• Groupes quantifiés contenant une alternance qui se chevauche, par exemple (a|a)+ ou (\w|\d)+ (\w inclut déjà \d).
• Un .* ou .+ greedy entre deux éléments qui peuvent aussi correspondre aux mêmes caractères, par exemple <.+>.*<.+>.
• Motifs non ancrés sur une longue entrée, qui relancent toute la correspondance à chaque position de départ.

Si les répétitions d'un groupe quantifié peuvent chacune correspondre à la même sous-chaîne, il y a ambiguïté, et l'ambiguïté est ce que le retour arrière explore.

Stratégies pour prévenir le retour arrière catastrophique

L'objectif de chaque correction ci-dessous est le même : supprimer l'ambiguïté qui permet au moteur de diviser l'entrée de plus d'une façon. Passer de greedy à lazy (+?, *?) n'aide pas ici — les deux explorent encore toutes les divisions ; lazy les explore simplement dans un ordre différent. Vous devez changer la structure du motif, pas son comportement greedy.

1. Éliminer le quantificateur imbriqué

(a+)+ est presque toujours équivalent à un seul quantificateur. Si vous avez juste besoin de « un ou plusieurs a », écrivez simplement a+. Il n'y a alors qu'une seule façon de le faire correspondre, donc le moteur ne peut pas revenir en arrière dans une explosion combinatoire.

2. Émuler un groupe atomique avec un préambule

JavaScript n'a pas de groupes atomiques (?>...) natifs ni de quantificateurs possessifs (a++) comme certains autres moteurs de regex. Vous pouvez reproduire le même comportement « correspondre une fois et ne jamais revenir en arrière » avec un préambule (lookahead) plus une référence arrière : (?=(a+))\1. Le lookahead fait correspondre a+ de façon greedy, le capture, et \1 consomme exactement ce texte — mais comme le groupe capturé était à l'intérieur d'un lookahead, le moteur ne le re-partitionnera pas lors du retour arrière.

3. Utiliser des classes de caractères spécifiques et non chevauchantes

Le retour arrière explose lorsque des parties adjacentes d'un motif peuvent correspondre aux mêmes caractères. Faites en sorte que chaque partie corresponde à un ensemble distinct pour qu'il n'y ait qu'une seule façon de diviser l'entrée. Par exemple, préférez \d+\.\d+ plutôt que [\d.]+\.[\d.]+, où les deux groupes [\d.]+ se disputent le même point.

4. Ancrer et délimiter le motif

L'ancrage avec ^ et $ permet au moteur d'échouer rapidement au lieu de relancer la correspondance à chaque position de la chaîne. Placer une limite supérieure explicite sur un quantificateur (a{1,20} au lieu de a+) limite la quantité de travail qu'une seule répétition peut générer.

Exemples pratiques et solutions

Exemple 1 : Correspondance de balises HTML imbriquées

Un cas d'utilisation courant pour les regex est la correspondance de balises HTML imbriquées, ce qui peut facilement mener à un retour arrière catastrophique si ce n'est pas géré correctement. Remarque : Les expressions régulières sont généralement inadaptées à l'analyse de structures HTML arbitraires ou profondément imbriquées ; utilisez un véritable parseur HTML pour les documents complexes.

Motif problématique

Motif amélioré

Remplacez le .* greedy (qui peut avaler tout le document puis revenir en rampant) par une classe qui ne peut pas franchir la balise fermante. [^<]* correspond à tout jusqu'au prochain <, il n'y a donc pas de chevauchement sur lequel revenir en arrière.

Exemple 2 : Valider une liste d'identifiants

Motif problématique

([a-zA-Z0-9_]+)+ est le même piège que (a+)+ : le + interne et le + externe répètent tous les deux sur les mêmes caractères, donc une longue entrée sans correspondance déclenche un retour arrière exponentiel.

Une alternance sûre

Tous les groupes quantifiés ne sont pas dangereux. (?:ab|cd)+e est sûr : ab et cd sont disjoints, donc le moteur n'a jamais à remettre en question la façon dont il a divisé l'entrée. Utilisez un groupe non capturant (?:...) quand vous n'avez pas besoin du texte capturé — c'est légèrement plus rapide et plus clair, même si cela ne change pas le comportement de retour arrière ici.

Conclusion

Le retour arrière catastrophique peut bloquer une application JavaScript — et comme il est déclenché par l'entrée, c'est un véritable risque de sécurité, pas seulement un problème de performance. La correction consiste presque toujours à supprimer l'ambiguïté : aplatir les quantificateurs imbriqués, faire en sorte que les parties adjacentes du motif correspondent à des ensembles de caractères disjoints, ancrer avec ^/$, délimiter les répétitions, ou émuler un groupe atomique avec (?=(...))\1. Passer aux quantificateurs lazy n'aide pas.

Quand vous écrivez une regex qui s'exécute sur des entrées non fiables, testez-la avec de longues chaînes en échec (par exemple une centaine de a suivis de !) et observez le temps d'exécution. Si ajouter un caractère de plus augmente notablement le temps, le motif est exponentiel et doit être restructuré.

Pour aller plus loin, consultez les chapitres connexes sur les quantificateurs, les quantificateurs greedy et lazy, les groupes capturants et les classes de caractères.

Pratique