A regular expression that works on every input you tried can still be the slowest line in your service. Not because it is wrong, but because someone can pick an input that makes the engine explore an exponential number of ways to match it. This page explains what the checker does, which shapes cause it, and how to get rid of them.
What the checker measures
Most ReDoS tools stop at pattern matching: they look for a quantifier inside a quantifier and print a warning. That answers half the question. A nested quantifier is only dangerous if the match can be made to fail, and how dangerous depends on numbers nobody gets from staring at the pattern.
So this tool does both. It parses the regex, finds every repetition that can consume the same characters in more than one way, and then builds an input that forces the engine down all of them: a prefix that gets into the ambiguous part, the repeated unit itself, and one trailing character that makes the whole match fail. That string is then run against your pattern with growing lengths, and the time is measured in this tab.
What comes out is a growth curve and three concrete numbers: the shape (exponential, polynomial or linear), the factor per added character, and the input length at which the match crosses one second of CPU. For ^(a+)+$ that number lands somewhere near 29 characters on current hardware, which is the whole argument in one figure.
How to read the report
Paste one pattern per line, either bare or in /pattern/flags form. Lines starting with # are ignored, so you can label them. Up to six patterns are checked per run, because each one is benchmarked for real.
- Pattern. The growth shape, the measured time at the last length tried, the one-second threshold, and the exact attack input, quoted so you can paste it into your own test.
- Growth. The raw measurements: input length against match time. This is where you see the difference between doubling per character and merely getting slower.
- Findings. Each ambiguous spot with its position in the pattern and the rewrite that removes it.
--benchmark
Runs the timing. Each measurement is repeated until it clears the timer resolution, so the growth rate is known from the second step onward and the next length can be predicted rather than guessed. That is what keeps the page responsive: a benchmark that guessed would eventually pick a length that takes a minute, and there is no way to interrupt a running regex in JavaScript. Switch it off if you only want the static analysis.
--polynomial
Also reports the quadratic hotspots, mainly two adjacent quantifiers over overlapping characters. They are not catastrophic, they are just slow, and they are much more common than the exponential ones.
Why backtracking explodes
A backtracking engine tries one path through the pattern at a time. When a path fails, it walks back to the last point where it had a choice, takes the next option and tries again. For most patterns there are few choices and it finishes in a single pass.
Ambiguity is what turns that into a search. Take (a+)+$ and the input aaaa!. The inner a+ can take one, two, three or four characters, and the outer + can repeat any number of times, so the four a-characters can be distributed across the repetitions in eight different ways: 4, 3+1, 2+2, 2+1+1, 1+3, and so on. Every one of those ends up at the !, fails, and sends the engine back for the next. Each character you add doubles the number of distributions, so 30 characters means about a billion attempts.
The important part is the failure. If the input is just aaaa, the first path matches and the engine stops immediately. The exponential cost only appears when the match has to be ruled out, which is exactly what an attacker controls: append one character that cannot fit.
The four shapes that blow up
| Shape | Example | Cost |
|---|---|---|
| Quantifier inside a quantifier | (a+)+, ([a-z]+)*, (\w+\s?)* | exponential |
| Repeated alternation with overlapping branches | (a|a)*, (a|ab)+ | exponential |
| Repeated group that can match nothing | (a*)*, (\s|)+ | exponential |
| Adjacent quantifiers over the same characters | \d+\d+, .*.*, \s+$ unanchored | quadratic |
The first three share one property: the same input can be consumed in more than one way, and the number of ways grows with the input. The fourth is different in kind. There is only one split point, so the work grows with the square of the length rather than exponentially, which is what made the Stack Overflow outage a 34-minute one rather than a permanent one.
The classic email validation pattern manages two of these at once. In ^([a-zA-Z0-9_\.\-])+@(([a-zA-Z\-])+\.)+([a-zA-Z]{2,4})+$ both the domain part and the TLD part nest a quantifier inside a quantifier, and the checker measures the second one crossing a second at roughly 55 characters of input.
Ambiguous is not the same as exploitable
This is where a warning-only tool sends people down the wrong path. /(a+)+/ used with .test() is not exploitable: there is nothing after the repetition, so the first attempt always succeeds and the engine never backtracks. Reported as vulnerable, it produces a ticket, a discussion and no bug.
The checker measures the pattern as you wrote it and reports linear growth when that is what it finds. It then measures the anchored variant separately and tells you that too, because the ambiguity is still in the pattern and the next edit that adds a $, a trailing token or a wrapping ^(?:…)$ turns it on. Our own take is that this class deserves a fix rather than a shrug: it is a landmine with the pin still in.
The reverse case matters as well. A pattern used with the g flag in a loop, or without an anchor at the start, is retried at every offset in the string, which multiplies whatever cost the pattern already has by the length of the input.
How to fix a vulnerable regex
In rough order of preference:
- Collapse the nesting.
(a+)+anda+match the same strings. So do([a-z]+)*and[a-z]*. The nested version was almost always an accident of grouping for a capture that is never used. - Make alternations disjoint. If two branches can match the same text, one of them is redundant.
(a|ab)+isa(b?)+, and usually what was meant is(ab?)+. - Move the optional part out of the repetition.
(\s|)+is\s*, and(a*)*isa*. A repeated group that can match nothing is always a bug, not a feature. - Bound the quantifier.
{1,64}instead of+caps the work at a polynomial with a known degree. Not elegant, and it fixes the whole class in one edit when the pattern cannot be restructured. - Use an atomic group where the engine has one.
(?>a+)in PCRE, Java and .NET, or the possessivea++. JavaScript has neither; the lookahead trick(?=(a+))\1does the same thing and is worth a comment above it. - Limit the input length. Not a fix, but it converts an unbounded cost into a bounded one, and it takes a minute to deploy.
What does not work: making the pattern lazy. Changing + to +? reverses the order in which the engine tries the alternatives and leaves the number of alternatives exactly the same. Lazy quantifiers are a readability choice, not a safety one.
Engines that cannot backtrack
The whole problem comes from the engine design. Perl-style engines backtrack because they support backreferences and lookaround, which a finite automaton cannot express. Engines that give those up run in time linear in the input, no matter what pattern you hand them.
| Engine | Backtracks | Where you meet it |
|---|---|---|
| V8, SpiderMonkey, JavaScriptCore | yes | every browser, Node, Deno, Bun |
| PCRE2 | yes | PHP, nginx, many C projects |
Python re, Java Pattern, .NET Regex | yes | most backends |
| RE2 | no | Go regexp, the re2 npm package, google-re2 for Python |
Rust regex | no | Rust services, ripgrep |
Go is the interesting one here: its standard library uses RE2, so a Go service is immune to ReDoS by default and its developers rarely think about any of this. The other side of that trade is that the Go regexp package has no lookahead, which surprises people porting patterns the other way.
If you run patterns from user input, or patterns from a config file that someone else edits, a linear-time engine is the only structural answer. For your own patterns in your own code, fixing the four shapes above is faster than swapping engines. The guide on catastrophic backtracking walks through the Cloudflare and Stack Overflow incidents in detail.
Patterns that blow up
Which linters or scanners catch a vulnerable regex before it ships?
For JavaScript, eslint-plugin-security has detect-unsafe-regex, which runs the safe-regex heuristic and only sees the obvious nesting. eslint-plugin-redos is stronger because it uses recheck, an analyser that decides exponential and polynomial blowup instead of matching shapes. Beyond linting there is CodeQL, whose js/redos and py/redos queries ship with GitHub code scanning, and Semgrep rules for the same. Run one of them on the diff, because a vulnerable pattern is almost always added, not discovered.
What should I do about a ReDoS advisory from npm audit?
Check reachability before you panic: an advisory only matters if attacker-controlled input reaches that regex. Find the dependent with npm ls <package>, then look at whether the vulnerable function runs on request data or on your own build-time strings, because a ReDoS in a CLI formatter you run locally is noise. If it is reachable, npm audit fix or an overrides entry in package.json pins the patched version; if the maintainer is gone, wrapping the call in a length check is a legitimate stopgap.
Can a validation library like Joi or validator.js be ReDoS-vulnerable?
Yes, and that is the common way it enters a codebase: the regex is in a dependency, not in your diff. validator.js has shipped several ReDoS advisories, most of them in the loosely specified formats such as email and data URIs, and any schema library that validates a string format has the same exposure. Treat a format check on untrusted input as attack surface, keep the libraries current, and put a length limit in front of the validator instead of relying on it.
Is (a+)+ always dangerous?
Only when the overall match can fail. On the input "aaaa" the pattern (a+)+ succeeds on the first attempt and never backtracks. Add an anchor or anything after it, as in (a+)+$ or (a+)+b, and the same pattern needs exponential time on "aaaa!" because every possible split has to be ruled out. That is why the checker measures the pattern as written and then measures the anchored variant separately.
How do I fix a regex with catastrophic backtracking?
Remove the ambiguity rather than the quantifier. (a+)+ describes the same language as a+, ([a-z]+)* is [a-z]*, and (a|ab)+ becomes a(b?)+. Where two parts overlap, make them disjoint: \w+\s? repeated is ambiguous because \w and the optional space can both be consumed by the outer repetition, and matching the whole run in one class fixes it. When the structure has to stay, bound the quantifier with {1,64}, which caps the work at a polynomial you can reason about.
What is an atomic group and does JavaScript have one?
An atomic group (?>...) tells the engine that once the group has matched, it may never give any of it back, which removes the backtracking entirely. Perl, PHP, Java and .NET have it, and so do possessive quantifiers like a++. JavaScript has neither, and the usual workaround is a lookahead with a backreference: (?=(a+))\1 matches what (?>a+) would. It works, and it reads badly enough that restructuring the pattern is usually the better answer.
Which regex engines are immune to ReDoS?
Engines built on finite automata rather than backtracking: RE2 (Go's standard regexp package, and the re2 bindings for Node, Python and Ruby), the Rust regex crate, and Hyperscan. They guarantee linear time in the input and pay for it by dropping backreferences and lookaround, which cannot be expressed in a finite automaton. If a regex has to run against input from strangers, that trade is usually worth making.
Has ReDoS actually taken down a real service?
Twice in public and memorably. Stack Overflow went down for 34 minutes in July 2016 because a trim regex of the form \s+$ hit a post with roughly 20000 consecutive space characters. Cloudflare's global outage in July 2019 came from one line in a new WAF rule containing .*.*=.*, which turned a routine deploy into 100 percent CPU on every machine in the edge network. Both were single regexes in otherwise ordinary code.
Does a timeout protect against ReDoS?
It limits the damage without removing the problem. .NET takes a Regex timeout argument, Java has no built-in one, and JavaScript has none at all because the match blocks the single thread it runs on, so nothing can interrupt it. In Node the practical version of a timeout is a worker thread or a child process you can kill, which costs more than fixing the pattern. Treat a timeout as the seatbelt, not the brakes.
Is a length limit on the input enough?
It helps a lot, and it is the cheapest mitigation you can deploy today. Exponential growth means the safe length is small: if a pattern needs a second at 30 characters, it needs a millisecond at 20, so capping a username at 64 characters removes most of the risk. It does nothing for a quadratic pattern on a field that legitimately holds a few kilobytes, such as a comment body or a log line.
Why is my regex slow but not exponential?
Two quantifiers side by side over the same characters give you quadratic time: \d+\d+ or .*.* have to try every split of the run between them. That is n^2 rather than 2^n, so it does not hang forever, but a 10000-character input still costs tens of milliseconds per request and a handful of concurrent requests is enough to saturate a thread pool. The --polynomial option reports these; they rarely make the news and they are far more common than the exponential ones.
Where do vulnerable regexes usually come from?
Copied validation patterns, mostly. The email regex with ([a-zA-Z0-9_\.\-])+@(([a-zA-Z\-])+\.)+ has been pasted into thousands of codebases and every group in it nests a quantifier. After that: input trimming (^\s*(.*?)\s*$), log and user-agent parsing, markdown and BBCode processing, and dependency-supplied patterns, which is what the npm advisories tagged ReDoS keep being about.