💻 computer science

PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

Dieses Paper stellt PUFFERDOS vor, ein neuartiges Tool, das praktische und effektive ReDoS-Angriffsstrings generiert, indem es Eingaben basierend auf drei formal verifizierten verwundbaren Mustern synthetisiert und diese durch kompositorische konkolische Ausführung verfeinert, um die Praxistauglichkeit innerhalb realistischer Längenbudgets sicherzustellen.

Ursprüngliche Autoren: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Veröffentlicht 2026-06-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben einen sehr intelligenten, aber leicht zwanghaften Sicherheitswachmann an der Tür eines Gebäudes. Seine Aufgabe ist es zu prüfen, ob Ihr Ausweis (der Input) einem bestimmten Muster (dem regulären Ausdruck oder „Regex“) entspricht. Normalerweise ist das schnell und einfach.

Aber es gibt einen Trick. Wenn Sie dem Wachmann einen sehr spezifischen, verwirrenden Ausweis geben, bleibt sein Gehirn in einer Endlosschleife stecken. Er beginnt, jeden einzelnen möglichen Weg zu prüfen, auf dem Ihr Ausweis dem Muster entsprechen könnte, immer und immer wieder, bis er seine Energie aufgebraucht hat und ohnmächtig wird. Das nennt man einen ReDoS-Angriff (Regular Expression Denial of Service). Es ist, als würde man einen Taschenrechner dazu bringen, unendlich lange mathematische Aufgaben zu lösen, sodass er einfriert.

Lange Zeit haben Sicherheitsforscher versucht, diese Fallen zu finden und spezielle „Test-Ausweise“ zu erstellen, um zu beweisen, dass der Wachmann eine Schwachstelle hat. Die alten Methoden hatten jedoch zwei große Probleme:

Die Ausweise waren zu lang: Sie erforderten Eingaben, die so riesig waren (wie ein ganzes Buch voller Text), dass keine echte Website sie jemals akzeptieren würde.
Sie passten nicht zum Gebäude: Sie testeten den Wachmann isoliert und ignorierten dabei, dass in einem echten Gebäude andere Wachmänner (Filter) vorhanden sind, die Ihren Ausweis stoppen könnten, noch bevor er die Haupttür erreicht.

Hier kommt PUFFERDOS ins Spiel. Betrachten Sie PUFFERDOS als einen Meister-Schlüsseldienst, der nicht nur das Schloss knackt, sondern genau herausfindet, wie man durch das gesamte Gebäude bis zum Schloss gelangt, indem man den kürzesten und effizientesten Schlüssel verwendet.

So funktioniert PUFFERDOS, aufgeschlüsselt in einfache Schritte:

1. Die „Stopppunkt“-Strategie (Den Wachmann härter arbeiten lassen)

Die Forscher erkannten, dass man nicht nur irgendein verwirrendes Muster braucht, um den Wachmann zum Einfrieren zu bringen; man braucht ein Muster, bei dem der Wachmann extrem kleine, ineffiziente Schritte machen muss.

Die Analogie: Stellen Sie sich vor, der Wachmann geht einen Flur entlang. Wenn man ihn dazu bringt, bei jedem einzelnen Zentimeter anzuhalten, um den Boden zu prüfen, wird er schnell müde. Wenn er nur alle 3 Meter anhält, wird er langsamer müde.
Die Lösung: PUFFERDOS erstellt „Schlüssel“ (Angriff-Strings), die den Wachmann zwingen, bei jedem winzigen Zentimeter anzuhalten. Dies geschieht durch die sorgfältige Auswahl spezifischer Zeichen und deren Anordnung, sodass der Wachmann so oft wie möglich zurückversetzen muss (backtracking/zurückgehen und erneut prüfen). Dadurch ist der Angriff tausendfach schneller als bisherige Methoden, da er denselben „Einfrier-Effekt“ mit einem viel kürzeren Schlüssel erreicht.

2. Die drei „Fallen“-Muster

Das Team entdeckte, dass die meisten defekten Schlösser drei spezifische Formen haben. PUFFERDOS hat für jede ein spezielles Rezept:

