Le backtracking catastrophique : pourquoi une regex peut se figer

La plupart des regex s'exécutent en quelques microsecondes. Quelques-unes, sur une saisie défavorable, tournent pendant des secondes, des minutes ou plus, en monopolisant un cœur de processeur tout du long. On appelle cela le backtracking catastrophique (retour arrière catastrophique), et il a déjà mis hors ligne de vrais sites web.

La bonne nouvelle, c'est que les motifs dangereux ont une forme reconnaissable, et que les correctifs sont généralement petits. Cet article montre la forme, les chiffres et les réécritures.

01Comment fonctionne le backtracking

JavaScript, Python, Java, PHP et la plupart des autres langages utilisent un moteur à backtracking. Quand un motif offre des choix (combien de caractères prend un +, quel côté d'un | essayer), le moteur en choisit un et continue. Si la correspondance échoue plus loin, il revient en arrière et essaie le choix suivant.

Pour un motif comme ^a+$ sur aaaa!, il n'y a pas grand-chose à essayer : a+ prend les quatre a, $ échoue sur le !, le moteur rend un a à la fois, et chaque tentative échoue vite. Une poignée d'étapes, puis « aucune correspondance ».

02La forme qui explose

Placez maintenant un quantificateur à l'intérieur d'un autre :

(a+)+ veut dire « un ou plusieurs groupes, chacun d'un ou plusieurs a ». Quatre a peuvent se découper en groupes de huit façons : aaaa, aaa|a, a|aaa, aa|aa, aa|a|a, etc. Quand le ! fait échouer la correspondance, le moteur essaie chaque découpage avant d'abandonner. Chaque a supplémentaire double le nombre de découpages.

Voici ce que cela donne avec Node 23 sur un ordinateur portable ordinaire, sur une chaîne de a suivie de ! :

Longueur	^(a+)+$	^a+$
24 a	0,12 s	moins de 0,01 ms
26 a	0,5 s	moins de 0,01 ms
28 a	2 s	moins de 0,01 ms
40 a	plus de deux heures (estimation)	moins de 0,01 ms

Mêmes chaînes trouvées, coût radicalement différent. Le danger vient toujours d'une correspondance qui échoue : quand la saisie correspond, le premier chemin fonctionne généralement.

La forme générale à surveiller est un groupe répété dont l'intérieur peut correspondre au même texte de plusieurs façons :

• Des quantificateurs imbriqués : (a+)+, (\w+)*, (\d*)+
• Des alternatives qui se chevauchent, répétées : (a|a)+, (\w|\d)+, (.*,)*
• Plusieurs .* à la suite sur le même texte : .*=.*=.*

03C'est arrivé en production

Stack Overflow, juillet 2016. Un message contenait environ 20 000 caractères d'espacement consécutifs au milieu d'une ligne. Une regex censée supprimer les espaces en fin de ligne, en gros \s+$, a tenté une correspondance à partir de chacune de ces espaces. Chaque tentative allait jusqu'au bout des espaces, trouvait encore du texte au lieu de la fin de ligne, et échouait. C'est un travail quadratique, environ 200 millions d'étapes, et le site est resté hors ligne 34 minutes.

Cloudflare, juillet 2019. Une nouvelle règle de pare-feu contenait un motif avec .*(?:.*=.*). Chaque serveur qui exécutait la règle est monté à 100 % de CPU, et le réseau de Cloudflare a perdu du trafic dans le monde entier pendant environ 27 minutes.

Aucun des deux motifs n'avait l'air dangereux au premier coup d'œil. Les deux se comportaient bien sur des saisies normales.

04Correctif n° 1 : rendre les choix exclusifs

Le correctif le plus propre est un motif où chaque caractère ne peut correspondre que d'une seule façon. Supprimez l'imbrication :

Un exemple réel : des nombres séparés par des virgules. La version risquée imbrique un groupe répété autour d'un autre quantificateur et rend la virgule facultative, si bien qu'une suite de chiffres peut se découper de nombreuses façons :

La version sûre rend la virgule obligatoire entre les éléments, si bien que chaque chiffre n'a qu'une seule place possible :

05Correctif n° 2 : dire ce qui ne peut pas apparaître

.* est souvent le coupable, car il peut correspondre à n'importe quoi, y compris au texte dont la partie suivante a besoin. Une classe négative est exclusive par construction :

06Correctif n° 3 : groupes atomiques et quantificateurs possessifs

Un groupe atomique (?>…) correspond une fois et ne rend jamais rien. Un quantificateur possessif (a++, \d*+) fait de même pour un seul quantificateur. L'un comme l'autre supprime les alternatives que le moteur réessaierait sinon.

Python prend en charge les deux depuis la 3.11. Java, PCRE et PHP les ont aussi. JavaScript n'a ni l'un ni l'autre, mais un lookahead avec une référence arrière se comporte comme un groupe atomique : (?=(a+))\1 prend les a une fois pour toutes, sans découpage possible.

07Correctif n° 4 : limiter la saisie, ou le moteur

• Plafonnez la longueur de la saisie avant la recherche. Beaucoup de motifs explosifs sont inoffensifs sur 200 caractères.
• Utilisez un moteur en temps linéaire pour les saisies non fiables. RE2 de Google (avec des bindings pour Node, Python, Go et d'autres) et la crate regex de Rust ne font jamais de backtracking : ils ne peuvent donc pas exploser. Ils ne prennent en charge ni les références arrière ni les lookarounds : c'est le prix à payer.
• Fixez un délai d'expiration quand la plateforme le permet. En .NET, Regex accepte un matchTimeout.

08À vous de jouer

Écrivez la version sûre d'une liste de nombres séparés par des virgules :

09Récapitulatif

• Signe de danger : un groupe quantifié dont l'intérieur peut correspondre au même texte de plusieurs façons : (a+)+, (\w|\d)+, (.*,)*.
• Le coût apparaît sur les correspondances qui échouent, et il peut doubler à chaque caractère.
• Faites en sorte que chaque caractère ne puisse correspondre que d'une façon : séparateurs obligatoires, pas d'imbrication.
• Préférez [^x]* à .* quand la partie suivante commence par x.
• Utilisez les groupes atomiques ou les quantificateurs possessifs quand c'est possible (Python 3.11+, Java, PCRE).
• Pour les saisies non fiables, plafonnez leur longueur ou utilisez RE2.

10Continuez à vous entraîner

• La section du guide sur les performances traite ce sujet avec d'autres exemples.
• L'article sur les quantificateurs gourmands et paresseux explique comment les quantificateurs choisissent ce qu'ils prennent.
• Carrière des quantificateurs est un pack d'entraînement pour maîtriser parfaitement les quantificateurs.