Regular Expression Denial of Service (ReDoS) und katastrophales Backtracking

Reguläre Ausdrücke sind unglaublich leistungsstark, doch kaum jemand würde behaupten, dass sie besonders intuitiv sind. Klar, Sie kennen vielleicht den einen Entwickler, der sich damit bestens auskennt. Die meisten Entwickler wissen jedoch gerade genug, um sich in Gefahr zu bringen. Leider sind die Sicherheitsrisiken bei regulären Ausdrücken erheblich. Ein falsches Verständnis regulärer Ausdrücke kann Angreifern letztlich dabei helfen, Ihre Website lahmzulegen. Sehen wir uns den folgenden regulären Ausdruck als Beispiel an:

regex = /A(B|C+)+D/

Aufgeschlüsselt bewirkt dieser reguläre Ausdruck Folgendes:

• A Die Zeichenfolge muss mit dem Buchstaben „A“ beginnen.

• (B|C+)+ Auf den Buchstaben A muss entweder der Buchstabe „B“ oder eine beliebige Anzahl von „C“-Zeichen folgen (das + steht für eine oder mehrere Wiederholungen). Das + am Ende dieses Abschnitts besagt, dass nach einer oder mehreren Übereinstimmungen mit diesem Abschnitt gesucht werden kann.

• D Zum Schluss stellen wir sicher, dass dieser Abschnitt der Zeichenfolge mit einem „D“ endet.

Der Ausdruck würde beispielsweise auf folgende Eingaben zutreffen:

ABBD
ABCCCCD
ABCBCCCD
ACCCCCD

Im Allgemeinen dauert es für eine Regex-Engine nicht lange, eine Übereinstimmung zu finden. Sehen wir uns zum Beispiel an, was passiert, wenn wir den Ausdruck mit der folgenden 30 Zeichen langen Zeichenfolge testen: „ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD“.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total

Wie erwartet stimmt die Zeichenfolge mit dem Ausdruck überein – und zwar schnell. Der gesamte Vorgang dauert etwa 52 ms (getestet auf einem MacBook Air). Sehen wir uns nun an, was passiert, wenn wir eine andere 30 Zeichen lange Zeichenfolge testen. Diesmal geben wir keine gültige Zeichenfolge an, sondern ersetzen das abschließende „D“ durch ein „X“: „ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX“.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total

Plötzlich dauert der Test fast zwei Sekunden – mehr als zehnmal so lange wie bei einer gültigen Zeichenfolge! Dieser erhebliche Unterschied ist auf die Auswertung regulärer Ausdrücke zurückzuführen. Kurz gesagt: Sie geben nicht gerne auf.

So funktionieren Regex-Engines

Regex-Engines unterscheiden sich, funktionieren aber meist sehr ähnlich. Die Engine sucht nach der ersten möglichen Art, das aktuelle Zeichen zu akzeptieren, und fährt mit dem nächsten fort. Kann sie das nächste Zeichen nicht zuordnen, geht sie zurück und prüft, ob es eine andere Möglichkeit gab, das vorherige Zeichen zu verarbeiten. Verfolgt sie diesen Ansatz zu weit und stellt erst dann fest, dass die Zeichenfolge letztlich nicht übereinstimmt, kann die Anzahl der Backtracking-Schritte sehr groß werden – insbesondere, wenn viele Zeichen mehrere gültige Regex-Pfade haben. Das Ergebnis ist das sogenannte katastrophale Backtracking. Sehen wir uns anhand einer kürzeren Zeichenfolge an, wie unser Ausdruck auf dieses Problem stößt: „ACCCX“. Das scheint recht einfach, doch es gibt immer noch vier verschiedene Möglichkeiten, wie die Engine diese drei C zuordnen kann:

1. CCC

2. CC+C

3. C+CC

4. C+C+C.

Die Engine muss jede dieser Kombinationen ausprobieren, um festzustellen, ob eine davon zum Ausdruck passt. Berücksichtigt man auch die weiteren erforderlichen Schritte, zeigt der RegEx 101-Debugger, dass die Engine insgesamt 38 Schritte ausführen muss, bevor sie feststellen kann, dass die Zeichenfolge nicht übereinstimmt. Danach nimmt die Anzahl der Schritte, die die Engine zur Validierung einer Zeichenfolge ausführen muss, immer weiter zu.

Sobald die Zeichenfolge 14 C enthält, muss die Engine mehr als 65.000 Schritte ausführen, nur um festzustellen, ob sie gültig ist. Stellen Sie sich nun vor, wie dieser Vorgang bei unserer ursprünglichen Zeichenfolge abläuft: „ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX“. Sie sehen, wie schnell dieses Backtracking außer Kontrolle geraten kann. Der folgende Screenshot zeigt nur einen kleinen Ausschnitt der Arbeit, die die Engine laut RegEx101-Debugger ausgeführt hat.

Wenn man bedenkt, wie die Engine einen regulären Ausdruck auswertet, wird der enorme Anstieg der Verarbeitungszeit bei einem ungültigen Ausdruck verständlicher: Zwischen der Länge der Zeichenfolge und der Anzahl der auszuwertenden Pfade besteht ein exponentieller Zusammenhang. Fügen wir unserer ungültigen Sequenz nur ein weiteres Zeichen hinzu, verdoppelt sich die Auswertungszeit nahezu.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
3.51s user 0.06s system 95% cpu 3.732 total

