A nested-quantifier regex went from 46ms to 31.6 seconds as input length grew from 20 to 32 characters
The safe rewrite stayed under 0.2ms at every length I tested, no slowdown at all
At 34 characters the vulnerable pattern didn't return within 2 minutes, so I killed the process
The fix is almost always the same: stop nesting quantifiers, let one quantifier own each repeated piece
Everyone who's heard of ReDoS knows the warning: a badly written regex can hang. Fewer people have actually watched the timing curve, so I wrote one vulnerable pattern, one safe rewrite, and ran both against inputs that grow two characters at a time.
The numbers are below, and they're worse than I expected going in.
What Catastrophic Backtracking Actually Is
Take this regex: ^(a+)+$. It matches one or more "a" characters, repeated one or more times, anchored to the whole string. Against a clean match like "aaaa" it's instant. Against "aaaa!", a string that almost matches but fails at the last character, it's a different story.
The engine doesn't know in advance that the string will fail. So it tries every way the inner a+ and outer + could have split up the "a" characters before giving up. For a run of n characters, there are roughly 2^n ways to group them between the two quantifiers, and the engine walks through a huge share of those groupings before it can be sure none of them lead to a match. That's catastrophic backtracking: exponential work hiding behind four characters of regex syntax.
Here's the exact pair I tested, nothing clever on either side:
const vulnerable = /^(a+)+$/;
const safe = /^a+$/;
The safe version drops the outer group entirely. One quantifier, one job. It matches exactly the same set of strings as the vulnerable one for any input that's pure "a" characters, which is the whole point: the nesting wasn't adding matching power, it was adding backtracking paths.
I ran both against a string of "a" characters with a trailing "!" to force a full failed match, since a failed match is what makes the engine search every grouping before giving up. A successful match on the vulnerable pattern can short-circuit early and never shows the problem.
That last point trips people up more than the regex syntax does. If your own testing only ever feeds the pattern strings that actually match, you'll never see this. The failure case, something that's almost right but not quite, is the one that triggers the worst behavior, and it's also exactly the shape of input a sloppy form field or a malicious request tends to send. A username validator gets "normaluser123" all day in testing and "normaluser123" followed by forty junk characters the one time someone's trying to break it.
The Numbers: 20 to 32 Characters
I measured both patterns in Node 22, timing each call with process.hrtime.bigint(), the same high-resolution timer I used to count debounce and throttle calls, so the numbers aren't rounded to the millisecond. Here's what came back:
| Input length | Vulnerable regex | Safe regex |
|---|---|---|
| 20 | 46.3ms | 0.11ms |
| 22 | 29.0ms | 0.07ms |
| 24 | 116.1ms | 0.005ms |
| 26 | 530.7ms | 0.005ms |
| 28 | 2,009.2ms | 0.006ms |
| 30 | 7,705.6ms | 0.007ms |
| 32 | 31,633.0ms | 0.007ms |
Read the right column first, because it's the boring one and that's the point. The safe regex doesn't care how long the input is. Every single measurement sits under a fifth of a millisecond, and the small jitter between runs is noise from the JavaScript engine warming up, not the regex doing more work.
The left column is the one that should worry you. Going from 20 to 32 characters, just 12 more "a"s, the vulnerable regex went from 46 milliseconds to over 31 seconds. I queued up 34 characters next and it didn't return within 2 minutes, so I killed the process rather than find out how long it actually takes. That's not a slow query. That's a single regex call that can turn a form field, a URL path, or a log line into a denial of service, and the attacker doesn't need anything exotic, just a string a few characters longer than whatever you tested with.
Why Doubling Two Characters Roughly Quadruples the Time
The pattern in that table isn't random. Each step adds 2 characters, and the runtime roughly multiplies by 4 each time: 46 to 116 is about 2.5x, 530 to 2009 is about 3.8x, 7705 to 31633 is about 4.1x. That's consistent with the 2^n backtracking paths I mentioned earlier. Adding 2 characters to the input roughly doubles twice, since each new character can slot into the grouping in roughly twice as many places as before, and the ratio climbs closer to a clean 4x as the input grows and the smaller-order effects wash out.
This is why ReDoS bugs are so easy to miss in testing and so easy to hit in production. If your test suite uses short strings, say under 15 characters, the vulnerable pattern looks completely fine. I found a similar cliff in Node's call stack depth: everything is smooth until a specific point, and past it the cost stops looking linear at all. A regex that takes 2 milliseconds on your test fixture can take half a minute on a user-submitted string that's barely longer, and the only difference is a length nobody thought to test.
That also means fuzzing with length matters more than fuzzing with variety here. If you want to catch this class of bug before a user does, throw the same pattern at your regex with inputs at 10, 20, 30 and 40 characters, almost-matching rather than matching, and watch whether the timing curve stays flat or takes off. A flat curve across a few different lengths is a much stronger signal than a single passing test at one length.
Finding and Fixing Vulnerable Patterns in Your Own Code
The shape to look for is a quantifier wrapped around a group that itself ends in a quantifier: (a+)+, (a*)*, (a+)*, and the alternation version, (a|a)+, where the same character can match through more than one branch. Each of those lets the engine attribute the same input character to the inner or outer repetition in more than one way, and that ambiguity is exactly what creates the exponential blowup.
The rewrite is almost always the same move I used above: collapse it to one quantifier that owns the repeated piece. (a+)+ becomes a+. (\w+\s)* protecting a sentence usually becomes (?:\w+\s)* with the inner group made non-capturing and non-nested, or rewritten entirely with a single quantified character class. The general rule is that a well-written regex should have exactly one quantifier responsible for any given stretch of the input, never two quantifiers that could both claim it.
A plain code review catches the obvious cases, nested parentheses followed by a plus or star inside another plus or star. For anything less obvious, npm install safe-regex gives you a quick static check: it flags patterns that look like they could backtrack badly without you having to run them. It's not perfect, a regex can be exponential in ways the heuristic misses, but it catches the common nested-quantifier shape in seconds and belongs in a pre-commit hook for anything that builds regexes from user-configurable input.
Email validation is where I see this most often, because people keep reaching for a hand-rolled pattern instead of the built-in one. A regex like ^([a-zA-Z0-9_.+-]+)+@ nests a plus inside a plus for no reason: the outer group adds nothing a single character class with one quantifier couldn't do on its own. Drop the outer parentheses and the outer plus, and the match stays identical while the backtracking risk disappears completely. The same goes for date and path validators built out of alternation, where two branches can both match the same character. If branch A and branch B of an alternation can both consume the letter "a", you've got the same ambiguity problem wearing a different syntax.
If you can't rewrite a pattern and you're stuck with something third-party, wrap the match in a timeout instead of trusting it. Node doesn't support a timeout on RegExp.test directly, but running it inside a worker thread with a hard kill after, say, 200 milliseconds turns a hang into a rejected request instead of a frozen process. That's a safety net, not a fix, and I'd only reach for it when the regex itself is out of my control, like validating input against a pattern a user or a plugin supplied.
Worth saying plainly: this is a real denial-of-service vector, not an academic edge case. A single request carrying a string a few characters longer than your test data can pin a CPU core at 100 percent for as long as the regex takes to give up, and depending on how your server handles concurrency, that one request can block every other request waiting behind it. The fix costs nothing in matching power. There's no reason to leave it unfixed once you've found it.
Bottom Line
The safe rewrite in this test did the exact same job as the vulnerable one, matched the exact same strings, and never took more than 0.11 milliseconds no matter how long the input got. There's no tradeoff here worth keeping the nested version around for.
If you've got regexes validating anything a user can submit, a username, a path, an email, spend ten minutes grepping for a quantifier wrapped around another quantifier. Then run the pattern against inputs at a few different lengths and watch whether the timing curve stays flat. If it climbs the way mine did, from 46 milliseconds to 31 seconds in six steps, you've found a denial-of-service bug before someone else finds it for you, and the fix is usually one character shorter than the bug.
What's the longest input your validation has actually been tested against, and is it longer than what a real user would ever type?
Top comments (0)