(a+)+$ against forty a’s followed by a !. In RE2 or Go’s regexp, microseconds. In stock JavaScript, Java, Python, or PCRE, it runs essentially forever — exponential time on a 41-character input. Same regular expression, same input, and the difference isn’t optimization polish: it’s two fundamentally different machines with different worst-case complexity, chosen at engine-design time. This split is the root of ReDoS, a real availability vulnerability, and it took down Cloudflare’s global edge for 27 minutes in July 2019 on one bad rule.

Two Ways to Match

A regex describes a set of strings; both engine families start by parsing it to a nondeterministic finite automaton (NFA) — states with possibly-multiple transitions per character. They differ entirely in how they run it.

Thompson NFA simulation (Ken Thompson, 1968) tracks the set of all states the machine could currently be in, advancing every one in lockstep per input character:

text
  input:  a  a  a  a  !
  states: {track every possible position simultaneously}
          the set has ≤ (states in NFA) members, always

Because the state set can’t exceed the pattern’s size, matching is O(n·m) — linear in input, period, no input can make it blow up. This is what powers grep, RE2 (Google), Go, Rust’s regex, and awk — the automata-theoretic tradition, guaranteed-linear by construction.

Backtracking takes the other road: try one path through the NFA, and on a dead end, rewind and try the next alternative, recursively. This is a depth-first search of all possible matches:

text
  (a+)(a+) on "aaa!": try (aaa)(?) fail → (aa)(a) fail → (a)(aa) fail
  → back up the outer group, re-split, retry... combinatorial explosion

With nested quantifiers like (a+)+, the number of ways to partition the input is exponential, and a non-matching suffix forces the engine to try all of them before giving up. That’s catastrophic backtracking — O(2ⁿ). Perl, PCRE, Python re, Java, JavaScript, .NET all backtrack.

Why Anyone Chooses the Explosive One

Backtracking isn’t a mistake — it buys features the pure-automaton model provably cannot express, because they make the language no longer regular: backreferences ((\w+)\s+\1 — match a repeated word), lookbehind/lookahead assertions, and possessive/atomic groups. If your patterns need those, you’re on a backtracking engine by necessity. The engineering failure isn’t using one — it’s using one on attacker-controlled patterns or attacker-controlled input without guards. A user-supplied search regex, a WAF rule, an email/URL validator fed a hostile string: any of these turns “one slow regex” into “one core pinned at 100% until timeout,” and if it’s on a request path, into a denial of service. The Cloudflare outage was a single rule with a nested quantifier deployed globally; Stack Overflow had a similar 34-minute outage from one backtracking regex in 2016. These are ordinary bugs with outsized blast radius.

Defending Against It

The mitigations, in order of robustness:

  • Use a linear engine where you can. RE2 (bindings for most languages), Go, Rust give you O(n) by construction — no timeout to tune, no pattern to audit. If you don’t need backreferences, this is the answer. (Node’s newer engines and V8 added an RE2-based fallback for exactly this reason; .NET added a nonbacktracking option.)
  • Never let untrusted input choose the pattern. User-supplied regexes on a backtracking engine are a direct DoS; if you must, run them under a hard timeout in an isolated worker.
  • Audit your own patterns for the danger shape: nested quantifiers ((x+)+, (x*)*), quantified alternation with overlap ((a|a)*), and quantifiers followed by an often-failing anchor. Static analyzers exist for this.
  • Always bound execution — regex timeouts, input length caps — even on trusted patterns, as defense in depth.

The broader lesson is worth keeping: “it’s just a regex” hides a choice between two algorithms with a complexity gap wide enough to be a security boundary. Knowing which engine you’re on, and whether its worst case can be triggered from outside, is the whole game.

Takeaways

  • Both families build an NFA; Thompson simulation runs it in O(n·m) linear time, backtracking searches paths in up-to-exponential time.
  • Catastrophic backtracking (nested quantifiers + failing suffix) is ReDoS — a real DoS that has caused public multi-minute outages.
  • Backtracking is chosen for backreferences and lookaround, which automata provably can’t express — legitimate, but dangerous on untrusted patterns/input.
  • Prefer RE2/Go/Rust (linear by construction) when you don’t need those features; never let untrusted input pick the pattern.
  • Audit for the explosive shapes and bound every regex with a timeout and input cap regardless.