Die Ein-Schleifen-Falle (One-Loop Trap): Ein einzelnes Muster, das auf mehrere verwirrende Arten gelesen werden kann. PUFFERDOS wählt das kürzeste, verwirrendste Zeichen, das sich wiederholt.
Die Zwei-Schleifen-Falle (Two-Loop Trap): Zwei Muster nebeneinander, die beide dasselbe Zeichen lesen können. PUFFERDOS nutzt ein Zeichen, das beide Muster lesen können, was dazu führt, dass sie darüber streiten, wer dieses Zeichen verarbeiten darf.
Die Multi-Schleifen-Falle (Multi-Loop Trap): Eine lange Kette von Mustern. PUFFERDOS baut einen Schlüssel, der den Wachmann zwingt, jedes Glied in der Kette einzeln zu prüfen.

3. Der „Real-World“-Durchgang (Concolic Execution)

Dies ist der wichtigste Teil. Alte Tools testeten das Schloss nur im Vakuum. PUFFERDOS simuliert das gesamte Gebäude.

Die Analogie: Stellen Sie sich vor, Sie haben einen Schlüssel, der eine Tür öffnet, aber die Tür befindet sich hinter einem Sicherheitscheck, einem Empfang und einem Labyrinth. Alte Tools zeigten Ihnen nur, dass der Schlüssel für die Tür funktioniert. PUFFERDOS geht mit Ihnen durch das Labyrinth, prüft, ob der Empfang Sie passieren lässt, und stellt sicher, dass Sie die Tür tatsächlich erreichen.
Die Methode: Es nutzt eine Technik namens „kompositionale koncolische Ausführung“ (compositional concolic execution). Denken Sie an dies als eine Zusammenfassung der Karte. Anstatt jeden einzelnen Schritt des Gebäudes jedes Mal neu zu gehen, erstellt PUFFERDOS für jeden Raum (Funktion) einen „Spickzettel“. Es fragt: „Wenn ich diesem Raum einen verwirrenden Schlüssel gebe, leitet er ihn an den nächsten Raum weiter oder wirft er ihn weg?“
Durch die Verwendung dieser Spickzettel kann PUFFERDOS schnell herausfinden, ob ein kurzer, effizienter Schlüssel tatsächlich das verwundbare Schloss in einem echten Programm erreicht oder ob er durch einen Filter früher im Prozess blockiert wird.

Die Ergebnisse

Das Team hat PUFFERDOS an tausenden realen Programmen und bekannten Sicherheitslücken (CVEs) getestet.

Geschwindigkeit: Es generierte Angriff-Strings, die 97- bis 3.800-mal effizienter waren als das bisher beste Tool. Es konnte ein System mit einem winzigen String einfrieren, anstatt mit einem massiven.
Erfolgsquote: Es konnte 96,8 % der bekannten Sicherheitslücken reproduzieren (im Vergleich zu 77,4 % beim alten Tool).
Neue Entdeckungen: Als sie PUFFERDOS an 12 populären, realen Softwareprojekten testeten, fanden sie 59 neue, bisher unbekannte Sicherheitslücken, die die alten Tools übersehen hatten, weil diese keine realistischen, kurzen Angriffe generieren konnten, um zu beweisen, dass die Schwachstelle tatsächlich existiert.

Kurz gesagt: PUFFERDOS ist eine intelligentere, praktischere Methode, um zu finden und zu beweisen, dass ein Computersystem durch ein verwirrendes Muster eingefroren werden kann. Es findet nicht nur das Schloss; es findet den kürzesten, realistischsten Schlüssel, um es zu blockieren, und beweist damit, dass die Gefahr real ist und behoben werden muss.

Technisches Resümee: PUFFERDOS

Problemstellung

Regular Expression Denial of Service (ReDoS)-Angriffe nutzen das pathologische Worst-Case-Ausführungsverhalten von Backtracking-Regex-Engines aus, indem sie eine superlineare oder exponentielle Anzahl von Matching-Pfaden erzwingen. Dies verbraucht übermäßige CPU-Ressourcen, was zu Dienstverschlechterung oder Nichtverfügbarkeit führt. Obwohl zahlreiche Detektionswerkzeuge existieren, um vulnerable Regex zu identifizieren und Proof-of-Concept-Angriffsstrings zu generieren, leiden aktuelle Ansätze unter zwei kritischen Einschränkungen, die eine praktische Ausnutzung erschweren:

