ReDoS: Regular Expression Denial of Service verstehen

1. Katastrophales Backtracking: die Ursache von ReDoS

Die meisten regulären-Ausdruck-Engines, einschließlich PHPs PCRE-Engine, arbeiten nach dem Backtracking-Prinzip: Stimmt ein Teil eines Musters an einer bestimmten Position nicht mit der Eingabe überein, versucht die Engine systematisch alternative Wege, wie die vorherigen, bereits erfolgreich zugeordneten Teile des Musters anders aufgeteilt werden könnten, um doch noch eine Gesamtübereinstimmung zu finden. Bei den meisten Mustern ist dieser Rücksetzungs-Prozess harmlos und schnell, weil es nur wenige plausible alternative Aufteilungen gibt.

Bei bestimmten Musterkonstruktionen, insbesondere verschachtelten Quantifizierern wie `(a+)+` oder mehreren aufeinanderfolgenden Quantifizierern, die dieselben Zeichen matchen können wie `(a|a)*`, explodiert die Anzahl der möglichen alternativen Aufteilungen jedoch exponentiell mit der Eingabelänge, weil die Engine für jede zusätzliche Kombination aus "wie viele a matcht die äußere Gruppe" und "wie viele a matcht die innere Gruppe" eine neue, eigenständige Möglichkeit ausprobieren muss. Bei zwanzig wiederholten Zeichen sind das bereits über eine Million Kombinationen, bei dreißig Zeichen mehr als eine Milliarde, wodurch die Ausführungszeit bei linear wachsender Eingabelänge exponentiell explodiert.

2. Ein klassisches verwundbares Muster in der Praxis

Ein in freier Wildbahn immer wieder gefundenes, verwundbares Muster ist eine naive E-Mail-Validierung mit verschachtelten Quantifizierern für den Local-Part, die versucht, mehrere gültige Zeichenklassen mit optionalen Wiederholungen zu kombinieren, ohne zu bedenken, dass sich diese Zeichenklassen gegenseitig überlappen können. Eine speziell konstruierte Eingabe wie eine lange Folge von "a"-Zeichen gefolgt von einem einzelnen ungültigen Zeichen zwingt die Engine dazu, praktisch jede mögliche Aufteilung der "a"-Folge auf die verschachtelten Gruppen durchzuprobieren, bevor sie endgültig feststellt, dass keine Übereinstimmung existiert.

<?php
declare(strict_types=1);

// VERWUNDBAR: verschachtelte Quantifizierer, katastrophales Backtracking
$verwundbaresMuster = '/^([a-zA-Z0-9]+)+@[a-zA-Z0-9]+\.[a-zA-Z]+$/';

// Eingabe: 30 Zeichen "a" gefolgt von einem ungueltigen Zeichen "!"
$angreiferInput = str_repeat('a', 30) . '!';

// Diese eine Zeile kann den PHP-Prozess fuer sehr lange Zeit blockieren:
preg_match($verwundbaresMuster, $angreiferInput);

3. Gefährliche Regex-Muster zuverlässig erkennen

Drei Grundmuster sind fast immer verantwortlich für katastrophales Backtracking: verschachtelte Quantifizierer wie `(a+)+` oder `(a*)*`, mehrere aufeinanderfolgende Quantifizierer über sich überlappende Zeichenklassen wie `[a-z]+[a-zA-Z]+`, und Alternierungen mit überlappenden Optionen innerhalb eines wiederholten Blocks wie `(a|a)*` oder `(a|ab)*`. Der gemeinsame Nenner all dieser Muster ist, dass es für dieselbe erfolgreich zugeordnete Teilzeichenkette mehrere unterschiedliche Wege gibt, wie das Muster sie sich intern aufgeteilt haben könnte, wodurch die Backtracking-Engine bei einem Fehlschlag alle diese Wege einzeln durchprobieren muss.

Automatisierte Analysewerkzeuge wie `safe-regex` (für Node.js) oder vergleichbare statische Regex-Analysatoren erkennen diese drei Grundmuster zuverlässig, indem sie den regulären Ausdruck in seine Struktur zerlegen und nach genau diesen gefährlichen Kombinationen suchen, statt sich auf manuelle Code-Reviews zu verlassen, bei denen ein verschachtelter Quantifizierer inmitten eines komplexen Musters leicht übersehen wird.

4. Sichere Formulierung ohne verschachtelte Quantifizierer

Die robusteste Absicherung besteht darin, das Muster so umzuformulieren, dass für jede erfolgreich zugeordnete Teilzeichenkette nur genau ein möglicher interner Zerlegungsweg existiert, meist erreichbar durch das Entfernen unnötiger Verschachtelung und durch die Verwendung sich gegenseitig ausschließender statt überlappender Zeichenklassen.

<?php
declare(strict_types=1);

// SICHER: keine verschachtelten Quantifizierer, linear auswertbar
$sicheresMuster = '/^[a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-zA-Z]+$/';

// Fuer strengere E-Mail-Validierung: dedizierte, gehaertete Bibliothek
// statt selbstgeschriebener Regex verwenden (z.B. egulias/email-validator).
preg_match($sicheresMuster, $eingabe);

5. Timeout- und Ressourcenlimit-Strategien als zweite Verteidigungslinie

Selbst mit sorgfältig geprüften Mustern lohnt sich eine zweite Verteidigungslinie in Form eines harten Zeitlimits für die Regex-Ausführung, da neue, unbekannte verwundbare Muster jederzeit versehentlich eingeführt werden können, etwa über eine von einem Nutzer konfigurierbare Regex-Filterregel. PHPs `pcre.backtrack_limit`-Ini-Einstellung begrenzt die Anzahl der erlaubten Backtracking-Schritte und lässt `preg_match()` bei Überschreitung mit `false` und dem Fehlercode `PREG_BACKTRACK_LIMIT_ERROR` fehlschlagen, statt unbegrenzt weiterzulaufen.

