skip to content

What kind of matching engine does java.util.regex use, and what is catastrophic backtracking?

level: seniorimportance: should knowfreq 55%

answer

  1. Java regex = backtracking NFA, not DFA
  2. NFA → backreferences & lookaround, but worst-case exponential
  3. Catastrophic backtracking: ambiguous nested quantifiers + failing input
  4. (a+)+ , (a|a)* are the textbook ReDoS shapes
  5. Fix: possessive (a++), atomic (?>...), rewrite, bound input length
  6. DFA (RE2) = linear time but no backreferences

basics

~20 s

Java's regex engine is a backtracking NFA, not a DFA. On certain patterns with nested or overlapping repetition it can try an exponential number of paths on a non-matching input, freezing the thread. This is catastrophic backtracking, the cause of regex denial-of-service (ReDoS).

solid answer

~50 s

java.util.regex compiles a pattern into a backtracking NFA: it explores match possibilities one path at a time and, when a path fails, it backtracks and tries the next alternative. This gives it powerful features (backreferences, lookaround) but means the work isn't bounded by input length. With patterns that have ambiguous nested quantifiers — classically (a+)+ or (a|a)* — the number of ways to split the input grows exponentially, so a long non-matching string like "aaaaaaaaaaaa!" can take seconds or hours. That's catastrophic backtracking, the basis of ReDoS attacks where attacker-controlled input pins a CPU. Mitigations: rewrite the regex to remove ambiguity, use possessive quantifiers (a++) or atomic groups ((?>...)) that forbid backtracking into a chunk, anchor and constrain the pattern, validate input length, and never feed untrusted input to a complex untested regex. A DFA engine (like RE2) avoids this by guaranteeing linear time but drops backreferences.

code

java · 7 lines
java
// Vulnerable: nested quantifiers -> exponential on a long failing input
Pattern bad = Pattern.compile("(a+)+$");
bad.matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!").matches(); // can hang for a long time

// Mitigated: possessive quantifier forbids backtracking into the run
Pattern good = Pattern.compile("a++$");
good.matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!").matches(); // fails fast

go deeper

for a junior

Aware that some regexes can be slow and that very complex patterns on big input should be avoided; not expected to know the NFA/DFA distinction in depth.

for a middle

Knows Java uses a backtracking engine and can name catastrophic backtracking as a risk with nested quantifiers.

for a senior

Explains NFA-backtracking vs DFA, identifies vulnerable patterns, and applies possessive quantifiers/atomic groups/rewrites; recognizes ReDoS in code review.

for a principal

Sets policy for untrusted-input regex (linear engine, timeouts, length caps), reasons about the engine trade-offs across services, and audits for ReDoS at scale.

## NFA vs DFA — the two ways to run a regex There are two classic strategies for executing a regex: - A **DFA (deterministic finite automaton)** processes the input one character at a time and is in exactly one state at each step. It runs in **linear time** in the input length, but it cannot support features like backreferences. Engines like RE2 / Go's regexp use this. - An **NFA (nondeterministic finite automaton), executed by backtracking**, tries one possible path through the pattern; if that path eventually fails, it *backtracks* — rewinds — and tries the next alternative. This supports rich features (backreferences `\1`, lookahead/lookbehind, lazy/greedy quantifiers) but its running time is **not bounded by input length** — it's bounded by the number of paths it explores. **Java's `java.util.regex` is a backtracking NFA.** That's why it has backreferences and lookaround, and also why it can blow up. ## How backtracking works (greedy quantifiers) A greedy quantifier like `a+` first grabs as many `a`s as it can, then gives them back one at a time if the rest of the pattern can't match. For a simple pattern this is cheap. The danger is **ambiguity**: when the same input can be divided among quantifiers in many different ways. ## Catastrophic backtracking — the exponential blow-up Consider `(a+)+$` against the input `"aaaaaaaaaaaaaaaaaaaa!"` (many `a`s then a `!`). - The outer `+` and the inner `+` can partition the run of `a`s in a huge number of combinations: 1 group of 20, or 19+1, or 18+2, or 10 groups of 2, etc. - The trailing `$` (or any character that *can't* match, like the `!`) forces the match to ultimately fail. - But before it can conclude failure, the engine must try **every** partition — and the number of partitions grows **exponentially** with the number of `a`s. So a 30-character input can require billions of steps and hang the thread for minutes. This is **catastrophic backtracking**. ## ReDoS — regular-expression denial of service If a server uses such a vulnerable regex on **attacker-controlled input** (e.g. validating a header, email, or URL), an attacker sends a crafted string that triggers the exponential path explosion, pinning a CPU core and starving the service. This is a real, common vulnerability class (ReDoS). Classic vulnerable shapes: - Nested quantifiers: `(a+)+`, `(a*)*` - Alternation with overlap under a quantifier: `(a|a)*`, `(.*a){n}` - Quantified groups that can match the same text multiple ways. ## Mitigations 1. **Rewrite to remove ambiguity.** Often the nested quantifier is unnecessary: `(a+)+` is equivalent to `a+`. 2. **Possessive quantifiers** `a++`, `a*+`, `a?+` — match greedily and **never give characters back** (no backtracking into them). 3. **Atomic groups** `(?>...)` — once the group matches, its internal backtracking is discarded, cutting the explosion. 4. **Anchor and bound** the pattern; constrain character classes; **limit input length** before matching. 5. **Never run a complex, untested regex on untrusted input.** Test pathological inputs; consider a linear-time engine (RE2/`re2j`) for untrusted data, accepting the loss of backreferences. 6. Some platforms add a **matching timeout**; plain `java.util.regex` has none, so guard externally. ## Key takeaways - Java regex = **backtracking NFA**, not DFA → powerful but worst-case super-linear/exponential. - The blow-up comes from **ambiguous nested/overlapping quantifiers** plus an input that ultimately fails. - Fix with possessive quantifiers / atomic groups / rewrites, and treat untrusted input as hostile.

  • What does a possessive quantifier like a++ do?
    It matches greedily and then refuses to give any characters back during backtracking. This prunes the search space, so a pattern that would otherwise explode fails fast — at the cost that it may fail some matches a greedy quantifier would have found.
  • Why does a DFA engine avoid catastrophic backtracking, and what does it give up?
    A DFA tracks all possible states simultaneously and scans the input once, guaranteeing time linear in input length. It gives up features that need backtracking — primarily backreferences and some lookaround.

saying these in an interview costs you the question

  • Believing Java uses a DFA / always linear-time engine
  • Assuming a short input can't cause a long hang (the input is short, the path count is huge)
  • Thinking adding more capturing groups speeds it up
  • Running a complex regex on untrusted input without bounding length or rewriting
  • Confusing lazy quantifiers (?) as a cure — they can backtrack too

context

resolving links…