Regex catastrophic backtracking: how to spot it and fix it
Most regular expressions finish in microseconds. A few take longer than the age of the universe on a 30 character string. Here is how to tell them apart before they reach production.
Last reviewed 2026-11-01. Behavior described is that of JavaScript (ECMAScript) regular expressions, which use backtracking matching.
Uses your browser's own RegExp engine (ECMAScript), in a background worker. A run that takes longer than 1 second is stopped, so a pattern that backtracks catastrophically cannot freeze this tab.
Why a pattern can run for ages
JavaScript regular expressions are matched by a backtracking engine. When part of a pattern can match in more than one way, the engine tries one choice, and if the rest of the pattern fails it goes back and tries the next. Usually there are few choices and failure is quick.
The trouble starts when the choices multiply. In (a+)+$ tested against a long run of a followed by one b, the engine can split the run of a characters between the inner and outer + in an exponential number of ways, and it tries them all before it can say the match fails. Each extra a doubles the time. This is called catastrophic backtracking, and when an attacker can choose the input, it is a denial of service known as ReDoS.
Try it safely
Paste (a+)+$ into the tester above, with the text aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab. The tester runs matching in a background worker with a one second budget and stops the match if it runs over, so the page stays responsive. Then shorten the run of a characters and watch the time drop. A real program has no such guard, so a pattern that merely feels slow in the tester deserves a rewrite.
Patterns that cause it
| Shape | Example | Why it explodes |
|---|---|---|
| Nested quantifier | (a+)+, (\w+\s?)* | The inner and outer repeats can divide the same text many ways. |
| Overlapping alternatives | (a|aa)+, (\d|\d\d)* | Both branches match the same text, so each position has two paths. |
| Adjacent greedy parts | .*.*=.* | Two wildcards can split the same text at any point; cost grows with the square or cube of the length. |
| Optional repeat next to its own match | (x+x+)+y | The engine tries every split between the two x+ parts. |
Cost is exponential for the nested quantifier, the overlapping alternatives and the split repeat when the match fails, and polynomial for the adjacent wildcards.
Four ways to rewrite
- **Remove the nesting.**
(a+)+matches the same strings asa+. If the inner group is only there for repetition, drop the outer quantifier. - **Make branches exclusive.** Replace
(a|aa)+witha+, or make the branches start with different characters so only one can match at each position. - **Use a more specific class.** Instead of
.*in the middle of a pattern, use[^=]*when you mean "up to the next equals sign". The engine then has one way to match, not many. - **Anchor and bound.** Use
^and$, and replace*with{0,64}where the input has a sensible maximum. A bounded repeat caps the damage even if the shape is imperfect.
A trick that works in JavaScript
Some engines have atomic groups, which forbid backtracking into a group once it has matched. JavaScript does not have them, but a lookahead with a backreference gives the same effect: (?=(a+))\1 matches the same text as a+ and then refuses to give any of it back. It is hard to read, so add a comment next to it and keep it for the rare case where the simple rewrites do not apply.
Testing a pattern before you ship it
- Test with a failing input as well as a matching one. Catastrophic cases happen on near misses: a long string that almost matches.
- Grow the input: try 20, 25 and 30 characters. Linear growth is fine; doubling per character is not.
- Use the
uflag when matching Unicode text, and remember that\wand\dmatch only ASCII characters in JavaScript unless you spell out the ranges. - Never run a user-supplied pattern on a server thread. Run user input through patterns you wrote, and bound its length first.
Frequently asked questions
Does every nested quantifier cause catastrophic backtracking?
No. It needs ambiguity: more than one way to match the same text. (ab)+ is safe because there is only one way to split a run of ab.
Is a longer timeout a fix?
No. Exponential cost outruns any timeout as the input grows. Fix the pattern and bound the input.
Does the tester send my pattern anywhere?
No. Matching runs in your browser, in a worker that the page stops if it runs past one second.
Sources
- MDN: Regular expressions guide checked 2026-11-01
- OWASP: Regular expression Denial of Service (ReDoS) checked 2026-11-01
- MDN: Lookahead assertions checked 2026-11-01