Skip to main content

Testeur Regex

Français

Testez des expressions régulières avec surlignage des correspondances.

Tous les calculs sont effectués localement dans votre navigateur. Aucune donnée n'est envoyée au serveur.

Les résultats sont fournis à titre informatif. Vérifiez-les auprès d'autres sources.

Une chaîne de 26 caractères peut mettre 368 ms à échouer contre le mauvais motif

Les expressions régulières s'exécutent d'ordinaire en un temps proportionnel à l'entrée. Imbriquez un quantificateur dans un groupe quantifié et ce n'est plus vrai : /^(a+)+$/ met environ 23 ms à rejeter 22 caractères, 95 ms pour 24 et 368 ms pour 26. Chaque caractère supplémentaire double à peu près le travail : une entrée un peu plus longue ne ralentit donc pas la recherche, elle l'empêche d'aboutir.

Comment ça marche

  • Teste un motif sur un texte d'exemple et affiche chaque correspondance avec ses groupes de capture.
  • Explique le rôle de chaque partie de l'expression, la syntaxe étant dense par conception.
  • Permet d'essayer les cas qui échouent, là où vivent les problèmes de performance.
la forme dangereuse : un quantificateur dans un groupe quantifié
  (a+)+   (a*)*   (a|a)*   (\d+)+

n caractères se répartissent entre les groupes d'un nombre exponentiel de façons,
et le moteur doit toutes les essayer avant de pouvoir conclure à l'absence de correspondance

équivalent sûr : a+   — un seul quantificateur, temps linéaire

Exemple chiffré

Chronométrage de /^(a+)+$/ sur des chaînes de a suivies d'un ! qui ne peut pas correspondre.

  1. 22 caractères → environ 23 ms
  2. 24 caractères → environ 95 ms
  3. 26 caractères → environ 368 ms
  4. les mêmes 26 a sans le ! → correspondance en moins de 0,01 ms
  5. la forme sûre /^a+$/ sur 100 000 caractères → 0,12 ms

Rejeter 26 caractères coûte trois mille fois plus qu'en accepter 100 000. Le succès est instantané et l'échec exponentiel, ce qui explique que cela n'apparaisse jamais aux tests : le chemin nominal est toujours rapide.

Lire le résultat

  • C'est un vecteur de déni de service partout où une saisie utilisateur atteint un motif. Un attaquant n'a pas besoin d'une longue chaîne : trente ou quarante caractères suffisent à occuper un fil de requête plusieurs minutes, et une poignée de telles requêtes met un serveur à terre.
  • Le correctif consiste presque toujours à supprimer l'imbrication plutôt qu'à optimiser autour. (a+)+ et a+ reconnaissent exactement le même langage : la version vulnérable n'apporte donc rien du tout, c'est une erreur et non un compromis.
  • Les mesures viennent d'une machine et varient selon le moteur, mais la forme du phénomène non. Toute implémentation à retour arrière — JavaScript, Python, Java, PCRE — se comporte ainsi. RE2 et le regexp de Go non, parce qu'ils refusent les fonctionnalités qui le rendent possible.
  • Testez vos motifs sur des entrées qui échouent, pas seulement sur celles qui correspondent. Le cas catastrophique n'apparaît que lorsque le moteur doit épuiser toutes les possibilités avant de conclure à l'absence de correspondance.

Questions fréquentes

Comment savoir si mon motif est vulnérable ?
Cherchez un quantificateur dans un groupe quantifié — (a+)+, (a*)*, (\d+)* et similaires — et des alternatives dont les branches peuvent reconnaître le même texte. Testez ensuite avec une longue chaîne qui correspond PRESQUE, car ce sont les quasi-correspondances qui déclenchent le chemin exponentiel.
Pourquoi est-ce rapide quand ça correspond et lent quand ça ne correspond pas ?
Parce que le moteur peut s'arrêter au premier succès mais doit épuiser toutes les possibilités avant de déclarer un échec. Avec des quantificateurs imbriqués, le nombre de possibilités double par caractère : le cas en échec est donc le seul jamais exploré intégralement.

Sources