What is catastrophic backtracking (ReDoS) in regex, how do quantifiers cause it, and how do you prevent it in a Java service?
answer
- Danger shapes: (a+)+, (a|aa)+, (.*)*
- Fails-near-miss input → exponential partition search
- Java regex = backtracking → vulnerable; no built-in timeout
- Fix order: unambiguous pattern → possessive/atomic → external timeout
- Negated class [^"]* beats .* between delimiters
- Never compile attacker regex on attacker input
basics
~20 sCatastrophic backtracking happens when nested or overlapping quantifiers give the engine exponentially many ways to match, so a crafted input makes one regex run effectively forever. An attacker can use this to freeze a thread — that's ReDoS. You prevent it with possessive quantifiers, atomic groups, or unambiguous patterns.
solid answer
~50 sCatastrophic backtracking occurs when a pattern has nested or adjacent quantifiers whose matches overlap — classic shapes are `(a+)+`, `(a|aa)+`, or `(.*)*`. For an input that almost matches but ultimately fails, the engine must try every way of partitioning the input among those quantifiers, which grows exponentially. A small malicious string can pin a CPU for seconds or minutes; exposed in a request path this is a denial-of-service vector called ReDoS. Java's `java.util.regex` is a backtracking engine, so it is vulnerable. Mitigations, in order of preference: (1) rewrite the pattern to be unambiguous — use negated character classes like `[^"]*` instead of `.*`, anchor it, avoid nested quantifiers; (2) make the inner quantifier possessive (`(a+)++`) or wrap it in an atomic group `(?>a+)+` to kill the redundant backtracking; (3) run user-supplied or risky regexes with a timeout — e.g. match on a separate thread you can interrupt, since Java has no built-in regex timeout. Never compile attacker-controlled regex patterns against attacker-controlled input.
go deeper
Has heard of slow/runaway regexes; may not yet recognize the danger shapes or the security implication.
Identifies nested-quantifier patterns as risky and knows possessive/atomic groups can help.
Diagnoses catastrophic backtracking from the pattern, reproduces it, and applies negated classes/atomic groups; understands ReDoS as a DoS vector.
Sets organizational policy: bans ambiguous patterns in code review, mandates anchoring/negated classes, enforces timeouts for any untrusted-pattern path, and chooses a non-backtracking engine where untrusted input demands it.
## Background: backtracking engines Java's `java.util.regex` is a **backtracking** (NFA-style) engine: when a quantifier could match several lengths, the engine picks one, proceeds, and if a later part fails it returns to try a different length. This is what makes greedy/lazy/possessive modes meaningful. It is also the root of the problem. ## How exponential blow-up happens Consider `(a+)+$` (a one-or-more of a's, grouped, repeated one-or-more, anchored at end). Feed it `"aaaaaaaaaaaaaaaaaaaa!"` — twenty a's then a `!` that prevents the `$` from matching. The engine asks: how do I split twenty a's between the **inner** `a+` and the **outer** `()+`? It could be one group of 20, or 10+10, or 5+5+5+5, or 19+1, ... There are exponentially many partitions (related to compositions of the integer 20). Because the final `!` makes every partition ultimately fail, the engine **tries them all** before giving up. Twenty a's is fast; forty is noticeable; sixty hangs. Time is roughly O(2^n). The general danger signature is **two quantifiers that can match the same characters**: nesting (`(x+)+`), an alternation where branches overlap (`(a|a)*`, `(a|aa)*`), or `(.*)*`. The overlap is what creates multiple equivalent partitions. ## ReDoS: the security angle When such a regex sits on a request path — validating an email, a header, a search query — an attacker sends a short input engineered to maximize backtracking and pins the worker thread at 100% CPU. With a few requests they exhaust the thread pool: a **Regular-expression Denial of Service**. It needs no large payload, just a clever small one, which is why it slips through size limits. ## Mitigations, best first **1. Make the pattern unambiguous (preferred).** - Replace `.*` between delimiters with a **negated class**: `"[^"]*"` instead of `".*"`. The negated class can match each character exactly one way, so there's no partition explosion. - **Anchor** patterns (`^...$`) so the engine doesn't retry at many start positions. - Avoid nesting quantifiers and overlapping alternations. **2. Possessive quantifiers / atomic groups.** - Convert the inner repetition to possessive: `(a+)++$`, or wrap it atomically: `(?>a+)+$`. Once the inner `a+` consumes its run it won't hand characters back to be re-partitioned, collapsing the search to linear time. This is a surgical fix when you can't restructure the pattern. **3. Run with a timeout (defense in depth).** - Java has **no** built-in regex timeout. The common pattern is to run the match on an executor and `cancel`/interrupt it, or wrap the `CharSequence` so `charAt` throws after a deadline (forcing the engine to abort). Treat this as a backstop, not the primary fix. **4. Don't compile untrusted patterns.** Never let users supply the regex *and* the subject text. If you must accept user patterns, run them sandboxed with strict timeouts and input-size caps, and consider a non-backtracking engine (e.g. RE2/J) for that path. ## Operational practice - Lint regexes in code review for the danger shapes above; some static analysers flag them. - Keep validation patterns simple and anchored; prefer parsing libraries over hand-rolled mega-regexes for structured input (URLs, emails). - Cache compiled `Pattern`s (they're thread-safe) so compilation cost isn't confused with match cost. ## Summary mental model The enemy is **ambiguity**: more than one way for the quantifiers to carve up the same input. Eliminate the ambiguity (negated classes, atomic groups, anchoring) and the engine has nothing to explore.
- Why is replacing .* with [^delimiter]* a stronger fix than just adding a timeout?The negated class removes the ambiguity that causes exponential backtracking, so the match is linear by construction; a timeout only caps the damage of a still-pathological pattern and adds thread-management complexity.
- Does Java's java.util.regex have a way to time out a match?No built-in option. You run the match on an interruptible thread/executor, or wrap the CharSequence so charAt throws after a deadline, forcing the engine to abort.
- Why doesn't the blow-up usually appear on inputs that match successfully?On a clean match the greedy choice often works on the first try; the exponential exploration is triggered when the input almost matches but a trailing character forces the engine to exhaust all partitions before failing.
saying these in an interview costs you the question
- Thinking input-size limits alone stop ReDoS (a tiny crafted input suffices)
- Assuming Java has a built-in regex timeout
- Reaching only for possessive quantifiers and never restructuring the ambiguous pattern
- Believing a successful-match benchmark proves safety — the blow-up is on near-miss failures