Wie man katastrophales Backtracking in Regex vermeidet?

Katastrophales Backtracking von regulären Ausdrücken bezieht sich darauf, dass der reguläre Ausdruck beim Matching zu viel zurückverfolgt, was zu 100% CPU-Auslastung führt und normale Dienste blockiert.

Hintergrund

Ich habe einen Artikel gelesen, der den Entdeckungs- und Lösungsprozess eines regulären Backtrackings beschreibt, das zu 100% CPU-Auslastung führt. Der ursprüngliche Artikel ist ziemlich lang, und ich bin bei der Entwicklung von OpenResty bereits zweimal auf ähnliche Probleme gestoßen.

Hier ist eine kurze Zusammenfassung, damit Sie sich nicht mit dem Hintergrund beschäftigen müssen.

1. Die Regularisierungs-Engines der meisten Entwicklungssprachen werden mit backtracking-basiertem NFA implementiert (und nicht basierend auf Thompsons NFA).
2. Katastrophales Backtracking mit 100% CPU, wenn es zu viele Rückverfolgungen gibt.
3. Es ist notwendig, den Dump mit gdb oder systemtap zu analysieren, um die Online-Umgebung zu lokalisieren.
4. Solche Probleme sind schwer zu erkennen, bevor der Code live geht, und erfordern eine fallweise Überprüfung der regulären Ausdrücke.

Aus Entwicklersicht ist die Behebung der problematischen regulären Ausdrücke das Ende der Geschichte. Höchstens fügt man einen Sicherheitsmechanismus hinzu, um die Anzahl der Rückverfolgungen zu begrenzen, wie dies in OpenResty der Fall ist.

lua_regex_match_limit 100000;

Auf diese Weise wird selbst bei katastrophalem Backtracking die CPU-Auslastung begrenzt und läuft nicht auf 100%.

Nun, sieht das nicht schon perfekt aus? Gehen wir über die Entwicklungsebene hinaus und betrachten dies aus einer anderen Dimension.

Angreifer

Man braucht nur eine Maschine, sendet eine Anfrage und kann den Server auf der anderen Seite lahmlegen. Das ist einfach der Traum eines Hackers von einer Nuklearwaffe. Im Vergleich dazu ist DDoS schwach, der Aufwand ist groß und kostspielig.

Dieser Angriff hat auch einen eigenen Namen: ReDoS (RegEx Denial of Service).

Da reguläre Ausdrücke so weit verbreitet sind und in fast jedem Teil des Backend-Services existieren, gibt es die Möglichkeit, eine der Schwachstellen auszunutzen.

Stellen Sie sich ein Szenario vor, in dem ein Hacker eine ReDoS-Schwachstelle in der WAF entdeckt und eine Anfrage sendet, um die WAF lahmzulegen; Sie können das Problem in kurzer Zeit nicht lokalisieren, nicht einmal erkennen, dass es sich um einen Angriff handelt; Sie entscheiden sich, die WAF neu zu starten oder vorübergehend zu deaktivieren, um Ihr Geschäft am Laufen zu halten; während die WAF außer Betrieb ist, nutzt der Hacker SQL-Injection, um Ihre Datenbank zu stehlen. Sie hingegen sind möglicherweise immer noch völlig ahnungslos.

Da Open-Source-Software und Cloud-Dienste weit verbreitet sind, reicht es nicht aus, sicherzustellen, dass die von Ihnen geschriebenen regulären Ausdrücke frei von Schwachstellen sind. Das ist ein anderes Thema, wir beginnen hier nur mit der Diskussion von regulären Ausdrücken, die unter unserer eigenen Kontrolle stehen.

Wie kann man solche regulären Ausdrücke entdecken?

Der erste Schritt zur Lösung von Problemen ist, sie zu finden und zu versuchen, alle zu finden, auch bekannt als die Fähigkeit, sie sicher zu finden.

Es ist nicht zuverlässig, problematische Regeln durch manuelle Code-Überprüfung zu finden. Die meisten Entwickler sind sich der Sicherheit nicht bewusst, und selbst wenn sie danach suchen würden, ist es unwahrscheinlich, dass sie das Problem in einem komplexen regulären Ausdruck finden könnten.

Hier kommen Automatisierungstools ins Spiel.

Wir haben die folgenden zwei automatisierten Methoden, um dies zu lösen.

• Statische Tests

Solche Tools können den Code nach regulären Ausdrücken scannen und gemäß einem bestimmten Algorithmus die regulären Ausdrücke mit katastrophalem Backtracking identifizieren.

