Die bösen regulären Ausdrücke

In diesem Blog-Beitrag gehe ich auf reguläre Ausdrücke (regex) und ihre Schattenseiten ein. Insbesondere gehe ich darauf ein, wie ein Regex einen Denial-of-Service-Angriff auslösen kann.

Was ist ein “Regular expression Denial-of-Service (ReDoS)” Angriff?

Ein ReDoS-Angriff ist einer von vielen verschiedenen Denial-of-Service-Angriffen. Das Hauptziel dieser Angriffe ist es, einen Dienst für den Endnutzer nicht mehr verfügbar zu machen.

Bei einem Denial-of-Service-Angriff versucht ein Angreifer mit verschiedenen Techniken, ein bestimmtes System oder Teile der Infrastruktur lahm zu legen. Beispielsweise könnte eine große Menge von Anfragen an einen Server gesendet werden. Dieser müsste alle gleichzeitig bearbeiten und beantworten, was zu einer unverhältnismäßig langen Antwortzeit führen würde. Es ist auch durchaus möglich, dass es durch die Beanspruchung vieler Ressourcen zu einem Systemausfall kommt.

ReDoS-Angriffe folgen dem gleichen Schema. Der Angreifer nutzt die Funktionsweise verschiedener Regex-Engines aus. Es wird eine Eingabe konstruiert, die in der Engine einen deutlich höheren Prüfaufwand erzeugt, als dies normalerweise der Fall wäre. Dadurch kann ein Systemabsturz oder ein Systemausfall provoziert werden.

Wie funktionieren reguläre Ausdrücke?

Bevor wir fortfahren, sollten wir uns ansehen, wie das Matching von regulären Ausdrücken unter der Haube funktioniert - dies wird uns helfen zu verstehen, warum bestimmte reguläre Ausdrücke besonders anfällig für Angriffe sind.

Der Abgleich von Mustern regulärer Ausdrücke kann durch die Konstruktion einer endlichen Zustandsmaschine (engl.: finite state machine, abgekürzt FSM) erfolgen. Diese kann man sich als eine abstrakte Maschine vorstellen. Mit Hilfe von Operatoren wird eine Reihe von Überprüfungen durchgeführt und entsprechend eine Aussage erzeugt.

Eine FSM kann sich zu jedem Zeitpunkt in genau einem Zustand befinden. Die Menge der Zustände ist endlich. Eine Transition findet statt, wenn ein endlicher Automat von einem Zustand in einen anderen übergeht. Ein Beispiel für einen endlichen Automaten ist ein Kaffeeautomat, der je nach Auswahl des Benutzers eine bestimmte Kaffeesorte ausschenkt.

Wie bereits erwähnt, kann der Vergleich regulärer Ausdrücke durch die Konstruktion einer FSM erfolgen. Reguläre Ausdrücke können auch leicht von einem endlichen Automaten in einen nichtdeterministischen Automaten umgewandelt werden, insbesondere für Ausdrücke, bei denen es für jede empfangene Eingabe mehrere mögliche nächste Zustände gibt. In solchen Fällen kann die Engine für reguläre Ausdrücke nach der Umwandlung mehrere Algorithmen verwenden, um die nächsten Zustände zu bestimmen. Wir werden uns jedoch auf die problematischsten Algorithmen konzentrieren:

• Die Engine probiert alle möglichen Pfade aus, bis eine Übereinstimmung gefunden wird oder alle Pfade ausprobiert wurden und fehlgeschlagen sind ("backtracking"). Dies ist problematisch, da für eine Eingabe der Länge n exponentiell viele Pfade durchlaufen werden, so dass sich im ungünstigsten Fall eine Laufzeit von O(n)=2^n ergibt.
• Die Engine versucht wiederum, von der nichtdeterministischen Automatisierung in die deterministische Automatisierung zu wechseln. Dies ist problematisch, da die Konvertierung je nach Ausführungspfad exponentiell lange dauern kann.

