A JavaScript service becomes unresponsive when it validates certain inputs with the regex /^(\w+\s?)*$/. Explain what is happening inside the regex engine, and how you would fix the pattern.

seniorshould knowfreq 44%

answer

engine explores alternatives on failure
the same text splits many ways
cost grows with each added character
a failing suffix is what triggers it
fix is to make the parse unique

basics

~20 s

The pattern is ambiguous: a nested quantifier lets the same text be split many ways. On input that ultimately fails to match, JavaScript's backtracking engine tries all of them, which grows exponentially with input length and blocks the thread. Rewrite the pattern so each character has one parse.

solid answer

~50 s

JavaScript's RegExp is a backtracking engine, and (\w+\s?)* is ambiguous — with \s? optional, the text "aaaa" can be divided among the outer * iterations in many different ways, all of which the engine considers equivalent. As long as the match succeeds it finds one quickly. Feed it a long run of word characters ending in something that cannot match, such as "aaaa…a!", and it must refute every division before declaring failure — a number that doubles with each added character. That is catastrophic backtracking, the basis of ReDoS. There is no timeout on a RegExp and matching is synchronous, so a single request pins the thread. The fix is to remove the ambiguity: /^\w+(\s\w+)*$/ forces each iteration to start with a required separator, so every character has exactly one parse. Also bound input length and treat user-supplied patterns as hostile.

JavaScript's `RegExp` is a backtracking engine, and `(\w+\s?)*` is ambiguous — with `\s?` optional, the text `"aaaa"` can be divided among the outer `*` iterations in many different ways, all of which the engine considers equivalent. As long as the match succeeds it finds one quickly. Feed it a long run of word characters ending in something that cannot match, such as `"aaaa…a!"`, and it must refute every division before declaring failure — a number that doubles with each added character. That is catastrophic backtracking, the basis of ReDoS. There is no timeout on a `RegExp` and matching is synchronous, so a single request pins the thread. The fix is to remove the ambiguity: `/^\w+(\s\w+)*$/` forces each iteration to start with a required separator, so every character has exactly one parse. Also bound input length and treat user-supplied patterns as hostile.

code

javascript · 12 lines

javascript

const bad = /^(\w+\s?)*$/;
const good = /^\w+(\s\w+)*$/;
const input = "a".repeat(28) + "!";

let t = Date.now();
good.test(input);
console.log("unambiguous:", Date.now() - t, "ms"); // ~0

t = Date.now();
bad.test(input);
console.log("ambiguous:", Date.now() - t, "ms");   // seconds, and doubling
// per extra character. Raise 28 slowly - do not run this with 40.

go deeper

for a junior

Recognise the shape: a quantifier inside a quantified group over overlapping characters can make a regex extremely slow on some inputs. Know the name catastrophic backtracking.

for a middle

Explain the mechanism — the pattern is ambiguous, so the same text can be split many ways, and a failing match forces the engine to try them all — and rewrite the example into an unambiguous form.

for a senior

Diagnose it in production from the symptoms, tie the stall to a specific request payload, and lead with a pattern rewrite plus an input-length bound rather than a mitigation that cannot actually interrupt a synchronous match.

for a principal

Set the policy: which inputs may reach a regex, whether user-supplied patterns are permitted at all, what static analysis and failing-input tests run in CI, and where a hand-written parser or a validation library is simply the better answer.

Why the engine can do exponential work

JavaScript's regular expressions are implemented as a backtracking engine. It walks the pattern making choices — how many characters a quantifier takes, which branch of an alternation to try — and whenever a choice leads to failure it returns to the most recent decision point and tries the next option. For most patterns this is fast. It becomes catastrophic when a pattern is ambiguous: when the same input can be carved up by the pattern in more than one way.

Look at (\w+\s?)* against "abcd". The outer * can run once with \w+ taking abcd. Or twice, with a then bcd. Or ab then cd. Or three times. Because \s? is optional, no separator is needed between iterations, so every way of splitting the run into consecutive pieces is a distinct path through the pattern. The number of such splits is 2^(n-1) for n characters.

While the overall match succeeds, none of that matters: the engine finds one valid path early and stops. The trap is failure. Append a character the pattern cannot accept:

/^(\w+\s?)*$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!");

Now $ fails at the end, and before the engine may report false it must prove that no split works. It enumerates all of them. Around 25–30 characters this crosses from milliseconds to seconds; a few more characters and it is effectively forever.

Why this is a production incident, not a curiosity

