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.

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: lkc-studio
• Source: lkc-studio/claude-plugins
• License: MIT

Install and usage instructions live in the source repository linked above.