ReDoS Protection: Anatomy of (a+)+ and How to Never Ship It

A regex hang is not a slow regex. It is a regex that failed, and the failure cost exponential time. That distinction drives everything below: the bug hides from your passing tests and ambushes the one input that doesn't match. Every timing in this page is measured on this box (Node v24.21.0, warmed with 50 priming iterations so the JIT stops lying). Reproduce them yourself in the tester before trusting any pattern you paste into a request handler.

Anatomy: why (a+)+ explodes

The pattern /^(a+)+$/ against 'a'.repeat(n) + '!':

1. (a+) enters, inner a+ greedily eats all n a's.
2. + loops: inner a+ tries again, fails (we're at !) — iteration of the group ends.
3. $ fails — we're sitting on !.
4. Backtrack. The engine now re-partitions the a-run every way the grammar allows: the outer + deciding how many group-iterations, each iteration's a+ deciding its length. For n a's, that's every composition of n — roughly 2^(n-1) ways to fail.
5. All of them fail. Each one costs a backtrack step.

n=20  reject=false   66.7ms
n=24  reject=false  231.7ms
n=26  reject=false  889.1ms
n=28  reject=false  3550.1ms
n=30  reject=false 14219.0ms

Read that table as the whole attack: each +2 characters costs ~4x the time (two doublings). n=30 is 14 seconds; n=40 is hours. Same pattern, matching input ('a'.repeat(300), no !): 0.0ms — greedy first pass succeeds and the engine never visits the exponential region. This is why the bug ships: your unit test uses a valid string.

Same family, /^(\w+\s?)+$/ — the canonical "words and spaces" validator, and a staple of Stack Overflow answers:

n=24 reject=false   225.3ms
n=26 reject=false   899.1ms
n=30 reject=false 14375.3ms

Thirty word characters is free to type and fourteen seconds to reject. If that regex sits behind any user-controlled field — username, comment, search query — you have a one-request downtime, no botnet required.

The alternation-overlap family: (?:x|xx)+

Same disease, different vector: the branches overlap in length, so the same end position is reachable through exponentially many branch sequences (Fibonacci-shaped, less savage):

n=28 reject=false    7.7ms
n=30 reject=false   20.3ms
n=32 reject=false   49.4ms
n=34 reject=false  125.7ms
n=36 reject=false  346.4ms

Slower curve, same arrow. The (a|aa)* and (a{1,3})+ shapes are the same family — and the last one is the tell: bounded inner quantifiers ((a{1,3}){1,10} on a 3000-char reject: 0.8ms) cap the search space. Unbounded nested quantifiers are the crime; nested-ness plus overlap is the indictment.

Why JS and PCRE2 blow up but RE2 cannot

Backtracking engines (V8/JS, PCRE2, Python's re, .NET) search a tree of paths depth-first, revisiting state on failure — that's what buys backreferences, lookahead, \K, and the exponential worst case. Thompson-style DFA engines (RE2, Go's regexp, Rust's regex crate) simulate all matching positions simultaneously, once per character — the state set is bounded by pattern size, so matching is O(n·m) provably, and the tree is never enumerated. Cost of the deal: no backreferences, no lookaround, and the engine rejects at compile time rather than pretending.

Nuance worth stating once: RE2's implementation can still be superlinear in practice (unanchored scans multiply by n), but it cannot produce 2^n — polynomial stays polynomial. For ReDoS purposes the asymmetry is total: backtracking engines have an exponential failure mode, RE2-class engines do not.

Practical corollaries: the u flag doesn't help (semantics, not algorithm). Anchors don't help — ^...$ still backtracks internally (the table above was fully anchored). Lazy quantifiers don't help: /^(a+?)+?$/ on the n=24 reject took 947ms in the same run, worse than greedy. Timeouts (worker threads + kill, re2 bindings, RE2-service sidecars) are damage control; the fix is the pattern.

Rewrites that make it linear

Rule: quantified groups must be disjoint at every repetition. For every nested/unbounded quantifier ask "can one iteration's end look like the start of the next?" If yes, flatten it:

Verified: /^\w+(?:\s\w+)*$/ on a 2000-char reject — 0.1ms (vs. unbounded n=30 at 14s). The rewrites are mechanical once you spot the family: name the run, mandate the separator, repeat the pair. Full vocabulary in best practices.

Where your engine has atomic groups or possessive quantifiers (PCRE2: (?>a+), a++ — both verified via grep -P, see the engine matrix), you can keep the pattern's shape and forbid the re-partitioning. JavaScript has neither — /a++/ throws Nothing to repeat, /(?>a)/ throws Invalid group, even under v — so in JS the rewrite is the fix. No rewrites in your control (third-party patterns, user-authored filters)? That's the RE2 row.

Measuring locally before you ship

1. The tester: paste the pattern, paste ALPHABET.repeat(30) + '!' — alphabet taken from the pattern's own character classes — then 34 and 38. Timing roughly quadruples per +2? You have exponential. The tester shows elapsed ms live; a linear pattern idles under a millisecond at n=3000.
2. CI gate, timing form: assert performance.now() delta < 100ms for reject inputs at n=30 and n=38, per pattern, on the CI box's clock. Reject-input only — matching inputs prove nothing (see the 0.0ms line above).
3. CI gate, compile form: pipe every user-suppliable pattern through an RE2 compiler at PR time; whatever fails to compile (\1, lookaround) fails at runtime on your RE2 backend anyway — better to learn in CI. Linters (safe-regex, ESLint no-redos) catch the classic shapes; the timing test catches what linters miss.

When you can't rewrite: the RE2 escape hatch

Swap the engine for untrusted patterns: Go's regexp, Rust's regex crate, re2 bindings or a RE2 sidecar for Node/Python. Linear-by-construction kills the class of bug, not the instance. Caveats: no backreferences, no lookaround, no \K, and leftmost-longest semantics differ from Perl-family leftmost-first — verified on this box: grep -oE 'go|gopher' on gopher returns gopher, grep -oP returns go. Patterns needing the missing features stay on the backtracking engine behind a worker-thread timeout: the standard two-tier design. Engine-by-engine tradeoffs are in regex alternatives.

FAQ

Is ReDoS the same as "slow regex"? No. Slow is linear-with-a-fat-pattern. ReDoS is exponential worst case from unbounded re-partitioning. One you fix with anchoring and factoring; the other structurally or by engine choice.

Does a request timeout make me safe? It bounds the damage, not the shape: the worker/child dies, but n concurrent 30-character inputs are n pinned threads — that's an availability incident with your logo on it. Timeout is the seatbelt; the rewrite/RE2 is the driver.

Does V8's regex IR or the v flag fix this? Both are optimizations/semantics inside a backtracking architecture — measured here: same exponential curve on Node 24. The failure mode is the algorithm, not the implementation.

Give me the one-line rule. No unbounded quantifier inside another unbounded quantifier unless the repetitions are provably disjoint — everything else in this page is that sentence with receipts.