Ein Regex Denial of Service tritt also auf, wenn einer dieser beiden Algorithmen auf einen bestimmten regulären Ausdruck angewendet wird. Ein böswilliger Benutzer kann dies ausnutzen, um eine dieser beiden Bedingungen auszulösen, was zu der schlimmsten Laufzeitkomplexität der Engine für reguläre Ausdrücke führt.

Welche Arten von regulären Ausdrücken sind anfällig für DoS-Angriffe?

Betrachten wir ein Beispiel für einen regulären Ausdruck, der für einen DoS-Angriff anfällig ist. Für die Laufzeitanalyse eines Befehls verwenden wir das CLI-Tool gnomon.

Starte die Konsole deiner Wahl und installiere es:

	
		npm install -g gnomon
	

Angenommen, wir haben ein Muster, /^(\w+\s?)*$/, das eine Gruppe von Wörtern mit einem optionalen Leerzeichen nach jedem Wort enthält. Die Quantoren ^ und $ beziehen sich auf die Wörter am Anfang und am Ende der Zeile.

Versuchen wir es nun mit einer Gruppe von Wörtern ohne Sonderzeichen:

	
		node -p "/^(\w+\s?)*$/.test('Nur valide Character')" | gnomon
	

Wir sehen, dass die Wörter übereinstimmen und dass es 0,0058 Sekunden gedauert hat, diesen regulären Ausdruck auf dem Terminal auszuführen.

Versuchen wir nun, einen Satz mit einem Sonderzeichen am Ende des letzten Wortes zu bilden:

	
		node -p "/^(\w+\s?)*$/.test('Invalide Character!')" | gnomon
	

Wie erwartet wurde false zurückgegeben und die Ausführung des regulären Ausdrucks dauerte etwa 0,0061 Sekunden.

Perfekt, alles funktioniert. Das Problem ist jedoch, dass es sehr lange dauern kann, bis die Regex-Engine den regulären Ausdruck für einen viel längeren Satz mit Sonderzeichen ausführt.

Sehen wir uns das mal in Aktion an. Führe folgendes in einem Terminal aus:

	
		node -p "/^(\w+\s?)*$/.test('Ein langer Satz mit invaliden Zeichen, dessen Abgleich so viel Zeit in Anspruch nimmt, dass die CPU-Auslastung moeglicherweise drastisch ansteigt!!!')" | gnomon
	

Von diesem Befehl ist kein Ergebnis zu erwarten... Wenn wir unseren Task-Manager öffnen, sehen wir, dass der betreffende Prozess einen sehr großen Teil der CPU für die Ausführung dieses regulären Ausdrucks verwendet. Tatsächlich sollten wir einen starken Anstieg der gesamten aktuellen CPU-Auslastung feststellen.

Wie man sieht, kann ein Angreifer ein scheinbar einfaches Regex-Muster ausnutzen, um unser System dazu zu bringen, mehr Ressourcen zu verbrauchen als erwartet. Längere Eingaben können also dazu führen, dass unser System hängt oder abstürzt.

Schauen wir uns genauer an, warum das so ist:

