ReDoS (Regular Expression Denial of Service)
ReDoS feeds an input that triggers catastrophic backtracking in a regex engine, pinning a CPU and starving the service.
Definition
Regular Expression Denial of Service (ReDoS) is the family of bugs in which an attacker exploits the exponential worst-case runtime of certain regex patterns against certain inputs. Most backtracking regex engines (Perl, Python `re`, JavaScript, .NET, Java's default `Pattern`) can take time exponential in the input length on patterns with nested quantifiers like `(a+)+`. A pattern that runs in microseconds on benign input takes minutes on a 50-character pathological input.
ReDoS is one of the most boring-looking vulnerabilities — until you realise that a regex sitting in your hot path takes down your whole service if anyone discovers the bad input. CDNs and WAF rules have shipped ReDoS-class vulnerabilities in their own normalisation regexes.
How it works
The regex engine, on a "bad" pattern + "bad" input, explores an exponentially-growing tree of backtracking states. Each state is cheap; there are too many. CPU pins, the request thread is stuck, and an attacker who can send a handful of requests can starve the entire service.
Impact
Denial of service. In a synchronous web framework (Express, Flask, Rails), a few bad requests pin every worker thread.
Mitigation
Audit every user-input-validating regex for nested quantifiers. Use a linear-time regex engine: RE2 (Go's default, available for Python via `google-re2` and for Node via `re2` packages), Hyperscan, .NET's non-backtracking mode (NET 7+). Set a regex execution timeout when the engine supports it. Open-source tools (rxxr, redos-detector) flag suspicious patterns in CI.
Examples
- CVE-2019-16769 — npm parse-link-header ReDoS.
- CVE-2020-7793 — express-fileupload busboy ReDoS.