Ein harmloser regulärer Ausdruck lastet einen Kern zu 100 % aus und hängt? Bei bestimmten Mustern explodiert der Aufwand — katastrophales Backtracking.
Aufwand:
ca. 30 Min.
Gilt für:
Backtracking-Regex-Engines (u. a. Python re ab 3.11)
Das Symptom
Ein Programm läuft normal, bis eine bestimmte Eingabe kommt — dann friert es ein,
scheinbar für immer. Ein Prozessorkern ist zu 100 Prozent ausgelastet, der
Speicherverbrauch bleibt aber konstant. Bei den meisten Eingaben passiert nichts
dergleichen; nur bestimmte Zeichenfolgen lösen das Hängen aus.
Die „Layer 8“-Wahrheit
Reguläre Ausdrücke wirken harmlos, aber unter der Haube probiert die verbreitetste
Sorte von Regex-Maschine beim Abgleich viele mögliche Wege durch und springt bei
einer Sackgasse zurück, um den nächsten zu versuchen — das Backtracking. Meist ist
das schnell. Bei ungünstig gebauten Mustern jedoch — typisch sind verschachtelte,
sich überlappende Wiederholungen — wächst die Zahl der zu prüfenden Wege mit der
Eingabelänge explosionsartig. Aus Millisekunden werden Sekunden, Minuten, Stunden,
obwohl der Ausdruck auf den ersten Blick trivial aussieht.
Der konstante Speicher bei voller Prozessorlast ist die Signatur dieses Problems:
Es wird nicht angehäuft, es wird nur gerechnet — und zwar sinnlos viel. Besonders
brisant wird es, wenn ein solcher Ausdruck Eingaben aus dem Internet verarbeitet:
Dann kann ein Angreifer mit einer kurzen, gezielt bösartigen Zeichenkette einen
ganzen Server blockieren — eine echte Sicherheitslücke namens ReDoS. Die Lösung ist,
das Muster eindeutig zu bauen, es spezifisch zu halten und, wo möglich, eine
Regex-Maschine zu wählen, die dieses Rückspringen gar nicht erst kennt.
Die echte, verifizierte Lösung
1000 % faktenbasiert. Jeder Befehl ist real, jeder Pfad existiert. Schritt für Schritt:
1.
Das Muster als Ursache erkennen
Bleibt ein Programm bei einer bestimmten Eingabe hängen und ein Prozessorkern läuft dabei auf 100 Prozent, während kein Speicher wächst, ist ein regulärer Ausdruck ein Hauptverdächtiger. Bei bestimmten Kombinationen aus verschachtelten Wiederholungen kann der Abgleich exponentiell viele Wege durchprobieren.
2.
Verschachtelte Wiederholungen entschärfen
Gefährlich sind Muster mit ineinander verschachtelten Quantoren, etwa eine Wiederholung innerhalb einer Wiederholung, die sich überlappen. Solche Konstruktionen umschreiben, sodass es für jede Position nur einen eindeutigen Weg gibt, statt vieler mehrdeutiger.
3.
Den Ausdruck spezifischer machen
Ein zu gieriges, allgemeines Muster lässt viele Rücksprünge zu. Präzisere Zeichenklassen und feste Grenzen statt weit offener Platzhalter reduzieren die Zahl möglicher Pfade drastisch und beseitigen das Problem oft ganz.
4.
Eine sichere Regex-Umgebung nutzen
Manche Sprachen und Bibliotheken bieten eine Regex-Ausführung, die dieses Verhalten grundsätzlich nicht kennt (etwa auf endlichen Automaten basierend). Wo verfügbar, ist sie für Muster auf unkontrollierten Eingaben die robuste Wahl.
5.
Eingaben von außen absichern
Trifft ein solcher Ausdruck auf Eingaben aus dem Internet, wird aus dem Fehler eine Sicherheitslücke (ReDoS): Ein Angreifer kann mit einer kurzen, bösartigen Eingabe den Server lahmlegen. Eingabelänge begrenzen und eine Zeitgrenze für den Abgleich setzen.
Häufige Fragen (FAQ)
?Ein regulärer Ausdruck lässt mein Programm einfrieren. Wie ist das möglich?
Durch katastrophales Backtracking. Bei verschachtelten Wiederholungen – etwa (a+)+ – kann die Regex-Engine exponentiell viele Kombinationen durchprobieren, um doch noch eine Übereinstimmung zu finden. Bei einer harmlos aussehenden Eingabe von dreißig Zeichen sind das Milliarden Versuche. Das Programm stürzt nicht ab, es rechnet.
?Ist das ein Sicherheitsproblem?
Ja, und es hat einen Namen: ReDoS, ein Denial of Service durch reguläre Ausdrücke. Verarbeitet Ihr Dienst Eingaben von außen mit einem anfälligen Muster, genügt ein einziger präparierter Aufruf, um einen Prozessorkern dauerhaft zu blockieren. Muster, die auf Benutzereingaben angewendet werden, gehören daraufhin geprüft.
Belege
Diese Seite ist gegen die folgenden Primärquellen geprüft – Hersteller, Standard oder Gesetzestext. Wer es nicht glaubt, muss es nicht: Da steht, wo es nachzulesen ist.
Der Editor ruckelt, die Lüfter drehen auf? Typische Verdächtige sind Erweiterungen und riesige Ordner — eingebaute Werkzeuge grenzen den Übeltäter ein.
npm warnt nach der Installation vor Sicherheitslücken? Nicht jede ist gefährlich — und ein blindes npm audit fix kann mehr kaputt machen, als es behebt.
SWAnfängerfehlerrunning scripts is disabled on this system