~/blog

A regex can be a denial-of-service bug, and the tell is nested quantifiers

published Aug 04, 2026

#regex#security#performance

TL;DR

Most regex engines backtrack, and backtracking can go exponential. The shape to look for is a quantifier wrapped around something that is itself quantified and can match the same characters — (a+)+, (\s*\w+)*, (.*,)*. On a non-matching input, the engine tries every way of splitting the string before it gives up. Thirty characters is enough to hang a request thread.

JavaScript gives you no timeout. Your options are: bound the input, change the pattern, or use a non-backtracking engine.

The problem

This is the whole bug, and it fits in one line:

// Fine. Matches instantly.
/^(a+)+$/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa')

// Same regex, one character appended. Hangs.
/^(a+)+$/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!')

The second call does not throw, does not log, and does not return in any useful amount of time. It pins a core. In Node that is your event loop; in a browser tab it is the main thread. Add ten more a characters and the runtime multiplies by roughly 1000.

Real code does not usually contain (a+)+. It contains things like this:

// A "collapse repeated words" pattern
/^(\w+\s*)+$/

// A crude CSV field splitter
/^(\s*[^,]+,)*\s*[^,]+$/

// Nested optional groups in a URL/path matcher
/^(\/[\w-]+)*\/?$/

The CSV one is the classic. (\s*[^,]+,)* is a quantified group whose contents can also match a variable number of characters, so a long line without a trailing valid field forces the engine to re-partition the whole string.

This is not theoretical. Cloudflare took a global outage on 2 July 2019 from exactly this: a WAF rule containing .*(?:.*=.*) was deployed, and CPU on every machine in the network went to 100%. Their postmortem walks through the backtracking step by step.

Why it happens

A backtracking engine tries one path through the pattern and, on failure, rewinds and tries the next. For most patterns the number of paths is small. For a quantifier containing a quantifier that matches overlapping text, the number of paths is the number of ways to partition the input — which grows exponentially.

Take (a+)+$ against aaaa!. The outer + can run one iteration of a+ matching all four characters, or two iterations splitting 1+3, 2+2, 3+1, or three iterations, or four. Every one of those ends at !, fails $, and backs up into the next arrangement. For n characters there are 2^(n-1) arrangements, and the engine walks all of them before reporting no match.

Three properties have to line up for it to blow up:

1. A quantifier (*, +, {2,}) applied to a group.
2. Inside that group, something that is itself variable-length and can match the same characters — another quantifier, or an alternation with overlapping branches like (a|aa)*.
3. An input that fails to match. A successful match usually finds a path early and stops. The dangerous input is the near-miss.

Point 3 is why these survive testing. Every fixture you wrote matches. The attacker sends the one that does not.

Alternation with overlap is the sneakier version — (\w|\d)+$ looks harmless, but \d is a subset of \w, so every digit gives the engine two ways to match it.

What to do

Spot it first

Search your codebase for a quantifier immediately following a closing paren: )*, )+, ){. That is a small list in most projects, and each one deserves thirty seconds of thought about whether the group’s contents are also variable-length. Paste the suspicious ones into a regex tester with a near-miss input — a long run of the character class followed by one character that breaks the match — and see if it returns.

Fix the pattern

Usually the nesting is redundant. (a+)+ and a+ match the same language; the outer quantifier only adds ambiguity. Rewriting to make each character matchable exactly one way removes the exponent:

// Ambiguous: [^,]+ and the trailing , can both be reached many ways
/^(\s*[^,]+,)*\s*[^,]+$/

// Unambiguous: split first, validate fields separately
line.split(',').every((f) => /^\s*[^,]+$/.test(f.trim()))

Splitting on a literal and validating the pieces is almost always faster and always linear. Reach for it before you reach for a cleverer regex.

Bound the input

If a pattern runs on user input, cap the length before it reaches the regex. This is a one-line change and it converts an unbounded exponent into a bounded constant:

if (input.length > 512) return false
return PATTERN.test(input)

It is a blunt fix, not a correct one — pick the cap from what the field legitimately holds, and treat it as a backstop for patterns you have also cleaned up.

Use the engine’s escape hatch

What is available depends entirely on your runtime:

Two things fall out of that table. Go and Rust bought their safety by dropping backreferences and lookaround — those features are what make linear matching impossible, which is also why V8’s l flag throws at construction when a pattern uses them. And JavaScript is the weakest position on the list: no timeout, no atomic groups, no standard opt-out. If you are matching untrusted input in Node and cannot restructure the pattern, a linear-engine binding such as RE2 is the real answer.

Possessive quantifiers and atomic groups, where you have them, are the surgical fix: (?>\s*\w+)* tells the engine that once the group has matched, it may not give those characters back. That kills the re-partitioning without changing what the pattern accepts, in the cases where giving characters back was never going to help.

Caveats

• Not every nested quantifier is exponential. (ab)+ is fine — the group is fixed-length, so there is only one way to consume each pair. The danger needs ambiguity, not just nesting.
• Polynomial blowup exists too and is easier to miss. \s*$ scanned repeatedly over a long line can be quadratic without ever looking exponential. It will not hang forever; it will just make one endpoint mysteriously slow under load.
• Input caps do not fix the pattern. They cap the damage. A 512-character cap on a quadratic pattern is fine; on an exponential one, 512 characters is still far past hanging.
• A regex tester proves presence, not absence. If your near-miss input returns fast, that particular input is fine. Deciding a pattern is safe for all inputs is static analysis, and tools that attempt it (linters with ReDoS rules) report both false positives and false negatives.
• This is about untrusted input. A pattern that only ever sees your own build-time constants is not a denial-of-service vector, however ugly it is.

References

• OWASP — Regular expression Denial of Service (ReDoS)
• Cloudflare — Details of the Cloudflare outage on July 2, 2019
• V8 — An additional non-backtracking RegExp engine
• .NET — Best practices for regular expressions
• Python 3.11 release notes — atomic grouping and possessive quantifiers
• PHP manual — PCRE runtime configuration (pcre.backtrack_limit)
• Go — regexp package documentation
• Rust — the regex crate
• google/re2 — a linear-time regular expression engine

────────────────────────────────────────