Node und ReDoS

Angreifer können die Komplexität der Auswertung regulärer Ausdrücke ausnutzen, indem sie eine lange, komplizierte Zeichenfolge übergeben, deren Auswertung die Engine unverhältnismäßig viel Zeit kostet. Das Ergebnis ist ein sogenannter Regular Expression Denial of Service (ReDoS).

Das ist in jeder Umgebung problematisch, in JavaScript-Umgebungen einschließlich Node jedoch besonders. Wie wir bereits in unserem Beitrag zu Timing-Angriffen erklärt haben, sind Node.js (und JavaScript im Allgemeinen) ereignisgesteuert.

Das bedeutet: Wird ein Thread durch eine erfolgreiche ReDoS-Anfrage belegt, blockiert diese Anfrage die gesamte Ereignisschleife, und die Anwendung kann keine anderen Aufgaben mehr ausführen.

Ein Beispiel aus der Praxis

Sehen wir uns ein aktuelles Beispiel aus der Praxis an, das in der beliebten moment-Bibliothek gefunden wurde. moment wird zum Parsen, Validieren, Bearbeiten und Formatieren von Datumsangaben verwendet. Mit dem Tool können Sie über die Methode format() das gewünschte Ausgabeformat für Ihr Datum festlegen:

moment().format('MMM Do YY');

//example output: Nov 22nd 16

Wenn Sie das Format definieren, verwendet moment einen regulären Ausdruck, um es zu überprüfen. In Versionen von moment vor 2.15.2 sieht der reguläre Ausdruck so aus:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/;

Entscheidend ist hier der Teil (\[[^\[\]]*\]|\s+)+ des Ausdrucks. Besonders wichtig ist, dass \s+ auf ein oder mehrere Leerzeichen prüft. Das + direkt außerhalb dieser Gruppe bedeutet jedoch auch, dass die in Klammern verschachtelte Gruppe ein- oder mehrmals vorkommen kann. Dadurch gibt es für die Regex-Engine viele verschiedene Möglichkeiten, diese Zeichen zu gruppieren, wenn das Format viele Leerzeichen enthält. Sie kann sie zu einer großen Gruppe zusammenfassen, die einmal erkannt wird, in einzelne Gruppen aufteilen, die jeweils separat erkannt werden, oder eine beliebige Variante dazwischen wählen. Daher kann die Auswertung einer Zeichenfolge, die nur knapp ungültig ist, sehr lange dauern.

Sehen Sie sich dieses Beispiel an, das wir veröffentlicht haben, als wir die Schwachstelle entdeckten:

var m = require("moment");
m.locale("be");
m().format("D                               MMN MMMM");
// Normal date format, other than the 31 spaces included in the string

In diesem Fall übergeben wir eine 40 Zeichen lange Zeichenfolge mit zahlreichen Leerzeichen. Auf einem handelsüblichen Laptop blockiert der Ausdruck die Ereignisschleife etwa 20 Sekunden lang.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/.test("D                               MMN MMMM");'
21.24s user 0.14s system 96% cpu 22.079 total

Nachdem wir moment über die Schwachstelle informiert hatten, erstellte der Autor eine Korrektur (Sie können jetzt testen, ob der Patch bei Ihnen greift), die den überflüssigen +-Operator innerhalb der Klammern entfernt:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/;

Damit vermeiden Sie zwei verschiedene übereinstimmende Gruppen, die jeweils eine bis alle Leerstellen enthalten könnten. Da auf das +-Zeichen kein s mehr folgt, kann es nur noch jeweils ein Leerzeichen erfassen. Testen Sie die Zeichenfolge erneut mit dem neuen regulären Ausdruck, benötigt die Engine nur noch wenige Millisekunden, um festzustellen, dass sie nicht übereinstimmt.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/.test("D                               MMN MMMM");'
0.05s user 0.02s system 53% cpu 0.135 total

Katastrophales Backtracking verhindern

Um katastrophales Backtracking zu verhindern, sollten Sie darauf achten, ob Sie die Operatoren „+“ oder „*“ in unmittelbarer Nähe zueinander verwenden. Ist das der Fall, können sie leicht in eine Art Tauziehen geraten, das zu katastrophalem Backtracking führt. Vergewissern Sie sich, dass beide Operatoren tatsächlich erforderlich sind. Sie können auch einen davon durch eine begrenzte Anzahl ersetzen. Falls Sie sich an die ReDoS-Schwachstelle in moment erinnern: Wir haben sie behoben, indem wir einen der „+“-Operatoren entfernt haben. Alternativ hätten wir einen davon durch einen Bereich ersetzen und so die Zahl der Leerzeichen in einer gültigen Zeichenfolge begrenzen können:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+){0,10}MMMM?/;

Regex-Parser sind ziemlich simpel, doch einige Sprachen bieten erweiterte Funktionen, mit denen sich katastrophales Backtracking verhindern lässt. Betrachten wir zum Beispiel den vereinfachten Ausdruck, mit dem wir begonnen haben:

