Why Is My Regex So Slow? Catastrophic Backtracking and ReDoS

You have a regex that works. It passes every test you threw at it, it ships, and for weeks nobody notices anything wrong. Then one day a slightly longer input comes through — a pasted paragraph, a malformed URL, a log line with a long run of spaces — and the tab locks up. The CPU pins to 100%. On a server, the whole Node.js process stops answering requests. Nothing threw an error; the regex is still, technically, correct. It just never finished.

Let’s be precise about which kind of “slow” this is, because not every slow regex is the same animal. Some are merely polynomial — quadratic, say, so twice the input is roughly four times the work, annoying but survivable. Some are only slow because the input is genuinely huge, or because you’re calling the regex in a tight loop. This article isn’t about those; those are ordinary optimization. It’s about the categorically nastier class where a small bump in input length makes the running time explode: the work grows exponentially, so adding a handful of characters turns microseconds into minutes into never. That has a name — catastrophic backtracking — and when an attacker feeds you that input on purpose to take your service down, it’s called a ReDoS (Regular expression Denial of Service) attack.

The good news is that this isn’t mysterious. It falls straight out of how a backtracking engine works, which the first article in this series walked through in detail. If you understand that the engine eats greedily and backtracks when it gets stuck, catastrophic backtracking is just that same mechanism running out of control. This article picks up exactly there: what makes the work explode, how to recognize the dangerous shapes on sight, where they hide in real code, and — since JavaScript gives you almost no built-in guardrails — how to rewrite your way out.

Where the explosion comes from

Here’s the engine model from the first article, compressed to a sentence: a backtracking engine, when a greedy quantifier can’t complete the match, rewinds and tries a different split — it hands characters back and looks for another way forward, giving up only once it has exhausted every possibility. Catastrophic backtracking is what happens when “every possibility” turns out to be an astronomically large number.

The textbook trigger is a nested quantifier — a repeating group that itself repeats:

(a+)+$

Read literally, it’s redundant. “One or more runs of one-or-more a’s, anchored to the end of the string” describes the exact same set of strings as a plain a+$. But the engine doesn’t know the two are equivalent, and that redundancy is precisely what sinks it: the inner a+ and the outer + can both lay claim to the same a’s, so a run of a’s can be carved into groups in more than one way — and the engine feels obligated to try all of them before it will admit defeat.

Watch it happen on just aaaX, four characters. The engine’s opening move is the greedy one: the inner a+ swallows all three a’s as a single group, (aaa). Now it wants $, but the cursor is parked on X — fail. So it backtracks. The inner a+ gives one a back, leaving (aa); the outer + seizes the chance to open a second group, and the inner a+ grabs the leftover, producing (aa)(a); try $, still X, fail. Backtrack again: (a)(aa), fail; (a)(a)(a), fail. Only after all four ways of grouping three a’s have been tried and rejected is the engine permitted to give up on this starting position — and shift one character right to begin the whole ordeal over.

Four groupings for three a’s is not a coincidence: a run of n a’s has 2ⁿ⁻¹ ways to be split into ordered groups, and the fatal $ — which can never hold in front of that X — forces the engine to walk every last one before it concedes. Ten a’s is 512 attempts; twenty is over half a million; thirty is more than half a billion. That’s why the freeze isn’t gradual but sudden: each a you add roughly doubles the work. The pattern isn’t slow, it’s exponential — and an exponential curve looks flat right up until the moment it goes vertical.

Don’t bother hunting for the exact length that tips it over; that shifts with your browser, your hardware, and the engine build. What matters is the shape of the curve — and one more property that turns a performance quirk into a weapon: the pathological case is the failing case. A pattern like this looks perfectly fast in testing, because the inputs you test with match quickly and cheaply. It’s the near-misses — input that matches almost all the way and then fails at the very last step — that drag the engine through the full exponential search. Attackers know this, which is why a ReDoS payload is engineered to almost match: a long run of a’s, then the one character that dashes it at the end.

The dangerous shapes, on sight

You don’t need to trace the engine every time — dangerous patterns have a small number of recognizable silhouettes. But it pays to be precise about how dangerous, because two very different cost curves get lumped together under “ReDoS,” and only one of them is the true bomb.

