Catastrophic regex backtracking (ReDoS) — how to spot and fix it

Some regular expressions run in exponential time on certain inputs because the engine backtracks through an explosion of ways to match. An attacker who can send input to a vulnerable pattern can make a single short string pin a CPU core for seconds or minutes, which is a denial of service. The fix is to remove the ambiguity that causes the backtracking, usually a nested or overlapping quantifier.

Why it's a problem

On a typical event-loop server, one request stuck in a backtracking regex blocks everything else on that worker. A handful of crafted requests can take the whole service down with almost no bandwidth. Because the pattern behaves normally on ordinary input, it passes testing and only fails when someone sends the specific shape that triggers the blowup.

// nested quantifier over an overlapping class: exponential on "aaaa...!"
const re = /^(a+)+$/;

// real-world shape: validating with (\s*\w+\s*)* style groups
const emailish = /^(\w+\s*)*@example\.com$/;

// remove the nesting; match the same language without ambiguity
const re = /^a+$/;

// anchor and avoid overlapping repeats; or validate with a parser/length cap
const emailish = /^\w+@example\.com$/;

Why AI tools write this

Assistants build regexes by composing pieces that look reasonable, and nested quantifiers like (x+)+ or (x*)* read as harmless to a model that is pattern-matching on syntax rather than reasoning about the matching engine's time complexity. The regex validates correct input in the example it was given, so nothing signals the exponential edge case.

The quick fix

• Look for nested quantifiers such as (a+)+, (a*)*, or (a|a)* and flatten them.
• Avoid overlapping alternations where the same character can match multiple ways.
• Cap input length before matching, and prefer a real parser for structured formats.
• Test suspect patterns with a long adversarial string and a timeout to confirm they stay linear.