Regular Expressions and ReDoS

Regular expressions are everywhere in validation: emails, URLs, user agents, log lines, routing rules, WAF signatures. Most regex engines in popular languages (JavaScript, Python, Java, Ruby, PHP, .NET, and Perl) use backtracking. Backtracking makes them expressive, supporting backreferences and lookaround, and it is also what lets certain patterns take exponential time on certain inputs. This is regular expression denial of service, ReDoS, and it has taken down production systems that had no other bug.

Two ways to run a regex

The key insight is that there are two families of regex engine, and they have completely different worst cases.

• Finite-automaton engines (NFA/DFA). A true regular expression can be compiled into a finite automaton that reads the input once, character by character, tracking all possible match states simultaneously. This runs in linear time, O(n), no matter how the pattern is written. RE2, Go’s regexp, and Rust’s regex work this way.
• Backtracking engines. These try one way to match, and on failure undo and try another. For most patterns there are only a handful of alternatives, so it is fast. But for patterns where the same text can be matched many different ways, the number of alternatives to try grows exponentially, and the engine explores them all before admitting there is no match. The expressiveness (backreferences cannot be done by a finite automaton) is bought with this worst case.

How backtracking goes wrong

The classic trigger is a nested quantifier:

^(a+)+$

Run it against aaaaaaaaaaaaaaaaaaaaaaaa! (a run of a ended by a non-matching !). The inner a+ can grab one, two, or more a characters, and the outer + can repeat the group in correspondingly many ways, so there are exponentially many ways to partition the run of as between the two quantifiers. The trailing ! guarantees every one of them ultimately fails, so the engine tries them all before giving up. Each additional a roughly doubles the work: around 30 characters take seconds, and a few more take minutes, from a tiny input. This is catastrophic backtracking.

A subtler, polynomial (not exponential) version comes from adjacent overlapping repeats like \d+\d+, which is “only” quadratic but still enough to hang a request with a long input.

Recognizing vulnerable patterns

Watch for ambiguity, meaning more than one way for the pattern to consume the same characters:

• Nested quantifiers: (a+)+, (\w*)*, (.*)*
• Alternation with overlap inside a repeat: (a|a)*, (\w|\d)+
• Adjacent overlapping repeats: \d+\d+, .*.*=, \s*\s*

It has caused real outages

This is not a toy concern. In July 2019 a single regular expression in Cloudflare’s WAF, containing a .*.* style ambiguity, consumed CPU catastrophically and took much of Cloudflare’s global network offline for roughly half an hour. ReDoS has also shipped in widely used libraries that validate emails, parse user agents, and highlight code, where one crafted input hangs every server running the library. A regex is code, and an ambiguous one is a latent denial of service.

Fixes

1. Use a linear-time engine. RE2, Rust’s regex, and Go’s regexp guarantee linear time by construction. They drop backreferences, which is almost always acceptable for validation.
2. Rewrite ambiguous patterns. ^(a+)+$ means exactly ^a+$. Remove the nesting. Use atomic groups or possessive quantifiers ((?>a+), a++) where your engine supports them, which forbid the backtracking that causes the blowup.
3. Cap input length before matching. Many ReDoS issues simply vanish when input is bounded to a sane size, because exponential growth on 20 characters is harmless.
4. Set a timeout. .NET takes a matchTimeout, Ruby 3.2+ has Regexp.timeout, and other code can run the match in a bounded worker and kill it.
5. Prefer a real parser for structured formats (URLs, emails, HTML). A regex that tries to validate a grammar is both wrong and dangerous.

Field notes: finding and proving ReDoS

• Find the vulnerable regex automatically. Static analyzers flag the ambiguous patterns: Semgrep and CodeQL ship ReDoS rules, and regexploit reads a regex (or a codebase) and reports the exact worst-case input that triggers exponential backtracking. Point regexploit at the patterns you extracted and it hands you the attack string.
• Construct the trigger by hand. The recipe is a prefix that drives the ambiguity followed by a character that forces failure. For ^(\d+)+$, feed a long run of digits ending in a non-digit: 1111...1111!. Add characters until the match time climbs; each one roughly doubles the work, so going from “fast” to “minutes” takes only a handful.
• Where to inject. Any user input that reaches a regex: email and URL validators, User-Agent and other header parsing, search filters, log processors, and WAF rules themselves. A single slow request ties up a worker, and a few concurrent ones exhaust the pool, which is a full denial of service with no other bug.
• Prove it safely. Confirm against a local copy with a timeout, never against production, because the entire nature of the bug is consuming the server’s resources. Measure match time as input length grows; a linear engine (RE2) stays flat while a vulnerable backtracking engine curves upward sharply.

The 2019 Cloudflare outage was one .*.* pattern doing exactly this across their fleet. Test only systems you own or are authorized to assess.

Testing notes

When you find a regex in an application, check it against the patterns above, and run static analysis (Semgrep and CodeQL ship ReDoS rules) to flag likely cases. Confirm a suspected ReDoS only in a local copy with a timeout, never against production, because the entire nature of the bug is that it consumes the server’s resources.