💻 computer science

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

Dit artikel introduceert PUFFERDOS, een nieuwe tool die praktische en effectieve ReDoS-attack strings genereert door inputs te synthetiseren op basis van drie formeel geverifieerde kwetsbare patronen en deze te verfijnen via compositionele concolische executie om exploitatie in de echte wereld binnen realistische lengtebudgetten te waarborgen.

Oorspronkelijke auteurs: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Gepubliceerd 2026-06-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer slimme, maar licht obsessieve beveiliger hebt bij de deur van een gebouw. Zijn taak is om te controleren of jouw ID-kaart (de input) overeenkomt met een specifief patroon (de reguliere expressie, of "regex"). Meestal gaat dit snel en gemakkelijk.

Maar, er is een truc. Als je de bewaker een heel specifieke, verwarrende ID-kaart geeft, raakt zijn brein in een loop. Hij begint elke mogelijke manier te controleren waarop jouw ID zou kunnen voldoen aan het patroon, keer op keer, totdat hij zijn energie verbruikt heeft en flauwvalt. Dit wordt een ReDoS-aanval genoemd (Regular Expression Denial of Service). Het is alsof je een rekenmachine probeert te misleiden om eeuwig met wiskunde bezig te zijn, zodat deze vastloopt.

Lange tijd hebben beveiligingsonderzoekers geprobeerd deze vallen te vinden en "test-ID's" te maken om te bewijzen dat de bewaker defect is. Echter, de oude methoden hadden twee grote problemen:

De ID's waren te lang: Ze vereisten inputs die zo enorm waren (zoals een boek vol tekst) dat geen enkele echte website ze ooit zou accepteren.
Ze pasten niet bij het gebouw: Ze testten de bewaker in isolatie, waarbij ze negeerden dat er in een echt gebouw andere bewakers (filters) zijn die jouw ID al tegenhouden voordat deze de hoofdingang bereikt.

Ontmoet PUFFERDOS. Denk aan PUFFERDOS als een meester-slotenmaker die niet alleen het slot kraakt, maar ook precies uitzoekt hoe ze door het hele gebouw naar het slot kunnen lopen, met de kortste, meest efficiënte sleutel mogelijk.

Hier is hoe PUFFERDOS werkt, onderverdeeld in eenvoudige stappen:

1. De "Stop Punt" Strategie (Maak de bewaker harder werken)

De onderzoekers realiseerden zich dat je om de bewaker te laten bevriezen niet zomaar een verwarrend patroon nodig hebt; je hebt een patroon nodig waarbij de bewaker kleine, inefficiënte stappen moet zetten.

De Analogie: Stel je voor dat de bewaker door een gang loopt. Als je hem dwingt om bij elke centimeter te stoppen om de vloer te controleren, wordt hij snel moe. Als hij alleen elke 10 voet stopt, wordt hij langzamer moe.
De Oplossing: PUFFERDOS creëert "sleutels" (attack strings) die de bewaker dwingen om bij elke kleine centimeter te stoppen. Dit doet het door zorgvuldig specifieke tekens te kiezen en deze zo te rangschikken dat de bewaker zo vaak mogelijk moet terugkeren (backtracken/teruggaan om opnieuw te controleren). Dit maakt de aanval duizenden keren sneller dan eerdere methoden, omdat het hetzelfde "bevries"-effect bereikt met een veel kortere sleutel.

2. De Drie "Val" Patronen

Het team ontdekte dat de meeste kapotte sloten in drie specifieke vormen vallen. PUFFERDOS heeft een speciaal recept voor elk van de drie:

De Eén-Loop Val: Een enkel patroon dat op meerdere verwarrende manieren gelezen kan worden. PUFFERDOS kiest het kortste, meest verwarrende teken om te herhalen.
De Twee-Loop Val: Twee patronen naast elkaar die beide hetzelfde teken kunnen lezen. PUFFERDOS gebruikt een teken dat beide patronen kunnen lezen, waardoor ze ruzie krijgen over wie het teken mag verwerken.
De Multi-Loop Val: Een lange keten van patronen. PUFFERDOS bouwt een sleutel die de bewaker dwingt om elke schakel in de keten afzonderlijk te controleren.

3. De "Real-World" Doorloop (Concolic Execution)

Dit is het belangrijkste deel. Oude tools testten het slot in een vacuüm. PUFFERDOS simuleert het volledige gebouw.

De Analogie: Stel je voor dat je een sleutel hebt die een deur opent, maar de deur bevindt zich achter een controlepost, een receptionist en een doolhof. Oude tools lieten je alleen zien dat de sleutel werkt op de deur. PUFFERDOS loopt je door het doolhof, controleert of de receptionist je doorlaat, en zorgt ervoor dat je de deur daadwerkelijk bereikt.
De Methode: Het gebruikt een techniek genaamd "compositional concolic execution". Denk aan dit als een samenvatting van een kaart. In plaats van elke stap in het gebouw telkens opnieuw te bewandelen, maakt PUFFERDOS een "spiekbriefje" voor elke kamer (functie) in het gebouw. Het vraagt: "Als ik deze kamer een verwarrende sleutel geef, geeft deze de sleutel dan door aan de volgende kamer, of gooit deze de sleutel weg?"
Door deze spiekbriefjes te gebruiken, kan PUFFERDOS snel uitzoeken of een korte, efficiënte sleutel daadwerkelijk de kwetsbare lock in een echt programma zal bereiken, of dat deze eerder in het proces door een filter wordt tegengehouden.