• Die Hauptursache für dieses Problem ist eine in Regex-Engines verfügbare Funktion namens Backtracking. Die Engine geht zuerst die Eingabe durch und versucht, den Inhalt der Klammern \w+\s? zu überprüfen.
• Da der Quantor + gierig ist, versucht er, so viele gültige Wörter wie möglich zu finden, und gibt daher zurück: einen langen Satz von ungültigen Zeichen, deren Überprüfung so viel Zeit in Anspruch nimmt, dass die CPU-Belastung drastisch ansteigen kann.
• Der Sternquantor (\w+\s?)* kann dann angewendet werden, aber es gibt keine gültigen Wörter mehr in der Eingabe, so dass er nichts zurückgibt.
• Aufgrund des $-Quantors in unserem Muster versucht die Regex-Engine, das Ende der Eingabe zu finden. Dort haben wir ein ungültiges Wort, ansteigt!!!, also gibt es keine Übereinstimmung.
• Die Maschine geht einen Schritt zurück zur vorherigen Position und versucht einen anderen Weg in der Hoffnung, eine Übereinstimmung zu finden. Der Quantor + verringert also die Anzahl der Wiederholungen, geht ein Wort zurück und versucht, den Rest der Eingabe abzugleichen - in diesem Fall Ein langen Satz mit ungültigen Zeichen, dessen Abgleich so viel Zeit in Anspruch nimmt, dass die CPU-Belastung drastisch ansteigen kann.
• Die Suchmaschine setzt die Suche an der nächsten Position fort: Der Sternquantor kann erneut angewendet werden und findet das Wort drastisch. Erinnert ihr euch? Wir haben den $-Quantor; die Maschine wendet ihn an, aber er scheitert erneut an ansteigt!!!

Die Regex-Engine geht zurück und verringert die Anzahl der Wiederholungen, bis alle möglichen Pfade untersucht wurden. Wir erwarten, dass die Suche nach regulären Ausdrücken eine Laufzeit von O(n) benötigt, wobei n die Länge der Eingabezeichenkette ist.

In den meisten Fällen mag das zutreffen. In einigen Fällen jedoch - wie in dem gerade betrachteten Fall - kann es vorkommen, dass die Regex-Engine eine exponentiell steigende Anzahl von Pfaden durch die Eingabezeichenfolge nehmen muss, um eine Übereinstimmung zu finden.

Bei einer Eingabe von etwa 125 Zeichen ergibt sich eine Situation, in der die Maschine eine exponentielle Anzahl von Pfaden nimmt. Etwa 2^125 verschiedene Pfade, was etwa 4,2535296e+37 verschiedene Kombinationen ergibt, weil ein ungültiges Wort an einer bestimmten Stelle vorkommt. Dies führt in der Regel zu einem sogenannten katastrophalen Backtracking. Die Ausführung solcher regulärer Ausdrücke ist sehr zeit- und ressourcenaufwändig.

Abschließend werden wir uns verschiedene Möglichkeiten ansehen, wie wir unsere Modelle vor solchen Problemen schützen können.

So könnt ihr euch gegen einen Angriff schützen

1. Reduziere die Anzahl der Kombinationen

Ein Ansatz besteht darin, die Anzahl der von den Regex-Engines durchgeführten Kombinationen zu verringern. Es gibt mehrere Möglichkeiten, dies zu tun:

• Vermeide verschachtelte Quantoren – zum Beispiel (a+)*
• Vermeide ORs mit sich überschneidenden Klauseln - etwa (b|b)*

Abhängig von der Engine können einige reguläre Ausdrücke, die mit verschachtelten Quantoren und überlappenden Klauseln geschrieben wurden, schnell ausgeführt werden, aber es gibt keine Garantie dafür. Vorsicht ist besser als Nachsicht.

2. Kontrolliere das Backtracking

Ein weiterer Ansatz ist die Kontrolle des Backtracking. Obwohl das Backtracking die Konstruktion komplexer und leistungsfähiger regulärer Ausdrücke ermöglicht, kann der letztendliche Nutzen unbedeutend sein, insbesondere im Vergleich zur schlechten Leistung in Fällen wie den oben untersuchten.

Glücklicherweise können wir bestimmte Funktionen verwenden, um das Backtracking entweder einzuschränken oder zu unterdrücken und trotzdem leistungsfähige reguläre Ausdrücke zu erstellen. Sehen wir uns zwei davon an: atomare Gruppen und Lookahead.

a. Atomare Gruppen

Eine atomare Gruppe verwendet die ?>-Syntax, um das Backtracking im Ausdruck zu unterdrücken. Sobald eine Übereinstimmung gefunden wurde, ist es nicht mehr möglich, zu anderen Teilen zurückzugehen, selbst wenn dies bedeutet, dass die Möglichkeit einer erfolgreichen Übereinstimmung besteht.

