skip to content

Why does a backtracking-prone validation pattern hang on a long near-match input rather than on an obviously wrong one?

level: middleimportance: should knowfreq 46%

answer

  1. cost depends on the verdict
  2. the first success ends the search
  3. no match means eliminate everything
  4. long valid prefix, one bad symbol
  5. almost-valid is the expensive band

basics

~20 s

A backtracking matcher stops at the first path that succeeds, so only failure forces it to eliminate every alternative. An input that satisfies the ambiguous part for a long prefix and then defeats the rest maximises the number of paths to eliminate.

solid answer

~40 s

Cost equals paths explored, and paths are only fully explored on a verdict of no match. An obviously wrong input fails almost immediately — the first symbol does not fit, so there is nothing to retry. A **near-match** input is the opposite: a long run that the ambiguous part accepts in exponentially many ways, followed by one symbol that makes the overall match impossible. The matcher must try every split of the run before it can say no. So the attacker's payload is not garbage, it is a valid-looking field with one poisoned symbol appended. This is also why ordinary test suites miss the problem: valid inputs match, and matching usually finds a path early.

go deeper

for a junior

Remember the counterintuitive part: the dangerous input looks almost correct. Garbage is rejected instantly; a nearly valid value with one wrong character at the end is what costs time.

for a middle

Explain why the verdict decides the cost: success exits at the first working path, failure must eliminate all of them, so the worst input maximises the number of surviving alternatives.

for a senior

Show how you would prove it on a running system: a growth test at several input lengths with a time bound, and an awareness that a validator on a public form lives on the failure path.

for a principal

Consider where adversarial inputs enter your platform at all, and whether the pattern-bearing code paths are the ones that see untrusted, almost-valid data most often.

## Success is cheap, failure is expensive A backtracking matcher explores match paths one at a time and returns the moment one of them works. Two verdicts therefore cost very different amounts: - **Match.** The matcher stops at the first successful path. With the usual longest-first ordering of a greedy quantifier, a well-formed input is normally accepted on the first or second path tried. - **No match.** There is no early exit. The matcher can only report failure once it has eliminated **every** remaining alternative at every choice point it saved. An ambiguous pattern is one with astronomically many alternatives, so the price of the second verdict is astronomically higher than the price of the first. ## Anatomy of the payload The input that maximises cost has three parts, in this order: 1. **A prefix that the ambiguous section accepts**, and accepts in many ways — typically a long run of symbols the repeated group matches, so the number of splits grows with the run length. 2. **Nothing that lets the matcher commit early**: no separator or symbol that forces one split and discards the others. 3. **One symbol at the end that makes the whole pattern fail** — a character outside every class, or simply a symbol that cannot satisfy the required tail or the end-of-input anchor. Against `^([a-z]+)+$`, forty lowercase letters followed by a single `!` is exactly this: forty letters that the group loves, and one symbol that the anchored end refuses. Against `^([0-9]+|[0-9a-f]+)+$`, a long digit run followed by `z` does the same job. | Input | Verdict | Work | |---|---|---| | `!aaaa...` | no match | trivial: fails at the first symbol, nothing saved to retry | | `aaaa...a` (all letters) | match | small: the first split tried succeeds | | `aaaa...a!` | no match | exponential: every split of the letter run must be eliminated | ## Why the poisoned symbol can sit anywhere after the ambiguity The symbol does not have to be literally last. What it has to do is make the **overall** match impossible at a point **after** the ambiguous section, so that the matcher is forced back into that section to look for another split. If the pattern ends with an anchor, appending one bad symbol is the simplest way; if the pattern requires a fixed suffix, omitting or corrupting that suffix does the same. If the ambiguity sits in the middle of the pattern, the poison goes after it, not before: anything that fails **before** the ambiguous part is reached costs nothing. ## Why the test suite never caught it Most test data is either clearly valid or clearly invalid, and both are cheap: - Valid examples match, and matching finds a path early. - Clearly invalid examples usually diverge from the pattern almost immediately, so few alternatives were ever saved. The expensive region is a narrow band that ordinary examples do not visit: *almost* valid. An adversary looking for it does not need source access either. Probing a public endpoint with progressively longer valid-looking values and watching response time reveals the doubling directly. ## Consequences for how you test and defend - **Write the adversarial case deliberately.** For every pattern that touches untrusted input, add a test that feeds a growing valid-looking prefix plus one defeating symbol, at 20, 30 and 40 symbols, with a time bound. Doubling between those points is the signature. - **Do not reason from the success case.** 'It returns in under a millisecond on realistic data' says nothing, because realistic data takes the cheap verdict. - **Fuzz in the right shape.** Random bytes rarely produce a near-match; generate from the pattern's own alphabet and then corrupt the tail. - **Remember which verdict your endpoint actually asks for.** A validator on a public form spends its life on the failure path, because that is where rejected submissions go — which is precisely the expensive path. An important limit on the model: a successful match is *usually* cheap, not guaranteed cheap. If the successful path happens to be ordered late, the matcher walks many failing paths before finding it. The reliable attack is the failing input, but 'it matched, therefore it was fast' is not a rule you can lean on.

  • The ambiguous group sits in the middle of the pattern, not at the end. Where does the defeating symbol go?
    After it. The point is to force the matcher back into the ambiguous section, which only happens if the rest of the pattern fails once that section has been satisfied. A symbol that breaks the match before the ambiguous group is reached costs nothing, because no alternatives have been saved yet.
  • Can an input that does match ever be slow?
    Yes, though it is not the reliable attack. The matcher pays for every path it walks before the successful one, so if the ordering of choices puts the working split late, a matching input is also expensive. Treat 'it matched quickly on our data' as weak evidence, not as proof that the pattern is linear.
  • How would you detect this from outside, with no access to the pattern?
    Send the same field with valid-looking values of increasing length, each with one trailing symbol likely to be rejected, and plot response time against length. A pattern with this defect shows time roughly doubling per added symbol, while a healthy validator stays flat or grows linearly.

saying these in an interview costs you the question

  • Thinks random junk input is the dangerous case
  • Says only inputs that match can be slow
  • Believes a fast valid case proves the pattern is linear
  • Puts the defeating symbol before the ambiguous section
  • Assumes an attacker needs the pattern source to find this