flawopen.com/Was ist ReDoS/Explained

Was ist ReDoS (katastrophales Backtracking)?

CWE-1333: Inefficient Regular Expression ComplexityReferenzseite

Kurz erklärt

Eine Regex-Engine mit Backtracking kann nach einem Fehlschlag verschiedene Aufteilungen derselben Eingabe ausprobieren. Bei manchen mehrdeutigen Mustern wächst die Zahl der Versuche exponentiell mit der Eingabelänge. Die Verzögerung hängt von Muster, Engine, Eingabegröße, Parallelität und Ressourcenlimits ab; wiederholte teure Anfragen können die Dienstkapazität erschöpfen.

VERLETZLICHE MUSTER

# 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.

SICHERER

# 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.

Warum Backtracking eskaliert

Ein Muster wie ^(a+)+$ ist in einer Backtracking-Engine mehrdeutig: aaaa lässt sich auf verschiedene Arten auf verschachtelte Quantifizierer verteilen. Ein abschließendes Zeichen ohne Treffer kann die Engine dazu zwingen, Alternativen zu prüfen, bevor sie die gesamte Zeichenfolge verwirft.

Bei solchen Mustern kann die Zahl der untersuchten Pfade mit der Länge eines passenden Präfixes vor einem Fehlschlag exponentiell wachsen. Das hängt von der konkreten Kombination aus Muster und Engine ab. Auch kürzere Eingaben zählen bei parallelen Anfragen; begrenzen Sie Eingabe, Parallelität und Laufzeit.

Wo nicht vertrauenswürdige Eingaben Regex erreichen

Eingabevalidierung ist naheliegend, doch Risiken stecken auch in der Verarbeitung von User-Agent und anderen Headern, Logs, Markdown und Syntaxhervorhebung, URL-Routing, Inhaltsfiltern und WAF-Regeln sowie Bibliotheken, die Regex auf übergebene Felder anwenden. Verbreitete Pakete hatten ReDoS-Advisories; Abhängigkeiten sind ebenso wichtig wie eigene Muster.

Häufige Fragen

Which languages are affected?

Das Risiko hängt von Engine und Muster ab, nicht nur von der Sprache. Backtracking-Engines können bei bestimmten Mustern übermäßig viele Alternativen prüfen. Go dokumentiert für regexp lineare Laufzeit zur Eingabelänge. Die Rust-Crate regex nennt O(m·n) pro Suche (m = Mustergröße, n = Eingabegröße), also linear in n bei festem Muster; Iteratoren wiederholter Suchen haben andere Grenzen. Diese Engines verzichten auf Funktionen wie Backreferences, die solche Garantien verhindern.

Is a length limit enough on its own?

Ein Limit begrenzt den möglichen Aufwand; ein sicherer Wert hängt von Muster, Engine, Anfragerate und Servicebudget ab. Beheben Sie mehrdeutige Muster und begrenzen Sie vor dem Parsen oder Abgleichen.

How do I find vulnerable patterns?

Nutzen Sie einen ReDoS-fähigen statischen Analyzer und prüfen Sie Befunde anhand der Engine. Suchen Sie nach wiederholten Gruppen mit Quantifizierern oder Alternativen mit überlappenden Präfixen; testen Sie mit begrenzten Eingaben und strengem Timeout in einer isolierten Umgebung.

Can I add a timeout instead?

Timeout-Unterstützung hängt von Runtime und API ab. Setzen Sie in .NET ein explizites Timeout für nicht vertrauenswürdige Eingaben. Prüfen Sie sonst die Kontrollen der konkreten Engine; verwenden Sie eine sicherere Engine oder entwerfen Sie das Muster um, wenn kein Timeout verfügbar ist. Ein Timeout ergänzt Größen- und Parallelitätslimits, macht ein mehrdeutiges Muster aber nicht effizient.

Quellen

Siehe auch ReDoS in Node.js: Regex und CVE-2026-83606