backtracklisted

# 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-