Déni de service par expression régulière (ReDoS) et retour arrière catastrophique

Les expressions régulières sont incroyablement puissantes, mais rares sont ceux qui les trouvent intuitives. Bien sûr, vous connaissez peut-être un développeur qui les maîtrise à la perfection, mais la plupart des développeurs en savent juste assez pour créer des problèmes. Malheureusement, les expressions régulières peuvent représenter un risque élevé pour la sécurité. Une mauvaise compréhension des expressions régulières peut permettre aux attaquants de mettre facilement votre site hors service. Prenons l’expression régulière suivante comme exemple :

regex = /A(B|C+)+D/

En la décomposant, voici ce que cette expression régulière accomplit :

• A La chaîne doit commencer par la lettre « A »

• (B|C+)+ La chaîne doit ensuite contenir, après la lettre A, soit la lettre « B », soit une ou plusieurs occurrences de la lettre « C » (+ correspond à une ou plusieurs occurrences). Le + à la fin de cette section indique qu’on peut rechercher une ou plusieurs correspondances de cette section.

• D Enfin, nous vérifions que cette section de la chaîne se termine par un « D »

L’expression correspondrait à des entrées telles que les exemples suivants :

ABBD
ABCCCCD
ABCBCCCD
ACCCCCD

En règle générale, un moteur d’expressions régulières trouve une correspondance très rapidement. Voyons, par exemple, ce qui se passe lorsqu’on le teste sur la chaîne suivante de 30 caractères : « ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCD ».

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total

Comme prévu, la chaîne correspond, et rapidement. Le processus complet prend environ 52 ms (test effectué sur un MacBook Air). Voyons maintenant ce qui se passe avec une autre chaîne de 30 caractères. Cette fois, au lieu de fournir une chaîne valide, remplaçons le « D » final par un « X » pour obtenir une chaîne non valide : « ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX ».

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total

Soudain, le test prend près de deux secondes, soit plus de dix fois le temps nécessaire avec une chaîne valide ! Cette différence spectaculaire s’explique par la manière dont les expressions régulières sont évaluées. En bref, elles n’aiment pas abandonner.

Fonctionnement des moteurs d’expressions régulières

Les moteurs d’expressions régulières varient, mais la plupart fonctionnent de manière assez similaire. Le moteur choisit la première façon possible de faire correspondre le caractère courant, puis passe au suivant. S’il ne parvient pas à faire correspondre ce caractère, il revient en arrière pour vérifier s’il existe une autre façon de traiter le caractère précédent. S’il s’engage trop loin dans cette piste avant de découvrir que la chaîne ne correspond finalement pas, et si de nombreux caractères peuvent emprunter plusieurs chemins valides dans l’expression régulière, le nombre d’étapes de retour arrière peut devenir très élevé. C’est ce qu’on appelle le retour arrière catastrophique. Voyons comment notre expression rencontre ce problème avec une chaîne plus courte : « ACCCX ». Même si cela semble assez simple, le moteur peut faire correspondre ces trois C de quatre façons différentes :

1. CCC

2. CC+C

3. C+CC

4. C+C+C.

Le moteur doit essayer chacune de ces combinaisons pour déterminer si l’une d’elles peut correspondre à l’expression. En tenant compte des autres étapes que le moteur doit effectuer, le débogueur RegEx 101 montre qu’il lui faut 38 étapes au total avant de conclure que la chaîne ne correspond pas. Le nombre d’étapes nécessaires pour valider une chaîne ne cesse ensuite d’augmenter.

Lorsque la chaîne contient 14 C, le moteur doit effectuer plus de 65 000 étapes simplement pour vérifier si elle est valide. Imaginez maintenant le même processus avec notre chaîne initiale : « ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX ». Vous voyez à quel point ce retour arrière peut rapidement devenir incontrôlable. La capture d’écran suivante ne montre qu’une petite partie du travail effectué par le moteur, comme le rapporte le débogueur RegEx101.

Compte tenu de la manière dont le moteur évalue une expression régulière, la raison de l’augmentation considérable du temps nécessaire au traitement d’une expression non valide devient plus claire : la longueur de la chaîne et le nombre de chemins que le moteur doit évaluer sont liés de façon exponentielle. Si nous ajoutons un seul caractère à notre séquence non valide, le temps d’évaluation double presque.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
3.51s user 0.06s system 95% cpu 3.732 total

