Regular expression denial of service occurs when a pattern uses ambiguous quantifiers. Attackers send strings that force the engine to backtrack excessively. Fix this by using atomic groups, possessive quantifiers, or linear-time engines. Avoid nested quantifiers and unbounded repetition in user input validation.
Mistake 1: Nesting Quantifiers on Similar Character Classes
Using two or more quantifiers that match overlapping character ranges creates ambiguity. The engine must try every possible way to split the input between the groups. This ambiguity explodes as input length increases.
Why it hurts: The regex engine backtracks through every combination. A short input of 10 characters can trigger thousands of checks. The application appears frozen to other users.
The fix: Ensure quantified groups match disjoint sets. If you match digits and letters separately, use a single character class like [a-z0-9]. This forces the engine to make one decision per character.
Mistake 2: Unbounded Repetition on Optional Elements
Placing a star or plus quantifier around an optional group allows empty matches. The engine can split the input into infinite zero-length segments. This creates a combinatorial explosion of empty paths.
Why it hurts: The engine tries to match the optional group at every position. It backtracks repeatedly to find valid combinations. This consumes memory and CPU cycles rapidly. The process becomes unresponsive within seconds.
The fix: Anchor optional groups with required characters. Require at least one concrete character before allowing repetition. Use possessive quantifiers if your engine supports them. This prevents the engine from revisiting empty states.
Mistake 3: Using Lookarounds with Variable Length
Lookarounds check conditions without consuming characters. When these checks involve variable-length patterns, the engine must re-evaluate them at every step. This multiplies the work for each character in the input.
Why it hurts: The engine performs nested evaluations. Each character position triggers a full scan of the lookaround condition. This turns linear scans into quadratic or worse operations. The latency increases disproportionately to input size.
The fix: Replace variable-length lookarounds with positive matches. Capture the required context in the main pattern. This allows the engine to move forward without re-checking previous positions.
Mistake 4: Ignoring Input Length Limits
Accepting arbitrary-length strings for regex validation invites abuse. Attackers send long strings designed to maximize backtracking. The engine processes the entire string before failing.
Why it hurts: The cost grows exponentially with length. A 50-character string can freeze a server for minutes. This blocks the thread handling the request. Other requests queue up and time out.
The fix: Enforce strict length limits before validation. Reject strings longer than necessary immediately. This bounds the maximum work the engine can perform. Combine this with timeout mechanisms for extra safety.
Mistake 5: Relying on Backtracking Engines for Complex Logic
Standard regex engines use backtracking. They try paths and undo decisions when they fail. This works for simple patterns but fails for complex logic. The engine cannot predict which path is correct.
Why it hurts: The engine explores all possible paths. It wastes cycles on dead ends. This behavior is inherent to the design. No optimization can fully prevent it for ambiguous patterns.
The fix: Use engines based on deterministic finite automata. These engines process input in linear time. They do not backtrack. Switching engines requires rewriting patterns to avoid features like backreferences.
Mistake 6: Failing to Timeout Regex Execution
Running regex without a time limit allows indefinite execution. A malicious input can hold the thread forever. The server runs out of available threads.
Why it hurts: The application stops accepting new connections. This is a denial of service. The server does not crash, so monitoring may not alert. The outage persists until manual intervention.
The fix: Implement hard timeouts for regex operations. Cancel the operation if it exceeds a safe threshold. Return an error to the user. Log the incident for further analysis.
Mistake 7: Validating User Input with Complex Patterns
Using regex to validate complex formats like email or URLs is risky. These formats have many edge cases. Patterns often become overly complex to cover all cases.
Why it hurts: Complex patterns are harder to audit. They often contain hidden ambiguities. Attackers can find these weaknesses. The validation step becomes the attack surface.
The fix: Use dedicated libraries for format validation. These libraries are optimized for safety. They avoid regex backtracking pitfalls. This separates parsing from security validation.
| Mistake | Fix |
|---|---|
| Nesting quantifiers | Use disjoint character classes |
| Unbounded optional repetition | Anchor with required characters |
| Variable-length lookarounds | Use positive matches instead |
| No input length limits | Enforce strict length caps |
| Backtracking engines | Switch to DFA-based engines |
| No timeouts | Implement hard execution limits |
| Complex validation patterns | Use dedicated parsing libraries |
Key takeaways
- Nested quantifiers create exponential backtracking paths that exhaust CPU resources.
- Unbounded repetition on optional elements allows attackers to craft worst-case inputs.
- Switching to deterministic finite automata engines prevents backtracking entirely.
Regex backtracking converts small inputs into massive CPU loads. Replace ambiguous patterns with linear-time alternatives or dedicated parsers.
Frequently asked questions
How do I know if my regex is vulnerable?
Test with increasingly long strings of repeated characters. Measure execution time. If time grows exponentially, the pattern is vulnerable.
Can firewalls prevent ReDoS attacks?
Firewalls can block known malicious payloads. They cannot analyze regex logic. The application must handle safe pattern design.
Are all regex engines vulnerable?
Backtracking engines are vulnerable. DFA-based engines are not. Check your language documentation for engine type.
Does this relate to unsafe YAML deserialization?
Both involve processing untrusted input. YAML deserialization executes code. ReDoS exhausts resources. Both require input validation.
How this guide was produced: written by the Patch Review editorial team with AI assistance, checked against the public references listed below, and reviewed when the facts change. See our editorial policy or report an error.