Regex matching in JavaScript is synchronous and there is no timeout option on RegExp. Nothing preempts it. A single unlucky input parks the thread that would otherwise be serving every other pending piece of work, so one request can stall an entire process. When the input is attacker-chosen this is a denial-of-service vector, conventionally called ReDoS, and it is unusually easy to trigger: the payload is a plain string, needs no privileges, and often lands in a validation path that runs before authentication.

The symptom in the wild is distinctive: CPU pinned at one core, no memory growth, no errors, requests timing out. A CPU profile shows time inside the regex, and correlating the stall with a request payload usually names the pattern immediately.

The shapes to recognise

The recognisable danger signs, all variations on ambiguity:

A quantifier inside a quantified group where the inner one can match what the outer one can: (a+)+, (a*)*, (\w+\s?)*, (\d+|\s)*.
Alternatives that overlap under a quantifier: (a|ab)*, (\w|\d)* — the same character matches more than one branch.
Adjacent quantifiers over overlapping classes: \s*\s*, or .*.*.

And the aggravating factor: something after the ambiguous part that can fail — an anchor, a required literal, a required suffix. Without a way to fail, the engine never explores the full space.

Fixing the pattern

The real fix is to make each character's parse unique. For the example, require the separator inside the repeated group and let the first word live outside it:

/^\w+(\s\w+)*$/

Now every iteration of * must begin with a whitespace character, \w and \s are disjoint, and there is exactly one way to divide any input. Failure is detected in linear time.

The general moves:

