On July 2, 2019, a single regular expression pushed to Cloudflare's edge network drove CPU utilization to nearly 100% across every server handling HTTP and HTTPS traffic worldwide, causing a 27-minute global outage. The cause wasn't a DDoS attack or a hardware failure — it was a WAF rule containing a regex vulnerable to catastrophic backtracking, deployed simultaneously to every edge node with no canary rollout, after a CPU-usage guardrail had been inadvertently removed during an earlier refactor. Cloudflare's own postmortem, published ten days later, is one of the clearest public records of what security researchers call ReDoS: Regular Expression Denial of Service. It isn't a new bug class — the underlying algorithmic weakness in backtracking regex engines has been understood for decades — but it keeps resurfacing in production because most languages ship pattern engines that make it trivially easy to write, and most code review processes have no way to catch it. This post walks through the mechanics of why certain regex patterns blow up exponentially on specific inputs, looks at two verified real-world incidents, and covers concrete rewriting and defense-in-depth techniques that work across Python, JavaScript, Java, and .NET.
What actually causes catastrophic backtracking?
Catastrophic backtracking happens when a regex engine has multiple ways to match the same portion of a string and, on failure, has to try all of them before giving up. Backtracking engines — used by PCRE, Java's java.util.regex, .NET's Regex, Python's re, and JavaScript's native engine — work by trying a path through the pattern, and if a later part fails to match, backtracking to try an alternative split of the input. A pattern like (a+)+ is the textbook trigger: matching it against a run of 30 a characters followed by a non-matching character forces the engine to consider every way to partition those 30 characters between the inner and outer +, roughly 2^30 possibilities, before it can conclude there's no match. Adjacent overlapping quantifiers like (a|a)* and patterns like (\w+\s?)+$ create the same ambiguity. The complexity is driven by the input's structure, not its length alone — an input just a few characters longer than the last one that resolved quickly can push runtime from milliseconds to hours.
How does a crafted input actually trigger the exponential blowup?
The attacker doesn't need to make the string match — a string engineered to almost match, then fail at the very end, produces the worst-case behavior. Take the pattern ^(a+)+$ applied to the input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!": every character before the ! is an a, so the engine explores every possible grouping of those a characters between the outer and inner quantifier before it reaches the ! and fails, then backtracks and tries again. Add one more a to the input and the number of partitions roughly doubles, so runtime for a 30-character prefix versus a 40-character one can be the difference between an imperceptible delay and a request that never returns. Because the payload is just a normal-looking string — a User-Agent header, an email field, a URL path — it sails through input validation that only checks length or character set, and lands directly on a single-threaded regex evaluation that can pin one CPU core at 100% until the process is killed or times out.
Has this actually been exploited in production libraries?
Yes — CVE-2022-25927 is a documented, patched example in one of the most widely used JavaScript packages. The ua-parser-js library, used to parse browser User-Agent strings, contained a trim() helper using the regex /\s\s*$/ to strip trailing whitespace. Versions from 0.7.30 up to 0.7.33, and 0.8.1 up to 1.0.33, were vulnerable to ReDoS via a crafted, very long User-Agent string that could bypass the library's own MAX_LENGTH guard and drive excessive backtracking, per the GitHub Security Advisory and NVD entry. Because ua-parser-js sits in the dependency tree of countless Node.js web servers that parse User-Agent headers on every request, an attacker could send a single malicious header and tie up a server thread. The fix, shipped in 0.7.33 and 1.0.33, removed the vulnerable trailing-whitespace pattern entirely rather than trying to bound its backtracking.
Which regex patterns should you treat as red flags in code review?
Four shapes account for most real-world ReDoS findings: nested quantifiers like (a+)+ or (a*)*, overlapping alternation inside a repeated group like (a|a)+, a quantified group followed by another quantifier over a shared character class such as (\w+\s?)+, and any pattern with unbounded repetition anchored only at one end, like ^\s*(\S+\s*)*$, which is the trim-style pattern responsible for the ua-parser-js CVE. The common thread is ambiguity: if the engine has more than one way to divide the same substring between two repetition operators, backtracking cost can grow exponentially with input length. A useful gut check during review is to ask whether removing the outer quantifier changes what the inner one can already match on its own — if it doesn't, the nesting is redundant and dangerous rather than expressive.
How do you rewrite a vulnerable pattern safely?
The most reliable fix is removing the ambiguity rather than trying to out-think the backtracking. (a+)+ collapses safely to a+, since the outer quantifier adds no matching power the inner one didn't already have. For genuinely nested structure, atomic groups ((?>...) in PCRE, Java, and .NET) or possessive quantifiers (a++) tell the engine to commit to a match and never backtrack into it, converting exponential worst cases into linear ones — Python's re module lacks these, but the third-party regex package supports both. Where the input source is untrusted (User-Agent headers, form fields, URL paths), the more robust move is switching engines: Google's RE2, the Rust regex crate, and Go's regexp package all use finite-automaton matching that guarantees linear-time execution by construction, at the cost of dropping backreferences and some lookaround syntax. As defense in depth on top of either fix, cap input length before it reaches the regex and set an execution timeout — .NET's Regex constructor accepts a matchTimeout parameter for exactly this purpose.
Can static analysis catch these patterns before they ship?
Static analysis tools built specifically for regex safety analysis exist and are commonly wired into CI to catch these patterns before merge. The Node.js safe-regex package estimates a pattern's worst-case backtracking complexity and flags anything above a configurable threshold; eslint-plugin-security's detect-unsafe-regex rule runs the same class of check as a lint step; and Semgrep ships community regex rules that pattern-match against known-dangerous shapes like nested quantifiers directly in source code across multiple languages. These tools are lexical and heuristic rather than exhaustive — they can miss ReDoS patterns hidden behind string concatenation or dynamically constructed regex — so they work best paired with the rewriting techniques above and a general SAST/SCA program that also tracks which vulnerable regex-using dependencies your code actually calls, rather than relying on any single check to catch every unsafe pattern before it reaches production.