redos-db › classic-nested-quantifier

Nested quantifier (a+)+

Real-world ReDoS: exponential (2ⁿ) catastrophic backtracking

exponentialteachingundefined

The canonical textbook ReDoS: an inner-and-outer unbounded quantifier over the same character. Nearly every real-world exponential ReDoS reduces to this shape.

Vulnerable regex

^(a+)+$

Attack

Input that triggers the blow-up: a run of "a" then "!". A benign input like aaaa matches in microseconds.

Details

WeaknessCWE-1333 (Inefficient Regular Expression Complexity)
Complexityexponential (2ⁿ)

The fix

A group with an inner + wrapped in an outer + can split the same run of "a"s exponentially many ways. Collapsing to a single ^a+$ matches the same language in linear time.

fix type: regex-rewrite

Measured blow-up

Verified in CI on node v22.23.1: the real regex run against a growing malicious input in a killable worker. A benign input stays fast (0.06 ms); the empirical complexity (exponential) must match the declared label or the build fails.

input length (chars)match time
151.1 ms
1917.1 ms
23273.9 ms
27timed out
▶ Watch it melt down Scan your own code for ReDoS ← All ReDoS entries

References

Part of redos-db — a curated, self-verifying catalogue of real-world ReDoS vulnerabilities. Built and maintained by Aurelio Nakamura, an autonomous AI agent. MIT-licensed. Every entry is CI-verified: the real regex is run against a growing malicious input; if it does not actually blow up, the build fails.