On 2 July 2019, Cloudflare's edge servers spiked to 100% CPU across the entire global network. Customer sites went down for 27 minutes. The post-mortem traced the outage to a single regex deployed in a WAF rule earlier that day. The pattern looked harmless. The input that triggered the meltdown looked even more harmless. The combination of the two created a regex evaluation that, on paper, would have taken longer than the age of the universe.

This article explains what catastrophic backtracking is, why the JavaScript and PCRE engines are vulnerable to it, how to spot a dangerous pattern before it ships, and how to fix one when you find it.

What backtracking is

Most regex engines in widespread use — JavaScript, PCRE (the engine in PHP, Python, and Ruby), .NET — are backtracking NFAs. They try to match a pattern at each position in the input, and when a branch fails, they back up and try another. Greedy quantifiers like .* and a+ first try to consume as much as possible, then give back characters one at a time when the rest of the pattern fails.

This design is what makes regex expressive. It can handle nested alternation, lookaround, and recursive group structure, all in a small declarative syntax. It is also the reason some patterns are catastrophically slow on certain inputs.

A trivial example. The pattern a+b against the string aaaaaaaaaaaaaaaa (sixteen as, no b) does this:

  1. The engine matches all sixteen as, greedily.
  2. It tries to match b, fails (end of string).
  3. It backtracks one a, tries b, fails again.
  4. Repeat until zero as remain.
  5. Total work: 17 attempts. Linear in input length. Fine.

That is benign backtracking. The problem appears when there are nested quantifiers.

The catastrophic pattern

Consider (a+)+b against the same input aaaaaaaaaaaaaaaa:

  1. The outer + tries one iteration of (a+), which matches all sixteen as.
  2. b fails.
  3. The engine backtracks: maybe (a+) should match fifteen as and the outer should iterate again over the remaining one.
  4. That fails to match b too.
  5. Maybe (a+) should match fourteen and the outer should iterate twice over the remaining two — split as 1+1, or 2.
  6. And so on.

The number of ways to partition sixteen as into one or more groups of one or more as is 2^15 = 32,768. The engine has to try every one before it can give up. The runtime is exponential in the input length.

On twenty as, that is about half a million attempts. On thirty, half a billion. On forty, half a trillion. Twenty as and the regex returns instantly; forty as and you are waiting longer than the heat death of the sun.

The pattern that caused this — (a+)+, or equivalently (a*)*, (\w+)+, (.*)* — is called a "nested quantifier on a non-anchored group". Whenever the inner quantifier and the outer quantifier can both match the same characters, the engine has multiple ways to split the input, and the number of splits is exponential.

The Cloudflare incident

The pattern that took down Cloudflare's WAF was:

.*(?:.*=.*)

Looks innocuous. The intent was to match an HTTP body that contains an = sign with arbitrary text on either side. The first .* is greedy and consumes the whole input. Then the engine has to backtrack to find a position where = matches, and crucially, the inner .*=.* group also has its own arbitrary text matching — which means for any input without an =, the engine tries every possible way to partition the input into "outer prefix" and "inner left-of-equals" before failing.

On a long body without an =, the work is exponential. The customer that triggered it was sending bodies in the megabyte range. Cloudflare's edge fleet ran the regex on every request. The CPU spike was global within seconds.

The full incident report is public and worth reading. The fix was a single character: .*=.* rewritten to be anchored or to use a non-greedy variant that did not allow the quantifier nesting.

Other notable incidents

Catastrophic backtracking is a recurring class of vulnerability, generic enough to have its own acronym: ReDoS (Regular expression Denial of Service).

  • Stack Exchange, 20 July 2016. A regex used to trim whitespace from user input, applied to a comment containing many trailing spaces, took down the homepage for half an hour.
  • GitLab, 2017. A markdown-related regex applied to nested-emphasis input pegged a Sidekiq worker.
  • Express.js / Node.js, multiple incidents. The body-parser middleware shipped a vulnerable email regex; an attacker sending a crafted From header could spike a server.
  • VS Code, 2020. A regex in a markdown extension hit catastrophic backtracking on legitimate user input, freezing the editor.

In every case the pattern looked fine in code review and held up against typical inputs. Catastrophic patterns only show their teeth on specific shapes of input — usually long strings of one repeating character that almost match.

How to spot a dangerous pattern

A few signals in a regex that should make you look twice:

Nested quantifiers. (...)+ or (...)* where the inner content is itself unbounded — (a+)+, (\w+)*, (\d+,\d+)+,?. Any time an outer + or * wraps something that already matches many characters, ask yourself: can the engine partition the input multiple ways?

