The Innocent Pattern That Freezes Your Server
A regular expression is usually one of the cheapest operations in your code. Yet a single carelessly written pattern can take seconds, minutes, or effectively forever to evaluate a short string — and an attacker who discovers it can lock up an entire request thread with one HTTP call. This failure mode is called catastrophic backtracking, and when it is exploitable it becomes a Regular Expression Denial of Service (ReDoS). This article explains the mechanism precisely, shows you how to recognise dangerous patterns, and gives you concrete rewrites you can validate in our Regex Tester.
If you have read our complete guide to regex syntax, you already know that quantifiers are greedy by default and that the engine backtracks when a match fails. ReDoS is what happens when that backtracking explodes combinatorially.
How Backtracking Actually Works
Most mainstream regex engines — including the one in JavaScript (ECMAScript), Java's java.util.regex, Python's re, and PCRE — use a backtracking algorithm rather than a finite-automaton approach. When a greedy quantifier consumes too much and the rest of the pattern cannot match, the engine gives characters back one at a time and retries. For a simple pattern this is cheap. The danger appears when the engine has many different ways to split the same input between two overlapping quantifiers, because it may try all of them before concluding that no match exists.
The classic textbook trigger is a quantifier applied to a group that itself contains a quantifier, where both can match the same characters. Consider (a+)+$ tested against a string of many a characters followed by a single !. The outer and inner + can partition the run of as in an exponential number of ways. Each partition is a distinct path the engine must explore before the trailing $ finally fails on the !. The work grows on the order of 2 raised to the input length — twenty-five characters can already mean tens of millions of steps.
The Three Shapes of Danger
Catastrophic backtracking almost always comes from one of three recognisable structures. Learning to see them by eye is the single most valuable skill here.
Nested quantifiers
A quantifier wrapping a group that contains another quantifier over an overlapping character set: (a+)+, (\d+)*, (a*)*, ([a-z]+)+. Because the inner and outer repetition can both consume the same characters, the number of ways to divide the input is exponential.
Quantified alternation with overlap
An alternation inside a quantifier whose branches can match the same text: (a|a)*, (\w|\d)*, (.|\s)*. Here \w already includes \d, so for every digit the engine has two equally valid choices, doubling the search space at each step.
Adjacent quantifiers competing for the same characters
Two quantifiers in sequence over the same class, joined by an anchor or literal that can fail: \d+\d+$ or the more subtle .*.*=.*. When the final constraint fails, the engine redistributes characters between the two greedy parts in quadratically or exponentially many combinations.
A Worked Example You Can Feel
Open the Regex Tester and try ^(\w+\s?)*$ — a pattern that looks like a perfectly reasonable "words separated by optional spaces" validator. Against a clean input like hello world it matches instantly. Now feed it a string of thirty word characters followed by a single space and an exclamation mark, for example aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa !. The trailing ! cannot be part of a word and is not whitespace, so $ fails — and the engine grinds through an astronomical number of ways to split those thirty characters between the inner \w+ and the outer *. The pattern that ran in microseconds now hangs.
This is exactly why the OWASP project maintains a dedicated page on Regular Expression Denial of Service, and why the Common Weakness Enumeration catalogues it as CWE-1333: Inefficient Regular Expression Complexity. The root cause is never the input size — it is the structure of the pattern.
Why This Is a Security Problem, Not Just a Performance Bug
In a single-threaded event loop like Node.js, regular expression evaluation is synchronous and blocks everything. While one request is stuck in catastrophic backtracking, no other request on that process can be served — health checks fail, the load balancer may mark the instance dead, and a single crafted string becomes a full denial of service. This is not theoretical. The Cloudflare outage of 2 July 2019 was caused by a regular expression in their WAF containing .*.*=.*, which backtracked catastrophically and drove global CPU to 100 percent. The Stack Overflow outage of 20 July 2016 was traced to a pattern matching trailing whitespace on a long line.
Because user input frequently flows into regex — validating emails, parsing User-Agent headers, sanitising markup, checking JSON values pulled from our JSON Formatter workflow — any pattern that touches untrusted data must be assumed reachable by an attacker.
How to Detect Vulnerable Patterns
Detection works on three levels, and you should use all three.
- Read for the three shapes. Scan every pattern for nested quantifiers, quantified overlapping alternation, and adjacent same-class quantifiers. If you see
(X+)+,(X*)*, or(X|Y)*where X and Y overlap, treat it as guilty until proven innocent. - Test with an adversarial string. Build the worst case deliberately — a long run of the character the inner quantifier accepts, ending in a character that forces the final anchor or literal to fail. Paste it into the Regex Tester and watch whether matching stays instant. A modern tester that warns on long evaluation time turns this into a one-second check.
- Run a static analyser. Tools such as the
eslint-plugin-redosESLint rule, the open-sourcerecheckengine, and thesafe-regexheuristic flag dangerous structures at lint time. They are imperfect — heuristics produce false negatives — but they catch the obvious cases automatically across a whole codebase.
How to Fix It
There is no single fix; there is a toolbox. Choose by what the pattern is actually trying to express.
Make the overlap impossible
The cleanest fix removes the ambiguity that lets the engine choose. The vulnerable ^(\w+\s?)*$ exists to match words separated by whitespace, so express that directly with non-overlapping pieces: ^\w+(?:\s+\w+)*$. Now each character belongs to exactly one part of the pattern — there is no way to redistribute it, so backtracking cannot explode. This single-path rewrite is the most reliable technique and should be your default.
Anchor the inner repetition
Replace a permissive class with a more specific one so the inner quantifier cannot consume the delimiter. If you are matching quoted strings, do not write ".*" — write "[^"]*", which stops the inner match at the closing quote and removes all ambiguity about where the string ends.
Use atomic groups or possessive quantifiers
Engines that support them — PCRE, Java, Ruby, and .NET — offer atomic groups (?>…) and possessive quantifiers a++, a*+. These tell the engine to commit to a match and never give characters back, which eliminates the backtracking entirely. JavaScript historically lacked them, but the TC39 regular-expression modifiers and the wider adoption of these constructs mean you should reach for them when your engine allows. Where they are unavailable, simulate atomicity with a lookahead-plus-backreference idiom: (?=(a+))\1.
Bound the input and the repetition
Defence in depth helps even after a structural fix. Reject overlong inputs before they reach the regex, and prefer bounded quantifiers like {1,64} over open-ended + where the domain allows. A length cap turns a potential exponential blowup into a merely large constant.
Switch to a linear-time engine
The most durable answer is to stop using a backtracking engine for untrusted input at all. Engines built on Thompson NFA simulation — Google's RE2, Rust's regex crate, and Go's standard regexp package — guarantee evaluation in time linear in the input length, with no backtracking and therefore no catastrophic case. They deliberately omit backreferences and lookaround, the very features that force backtracking, which is a trade most validation code can accept gladly.
A Checklist Before You Ship a Pattern
- Does any quantifier wrap a group containing another quantifier over an overlapping class? Rewrite to a single path.
- Does an alternation inside a quantifier have branches that match the same characters? Collapse or disjoin them.
- Will this pattern ever run on untrusted input? If so, cap the input length and consider RE2 or the Rust regex crate.
- Have you tested the worst case — a long accepting run ending in a rejecting character — and confirmed it stays fast?
- Is a static analyser like
recheckoreslint-plugin-redosin your CI pipeline?
Putting It Into Practice
Catastrophic backtracking is one of those bugs that is invisible in every test you write and obvious to the first person who attacks you. The defence is not memorising a blacklist of bad patterns but understanding the mechanism — overlapping repetition multiplies the engine's search space — and building the habit of testing each pattern with a deliberately hostile string. Take every regex in this article, paste it into the Regex Tester alongside its adversarial input, and watch the difference between the vulnerable form and the rewritten one. That direct, immediate feedback is what turns an abstract warning into a reflex.
For a deeper grounding in the quantifier and grouping mechanics underneath all of this, keep our complete regex syntax guide open in another tab. The two articles are designed to be read together: one teaches you to write patterns, this one teaches you to write patterns that cannot be turned against you.