Cloudflare, 2 July 2019, 27 minutes
At 13:42 UTC Cloudflare deployed a new set of managed WAF rules. Within seconds CPU usage hit 100 percent on every core handling HTTP and HTTPS traffic across the entire network. Customers worldwide got 502s. At the worst point, traffic through the network was down 82 percent. Service came back at 14:09 UTC when the WAF was killed globally, so 27 minutes end to end.
The culprit was one rule meant to catch inline JavaScript in requests. The relevant fragment of the pattern was .*.*=.*. Two unbounded wildcards in a row, followed by a literal, followed by another wildcard. On a string that does not contain what the rule is looking for, the engine has to try every possible way of splitting the input between those two .* groups before it can conclude “no match”, and the number of ways grows with the square, then the cube, of the input length as you add groups.
Two details from Cloudflare’s public postmortem make the story worth retelling. The rule had been through their normal test process. And a CPU-exhaustion guard that would have caught it in production, a protection against exactly this class of bug, had been removed during an earlier refactor of the WAF, so nothing stopped the runaway match. In the writeup they said they were looking at replacing the backtracking engine with a linear-time one, naming the Rust regex crate and RE2 as the candidates.
Worth being precise about what this was and was not: no attacker, no crafted payload, no security bypass. Cloudflare DoSed itself with a config change, on a Tuesday afternoon.
Stack Overflow, 20 July 2016, 34 minutes
Stack Overflow went down for 34 minutes because someone posted about 20,000 consecutive space characters on one line. The post landed on the homepage list, and the homepage ran a trim regex over it on every view, so a single post took the site down.
The regex, from their postmortem, was ^[\s\u200c]+|[\s\u200c]+$, trimming whitespace and zero-width non-joiners from both ends of a line. (Yes, U+200C, one of the invisible characters we went through in the guide to invisible Unicode, and it is in that pattern because people paste them into posts.) Nothing exotic. Nothing nested. Simplify it to \s+$ and the problem is still there.
Here is why. Anchoring whitespace to the end of a string with a backtracking engine means: start at the first space, consume all 20,000, hit the non-space character at the end, discover $ does not apply, give up, restart at the second space, consume 19,999, fail again. Stack Overflow’s own number for the malformed post is 199,990,000 comparisons for a single call. Their timeline was 10 minutes to identify the cause, 14 minutes to write the fix and 10 minutes to roll it out.
This one is the more instructive of the two outages, because \s+$ has no nested quantifier at all. It is quadratic, not exponential, and quadratic is more than enough when the input is user-controlled and the multiplier is “every page view”.
What the engine is actually doing
Almost every regex engine you use daily (PCRE, Java’s java.util.regex, Python’s re, JavaScript’s Irregexp in V8, .NET by default, Ruby’s Onigmo) is a backtracking engine. It walks the pattern, and whenever a quantifier has a choice about how many characters to consume, it takes the greedy option, remembers the alternative, and comes back to try it if the rest of the pattern fails.
That is fine when there is one sensible way to split the input. It becomes exponential when there are many. The textbook example:
^(a+)+$ tested against aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
The inner a+ and the outer + can carve up those 30 a-characters in an enormous number of ways: one group of 30, two groups of 15, three of 10, 15 of 2, and every irregular combination in between. That is 2^29 partitions, over half a billion, and the trailing ! guarantees every one of them ends in failure. Add one more a and the work doubles. Around 40 characters you are into minutes; around 50, longer than the process will live.
The property that makes ReDoS a security bug rather than a performance quirk is this: the explosion only happens on input that does not match. A successful match stops at the first path that works, usually the first one tried. Failure is what forces the engine to prove that no path works, which means visiting all of them. So the payload is not a weird string, it is a string that looks almost right.
Spotting a dangerous pattern
Three shapes cause nearly all real cases:
- A quantifier inside a quantifier.
(a+)+,(a*)*,(\d+)*, and the sneaky version([a-z]+\s?)+that shows up in name and address validators. Exponential. - Adjacent quantifiers over overlapping sets.
.*.*as in the Cloudflare rule, or\w+\d+where a digit is also a word character. The engine has to try every boundary between them. Polynomial, and polynomial is plenty. - Alternation where both branches can match the same text.
(a|a)+is the toy version; the realistic one is(\w|\d|_)+or an email validator with several overlapping alternatives for the local part. Exponential.
Email validation deserves a special mention because it is the single most copy-pasted regex on the internet and several of the popular monsters are vulnerable. The one that used to sit in a well-known validation library, matching a local part like ([a-zA-Z0-9_\.\-])+ followed by more optional groups, blows up on a long run of dots and letters ending in a character that cannot be there. If you validate email with a regex at all, use a short permissive one, cap the length, and send a confirmation mail, since that is the only real check anyway.
“It was fast in testing” proves nothing
This is the part that catches experienced people. You benchmark the pattern, it runs in microseconds on your sample data, you ship it. Your sample data matched. The slow path is the failure path, and nobody writes a performance test out of strings that are supposed to be rejected.
Cloudflare tested their rule. The rule worked. It matched what it was supposed to match, quickly, and the traffic it did not match was what ended the afternoon.
A test that would catch it takes three lines: run the pattern against a repeated character sequence at lengths 10, 20, 30 and 40, each with one character appended that makes the match impossible, and time it. Safe patterns stay flat. A vulnerable one roughly doubles per added character, so the jump between 20 and 30 is unmistakable long before you have to wait for anything. Do the same thing in CI for any pattern that touches user input.
Engines that can’t explode
Backtracking is not the only way to run a regular expression. Simulating a finite automaton, the approach Ken Thompson published in 1968, matches in time linear in the input length, because it tracks all possible states at once instead of trying paths one after another. The price is that backreferences and lookaround cannot be expressed that way, so linear engines simply refuse them.
| Engine | Guarantee | Cost |
|---|---|---|
| RE2 (C++, open-sourced 2010) | linear time, bounded memory | no backreferences, no lookaround |
| Go regexp, Rust regex crate | linear time, same model as RE2 | same restrictions |
| .NET 7+ RegexOptions.NonBacktracking | linear time | no lookaround, no backreferences, no RightToLeft |
| V8 experimental engine (since 8.8) | linear time | opt-in flag, non-standard, restricted syntax |
| PCRE, Java, Python re, JS default, Ruby | none | full syntax, unbounded worst case |
The runtime-level answers, in the order they became available. .NET has had a match timeout since 4.5 (2012) via the Regex constructor that takes a TimeSpan, and Microsoft’s own guidance is to always set one for a backtracking pattern that touches untrusted input. .NET 7, released November 2022, added RegexOptions.NonBacktracking, which drops to a linear algorithm at the cost of lookaround and backreferences. Ruby 3.2, released the following month, added Regexp.timeout plus a memoisation strategy that makes most patterns run in linear time without any code change. Python 3.11 took a different route and added atomic grouping (?>...) and possessive quantifiers to the re module, which let you switch off backtracking for a subexpression by hand.
JavaScript is the weak spot. No timeout, no atomic groups, no possessive quantifiers, and one blocked event loop takes every concurrent request with it. V8 has shipped a non-backtracking engine since version 8.8, reachable with --enable-experimental-regexp-engine and a non-standard l flag on the pattern, and years later it is still experimental and off by default. The workaround that does exist today is emulating an atomic group with a lookahead and a backreference: (?=(a+))\1 matches the same text but throws away the alternatives, which kills the backtracking. Ugly, effective, and worth a comment in the code so the next person does not “simplify” it.
ReDoS arrives through your dependencies
You do not have to write the bad regex yourself. Two examples that hit large parts of the ecosystem:
- semver, CVE-2022-25883, disclosed June 2023 with a CVSS score of 7.5. The range parser backtracked catastrophically on range strings padded with whitespace, so anything passing a user-supplied version range into
new Range()was exposed. Fixed in 7.5.2, 6.3.1 and 5.7.2. Given that semver is a transitive dependency of roughly everything in the npm registry, the interesting part was not the patch but how long the vulnerable copies survived deep in lockfiles. - ansi-regex, CVE-2021-3807, fixed in 6.0.1. A pattern for stripping terminal colour codes, pulled in transitively by chalk and strip-ansi, which is to say by most CLI tooling in existence at the time.
Both are a good argument for reading your lockfile rather than your manifest. A caret range in package.json says what you would accept, the lockfile says what you actually run, and the difference is exactly where an unpatched transitive copy hides. We went through the mechanics of that in caret vs tilde in semver.
Defences that hold, roughly in order of value
- Cap the input length before the regex runs. Boring, unglamorous, and it defeats every ReDoS in this article. Exponential growth on 200 characters is still fast; on 20,000 it is not. Apply the cap at the edge and to every field, not only the ones you expect to be long.
- Fix the pattern shape. Remove nesting, make adjacent quantifiers cover disjoint character sets, anchor with
^and$so the engine cannot retry from every offset, and replace.*with a negated character class such as[^"]*where you know what the delimiter is. Most ambiguity disappears once you stop using the dot as a shrug. - Use atomic groups or possessive quantifiers where the flavour supports them.
(?>a+)anda++tell the engine it may never give characters back. Available in PCRE, Java, Ruby and Python 3.11 or newer, not in JavaScript, where the lookahead trick above is the substitute. - Never run a user-supplied pattern on a backtracking engine. Search filters, admin rules, log query boxes: if the pattern comes from outside, run it on RE2 (via the
re2bindings in Node, or Go, or Rust) so the worst case is bounded by construction. - Add a timeout as a backstop, not as the fix. A timeout converts a hang into an error, which is a real improvement, but an attacker can still consume the full budget on every request. Same reasoning as putting an expensive password hash on an unauthenticated endpoint, which we covered in the password hashing guide: bounded per-request cost is still a cost you can multiply.
- Scan in CI. The
recheckengine behind eslint-plugin-redos and CodeQL’s ReDoS queries both find the realistic cases;safe-regexis quicker to add but misses more.
Both postmortems point the same way: treat every regex that touches user input the way you treat a database query built from user input. Bound the input, know your engine’s worst case, and assume the interesting traffic is the traffic that fails to match.
ReDoS questions
What is ReDoS?
ReDoS, or regular expression denial of service, is an attack in which a small input makes a regular expression take an enormous amount of CPU time to fail. It works against backtracking regex engines, which try every possible way to match a pattern before giving up, so an input that almost matches can force millions or billions of attempts. No exploit code and no unusual traffic volume is needed; a few kilobytes of text in a normal form field is often enough to pin a CPU core.
What is catastrophic backtracking?
Catastrophic backtracking is what happens when a backtracking regex engine has more than one way to split the same input between parts of a pattern and has to try all of them. Nested quantifiers such as (a+)+ or adjacent ones such as .*.*= create that ambiguity, and the number of combinations grows exponentially with input length. The blow-up only occurs on input that does not match, because a successful match stops at the first path that works.
How do I know if my regex is vulnerable to ReDoS?
Look for a quantifier applied to something that already contains a quantifier or an alternation that can match the same text two ways, then test the pattern against a long non-matching string rather than a matching one. Static analysers do this properly: the recheck engine behind eslint-plugin-redos, CodeQL’s polynomial and exponential ReDoS queries, and the older safe-regex package. Timing a pattern against 10, 20 and 30 repeated characters is a decent smoke test, since a vulnerable pattern roughly doubles its runtime per added character.
Is JavaScript vulnerable to ReDoS?
Yes. V8’s regular expression engine, Irregexp, is a backtracking engine, and JavaScript has no regex timeout and no atomic groups or possessive quantifiers to constrain it. A single expensive match blocks the Node.js event loop, so one request can stall every other request the process is handling. V8 has shipped an experimental linear-time engine since version 8.8, enabled with the --enable-experimental-regexp-engine flag and a non-standard l flag on the pattern, but it is off by default.
What is RE2 and why does it not support backreferences?
RE2 is Google’s regular expression library, open-sourced in 2010, which guarantees a match runs in time linear in the length of the input. It gets that guarantee by simulating a finite automaton instead of backtracking, which means it never explores the same position twice. Backreferences and lookaround cannot be expressed in that model, so RE2 rejects them outright. Go’s standard regexp package and Rust’s regex crate use the same approach and make the same trade.
Does limiting input length prevent ReDoS?
It is the single most effective defence and usually the fastest to deploy, because the cost of catastrophic backtracking grows with input length. Capping a field at a few hundred characters turns an exponential blow-up into something that finishes in microseconds. The limit has to be enforced before the regex runs, not after, and it has to cover every path into the pattern, including request bodies, headers, query strings and file uploads that get scanned server-side.
Can a regex timeout fix ReDoS?
A timeout limits the damage of one match, it does not remove the vulnerability. .NET has supported a match timeout since version 4.5 through the Regex constructor that takes a TimeSpan, and Ruby added Regexp.timeout in 3.2. Both turn a hang into an exception, which is a real improvement over a wedged process, but an attacker can still burn the full timeout on every request and exhaust the CPU with concurrency. Java, Python and JavaScript have no timeout at all.
Which regex features cause backtracking?
Quantifiers with a choice about how much to consume: star, plus, the brace form and the lazy variants, plus alternation. A pattern backtracks whenever a later part of the expression fails and an earlier quantifier can give back characters and try again. Anchors, character classes and literals are cheap. The dangerous combinations are a quantifier inside another quantifier, two quantifiers over overlapping character sets next to each other, and alternation branches that can match the same text.