A shipped validation pattern backtracks catastrophically on crafted input: how do you rewrite it so that matching cannot blow up?

seniorshould knowfreq 52%

answer

one path per accepted string
flatten, disjoin, separate
item then separator-item, repeated
atomic grouping narrows what is accepted
growth test proves the fix

basics

~20 s

Remove the ambiguity so every accepted string has exactly one way to match: flatten a quantifier nested in a quantifier, make alternation branches disjoint, and express a separated list as item followed by repeated separator-item. Then anchor, cap the input and prove it with a growth test.

solid answer

~40 s

Aim for a pattern with one match path per string. Three moves cover most real cases. Flatten a quantifier under a quantifier where the two describe the same language — ([a-z]+)+ accepts exactly what [a-z]+ accepts, so the outer + buys nothing and costs everything. Make overlapping alternation branches disjoint, so no string can be explained twice. Rewrite a repeated separated group from (item sep?)+ to item (sep item)*, which pins every boundary to a separator. Then anchor both ends so the search does not restart at each offset, cap the field length, and add a test that feeds a growing valid prefix plus one defeating symbol and asserts a time bound. Where the ambiguity is genuinely needed, an atomic group can contain it, at the cost of narrowing what the pattern accepts.

Aim for a pattern with **one match path per string**. Three moves cover most real cases. Flatten a quantifier under a quantifier where the two describe the same language — `([a-z]+)+` accepts exactly what `[a-z]+` accepts, so the outer `+` buys nothing and costs everything. Make overlapping alternation branches disjoint, so no string can be explained twice. Rewrite a repeated separated group from `(item sep?)+` to `item (sep item)*`, which pins every boundary to a separator. Then anchor both ends so the search does not restart at each offset, cap the field length, and add a test that feeds a growing valid prefix plus one defeating symbol and asserts a time bound. Where the ambiguity is genuinely needed, an atomic group can contain it, at the cost of narrowing what the pattern accepts.

go deeper

for a junior

Learn the safe idiom for a separated list: match one item, then repeat the separator-plus-item group. Prefer it over wrapping an optional separator inside a repeated group.

for a middle

Explain why each rewrite works in terms of match paths: flattening, disjoint branches and separator-anchored boundaries all leave exactly one way to match any accepted string.

for a senior

Own the whole change: identify which cost loop is at fault, rewrite it, keep the accepted language pinned by tests, and add the growth test that would have caught the original.

for a principal

Decide how this stops recurring — where validation patterns live, whether they are reviewed as code, and whether the safe idioms are available centrally rather than retyped per service.

The goal: exactly one way to match

The repair is not 'make the pattern faster', it is make the pattern unambiguous. If every string that the pattern accepts has exactly one derivation through it, the matcher never has a saved alternative to return to, and failure is reached by the same short route as success. Ambiguity is the resource the attacker spends; rewriting removes the resource rather than rationing it.

That gives a concrete acceptance criterion for the review: pick any string and ask whether the pattern could account for it in two different ways. If yes, you are not finished.

The rewrite moves

Flatten a quantifier under a quantifier. ([a-z]+)+ accepts precisely the same strings as [a-z]+; the outer repetition adds no expressive power and all of the branching. Delete it.
Make alternation branches disjoint. ([0-9]+|[0-9a-f]+)+ has two branches that both accept digit runs. Either drop the redundant branch or give each a distinguishing prefix or class so no string satisfies both.
Anchor a separated list on its separators. Replace ^([a-z]+ ?)+$ with ^[a-z]+( [a-z]+)*$. In the rewritten form the spaces decide the boundaries, so a given input has exactly one decomposition instead of 2^(n-1).
Anchor the pattern at start and end when it is meant to describe the whole field. This removes the separate cost of restarting at every offset — a factor of n — though it does nothing about ambiguity by itself.
Bound the input before matching. Reject on length first. This is a strong control against polynomial cost and a weak one against exponential cost, so it is a companion to the rewrite, never a replacement.