Node et ReDoS

Des acteurs malveillants peuvent exploiter la complexité de l’analyse des expressions régulières en transmettant une chaîne longue et complexe qui oblige le moteur à prendre un temps démesuré pour l’évaluer. C’est ce qu’on appelle une attaque par déni de service par expression régulière (ReDoS).

Ce n’est évidemment souhaitable dans aucun environnement, mais c’est encore pire dans les environnements JavaScript, notamment Node. Comme nous l’expliquions dans notre article précédent sur les attaques temporelles, Node.js (et JavaScript en général) fonctionne sur un modèle événementiel.

Ainsi, si une requête ReDoS réussie monopolise un thread, elle bloque toute la boucle événementielle et l’application ne peut effectuer aucun autre traitement.

Un exemple concret

Examinons un exemple concret récent découvert dans la célèbre moment, une bibliothèque. moment sert à analyser, valider, manipuler et formater des dates. Avec cet outil, vous pouvez définir le format de sortie de vos dates à l’aide de la méthode format() :

moment().format('MMM Do YY');

//example output: Nov 22nd 16

Lorsque vous définissez le format, moment utilise une expression régulière pour le vérifier. Dans les versions de moment antérieures à la version 2.15.2, l’expression régulière est la suivante :

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/;

L’élément clé ici est la partie (\[[^\[\]]*\]|\s+)+ de l’expression. Il faut notamment noter que \s+ recherche la présence d’un ou plusieurs espaces. Cependant, le + juste après ce groupe signifie également que le groupe entre parenthèses peut apparaître une ou plusieurs fois. Ainsi, lorsque le format contient beaucoup d’espaces, le moteur d’expressions régulières peut essayer de regrouper ces caractères de nombreuses façons pour trouver une correspondance. Ils peuvent être réunis dans un grand groupe correspondant une seule fois, répartis en groupes individuels correspondant chacun de leur côté, ou organisés de toute autre manière. Il peut donc falloir beaucoup de temps pour évaluer une chaîne presque valide.

Considérez cet exemple que nous avons publié lorsque nous avons découvert la vulnérabilité :

var m = require("moment");
m.locale("be");
m().format("D                               MMN MMMM");
// Normal date format, other than the 31 spaces included in the string

Dans ce cas, nous fournissons une chaîne de 40 caractères comportant de nombreux espaces. Un test sur un ordinateur portable standard a montré que l’expression bloquait la boucle événementielle pendant environ 20 secondes.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/.test("D                               MMN MMMM");'
21.24s user 0.14s system 96% cpu 22.079 total

Après avoir signalé la vulnérabilité à moment, son auteur a proposé un correctif (vous pouvez maintenant le tester pour vérifier s’il s’applique à votre cas), qui supprime l’opérateur + superflu des parenthèses :

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/;

Ainsi, vous évitez d’avoir deux groupes de correspondance différents, qui pourraient chacun contenir d’un seul à tous les espaces. Comme l’opérateur + ne suit plus le s, il ne peut correspondre qu’à un espace à la fois. Si vous testez à nouveau la chaîne avec la nouvelle expression régulière, le moteur n’a besoin que de quelques millisecondes pour conclure qu’il n’y a pas de correspondance.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/.test("D                               MMN MMMM");'
0.05s user 0.02s system 53% cpu 0.135 total

Éviter le retour arrière catastrophique

Pour éviter le retour arrière catastrophique, surveillez les cas où vous utilisez des opérateurs « + » ou « * » à proximité les uns des autres. Si c’est le cas, ils risquent de se livrer à un bras de fer qui provoquera un retour arrière catastrophique. Vérifiez que les deux opérateurs sont vraiment nécessaires. Vous pouvez également remplacer l’un d’eux par un ensemble limité. Si vous vous souvenez de la vulnérabilité ReDoS dans moment, nous l’avons corrigée en supprimant l’un des opérateurs « + ». Nous aurions aussi pu remplacer l’un d’eux par une plage, afin de limiter le nombre d’espaces autorisés dans une chaîne valide :

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+){0,10}MMMM?/;

L’analyse des expressions régulières est assez rudimentaire, mais certains langages proposent des fonctionnalités avancées qui peuvent aider à éviter le retour arrière catastrophique. Prenons, par exemple, l’expression simplifiée par laquelle nous avons commencé :

