skip to content

Which shape in a regular-expression validation pattern makes its matching work grow exponentially with the length of one input field?

level: middleimportance: must knowfreq 72%

answer

  1. ambiguity, not input size
  2. one run, many legal splits
  3. a quantifier inside a quantifier
  4. branches that accept the same text
  5. failure forces every path

basics

~20 s

Ambiguity: a quantifier nested inside another quantifier, or alternation branches that can match the same text. A backtracking matcher then has exponentially many ways to split one input, and on a failing input it tries them all.

solid answer

~40 s

The dangerous property is not length or complexity, it is **ambiguity**: the pattern can match one string in more than one way. Two shapes produce it. A quantifier applied to an already-quantified group, such as `([a-z]+)+`, lets a run of n letters be cut into pieces in any of the 2^(n-1) possible ways. Alternation branches that overlap under a quantifier, such as `([0-9]+|[0-9a-f]+)+`, give every piece a second way to be matched. A backtracking matcher takes the first path and, when that path fails, returns to the most recent choice point and tries the next, so the cost is the number of paths it explores. That number stays small while a match succeeds early and becomes astronomical when the overall match must fail.

code

pseudocode · 12 lines
pseudocode
# outer quantifier over an already-quantified group: (inner+)+
match_repeat(text, i):
    if i = length(text):
        return rest_of_pattern_matches(i)

    # every piece length is a separate branch to explore
    for len from longest_inner_match(text, i) down to 1:
        if match_repeat(text, i + len):
            return true
        # this split failed - undo it and try a shorter piece

    return false   # no split from position i works; caller tries another

go deeper

for a junior

Recall the headline: a small pattern can hang a service, and the trigger is a pattern that can match the same text in more than one way, not merely a big input.

for a middle

Explain the mechanism: choice points, saved alternatives, and cost measured as the number of match paths. Point at ([a-z]+)+ and say why a run of n letters has 2^(n-1) splits.

for a senior

Show that you can spot the shape in a code review and construct the input that proves it, then reason about what it does to a request worker pool rather than to one benchmark.

for a principal

Frame it as an availability class, not a bug: which patterns run on untrusted input, who is allowed to author them, and what the platform does so that one bad pattern cannot exhaust shared capacity.

## What a backtracking matcher actually does A backtracking matcher walks the pattern and the input together. Wherever the pattern offers a choice — how many times a quantifier repeats, which branch of an alternation to take — it picks one option, remembers the others, and carries on. If the rest of the pattern then fails to match, it returns to the most recent remembered choice and tries the next option. Its running cost is therefore not the length of the input and not the length of the pattern: it is **the number of distinct match paths it explores before it can announce a verdict**. That reframes the whole problem. A pattern is dangerous when the input can be matched in many ways, because every one of those ways is a path the matcher may have to walk. ## The two shapes that create many paths **A quantifier under a quantifier.** In `([a-z]+)+`, the inner `+` decides how long each piece is and the outer `+` decides how many pieces there are. A run of n letters can be cut into consecutive non-empty pieces in 2^(n-1) ways (one binary decision at each of the n-1 gaps), and every one of them satisfies the pattern equally well. **Overlapping alternation under a quantifier.** In `([0-9]+|[0-9a-f]+)+`, both branches accept a run of digits, so every piece has two justifications. Even a milder overlap multiplies paths: an alternation of a one-symbol branch and a two-symbol branch repeated over n symbols has Fibonacci-many parses, which still grows by a constant factor per added symbol. | Shape | Example | Ways to match a run of n symbols | Growth per extra symbol | |---|---|---|---| | Single quantifier | `[a-z]+` | 1 | none | | Quantifier under a quantifier | `([a-z]+)+` | 2^(n-1) | doubles | | Overlapping branches under a quantifier | `([0-9]+\|[0-9a-f]+)+` | at least 2^(n-1) | doubles | | Disjoint branches under a quantifier | `([0-9]+\|[g-z]+)+` | 1 | none | The last row is the point of the whole table: alternation is not the problem, **overlap** is. If no string can be matched by two branches, the matcher never has a second option to return to. ## Why the paths get walked A backtracking matcher stops the moment one path succeeds. So an ordinary valid input is fast — the first split it tries works. The exhaustive walk happens only when **no** path succeeds, because failure can only be declared after every alternative has been eliminated. The costly input is therefore one that looks valid for a long prefix and then defeats the rest of the pattern: a long run of letters followed by one symbol the pattern cannot accept. ## From a pattern to an outage The growth is what makes this an availability problem rather than a performance annoyance. Each extra symbol in the crafted field **doubles** the work. Twenty extra symbols is a factor of 2^20, about a million. A field that returns in a few milliseconds at 25 symbols will not finish this week at 45. One request then occupies one worker for an unbounded time; a handful of identical requests drains the pool, healthy requests queue behind them, and the service fails its own health checks while its processor sits pinned. Nothing in the logs says 'regular expression' — it looks like a generic saturation incident. ## What is not the cause - **Input length on its own.** An unambiguous pattern over a megabyte of input is linear and boring. - **A long or visually complicated pattern.** Some of the worst offenders are under twenty characters. - **A pattern that passes its tests.** Ordinary test data matches, and matching is the fast case, so a test suite of valid and obviously-invalid examples will never see this. - **Quantifier greediness.** Making a quantifier lazy changes the order in which paths are tried, not how many exist. Not every matching strategy backtracks; some explore all alternatives simultaneously and never exhibit this behaviour at all, but that comparison belongs with engine architecture rather than with the pattern shape. ## Reading a pattern for this in three steps 1. Find every quantifier. For each, ask whether anything inside it is also quantified. 2. Find every alternation under a quantifier and ask whether two branches can accept the same string. 3. For each hit, construct the killer input: a long run that satisfies the ambiguous part, plus one trailing symbol that makes the whole match fail. Time it at 20, 30 and 40 symbols and watch for doubling.

  • Roughly how many ways can a matcher split a run of n identical symbols across a quantifier nested in a quantifier?
    2^(n-1). Between the n symbols there are n-1 gaps, and each gap is independently either a piece boundary or not, so the run has 2^(n-1) decompositions into consecutive non-empty pieces. Every one satisfies the pattern, so every one is a path the matcher may have to walk before it can declare failure.
  • Why does anchoring the pattern at both ends not remove the exponential shape?
    Anchoring removes a different cost: without it the matcher restarts the whole attempt at each of the n starting offsets, which multiplies the work by n. The ambiguity inside the pattern is untouched, so an anchored `^([a-z]+)+$` still explores 2^(n-1) splits on a failing input. Anchoring is worth doing, but it turns an exponential-times-n cost into an exponential one.
  • Two alternation branches sit under a quantifier. What makes that pair safe rather than dangerous?
    Disjointness. If no string is accepted by both branches, each piece of the input has exactly one justification and the matcher never has a saved alternative to return to. Give each branch a distinguishing first symbol or a disjoint character class and the repeated group stops multiplying paths, even though the alternation is still there.

A clerk is asked whether a shelf of identical boxes can be grouped into valid batches. If any grouping counts, the clerk finds one instantly; only when the answer is no must every possible grouping be tried before reporting failure.

saying these in an interview costs you the question

  • Thinks any sufficiently long input makes any pattern slow
  • Believes only a long or complicated pattern can be dangerous
  • Says making the quantifier lazy removes the blow-up
  • Assumes a pattern that passes its test suite is safe
  • Names nested quantifiers only, missing overlapping alternation