# Regex Engines: The NFA/Backtracking Split That Explains ReDoS

> The same pattern runs in microseconds in Go and hangs for years in JavaScript, on the same input. The reason is a fork in engine design made in the 1970s — automata vs backtracking — and it's why one regex took Cloudflare's edge offline.

URL: https://harshith.in/blog/how-regex-engines-work/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, security, fundamentals

`(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.