The regex that stops your server, measured char by char
Sanjeev SharmaAdvertisement
A user pastes thirty characters into a form. Your process stops answering anything — not that request, every request — for seven seconds. No error, no crash, nothing in the logs except a gap.
This is that failure, measured character by character, on a pattern of the kind that sits in real validation code.
The short answer
A regex with nested, ambiguous quantifiers — (\w+\s?)*, (a+)+, (x|xy)* —
can take time that doubles with every two characters of input. Measured here: 20
characters took 6.6 ms, 30 characters took 6,809 ms. The same language matched
with an unambiguous pattern took 0.0015 ms at every length. The fix is the
pattern, not a faster machine.
What the curve actually looks like
Two patterns, same input, one process. The vulnerable one is
/^(\w+\s?)*$/ — words separated by optional spaces, which is what a "letters
and spaces only" validator looks like when it is written quickly. The safe one is
/^\w+(\s\w+)*\s?$/, which matches the same strings with one path to each match.
Input is 'a'.repeat(n) + '!'. The trailing ! is the point: it can never
match, so the engine has to exhaust every way of splitting the a-run before it
can say no.
- 18 chars · vulnerable1.693
- 20 chars · vulnerable6.643
- 22 chars · vulnerable26.332
- 24 chars · vulnerable104.024
- 26 chars · vulnerable419.773
- 28 chars · vulnerable1,680
- 30 chars · vulnerable6,809
- 30 chars · rewritten0.0015
- 24 chars · vulnerable — past a 100 ms budget already
- 30 chars · vulnerable — one request, 6.8 seconds of blocked event loop
- 30 chars · rewritten — same input, same answer
Every two characters multiplies the work by about four. That is not a slow regex; it is an exponential one, and the difference matters because exponential means the input that kills you is barely longer than the input that was fine.
| Input length | Vulnerable (\w+\s?)* | Rewritten \w+(\s\w+)* | Ratio |
|---|---|---|---|
| 18 chars | 1.7 ms | 0.0004 ms | 4,000× |
| 22 chars | 26.3 ms | 0.0015 ms | 17,000× |
| 26 chars | 419.8 ms | 0.0015 ms | 280,000× |
| 30 chars | 6,809 ms | 0.0015 ms | 4,500,000× |
The classic textbook pattern /^(a+)+$/ measured the same shape: 7.8 ms at 18
characters, 7,111 ms at 30. Both are the same bug wearing different clothes.
Why does adding two characters multiply the work by four?
Because the engine is trying every way to divide the input between the inner and outer quantifier, and the number of divisions grows exponentially.
The rule of thumb that falls out of this: a quantifier inside a quantifier is only dangerous when the two can match the same character. If a separator forces the split, the ambiguity is gone.
Both patterns match the same strings. Only one of them has more than one way to do it, and that is the whole difference between 0.0015 ms and 6.8 seconds.
Which nested quantifiers are actually dangerous?
Not all of them, and this is where most advice is too blunt. The same benchmark
ran /^([a-z0-9]+-)+[a-z0-9]+$/ — a slug validator, nested quantifier, looks
identical in shape — against inputs up to 88 characters. It stayed at 0.001 ms.
The difference is ambiguity. In the slug pattern, - can only be matched by the
separator, so there is exactly one way to split abc-def-ghi. In (\w+\s?)* the
space is optional, so \w+ can swallow characters the outer loop could also
have taken.
| Pattern | Nested? | Ambiguous? | Measured at 30 chars |
|---|---|---|---|
^(a+)+$ | yes | yes — a matchable by both | 7,111 ms |
^(\w+\s?)*$ | yes | yes — optional separator | 6,809 ms |
^([a-z0-9]+-)+[a-z0-9]+$ | yes | no — - forces the split | 0.001 ms |
^\w+(\s\w+)*\s?$ | yes | no — separator is required | 0.0015 ms |
So the test is not "does it nest". It is: can the inner and outer parts match the same character? If yes, there is more than one path, and the engine will try all of them before giving up.
What to do about it
| Option | Cost | Catches | Effort | Pick it when |
|---|---|---|---|---|
| Rewrite the patterndefault | 0 | the actual bug | minutes | You own the pattern and can express the separator explicitly |
| Cap input length before matching | ~0 | everything past the cap | one line | Always, as a second layer — a 64-character limit makes most of these unreachable |
| Swap in RE2 | native dep, no backtracking features | all catastrophic patterns | a dependency | Patterns come from users or config and cannot be audited |
| Run matching in a worker with a timeout | thread + message overhead | the symptom, not the cause | a harness | Untrusted patterns you must keep supporting |
| Hope | 0 | nothing | none | Never. The input length that kills you is only two characters past one that was fine |
The rewrite rule is mechanical: make the separator mandatory inside the repeat
and lift the optional part out. (\w+\s?)* becomes \w+(\s\w+)*\s?. Same
language, one path. Both the
MDN reference on quantifiers
and the regular expression
guide
spell out greedy versus lazy matching, which is the mechanism underneath.
If the patterns are not yours — a search box that accepts a regex, rules loaded
from a database — no rewrite can save you, and the answer is an engine that does
not backtrack at all. RE2 guarantees linear time
by refusing the features that make backtracking necessary, and
node-re2 exposes it with a RegExp-shaped
API.
When does your pattern cross your timeout?
Input length that blows the budget
formula: unknown variable "Math" in "20 + 2 * Math.ceil(Math.log(budget / base) / Math.log(4))"
20 + 2 × log₄(200 ÷ 7) — the measured curve quadruples every 2 chars
Time at your maximum accepted length
formula: unknown variable "Math" in "base * Math.pow(4, (maxlen - 20) / 2)"
7 ms × 4^((64 − 20) ÷ 2)
Safe input cap for this budget
formula: unknown variable "Math" in "20 + 2 * Math.floor(Math.log(budget / base) / Math.log(4))"
the length where a single match still fits inside the budget
Only meaningful for a pattern you have already measured as exponential. Put your own number in the second slider by timing one .test() at 20 characters — the script in this repository prints it.
How to find these before a user does
Three passes, cheapest first.
The first is grep: look for )*, )+, ){ immediately after a group that ends
in a quantifier — (\w+)+, ([a-z]*)*, (\d+|\d+\w)*. That catches most of
them by shape.
The second is the measurement in this post. Take each suspicious pattern, run it
against 'a'.repeat(n) + '!' for n from 14 to 30, and watch the times. Linear
means safe; quadrupling means exponential. The script is
tools/bench/regex-backtracking.mjs and it takes about a second per pattern.
The third is a hard input cap at the edge — body size limits, field length
validation, a maxLength on the input — because it turns an exponential problem
into a bounded one regardless of what the pattern does. Validation that runs
before the expensive check is the same idea as
validating pagination parameters
before they reach the database.
Can you spot the dangerous one?
3 questions — answers explained as you go.
1. Which of these can take exponential time?
2. Your pattern takes 7 ms at 20 characters. What does it take at 28?
3. Users supply the regex themselves. What is the fix?
Frequently Asked Questions
What is catastrophic backtracking?
A regular expression where the engine has more than one way to match the same input, so a failing match forces it to try every combination. The number of combinations grows exponentially with input length — in this article, four times the work for every two extra characters.
Does a nested quantifier always mean a ReDoS?
No. A nested quantifier is only dangerous when the inner and outer parts can match the same character. A slug pattern like ^([a-z0-9]+-)+[a-z0-9]+$ nests but stays linear, because the hyphen forces exactly one split. It measured 0.001 ms at 88 characters.
Can I just add a timeout to the regex?
JavaScript has no per-regex timeout. The match runs on the same thread as everything else, so the process is unresponsive until it finishes. A timeout only helps if the match runs in a worker thread you can terminate, which costs a thread and a message round trip per call.
How do I test my own patterns for this?
Time a single .test() against strings of increasing length that cannot match — an alphabetic run plus one invalid character is the standard shape. If the time roughly quadruples every two characters, the pattern is exponential. The script in this repository does it in about a second per pattern.
Is this a Node problem specifically?
No. It is how backtracking engines work, so the same patterns behave the same way in browsers, Python, Java and PHP. What differs is the blast radius: in a single-threaded runtime, one bad match stops every concurrent request on that process rather than one thread out of many.
The part worth remembering
The input that takes seven seconds is thirty characters long. There is no gradual degradation to alert on, no slow query to spot, and the request that does it looks exactly like the one before it.
So treat this as a code-review rule rather than a monitoring problem: a quantifier inside a quantifier gets read out loud, and if the two can match the same character, it gets rewritten before it merges. When one does slip through, the symptom is an event loop that stops rather than an error — which is the same signature as the blocking work covered in Node performance profiling, and it is worth knowing both shapes.
For the surrounding practice: error handling that survives async is what tells you a request died rather than vanished, async logging keeps the log line itself off the hot path, and the backend performance checklist lists input caps alongside the other cheap defences. The measurement method here — interleave, take the best round, print the spread — is the same one used in Node 22 vs 24 vs 26, and the context cost it borrows from is in what AsyncLocalStorage costs.
Advertisement
