Warum Backtracking-Regex-Muster Ihren Server heimlich lahmlegen können

Ein Muster zur Überprüfung von Benutzernamen wurde einer Code-Review unterzogen, bestand die gesamte Testsuite und führte dann, Wochen nach der Bereitstellung, dazu, dass ein API-Endpunkt aufgrund einer einzigen eingehenden Anfrage elf Sekunden lang stillstand. Es kam weder zu einem Absturz noch zu einer ausgelösten Ausnahme – der Prozess hörte einfach auf zu reagieren und verbrauchte dabei 100 % der CPU-Leistung, während er eine Zeichenkette verarbeitete, die kaum vierzig Zeichen lang war.

In dem üblichen Sinne wurde kein Fehler eingeführt. Die reguläre Ausdrucksregel selbst war gültig und passte genau zu dem, was sie ursprünglich erfassen sollte. Doch sie besaß eine verborgene Eigenschaft, auf die die meisten Entwickler nie achten lernen; um sie zu verstehen, muss man über die Symbole hinausblicken und begreifen, was eine reguläre Ausdrucksregel tatsächlich tut, wenn sie ausgeführt wird – etwas, was die meisten Tutorials bei der Erklärung von Token wie \d und + überspringen.

Ein Regex ist ein kleines Flussdiagramm, keine Zeichenkette

Betrachten wir ein Muster zur Überprüfung eines Produktcodes, der aus zwei Großbuchstaben und anschließend vier Ziffern besteht:

const productCode = /^[A-Z]{2}\d{4}$/;
console.log(productCode.test("LM4821")); // true
console.log(productCode.test("LM482"));  // false

Es ist verständlich, dies als abgekürzte Beschreibung der Struktur einer Zeichenkette zu betrachten. Ein besseres mentales Modell, das später Vorteile bringt, besteht darin, es als Miniatur-Flussdiagramm zu sehen: Start, Anforderung nach genau zwei Großbuchstaben, anschließend Anforderung nach genau vier Ziffern und schließlich Ende der Eingabe. Der Interpreter durchläuft die Eingabe Zeichen für Zeichen und versucht, einen Pfad durch dieses Diagramm vom Startknoten zum Endknoten zu finden. Wenn er erfolgreich das Ende erreicht, liegt eine Übereinstimmung vor. Stößt er auf ein Hindernis und es gibt noch einen ungetesteten Pfad weiter hinten, zieht er sich zurück und versucht stattdessen diesen anderen Pfad.

Der Rückzugsschritt – das Zurückgehen, um einen alternativen Pfad zu testen – wird als Backtracking bezeichnet und ist wohl das wichtigste Konzept in regulären Ausdrücken. Er verleiht ihnen ihre Flexibilität und war zugleich der Grund für den oben beschriebenen Produktionsfehler.

Gruppen verwandeln „Passt es?“ in „Was ist tatsächlich darin?“

Die Aufrufung von .test() gibt nur true oder false zurück. Das Einfügen von Klammern um Teile eines Musters ermöglicht es, einzelne Abschnitte des abgeglichenen Textes zu erfassen – genau hier wird regex wirklich nützlich, um Daten zu parsen und nicht nur zu validieren:

const logPattern = /^\[(\w+)\] (\d{4}-\d{2}-\d{2}T\d{2}:\d{2}:\d{2}) (.+)$/;
const line = "[ERROR] 2026-08-15T10:22:01 Failed to connect to database";

const match = logPattern.exec(line);
console.log(match[1]); // "ERROR"
console.log(match[2]); // "2026-08-15T10:22:01"
console.log(match[3]); // "Failed to connect to database"

Jeder in Klammern gesetzte Abschnitt des Musters wird als eigene Eintragung im Ergebnisarray abgelegt, sortiert nach dem Auftreten des öffnenden Klammernzeichens im Muster. Dadurch wird eine einfache Prüfung auf Erfolg oder Misserfolg – also die Überprüfung, ob eine Zeile die Form eines Log-Eintrags hat – zu etwas Weitaus Nützlicherem: Der Schweregrad, das Zeitstempel und der Nachrichteninhalt stehen als drei separate Werte zur Verfügung, die direkt verwendet werden können. Genau diese Fähigkeit erklärt, warum reguläre Ausdrücke so häufig bei der Verarbeitung von Logs, beim Parsen von Konfigurationen sowie in jeder Situation verwendet werden, in der strukturiertes Textmaterial in etwas umgewandelt werden muss, mit dem ein Programm direkt arbeiten kann.

Greedy-Matching holt mehr, als beabsichtigt

Dieser nächste Fehler wird fast jeder Entwickler mindestens einmal machen. Stellen Sie sich einen Fall vor, in dem leichte HTML-Tags aus einem Textfeld entfernt werden müssen:

const html = "<b>Featured</b> item, <i>on sale</i> now";
console.log(html.replace(/<.*>/g, ""));
// "Featured item, on sale now" — wait, that actually looks right...

const html2 = "<b>Sale</b> ends <i>Friday</i>";
console.log(html2.replace(/<.*>/g, ""));
// "" — everything vanished

Der zweite String zeigt den Fehler auf. Standardmäßig ist .* gierig – es versucht, so viele Zeichen wie möglich aufzunehmen und gibt sie erst zurück, wenn der Rest des Musters es unbedingt erfordert. Da dieser String zwei separate Tags enthält, stoppt das Muster <.*> nicht bei dem ersten schließenden </b>. Es nimmt weiterhin alles nach diesem Punkt auf – über ends hinaus, direkt bis zum letzten > im String innerhalb von </i> – denn ein einzelnes gieriges .*> ist bereits vollständig erfüllt, sobald es auf das letzte verfügbare > im Text stößt, egal wie weit entfernt es ist.