The exponential shapes — the real bombs. These are the ones where the cost roughly doubles with each added character, exactly as traced above. The signature is repetition stacked on repetition where both layers can match the same characters, so a single run can be partitioned an exponential number of ways:

(a+)+$       (a*)*$       (\w+)*$       ([\w.]+)+@

Overlapping alternation under a quantifier is the same disease in a different skin: when two branches can match the same text, each character has more than one route, and the quantifier multiplies them out.

(a|a)*$      (\w|\d)*$

\d is a subset of \w, so (\w|\d)* has two ways to match every digit — against a long digit string that ultimately fails, that’s 2ⁿ paths. (The branches have to overlap on the same characters. (a|ab)*, whose branches consume different lengths, is a subtler, usually polynomial case — not a guaranteed bomb.)

The polynomial shapes — slow, occasionally exploitable. Adjacent unbounded quantifiers, or a broad .* hunting for something that isn’t there, don’t detonate exponentially — but they can still burn O(n²) or worse and hang on large enough input:

.*.*=        \s*.*\s*$        a.*b.*c

These deserve a fix too, but they’re a different severity class. Knowing the line keeps you from crying “exponential” at every .*.

Lazy doesn’t defuse any of this. “Switch greedy to lazy” gets handed around as a performance fix; it isn’t one. Laziness only flips the order the engine tries splits — shortest-first instead of longest-first — and on a failing match it still visits all of them. (a+?)+$ is exactly as exponential as (a+)+$. Don’t mistake *? for a safety feature.

One caveat governs both tiers: a dangerous shape only actually bites on a failing match. Whether it’s exploitable depends on there being an input that forces the full search — usually a long repeated prefix followed by a character that defeats an anchor or a required suffix — and on how long an attacker can make that input. Shape tells you the risk exists; the failing path and the input length tell you how bad it gets.

If you want to feel the difference, drop these into the regex tester and let its ReDoS analysis weigh in — it runs in the background and flags a vulnerable shape for you. What you should not do is paste in a long attack string just to watch the page freeze: matching runs on the browser’s main thread, so all you’d accomplish is hanging your own tab to prove a point the analyzer already made.

Where it actually hides

Nobody writes (a+)+$ in production on purpose. Catastrophic backtracking gets shipped because it hides inside patterns that look completely reasonable — and specifically inside validators, the regexes we point at untrusted user input, which is precisely the worst place for it.

Email and URL validation. Hand-rolled address validators sit behind a long list of real ReDoS CVEs, and the vulnerable ones share a shape: a repeated group whose contents overlap with the repetition wrapped around it. Take a local-part check written as ^([a-zA-Z0-9]+[._-]?)+@. It reads as careful — “letters and digits, an optional separator, repeated.” But feed it a long run of letters with no separator and no @, and the optional [._-]? matches empty on every pass, collapsing the whole thing into ([a-zA-Z0-9]+)+ — the exponential shape from above, just wearing a disguise. (Note that the deliberately-benign-looking ^([a-zA-Z0-9]+\.)+[a-zA-Z]{2,}$ is not this bug: its inner class can’t match the ., and each outer repetition must consume a literal ., so there’s no way to re-partition the same characters. The overlap is what matters, not the mere presence of a nested +.)

Repeated-whitespace patterns. Here it’s worth slowing down, because a scary-looking trim is usually fine. The everyday ^\s+|\s+$ is not a ReDoS risk — it’s two simple anchored runs, no nesting and no overlap, so keep using it. The danger is the nested form: (\s+)+, (\s*)*, or (\s|\t)+ under an outer quantifier, which reintroduces the overlap. Since whitespace normalization tends to run on everything a user submits, a nested one is a prime target — but don’t go deleting ordinary trims in a panic.

Anything with (.*,)* or repeated groups — parsing a comma-separated list, a series of key-value pairs, repeated HTML attributes, a path with repeated segments. The moment you write “one-or-more of (something that itself contains one-or-more),” stop and check the one thing that decides it: can the inner and outer parts consume the same characters? If each repetition is pinned to its own separator, or the input can’t grow long, the worst case is a performance cost worth measuring — not a bomb. It’s a genuine ReDoS candidate only when the overlap is real and a long failing input is possible.

The pattern behind the pattern: the regexes most likely to contain a backtracking bomb are exactly the ones you run against untrusted input, because validators are where nested quantifiers naturally arise. That overlap between “vulnerable shape” and “attacker-controlled input” is the entire ReDoS threat.