De Resultaten

Het team heeft PUFFERDOS getest op duizenden echte programma's en bekende beveiligingslekken (CVE's).

Snelheid: Het genereerde aanval-strings die 97 tot 3.800 keer efficiënter waren dan de vorige beste tool. Het kon een systeem laten bevriezen met een minuscule string in plaats van een enorme string.
Succespercentage: Het reproduceerde succesvol 96,8% van de bekende beveiligingslekken (vergeleken met 77,4% voor de oude tool).
Nieuwe Ontdekkingen: Wanneer ze PUFFERDOS testten op 12 populaire, real-world softwareprojecten, vonden ze 59 nieuwe, voorheen onbekende beveiligingslekken die de oude tools misten omdat die oude tools niet in staat waren om een realistische, korte genoeg aanval te genereren om te bewijzen dat de kwetsbaarheid bestond.

Kortom: PUFFERDOS is een slimmere, meer praktische manier om te vinden en te bewijzen dat een computersysteem kan worden bevroren door een verwarrend patroon. Het vindt niet alleen het slot; het vindt de kortste, meest realistische sleutel om het te blokkeren, waarmee wordt bewezen dat het gevaar echt is en opgelost moet worden.

Technische Samenvatting: PUFFERDOS

Probleemstelling

Regular Expression Denial of Service (ReDoS) aanvallen maken misbruik van het pathologische worst-case executiegedrag van backtracking regex-engines, waarbij ze een superlineair of exponentieel aantal matching-paden dwingen te verkennen. Dit verbruikt excessieve CPU-bronnen, wat leidt tot degradatie van de dienstverlening of onbeschikbaarheid. Hoewel er talrijke detectietools bestaan om kwetsbare regexes te identificeren en proof-of-concept aanvalssignatures te genereren, lijden huidige benaderingen onder twee kritieke beperkingen die praktische exploitatie in de weg staan:

Impraktische Invoerlengtes: Bestaande tools genereren vaak aanvalssignatures die onrealistisch lang zijn (bijv. vereisten van honderdduizenden tekens) om een significante vertraging te veroorzaken. In real-world implementaties beperken invoerrestricties (zoals limieten voor HTTP-headers) deze strings vaak door ze af te kappen voordat ze de kwetsbare regex kunnen bereiken, waardoor de aanval ineffectief wordt.
Gebrek aan Programmaniveau Validatie: Veel gegenereerde strings worden alleen gevalideerd tegen de regex in isolatie. Ze houden geen rekening met data-flow restricties, filterlogica of invoertruncatie binnen het gastprogramma. Bijgevolg kunnen deze strings de kwetsbare regex in een echte uitvoeringcontext vaak niet bereiken, waardoor ontwikkelaars gerapporteerde kwetsbaarheden afdoen als laag-kritiek of niet-exploiteerbaar.

Methodologie

De auteurs stellen PUFFERDOS voor, een hybride framework ontworpen om aanvalssignatures te synthetiseren die zowel efficiënt (het maximaliseren van de matching-kosten binnen realistische lengtebudgetten) als effectief (gevalideerd om de kwetsbare regex in het eigenlijke programma te bereiken) zijn. De methodologie bestaat uit drie kerncomponenten:

1. Formele Analyse en Patroon Taxonomie

