When a JavaScript regex can be driven into catastrophic backtracking, node-re2 offers an alternative: a native Node.js binding to a DFA regex engine that eliminates backtracking and guarantees O(n) execution time for an input of length n. section 12.6.3
The tradeoff is reduced regex features: engines that eliminate backtracking cannot implement features that depend on it, such as backreferences and lookbehind. Consider node-re2 when regex safety is a priority. 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`,
);
A roster-matching regex illustrates how a seemingly ordinary pattern can take seconds to reject an attack string. section 12.6.3
