A regular expression engine that supports backreferences and lookarounds usually works by trying one path and, when it fails, backing up and trying another. That is fast on ordinary input. On a crafted input that almost matches, the number of paths can grow exponentially with the input length, and a single request can occupy a CPU core for minutes. This is ReDoS, regular expression denial of service.
On 20 July 2016 Stack Overflow went down for about half an hour after a post containing a long run of whitespace hit a pattern that trimmed leading and trailing spaces, an unanchored \s+$ shape. On 2 July 2019 a single WAF rule containing .*(?:.*=.*) pinned Cloudflare's edge CPUs and took a large share of the web with it for roughly half an hour. Neither pattern looks dangerous in code review, which is the whole problem.
(a+)+$, ^(\w+\s?)+$The inner repeat can end anywhere, and the outer repeat can start where the inner one stopped. For aaaaaaaaaaaaaaaaaaaaaaaaaaa! the engine can divide the run of as between iterations in 2n ways and tries them all before concluding the ! does not match. Fix: make the iterations unambiguous (a+), or put a mandatory separator between them.
(a|aa)+$, (\d|\w)+$When two branches can match the same text, each repeat has a choice, and choices multiply. Fix: make the branches disjoint, or collapse them into one character class.
\d+\d+$, ^\s*(.*?)\s*$Two unbounded repeats over the same characters leave the engine a split point to try after every character. That is polynomial rather than exponential (quadratic here, cubic with three), but a few thousand characters is enough to hurt.
\s+$With no ^ the engine restarts at every position, rescanning the same long run each time. Anchor the start, or use trim().
Reading the pattern tells you where ambiguity can exist. It does not tell you whether an attacker controls the input, how long it can be, or whether your engine has an optimisation that rescues the case. So a finding is a suspect. In Node the CLI's --probe mode closes that gap for JavaScript patterns: it generates a repeated-character input, times the real engine inside a sandboxed vm with a hard timeout, and reports a pattern as confirmed only if the time actually blows up.
node cli.mjs scan src --probe ERROR nested-quantifier src/validate.js:12 ... Confirmed: exponential -- "a".repeat(26) + "!" took >250 ms.
node cli.mjs scan src --fail-on error # exit 1 on a likely-exponential pattern node cli.mjs scan src --fail-on warn # also fail on polynomial warnings
The CLI is zero-dependency and makes no network call, so it runs in any pipeline that has Node 18 or newer.
No. (\d+,)+ is linear because each iteration must end in a comma the repeat cannot consume. The danger is a repeat whose iterations can end and begin on the same characters, such as (a+)+, because then the engine can split a run of those characters between iterations in exponentially many ways.
A length cap is the cheapest backstop and often enough: exponential growth needs a few dozen characters, so a cap of a few hundred does not remove the risk but a cap of twenty does. Rewriting the pattern so each character has one way to match is the real fix.
Engines built on automata, such as RE2, Go's regexp and Rust's regex crate, match in linear time and cannot be ReDoS'd, at the cost of features like backreferences and lookarounds. Node.js, Python's re, Java and .NET use backtracking; .NET and recent V8 builds offer opt-in linear modes.