regex = /A(B|C+)+D/

Atomare Gruppen

Wie bereits erläutert, kann der Ausdruck zu katastrophalem Backtracking führen. Der in Node.js unterstützte Parser für reguläre Ausdrücke bietet keine native Funktion, mit der sich das Problem beheben lässt. In einigen anderen Sprachen ist das anders. Ruby unterstützt beispielsweise sogenannte atomare Gruppen. Damit können Sie dem Regex-Parser mitteilen, bei einer gefundenen Übereinstimmung nicht zurückzugehen. Dazu stellen Sie einer Gruppe ?> voran, etwa so:

/A(?>B|C+)+D/

Wenn Sie der Gruppe, die nach einer beliebigen Anzahl von „C“ sucht, ?> hinzufügen, wird sie zu einer atomaren Gruppe. Zuvor muss der Regex-Parser zwei konkurrierende Operatoren berücksichtigen: Das „C“ innerhalb der Gruppe kann beliebig oft vorkommen, ebenso die Gruppe selbst. Wird also ein ungültiger Ausdruck mit vielen „C“-Zeichen übergeben, gerät der Parser in einen Wettstreit zwischen den beiden Gruppen und versucht wiederholt, eine magische Kombination zu finden, durch die der Ausdruck gültig wird.

Mit atomarer Gruppierung fixiert der Parser jedoch die Übereinstimmung dieser Gruppe. In diesem Fall erfasst er so viele „C“, wie vorhanden sind. Ist der Ausdruck ungültig, kann der Parser diese Gruppe nicht erneut durchlaufen – die Zuordnung ist an diesem Punkt endgültig. Da die „C“ nicht mehr zwischen den beiden möglichen übereinstimmenden Operatoren aufgeteilt werden müssen, wird ein ungültiger Ausdruck sehr schnell erkannt und katastrophales Backtracking verhindert.

Lookahead

JavaScript unterstützt zwar keine atomaren Gruppen, aber LookAhead. Damit lässt sich im Wesentlichen derselbe Effekt wie mit atomarer Gruppierung erzielen.

A(?=(B|C+))\1+D

In diesem Fall verwenden wir ?=, um einen Lookahead anzugeben. Das bedeutet, dass der reguläre Ausdruck die Gruppe nur dann erfasst, wenn unmittelbar danach die nächste Gruppe folgt. Mit \1 erfassen wir die übereinstimmende Gruppe und erzeugen damit effektiv eine atomare Gruppe. Der Parser behandelt diese Übereinstimmung nun wie eine atomare Gruppe und verhindert katastrophales Backtracking.

Wenn wir unsere Zeichenfolge jetzt mit dem Ausdruck samt Lookahead testen, sehen wir, dass sich die Zeit bis zur Zurückweisung drastisch verkürzt hat: von 1,8 Sekunden ohne Lookahead auf 94 ms mit Lookahead.

$ time node -e '/A(?=(B|C+))\1+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
0.05s user 0.02s system 51% cpu 0.094 total

Der Kompromiss besteht hier in der Komplexität. Sie verhindern zwar katastrophales Backtracking, erhöhen aber die Komplexität Ihres Ausdrucks. Dadurch wird er für andere Teammitglieder schwerer verständlich und es wird einfacher, Fehler einzubauen. Wenn Sie die Kombination der Operatoren erkennen, die Backtracking verursachen könnte (in diesem Fall die beiden +), ist es möglicherweise besser, den Ausdruck insgesamt neu zu gestalten, damit er klarer und lesbarer ist.

Zusammenfassung

ReDoS-Angriffe können eine Anwendung vollständig lahmlegen. Das gilt besonders für Node.js, wo die Ereignisschleife die Auswirkungen katastrophalen Backtrackings noch verstärkt.

Um ReDoS-Schwachstellen zu verhindern, sollten Sie Ihre regulären Ausdrücke im Blick behalten und Ihre Abhängigkeiten auf ReDoS-Schwachstellen prüfen.

Es gab mehrere Versuche, Tools zur automatischen Erkennung von Ausdrücken zu entwickeln, die anfällig für ReDoS-Angriffe sind (am bekanntesten ist safe-regex). Doch selbst bei begrenzten Tests stellten wir zahlreiche falsch positive Ergebnisse sowie mehrere Ausdrücke fest, die fälschlicherweise als sicher eingestuft wurden.

Ihre Abhängigkeiten zu testen, ist dagegen recht eindeutig – das kann Snyk für Sie übernehmen.

In jedem Fall lohnt es sich, etwas Zeit für Experimente aufzuwenden. Mit einem Tool wie dem Debugger von RegEx101 können Sie hervorragend verschiedene Ausdrücke ausprobieren und besser nachvollziehen, welche Schritte der Parser für reguläre Ausdrücke beim Abgleich Ihres Ausdrucks ausführt.

Wer weiß – mit genügend Zeit und Experimentierfreude sind vielleicht eines Tages Sie es, die mit Ihrem umfassenden Wissen über reguläre Ausdrücke zur Rettung eilen.