Defending Against ReDoS: Writing High-Performance Regular Expressions
Learn how catastrophic backtracking crashes Node.js and web services, and how to write linear-time, ReDoS-safe regular expressions.
1. The Anatomy of Catastrophic Backtracking
Regular Expression Denial of Service (ReDoS) occurs when a regular expression engine encounters an ambiguous pattern with overlapping, nested quantifiers applied to non-matching input strings.
In non-deterministic finite automaton (NFA) engines (used by JavaScript and Python), the engine attempts every permutation of matches. When evaluated against crafted inputs, computation complexity spikes from linear `O(n)` to exponential `O(2^n)`, freezing the Node.js event loop completely.
2. Identifying Vulnerable Patterns
The hallmark of a ReDoS vulnerability is nested repetition of overlapping token sets. Consider the classic vulnerable email pattern: `^([a-zA-Z0-9_.-]+)+@domain.com$`.
When fed `aaaaaaaaaaaaaaaaaaaaaaaaaaaa!`, the engine evaluates billions of backtracking combinations to test whether the final character might match, blocking CPU cores indefinitely.
// VULNERABLE: Nested repetition with overlapping character classes
const unsafePattern = /^([a-zA-Z0-9]+_?)+$/;
// SAFE: Atomic group equivalent with mutual exclusivity
const safePattern = /^[a-zA-Z0-9]+(_[a-zA-Z0-9]+)*$/;
// Testing safety with execution time bounds
export function safeRegexMatch(pattern, input, maxTimeMs = 100) {
const start = performance.now();
const match = pattern.test(input);
const elapsed = performance.now() - start;
if (elapsed > maxTimeMs) {
console.warn(`Slow regex detected: ${elapsed.toFixed(2)}ms`);
}
return match;
}3. Best Practices for Production Engines
1. Avoid nested quantifiers like `(a+)+` or `(a*)*`.
2. Ensure tokens separated by quantifiers are mutually exclusive.
3. For complex user-supplied patterns, enforce execution timeouts or execute searches inside dedicated Web Workers.