Dangerous	Safe	Why the safe form has one path
`^([a-z]+)+$`	`^[a-z]+$`	one maximal run, no splits to choose between
`^([a-z]+ ?)+$`	`^[a-z]+( [a-z]+)*$`	separators fix every boundary
`^([0-9]+\|[0-9a-f]+)+$`	`^[0-9a-f]+$`	one branch, so no string is explained twice
`^(.,)[a-z]+$`	`^([a-z],)[a-z]+$`	the repeated part can no longer swallow separators

When the ambiguity is genuinely needed

Sometimes the language you must accept really does have two readings and you cannot flatten it away. Two tools remain.

Atomic grouping or a possessive quantifier tells the matcher to commit to the first way a section matched and discard the saved alternatives, so the search tree collapses at that node. It is effective and it is a semantic change: strings that only matched by re-splitting that section are now rejected. Use it deliberately, with tests that pin down what the pattern now accepts, not as a blind sprinkle.

Step outside pattern matching. If the field needs counting, nesting or cross-field agreement, no regular pattern expresses it correctly anyway, and the honest fix is a small hand-written scan or parser with an explicit loop — which also gives you an obvious cost bound and a useful error message.

Proving the rewrite

A rewrite you have not measured is a hope. Add, in the same change:

A growth test: the valid-looking prefix plus one defeating symbol at 20, 30 and 40 symbols, asserting a wall-clock bound at the largest. On the old pattern it fails; on the new one the times stay flat.
Equivalence tests: a corpus of strings that must still be accepted and a corpus that must still be rejected, so the rewrite cannot quietly change the contract — this is the test that catches an over-eager atomic group.
A review note stating which of the two loops you fixed. A reviewer who sees only an added anchor on a nested-quantifier pattern should reject the change.

The trap to avoid

The most common bad fix is cosmetic: adding an anchor, making a quantifier lazy, or trimming the input by a few symbols, then declaring victory because the one test input got faster. Laziness only reorders the search; an anchor removes a different factor; a small trim divides an astronomically large number by another astronomically large number. If you cannot state, in one sentence, why the new pattern has a single match path for every string, the defect is still there.

