Regular Expression Denial of Service
ReDoS exploits catastrophic backtracking in regex engines: crafted inputs make matching time grow exponentially, hanging request handlers on a single CPU core per input.
Definition
ReDoS is a denial-of-service class where a regular expression with nested quantifiers or overlapping alternations exhibits exponential or super-linear backtracking on adversarial input. A few dozen characters can force billions of comparison steps. Defenses: possessive quantifiers, atomic groups, bounded repetition, linear-time engines, and input length limits.
Context and scope
Hits login validation, header parsing, WAF rules, log scraping, and search-as-you-type filters — anywhere user input meets a regex with quantifiers over quantifiers.
Common misconceptions
- Only huge inputs are dangerous — twenty characters can be enough; complexity is in the pattern, not the payload size
- Testing a regex once proves safety — one passing input exercises one backtracking path; adversarial inputs explore others
- Compiled regexes are safe — compilation speeds matching; it does not change exponential backtracking semantics
Anti-patterns
- Validating user fields with patterns like nested quantifiers over alternations without testing pathological inputs
- Deploying WAF rule sets whose regexes were never fuzzed for backtracking behavior
- Running untrusted regexes from configuration or user search syntax on server CPU without a safe engine
Related concepts
Related examples
Authoritative source
https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
What it is
Backtracking engines try one path, then retreat and retry alternatives. Patterns where multiple quantified groups can match the same characters — such as a nested star over an optional group ending with a required char — generate a tree of retries whose size doubles per input character.
How it works
The attacker crafts an input that is almost-matching, maximizing ambiguity: many repetitions of the ambiguous prefix and no satisfying suffix. Every ambiguity multiplies paths. Safe patterns use atomic grouping and possessive quantifiers to commit to one path, or bounded repetition to cap retries; linear engines (RE2, Rust regex) trade some features for guaranteed linear time.
When to audit
Every regex reachable from request data, including library and framework patterns you inherit. Static analyzers flag catastrophic patterns; fuzzers search for slow inputs; benchmark with pathological cases in CI.
Pitfalls
Nested quantifiers hide in composed expressions — building patterns from user fragments multiplies the risk. Linear engines lack backreferences and lookaround, so some rules cannot port. Timeout-based mitigation exists per engine but is not uniform — treat it as a backstop, not the fix.