Catastrophic backtracking
Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time.
Secrets of the JavaScript Ninja, Third Edition
Catastrophic backtracking is regex backtracking whose possible paths grow exponentially and can exhaust execution time or block a thread.
- How it is used
- Explains how regex backtracking can turn pattern matching into a performance and denial-of-service risk.
- How deep it goes
- Traces a failing match through alternative word splits and compares DFA tradeoffs, without detailing sandboxing.
- Examples
- Uses a roster-matching regex and a near-match ending in an exclamation mark to demonstrate exponential backtracking.
- What you can do after
- Evaluate regex performance risks and consider a DFA-based engine when safety is a priority.
Read how Secrets of the JavaScript Ninja, Third Edition explains catastrophic backtracking →
Regular Expression Puzzles and AI Coding Assistants
Catastrophic backtracking is regex matching behavior in which an engine explores exponentially many alternatives caused by ambiguous pattern assignments before determining that no match exists.
- How it is used
- Validates an alternating-block message protocol while exposing regex performance hazards.
- How deep it goes
- Traces ambiguous group assignments through timing tests and mitigations without detailing matcher internals.
- Examples
- Tests geometric protocol messages and letter-based alternating strings with valid, malformed, and near-miss endings.
- What you can do after
- Diagnose/debug with it by timing adversarial failures and applying prevalidation or possessive quantifiers.
Read how Regular Expression Puzzles and AI Coding Assistants explains catastrophic backtracking →
Related concepts
- exponential time complexityproduces · Exponential time complexity is a computational growth rate in which an algorithm’s running time increases exponentially with input size.
- redosused by · ReDoS is a denial-of-service vulnerability in which crafted input causes regular-expression evaluation to consume excessive computational resources.
- backtrackingkind of · Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.
- non-greedy quantifiercontrasts with · A non-greedy quantifier matches the fewest repetitions that allow the entire regular expression to match.
- regex engineused by · A regular-expression engine is software that interprets regular-expression patterns and applies them to text for matching, searching, splitting, or transformation.
Questions about catastrophic backtracking
What is catastrophic backtracking?
Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time.
Which Manning books explain catastrophic backtracking?
Secrets of the JavaScript Ninja, Third Edition and Regular Expression Puzzles and AI Coding Assistants.
What is the difference between catastrophic backtracking and non-greedy quantifier?
Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time. A non-greedy quantifier matches the fewest repetitions that allow the entire regular expression to match.
What is catastrophic backtracking a kind of?
Catastrophic backtracking is a kind of backtracking. Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.