Unpraktische Eingabelängen: Bestehende Werkzeuge generieren oft Angriffsstrings, die unrealistisch lang sind (z. B. Hunderttausende von Zeichen erfordern), um eine signifikante Verzögerung auszulösen. In realen Implementierungen begrenzen Eingabe-Constraints (wie etwa HTTP-Header-Limits) diese Strings oft, bevor sie die vulnerable Regex erreichen können, wodurch der Angriff unwirksam wird.
Fehlende Programm-Ebene-Validierung: Viele generierte Strings werden nur isoliert gegen die Regex validiert. Sie berücksichtigen keine Data-Flow-Constraints, Filterlogiken oder Eingabe-Trunkierungen innerhalb des Host-Programms. Infolgedessen können diese Strings in einem realen Ausführungskontext oft die vulnerable Regex nicht erreichen, was dazu führt, dass Entwickler gemeldete Schwachstellen als geringfügig oder nicht ausnutzbar abtun.

Methodik

Die Autoren schlagen PUFFERDOS vor, ein hybrides Framework, das darauf ausgelegt ist, Angriffsstrings zu synthetisieren, die sowohl effizient (Maximierung der Matching-Kosten innerhalb realistischer Längenbudgets) als auch effektiv (validiert, um die vulnerable Regex im tatsächlichen Programm zu erreichen) sind. Die Methodik besteht aus drei Kernkomponenten:

1. Formale Analyse und Muster-Taxonomie

Die Autoren formalisieren zunächst die Beziehung zwischen der Struktur eines Angriffsstrings und den Matching-Kosten. Durch formale Beweise (Lemmata 3.2–3.4 und Theorem 3.5) stellen sie fest, dass die Matching-Kosten steigen, wenn:

Repetitions-Einheiten so kurz wie möglich sind.
Repetitions-Einheiten aus dem Schnittpunkt der Alphabete benachbarter Loop-Expressions (LEs) ausgewählt werden, was es mehreren LEs ermöglicht, denselben Substring zu konsumieren.
Stopp-Punkte (Indizes, an denen LEs enden) voneinander getrennt statt ineinander verschachtelt sind, was den Engine dazu zwingt, längere Eingments während des Backtrackings erneut zu verarbeiten.

Basierend darauf definieren sie drei vulnerable Muster, um die String-Generierung zu leiten:

Exponential One-Loop (EOL): Eine einzelne LE mit entfaltenden Sub-Regexes, die überlappende Alphabete aufweisen.
Loop-Intersect-Loop (LIL): Zwei benachbarte LEs, die durch ein Nicht-Loop-Segment getrennt sind, welches von beiden LEs gematcht werden kann.
Polynomial Multi-Loop (PML): Benachbarte LEs mit disjunkten Alphabeten oder Separatoren, die nicht von beiden konsumiert werden können.

2. Strukturgesteuerte Angriffsstring-Generierung

PUFFERDOS parst vulnerable Regex in einen Abstract Syntax Tree (rAST), um das spezifische vulnerable Muster (EOL, LIL oder PML) zu identifizieren. Es synthetisiert anschließend Kandidaten-Angriffsstrings ( $s_a = x \cdot y^q \cdot z$ ) unter Verwendung muster-spezifischer Regeln:

Infix-Generierung: Wählt die kürzeste Repetitions-Einheit ( $y$ ) aus dem Alphabet-Schnitt der relevanten LEs. Für Muster mit mehreren LEs werden unabhängig wiederholte Einheiten konkateniert, um sicherzustellen, dass Stopp-Punkte getrennt sind, was die Backtracking-Schritte maximiert.
Präfix-/Suffix-Konstruktion: Leitet das Präfix ( $x$ ) aus dem Nicht-Loop-Präfix der Regex und das Suffix ( $z$ ) aus dem Nicht-Loop-Suffix ab, um sicherzustellen, dass der finale String von der Regex abgelehnt wird, um ein exhaustives Backtracking auszulösen.

3. ReDoS-spezifische Kompositionale Koncolic-Verfeinerung

Um sicherzustellen, dass der generierte String in einem realen Programm die vulnerable Regex erreicht, nutzt PUFFERDOS eine kompositionale koncolische Ausführungsstrategie:

