Regex series: 1. Syntax, the Java API and validation exercises · 2. Exercises: network configs, logs to CSV, lookbehind, duplicate lines · 3. The engine, backtracking and catastrophic backtracking · 4. ReDoS in Java: outages and defences
Most of the time regex is write-and-forget. Then a 40-character “full name” pins a thread at 100% CPU for seconds, with no exception and no log; a few dozen such requests drain the thread pool. That’s ReDoS (Regular expression Denial of Service), and its root is how Java’s regex engine (and JavaScript’s, Python’s, PCRE) works: backtracking. By the end you’ll understand how the engine runs and be able to spot and fix dangerous patterns; syntax is in part 1, real outages and defences (a home-made timeout, input limits, RE2/J) in part 4.
1. How a backtracking engine works
Key idea: the engine walks left to right, remembers every choice point, and on failure returns to the latest one; the first path that reaches the end of the pattern is the match.
1.1. One character at a time, left to right
Key idea: java.util.regex runs a depth-first search over a tree of choices (textbooks call it an “NFA engine”) and accepts the first option that succeeds, so alternation picks the first branch that matches, not the longest.
- Start at position 0 and compare the pattern element by element with the input.
- At a choice point (a
|branch, a quantifier that could take more or fewer): take the first option and remember the rest. - On failure, go back (backtrack) to the latest choice point and try its next option.
- Out of options? Move the start to position 1, 2, … (what
find()does). - The first path to reach the end of the pattern is the match, not the “longest” one.
Step 5 explains the slide’s car|carpet example:
Pattern.compile("car|carpet").matcher("carpet and car").results().map(MatchResult::group).toList();
// [car, car]
Pattern.compile("\\b(?:car|carpet)\\b").matcher("carpet and car").results().map(MatchResult::group).toList();
// [carpet, car]
This is the leftmost, first alternative wins rule; POSIX engines (grep, awk) follow leftmost-longest and return “carpet”. Fixes in Java: put the longer branch first (carpet|car), or add \b on both sides like the slide: the car branch hits the boundary between “r” and “p” (both \w), fails, and the engine moves on to carpet.
1.2. Backtracking by example
Key idea: when a branch fails, the engine returns to the latest choice point and tries the next branch. The state it needs to go back lives on the call stack.
Pattern \bapple(?:past(?:ry|e)|pie)\b: on “applepaste”, ry fails at “e”, so the engine backs up and tries e; on “applepie”, past fails at “i”, so it tries pie. Result: [applepaste, applepie].
flowchart LR
S[apple] --> P[past]
S --> Q[pie]
P --> R[ry]
P --> E[e]
R -->|fail, go back| E
E --> B[word boundary]
Q --> B
The engine is a set of nodes calling each other recursively, so “where am I, which branch” lives on the call stack (part 4 covers StackOverflowError).
Step by step on “Twenty popular recipes to make applepaste”
Input: “Twenty popular recipes to make applepaste” and “Popular applepie recipe”. Skip the starting positions that fail immediately at \ba (most fail on the first character, so they’re cheap). For “applepaste”:
| Step | Pattern part | Remaining input | Result |
|---|---|---|---|
| 1 | \b then apple |
applepaste | matches 5 characters |
| 2 | branch 1: past |
paste | matches “past” |
| 3 | sub-branch 1: ry |
e | “e” is not “r”, fail, go back to the latest choice point |
| 4 | sub-branch 2: e |
e | matches |
| 5 | \b |
(end of line) | matches, the match is “applepaste” |
For “applepie”: apple matches, branch 1 past fails immediately on “i” versus “a”, the engine backtracks into branch 2 pie, which matches, then \b matches.
1.3. Greedy, lazy, possessive and atomic groups
Key idea: the three quantifier kinds differ in the order they try options and whether they allow going back. Possessive quantifiers and atomic groups cut backtracking entirely, but can stop the pattern from matching.
| Kind | Syntax | Behaviour | <.+> on <b>bold</b> |
|---|---|---|---|
| Greedy | *, +, ?, {n,m} |
take as much as possible, give back one character at a time on failure | one match: <b>bold</b> |
| Lazy | *?, +?, ?? |
take as little as possible, take one more at a time on failure | <b>, </b> |
| Possessive | *+, ++, ?+ |
take as much as possible and never give back |
Both greedy and lazy can backtrack a lot. Better to say exactly what you mean: <[^>]+> (anything but >) leaves nothing to backtrack into. An atomic group (?>...) throws away every choice point inside it once it has matched; X*+ is equivalent to (?>X*).
Pattern.matches("a+a", "aaa"); // true: a+ gives back one "a" for the final a
Pattern.matches("a++a", "aaa"); // false: a++ eats all three and never gives back
Pattern.matches("\".*+\"", "\"abc\""); // false: .*+ also eats the closing "
Pattern.matches("\"[^\"]*+\"", "\"abc\""); // true
2. Two engine families: backtracking and automata
Key idea: an automaton engine walks the input exactly once, so it’s always linear; the price is losing backreferences and lookaround.
Automaton (a Thompson NFA, a lazily built DFA): a state machine that tracks every possible state at once, in O(pattern size × input size) time. Examples: RE2 (C++, from Google), RE2/J (its Java port), Go’s regexp, Rust’s regex crate, the default mode of grep.
Dropped: backreferences (\1), lookahead/lookbehind, possessive quantifiers and atomic groups (not needed anyway). Rust supports \b and anchors, but not general lookaround.
3. Catastrophic backtracking
Key idea: when a match fails, the engine must try every way to match; if the pattern allows several ways to split the same stretch of input, the count grows exponentially (or as a high-degree polynomial).
3.1. Why some patterns run in exponential time
Key idea: the warning sign is two different ways for one stretch of input to match the same part of the pattern.
Take ^(a+)+$ on n a’s followed by !: to conclude failure, the engine tries every way of splitting the a’s into a+ groups ((aaaa), (aaa)(a), (aa)(aa), …): 2^(n-1) ways.
Three common shapes:
- Nested quantifiers where the inner and outer part can match the same character:
(a+)+,(\w*)*,(\w+\s?)*. - Overlapping alternation:
(a|aa)+,(\d+|\w+)*(\wincludes\d). - Adjacent overlapping parts plus a failure point at the end:
.*.*=.*,\s+$withfind(). Polynomial (n², n³), but input of a few dozen KB is still enough to hang.
3.2. Measured on JDK 21: a surprise
Key idea: modern JDKs memoize */+ group loops, so many classic examples are instant; bounded repetition, backreferences, three-level nesting and polynomial shapes still blow up.
Measured on JDK 21 (Apple Silicon, java File.java, crude timing loops, no JMH): read as orders of magnitude.
- 0 ms up to n = 30 (input
"a".repeat(n) + "!"):(a+)+b,^(\w*)*$(the slide’s example),(a|aa)+b,^(\w+\s?)*$. From JDK 9 (as far as I know) the engine memoizes (remembers computed results): once it knows “this loop starting at position i fails”, it doesn’t try again. - Still exponential:
^(a+){2,30}$,^(a+)+\1$,((a+)+)+$, and two sign-up form patterns using{1,20}(10 to 16 seconds at n = 30). Two extra characters multiply the time by about four: the 2^n shape exactly. - Polynomial (memoization doesn’t help):
.*.*=.*takes 50–87 s on 5,000 characters;\s+$takes 630 ms on 20,000 spaces.
Full measurement tables on JDK 21
Classic patterns, input "a".repeat(n) + "!":
| Pattern | n = 20 | n = 26 | n = 30 |
|---|---|---|---|
(a+)+b |
0 ms | 0 ms | 0 ms |
^(\w*)*$ (the slide’s example) |
0 ms | 0 ms | 0 ms |
(a|aa)+b |
0 ms | 0 ms | 0 ms |
^(\w+\s?)*$ |
0 ms | 0 ms | 0 ms |
Patterns that still explode on JDK 21:
| Pattern | n = 20 | n = 24 | n = 26 | n = 28 | n = 30 |
|---|---|---|---|---|---|
^(a+){2,30}$ (bounded repetition) |
9 ms | 152 ms | 622 ms | 2.4 s | 9.7 s |
^(a+)+\1$ (with a backreference) |
12 ms | 173 ms | 692 ms | 2.8 s | 11.4 s |
((a+)+)+$ (three levels of nesting) |
44 ms | 745 ms | 3.1 s | ||
^([a-zA-Z0-9]+[._-]?){1,20}@[a-z]+\.com$ |
18 ms | 258 ms | 1.0 s | 4.1 s | 15.7 s |
^(\w+\s?){1,20}$ |
16 ms | 219 ms | 869 ms | 3.4 s | 13.2 s |
The last two rows are “normal-looking” sign-up form patterns: the author added a {1,20} limit “for safety” and pushed the pattern out of the zone memoization protects.
Polynomial shapes (input is n x characters, or n spaces followed by x, with find()):
| Pattern | n = 1,000 | n = 5,000 | n = 20,000 |
|---|---|---|---|
.*.*=.* |
0.5–0.7 s | 50–87 s | (gave up, too slow) |
\s+$ |
6 ms | 76 ms | 630 ms |
Exercises
Exercise 1: Fix three vulnerable patterns
Task: for each pattern running in the service, give a hostile input, explain why it’s slow, and write a fix that keeps the intent.
- Internal email validation:
^([a-zA-Z0-9]+[._-]?){1,20}@[a-z]+\.com$ - Detecting trailing whitespace in a comment, with
find():\s+$ - Filtering
key=valueconfig lines, withfind():.*.*=.*
Solution to Exercise 1 (measured on JDK 21)
- Hostile input: 30 a’s followed by
!. The group[a-zA-Z0-9]+[._-]?has an optional separator, so a run of letters can be split across iterations in a huge number of ways, and{1,20}isn’t protected by memoization. Measured: 15.7 s. The fix^[a-zA-Z0-9]+(?:[._-][a-zA-Z0-9]+)*@[a-z]+\.com$requires a separator between letter runs, so only one split remains: 0 ms. It still acceptsjohn.doe@acme.comanda-b_c@x.com, and now also rejectsa..b@x.comand.a@x.com, a reasonable tightening. If you need the 20-segment cap, check the length separately. - Hostile input: 20,000 spaces followed by an
x. From each space,\s+eats the rest of the run and then$fails: O(n²), measured at 630 ms. Fix:(?<!\s)\s+$, which may only start at the first whitespace of a run (0 ms), or drop the regex:!s.equals(s.stripTrailing()). - Hostile input: a 5,000-character line with no
=. Three.*share the same stretch of input at every starting position: O(n³), measured at 87 s. Fix:^[^=]*=.*, or simplyline.indexOf('=') >= 0.
Remember
- Explain why
car|carpeton “carpet” returns “car”, and the two fixes. - Tell greedy, lazy and possessive apart; know when possessive changes the meaning.
- Know when to pick RE2/J, and what you lose.
- Spot the three shapes behind catastrophic backtracking and fix them by removing ambiguity.
- Explain why
(a+)+bis fast on JDK 21 while^(\w+\s?){1,20}$still blows up.
Interview questions
Mid
How do greedy, lazy and possessive quantifiers differ?
Greedy takes as much as possible then gives back, lazy takes as little as possible then takes more, possessive takes as much as possible and never gives back.
Greedy and lazy can reach the same set of matches but try them in a different order, so they pick different matches (<.+> versus <.+?>). Possessive can change the result (".*+" never matches) but cuts backtracking completely.
Why does car|carpet on “carpet” return “car”?
Because Java’s backtracking engine tries branches in order and accepts the first one that leads to a match; it doesn’t look for the longest.
A POSIX engine follows leftmost-longest and would return “carpet”. Fix: put the longer branch first (carpet|car) or anchor with \b(?:car|carpet)\b.
What is catastrophic backtracking, and how do you spot a dangerous pattern?
It’s when the number of paths the engine must try grows exponentially (or as a high-degree polynomial) with input length, usually when the match ultimately fails.
Warning signs: the same stretch of input can match the same part of the pattern in several ways: nested quantifiers ((a+)+, (\w+\s?)*), overlapping alternation ((a|aa)+, (\d+|\w+)*), or adjacent .* (.*.*=.*). Fix it by removing the ambiguity: negated character classes, mandatory separators, possessive quantifiers or atomic groups.
What is an atomic group (?>...) for?
To stop useless backtracking: once the group has matched, the engine discards every choice point inside it and never goes back in to try alternatives.
X*+ is exactly (?>X*). The catch: the pattern may stop matching at all if what follows needs characters back from the group, so use it only when the boundary is clear.
Senior
How does RE2 differ from java.util.regex? When would you pick RE2/J?
RE2 builds an automaton and walks the input once, so it’s always linear and can’t be ReDoS’d; in exchange it has no backreferences or lookaround.
I’d pick RE2/J when the pattern or the input comes from outside: users writing their own search or alert regexes, WAF rules, untrusted imported data. For reviewed internal patterns on length-limited input, the JDK engine is enough.
Textbook ReDoS examples like (a+)+b run instantly on your JDK 21. Is Java immune to ReDoS now?
No. Modern JDKs only memoize */+ group loops, so the classic examples don’t reproduce, but many other shapes still blow up.
Bounded repetition ((X+\s?){1,20}), backreferences and three-level nested quantifiers are still exponential; .*.*=.* or \s+$ with find() are still quadratic or cubic. I measured 13 seconds for ^(\w+\s?){1,20}$ on 30 characters. You have to test your actual pattern with hostile input, or use SonarQube or CodeQL to flag it.
Useful phrases for interviews
- “A backtracking engine explores one path at a time and goes back to the last choice point when it fails.”
- “Java takes the first alternative that works, not the longest, so I put the more specific branch first.”
- “The fix isn’t a different quantifier; it’s removing the ambiguity so each input has exactly one way to match.”
- “A negated character class says what I mean and leaves nothing for the engine to backtrack into.”
- “Possessive quantifiers cut backtracking, but they change the semantics, so I only use them when the boundary is certain.”
- “RE2 trades backreferences and lookaround for a linear-time guarantee.”
- “Modern JDKs memoize star and plus loops, so the textbook examples are fast, but bounded repetition still blows up.”
- “Every two extra characters quadrupled the time, which is the exponential signature.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.