Ein Regex-Muster kann mit normalen Beispielen sofort reagieren und bei einer leicht veränderten Eingabe plötzlich Sekunden oder Minuten benötigen. Ursache ist oft Backtracking: Die Engine probiert verschiedene Aufteilungen wiederholbarer Teile aus, nachdem ein späterer Abschnitt nicht passt. Gibt es sehr viele gleichwertige Möglichkeiten, wächst die Sucharbeit explosionsartig. Bei nicht vertrauenswürdigen Inputs wird daraus Regular Expression Denial of Service, kurz ReDoS.
Backtracking ist zunächst ein nützlicher Mechanismus
Eine traditionelle Engine versucht einen Pfad durch das Muster. Scheitert ein späterer Teil, kehrt sie zu einer früheren Entscheidung zurück und probiert eine andere Länge oder Alternative. Dadurch funktionieren flexible Quantifizierer und Alternativen so intuitiv.
Problematisch wird es, wenn viele Pfade denselben Text auf unterschiedliche Weise konsumieren können. Ein endgültiges Scheitern zwingt die Engine dann, einen großen Suchbaum nahezu vollständig zu erkunden.
Verschachtelte Quantifizierer sind ein Warnsignal
Muster nach dem Prinzip (a+)+ erlauben, dieselbe Folge von a-Zeichen in zahlreiche innere Gruppen aufzuteilen. Folgt am Ende ein erwartetes b, ist ein Input aus vielen a und einem falschen Schlusszeichen besonders teuer. Jeder erfolglose Versuch erzeugt weitere Aufteilungen.
Nicht jede Verschachtelung ist automatisch gefährlich, aber überlappende Wiederholungen verdienen Review und Lasttests. Je weniger eindeutig ein Zeichen einem Teil des Patterns zugeordnet werden kann, desto größer das Risiko.
Mehrdeutige Alternativen erzeugen ähnliche Kosten
(a|aa)+ kann eine lange a-Folge auf viele Arten zerlegen. Auch realistische Alternativen mit gemeinsamen Präfixen besitzen dieses Problem. Wenn anschließend ein zwingender Suffix fehlt, muss die Engine immer neue Kombinationen prüfen.
Gemeinsame Teile sollten herausgezogen oder Alternativen so gestaltet werden, dass sie sich früh unterscheiden. Eine deterministischere Grammatik ist meist sowohl lesbarer als auch schneller.
Ein unbeschränkter Punkt vergrößert den Suchraum
.* kann fast den gesamten Rest des Inputs aufnehmen. Kommen mehrere solche Abschnitte oder optionale Gruppen zusammen, entstehen viele mögliche Grenzen. Eine negierte Zeichenklasse bis zu einem bekannten Separator beschreibt die Absicht genauer.
Auch Längenbegrenzungen helfen. Wenn ein Feld fachlich höchstens 200 Zeichen besitzen darf, sollte diese Grenze vor der Regex und möglichst im Pattern sichtbar sein. Unendliche Flexibilität ist selten eine echte Anforderung.
Erfolgreiche Beispiele zeigen das Problem oft nicht
Bei einem passenden Input findet die Engine möglicherweise sofort einen Weg. Der Worst Case ist häufig ein fast passender String: sehr langer erlaubter Präfix, gefolgt von einem einzigen falschen Zeichen. Deshalb müssen Performance-Tests gezielt Nicht-Matches enthalten.
Die Testlängen sollten schrittweise wachsen. Wenn sich bei Verdopplung des Inputs die Laufzeit vervielfacht statt ungefähr linear zu steigen, ist das ein starkes Warnsignal.
Atomare Gruppen und possessive Quantifizierer begrenzen Rückwege
Ein possessiver Quantifizierer gibt konsumierten Text nicht wieder frei. Eine atomare Gruppe verhindert Backtracking in ihren bereits erfolgreichen Teil. Beide Features können eine eindeutige Entscheidung ausdrücken und den Suchbaum stark verkleinern.
Sie sind jedoch kein blindes Performancepflaster. Wenn ein späterer Teil tatsächlich Text zurückbenötigt, ändert die atomare Form die akzeptierte Sprache. Tests müssen beweisen, dass die früh festgelegte Grenze fachlich korrekt ist.
Lineare Engines vermeiden die ganze Fehlerklasse
RE2 und ähnliche Engines garantieren für unterstützte Konstrukte eine lineare Laufzeit und verzichten dafür unter anderem auf manche Backreferences und Lookarounds. Bei untrusted Input kann dieser Trade-off sehr attraktiv sein.
Ein Enginewechsel ist nicht immer möglich, weil bestehende Muster Features benötigen. Für neue Validierungen lohnt dennoch die Frage, ob die zusätzliche Ausdrucksmacht wirklich gebraucht wird.
Timeouts sind eine zweite Verteidigung
Einige Plattformen erlauben ein Regex-Zeitlimit oder eine maximale Zahl interner Schritte. Das schützt einen Prozess vor unbegrenzter Arbeit, macht ein schlechtes Pattern aber nicht effizient. Viele parallele Requests können auch jeweils unterhalb des Limits Ressourcen binden.
Timeouts sollten mit Input-Limits, Rate Limits und Pattern-Verbesserungen kombiniert werden. Ein Abbruch muss als kontrollierter Validierungsfehler behandelt und beobachtbar gemacht werden.
Input-Limits gehören vor die teure Verarbeitung
Eine E-Mail-Adresse, ein Benutzername oder eine Route hat eine sinnvolle Maximallänge. Der Server sollte übergroße Werte ablehnen, bevor komplexe Regex, Unicode-Normalisierung oder Datenbankabfragen beginnen. HTTP- und Feldlimits bilden gemeinsam eine Kostenbegrenzung.
Das Limit muss in Bytes und Zeichen korrekt verstanden werden. Ein Unicode-String kann je nach Darstellung unterschiedlich viele Bytes belegen, während die Engine auf Codepoints oder Code Units arbeitet.
Dynamische Regex vergrößert das Risiko
Darf ein Nutzer selbst ein Pattern liefern, kann er absichtlich ein teures Konstrukt wählen. Das Escapen von Eingabedaten hilft nur, wenn sie als Literal gemeint sind. Für echte benutzerdefinierte Suche braucht es eine sichere Engine, strenge Limits oder eine eingeschränkte Abfragesprache.
Auch intern konfigurierte Patterns sollten wie Code reviewed werden. Eine Änderung in einem Administrationsfeld kann dieselbe Produktionswirkung wie ein Deployment besitzen.
Profiler und statische Analyse liefern Hinweise
Werkzeuge können verschachtelte Quantifizierer und überlappende Alternativen markieren. Sie beweisen nicht immer eine reale Schwachstelle, helfen aber bei der Priorisierung. Laufzeitmessungen mit repräsentativen Worst-Case-Inputs bleiben entscheidend.
In Produktion können Metriken zu Matchdauer, Timeouts und Inputlänge ungewöhnliche Muster zeigen. Der vollständige sensible Text muss dafür nicht geloggt werden.
Manchmal ist ein kleiner Parser einfacher
Wenn ein Format aus klaren Trennzeichen und mehreren Regeln besteht, kann eine lineare Schleife oder ein Parser verständlicher und garantiert schnell sein. Erst splitten, dann jeden Teil prüfen, reduziert Mehrdeutigkeit und verbessert Fehlermeldungen.
Die kürzeste Quelltextzeile ist nicht automatisch die einfachste Ausführung. Ein paar explizite Schritte können sowohl Sicherheitsrisiko als auch Wartungsaufwand senken.
ReDoS-Prävention ist Teil normaler Eingabevalidierung
Ein sicheres Pattern besitzt eindeutige Wiederholungen, begrenzte Eingaben und Tests für lange Nicht-Matches. Wo möglich, liefert eine lineare Engine zusätzliche Garantien. Timeouts und Metriken begrenzen den Schaden verbleibender Fehler.
Regex sollte Text erkennen, nicht unkontrolliert nach einer möglichen Interpretation suchen. Sobald ein Ausdruck viele gleichwertige Wege durch denselben Input besitzt, ist das ein Architekturhinweis: Die Grammatik muss präziser oder das Werkzeug gewechselt werden.