regex = /A(B|C+)+D/

Groupes atomiques

Comme nous l’avons vu, l’expression peut provoquer un retour arrière catastrophique. L’analyseur d’expressions régulières de Node.js ne propose aucune fonctionnalité native permettant de résoudre le problème. Ce n’est pas le cas dans certains autres langages. Ruby, par exemple, prend en charge les groupes atomiques. Ceux-ci permettent d’indiquer à l’analyseur d’expressions régulières de ne pas revenir en arrière lorsqu’un groupe a correspondu. Pour cela, faites précéder le groupe de ?>, comme ceci :

/A(?>B|C+)+D/

En ajoutant ?> au groupe qui recherche un certain nombre de « C », on en fait un groupe atomique. Auparavant, l’analyseur d’expressions régulières devait tenir compte de deux opérateurs concurrents. Le « C » à l’intérieur du groupe peut apparaître un nombre quelconque de fois, tout comme le groupe lui-même. Ainsi, si une expression non valide contenant un grand nombre de caractères « C » est transmise, l’analyseur se retrouve pris entre les deux groupes et tente sans cesse de trouver une combinaison magique qui rendrait l’expression valide.

En revanche, avec le regroupement atomique, l’analyseur verrouille la correspondance de ce groupe. Ici, il fera correspondre le nombre de « C » présents. Si l’expression n’est pas valide, il ne pourra pas revenir en arrière sur ce groupe : à ce stade, il est définitivement fixé. Sans avoir à répartir les « C » entre les deux opérateurs de correspondance possibles, l’analyseur identifie très rapidement une expression non valide et évite tout retour arrière catastrophique.

Anticipation

Bien que JavaScript ne prenne pas en charge les groupes atomiques, il prend en charge l’anticipation, qui permet d’obtenir un effet similaire.

A(?=(B|C+))\1+D

Ici, nous utilisons ?= pour définir une anticipation. Cela signifie que l’expression régulière fera correspondre ce groupe uniquement s’il est immédiatement suivi du groupe suivant. À l’aide de \1, nous capturons le groupe correspondant, ce qui crée de fait un groupe atomique. L’analyseur traitera alors cette correspondance comme un groupe atomique et évitera tout retour arrière catastrophique.

Si nous testons maintenant notre chaîne avec l’expression et l’anticipation, nous constatons que le temps nécessaire pour invalider la chaîne a considérablement diminué : il passe de 1,8 seconde sans anticipation à 94 ms avec.

$ time node -e '/A(?=(B|C+))\1+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
0.05s user 0.02s system 51% cpu 0.094 total

Le compromis, ici, est la complexité. Vous évitez le retour arrière catastrophique, mais ajoutez une certaine complexité à votre expression, qui devient plus difficile à comprendre pour le reste de votre équipe et plus susceptible de contenir une erreur. Si vous pouvez repérer la combinaison d’opérateurs susceptible de provoquer un retour arrière (ici, les deux +), mieux vaut peut-être remanier complètement l’expression pour la rendre plus claire et lisible.

En résumé

Les attaques ReDoS peuvent paralyser une application. C’est particulièrement vrai avec Node.js, où la boucle événementielle amplifie l’impact du retour arrière catastrophique.

Pour prévenir les vulnérabilités ReDoS, surveillez vos expressions régulières et vérifiez également que vos dépendances ne présentent pas de vulnérabilités ReDoS.

Plusieurs outils ont été créés pour détecter automatiquement les expressions susceptibles aux attaques ReDoS (notamment safe-regex), mais même lors de tests limités, nous avons relevé plusieurs faux positifs, ainsi que plusieurs expressions considérées comme sûres alors qu’elles ne l’étaient pas.

La vérification de vos dépendances est plus simple : Snyk peut s’en charger pour vous.

Dans tous les cas, cela vaut la peine d’expérimenter. Un outil comme le débogueur de RegEx101 est idéal pour tester différentes expressions et mieux comprendre les étapes que les analyseurs d’expressions régulières suivent pour tenter de faire correspondre votre expression.

Qui sait ? Avec suffisamment de temps et d’expérimentation, peut-être qu’un jour, vous serez la personne qui viendra sauver la situation grâce à votre connaissance approfondie des expressions régulières.