Zum Beispiel RXXR2, das auf einem Algorithmus in einem Papier basiert, das reguläre Ausdrücke in ε-NFA umwandelt und dann danach sucht, aber die erweiterte Syntax von regulären Ausdrücken nicht unterstützt, sodass es zu Fehlalarmen kommt.

• Dynamisches Fuzzing

Der Fuzz-Test ist eine allgemeine Software-Testmethode, die Softwareabstürze, Speicherlecks und andere Probleme durch die Eingabe großer Mengen zufälliger Daten über lange Zeiträume erkennt.

Ebenso können wir diesen Ansatz in regulären Tests verwenden. Wir können Testdaten basierend auf vorhandenen regulären Ausdrücken generieren oder sie völlig zufällig erzeugen.

SlowFuzz ist eines der Open-Source-Tools, ebenfalls basierend auf einem Algorithmus aus einem Papier, das am Ende dieses Artikels aufgeführt wird. Es ist ein allgemeines Tool und verarbeitet die Struktur des regulären Ausdrucks nicht, sodass es zu Fehlalarmen kommt.

SDLFuzzer ist ein spezialisiertes ReDoS-Erkennungstool, das vor einigen Jahren von Microsoft entwickelt wurde, aber nicht mehr gepflegt wird.

Es gibt nicht viele Tools in diesem Bereich zur Auswahl, und es wird nicht viel Aufmerksamkeit geschenkt. Allerdings war ich begeistert, während meiner Informationssuche ein Papier über ReDoS von mehreren Lehrern und Doktoranden der Nanjing University zu finden, das das Tool ReScue zusammen mit dem Papier veröffentlicht hat: https://2bdenny.github.io/ReScue/. Dieses Tool hat ReDoS-Schwachstellen in mehreren Open-Source-Projekten identifiziert.

Hier sind die Ergebnisse der Vergleichstests im Papier.

Kann es ein für alle Mal gelöst werden?

Selbst wenn wir solche Tools verwenden, wird es unweigerlich Fehlalarme und übersehene Alarme geben. Gibt es also eine einmalige Lösung für ReDoS?

Dann müssen wir zurück zur Wurzel des Problems gehen, um die Antwort zu finden: die reguläre Engine verwendet Backtracking für das Matching.

Wäre es nicht in Ordnung, wenn wir diesen Ansatz aufgeben? Ja, es gibt bereits mehrere andere Implementierungen von regulären Engines, die das Problem ein für alle Mal lösen können. Sie verzichten auf Backtracking und verwenden den NFA/DFA-Automaten-Ansatz zur Implementierung, der Vorteil ist, dass er für Streaming-Matching geeignet ist und auch sicherer ist, der Nachteil ist, dass er viele erweiterte Syntaxen von regulären Ausdrücken nicht unterstützt, wie Rückverweise, die jedoch im Allgemeinen nicht verwendet werden.

• Google RE2

Googles RE2 ist eines der vollständigeren Open-Source-Projekte. Es unterstützt die meisten Syntaxen von PCRE, und es gibt Bibliotheksimplementierungen für Go, Python, Perl, Node.js und andere Entwicklungssprachen, der Start- und Ersetzungskosten sind sehr niedrig.

Nehmen wir Perl als Beispiel und sehen, ob RE2 katastrophale Backtracking-Probleme vermeiden kann.

Schauen wir uns diese Vergleichstabelle der Ergebnisse an.

Der Code ist wie folgt, Sie können es selbst ausprobieren, wenn Sie interessiert sind.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

Es dauert 40,8 Sekunden, um diesen regulären Ausdruck auszuführen, während dieser Zeit ist die CPU bei 99%.

Mit RE2 ist der Kontrast sehr deutlich.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total

• Intel Hyperscan

Intel Hyperscan ist ebenfalls eine reguläre Engine ähnlich wie RE2, und es gibt Bibliotheken für Perl, Python und andere Sprachen, sodass der Einstieg nicht zu schwierig ist.

Nur nach Intels Praxis ist es stärker an Plattformen gebunden und kann nur auf x86 laufen.

Wenn es einen einzigartigen Vorteil gibt, dann vielleicht die Fähigkeit, besser mit Intels Befehlssatz und Hardware zusammenzuarbeiten, mit Leistungsverbesserungen, wie z.B. in Kombination mit seinem eigenen DPDK.

Snort, ein Open-Source-Netzwerk-Intrusion-Detection-Tool, verwendet ebenfalls Hyperscan, um die vorherige reguläre Engine zu ersetzen, sodass Studenten, die mit Snort vertraut sind, es ausprobieren können.

Erweiterungen

Hier sind einige Papiere über reguläre Ausdrücke, die als Erweiterung gelesen werden können, wenn Sie interessiert sind.

1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html