## The goal: exactly one way to match The repair is not 'make the pattern faster', it is **make the pattern unambiguous**. If every string that the pattern accepts has exactly one derivation through it, the matcher never has a saved alternative to return to, and failure is reached by the same short route as success. Ambiguity is the resource the attacker spends; rewriting removes the resource rather than rationing it. That gives a concrete acceptance criterion for the review: pick any string and ask whether the pattern could account for it in two different ways. If yes, you are not finished. ## The rewrite moves 1. **Flatten a quantifier under a quantifier.** `([a-z]+)+` accepts precisely the same strings as `[a-z]+`; the outer repetition adds no expressive power and all of the branching. Delete it. 2. **Make alternation branches disjoint.** `([0-9]+|[0-9a-f]+)+` has two branches that both accept digit runs. Either drop the redundant branch or give each a distinguishing prefix or class so no string satisfies both. 3. **Anchor a separated list on its separators.** Replace `^([a-z]+ ?)+$` with `^[a-z]+( [a-z]+)*$`. In the rewritten form the spaces decide the boundaries, so a given input has exactly one decomposition instead of 2^(n-1). 4. **Anchor the pattern** at start and end when it is meant to describe the whole field. This removes the separate cost of restarting at every offset — a factor of n — though it does nothing about ambiguity by itself. 5. **Bound the input before matching.** Reject on length first. This is a strong control against polynomial cost and a weak one against exponential cost, so it is a companion to the rewrite, never a replacement. | Dangerous | Safe | Why the safe form has one path | |---|---|---| | `^([a-z]+)+$` | `^[a-z]+$` | one maximal run, no splits to choose between | | `^([a-z]+ ?)+$` | `^[a-z]+( [a-z]+)*$` | separators fix every boundary | | `^([0-9]+\|[0-9a-f]+)+$` | `^[0-9a-f]+$` | one branch, so no string is explained twice | | `^(.*,)*[a-z]+$` | `^([a-z]*,)*[a-z]+$` | the repeated part can no longer swallow separators | ## When the ambiguity is genuinely needed Sometimes the language you must accept really does have two readings and you cannot flatten it away. Two tools remain. **Atomic grouping or a possessive quantifier** tells the matcher to commit to the first way a section matched and discard the saved alternatives, so the search tree collapses at that node. It is effective and it is a **semantic change**: strings that only matched by re-splitting that section are now rejected. Use it deliberately, with tests that pin down what the pattern now accepts, not as a blind sprinkle. **Step outside pattern matching.** If the field needs counting, nesting or cross-field agreement, no regular pattern expresses it correctly anyway, and the honest fix is a small hand-written scan or parser with an explicit loop — which also gives you an obvious cost bound and a useful error message. ## Proving the rewrite A rewrite you have not measured is a hope. Add, in the same change: - A **growth test**: the valid-looking prefix plus one defeating symbol at 20, 30 and 40 symbols, asserting a wall-clock bound at the largest. On the old pattern it fails; on the new one the times stay flat. - **Equivalence tests**: a corpus of strings that must still be accepted and a corpus that must still be rejected, so the rewrite cannot quietly change the contract — this is the test that catches an over-eager atomic group. - A **review note** stating which of the two loops you fixed. A reviewer who sees only an added anchor on a nested-quantifier pattern should reject the change. ## The trap to avoid The most common bad fix is cosmetic: adding an anchor, making a quantifier lazy, or trimming the input by a few symbols, then declaring victory because the one test input got faster. Laziness only reorders the search; an anchor removes a different factor; a small trim divides an astronomically large number by another astronomically large number. If you cannot state, in one sentence, why the new pattern has a single match path for every string, the defect is still there.

What does wrapping a section in an atomic group cost you?
Expressiveness. The matcher commits to the first way that section matched and throws away the alternatives, so any string that could only match by re-splitting that section is now rejected. The pattern is faster and accepts a smaller language. That is fine when you have tests pinning down the accepted set, and a silent contract change when you do not.
How do you prove the rewrite actually fixed it rather than moved it?
With a growth test in the same change: feed a valid-looking prefix plus one defeating symbol at 20, 30 and 40 symbols and assert a time bound at the largest size. Doubling between sizes means the ambiguity survives. Pair it with accept and reject corpora so the rewrite cannot change the contract unnoticed.
The field needs balanced nesting. Why is no rewrite of the pattern the answer?
Because balanced nesting is not expressible by a finite-state pattern at all; any pattern that appears to do it is approximating with a bounded depth. Write an explicit scan with a counter or a small parser instead. You get correctness, a clear linear cost bound, and a better error message than a rejected match.
Why is making the quantifiers lazy not a fix?
Laziness changes the order in which the alternatives are tried, not how many exist. On an input that ultimately fails, the matcher still has to eliminate every one of them, so the worst case is unchanged. It can move which inputs are fast and which are slow, which is worse than useless because it may hide the defect from the one test you had.

saying these in an interview costs you the question

Adds an anchor to a nested quantifier and calls it fixed
Switches quantifiers to lazy as the remedy
Sprinkles atomic groups without checking what is still accepted
Shortens the input limit slightly and declares the risk gone
Ships the rewrite with no test that grows the input length
Tries to match balanced nesting with a cleverer pattern

A shipped validation pattern backtracks catastrophically on crafted input: how do you rewrite it so that matching cannot blow up?

§ answer

basics

solid answer

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The goal: exactly one way to match

The rewrite moves

When the ambiguity is genuinely needed

Proving the rewrite

The trap to avoid

▾common follow-ups4 questions

▾red flags6 flags

The goal: exactly one way to match

The rewrite moves

When the ambiguity is genuinely needed

Proving the rewrite

The trap to avoid

answer

go deeper