Reguläre Ausdrücke: Catastrophic Backtracking und Performance-Fallstricke in PHP

1. Wie PCRE-Backtracking grundsätzlich funktioniert

PHPs preg-Funktionen basieren auf der PCRE-Bibliothek, die einen sogenannten backtracking-basierten Matching-Algorithmus verwendet, im Unterschied zu alternativen Ansätzen wie einer echten NFA-Simulation ohne Rücksetzpunkte, wie sie etwa RE2 nutzt. Backtracking bedeutet konkret: Trifft die Engine bei einem Quantifizierer wie + oder * auf mehrere mögliche Interpretationen, wie viele Zeichen dieser konsumieren soll, probiert sie zunächst die gierigste Variante, merkt sich dabei aber einen Rücksetzpunkt, zu dem sie zurückkehren kann, falls der restliche Ausdruck an dieser Stelle später nicht mehr passt.

Für die allermeisten Patterns bleibt die Anzahl dieser Rücksetzpunkte klein und das Matching läuft in linearer oder nahezu linearer Zeit relativ zur Eingabelänge ab. Problematisch wird es erst, wenn ein Pattern mehrdeutig ist in dem Sinn, dass dieselbe Eingabe auf viele unterschiedliche Weisen durch dasselbe Pattern konsumiert werden kann, denn dann muss die Engine im schlimmsten Fall jede dieser Interpretationen einzeln durchprobieren, bevor sie endgültig feststellt, dass kein Match existiert.

2. Catastrophic Backtracking: Verschachtelte Quantifizierer als Ursache

Der klassische Auslöser für catastrophic Backtracking ist ein Quantifizierer innerhalb eines weiteren Quantifizierers, wobei sich beide Ebenen in ihrer Zeichenmenge überschneiden, etwa das Pattern (a+)+ oder (a|aa)+. Bei einer Eingabe wie 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX', die am Ende bewusst nicht zum Pattern passt, muss die Engine jede mögliche Aufteilung der a-Zeichen auf die innere und äußere Wiederholung durchprobieren, bevor sie endgültig aufgibt, und die Anzahl dieser Aufteilungen wächst exponentiell mit der Länge der Eingabe.

Der entscheidende Mechanismus dahinter ist, dass jedes zusätzliche a-Zeichen die Anzahl möglicher Kombinationen verdoppelt, da es entweder von der inneren Wiederholung a+ konsumiert werden kann oder von einer zusätzlichen Iteration der äußeren Klammer. Bei zwanzig zusätzlichen Zeichen bedeutet das bereits über eine Million Kombinationen, bei dreißig Zeichen über eine Milliarde, ein Wachstum, das jede realistische Antwortzeit sprengt und einen einzelnen PHP-Worker-Prozess für die Dauer eines einzigen Requests komplett blockiert.

3. Praktisches Beispiel: Ein gefährliches Pattern und seine Entschärfung

Ein realistisches Beispiel aus der Praxis ist eine naive Validierung von E-Mail-artigen Strings mit einem Pattern wie ^([a-zA-Z0-9._-]+)+@, das eigentlich nur die Zeichen vor dem At-Zeichen prüfen soll, dabei aber versehentlich einen Quantifizierer um einen bereits selbst quantifizierten Ausdruck legt. Eine Eingabe wie eine sehr lange Zeichenkette gültiger Zeichen ohne abschließendes At-Zeichen bringt dieses Pattern bereits bei wenigen Dutzend Zeichen in den mehrsekündigen Bereich, obwohl das eigentliche Matching-Ziel simpel ist.

Die Entschärfung besteht fast immer darin, die redundante äußere Verschachtelung zu entfernen: Aus ([a-zA-Z0-9._-]+)+ wird schlicht [a-zA-Z0-9._-]+, ohne dass sich das eigentlich gewünschte Matching-Ergebnis für gültige Eingaben ändert, denn die äußere Wiederholung war ohnehin funktional überflüssig und existierte nur durch ein Versehen beim Zusammensetzen des Patterns aus mehreren Teilausdrücken. Diese Art von Redundanz entsteht in der Praxis besonders häufig, wenn Patterns aus mehreren Quellen zusammenkopiert oder programmatisch aus Bausteinen generiert werden.

<?php

declare(strict_types=1);

// Gefährlich: verschachtelter Quantifizierer über denselben Zeichenraum.
$dangerousPattern = '/^([a-zA-Z0-9._-]+)+@[a-zA-Z0-9.-]+$/';

// Entschärft: die äußere Wiederholung war funktional überflüssig.
$safePattern = '/^[a-zA-Z0-9._-]+@[a-zA-Z0-9.-]+$/';

$maliciousInput = str_repeat('a', 40) . '!';

