# Backtrack

> This skill should be used when a regex might be exploitable or slow — when the user says "is this regex safe", "ReDoS", "catastrophic backtracking", "the regex hangs", "one request pins the CPU", "check my regexes for denial of service", or is writing a pattern that validates user-supplied input. Statically flags backtracking-prone regexes, then proves the dangerous ones by feeding them a crafted input and measuring the blow-up.

- Skill: `lkc-studio/backtrack` (Agent Skill, multi-file: 5 files)
- Install (CLI): `npx skillmds@latest add lkc-studio/backtrack`
- Raw SKILL.md: https://api.skillmd.com/api/skills/lkc-studio/backtrack/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: lkc-studio (https://skillmd.com/u/lkc-studio)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/lkc-studio/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

```bash
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.