How a regex engine matches
JavaScript's regular expressions are backtracking engines. When a pattern can match in more than one
way, the engine tries one path, and if the rest of the pattern fails it returns to the last choice and
tries the next. That is what makes patterns like (foo|bar)+ work without a compiler, and
it is also what makes some patterns quadratic or exponential in the length of the input.
The classic shape is a quantifier inside a quantifier: (a+)+, (a*)*,
(a|aa)+. On a string that matches, the first path succeeds and the cost is linear. On a
string that almost matches — the same characters followed by one that cannot match — the
engine must exhaust every way of dividing the a's between the inner and outer repetitions before it
concludes there is no match. For n a's, the number of ways is exponential in n.
The cost, measured
The table below times /^(a+)+$/ and /^a+$/ on the same input: a run of
n a's followed by a character that prevents a match. Timings are from Node.js 20 on the
machine used to write this page; absolute numbers vary by hardware, but the shape does not.
| Input length | ^(a+)+$ | ^a+$ | Growth |
|---|---|---|---|
| 16 a's + “!” | 3.22 ms | 0.02 ms | — |
| 18 | 2.66 ms | 0.05 ms | startup noise |
| 20 | 9.86 ms | < 0.01 ms | ≈ 3.7× |
| 22 | 38.02 ms | < 0.01 ms | ≈ 3.9× |
| 24 | 144.00 ms | 0.01 ms | ≈ 3.8× |
Each two extra characters multiply the time by about four — the signature of exponential growth. At 30 characters the same pattern takes seconds; at 40 it takes longer than anyone will wait. The linear pattern stays flat because there is only one way to match a run of a's.
Measure this yourself in the browser console with console.time and a loop. Run each
length once, discard the first timing as warm-up, and double the input rather than adding a fixed
amount: exponential cost is visible as a constant multiplier, not as a constant addition.
Recognising the dangerous shapes
- A quantified group containing a quantifier —
(a+)+,(\d*)*,(.*)*. The inner and outer repetitions can split the same text many ways. - Alternatives with a common prefix —
(a|ab)+on a string of a's. The engine can choose the longer or the shorter branch at every position. - Optional parts that can match the same text —
(a?)*,(a|a?)+. Each optional match is another branch to revisit. - A failure at the very end — the cost is highest when the first n − 1 characters match and the last one does not, because every path is explored before giving up.
None of these is wrong in every context. A pattern with nested quantifiers applied to a fixed, short, trusted string is fine. The problem is applying it to input whose length the user controls.
Rewriting for linear behaviour
The first move is to remove the ambiguity rather than to tune the engine. (a+)+ and
a+ describe the same language for this input; the outer group adds nothing but choices.
(a|aa)+ can often be rewritten as a+ plus a separate condition. When the
alternation is genuinely needed, order it so that the most specific branch comes first, and make the
branches disjoint if you can.
The second move is to bound the input. A regex that is exponential in n is survivable at n = 20 and fatal at n = 200; checking the length before matching is a one-line defence. The third is to move the match off the critical path — a worker, a server-side engine with a time limit, or a library such as RE2 that guarantees linear time by giving up backtracking features. JavaScript's own engine has no timeout, so a pathological pattern on the main thread freezes the page until the browser gives up.
What this means for the tester
The regex tester on this site runs your pattern in the page, which is convenient and also means a pathological pattern will hang the tab. That is not a defect in the tester; it is the same engine the browser uses for every other regex. If a pattern freezes while you are iterating, reload the page and simplify the pattern — the freeze is the finding. On a server, the same pattern is a denial-of-service vector (ReDoS), because an attacker can send the input that triggers the worst case.
Where it bites in practice
The textbook example is (a+)+, but production incidents usually involve a pattern that
was trying to be helpful. An email validator written as
^([a-zA-Z0-9]+)*@… has the same nested-quantifier shape; a “match a quoted string”
pattern such as (".*?")* can backtrack heavily on unclosed quotes; a log parser that
allows whitespace between optional fields can generate many paths for a line that ends unexpectedly.
In each case the happy path is fast and the malformed input — exactly what an attacker or a corrupt
file supplies — is the slow one.
The detection habit is to ask, for every pattern that will see untrusted input: what is the longest input it could receive, and which input makes it fail? Then test that input, not the example in the documentation. If the failure case is quadratic rather than exponential, it may still be too slow at scale: doubling a 1,000-character input from 1 ms to 4 ms is tolerable, but the same curve at 100,000 characters is not.
Checking a pattern before it ships
- Look for a quantifier inside a quantified group; if present, ask what the inner repetition adds.
- Test with a long run of the repeated character followed by one that fails — the worst case, not the happy path.
- Double the input length and watch the time; a 4× jump per doubling means exponential, 2× means quadratic.
- Bound the input in code, and never run an unbounded user-supplied pattern on a server without a time limit.