On July 2, 2019, Cloudflare's entire network hit close to 100% CPU across every edge server handling HTTP and HTTPS traffic. Sites went down globally for 27 minutes. A single regular expression did it.
The pattern
The category of pattern is well understood: nested quantifiers on the same character class — something structurally like (a+)+b — create exponential backtracking. Give a backtracking regex engine an input that almost matches but doesn't, and it tries every possible way to partition the string across those nested quantifiers before it gives up.
For an input of length n, that's roughly 2^(n-1) partitions to try:
| Input length | Backtracks attempted |
|---|---|
| 10 | 512 |
| 20 | 524,288 |
| 30 | ~500 million |
| 40 | ~500 billion |
Forty adversarial characters was enough to pin a CPU core — no exploit chain, no crafted payload, just the wrong forty characters against the wrong pattern.
Why This Wasn't a Coding Mistake
The regex compiled fine. It matched correctly on every normal input. It passed review. Nothing was wrong with the code — the vulnerability is a property of the pattern interacting with the engine architecture: nested quantifiers on the same character class create exponential choice points, in any language, regardless of code quality. It's a formally recognized vulnerability class (CWE-1333, ReDoS), not a one-off mistake somebody should have caught.
Picking a DFA-based engine prevents this class of bug entirely; more careful code review doesn't. re2, Go's regexp, and Rust's regex crate all guarantee linear time by compiling to a deterministic automaton instead of backtracking — the tradeoff is losing backreferences (\1), which backtracking engines support and DFA engines structurally cannot. Python's re, JavaScript, Java, and most "standard" engines backtrack: fast on the happy path, exponential on the adversarial one.
I wrote up the full mechanics of this — how a regex actually compiles to a state machine, why backreferences make a pattern provably non-regular, and the hard boundary of what no regex engine can ever match — as part of a CS-theory site aimed at working engineers, not CS students: Regular Expressions: The Formal Model.
Anyone else run into ReDoS in production, or catch a nested-quantifier pattern in review before it shipped?
