Catastrophic backtracking: why a regex freezes a page
When a quantifier is applied to a group that already repeats the same characters, the number of ways to split the input grows exponentially and a short string can hang the engine for minutes.
At a glance
- Trigger
- a quantifier over a group that already quantifies the same characters
- Growth
- exponential in the length of the input
- Symptom
- one CPU core pinned and an unresponsive tab or process
- Safe rewrites
- bound the counts, make the branches disjoint, or use a negated class
- Also called
- regular expression denial of service, or ReDoS, when it is reachable from input
- In this tester
- nested quantifiers are flagged and evaluation is capped at 1500ms off the main thread
In detail
The mechanism is combinatorial rather than mysterious. In /^(a+)+$/ the inner plus can take one a, or two, or three, and the outer plus can then repeat that choice in any number of ways. For a run of a characters followed by one character that cannot match, the engine has to try every possible split before it can conclude there is no match, and the number of splits doubles with every extra character.
The giveaway shape is a quantifier applied to a group whose contents are already quantified over the same character set. (a+)+, (\w+\s?)*, (\d+|\s)+ and (.*)* are all the same mistake wearing different clothes. Alternation with overlapping branches counts too, because two branches that can match the same text give the engine two paths to the same position.
The three fixes are all about removing choice. Make the pieces disjoint so only one path exists, as in ^\w+(?:\s\w+)*$ instead of ^(\w+\s?)+$. Bound the counts so the search space has a ceiling. Or replace a dot with a negated character class so the quantifier physically cannot cross the delimiter it was supposed to stop at.
This tester will not hang on a pattern like that. It lints for nested quantifiers that carry the risk and warns before you run one, and it evaluates patterns off the main thread with a hard 1500ms timeout, so a runaway pattern is cut off rather than taking the page with it. That makes it a reasonable place to experiment with a rewrite, which is exactly the wrong thing to do in a production server.
Examples
// Exponential: every extra "a" roughly doubles the work.
// 28 a characters take a few seconds here. 34 would take minutes.
/^(a+)+$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaX");
// Linear, and matches exactly the same set of strings.
/^a+$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaX"); // false, immediatelyThe two patterns accept the same language. Only one of them takes exponential time to reject a near miss, and the trailing X is what makes it a near miss.
// Risky: the group can match a word with or without a trailing space,
// so a long line of words has exponentially many ways to be divided up.
const risky = /^(\w+\s?)*$/;
// Safe: exactly one way to split any given input.
const safe = /^\w+(?:\s\w+)*$/;
safe.test("one two three"); // true
safe.test("one two"); // false, two spacesThings that catch people out
- The pattern usually works fine on every string that matches. The blow up only happens on input that almost matches, which is exactly the input an attacker sends and a test fixture never contains.
- Making the quantifier lazy does not help. A lazy quantifier explores the same number of paths, just in the opposite order.
- Anchoring with ^ and $ often makes it worse, because the anchor forces the engine to prove that no split works rather than giving up at the first partial match.
- A pattern built by concatenating user supplied fragments can create the nested shape even when no single fragment contains it.
Try it: Regex Tester
Type a pattern and a test string, watch every match highlight as you go, read a plain English breakdown of each token, and check the numbered and named groups it captured.
Regex Tester
LOCAL · Browser-OnlyTest and debug regular expressions with live matching and highlights
Related Regex syntax
All regex syntax →Lazy quantifiers: *?, +?, ?? and {n,m}?
A trailing question mark makes a quantifier prefer the shortest match. It fixes the overreaching tag pattern, and a negated class often fixes it better still.
Atomic groups in JavaScript: emulating them with a lookahead
JavaScript has no (?>...) and no possessive quantifiers. The lookahead and backreference pair gives you the same no backtracking behaviour.
{n,}: at least n repetitions, with no upper bound
The open ended count covers everything * and + cannot express, and a stray space after the comma turns the whole quantifier into literal text.
The ^ anchor: start of string, or start of line
Where the caret matches with and without the m flag, why it consumes nothing, and the entirely different job it does inside a character class.
The $ anchor: end of string, and the trailing newline question
Where $ matches in JavaScript, why it refuses to match before a trailing newline when Python and Ruby allow it, and how to write a literal dollar sign.
\A and \z in JavaScript: what to use instead
JavaScript has no \A, \z or \Z. Here is what those anchors silently turn into, and the absolute start and end assertions that survive the m flag.
Tools for this
- Regex Tester Free online regex tester - test and debug regular expressions with live matching and highlights
- AI Regex Explainer Get plain English explanations of regex patterns using a local AI - with live match testing
- Regex Playground Regex playground with live match highlighting, named groups, find and replace, and shareable links