💻 computer science

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

This paper introduces PUFFERDOS, a novel tool that generates practical and effective ReDoS attack strings by synthesizing inputs based on three formally verified vulnerable patterns and refining them through compositional concolic execution to ensure real-world exploitability within realistic length budgets.

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

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but slightly obsessive, security guard at the door of a building. This guard's job is to check if your ID card (the input) matches a specific pattern (the regular expression, or "regex"). Usually, this is fast and easy.

But, there's a trick. If you give the guard a very specific, confusing ID card, their brain gets stuck in a loop. They start checking every single possible way your ID could match the pattern, over and over again, until they run out of energy and pass out. This is called a ReDoS attack (Regular Expression Denial of Service). It's like tricking a calculator into doing math forever so it freezes.

For a long time, security researchers have tried to find these traps and create "test IDs" to prove the guard is broken. However, the old methods had two big problems:

The IDs were too long: They required inputs so huge (like a book's worth of text) that no real website would ever accept them.
They didn't fit the building: They tested the guard in isolation, ignoring the fact that in a real building, there are other guards (filters) who might stop your ID before it even reaches the main door.

Enter PUFFERDOS. Think of PUFFERDOS as a master locksmith who doesn't just pick the lock; they figure out exactly how to walk through the entire building to get to the lock, using the shortest, most efficient key possible.

Here is how PUFFERDOS works, broken down into simple steps:

1. The "Stop Point" Strategy (Making the Guard Work Harder)

The researchers realized that to make the guard freeze, you don't just need any confusing pattern; you need a pattern where the guard has to take tiny, inefficient steps.

The Analogy: Imagine the guard is walking down a hallway. If you make them stop at every single inch to check the floor, they get tired fast. If they only stop every 10 feet, they get tired slower.
The Fix: PUFFERDOS creates "keys" (attack strings) that force the guard to stop at every single tiny inch. It does this by carefully choosing specific characters and arranging them so the guard has to backtrack (go back and check again) as many times as possible. This makes the attack thousands of times faster than previous methods because it achieves the same "freeze" effect with a much shorter key.

2. The Three "Trap" Patterns

The team discovered that most broken locks fall into three specific shapes. PUFFERDOS has a special recipe for each:

The One-Loop Trap: A single pattern that can be read in multiple confusing ways. PUFFERDOS picks the shortest, most confusing character to repeat.
The Two-Loop Trap: Two patterns next to each other that can both read the same character. PUFFERDOS uses a character that both patterns can read, forcing them to argue over who gets to process it.
The Multi-Loop Trap: A long chain of patterns. PUFFERDOS builds a key that forces the guard to check every link in the chain individually.

3. The "Real-World" Walkthrough (Concolic Execution)

This is the most important part. Old tools just tested the lock in a vacuum. PUFFERDOS simulates the entire building.

The Analogy: Imagine you have a key that opens a door, but the door is behind a security checkpoint, a receptionist, and a maze. Old tools just showed you the key works on the door. PUFFERDOS walks you through the maze, checks if the receptionist lets you pass, and ensures you actually reach the door.
The Method: It uses a technique called "compositional concolic execution." Think of this as a map summary. Instead of re-walking every single step of the building every time, PUFFERDOS creates a "cheat sheet" for each room (function) in the building. It asks: "If I give this room a confusing key, does it pass it along to the next room, or does it throw it away?"
By using these cheat sheets, PUFFERDOS can quickly figure out if a short, efficient key will actually reach the vulnerable lock in a real program, or if it will get blocked by a filter earlier in the process.

The Results

The team tested PUFFERDOS on thousands of real-world programs and known security holes (CVEs).

Speed: It generated attack strings that were 97 to 3,800 times more efficient than the previous best tool. It could freeze a system with a tiny string instead of a massive one.
Success Rate: It successfully recreated 96.8% of known security holes (compared to 77.4% for the old tool).
New Discoveries: When they tested it on 12 popular, real-world software projects, they found 59 new, previously unknown security holes that the old tools missed because the old tools couldn't generate a realistic, short enough attack to prove the vulnerability existed.

In short: PUFFERDOS is a smarter, more practical way to find and prove that a computer system can be frozen by a confusing pattern. It doesn't just find the lock; it finds the shortest, most realistic key to jam it, proving that the danger is real and needs to be fixed.

Technical Summary: PUFFERDOS

Problem Statement

Regular Expression Denial of Service (ReDoS) attacks exploit the pathological worst-case execution behavior of backtracking regex engines, forcing them to explore a superlinear or exponential number of matching paths. This consumes excessive CPU resources, leading to service degradation or unavailability. While numerous detection tools exist to identify vulnerable regexes and generate proof-of-concept attack strings, current approaches suffer from two critical limitations that hinder practical exploitation:

Impractical Input Lengths: Existing tools often generate attack strings that are unrealistically long (e.g., requiring hundreds of thousands of characters) to trigger a significant slowdown. In real-world deployments, input constraints (such as HTTP header limits) often truncate these strings before they can reach the vulnerable regex, rendering the attack ineffective.
Lack of Program-Level Validation: Many generated strings are validated only against the regex in isolation. They fail to account for data-flow constraints, filtering logic, or input truncation within the host program. Consequently, these strings often cannot reach the vulnerable regex in a real-world execution context, leading developers to dismiss reported vulnerabilities as low-severity or unexploitable.

Methodology

The authors propose PUFFERDOS, a hybrid framework designed to synthesize attack strings that are both efficient (maximizing matching cost within realistic length budgets) and effective (validated to reach the vulnerable regex in the actual program). The methodology consists of three core components:

1. Formal Analysis and Pattern Taxonomy

The authors first formalize the relationship between attack string structure and matching cost. Through formal proofs (Lemmas 3.2–3.4 and Theorem 3.5), they establish that matching cost increases when:

Repetition units are as short as possible.
Repetition units are selected from the intersection of alphabets of adjacent Loop Expressions (LEs), allowing multiple LEs to consume the same substring.
Stop points (indices where LEs terminate) are separated rather than interleaved, forcing the engine to reprocess longer input segments during backtracking.

Based on this, they define three vulnerable patterns to guide string generation:

Exponential One-Loop (EOL): A single LE with unfolding subregexes having overlapping alphabets.
Loop-Intersect-Loop (LIL): Two adjacent LEs separated by a non-loop segment that can be matched by both LEs.
Polynomial Multi-Loop (PML): Adjacent LEs with disjoint alphabets or separators that cannot be consumed by both.

2. Structure-Driven Attack String Generation

PUFFERDOS parses vulnerable regexes into an Abstract Syntax Tree (rAST) to identify the specific vulnerable pattern (EOL, LIL, or PML). It then synthesizes candidate attack strings ( $s_a = x \cdot y^q \cdot z$ ) using pattern-specific rules:

Infix Generation: Selects the shortest repetition unit ( $y$ ) from the alphabet intersection of the relevant LEs. For patterns with multiple LEs, it concatenates independently repeated units to ensure stop points are separated, maximizing backtracking steps.
Prefix/Suffix Construction: Derives the prefix ( $x$ ) from the non-loop prefix of the regex and the suffix ( $z$ ) from the non-loop suffix, ensuring the final string is rejected by the regex to trigger exhaustive backtracking.

3. ReDoS-Specific Compositional Concolic Refinement

To ensure the generated string reaches the vulnerable regex in a real program, PUFFERDOS employs a compositional concolic execution strategy:

Path Extraction: Constructs a call graph to identify feasible paths from program entry points to the vulnerable regex.
Function Summarization: Performs concolic unit testing on functions along the path to generate ReDoS-specific function summaries. Unlike traditional summaries, these are pruned to retain only behaviors relevant to the propagation of the attack string (e.g., identity transformations or constant returns), discarding unrelated regex reasoning that causes path explosion.
System-Level Refinement: Uses the summaries to guide system-level concolic execution, resolving interprocedural constraints to refine the attack string so it bypasses filters and reaches the target regex without exceeding realistic input length budgets.

Key Contributions

Formal Proof of Efficiency: The paper formally proves that selecting specific characters and ordering them to separate stop points in adjacent LEs significantly amplifies regex matching cost. This leads to the derivation of three regex vulnerable patterns and provably efficient generation rules.
PUFFERDOS Framework: The development of a hybrid generator that integrates formal generation rules with ReDoS-specific compositional concolic refinement. This approach bridges the gap between theoretical detection and practical exploitation by ensuring strings are short enough for real-world constraints and valid within the program's data flow.
Comprehensive Evaluation: The tool is evaluated on a large-scale corpus of 17,962 vulnerable regexes, 31 known CVEs, and 12 popular open-source projects.

Results

The evaluation demonstrates significant improvements over the state-of-the-art tool, RENGAR:

Efficiency: PUFFERDOS generates attack strings that are 97.2× to 3,872.4× shorter than those produced by RENGAR while achieving the same matching time thresholds (0.1s, 1s, and 10s).
CVE Reproduction: PUFFERDOS successfully reproduced 96.8% of exploited ReDoS CVEs, compared to 77.4% for RENGAR.
New Vulnerabilities: Applied to 12 popular open-source projects, PUFFERDOS discovered 59 exploitable ReDoS instances (25 more than RENGAR). Developers from six of these projects validated 21 of the findings.
Real-World Impact: In a motivating example involving a syntax-highlighting library, PUFFERDOS generated a 1,000-character string that caused a system hang exceeding 4,000 seconds, whereas traditional methods required 500,000 characters and failed to trigger a hang due to input truncation in the actual program.

Significance

The paper argues that the practical utility of ReDoS detection is currently limited because generated attack strings are often too long or fail to propagate through program logic. By addressing these specific shortcomings, PUFFERDOS provides a mechanism to generate practically exploitable evidence of vulnerabilities. This is significant because it directly addresses the reason developers often ignore ReDoS reports (perceiving them as low-severity or unexploitable). By providing short, valid attack strings, PUFFERDOS enables more accurate risk assessment and facilitates the remediation of ReDoS vulnerabilities in real-world software systems.