Diese Methode zur Unterdrückung der Rückverfolgbarkeit trägt zur Verbesserung der Leistung bei der Verwendung von verschachtelten Quantoren bei. Leider ist diese Funktion nicht in allen Regex-Engines implementiert und insbesondere in JavaScript/Node.js nicht verfügbar.

Schauen wir uns eine andere Funktion an, mit der wir etwas Ähnliches erreichen können und die in JavaScript/Node.js verfügbar ist.

b. Lookahead

In dem Beispiel, das wir zuvor gesehen haben, möchten wir, dass unser Quantor nicht zurückverfolgt wird, da das Backtracking in den meisten Fällen zu schwerwiegenden Problemen führen kann, wie wir zuvor gesehen haben. Um dies zu erzwingen, können wir eine Funktion namens Lookahead verwenden.

Bei der Verwendung von Lookahead-Assertions verwenden wir die ?=-Syntax - beispielsweise sagt ein Muster A(?=B) einfach: “Suche nach A, aber gehe nur weiter, wenn B folgt”. Das ist wichtig, denn so können wir feststellen, ob der Ausdruck mit den nächsten Zeichen übereinstimmt, ohne zurück oder weiter gehen zu müssen.

In diesem Fall wollen wir so viele Wörter wie möglich finden, ohne zurückgehen zu müssen. Wir können das Muster so umschreiben, dass es Wörter von \w+ bis (?=(\w+))\1 enthält. Dies mag auf den ersten Blick etwas unintuitiv erscheinen.

In unserem umgeschriebenen Muster (?=(\w+))\1 weisen wir die Suchmaschine an, nach dem längsten Wort an der aktuellen Position zu suchen. Das Muster in den inneren Klammern, (\w+), weist die Suchmaschine an, sich den Inhalt zu merken, und wir können \1 verwenden, um später darauf zu verweisen.

Damit ist unser Problem gelöst, denn wir können die Lookahead-Funktion verwenden, um das Wort w+ als Ganzes zu finden und es mit dem Muster \1 zu referenzieren. Im Wesentlichen können wir einen possessiven +-Quantor implementieren, der auf das ganze Wort und nicht auf Teile davon passen muss.

In unserem ersten Beispiel deckt das angegebene Muster die Wörter ab, aber wenn es auf ein ungültiges Wort stößt, zwingt der +-Quantor es, so lange zurückzugehen, bis es erfolgreich ist oder nicht. In unserem umgeschriebenen Beispiel haben wir Lookahead verwendet, um ein gültiges Wort zu finden, das als Ganzes verglichen und mit \1 in das Muster aufgenommen wurde.

Lassen wir dieses neue Muster zusammen mit unseren vorherigen Quantoren laufen, um zu sehen, ob wir das gleiche Problem haben:

	
		node -p "/^((?=(\w+))\1\s?)*$/.test('Ein langer Satz mit invaliden Zeichen, der aber nicht zu einem drastischen Anstieg der CPU-Auslastung fuehrt!!!')" | gnomon
	

Voila! Wir sehen, dass der reguläre Ausdruck ausgeführt wird und wir sofort eine Ausgabe erhalten; es dauerte etwa 0,0052 Sekunden, um ein Ergebnis zu erhalten.

Fazit

In diesem Blog-Beitrag haben wir gelernt, wie wir verhindern können, dass reguläre Ausdrücke für Denial-of-Service-Angriffe verwendet werden. Wir haben uns eingehend mit der Funktionsweise von regulären Ausdrücken beschäftigt, um zu verstehen, warum und wie dieses Problem auftritt. Anschließend haben wir uns ein Beispiel für ein reguläres Ausdrucksmuster mit einer solchen Schwachstelle angesehen und gezeigt, wie die Lücken, die Angreifer ausnutzen können, geschlossen werden können.