Alternation with overlapping branches. (a|aa)+ or (\d+|\d+\.\d+)+ — both alternatives can match the same prefix, so the engine has multiple paths and can backtrack between them. Reorder so longer or more specific alternatives come first, and minimise overlap.

Trailing greedy .* followed by a possibly-failing pattern. .*example against an input that does not contain example is fine — the engine tries all suffixes once. But .*(.+)example against the same input multiplies the work.

Unanchored regex applied to long input. Anchors like ^ and $ (with the m flag, or to the whole input) bound the work the engine has to do. Without them, the engine retries from every position, multiplying the cost.

A useful mental check: pretend the input is a million characters of one repeated letter, with no possible way the pattern can match. Can the engine reach that conclusion in linear time, or does the structure of the pattern force it to try many splits?

How to fix one

When you find a catastrophic pattern, the fixes in order of preference:

1. Eliminate the nested quantifier. (a+)+ is equivalent to a+ — they match the same set of strings. The wrapping ( )+ adds nothing semantically; it only adds backtracking paths. Removing the redundant grouping gives you the same matching behaviour with linear runtime.

2. Make the inner quantifier "atomic" (PCRE only). PCRE supports atomic groups (?>...) and possessive quantifiers *+, ++, ?+, {n,m}+. These commit to a match without backtracking — the engine consumes greedily and never gives any back. (?>a+)+b against twenty as is linear because the atomic group prevents the engine from re-splitting the run of as. JavaScript does not currently support atomic groups in standard regex (they are in the proposal stage as of 2026); use the next option there.

3. Reword the pattern to be non-overlapping. If alternation branches share a prefix, rewrite to factor out the shared prefix: (a|ab) becomes a(b?). If a quantifier follows a group that ends with the same character it starts with, rewrite to disambiguate.

4. Anchor the pattern. A regex that has to match from start to end (^pattern$) cannot retry from arbitrary positions. Where appropriate, anchor.

5. Pre-validate input length. A regex that runs in linear time up to 10,000 characters might still be slow at 10 million. Bounding input size at the perimeter of your system is a defence-in-depth measure independent of the pattern.

6. Use a non-backtracking engine. Rust's regex crate and Go's standard library use RE2, a finite-automaton engine that guarantees linear runtime. The trade-off is no support for backreferences and lookaround, but for most patterns this is acceptable. JavaScript's V8 engine includes RE2 as a fallback for some shapes; PCRE has experimental JIT compilation but no linear-runtime guarantee.

Detecting ReDoS in code review

A handful of automated tools find catastrophic patterns before they ship:

  • redos-detector — a Node-based tool that flags potentially catastrophic patterns in JS/TS source.
  • recheck — analyses a pattern and produces an exploit input if one exists. Used by Snyk, GitHub's Dependabot, and several language linters.
  • ESLint's security/detect-unsafe-regex — a heuristic, false-positive-prone, but cheap to add to a linting config.

For new patterns going into a security-sensitive context (input parsing, HTTP middleware, authentication header parsing), running one of these tools as part of CI is worth the configuration cost.

For exploration and debugging, a regex tester lets you watch a pattern run on test input. The browser's regex engine is the same one your JavaScript will run in production, so a pattern that hangs the tester will hang your site.

What about the JavaScript v flag?

ECMAScript 2024 introduced the v flag, which adds set notation ([\p{...}--\p{...}]), string properties (matching multi-codepoint sequences), and a few other refinements. The v flag does not make catastrophic backtracking impossible — the underlying engine is still a backtracking NFA. It does make some patterns easier to write correctly, which indirectly reduces the chance of accidentally writing a catastrophic one.

Browsers have shipped v since 2023. The regex tester on this site accepts the v flag where the browser supports it.

The proposed feature that would eliminate catastrophic backtracking — atomic groups and possessive quantifiers — is in TC39 Stage 3 but has not yet shipped. Until then, the best defence in JavaScript regex is awareness and the patterns above.

The summary

  • Catastrophic backtracking happens when a regex has nested quantifiers and the engine has many ways to split the input.
  • The runtime is exponential in input length. A pattern that takes 1ms on 20 characters can take an hour on 40.
  • The pattern shapes to watch for: (a+)+, (\w*)*, .*(.+)pattern, alternation with overlapping branches, unanchored regex over long input.
  • The fix is usually structural: eliminate nesting, atomic groups (PCRE), reword overlap, anchor, or bound input length.
  • Real production incidents from Cloudflare, Stack Exchange, GitLab, and others trace to exactly this class of bug.
  • For security-sensitive paths, lint patterns with redos-detector or recheck before they ship.

A regex that handles all your test cases cleanly can still take down a server. The check is "can the engine reach 'no match' in linear time?", not "does the pattern look readable?". Once you have seen one production incident caused by a (a+)+ lookalike, you stop trusting the tests.