Fixing it: rewrite, because JavaScript won’t save you

Some regex engines hand you a direct off switch for backtracking. Atomic groups (?>...) tell the engine “once you’ve matched this, never give it back,” and possessive quantifiers a++, a*+ do the same for a single quantifier. Point them at the ambiguous part and the exponential search is locked out at the source.

Here’s the hard limit worth burning into memory: JavaScript has neither. No atomic groups, no possessive quantifiers, to this day. (Java, PCRE, Ruby, and .NET all have them; JS is the notable holdout.) So in JavaScript the only lever you have is to rewrite the pattern so the ambiguity never exists — remove the overlap, and there’s nothing to backtrack through. Here’s the toolbox, roughly in order of how often it’s the answer:

1. Use a negated character class instead of .* or .*?. This is the single highest-value fix, and it’s the one the first article kept foreshadowing. [^"]* can’t cross a quote, so when you write "[^"]*" there’s exactly one way to match the contents — no probing back and forth. Compare ".*" (over-greedy: the .* eats the closing quote and has to give it back — a small, linear bit of backtracking, not a catastrophe on its own) with "[^"]*" (unambiguous, hard boundary). On its own the win is precision and correctness; the payoff for this article is that a hard boundary can’t form the kind of overlap that turns exponential once the construct is nested inside another quantifier. Whenever you can name the character that ends a run, match “anything but that character” instead of “anything, lazily.”

".*?"    →    "[^"]*"
\w+@.*   →    \w+@[^\s@]+

That second example isn’t a blind equivalence — \w+@.* and \w+@[^\s@]+ don’t match the same thing. [^\s@]+ deliberately narrows the tail to “a domain part with no spaces and no second @,” which is usually what you actually meant. Pick the negated set to fit your real intent, not just to dodge backtracking.

2. Make alternation branches mutually exclusive. If your alternatives overlap, restructure so each character has exactly one branch that can match it. (\w|\d)* becomes just \w* (since \d was already inside \w). Overlap is the enemy; eliminate it.

3. Anchor to cut down start positions — but know the limit. Adding ^/$ or a concrete delimiter between repeated groups stops the engine from retrying the whole match at every start position, which removes the outer linear or polynomial factor. What it does not do is defuse an inner exponential blowup — (a+)+$ is already anchored, and that $ is the very thing forcing the exponential failure. Anchoring helps the polynomial cases; it is not a cure for a nested-overlap bomb.

4. Bound the input as defense-in-depth, not as the fix. A hard length cap at the business layer — reject inputs over n characters before the regex ever sees them — is genuinely worth having, and {1,64} instead of + puts a ceiling on nesting depth. But don’t mistake a bound for removing the vulnerability: {1,64} still permits up to 2⁶⁴ paths, which is astronomically unrunnable. Bounds contain the blast radius; eliminating the overlap is what actually removes the bomb.

5. Stop using a regex. Some jobs — nested structures, anything resembling a real grammar, parsing HTML or JSON — are not regular languages, and forcing a regex onto them is how you end up with these monsters in the first place. A hand-written loop over the string, a String.split on a plain string delimiter (not split(/regex/), which still runs a regex), or a real parser is often simpler, faster, and immune to this whole class of bug.

After every rewrite, confirm two things: it still matches everything it’s supposed to (regressions love to hide in “safer” rewrites), and it no longer trips the ReDoS check. Both are a paste away in the regex tester — put the old pattern and the new one side by side against the same near-miss input.

The security angle: why this is a DoS, not just a bug

It’s worth stating plainly why catastrophic backtracking graduates from “performance nuisance” to “security vulnerability,” because the leap is specific to how servers run.

Node.js executes JavaScript on a single thread. When a regex enters catastrophic backtracking, that thread is captured completely — it isn’t yielding, it isn’t handling other requests, it’s spinning inside the regex engine. So one crafted input doesn’t just slow down the request that carried it; it freezes that whole process for every user it’s serving. And here’s the barb: a request-timeout you set with setTimeout can’t rescue you, because the timer callback can only fire once the event loop is free — and the runaway regex is precisely what’s holding the event loop hostage. Node can’t interrupt a synchronous regex that’s already running; the captured thread stays captured until the match finishes on its own, which may be effectively never.