Diese Ini-Einstellung ist allerdings ein globales Limit für den gesamten PHP-Prozess und kann nicht pro einzelnem Regex-Aufruf granular gesetzt werden, weshalb bei besonders kritischen, nutzergesteuerten Mustern zusätzlich ein expliziter Timeout auf Anwendungsebene sinnvoll ist, etwa durch Auslagern der Regex-Auswertung in einen separaten Prozess mit hartem Zeitlimit, wenn Nutzer eigene Suchmuster definieren dürfen.

6. ReDoS-Anfälligkeit gezielt testen

Eine effektive Testmethode für ReDoS-Anfälligkeit ist, jedes im Code vorkommende Regex-Muster gegen eine automatisch generierte, lange Wiederholung eines einzelnen, für das Muster charakteristischen Zeichens zu testen und dabei die Ausführungszeit zu messen, wobei ein überproportionaler, exponentieller Anstieg der Zeit bei linear wachsender Eingabelänge ein eindeutiges Warnsignal ist. Dieser Test lässt sich gut mit dem im Fuzzing-Artikel beschriebenen Coverage-guided Fuzzing kombinieren, da ein Fuzzer automatisch auf genau solche Eingaben stößt, ohne dass ein Mensch das verwundbare Muster vorher identifiziert haben müsste.

Spezialisierte Online-Werkzeuge und Bibliotheken zur statischen ReDoS-Analyse können zudem direkt in die CI-Pipeline integriert werden, um jedes neu hinzugefügte oder geänderte Regex-Muster automatisch gegen bekannte gefährliche Konstruktionen zu prüfen, bevor der Code überhaupt gemergt wird.

7. Framework-seitige Schutzmaßnahmen in Symfony

Symfonys Routing-Komponente und Validator-Constraints wie `Regex` nutzen intern ebenfalls PHPs PCRE-Engine und sind damit grundsätzlich genauso anfällig für ReDoS wie selbstgeschriebener Code, wenn ein Entwickler ein gefährliches Muster in eine Routen-Anforderung (`requirements`) oder eine `Regex`-Validierungs-Constraint einträgt. Da Routen-Muster typischerweise bei jedem einzelnen eingehenden Request ausgewertet werden, ist ein verwundbares Routen-Muster besonders kritisch, weil ein Angreifer keinen speziellen Endpunkt finden muss, sondern jede beliebige URL mit der präparierten Eingabe treffen kann.

Eine sinnvolle Absicherung ist deshalb, alle in `requirements`-Blöcken und `Regex`-Constraints verwendeten Muster genauso sorgfältig zu prüfen wie selbstgeschriebene Validierungslogik, da Symfony selbst keine automatische ReDoS-Prüfung für diese Muster durchführt.

8. Bekannte reale ReDoS-Vorfälle als Warnung

ReDoS ist keine rein theoretische Gefahr: Ein besonders bekannt gewordener Vorfall legte 2019 für rund 30 Minuten weltweit Cloudflares gesamte Content-Delivery-Infrastruktur lahm, ausgelöst durch ein einziges, verwundbares Regex-Muster in einer Web-Application-Firewall-Regel, das bei bestimmten Eingaben katastrophales Backtracking auslöste und dadurch die CPU-Auslastung auf allen betroffenen Servern nahezu gleichzeitig auf 100 Prozent trieb. Dieser Vorfall zeigt eindrücklich, dass selbst Unternehmen mit umfangreichen Sicherheitsteams und ausgereiften Testprozessen von ReDoS betroffen sein können, wenn ein einzelnes Muster durch die Prüfung rutscht.

Auch mehrere populäre npm-Pakete und PHP-Bibliotheken hatten in der Vergangenheit dokumentierte ReDoS-CVEs, oft in scheinbar harmlosen Hilfsfunktionen wie Trim-, URL- oder Datums-Parsing-Routinen, was zeigt, dass ReDoS-Schwachstellen nicht nur in offensichtlich komplexen, selbstgeschriebenen Mustern lauern, sondern auch in weit verbreiteten, viel genutzten Standardbibliotheken auftreten können, die von tausenden anderen Projekten als vermeintlich vertrauenswürdige, gut getestete Grundlage eingebunden werden, ohne dass die einzelnen Nutzer dieser Bibliotheken die verwendeten Muster jemals selbst geprüft hätten.

Die Lehre aus diesen Vorfällen ist, dass ReDoS-Prüfungen nicht nur für offensichtlich komplexe, selbst geschriebene Validierungsmuster gelten sollten, sondern grundsätzlich für jeden regulären Ausdruck, der potenziell nutzergesteuerte oder extern beeinflussbare Eingaben verarbeitet, unabhängig davon, ob dieser Ausdruck aus eigenem Code stammt oder Teil einer eingebundenen, scheinbar etablierten und langjährig bewährten Drittanbieter-Bibliothek ist, deren interne Implementierungsdetails die allerwenigsten Nutzer jemals tatsächlich vollständig gelesen und nachvollzogen haben. Genau dieses blinde Vertrauen in scheinbar bewährten Fremdcode ist der eigentliche gemeinsame Nenner fast aller hier beschriebenen realen Vorfälle.

9. Schutzmaßnahmen im Überblick

Die folgende Tabelle vergleicht die vorgestellten Schutzmaßnahmen gegen ReDoS.

10. Zusammenfassung

11. FAQ: ReDoS: Das Wichtigste auf einen Blick