console.log(html2.replace(/<.*?>/g, ""));
// "Sale ends Friday"

Durch das Hinterlegen eines ? direkt nach dem * ändert sich dessen Verhalten von „greedy“ zu „lazy“: Der Parser versucht nun, so wenige Zeichen wie möglich abzubilden und erweitert sich nur dann, wenn es keine andere Möglichkeit gibt, das Folgende zu erfassen. Durch diese Änderung wird jede <...>-Sequenz am nächsten > geschlossen, anstatt direkt zum letzten > in der gesamten Zeichenkette zu gelangen, sodass die Tags wie vorgesehen nacheinander entfernt werden. Dieser einzige Unterschied zwischen * und *? erklärt stillschweigend einen großen Teil der Fehler, bei denen „Regex mehr Text löscht als erwartet“.

Der Fehler, der den Server tatsächlich lahmlegte

Betrachten Sie eine vereinfachte Version des Musters, das für die elf Sekunden dauernde Verzögerung verantwortlich ist: Eine Überprüfung des Benutzernamens, bei der ein oder mehrere Abschnitte aus Wortzeichen erforderlich sind, möglicherweise getrennt durch Leerzeichen, gefolgt von einem @-Zeichen.

const badPattern = /^(\w+)+@/;
console.log(badPattern.test("valid_user@example.com")); // true, fast
console.log(badPattern.test("this_is_a_fairly_long_username_with_no_at_sign"));
// hangs, sometimes for a very long time, depending on length

Das Problem liegt in der verschachtelten Wiederholung: (\w+)+, also eine Abfolge von einem oder mehren Wortzeichen, die wiederum in einer Gruppe steckt, die sich ein- oder mehrfach wiederholt. Wenn der Eingabestring tatsächlich ein @ enthält, findet das Verarbeitungssystem fast sofort eine Übereinstimmung. Doch wenn ein String überhaupt kein @ enthält, kann das System nicht sofort aufgeben – es muss nachweisen, dass keine mögliche Anordnung funktioniert. Es gibt eine erstaunlich große Anzahl an Anordnungen zu überprüfen: Das innere + könnte ein Zeichen erfassen, während die äußere Gruppe den Rest wiederholt, oder es könnte zwei Zeichen erfassen und die äußere Gruppe den verbleibenden Teil wiederholen – jede mögliche Aufteilung wird getestet. Das Verarbeitungssystem prüft alle diese Kombinationen nacheinander, bevor es einen Misserfolg ausruft, und jedes zusätzliche Zeichen verdoppelt in etwa die Anzahl der Kombinationen.

Es existieren solche Fälle. Das bedeutet, dass ein 40-Zeichen-Username, der nicht übereinstimmt, nicht nur zehnmal langsamer abgelehnt wird als ein 4-Zeichen-Username, sondern in einem exponentiell wachsenden Maße langsamer – was erklärt, warum eine Regex, die bei Tests, in denen nur gültige Benutzernamen vorkamen, problemlos funktionierte, plötzlich blockiert, sobald sie eine lange Zeichenkette erhält, mit der sie ursprünglich nicht übereinstimmen sollte.

const fixedPattern = /^\w+@/;

Sobald man die Ursache verstanden hat, erscheint die Lösung fast zu einfach: Die verschachtelte Wiederholung war von Anfang an überhaupt nicht notwendig. \w+ bedeutet für alle Eingaben, die tatsächlich erfolgreich sein sollten, genau dasselbe wie (\w+)+, ohne das darunter verborgene Risiko eines exponentiellen Rückverfolgungsproblems. Dieser Fehler trägt den bekannten Namen „katastrophales Rückverfolgungsproblem“, und typisch dafür ist, wenn ein Wiederholungsoperator auf eine Gruppe angewendet wird, die bereits ihren eigenen Wiederholungsoperator enthält – Muster wie (x+)+, (x*)+ oder (x+)* sind alle Variationen derselben zugrunde liegenden Falle.

Was man dadurch eigentlich lernen sollte

Ihr müsst euch nicht jedes mögliche gefährliche Musterformat einprägen. Entscheidend ist es, eine grundlegende Wahrheit zu verinnerlichen: Ein Regex-Engine bewertet ein Muster nicht sofort, sondern sucht nach einer Übereinstimmung – Schritt für Schritt, wobei sie bei Misserfolg zurückgeht und einen anderen Weg ausprobiert. Gewöhnliche Muster haben so wenige zu prüfende Wege, dass diese Suche bereits vor dem Auftreten einer Verzögerung abgeschlossen ist. Die eigentliche Gefahr tritt insbesondere bei verschachtelten, überschneidenden Wiederholungen auf, wo die Anzahl der zu überprüfenden Wege nicht nur stetig zunimmt, sondern mit jedem zusätzlichen Zeichen, das sich nicht korrekt verhält, weiter ansteigt. Prüft daher eure Regex-Regeln nicht nur an den Zeichenketten, mit denen ihr eine Übereinstimmung erwartet, sondern auch an langen Zeichenketten, die absichtlich so konstruiert sind, dass sie fehlschlagen. Genau die Eingabedaten, die eure Testsuite nie in Betracht gezogen hat, tauchen letztendlich in der Produktion auf.