flawopen.com/Qu’est-ce que ReDoS/Explained

Qu’est-ce que ReDoS (retour arrière catastrophique) ?

CWE-1333: Inefficient Regular Expression ComplexityPage de référence

Réponse courte

Un moteur regex avec retour arrière peut essayer plusieurs découpages de la même entrée après un échec. Pour certains motifs ambigus, le nombre d’essais croît de façon exponentielle avec l’entrée. Le délai dépend du motif, du moteur, de la taille de l’entrée, de la concurrence et des limites de ressources ; des requêtes coûteuses répétées peuvent épuiser le service.

MOTIFS VULNÉRABLES

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

PLUS SÛR

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

Pourquoi le retour arrière explose

Un motif comme ^(a+)+$ est ambigu dans un moteur à retour arrière : aaaa peut être réparti de plusieurs façons entre les quantificateurs imbriqués. Un caractère final qui ne correspond pas peut obliger le moteur à explorer des possibilités avant de rejeter la chaîne entière.

Pour ces motifs, les chemins explorés peuvent croître de façon exponentielle selon la longueur du préfixe correspondant suivi d’un échec. Cela dépend du couple motif-moteur, pas de toutes les regex ou de tous les échecs. Des entrées plus courtes comptent aussi sous concurrence ; bornez taille, concurrence et durée.

Où les entrées non fiables atteignent une regex

La validation des entrées est évidente, mais les risques sont aussi dans l’analyse de User-Agent et d’autres en-têtes, les journaux, Markdown et coloration syntaxique, le routage d’URL, les filtres de contenu et les règles WAF, ou les bibliothèques appliquant une regex à un champ fourni. Des paquets répandus ont publié des avis ReDoS : les dépendances comptent autant que vos motifs.

Questions fréquentes

Which languages are affected?

Le risque dépend du moteur et du motif, pas seulement du langage. Certains moteurs à retour arrière explorent trop de possibilités pour certains motifs. Go garantit dans sa documentation regexp un temps linéaire en fonction de l’entrée. La crate Rust regex indique O(m·n) par recherche (m = taille du motif, n = taille de l’entrée), donc linéaire en n pour un motif fixe ; les itérateurs de recherches répétées ont d’autres bornes. Ces moteurs excluent des fonctions comme les backreferences qui empêchent ces garanties.

Is a length limit enough on its own?

Une limite réduit le travail possible, mais la borne sûre dépend du motif, du moteur, du débit des requêtes et du budget du service. Corrigez les motifs ambigus et appliquez les limites avant l’analyse ou la recherche.

How do I find vulnerable patterns?

Utilisez un analyseur statique spécialisé ReDoS et vérifiez ses résultats pour le moteur utilisé. Examinez les groupes répétés contenant une répétition ou des alternatives aux préfixes chevauchants ; testez ensuite des entrées bornées avec un délai strict en environnement isolé.

Can I add a timeout instead?

Le support des délais dépend du runtime et de l’API. En .NET, définissez un timeout explicite pour les entrées non fiables. Ailleurs, vérifiez les contrôles documentés du moteur précis ; choisissez un moteur plus sûr ou repensez le motif si aucun timeout applicable n’existe. Le timeout complète les limites de taille et de concurrence sans rendre efficace un motif ambigu.

Références

À voir aussi ReDoS dans Node.js : regex et CVE-2026-83606