Pfad-Extraktion: Konstruiert einen Call-Graph, um durchführbare Pfade von den Programmpunkten bis zur vulnerablen Regex zu identifizieren.
Funktions-Summarisierung: Führt koncolische Unit-Tests an Funktionen entlang des Pfades durch, um ReDoS-spezifische Funktions-Summaries zu generieren. Im Gegensatz zu traditionellen Summaries sind diese so beschnitten, dass sie nur Verhaltensweisen beibehalten, die für die Propagation des Angriffsstrings relevant sind (z. B. Identitäts-Transformationen oder konstante Rückgaben), wobei unbezogene Regex-Reasoning verworfen wird, um die Pfadexplosion zu vermeiden.
System-Ebene-Verfeinerung: Nutzt die Summaries, um die systemweite koncolische Ausführung zu leiten, wobei interprozedurale Constraints aufgelöst werden, um den Angriffsstring so zu verfeinern, dass er Filter umgeht und die Ziel-Regex erreicht, ohne das Budget für realistische Eingabelängen zu überschreiten.

Zentrale Beiträge

Formaler Beweis der Effizienz: Das Paper beweist formal, dass die Auswahl spezifischer Zeichen und deren Anordnung zur Trennung von Stopp-Punkten in benachbarten LEs die Regex-Matching-Kosten signifikant verstärkt. Dies führt zur Ableitung von drei vulnerablen Regex-Mustern und nachweislich effizienten Generierungsregeln.
PUFFERDOS-Framework: Die Entwicklung eines hybriden Generators, der formale Generierungsregeln mit ReDoS-spezifischer kompositionaler koncolischer Verfeinerung integriert. Dieser Ansatz schließt die Lücke zwischen theoretischer Detektion und praktischer Ausnutzung, indem er sicherstellt, dass Strings kurz genug für reale Constraints sind und valide innerhalb des Programms-Data-Flows bleiben.
Umfassende Evaluierung: Das Tool wird an einem groß angelegten Korpus von 17.962 vulnerablen Regex, 31 bekannten CVEs und 12 populären Open-Source-Projekten evaluiert.

Ergebnisse

Die Evaluierung zeigt signifikante Verbesserungen gegenüber dem State-of-the-Art-Tool RENGAR:

Effizienz: PUFFERDOS generiert Angriffsstrings, die 97,2- bis 3.872,4-mal kürzer sind als die von RENGAR, während sie dieselben Matching-Zeit-Schwellenwerte (0,1s, 1s und 10s) erreichen.
CVE-Reproduktion: PUFFERDOS reproduzierte erfolgreich 96,8 % der ausgenutzten ReDoS-CVEs, im Vergleich zu 77,4 % bei RENGAR.
Neue Schwachstellen: Angewendet auf 12 populäre Open-Source-Projekte entdeckte PUFFERDOS 59 ausnutzbare ReDoS-Instanzen (25 mehr als RENGAR). Entwickler von sechs dieser Projekte validierten 21 der Funde.
Praxisrelevanz: In einem motivierenden Beispiel mit einer Syntax-Highlighting-Library generierte PUFFERDOS einen 1.000-Zeichen-String, der einen System-Hang von über 4.000 Sekunden verursachte, während traditionelle Methoden 500.000 Zeichen erforderten und aufgrund von Eingabe-Trunkierung im tatsächlichen Programm keinen Hang auslösen konnten.

Bedeutung

Das Paper argumentiert, dass der praktische Nutzen der ReDoS-Detektion derzeit dadurch begrenzt ist, dass generierte Angriffsstrings oft zu lang sind oder nicht durch die Programmlogik propagieren können. Durch die Adressierung dieser spezifischen Mängel bietet PUFFERDOS einen Mechanismus zur Generierung von praktisch ausnutzbaren Belegen für Schwachstellen. Dies ist signifikant, da es direkt den Grund adressiert, warum Entwickler ReDoS-Meldungen oft ignorieren (da sie diese als geringfügig oder nicht ausnutzbar wahrnehmen). Durch die Bereitstellung kurzer, valider Angriffsstrings ermöglicht PUFFERDOS eine genauere Risikobewertung und erleichtert die Behebung von ReDoS-Schwachstellen in realen Softwaresystemen.