ReDoS: Catastrophic Regex Backtracking

1. Problem: Catastrophic Backtracking and ReDoS vulnerabilities

Traditional regular expression engines (such as NFA engines in V8, Python, and Java) rely on backtracking. When a pattern contains overlapping or nested quantifiers (e.g., (a+)+$, (a|a)+$) and evaluates a non-matching input, the engine tests an exponential number of paths (O(2^N) or O(N^k)), consuming 100% CPU and freezing single-threaded applications.

2. Minimal reproduction: nested quantifier code triggering 100% CPU spikes

This example demonstrates a classic ReDoS pattern that induces catastrophic backtracking:

/* Classic ReDoS trigger: nested quantifiers (a+)+$ */

const unsafeRegex = /^(a+)+$/;
const maliciousInput = "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!"; // 28 'a' chars plus non-matching '!'

console.time("ReDoS Test");
// The line below causes V8 to evaluate hundreds of millions of failing backtracking paths!
const isMatched = unsafeRegex.test(maliciousInput);
console.timeEnd("ReDoS Test");

3. Root cause: backtracking decision trees and ambiguous paths

1. Branch trialing: with (a+)+$, a backtracking engine can allocate each a across different repetitions. 2. Exponential paths: a failing suffix may force exploration of roughly 2^{N-1} partitions. 3. Event-loop starvation: when Node.js performs this synchronous work on the event-loop thread, other requests cannot be scheduled promptly; the thread is occupied rather than deadlocked in the database sense.

4. Recommendation: refactoring, input bounds, and worker isolation

Refactor ambiguous nesting and overlapping branches, bound input according to the business contract, and execute untrusted or dynamic regexes in a terminable Web Worker or Node.js worker_threads. Evaluate a linear-time engine such as RE2 for high-risk paths, after confirming its restricted syntax supports the required patterns. Static scanners and one length threshold are defense in depth, not proofs of safety.

5. Complete code: genuinely interruptible matching in a browser Worker

Recording elapsed time after a synchronous match cannot interrupt catastrophic backtracking. This browser implementation runs the match in an isolated Worker and terminates it on timeout, while retaining an input-length guard. On Node.js, use worker_threads or a linear-time engine such as RE2.

function regexMatchWithTimeout(
  pattern: RegExp,
  input: string,
  maxLength = 500,
  timeoutMs = 100,
): Promise<boolean> {
  if (input.length > maxLength) {
    return Promise.reject(new RangeError("Input exceeds the safe length limit"));
  }

  const source = [
    "self.onmessage = (event) => {",
    "  const { source, flags, input } = event.data;",
    "  try {",
    "    self.postMessage({ matched: new RegExp(source, flags).test(input) });",
    "  } catch (error) {",
    "    self.postMessage({ error: error instanceof Error ? error.message : String(error) });",
    "  }",
    "};",
  ].join("\n");
  const url = URL.createObjectURL(new Blob([source], { type: "text/javascript" }));
  const worker = new Worker(url);

  return new Promise((resolve, reject) => {
    let timer = 0;
    const cleanup = () => {
      window.clearTimeout(timer);
      worker.terminate();
      URL.revokeObjectURL(url);
    };

    timer = window.setTimeout(() => {
      cleanup();
      reject(new Error("Regex timed out; Worker terminated"));
    }, timeoutMs);
    worker.onmessage = (event) => {
      cleanup();
      if (event.data.error) reject(new Error(event.data.error));
      else resolve(Boolean(event.data.matched));
    };
    worker.onerror = (event) => {
      cleanup();
      reject(new Error(event.message || "Regex Worker failed"));
    };
    worker.postMessage({ source: pattern.source, flags: pattern.flags, input });
  });
}

console.log(await regexMatchWithTimeout(/^a+$/, "aaaaaaaa!")); // false

6. Incorrect approaches

Assuming lazy quantifiers +? eliminate ReDoS (lazy quantifiers still backtrack exhaustively on failing suffixes). Exposing custom user-defined regexes to servers without string length limits.

7. Boundaries: engine features, CSP, and Worker overhead

Native V8 and Node.js regexes support advanced features such as backreferences and lookarounds, and some patterns catastrophically backtrack. Google RE2 trades a restricted syntax for finite-automata execution whose time is linear in input length. Blob Workers also depend on the site's worker-src CSP. Reuse a controlled pool for frequent short matches, but discard any Worker that times out.

8. Verification

Scan regex patterns for (a+)+ or (a|b)+ structures using static analysis tools. Incorporate ReDoS fuzz testing into CI/CD pipelines. Monitor CPU usage spikes tied to RegExp execution.

9. FAQ

Why can a single ReDoS expression crash an entire Node.js server? Node.js uses a single-threaded Event Loop; synchronous CPU-bound backtracking starves the thread, preventing request scheduling.

Do all regular expressions have ReDoS risks? No. Only patterns with overlapping quantifiers or ambiguous branches evaluating non-matching input suffer from catastrophic backtracking.

How do I fix (a+)+$ to make it safe? Simplify it to a single-level quantifier ^a+$, removing partition ambiguity and reducing execution time to milliseconds.

10. Summary

ReDoS attacks exploit algorithmic flaws in NFA regex engines. Production applications must eliminate nested quantifiers, enforce input length limits, and employ worker isolation or DFA engines for high-risk inputs.