Working AtlasSecurity & runtime

Backtrack Bomb

Compare two pattern-checking methods as the input grows.

TryRaise Length n stepwise or choose Jump to max length. Compare recursive calls with state-set advances, not runtime.

Watch forThe state-set matcher tracks possible pattern positions together as the input grows.

Jump to the model

Independent systems exercise

Standalone teaching model; it represents no production implementation.

Interactive model

Pattern

Preset

(a+)+b — nested quantifiers create exponentially many equivalent ways to split the same run of characters.

Evil string

Length n (all 'a', no trailing match)12 chars

Capped at 20 chars — this teaching backtracker reaches millions of steps for the nested pattern; longer strings could freeze this tab.

Climbing fast — 398:1 modeled counter ratio

At n=12, the backtracking matcher records 28,670 recursive attempts against 72 state-set matcher advances. They are different operations, so the ratio is not a runtime comparison. This pattern's nested quantifiers mean each extra character roughly doubles the backtracking count. Drag the length slider to watch the growth.

Recursive calls (log scale)
State-set matcher advances (log scale)
Rapid backtracking-counter growth

Backtracking calls

28,670

Recursive matcher calls for n=12

State-set matcher steps

Same input, different counter unit

Counter ratio

398.2x

Different matcher operation counts, not runtime

Preparing the interactive experiment…

Skill practicedSpot patterns that make input checks grow expensive

Transferable practiceSee how some pattern choices make input checking grow sharply as the text gets longer.

Understand the result

The same pattern is run through two teaching engines against a growing input. NFA means nondeterministic finite automaton: this matcher tracks a set of possible pattern positions and advances them together. The backtracking counter records recursive matcher calls; the state-set counter records advances. For the supported pattern subset, nested quantifiers make backtracking grow exponentially while the NFA counter grows with input length. These counters measure different operations, so their ratio is not a runtime comparison or benchmark.

Controls

Preset: Catastrophic uses (a+)+b — the classic nested-quantifier pattern; Benign uses a+b for comparison.
Length n (all 'a', no trailing match): How many 'a' characters are in the test string — never a trailing match, so both engines have to fully search and fail.
Jump to max length: Snaps straight to the longest length the demo allows.
Reset experiment: Returns to the catastrophic pattern and the default input length so you can replay the comparison from a known starting point.

What to watch for

On the Catastrophic preset, drag Length n up one step at a time and watch recursive-call counts roughly quadruple with each +2 characters.
The Thompson-style state-set matcher counter grows proportionally to input length for this supported pattern subset.
Switch to the Benign preset — both measured counters now grow proportionally to input length because there is no nested repetition for the backtracker to re-explore. Their different units still do not compare runtime.

Why it happens

The demo contrasts a backtracking search with a Thompson-style state-set matcher. Its counters record different operations (recursive matcher calls versus state-set advances), so their ratio is not a runtime comparison. Production engines such as RE2 and Rust regex avoid this class of catastrophic backtracking for supported syntax, with syntax limits and implementation tradeoffs.

What this exercise helps me practice

This standalone security and runtime exercise is not a production validator. It shows how I examine input-dependent computational cost by contrasting ambiguous backtracking with bounded-state matching for the supported pattern subset, keeping hostile input and availability risk in view.

See the broader engineering brief