Use disjoint classes so consecutive parts cannot claim the same character. Replacing . with a negated class such as [^"] is the same idea.
Avoid nesting a quantifier inside a quantified group unless the inner match is bounded and non-overlapping.
Prefer counted quantifiers where the domain allows: {1,64} bounds the search space directly.
Bound the input before matching. A length cap turns an exponential into a constant, and it is the one mitigation that applies even to patterns you did not write.

JavaScript offers no engine-level escape hatch: there are no possessive quantifiers, no atomic groups, and no match timeout. That absence is exactly why the fix has to be the pattern.

Practices that keep it from recurring

Treat a regex applied to untrusted input as code with a performance contract. Test patterns against long inputs that fail — a hundred repeated characters plus a terminator — and assert the call returns quickly, rather than only testing the happy path. Static analysers for ReDoS catch the classic shapes and are worth wiring into CI. And where a pattern is genuinely user-supplied, either forbid it, or accept that you have handed a caller a way to burn your CPU and design around that fact.

Finally, keep proportion: not every nested quantifier is dangerous, and rewriting every regex out of superstition costs clarity. The question is whether the input is attacker-influenced and unbounded, and whether the pattern is ambiguous. Both being true is what makes it urgent.

## Why the engine can do exponential work JavaScript's regular expressions are implemented as a **backtracking** engine. It walks the pattern making choices — how many characters a quantifier takes, which branch of an alternation to try — and whenever a choice leads to failure it returns to the most recent decision point and tries the next option. For most patterns this is fast. It becomes catastrophic when a pattern is **ambiguous**: when the same input can be carved up by the pattern in more than one way. Look at `(\w+\s?)*` against `"abcd"`. The outer `*` can run once with `\w+` taking `abcd`. Or twice, with `a` then `bcd`. Or `ab` then `cd`. Or three times. Because `\s?` is optional, no separator is needed between iterations, so every way of splitting the run into consecutive pieces is a distinct path through the pattern. The number of such splits is 2^(n-1) for n characters. While the overall match **succeeds**, none of that matters: the engine finds one valid path early and stops. The trap is failure. Append a character the pattern cannot accept: ```js /^(\w+\s?)*$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"); ``` Now `$` fails at the end, and before the engine may report `false` it must prove that *no* split works. It enumerates all of them. Around 25–30 characters this crosses from milliseconds to seconds; a few more characters and it is effectively forever. ## Why this is a production incident, not a curiosity Regex matching in JavaScript is synchronous and there is no timeout option on `RegExp`. Nothing preempts it. A single unlucky input parks the thread that would otherwise be serving every other pending piece of work, so one request can stall an entire process. When the input is attacker-chosen this is a denial-of-service vector, conventionally called **ReDoS**, and it is unusually easy to trigger: the payload is a plain string, needs no privileges, and often lands in a validation path that runs before authentication. The symptom in the wild is distinctive: CPU pinned at one core, no memory growth, no errors, requests timing out. A CPU profile shows time inside the regex, and correlating the stall with a request payload usually names the pattern immediately. ## The shapes to recognise The recognisable danger signs, all variations on ambiguity: - **A quantifier inside a quantified group** where the inner one can match what the outer one can: `(a+)+`, `(a*)*`, `(\w+\s?)*`, `(\d+|\s)*`. - **Alternatives that overlap** under a quantifier: `(a|ab)*`, `(\w|\d)*` — the same character matches more than one branch. - **Adjacent quantifiers over overlapping classes**: `\s*\s*`, or `.*.*`. And the aggravating factor: something after the ambiguous part that can fail — an anchor, a required literal, a required suffix. Without a way to fail, the engine never explores the full space. ## Fixing the pattern The real fix is to make each character's parse unique. For the example, require the separator inside the repeated group and let the first word live outside it: ```js /^\w+(\s\w+)*$/ ``` Now every iteration of `*` must begin with a whitespace character, `\w` and `\s` are disjoint, and there is exactly one way to divide any input. Failure is detected in linear time. The general moves: - **Use disjoint classes** so consecutive parts cannot claim the same character. Replacing `.` with a negated class such as `[^"]` is the same idea. - **Avoid nesting a quantifier inside a quantified group** unless the inner match is bounded and non-overlapping. - **Prefer counted quantifiers** where the domain allows: `{1,64}` bounds the search space directly. - **Bound the input** before matching. A length cap turns an exponential into a constant, and it is the one mitigation that applies even to patterns you did not write. JavaScript offers no engine-level escape hatch: there are no possessive quantifiers, no atomic groups, and no match timeout. That absence is exactly why the fix has to be the pattern. ## Practices that keep it from recurring Treat a regex applied to untrusted input as code with a performance contract. Test patterns against long inputs that *fail* — a hundred repeated characters plus a terminator — and assert the call returns quickly, rather than only testing the happy path. Static analysers for ReDoS catch the classic shapes and are worth wiring into CI. And where a pattern is genuinely user-supplied, either forbid it, or accept that you have handed a caller a way to burn your CPU and design around that fact. Finally, keep proportion: not every nested quantifier is dangerous, and rewriting every regex out of superstition costs clarity. The question is whether the input is attacker-influenced and unbounded, and whether the pattern is ambiguous. Both being true is what makes it urgent.

Why does the pathological behaviour appear on failing input rather than on strings that match?
When a match exists the engine finds one path and stops, so the work is small. Failure requires proving that no path works, which means enumerating the whole ambiguous search space. That is why a trailing character the pattern cannot accept — often just an anchor at the end refusing to line up — is the trigger in every classic example.
Can't you just wrap the match in a timeout?
Not usefully. `RegExp` matching is synchronous and there is no timeout option, so no timer can interrupt it — a `setTimeout` fires only after the match has already returned. Offloading to a separate execution context that you can terminate is the only way to make an interruption real, and that trades a simple call for lifecycle management. Fixing the pattern is almost always cheaper.
How would you catch this class of defect before it reaches production?
Test patterns against failing inputs, not just matching ones: build a string of a hundred repeated characters plus a terminator the pattern rejects, and assert the call completes fast. Add a ReDoS-aware static analyser to CI to flag nested and overlapping quantifiers. And cap input length at the boundary so an undiscovered pattern cannot be driven far enough to hurt.
Is every nested quantifier a problem?
No. The danger needs ambiguity — the inner and outer parts must be able to claim the same characters — plus something afterwards that can fail. `(\s\w+)*` is nested but safe because each iteration must consume a whitespace character and `\s` and `\w` are disjoint, so there is exactly one parse. Judge by ambiguity, not by shape alone.

saying these in an interview costs you the question

Blames a slow machine or a large input size rather than the pattern
Thinks a timeout or setTimeout can interrupt a running match
Says only user-supplied patterns can cause this, never hardcoded ones
Proposes atomic groups or possessive quantifiers, which JavaScript lacks
Only tests patterns against inputs that match

A JavaScript service becomes unresponsive when it validates certain inputs with the regex /^(\w+\s?)*$/. Explain what is happening inside the regex engine, and how you would fix the pattern.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why the engine can do exponential work

Why this is a production incident, not a curiosity

The shapes to recognise

Fixing the pattern

Practices that keep it from recurring

▾common follow-ups4 questions

▾red flags5 flags

§ context

▾related questions6 questions

▾related topics4 topics

Why the engine can do exponential work

Why this is a production incident, not a curiosity

The shapes to recognise

Fixing the pattern

Practices that keep it from recurring

answer

go deeper

context