Katastrophales Backtracking

Katastrophales Backtracking ist ein Phänomen bei regulären Ausdrücken, bei dem die Engine eine übermäßig lange Zeit benötigt, um bestimmte Muster auszuwerten, was zu erheblichen Leistungseinbußen führt — manchmal Sekunden, Minuten oder praktisch ewig. Es entsteht, weil die Engine versucht, Teile des Strings auf sehr viele verschiedene Arten abzugleichen, bevor sie aufgibt, und die Anzahl der untersuchten Kombinationen wächst exponentiell mit der Eingabelänge.

Diese Seite erklärt, was das Problem auslöst, wie man ein gefährliches Muster erkennt und zeigt konkrete Techniken, um einen Regulärausdruck so umzuschreiben, dass er schnell bleibt. Es wird vorausgesetzt, dass Sie mit Quantoren und dem Unterschied zwischen greedy und lazy Matching vertraut sind.

Warum das wichtig ist: Ein einziger langsamer Regulärausdruck, der auf benutzerseitige Eingaben angewendet wird, ist ein realer Denial-of-Service-Angriffsvektor (oft als „ReDoS" bezeichnet). Ein Angreifer muss lediglich einen kurzen, gezielt konstruierten String senden, der das Backtracking maximiert, um Ihren Node.js-Event-Loop einzufrieren.

Was verursacht katastrophales Backtracking?

Katastrophales Backtracking tritt typischerweise bei verschachtelten Quantoren auf — einem Quantor innerhalb einer Gruppe, die selbst quantifiziert ist, wie z. B. (a+)+. Die Gefahr zeigt sich, wenn zwei Teile des Musters dieselben Zeichen abgleichen können, sodass die Engine viele überlappende Möglichkeiten hat, die Eingabe aufzuteilen. Wenn der Abgleich letztendlich scheitert, muss die Engine jede dieser Aufteilungen ausprobieren, bevor sie feststellen kann, dass nichts übereinstimmt. Hier ist das klassische Beispiel:

Wenn dies auf Ihrem Computer nicht lange dauert, können Sie der str ein weiteres a-Zeichen hinzufügen. Warum dauert das so lange? Analysieren wir das. Das Muster /^(a+)+$/ besteht aus:

• ^ das die Position am Anfang des Strings bestätigt.
• (a+) das ein oder mehrere a-Zeichen abgleicht.
• + das der vorherigen Gruppe (a+) erlaubt, sich ein oder mehrere Male zu wiederholen.
• $ das die Position am Ende des Strings bestätigt.

Der Abgleichprozess läuft nun wie folgt ab:

1. Erster Abgleich: Die Engine beginnt am Anfang des Strings (^).
2. Erster Gruppenabgleich: Die Engine gleicht das erste a+ ab und verbraucht alle a-Zeichen (aaa...).
3. Äußerer Quantor: Das äußere + erlaubt der Engine, die Gruppe (a+) zu wiederholen.

Wenn die Engine das Ausrufezeichen (!) erreicht, kann sie es nicht mit dem Muster abgleichen, wodurch der Abgleich fehlschlägt. Zu diesem Zeitpunkt beginnt das Backtracking:

1. Backtracking-Versuch: Die Engine geht zurück und verteilt die abgeglichenen a-Zeichen wiederholt zwischen dem inneren a+ und dem äußeren +-Quantor. Sie bewertet jede Aufteilung neu, um zu prüfen, ob eine andere Partition das Muster bis zum Ende des Strings abgleichen kann.
2. Exponentielles Wachstum: Dieser Backtracking-Prozess kann exponentiell wachsen, da die Engine jede mögliche Weise ausprobiert, den String aus a-Zeichen in verschiedene Gruppen aufzuteilen, die (a+)+ potenziell abgleichen könnten.

Für einen String aus n a-Zeichen können das innere a+ und das äußere + diese Zeichen auf ungefähr 2^(n-1) verschiedene Arten in Gruppen aufteilen. Wenn das abschließende ! den Abgleich scheitern lässt, muss die Engine alle dieser Varianten ausprobieren. Deshalb verdoppelt das Hinzufügen eines einzigen weiteren a zur Eingabe die Laufzeit ungefähr — das typische Merkmal eines exponentiellen Wachstums. Der folgende Abgleich gelingt schnell, weil kein fehlschlagendes Ende vorhanden ist, das eine vollständige Untersuchung erzwingt:

Die Erkenntnis: Katastrophales Backtracking schlägt nur zu, wenn ein Muster auf viele Arten abgeglichen werden kann und der Gesamtabgleich letztendlich scheitert. Gezielt konstruierte fehlschlagende Eingaben sind genau das, was ein Angreifer sendet.

Muster erkennen, die zu katastrophalem Backtracking neigen

Als mentale Checkliste ist ein Muster gefährdet, wenn es alle drei folgenden Merkmale aufweist: eine Wiederholung innerhalb einer anderen Wiederholung über Zeichen, die sich überlappen. Häufige Warnsignale:

• Verschachtelte Quantoren, z. B. (a+)+, (\d*)*, (\w+)*.
• Quantifizierte Gruppen mit einer überlappenden Alternation, z. B. (a|a)+ oder (\w|\d)+ (\w schließt bereits \d ein).
• Ein gieriges .* oder .+ zwischen zwei Elementen, die dieselben Zeichen abgleichen können, z. B. <.+>.*<.+>.
• Nicht verankerte Muster auf langen Eingaben, die den gesamten Abgleich an jeder Startposition neu versuchen.

Wenn die Wiederholungen einer quantifizierten Gruppe jeweils denselben Teilstring abgleichen können, entsteht Mehrdeutigkeit — und Mehrdeutigkeit ist das, was Backtracking erkundet.

Strategien zur Vermeidung von katastrophalem Backtracking

Das Ziel jeder Korrektur unten ist dasselbe: die Mehrdeutigkeit beseitigen, die es der Engine erlaubt, die Eingabe auf mehr als eine Weise aufzuteilen. Das Wechseln von greedy zu lazy (+?, *?) hilft hier nicht — beide erkunden weiterhin jede Aufteilung; lazy tut es nur in einer anderen Reihenfolge. Sie müssen die Struktur des Musters ändern, nicht seine Gierigkeit.

1. Den verschachtelten Quantor eliminieren

(a+)+ ist fast immer äquivalent zu einem einzelnen Quantor. Wenn Sie nur „ein oder mehr a" benötigen, schreiben Sie einfach a+. Es gibt genau eine Möglichkeit, das abzugleichen, sodass die Engine nicht in eine kombinatorische Explosion zurückfallen kann.

2. Eine atomare Gruppe mit Lookahead emulieren

JavaScript hat keine eingebauten atomaren Gruppen (?>...) oder besitzergreifende Quantoren (a++) wie manche anderen Regex-Varianten. Sie können dasselbe „einmal abgleichen und nie zurückgeben"-Verhalten mit einem Lookahead und einer Rückreferenz nachbilden: (?=(a+))\1. Der Lookahead gleicht a+ greedy ab, erfasst es, und \1 verbraucht genau diesen Text — aber weil die erfasste Gruppe innerhalb eines Lookaheads war, wird die Engine sie beim Backtracking nicht erneut aufteilen.

3. Spezifische, nicht überlappende Zeichenklassen verwenden

Backtracking explodiert, wenn benachbarte Teile eines Musters dieselben Zeichen abgleichen können. Lassen Sie jeden Teil eine eigene Menge abgleichen, sodass es nur eine Möglichkeit gibt, die Eingabe aufzuteilen. Bevorzugen Sie beispielsweise \d+\.\d+ gegenüber [\d.]+\.[\d.]+, bei dem beide [\d.]+-Gruppen um denselben Punkt konkurrieren.

4. Das Muster verankern und begrenzen

Das Verankern mit ^ und $ ermöglicht es der Engine, schnell zu scheitern, anstatt den Abgleich an jeder Position im String erneut zu versuchen. Das Festlegen einer expliziten Obergrenze für einen Quantor (a{1,20} statt a+) begrenzt, wie viel Arbeit eine einzelne Wiederholung erzeugen kann.

Praktische Beispiele und Lösungen

Beispiel 1: Abgleich verschachtelter HTML-Tags

Ein häufiger Anwendungsfall für Regulärausdrücke ist der Abgleich verschachtelter HTML-Tags, was bei falscher Handhabung leicht zu katastrophalem Backtracking führen kann. Hinweis: Reguläre Ausdrücke sind generell ungeeignet für das Parsen beliebiger oder tief verschachtelter HTML-Strukturen; verwenden Sie für komplexe Dokumente einen geeigneten HTML-Parser.

Problematisches Muster

Verbessertes Muster

Ersetzen Sie das greedy .* (das das gesamte Dokument verschlucken und dann zurückkriechen kann) durch eine Klasse, die die schließende spitze Klammer nicht überschreiten kann. [^<]* gleicht alles bis zum nächsten < ab, sodass es keine Überlappung gibt, durch die zurückgetracked werden könnte.

Beispiel 2: Validierung einer Bezeichnerliste

Problematisches Muster

([a-zA-Z0-9_]+)+ ist dieselbe Falle wie (a+)+: Das innere + und das äußere + wiederholen sich über dieselben Zeichen, sodass eine lange nicht-übereinstimmende Eingabe exponentielles Backtracking auslöst.

Eine sichere Alternation

Nicht jede quantifizierte Gruppe ist gefährlich. (?:ab|cd)+e ist in Ordnung: ab und cd sind disjunkt, sodass die Engine nie zweimal überlegen muss, wie sie die Eingabe aufgeteilt hat. Verwenden Sie eine nicht erfassende Gruppe (?:...), wenn Sie den erfassten Text nicht benötigen — sie ist etwas schneller und klarer, auch wenn sie das Backtracking-Verhalten hier nicht ändert.

Fazit

Katastrophales Backtracking kann eine JavaScript-Anwendung einfrieren — und da es durch Eingaben ausgelöst wird, ist es ein echtes Sicherheitsrisiko, nicht nur ein Performance-Problem. Die Lösung besteht fast immer darin, Mehrdeutigkeit zu beseitigen: verschachtelte Quantoren abflachen, benachbarte Teile des Musters disjunkte Zeichenmengen abgleichen lassen, mit ^/$ verankern, Wiederholungen begrenzen oder eine atomare Gruppe mit (?=(...))\1 emulieren. Der Wechsel zu lazy Quantoren hilft nicht.

Wenn Sie einen Regulärausdruck schreiben, der gegen nicht vertrauenswürdige Eingaben ausgeführt wird, testen Sie ihn mit langen fehlschlagenden Strings (z. B. hundert as gefolgt von !) und beobachten Sie die Timing-Werte. Wenn das Hinzufügen eines weiteren Zeichens die Zeit merklich verlängert, ist das Muster exponentiell und muss umstrukturiert werden.

Zur Vertiefung empfehlen sich die verwandten Kapitel zu Quantoren, greedy und lazy Quantoren, Erfassungsgruppen und Zeichenklassen.

Übungen