What is ReDoS (catastrophic backtracking)?

CWE-1333: Inefficient Regular Expression ComplexityReference page

Short answer

A backtracking regex engine may retry different ways to divide the same input after a match fails. With some ambiguous patterns, those retries can grow exponentially as the input grows. The actual delay depends on the regex, engine, input length, concurrency, and resource limits; repeated expensive requests can exhaust a service's capacity.

VULNERABLE PATTERNS

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

SAFER

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

Why backtracking explodes

A pattern like ^(a+)+$ is ambiguous in a backtracking engine: the run aaaa can be partitioned among the nested quantifiers in several ways. An input ending in a non-matching character can make the engine explore alternatives before it concludes that the whole string fails.

For patterns with the relevant ambiguity, the number of explored paths can grow exponentially with the length of a matching prefix followed by a mismatch. This is a property of particular pattern and engine combinations, not every regex or every failure. Even much smaller inputs can matter when requests run concurrently; enforce input, concurrency, and time budgets.

Where untrusted input reaches a regex

Input validation is the obvious place, but the higher-risk cases are often less visible: parsing User-Agent or other request headers, log processing pipelines, Markdown and syntax highlighting, URL routing rules, content filters and WAF rules, and any library that runs a regex over a field you pass it. Several widely used packages have shipped ReDoS advisories for exactly this reason, so your dependency tree matters as much as your own patterns.

FAQ

Which languages are affected?

Risk depends on the engine and pattern, not just the language. Common backtracking engines can exhibit excessive backtracking for some patterns. Go's regexp documents linear time in input length. Rust's regex crate documents O(m·n) for one search (m is pattern size, n input size), which is linear in input size for a fixed pattern; repeated-match iterators have different worst-case bounds. These engines omit features such as backreferences that prevent the same guarantees.

Is a length limit enough on its own?

It limits the amount of work available to a match, but the safe bound depends on the pattern, engine, request rate, and service budget. Fix ambiguous patterns as well, and apply limits before parsing or matching.

How do I find vulnerable patterns?

Use a ReDoS-aware static analyzer and review findings against the actual regex engine. Manually inspect repeated groups containing repetition or alternatives with overlapping prefixes, then test with bounded inputs and a strict timeout in an isolated test environment.

Can I add a timeout instead?

Timeout support varies by runtime and API. For .NET, set an explicit timeout on untrusted-input matches. Elsewhere, check the exact engine's documented controls; use a safer engine or redesign the pattern when an enforceable timeout is unavailable. A timeout complements input and concurrency limits; it does not make an ambiguous pattern efficient.

What is ReDoS (catastrophic backtracking)?

Why backtracking explodes

Where untrusted input reaches a regex

FAQ

References