How far that blast spreads depends on your deployment: a single-process server goes fully dark, while multiple processes or worker threads, a gateway-level timeout that drops the connection, and rate limiting all shrink the radius. But the core asymmetry survives all of that — trivial cost to attack, disproportionate cost to absorb — which is why ReDoS shows up so regularly in CVE reports against popular libraries.

This also explains a puzzle the first article flagged: why the same dangerous pattern runs instantly under ripgrep but hangs Node. Tools like ripgrep (Rust’s regex crate) and Go’s regexp are built on finite automata, a different engine architecture that turns matching into a single linear scan with no backtracking at all. They are immune to catastrophic backtracking by construction — the trade-off being that they drop features like backreferences that fundamentally require backtracking. Which engine class you’re running on decides whether this threat even applies to you. On the backtracking engines — JavaScript, Python, PCRE, Java — it very much does.

There’s a practical corollary here for Node specifically. When a pattern genuinely can’t be rewritten safely — or you simply don’t trust yourself to get every one right by hand — you can run it on a linear engine instead of the built-in one. Google’s RE2 is a finite-automata engine with exactly that linear guarantee, and the re2 npm binding is a near drop-in for RegExp in Node. The price is the features that fundamentally need backtracking: RE2 supports no look-around at all — neither lookahead nor lookbehind — and no backreferences. In exchange, match time grows linearly with the input length (a more complex pattern just means a larger constant factor), never exponentially, no matter what an attacker feeds it. For a regex that has to run against untrusted data, that’s often the right trade.

Catch it before it ships

The best time to find a backtracking bomb is before it reaches production, and you don’t have to eyeball every pattern by hand. This site’s regex tester runs a ReDoS analysis on your pattern asynchronously: paste the regex in, and it checks for vulnerable structure in the background. When it finds a problem it shows you a concrete attack string — the actual input that would blow the pattern up — so you can see the failure rather than take it on faith. And when the analysis can’t reach a definite verdict, it tells you that too, plainly, instead of pretending everything’s fine. Everything runs locally in your browser; the pattern never leaves the page.

Treat it as a smoke detector, not a certificate. A clean result is a good sign, but it isn’t a proof of safety, and a real performance test at your true input scale is still the final word. What the check buys you is the cheap, early catch — the chance to spot ([a-zA-Z0-9]+[._-]?)+@ for the bomb it is before it’s guarding a login form in production.

A checklist you can actually follow

When a regex hangs, or before you ship one that touches user input, run this:

1. Hangs the moment it runs, CPU pegged? That’s catastrophic backtracking, not ordinary slowness. Don’t optimize around it — the pattern is exponential and needs rewriting.
2. Scan for the exponential shapes first. (a+)+, (\w+)*, ([\w.]+)+, (a|a)* — repetition stacked on repetition, or overlapping alternation, where both layers grab the same characters. These are the real bombs.
3. Then the polynomial ones. .*.*, \s*.*\s* — adjacent unbounded quantifiers. Slower than they should be and occasionally exploitable, but not the same emergency.
4. Don’t count on lazy. (a+?)+ is as dangerous as (a+)+; *? changes the order of the search, not its size.
5. Look hardest at your validators. Email, URL, and repeated-whitespace patterns are where overlap hides and where untrusted input lands. Confirm the trim you’re worried about is actually nested ((\s+)+), not the harmless ^\s+|\s+$.
6. Fix by removing the overlap, not by patching around it. Prefer a negated character class ([^"]*) over .*?; make alternation branches exclusive; drop the regex for a parser when the job isn’t regular. Anchors and input caps help contain the damage but don’t defuse a nested bomb — and JavaScript has no atomic groups or possessive quantifiers, so the rewrite is the whole game. When you truly can’t rewrite, run it on RE2.
7. Verify the rewrite still matches, then re-check ReDoS. Old and new pattern, side by side, against the near-miss input.

Catastrophic backtracking feels like a dark corner of regex until you see it as the same backtracking engine from the first article doing exactly what it always does — just too many times. Once “eat greedily, backtrack when stuck” is in your bones, the dangerous shapes light up on sight, and the fix is almost always the same quiet move: draw the boundary explicitly, and give the engine nothing to second-guess.