ReDoS Deep Dive

ReDoS (Regular Expression Denial of Service) is a vulnerability where a crafted input makes a backtracking regex engine do exponential or high polynomial work before it gives up. In PHP, that work usually ends in a silent failure: preg_match() returns false once PCRE’s backtrack limit is exhausted.

Simple explanation

Take /(a+)+$/ and the input "aaaaaaaaaaaaaaaaaaa!". The ! means the pattern cannot match, but the engine only learns that after trying every way of splitting the as between the inner + and the outer +. Each extra a doubles the number of ways. With PHP’s default limits, 19 a and a ! are enough for preg_match() to fail with “Backtrack limit exhausted”.

How ReDoS happens

The problem: ambiguity under backtracking

PCRE tries the alternatives of a pattern in a fixed order: the left alternative first, a greedy quantifier’s next iteration before its exit, a lazy one the other way round. When an attempt fails, it backtracks to the last choice and tries the next one. That costs nothing when there is only one way to match each part of the input. It costs a lot when there are many:

Pattern: /(a+)+$/
Input:   "aaaa!"

The engine tries:
- (a+) takes "aaaa", the outer + stops, $ fails on "!"
- (a+) takes "aaa", the outer + repeats with "a", $ fails
- (a+) takes "aa", then "aa", $ fails
- (a+) takes "aa", then "a", then "a", $ fails
- ... every composition of 4: 2^3 ways, then 2^(n-1) for n characters

Two classes of cost

• Exponential: a loop that can read the same text in two different ways, as (a+)+, (a|aa)* or (a|a)*. Each repetition of that text doubles the work: 2ⁿ steps.
• Polynomial: two or more quantifiers in a row that can read the same text, as a*a* (n² steps) or a*a*a* (n³). The backtrack limit does not stop it in time: /a*a*$/ matches 200,000 a and a ! without an error, after 6.5 seconds.

Vulnerable shapes

Each pattern below was run through RedosAnalyzer and, for the vulnerable ones, its attack replayed on PCRE2:

How PHPRegex detects ReDoS

PHPRegex reads the pattern, and runs it only to check a witness through a lookaround on a few short inputs (or in confirmed mode):

1. The lexer and parser build a RegexNode AST.
2. RedosAnalyzer builds from it a prioritized NFA: an automaton whose ε-transitions are ordered as PCRE tries them. Atomic groups, possessive quantifiers and atomic lookaround bodies are separate automata, analysed on their own and seen from outside as one step.
3. It looks for ambiguity in that automaton, after the method of Weideman et al. (“Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguous NFA”, 2016):
   • a state with two different loops reading the same word means exponential cost;
   • a chain of k states, each looping on a word and reaching the next on that same word, means polynomial cost of degree k.
4. From the ambiguous loop it builds the witness: a prefix that reaches it, the word to pump, and the shortest suffix that makes the attempt fail. Characters are chosen deterministically: the smallest printable ASCII character of each set, then the other sets of the loop, before giving up. The model does not decide a lookaround: a witness through one is checked on the running PCRE2, its attempt pinned where it starts.
5. The pattern’s class is the worst class over the pattern and its sub-searches.

A pattern is safe (proven) only when the automaton holds no ambiguity at all. An ambiguity for which no witness can be built is not taken as safe: the heuristics decide, and abstractions lists ambiguity without witness at offset N.

The model covers characters and classes (exact sets under /u and /i, computed from the running PCRE2), alternation, groups, every quantifier, atomic groups, possessive quantifiers, atomic lookarounds, anchors and word boundaries. It reads inline options as PCRE does: an option set inside one alternative also holds in the alternatives after it, r (caseless restrict) and the ASCII options (a, aD, aS, aW, aP, aT) are read per scope, (?^) clears i, m, n, s, x, xx and r but keeps U and the ASCII options, xx drops a class’s spaces and tabs, and \b under aW reads the ASCII \w. Backreferences, conditionals, recursion and subroutine calls, backtracking control verbs, callouts, \X, \R, non-atomic lookarounds such as (*napla:…), \b and \B under two different ASCII scopes in one pattern ((?aW:\b)…\b), and a bounded repeat whose body can match the empty string are outside it: there, as for a pattern over the analysis budget, the structural heuristics of RedosProfiler decide, as in 1.x:

• star height: nested unbounded quantifiers;
• overlapping alternatives inside a repetition, through CharSetAnalyzer;
• backreference loops inside a repetition;
• quantifiers over sub-patterns that can match nothing;
• adjacent quantifiers over overlapping character sets;
• atomic groups and possessive quantifiers lowering the severity.

The result says which of the two decided: proof is proven, heuristic, budget_exceeded or not_analyzed. The ReDoS guide states what a proof guarantees, and its limits.

composer require --dev php-regex/php-regex:2.x-dev

The commands below need the CLI package; the PHP API needs php-regex/regex-toolkit. The pre-release monorepo above installs both, binary included.

Using PHPRegex for ReDoS protection

CLI usage

# Check a single pattern
vendor/bin/regex analyze '/(a+)+$/'

# Replay the attack on the running PCRE
vendor/bin/regex analyze '/(a+)+$/' --redos-mode=confirmed

# Scan your entire codebase for ReDoS risk
vendor/bin/regex lint src/ --redos --no-lint --no-optimize

PHP API

use PHPRegex\Redos\RedosSeverity;
use PHPRegex\Toolkit\Regex;

$regex = Regex::create();

$analysis = $regex->redos('/(a+)+b/');
echo $analysis->severity->value, "\n";   // critical
echo $analysis->complexity->value, "\n"; // exponential
echo $analysis->proof->value, "\n";      // proven
echo $analysis->witness->render(), "\n"; // "a" x n . "!b"

// Check against a threshold
if ($analysis->exceedsThreshold(RedosSeverity::High)) {
    echo "Pattern is vulnerable\n";
}

// Proven safe, not just "nothing found"
var_dump($regex->redos('/a+b/')->isProvenSafe()); // bool(true)

// Recommendations from the structural analysis
foreach ($analysis->recommendations as $recommendation) {
    echo 'Suggestion: ', $recommendation, "\n";
}

Fixing vulnerable patterns

Every fix works the same way: it removes the ambiguity the automaton found, leaving one way to read each repetition instead of many. Possessive quantifiers and atomic groups commit to the first match and never revisit it; simplifying (a+)+ to a+ deletes the second way to split the same text; bounding a repeat caps the work even when overlap remains.

The rewrite cookbook - each repair proven safe (or not) by the analyzer, the quick-reference table of vulnerable vs safer pairs, and the defense-in-depth checklist - lives in the ReDoS guide:

• Repairs with proofs - RedosRepairer rewrites a pattern and certifies the rewrites
• Fixing Vulnerable Patterns - the seven rewrites, each with its verdict
• Quick Reference: Vulnerable vs Safer - the pairs at a glance
• Defense in Depth - the checklist beyond rewriting

Related concepts

• ReDoS Guide - The verdict, the witness, confirmed mode and the guarantee
• Architecture - Where the analysis sits in the library
• FAQ & Glossary - Common ReDoS questions

Further reading

• OWASP ReDoS Guide - Security best practices
• Weideman et al. 2016 - The ambiguity analysis this library implements
• Catastrophic Backtracking - Detailed explanation

Edit on GitHub Copy as Markdown