regex · traitement de texte · sécurité

Une regex, c'est quoi exactement ?

Une expression régulière, ou regex, est un petit langage qui décrit la forme d'un texte plutôt que son contenu exact. Au lieu de demander « cette chaîne est-elle égale à abc », vous demandez « cette chaîne ressemble-t-elle à trois lettres, un tiret, quatre chiffres ».

C'est toute l'idée. Le reste n'est que notation.

La notation, en une passe

L'essentiel de ce que vous lirez se construit avec une poignée d'éléments :

• . n'importe quel caractère, \d un chiffre, \w un caractère de mot, \s une espace
• * zéro ou plus, + un ou plus, ? zéro ou un, 5 entre deux et cinq
• [abc] l'un de ceux-ci, [^abc] tout sauf ceux-ci, [a-z] un intervalle
• ^ le début de la chaîne, $ sa fin
• (...) un groupe que l'on peut répéter ou capturer, | l'un ou l'autre

Ainsi ^\d3-\d4$ se lit : depuis le début, trois chiffres, un tiret, quatre chiffres, puis la fin. Rien de plus.

Pourquoi le même motif se comporte autrement dans deux langages

Il n'existe pas une regex. Il existe une famille de dialectes qui s'accordent sur les bases et divergent au-delà : POSIX, PCRE, la variante intégrée à JavaScript, celle de Python, celle de Go. Le lookbehind, les groupes nommés, les échappements de propriétés Unicode et jusqu'à ce que \d considère comme un chiffre sont autant d'endroits où ils se séparent.

Conséquence pratique : un motif copié d'une réponse écrite pour un autre langage peut faire silencieusement autre chose dans le vôtre. Testez-le là où il tournera, pas là où vous l'avez trouvé. C'est à cela que sert le testeur de regex de ce site.

Le mode de défaillance à connaître : le backtracking catastrophique

Voici ce qui transforme un utilitaire de correspondance de texte en problème d'exploitation.

La plupart des moteurs de regex des langages courants fonctionnent par retour sur trace. Quand un motif peut correspondre de plusieurs façons, le moteur essaie une découpe, et si la suite échoue, il revient en arrière et en essaie une autre. Pour des motifs ordinaires, c'est peu coûteux. Pour certains, non.

La forme dangereuse est une répétition à l'intérieur d'une répétition, où les deux peuvent se partager le même texte de multiples façons. L'exemple des manuels est (a+)+$. Soumis à une longue série de a suivie d'un caractère qui ne peut pas correspondre, le moteur doit essayer toutes les manières de répartir ces a entre la répétition interne et l'externe avant de pouvoir conclure à l'échec. Le nombre de combinaisons croît exponentiellement avec la longueur de l'entrée.

Vingt caractères peuvent être instantanés. Trente peuvent prendre une seconde. Quarante peuvent ne pas finir avant votre départ à la retraite. Et comme cela ne survient que sur une entrée qui correspond presque, cela n'apparaît jamais dans les tests que vous avez écrits avec une entrée qui correspond.

Quand cette regex s'exécute sur une entrée fournie par l'utilisateur, côté serveur, le cas exponentiel est atteignable par quiconque peut envoyer une requête. C'est la classe de déni de service appelée ReDoS, répertoriée par l'OWASP comme déni de service par expression régulière.

Comment s'en tenir à l'écart

Méfiez-vous des quantificateurs imbriqués. Un + ou un * appliqué à un groupe qui en contient déjà un est la forme à repérer. Souvent, on peut l'aplatir en quelque chose qui n'a qu'une seule façon de correspondre.

Ancrez et soyez précis. ^, $ et des classes de caractères précises réduisent le nombre de découpes que le moteur doit envisager. [^"]* vaut généralement mieux que .*.

Ne faites pas passer à la légère une entrée utilisateur dans une regex écrite à la main. Pour les adresses e-mail, les URL et les dates, un analyseur ou une bibliothèque éprouvée vaut mieux qu'un motif astucieux, et il échoue d'une manière lisible.

Connaissez votre moteur. Certains, comme RE2 en Go, reposent sur un autre algorithme et ne font aucun retour sur trace. Ils renoncent à des fonctionnalités comme les références arrière en échange d'une correspondance garantie en temps linéaire. Si une regex doit s'exécuter sur une entrée hostile, ce compromis est souvent le bon.

En résumé

Une regex décrit la forme d'un texte, dans une notation plus petite qu'elle n'en a l'air et moins portable qu'elle ne le paraît. Apprenez la douzaine de symboles, vérifiez le dialecte là où le code tournera, et traitez un quantificateur dans un quantificateur comme un défaut jusqu'à preuve du contraire. Le motif qui passe tous vos tests n'est pas celui qui fera tomber le site.