Regex Engines and Catastrophic Backtracking

Two Meanings of NFA Execution

“NFA engine” is used for two fundamentally different execution strategies. A Thompson-style engine maintains the complete set of automaton states reachable after each input symbol. Equivalent states are merged, so the engine does not revisit every path that reached them. For a pattern with $m$ automaton states and an input of length $n$, straightforward simulation takes $O(mn)$ time and $O(m)$ active-state space.

A recursive backtracking engine instead commits to one alternative, records choice points, and explores another path after a later failure. This makes captures, backreferences, lookaround, conditionals, and engine-specific extensions convenient, but many paths can represent the same logical state. If overlapping alternatives or nested quantifiers partition the same input in exponentially many ways, a failure near the end can force the engine to enumerate those paths.

A DFA represents each reachable NFA-state set as one deterministic state. Matching is linear in the input length after construction, but eager determinization can create exponentially many states. Production automata engines therefore use lazy construction, bounded caches, tagged NFAs, or hybrid NFA/DFA execution.

Where Exponential Behavior Comes From

Consider ^(a+)+$ and the input aaaa...a!. The inner a+ consumes one or more a symbols, while the outer + chooses how many runs exist. Before reaching !, many partitions appear equivalent: five symbols can be grouped as aaaaa, a|aaaa, aa|aaa, a|a|aaa, and so on.

The terminal $ fails because ! remains. A backtracking engine shortens the most recent repetition, redistributes symbols among earlier repetitions, and retries the same doomed suffix. With $k$ interchangeable symbols, there are $2^{k-1}$ ways to place or omit boundaries between adjacent symbols. Exact step counts vary by implementation, but the ambiguity permits exponential exploration.

Repetition alone is not enough. The explosion needs repeated alternatives that consume the same prefixes plus a later condition that makes the complete match fail. Replacing the nested expression with ^a+$ removes the partition choices while recognizing the same language.

flowchart TD
    A["Match ^(a+)+$ against aaaa!"] --> B{"How much does the first a+ consume?"}
    B --> C["Consume aaaa"]
    B --> D["Consume aaa"]
    B --> E["Consume aa"]
    B --> F["Consume a"]
    C --> G["$ sees ! and fails"]
    D --> H{"Partition remaining a"}
    E --> I{"Partition remaining aa"}
    F --> J{"Partition remaining aaa"}
    H --> G
    I --> K["Try a|a, then aa"]
    J --> L["Try a|aa, aa|a, or a|a|a"]
    K --> G
    L --> G
    G --> M["Backtrack to another partition"]
    M --> B

ReDoS Threat Modeling

Regular-expression denial of service becomes a security issue when an attacker influences the text, pattern, or both, and matching consumes a scarce request thread, event loop, worker, or validation service. Anchored validators are especially exposed because a long near-match postpones failure until the final symbol.

Assess maximum input length, normalization expansion, matches per request, concurrent requests, and whether the engine provides an enforceable deadline. Benchmark adversarial near-misses rather than only successful examples. A 200-millisecond match may look tolerable alone but exhaust a small worker pool under concurrency.

Treat tenant-supplied patterns and imported configuration as executable resource policies. Use syntax restrictions, input caps, compilation limits, deadlines, isolation, and latency monitoring according to the trust boundary. A timeout bounds one invocation but does not make an inefficient expression safe against repeated requests.

Safer Patterns and Engines

Begin by removing ambiguity. Replace ^(a+)+$ with ^a+$, factor (cat|car) into ca(?:t|r), avoid repeating nullable expressions, and prefer delimiter-aware character classes over broad .* searches.

Atomic groups and possessive quantifiers can prevent reconsideration when ambiguity is intentional. For example, (?>a+)+ or (a++)+ commits to consumed characters in supporting engines. These constructs may change the accepted language when later terms legitimately need characters returned, so test equivalence rather than assuming it.

For untrusted workloads, prefer an automata engine when required features are regular. If backtracking is necessary, combine review with input limits, engine deadlines, recursion or step limits where available, process isolation for hard cancellation, and timeout metrics. The benchmark below uses small failing inputs and caps length because benchmarking an unrestricted ReDoS pattern can itself consume excessive CPU. Python 3.11 or newer is required for the atomic group.

import argparse
import re
import statistics
import sys
import time
from dataclasses import dataclass


@dataclass(frozen=True)
class Result:
    label: str
    length: int
    matched: bool
    median_ms: float


PATTERNS = {
    "vulnerable": re.compile(r"^(a+)+$"),
    "simplified": re.compile(r"^a+$"),
    "atomic": re.compile(r"^(?>a+)+$"),
}


def timed_fullmatch(
    expression: re.Pattern[str],
    text: str,
    repeats: int,
) -> tuple[bool, float]:
    """Return match result and median wall-clock duration in milliseconds."""
    samples: list[float] = []
    matched = False
    for _ in range(repeats):
        started = time.perf_counter_ns()
        matched = expression.fullmatch(text) is not None
        samples.append((time.perf_counter_ns() - started) / 1_000_000)
    return matched, statistics.median(samples)


def benchmark(lengths: list[int], repeats: int = 3) -> list[Result]:
    """Benchmark safely bounded failing inputs of the form a^n!."""
    results: list[Result] = []
    for length in lengths:
        attack = "a" * length + "!"
        for label, expression in PATTERNS.items():
            matched, median_ms = timed_fullmatch(expression, attack, repeats)
            results.append(Result(label, length, matched, median_ms))
    return results


def verify_equivalent_on_domain(max_length: int = 32) -> None:
    """Check agreement for the intended language: one or more ASCII a symbols."""
    samples = ["", "!", "b", "a!", "aa!", "ba", "ab"]
    samples.extend("a" * length for length in range(1, max_length + 1))
    for sample in samples:
        outcomes = {
            label: expression.fullmatch(sample) is not None
            for label, expression in PATTERNS.items()
        }
        assert len(set(outcomes.values())) == 1, (sample, outcomes)


def print_results(results: list[Result]) -> None:
    print(f"{'pattern':<12} {'a count':>8} {'matched':>9} {'median ms':>12}")
    print("-" * 45)
    for result in results:
        print(
            f"{result.label:<12} {result.length:>8} "
            f"{str(result.matched):>9} {result.median_ms:>12.6f}"
        )


def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser(
        description="Safely demonstrate catastrophic regex backtracking."
    )
    parser.add_argument(
        "--max-n", type=int, default=18,
        help="largest number of a characters; capped at 24",
    )
    parser.add_argument(
        "--repeats", type=int, default=3,
        help="timing samples per pattern and length",
    )
    return parser.parse_args()


def main() -> None:
    if sys.version_info < (3, 11):
        raise SystemExit("Python 3.11+ is required for atomic-group syntax")
    args = parse_args()
    if not 4 <= args.max_n <= 24:
        raise SystemExit("--max-n must be between 4 and 24")
    if not 1 <= args.repeats <= 20:
        raise SystemExit("--repeats must be between 1 and 20")

    verify_equivalent_on_domain()
    results = benchmark(list(range(4, args.max_n + 1, 2)), args.repeats)
    assert all(not result.matched for result in results)
    print_results(results)

    vulnerable = {
        result.length: result.median_ms
        for result in results
        if result.label == "vulnerable"
    }
    if len(vulnerable) >= 2:
        first = vulnerable[min(vulnerable)]
        last = vulnerable[max(vulnerable)]
        print(f"\nVulnerable growth: {first:.6f} ms -> {last:.6f} ms")
        print("Timings vary by machine; structural ambiguity is the finding.")


if __name__ == "__main__":
    main()