ReDoS — Regex DoS Attack

The attack vector

ReDoS (Regular Expression Denial of Service) is the practical exploitation of catastrophic backtracking. An attacker who can supply input to a vulnerable regex causes the server to spin a CPU core for minutes — or until your process is killed by an out-of-memory or timeout signal.

Real-world example: Cloudflare 2019

In July 2019, a single regex with nested quantifiers caused a global Cloudflare outage. The pattern was checking firewall rules against HTTP request bodies. An adversarial body triggered exponential backtracking; CPU saturation propagated through the network. Outage lasted ~30 minutes, affected millions.

Common vulnerable patterns in the wild

• Email validators with nested quantifiers — many old email regexes have (.+)+ shapes.
• URL parsers with greedy lookahead — .*?(?=&) can backtrack badly on long inputs without &.
• HTML/XML extraction — <(.+)>.*</\1> with backreferences and greedy.
• Markdown rewrite — **(.+?)** chains can explode if patterns nest weirdly.

Defense

1. Don't run untrusted patterns. If users can write regex (search filters, etc.), use RE2 or impose strict timeouts.
2. Don't feed untrusted input to fragile patterns. Use atomic groups, possessive quantifiers, negated classes.
3. Set timeouts. Most languages let you cap regex execution time. Python's re doesn't natively, but regex module does.
4. Use RE2 for any user-supplied input — Go's regexp, Python's google-re2 binding. Linear time guaranteed.

Detection tools

Tools exist to scan codebases for vulnerable patterns: safe-regex (npm), recheck, GitHub's CodeQL queries. Run periodically.