De auteurs formaliseren eerst de relatie tussen de structuur van de aanvalssignatuur en de matching-kosten. Door middel van formele bewijzen (Lemma's 3.2–3.4 en Stelling 3.5) stellen zij vast dat de matching-kosten toenemen wanneer:

Repetitie-eenheden zo kort mogelijk zijn.
Repetitie-eenheden worden geselecteerd uit de intersectie van de alfabetten van aangrenzende Loop Expressions (LE's), waardoor meerdere LE's dezelfde substring kunnen consumeren.
Stop-punten (indices waar LE's eindigen) gescheiden zijn in plaats van verweven, wat de engine dwingt om langere inputsegmenten opnieuw te verwerken tijdens backtracking.

Op basis hiervan definiëren zij drie kwetsbare patronen om stringgeneratie te sturen:

Exponential One-Loop (EOL): Een enkele LE met unfolding subregexes met overlappende alfabetten.
Loop-Intersect-Loop (LIL): Twee aangrenzende LE's gescheiden door een niet-loop segment dat door beide LE's gematcht kan worden.
Polynomial Multi-Loop (PML): Aangrenzende LE's met disjuncte alfabetten of separators die niet door beide geconsumeerd kunnen worden.

2. Structuur-gestuurde Aanvalssignatuur Generatie

PUFFERDOS parseert kwetsbare regexes naar een Abstract Syntax Tree (rAST) om het specifieke kwetsbare patroon (EOL, LIL of PML) te identificeren. Vervolgens synthetiseert het kandidaat-aanvalssignatures ( $s_a = x \cdot y^q \cdot z$ ) met behulp van patoonspecifieke regels:

Infix Generatie: Selecteert de kortste repetitie-eenheid ( $y$ ) uit de alfabet-intersectie van de relevante LE's. Voor patronen met meerdere LE's worden onafhankelijk herhaalde eenheden geconcateneerd om te garanderen dat stop-punten gescheiden zijn, wat het aantal backtracking-stappen maximaliseert.
Prefix/Suffix Constructie: Afgeleid de prefix ( $x$ ) uit de niet-loop prefix van de regex en de suffix ( $z$ ) uit de niet-loop suffix, om te garanderen dat de uiteindelijke string door de regex wordt afgewezen om uitputtende backtracking te triggeren.

3. ReDoS-specifieke Compositionele Concolic Verfijning

Om te garanderen dat de gegenereerde string de kwetsbare regex in een echt programma bereikt, gebruikt PUFFERDOS een compositionele concolic executie-strategie:

Pad Extractie: Bouwt een call graph om haalbare paden van programmapunten naar de kwetsbare regex te identificeren.
Functie Summarisatie: Voert concolic unit testing uit op functies langs het pad om ReDoS-specifieke functie-samenvattingen te genereren. In tegenstelling tot traditionele samenvattingen, zijn deze gepruned om enkel gedragingen te behouden die relevant zijn voor de propagatie van de aanvalssignatuur (bijv. identiteitstransformaties of constante returns), waarbij ongerelateerde regex-redeneringen die leiden tot path explosion worden weggegooid.
Systeem-niveau Verfijning: Gebruikt de samenvattingen om systeem-niveau concolic executie te sturen, waarbij interprocedurale constraints worden opgelost om de aanvalssignatuur te verfijnen zodat deze filters passeert en de doel-regex bereikt zonder de realistische invoerlengte-budgetten te overschrijden.

Belangrijkste Bijdragen

Formeel Bewijs van Efficiëntie: Het artikel bewijst formeel dat het selecteren van specifieke karakters en het ordenen daarvan om stop-punten in aangrenzende LE's te scheiden, de regex matching-kosten aanzienlijk versterkt. Dit leidt tot de afleiding van drie kwetsbare regex-patronen en bewezen efficiënte generatieregels.
PUFFERDOS Framework: De ontwikkeling van een hybride generator die formele generatieregels integreert met ReDoS-specifieke compositionele concolic verfijning. Deze benadering overbrugt de kloof tussen theoretische detectie en praktische exploitatie door ervoor te zorgen dat strings kort genoeg zijn voor real-world constraints en geldig zijn binnen de data-flow van het programma.
Uitgebreide Evaluatie: De tool wordt geëvalueerd op een grootschalige corpus van 17.962 kwetsbare regexes, 31 bekende CVE's en 12 populaire open-source projecten.

Resultaten

De evaluatie toont significante verbeteringen aan ten opzichte van de state-of-the-art tool, RENGAR:

Efficiëntie: PUFFERDOS genereert aanvalssignatures die 97,2× tot 3.872,4× korter zijn dan die van RENGAR, terwijl ze dezelfde matching-tijd drempels (0,1s, 1s en 10s) bereiken.
CVE Reproductie: PUFFERDOS reproduceerde succesvol 96,8% van de geëxploiteerde ReDoS CVE's, vergeleken met 77,4% voor RENGAR.
Nieuwe Kwetsbaarheden: Toegepast op 12 populaire open-source projecten, ontdekte PUFFERDOS 59 exploiteerbare ReDoS-instanties (25 meer dan RENGAR). Ontwikkelaars van zes van deze projecten valideerden 21 van de bevindingen.
Real-World Impact: In een motiverend voorbeeld met betrekking tot een syntax-highlighting bibliotheek, genereerde PUFFERDOS een 1.000-karakter string die een systeem hang veroorzaakte van meer dan 4.000 seconden, terwijl traditionele methoden 500.000 karakters vereisten en faalden om een hang te triggeren door invoertruncatie in het eigenlijke programma.

Betekenis

Het artikel betoogt dat het praktische nut van ReDoS detectie momenteel beperkt is omdat gegenereerde aanvalssignatures vaak te lang zijn of niet door de programmalogica kunnen propageren. Door deze specifieke tekortkomingen aan te pakken, biedt PUFFERDOS een mechanisme om praktisch exploiteerbaar bewijs van kwetsbaarheden te genereren. Dit is significant omdat het direct ingaat op de reden waarom ontwikkelaars ReDoS-rapportages vaak negeren (door ze als laag-kritiek of niet-exploiteerbaar te beschouwen). Door korte, geldige aanvalssignatures te bieden, maakt PUFFERDOS een nauwkeurigere risicobeoordeling mogelijk en faciliteert het de mitigatie van ReDoS-kwetsbaarheden in real-world software systemen.