How to Fix Catastrophic Backtracking in Regular Expressions (ReDoS Prevention)
Learn how nested quantifiers cause catastrophic backtracking in regular expression engines, leading to 100% CPU lockups (ReDoS), and how to fix them.
Catastrophic backtracking occurs when a Non-deterministic Finite Automaton (NFA) regex engine tests exponential combinations due to overlapping or nested quantifiers like (a+)+ or ([a-zA-Z]+)*. When input fails near the end of a long string, execution time grows as O(2^n), locking CPU cores at 100% in a Regular Expression Denial of Service (ReDoS).
Solve this problem now with our free Regex Tester & Debugger
Try it instantly in your browser — zero tracking, 100% client-side privacy.
Specification & Architecture Reference
| Vulnerable Pattern | Dangerous Input Sample | Safe Linear Alternative |
|---|---|---|
| (a+)+$ | aaaaaaaaaaaaaaaaaaaaaaaaaaaa! | a+$ |
| ([a-zA-Z0-9]+)*$ | user_identifier_long_string_invalid# | [a-zA-Z0-9]+$ |
| (x+x+)+y | xxxxxxxxxxxxxxxxxxxxxx | x+y |
| .*text.* | A massive 50MB log file without match | text (plain substring search) |
What Causes Catastrophic Backtracking?
Most mainstream programming languages (JavaScript, Python, Java, PHP, Ruby) implement **NFA (Non-deterministic Finite Automaton)** regular expression engines. NFAs evaluate patterns by traversing alternative paths and "backtracking" to previous states when a character fails to match.
When a pattern contains nested or adjacent quantifiers: ```regex ^(a+)+$ ``` For an input string of just 25 `a` characters followed by an exclamation mark `!`, the engine tests every possible permutation of dividing the 25 characters between the inner and outer quantifiers: - $2^{25} = 33,554,432$ evaluation steps. - At 30 characters, the step count exceeds **1,073,741,824**, freezing the Node.js event loop or web worker indefinitely.
3 Rules to Prevent ReDoS
- **Eliminate Nested Quantifiers:** Never nest `+`, `*`, or `{n,m}` inside a group that also has a quantifier:
- **Make Alternatives Mutually Exclusive:** Ensure that adjacent alternatives cannot match the exact same character:
- **Use Lookahead-Based Emulation of Atomic Groups:** Modern JavaScript supports lookaheads, which discard backtracking states once evaluated:
Testing and Debugging Never ship unverified regular expressions to production servers. Use Mickytool's in-browser **Regex Tester & Debugger** to test match behavior, inspect capture groups, and verify pattern efficiency safely inside an isolated client sandbox.
Solve this problem now with our free Regex Tester & Debugger
Execute this workflow immediately without saving data on remote servers.
Frequently Asked Questions
Does Go or Rust suffer from catastrophic backtracking?
No. Languages using DFA engines (like Go's regexp package or Rust's regex crate) guarantee linear O(n) execution time, though they do not support backreferences or lookaround.
Can an attacker exploit ReDoS on client-side React apps?
Yes. While it won't crash your server, a ReDoS pattern executed on user input will freeze the client's browser tab, leading to an unresponsive UI.