Patterns Can Hide Search Trees

A regular expression often looks like a label on a jar.

match this shape of text

That is the friendly reading. Under the lid, a regex engine is executable machinery. Two engines can accept the same language and have radically different failure behavior. One walks a finite automaton. Another performs a depth-first search through choices. Most of the time both feel instant. Then someone sends a string that almost matches.

That small implementation detail becomes production.

The specimen on the bench is:

^(a+)+b$

It recognizes the same simple language as:

^a+b$

One or more a characters, followed by a b.

The two patterns are extensionally equivalent for this toy alphabet: they describe the same set of strings. They do not have the same operational meaning in a backtracking engine. The first pattern asks the engine to decide how the run of as should be split across the inner a+ and the outer +. If the final b is missing, every split is wrong, and the engine may have to prove that by trying them.

That is the whole bug: a regular expression can hide a combinatorial search.

Ken Thompson Already Took the Shortcut

Ken Thompson’s 1968 regular-expression algorithm compiled a regular expression into an automaton-like program and simulated possible states together.¹ The implementation details are beautifully old-school, but the engineering lesson is modern: do not confuse nondeterminism with backtracking. You can carry many possible states at once instead of recursively guessing one path and returning later.

Russ Cox’s classic article made this contrast concrete for working programmers: some widely used backtracking engines take exponential time on pathological patterns, while a Thompson NFA simulation stays fast for regular expressions without non-regular features.²

The phrase “without non-regular features” matters. Modern regex dialects are not just regular expressions in the formal-language sense. Backreferences, lookarounds, captures, lazy quantifiers, atomic groups, Unicode rules, and leftmost-first submatch semantics all complicate the story. Some features can be handled with automata. Some are not regular. Some engines use hybrid strategies.

Still, the core distinction is sturdy:

backtracking asks "which path should I try first?"
automata simulation asks "which states are possible now?"

The second question is much harder to trick into exponential wandering.

A Near-Miss Is the Expensive Case

Catastrophic backtracking is usually loudest when the input almost matches.

For ^(a+)+b$, the string:

aaaaaaaaaaaaaaaaaa

has no final b. A human sees the missing character immediately. A naive backtracking engine cannot skip the proof. Maybe the first a+ consumed too many as. Maybe the outer repetition should have split them differently:

aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa | a
aaaaaaaaaaaaaaaa | aa
aaaaaaaaaaaaaaaa | a | a
...

There are $2^{n-1}$ ways to place cuts between $n$ adjacent a characters. Every one still lacks a final b.

That is why regular expression denial of service, ReDoS, belongs to the broader family of algorithmic complexity attacks: the attacker supplies a small input that drives a common-case-fast algorithm into its worst case.³ Recent surveys of ReDoS research emphasize the same engineering gap: regex engines, their defenses, and their language features vary enough that analysis must be grounded in real implementations, not only textbook models.⁴

Watch the Search Tree Wake Up

The lab below models full-string matching of ^(a+)+b$. It compares three execution stories:

Backtracking: depth-first exploration of possible splits of the a run.
Thompson NFA: state-set simulation of the same nested pattern.
Rewrite: the equivalent pattern ^a+b$.

The counts are not timings from your browser’s regex engine. That is deliberate. Different JavaScript versions have different regexp mitigations, fallbacks, and JIT behavior. The lab counts the abstract work of the algorithms so the structure is visible.

Number of a's: 18 Input suffix: a...a Plot through n: 24 Highlight: backtracking

backtracking Thompson NFA rewrite active NFA state

Deterministic algorithm model. It counts abstract engine work, not browser wall-clock time. The NFA panel shows active states after each consumed character; state 4 is the pending final b.

Two toggles tell the story.

First, switch Input suffix to Has final b. The backtracking engine succeeds quickly because its greedy first guess works: one big a+, then b.

Now switch back to Missing final b and increase Number of a's. The language has not become complicated. The proof of failure has. The backtracking line climbs on the log plot because the engine explores possible cuts. The NFA line stays almost flat because it keeps possible states alive together.

The rewrite ^a+b$ also stays linear. The cheapest fix is often not a smarter engine; it is removing the ambiguous nested quantifier.

Why Backtracking Survived

If Thompson-style simulation is so good, why do backtracking engines exist?

Because regex dialects grew features and semantics that are convenient for programmers but awkward for pure automata. Capturing groups need specific submatch choices. Lookarounds observe context. Backreferences can make the language non-regular. Leftmost-first behavior is part of what many programmers expect. Backtracking is a natural implementation strategy for those features, and it is fast on ordinary patterns.

Modern systems therefore mix tactics. Google’s RE2 is explicitly positioned as a safe alternative to backtracking engines, trading away some features for predictable behavior.⁵ V8 added an experimental non-backtracking regexp engine and fallback machinery to prevent many catastrophic cases, while noting that its usual Irregexp engine remains extremely fast for most patterns.⁶ Recent work on linear matching for JavaScript regular expressions pushes the boundary further, showing that some features traditionally excluded from linear-time engines can be supported with more careful algorithms.⁷

So the engineering answer is not “all backtracking is bad.” It is:

know when your pattern is a search program,
know what engine will execute it,
and never run untrusted text through an uncapped exponential search.

What I Check in Code Review

When I review a regex in production code, I do not only ask whether it matches the happy examples. I ask:

Does it have nested quantifiers over overlapping languages?
Does it have ambiguous alternation such as (a|aa)+ before a required suffix?
Does it run on untrusted input or in a shared event loop?
Is the engine backtracking, automata-based, hybrid, or timeout-capped?
Are input lengths bounded before the regex runs?
Can the pattern be rewritten with mutually exclusive branches?
Can a parser, split, or hand-written scanner make the intended grammar clearer?
Does the test suite include near-miss failures, not only successful matches?

The near-miss is the case that earns its own test. A regex that matches quickly may still fail slowly.

The Tooling I Want

I would like regex tooling to report an operational type, not only a syntax highlight.

Imagine a linter that says:

language: regular
engine requirement: no backreferences
worst-case model: exponential on backtracking VM, linear on Thompson NFA
attack string shape: "a"^n
safe rewrite candidate: ^a+b$

The hard part is not catching the classroom examples. It is integrating engine semantics, production input bounds, and dependency scanning well enough that a warning means something. That is where the recent ReDoS literature is moving: away from a single abstract model and toward an engineering account of real regex engines and their defenses.

A regex is a tiny program. It deserves a profiler.