liveBook · Manning

Catastrophic backtracking

As explained in 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.

When a regex engine backtracks through exponentially many possible matches, a seemingly ordinary input can consume excessive execution time and block JavaScript’s thread. Exploiting this behavior to overwhelm a system is called ReDoS. section 12.6.3

Listing 12.13 A regex with catastrophic backtracking
const rosterRegex = /^(?:\w+\s*)+$/; #A

console.assert( #B
  rosterRegex.test("Hattori Yoshi Fuma"), #B
  "A genuine roster is accepted instantly", #B
); #B

const attack = #C
  "I will erase your existence from this realm!"; #C
const start = performance.now(); #C
rosterRegex.test(attack); #C
const elapsed = performance.now() - start; #C
console.log(
  `Rejecting the attack string took ${elapsed.toFixed(0)}ms`,
);

The pattern /^(?:\w+\s*)+$/ accepts a roster, but a near-match ending in ! makes the engine reconsider how it split the words. With 36 letters, the example describes 2³⁶ possible splits. section 12.6.3

Options for reducing the risk include:

  • Consider a DFA-based engine, such as node-re2; it avoids backtracking and guarantees linear execution time, but does not support backreferences or lookbehind. section 12.6.3

How Secrets of the JavaScript Ninja, Third Edition covers it

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.
How it connects
Connects regular expressions with backtracking, ReDoS, DFA engines, backreferences, and lookbehind.

Also explained in

Compare how 2 books explain catastrophic backtracking →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Secrets of the JavaScript Ninja, Third Edition. The section links point to the parts of the book it draws on.