// Mit $dangerousPattern kann dieser Aufruf mehrere Sekunden blockieren.
$result = preg_match($safePattern, $maliciousInput);

4. pcre.backtrack_limit richtig konfigurieren

PHP begrenzt die Anzahl der Backtracking-Schritte standardmäßig über die INI-Einstellung pcre.backtrack_limit, deren Default-Wert bei eine Million liegt. Wird dieses Limit während eines Matching-Vorgangs überschritten, bricht die Engine ab, preg_match liefert false statt eines Fehlers zurück, und die Funktion preg_last_error meldet den spezifischen Fehlercode PREG_BACKTRACK_LIMIT_ERROR, der sich klar von einem regulären Nicht-Match unterscheiden lässt.

Der Wert von einer Million ist bewusst hoch genug gewählt, um die meisten legitimen, auch komplexeren Patterns nicht zu behindern, aber niedrig genug, um catastrophic Backtracking nach spätestens wenigen hundert Millisekunden statt nach Minuten abzubrechen. Für Anwendungen, die Nutzereingaben gegen extern konfigurierbare oder generierte Patterns prüfen, lohnt sich ein bewusst niedrigeres Limit über ini_set direkt vor dem betreffenden preg-Aufruf, kombiniert mit konsequenter Prüfung von preg_last_error, statt sich blind auf einen erfolgreichen Rückgabewert zu verlassen.

<?php

declare(strict_types=1);

/**
 * Prüft eine Eingabe gegen ein extern konfigurierbares Pattern und
 * unterscheidet explizit zwischen Nicht-Match und Backtracking-Abbruch.
 *
 * @param string $pattern Ein extern konfiguriertes PCRE-Pattern
 * @param string $subject Die zu prüfende Eingabe
 * @return bool True, wenn das Pattern zuverlässig gematcht hat
 * @throws RuntimeException Wenn das Backtracking-Limit überschritten wurde
 */
function safeMatch(string $pattern, string $subject): bool
{
    $previousLimit = ini_set('pcre.backtrack_limit', '200000');

    try {
        $result = preg_match($pattern, $subject);

        if (preg_last_error() === PREG_BACKTRACK_LIMIT_ERROR) {
            throw new RuntimeException('Pattern überschritt das Backtracking-Limit.');
        }

        return $result === 1;
    } finally {
        ini_set('pcre.backtrack_limit', $previousLimit);
    }
}

5. preg_last_error und konsequente Fehlerbehandlung

Ein häufiger Fehler in produktivem Code ist, den Rückgabewert von preg_match nur binär als match oder kein match zu interpretieren, ohne zwischen einem echten Nicht-Match und einem stillen Abbruch durch Erreichen eines Limits zu unterscheiden. Da beide Fälle denselben Rückgabewert false beziehungsweise 0 liefern, kann eine Anwendung bei catastrophic Backtracking fälschlich annehmen, eine Eingabe sei ungültig, obwohl in Wahrheit die Prüfung gar nicht zu Ende geführt wurde.

Neben PREG_BACKTRACK_LIMIT_ERROR existieren mit PREG_RECURSION_LIMIT_ERROR, gesteuert über pcre.recursion_limit, sowie PREG_INTERNAL_ERROR und PREG_JIT_STACKLIMIT_ERROR weitere spezifische Fehlercodes, die jeweils unterschiedliche interne Ressourcenlimits betreffen. Für sicherheitskritische Validierungen, etwa bei Formulareingaben aus dem öffentlichen Internet, sollte preg_last_error nach jedem preg_match-Aufruf konsequent geprüft und im Fehlerfall bewusst als 'Validierung fehlgeschlagen' statt als 'Eingabe ungültig' behandelt werden.

6. Possessive Quantifiers als direkte Gegenmaßnahme

PCRE unterstützt possessive Quantifiers in der Form ++, *+ und ?+, die sich von den regulären, gierigen Quantifizierern dadurch unterscheiden, dass sie nach dem ersten Konsumieren von Zeichen keinerlei Rücksetzpunkte mehr hinterlassen. Ein possessive Quantifizierer probiert also nicht mehrere Aufteilungen durch, sondern konsumiert einmalig maximal viele Zeichen und gibt bei einem späteren Fehlschlag des restlichen Patterns sofort komplett auf, ohne zurückzugehen und alternative Aufteilungen zu testen.

Für das zuvor gezeigte problematische Pattern bedeutet das: (a+)+ wird durch die possessive Variante (a++)++ funktional zu einer festen, nicht mehr rücksetzbaren Konsumierung, wodurch catastrophic Backtracking bei diesem konkreten Ausdruck strukturell unmöglich wird. Der Kompromiss ist, dass possessive Quantifiers bestimmte, seltene aber legitime Matching-Fälle verhindern können, bei denen ein Rücksetzen tatsächlich notwendig gewesen wäre, weshalb sie gezielt und nicht pauschal auf jeden Quantifizierer im Pattern angewendet werden sollten.

