ReDoS in Practice: How One Character Doubles Your Regex Runtime

Take this innocuous-looking pattern, which someone might write to validate "one or more groups of letters":

/^(a+)+$/

Feed it a string it matches and it returns instantly. Feed it a string it almost matches — thirty as followed by one b — and Node 20 on our M2 Pro spends 6.5 seconds rejecting it. Add one more a and it takes 13 seconds. Every single character doubles the runtime. That is catastrophic backtracking, the mechanism behind ReDoS (regular expression denial of service), and this post measures it, explains it, and shows what we changed in our own regex tester because of it.

The measurement

All numbers below are from Node v20.10 on an Apple M2 Pro; the scripts are inline so you can rerun them. First, the exponential case — /^(a+)+$/ against 'a'.repeat(n) + 'b':

for (let n = 24; n <= 30; n++) {
  const input = 'a'.repeat(n) + 'b';
  const t0 = performance.now();
  /^(a+)+$/.test(input);
  console.log(n, (performance.now() - t0).toFixed(1), 'ms');
}

The growth factor is not "roughly" two — it is two, to the second decimal place, seven measurements in a row. Extrapolating the measured doubling: 40 characters would run for about 110 minutes, and 50 characters for about 78 days. An attacker does not need a megabyte of payload; they need a few dozen bytes.

For contrast, the unambiguous pattern that matches exactly the same strings:

/^a+$/.test('a'.repeat(1_000_000) + 'b');  // 1.1 ms

One million characters, one millisecond. The regex engine is not slow. Ambiguity is slow.

Why one character doubles the work

A backtracking engine (which is what JavaScript, Python, Java, and Ruby all use) resolves a failed match by undoing choices and trying alternatives. The pattern (a+)+ gives it choices to undo: a run of five as can be one group of five, five groups of one, a group of two then a group of three… every way of slicing the run into non-empty chunks is a distinct path, and there are 2ⁿ⁻¹ of them.

When the input ends in b, the $ anchor fails — and the engine dutifully walks back through every slicing before giving up. Each extra a doubles the number of slicings, which is exactly the ×2.00 in the table. The fix is to remove the ambiguity, not the regex: (a+)+ describes the same language as a+, which has exactly one way to match any run and fails in linear time.

The same trap wears other costumes: (\w*)*, (.*,)*, (a|ab)+ — anything where a quantified group can match the same text in more than one way, followed by something that can fail.

The quadratic trap is the one that ships

Exponential patterns are dramatic but usually get caught. The pattern that actually reaches production is the quadratic one, because it feels completely harmless. Here is /\s+$/ — "trim trailing whitespace" — against a long run of spaces that does not end the string:

for (const n of [10_000, 20_000, 40_000, 80_000]) {
  const input = ' '.repeat(n) + 'x';
  const t0 = performance.now();
  /\s+$/.test(input);
  console.log(n, (performance.now() - t0).toFixed(1), 'ms');
}

Double the input, quadruple the time — the signature of O(n²). The engine starts a match attempt at the first space, consumes all 80,000, fails at the x, then retries from the second space, and the third… roughly n²/2 character reads in total.

This is not a hypothetical. On July 20, 2016, Stack Overflow went down for 34 minutes because their homepage rendering called a trim regex of exactly this shape on a post containing about 20,000 consecutive whitespace characters. Three years later, on July 2, 2019, Cloudflare's global outage — 27 minutes of 502s across their network — traced back to a WAF rule containing .*(?:.*=.*), whose nested .*s sent CPU usage to 100% on the machines running it. Two of the most engineering-heavy companies on the internet, taken down by a character class and a quantifier.

The boring fix for the trim case, measured on the same 80,000-space string:

input.trimEnd();  // 0.034 ms — over 100,000× faster

How to spot a dangerous pattern

Three questions to ask of any regex that will ever see user-controlled input:

1. Is there a quantifier inside a quantified group — (x+)*, (x*)*, (x+)+? Can the inner and outer quantifier split the same text in more than one way? That is the exponential shape.
2. Can alternation branches match the same text — (a|ab)+, (\d|\w)*? Overlapping branches are nested-quantifier ambiguity in disguise.
3. Can the pattern fail after the ambiguous part? Backtracking only explodes when the engine has a reason to walk back through the choices. ^(a+)+$ explodes on aaab; drop the $ and it returns instantly, because the first greedy attempt succeeds. This is why vulnerable patterns often test fine — the author only tries inputs that match.

A quieter warning sign from question 3: the worst case is always an input that almost matches. Test your validation patterns against near-misses, not just valid and obviously-invalid strings. OWASP's ReDoS page catalogs more of these "evil regex" shapes and their attack payloads if you want further examples.

What JavaScript gives you (and what it doesn't)

Some regex engines have escape hatches. .NET lets you pass a matchTimeout. Rust's regex crate and Google's RE2 refuse backtracking entirely and guarantee linear time — at the cost of dropping backreferences and lookaround, the features that require it. V8 has an experimental non-backtracking engine behind a flag that falls back to the classic engine for those same features.

Standard JavaScript in 2026 has none of this by default: no timeout, no atomic groups, no possessive quantifiers. A synchronous .test() or .match() call holds the thread until it finishes, however long that takes. Your realistic options:

• Rewrite the ambiguity away. (a+)+ → a+; trim with trimEnd(); anchor patterns so failure happens early. This is the real fix — everything else is containment.
• Cap input length before matching. Even a quadratic pattern is fine at 200 characters; our /\s+$/ measurement needed tens of thousands to hurt.
• Make the match killable. On a server, that means a worker thread or the re2 npm binding. In a browser, a Web Worker you can terminate().

That last one is the change we shipped today. Our regex tester used to run your pattern directly on the page's main thread — which meant pasting ^(a+)+$ with a 30-character near-miss froze the tab for six seconds, exactly as the table above predicts, with no way to interrupt it. Matching now runs in a Web Worker with a 2-second deadline; if your pattern blows past it, the worker is terminated and the tester tells you the pattern likely backtracks catastrophically instead of hanging your browser. If you want to see the failure mode safely, that is now the place to try it.

One caveat on the numbers: the doubling behavior and the O(n²) shape are properties of the backtracking algorithm and will reproduce on any hardware — but the absolute milliseconds are specific to Node 20.10 on this machine, and engines do add optimizations over time. Rerun the snippets on your own stack before quoting the exact figures.