Backtrack

Backtrack: regexes a single input can freeze

Some regex shapes take exponential time on a crafted string. (a+)+$ against "aaaaaaaaaaaaaaaaaaaaaaX" makes the engine try every way to partition the a's before it can conclude there is no match — a couple of dozen characters can pin a CPU for minutes. When that regex validates user input, one request is a denial of service.

The vulnerability is called ReDoS, and it is common precisely because the patterns look innocent. (\d+)*, (\w+\s?)+, (a|a)* — all ordinary-looking, all catastrophic.

Static suspicion is not enough — this proves it

The distinctive move: structure analysis only suspects. Whether a pattern actually blows up depends on subtleties (anchoring, whether the branches truly overlap) that are hard to settle by reading. So backtrack then proves — it feeds each suspect a growing attack string, times the match, and confirms only the ones whose runtime actually explodes.

suspect     nested/overlapping quantifier found by structure
CONFIRMED   runtime measured to blow up super-linearly with input length

A confirmed finding comes with the exact attack string and the measured slowdown. That is evidence, not a heuristic — you can hand it to whoever owns the regex and they can reproduce it.

Step 1: scan

scripts/backtrack.py app.py            # one file, static + dynamic
scripts/backtrack.py --all src/        # a tree
scripts/backtrack.py --static-only x.py  # skip timing (fast, CI-friendly)
scripts/backtrack.py --json app.py     # machine-readable

Standard library only. It extracts regex literals passed to re.*, flags the suspect structures, then confirms.

  app.py:2  [CONFIRMED]
      /^(a+)+$/
      nested quantifier -- a group repeated inside another repeat
      attack: 'a' * 26 + a non-matching byte   (~260x slower over 8 more chars)

Exit code: 2 if anything is confirmed, 1 if only unproven suspects, 0 if clean.

The dynamic pass is safe

A catastrophic regex cannot be timed in-process — Python's re has no per-call timeout and the C matcher ignores signals mid-run, so a blow-up would hang the scanner itself. Each timing run therefore happens in a separate process group that is SIGKILLed at the timeout. Nothing is left burning CPU. (This is the lesson from the strays skill applied deliberately; a tool that hunts runaway processes must not create them.)

Step 2: fix a confirmed pattern

The cause is always the same: the engine has more than one way to match the same input, so on failure it tries them all. Remove the ambiguity.

• Nested quantifiers (a+)+ → collapse to a single quantifier: a+. The nesting adds nothing but backtracking.
• Overlapping alternation (a|ab)* → make the branches mutually exclusive, or anchor so only one can match at each position.
• Adjacent open-ended repeats .*x.* → anchor, or bound the repeats ([^x]*x.*) so they cannot overlap.

Engine-level fixes when the pattern cannot be simplified:

• Possessive quantifiers / atomic groups ((?>...), a++) tell the engine never to backtrack into that group. Available in the regex module on PyPI, not the stdlib re.
• A non-backtracking engine — Go's regexp, Rust's regex, or RE2 — runs in guaranteed linear time. Best for regexes that must handle untrusted input at scale.
• Bound the input length before matching. A cap of a few hundred characters turns "minutes" into "milliseconds" and is a cheap defence in depth even after the pattern is fixed.

references/redos.md has the vulnerable-shape catalog, worked rewrites, and per-language engine notes.

Step 3: verify the fix

Rerun backtrack.py on the fixed pattern. A correct rewrite drops from CONFIRMED to absent — the same attack string no longer blows up. Re-running is the proof the fix worked, exactly as the original run was the proof it was broken.

Limits

• Only literal regexes passed to re.* are seen. Patterns built at runtime from concatenated strings are invisible to static extraction.
• The dynamic pass can have false negatives. A pattern needing a longer or differently-shaped input than the tool tries may not blow up within the time budget. suspect-but-unconfirmed still deserves a look.
• False positives are possible in the static pass and are exactly why the dynamic pass exists — trust CONFIRMED over suspect.
• Confirmation proves a pattern is vulnerable; absence of confirmation does not prove it is safe. For regexes on untrusted input, prefer a linear-time engine regardless.

Resources

• scripts/backtrack.py — static structural analysis plus a killable, process-group-isolated dynamic confirmation pass. --static-only, --all, --json.
• references/redos.md — the catalog of catastrophic shapes, side-by-side rewrites, engine and language options, and input-hardening.