liveBook · Manning

Redos

As explained in Secrets of the JavaScript Ninja, Third Edition

ReDoS is a denial-of-service vulnerability in which crafted input causes a regular-expression matcher to consume excessive computational resources.

ReDoS is a denial-of-service attack that exploits catastrophic backtracking: a regex matcher tries many possible ways to split a string, potentially consuming excessive CPU time. Even strings of reasonable length can trigger exponential work. 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 roster regex accepts a valid name list quickly but can take seconds to reject a crafted string. section 12.6.3

Possible ways to reduce the risk include:

  • Use a DFA-based engine such as node-re2 when regex safety is a priority; this avoids backtracking but does not support features such as backreferences and lookbehind. section 12.6.3
  • Run user-provided patterns in a worker and stop execution when it exceeds a time limit. section 12.6.3

How Secrets of the JavaScript Ninja, Third Edition covers it

How deep it goes
Traces exponential backtracking and compares engine and sandbox mitigations without detailing their implementation.
Examples
Demonstrates a roster regex rejecting crafted input and cites a 2019 Cloudflare outage.
What you can do after
Evaluate regex worst-case behavior and consider node-re2 or timed worker isolation for untrusted patterns.
How it connects
Connects ReDoS to catastrophic backtracking, regular expressions, DFA engines, and worker threads.

Also explained in

Compare how 2 books explain redos →

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.