<?php

declare(strict_types=1);

// Possessive Quantifiers verhindern Rücksetzen und damit catastrophic
// Backtracking strukturell, auf Kosten weniger Flexibilität.
$possessivePattern = '/^([a-zA-Z0-9._-]++)++@[a-zA-Z0-9.-]+$/';

$result = preg_match($possessivePattern, 'user.name@example.com');

7. Atomic Groups: dieselbe Idee ohne possessive Syntax

Atomic Groups, geschrieben als (?>...), erreichen konzeptionell dasselbe Ziel wie possessive Quantifiers, wenden das Prinzip aber auf eine ganze Gruppe statt auf einen einzelnen Quantifizierer an: Sobald die Engine die Gruppe erfolgreich einmal durchlaufen hat, wird jeder interne Rücksetzpunkt innerhalb dieser Gruppe verworfen, und ein späterer Fehlschlag im restlichen Pattern kann nicht mehr in die Gruppe zurückspringen, um eine alternative innere Aufteilung zu probieren.

Atomic Groups sind besonders dann das passendere Werkzeug, wenn nicht ein einzelner Quantifizierer, sondern eine ganze Sequenz aus mehreren Elementen vor Rücksetzen geschützt werden soll, etwa (?>[a-z]+[0-9]+) als Ganzes. Sie lassen sich außerdem mit älteren PCRE-Versionen kombinieren, die möglicherweise noch keine possessive Quantifiers unterstützen, wobei aktuelle PHP-Versionen mit PCRE2 beide Konstrukte vollständig unterstützen und die Wahl damit primär eine Frage von Lesbarkeit und Struktur des jeweiligen Patterns ist.

8. Alternative Strategien: Pattern vereinfachen statt reparieren

Neben possessive Quantifiers und Atomic Groups lohnt sich häufig die grundsätzlichere Frage, ob ein komplexes, potenziell mehrdeutiges Pattern überhaupt nötig ist, oder ob sich dasselbe Ziel durch mehrere einfache, garantiert lineare Patterns in Kombination mit regulärem PHP-Code erreichen lässt. Eine E-Mail-Validierung etwa lässt sich oft in eine grobe Format-Vorprüfung mit einem einfachen Pattern und eine anschließende, genauere Prüfung mit filter_var und FILTER_VALIDATE_EMAIL aufteilen, was komplett ohne selbstgeschriebene, potenziell gefährliche Backtracking-Konstrukte auskommt.

Für sehr komplexe Grammatiken, etwa das Parsen strukturierter Formate wie CSV-Dialekte oder verschachtelte Klammerausdrücke, ist ein dedizierter, handgeschriebener Parser oft nicht nur sicherer, sondern auch wartbarer als ein einzelnes, hochkomplexes Regex-Pattern, selbst wenn der initiale Implementierungsaufwand höher erscheint. Die Faustregel lautet: Sobald ein Pattern mehr als zwei oder drei verschachtelte Quantifizierer-Ebenen benötigt, lohnt sich eine grundsätzliche Überarbeitung der Herangehensweise.

9. Testing und Monitoring: ReDoS-anfällige Patterns identifizieren

Statische Analyse-Tools wie der npm-Paket-basierte safe-regex-Checker oder rxxr2 können Patterns automatisiert auf strukturelle Merkmale von catastrophic Backtracking untersuchen und lassen sich in eine CI-Pipeline integrieren, um neue oder geänderte Patterns vor dem Merge zu prüfen. Ergänzend dazu lohnt sich ein gezielter Unit-Test pro sicherheitsrelevantem Pattern, der eine bewusst konstruierte, lange, am Ende nicht passende Eingabe gegen das Pattern matcht und dabei eine harte Zeitgrenze mittels set_time_limit oder einer Testframework-eigenen Timeout-Funktion durchsetzt.

Im produktiven Betrieb ergänzt Monitoring der php-fpm-Request-Dauer diese präventiven Maßnahmen: Ein plötzlicher Anstieg vereinzelter, extrem langsamer Requests bei ansonsten stabiler Last ist ein starkes Indiz für catastrophic Backtracking, ausgelöst durch eine bislang unentdeckte, bösartige oder einfach nur unglücklich gewählte Eingabe, und rechtfertigt eine gezielte Nachprüfung der beteiligten Patterns, selbst wenn die vorherige statische Analyse unauffällig war.

10. Zusammenfassung

11. FAQ: Regex-Backtracking: Das Wichtigste auf einen Blick