Lion Cipher Lab
Find and Fix Catastrophic Regex Backtracking (ReDoS) in Your Own Code
- AppSec / DevSecOps
- Advanced
- ~90 min
- Free · no account required
Why it matters
A regular expression that looks completely ordinary can turn a 28-character HTTP request into 20 seconds of pinned CPU. That is not 'slow code' — it is a denial-of-service vulnerability with a request-level blast radius, catalogued as CWE-1333, and it has taken down real infrastructure: Cloudflare's global 30-minute outage on 2 July 2019 was one WAF rule containing a backtracking regex, and Stack Overflow's 34-minute outage on 20 July 2016 was a regex for trimming trailing whitespace. Both were written by good engineers and both passed code review, because you cannot see the bug unless you…
What you'll learn
- ReDoS / catastrophic backtracking (CWE-1333)
- writing a backtracking regex engine from scratch
- Thompson NFA simulation and linear-time matching
- recognising dangerous regex shapes by eye
- atomic groups and possessive quantifiers
- regex time-budget CI gates
- availability-bug threat modelling
Steps in this lab
- The words first: regex, quantifier, backtracking, ReDoS
- Set up: a folder and a Python you can run
- Build a backtracking regex engine from scratch, with a step counter
- Count the explosion: watch the step counter double per character
- Reproduce it in a real engine, on a regex that looks like production code
- Learn the four shapes so you can spot them by eye
- Prove why a finite-automaton engine cannot blow up
- Fix it four ways and time every one — including the fix that does not work
- The blast radius: one request wedges the whole process
- Find every instance: grep the codebase for the four shapes
- Do it better: a CI gate that fails the build on a slow regex
- When this matters, when it does not, and what to carry away