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
ReDoS (Regular expression Denial of Service) is when one request with a few dozen carefully chosen characters pins a thread at 100% CPU for seconds, with no exception and no error log. This post covers two real outages, the attack surface of a Java backend, the layers of defence when java.util.regex has no timeout, and the slide’s best practices re-checked with measurements. Read part 3 first to see why the backtracking engine blows up.
At a glance:
flowchart TD
A["Thread RUNNABLE stuck in regex"] -->|"Spot it with"| B["Thread dump"]
B --> C["Defense in layers"]
C --> D["Pattern with one match path"]
C --> E["Limit length before regex"]
C --> F["CharSequence with deadline"]
C --> G["Untrusted input: RE2/J"]
C --> H["Character class over alternation"]
1. ReDoS in production
Key idea: one ambiguous pattern on a hot path is enough to take down a large system. Stack Overflow was down 34 minutes because of \s+$; Cloudflare lost global traffic for 27 minutes because of .*.*=.*.
- Stack Overflow, July 2016: one post had ~20,000 consecutive whitespace characters, and the trimming code used
^[\s]+|[\s]+$. About 200 million steps per page render, and that post was linked from the home page. - Cloudflare, July 2019: a WAF rule (Web Application Firewall, a filter in front of HTTP traffic) contained
.*(?:.*=.*)and was deployed everywhere at once. CPU on the HTTP-serving machines hit 100%.
The two outages in detail: why so many steps, and the lessons
Stack Overflow. For the second half, [\s]+$, the engine tried to start at every whitespace character, ate the rest of the run, then failed because the end of the run wasn’t the end of the string: 20,000 + 19,999 + … ≈ 200 million steps. The load balancer saw the slow home page and marked the servers unhealthy, so the site was down for about 34 minutes. It’s exactly the \s+$ shape measured in part 3: 20,000 spaces took 630 ms on JDK 21.
Cloudflare. .*(?:.*=.*) is the .*.*=.* shape: three adjacent .* sharing the same stretch of input, cubic cost. Global traffic dropped for about 27 minutes. The lessons were both technical (move to an engine with time guarantees, RE2 or Rust’s engine) and procedural (WAF rules must be rolled out gradually, like code).
Recap from part 3: on JDK 21 some patterns are still exponential (bounded repetition {n,m}, backreferences, three-level nesting) or polynomial (.*.*=.*, \s+$ with find()). All numbers in this post are from JDK 21 using crude timing loops (not JMH), so treat them as orders of magnitude.
The typical attack surface of a Java backend:
@Patternon DTOs for free-text fields like name, address, description.- Parsing headers (
User-Agent,Accept-Language), URLs and query strings with home-grown regexes. - Logs or imported data, where one abnormal line can be megabytes long.
- Features that let users enter a regex: search, filters, alert rules.
- Third-party libraries: there have been many ReDoS CVEs in user-agent parsers, email validators and markdown libraries.
2. Defending in Java
Key idea: defence in depth: unambiguous patterns, input length limits, a home-made timeout, a linear-time engine for foreign input, and tools that catch problems early. No single layer is enough.
2.1. Write unambiguous patterns
The root-cause fix is to make sure each stretch of input has exactly one way to match. Three fixes, measured on the same hostile input:
| Vulnerable pattern | Fix | Before | After |
|---|---|---|---|
^([a-zA-Z0-9]+[._-]?){1,20}@[a-z]+\.com$ |
^[a-zA-Z0-9]+(?:[._-][a-zA-Z0-9]+)*@[a-z]+\.com$ |
15.7 s (n=30) | 0 ms |
\s+$ (with find) |
(?<!\s)\s+$, or String.stripTrailing() |
630 ms (n=20,000) | 0 ms |
.*.*=.* (with find) |
^[^=]*=.* |
87 s (n=5,000) | 0 ms |
Five techniques behind the fixes, with measurements
- Replace
.with a negated class that states the boundary:[^=]*=instead of.*=. - Require a separator between iterations:
\w+(?:\s\w+)*instead of(\w+\s?)*. - Anchor the start when you can:
^[^=]*=is only tried at position 0, while the unanchored[^=]*=is still tried at n positions (670 ms at n=20,000). - Use a lookbehind so a match can only start at the beginning of a run:
(?<!\s)\s+$. - Possessive quantifiers or atomic groups (they never give back what they consumed) when what follows doesn’t need characters back:
\s++$drops from 630 ms to 142 ms but stays quadratic, because it doesn’t reduce the number of starting positions. Possessive helps, but it’s no substitute for removing ambiguity.
2.2. Limit input length before running a regex
Every backtracking pattern is cheap on short input, so this is the cheapest layer: 100 characters for a name, a few KB for a header, log lines truncated at 10 KB before parsing.
2.3. Timeouts: Java has none
java.util.regex has no timeout parameter (.NET has Regex.MatchTimeout). The first idea is usually running the match on another thread and calling future.get(timeout), but that doesn’t stop the regex:
Future<Boolean> f = executor.submit(() -> evil.matcher("a".repeat(30) + "!").matches());
try { f.get(100, TimeUnit.MILLISECONDS); }
catch (TimeoutException e) { f.cancel(true); } // cancel returns true...
// ...but the worker keeps going: measured finishing after 15.4 seconds
What does work: the engine reads input through CharSequence.charAt() constantly, so wrap the input in a CharSequence that throws once the deadline has passed. With ^(a+){2,30}$ on 32 a’s plus !, matchesWithin(..., 100 ms) throws after roughly 100 ms; normal input like “aaaa” still returns true.
The DeadlineCharSequence code and details for using it
final class DeadlineCharSequence implements CharSequence {
private final CharSequence inner;
private final long deadlineNanos;
DeadlineCharSequence(CharSequence inner, long deadlineNanos) {
this.inner = inner;
this.deadlineNanos = deadlineNanos;
}
@Override public char charAt(int index) {
if (System.nanoTime() > deadlineNanos) throw new RegexTimeoutException();
return inner.charAt(index);
}
@Override public int length() { return inner.length(); }
@Override public CharSequence subSequence(int start, int end) {
return new DeadlineCharSequence(inner.subSequence(start, end), deadlineNanos);
}
@Override public String toString() { return inner.toString(); }
}
final class RegexTimeoutException extends RuntimeException {
RegexTimeoutException() { super("regex evaluation exceeded its time budget", null, false, false); }
}
static boolean matchesWithin(Pattern p, CharSequence input, Duration budget) {
long deadline = System.nanoTime() + budget.toNanos();
return p.matcher(new DeadlineCharSequence(input, deadline)).matches();
}
- The exception disables its stack trace (
writableStackTrace = false) because it’s control flow, not a bug. - Calling
System.nanoTime()in everycharAtcosts a few dozen nanoseconds. If that matters, check only every 1,000 calls using a counter. - Catch
RegexTimeoutExceptionat the call site and return a 400 for that input, plus a metric so you know when someone is probing you. - This doesn’t help with regexes inside third-party libraries that call
String.matchesthemselves.
2.4. Linear-time engines
When users supply the pattern, or the input is large and untrusted, switching engines is safer than patching patterns one by one. RE2/J (com.google.re2j:re2j) doesn’t backtrack, so its time is linear in the input length, and its API is close to the JDK’s:
com.google.re2j.Pattern p = com.google.re2j.Pattern.compile(userSuppliedRegex);
boolean hit = p.matcher(line).find(); // linear in the input length
Patterns with backreferences or lookaround are rejected at compile time, which is exactly what you want for regexes written by outsiders. (I didn’t run this snippet for the post, since it needs an extra dependency.)
2.5. StackOverflowError from alternation inside a loop
Java’s engine recurses one level for every iteration of a group containing an alternation (a|b). (a|b)* on a 5,000-character “abab…” string already overflows a 2 MB stack, while [ab]* and (?:a|b)*+ don’t.
Measurements by input length and stack size
| Input | (a|b)* |
[ab]* |
(?:a|b)*+ |
|---|---|---|---|
| 1,000 characters | true | true | true |
| 5,000 characters | StackOverflowError |
true | true |
| 100,000 characters | StackOverflowError |
true | true |
Default thread stack is 2 MB on macOS ARM. Linux x64 defaults to 1 MB, so the threshold is even lower; with -Xss512k, 1,000 characters already overflow.
2.6. Catch it early with tooling
- SonarQube and SonarLint: a rule for regexes prone to excessive backtracking (S5852) and one for regex stack overflow (S5998).
- CodeQL: the
java/redosandjava/polynomial-redosqueries, which run in GitHub code scanning. - Fuzz important patterns with long generated input in unit tests, with
@Timeout(1)from JUnit 5.
3. The slide’s best practices, re-examined
Key idea: most of the slide’s advice holds, but three points need correcting: capturing groups are barely more expensive, the ^(\w*)*$ example is outdated on JDK 21, and “add a timeout” is something Java makes you build yourself.
| Slide advice | Short verdict |
|---|---|
| Compile once | Correct, twice as fast as String.matches |
| Don’t make everything optional | Correct, more important than it looks |
Use *, + sparingly |
Half right: overlap is the real harm |
Use lazy +? |
Careful: doesn’t reduce the number of attempts |
| Negated character classes instead of the dot | Correct |
Capturing groups are expensive, use (?:) |
Right for readability, overstated for performance |
Avoid exponential patterns like ^(\w*)*$ |
Right in principle, outdated example |
| Add a timeout if possible | Right, but Java doesn’t have one |
Each piece of advice in detail, with measurements
- Compile once.
String.matchesrecompiles on every call. A rough measurement of one million email validations: about 500 ns per call withString.matches, 240 ns with astatic final Pattern. Twice the cost plus extra garbage; at a few thousand requests per second it’s not the bottleneck yet, but it’s free, so do it. - Don’t make everything optional; think about what must not match. A pattern full of
?and*both matches too much (the empty string becomes valid) and creates many ways to match the same input, which is exactly what backtracking feeds on. - Use
*,+sparingly. The problem isn’t the number of quantifiers but quantifiers that overlap.[^,]*,[^,]*is safe despite two*. - Use lazy
+?. Lazy changes the order of attempts, not their number; on failing input it costs as much as greedy. A negated character class is usually better. - Negated character classes instead of the dot. It states the intent and removes the overlap:
"[^"]*"can never run past the closing". - Capturing groups are expensive, use
(?:). I measured(\w+)@(\w+)\.(\w+)against its non-capturing version: 77–85 ns versus 75–81 ns, practically the same. The real reasons to use(?:): group numbers don’t shift when you add groups, and readers know the group isn’t used. - Avoid exponential patterns, e.g.
^(\w*)*$. JDK 21 runs that exact example instantly (part 3, section 3.2); bounded repetition, backreferences, three-level nesting and polynomial shapes are still dangerous. - Add a timeout if possible. You build it yourself with a deadline-aware
CharSequence(section 2.3);Future.canceldoes nothing.
Exercises
Exercise 1: Review a validator
Task: review this code in a PR.
public record CreateCustomerRequest(
@Pattern(regexp = "^([a-zA-Z]+\\s?){1,10}$") String fullName,
String searchRule) {}
@Service
class CustomerService {
List<Customer> search(CreateCustomerRequest req, List<Customer> all) {
return all.stream()
.filter(c -> c.note().matches(req.searchRule()))
.toList();
}
String mask(String text, String secret) {
return text.replaceAll(secret, "***");
}
}
Solution to Exercise 1, written as review comments
- TODO (
fullName): the pattern has the(X+\s?){1,10}shape, which is a ReDoS on JDK 21 (the same shape,^(\w+\s?){1,20}$, took 13 seconds on 30 characters). Change it to^[\p{L}]+(?:\s[\p{L}]+){0,9}$.\p{L}accepts accented names such as Vietnamese ones; also add@Size(max = 100), plus a body size limit at the server, because@Sizedoesn’t stop@Pattern. - TODO (
searchRule): users supply their own regex, run by a backtracking engine against every record. A rule like(a+){2,30}$hangs the thread. Either switch to plain search (contains, full-text search), or use RE2/J and compile once outside the loop, with a limit on rule length. Right nowString.matchesalso recompiles the pattern for every record. - TODO (
mask):secretis used as a pattern. If it contains.or+it matches the wrong text; if it contains(it throwsPatternSyntaxException. Usetext.replace(secret, "***"), which replaces every occurrence literally, no regex involved. - NIT:
^...$is redundant in@Pattern, since Hibernate Validator usesmatches(), which already anchors the whole string; keeping it isn’t wrong, it just saves readers from wondering.
Remember
- Explain why
\s+$withfind()is quadratic, and connect it to the 2016 Stack Overflow outage. - Rewrite an ambiguous pattern so every input has only one way to match.
- Explain why
@SizeandFuture.cancel(true)don’t protect a regex, and what to use instead. - Know when to switch to RE2/J, and what you give up.
- Recognise ReDoS from a thread dump, and know why
(a|b)*is more dangerous than[ab]*.
Interview questions
Mid
A form validates names with @Pattern. What do you check to make sure it isn’t a ReDoS hole?
Three things: whether the pattern is ambiguous, whether input length is capped before the regex, and whether there’s a test with hostile input.
- Whether the pattern has nested quantifiers or bounded repetition of a group with an optional part (
(\w+\s?){1,20}); if so, rewrite it so every input has one way to match (\w+(?:\s\w+){0,19}). - Whether input length is limited before it reaches the regex: an
@Sizenext to it isn’t enough, because constraint order isn’t guaranteed, so you need a server-side body limit or a@GroupSequence. - A unit test with the longest worst-case input and a
@Timeout.
Why is \s+$ with find() slow even though it has no nested quantifiers?
Because find() tries every starting position, and from each one \s+ eats the rest of the run and then fails: about n²/2 steps in total.
20,000 spaces took 630 ms, and that’s exactly the 2016 Stack Overflow outage. Fix it with (?<!\s)\s+$, so a match can only start at the beginning of a run, or skip regex entirely: stripTrailing().
Senior
Your Java service suddenly burns 100% CPU with no error logs. How do you tell whether it’s ReDoS?
Take a few thread dumps a few seconds apart; many RUNNABLE threads with deep stacks full of java.util.regex.Pattern$...match frames make it almost certain.
- Use
jcmd <pid> Thread.print, and look for the same application frame at the bottom. JFR or async-profiler gives a clearer flame graph. - Find the triggering request in the access log (slow requests, long payloads), reproduce it in a unit test, fix the pattern.
- Add an input length limit and a deadline-aware
CharSequencetimeout.
Does Java have a regex timeout? How do you get one?
No. What works is wrapping the input in a CharSequence whose charAt throws past a deadline, since the engine calls charAt constantly.
Future.get(timeout) followed by cancel(true) doesn’t stop it, because the engine never checks the interrupt flag; the thread keeps running until the regex finishes. Alongside that: limit input length, and for user-supplied patterns use a linear-time engine such as RE2/J.
Why can (a|b)* cause a StackOverflowError, and why is that dangerous?
Java’s engine recurses one level per iteration of a group containing an alternation, so stack depth grows with input length.
On a 2 MB thread stack, 5,000 characters already overflow. StackOverflowError is an Error, not caught by catch (Exception e), so it can kill a consumer or worker thread. Fix it with a character class [ab]*, a possessive group, or [\s\S]* instead of (.|\n)*.
What regex review checklist would you give your team?
Unambiguous patterns, bounded input, tests with hostile input, and a linear-time engine for anything from outside.
- Patterns are
static final; noString.matches/replaceAllon hot paths. Anchors in the right places. - No nested quantifiers or overlapping alternation; negated character classes instead of
.*in the middle of a pattern. - Input length limited before the regex runs.
- Unit tests with must-match cases, near-miss cases that must not match, and long hostile input under
@Timeout. - RE2/J for patterns or input from outside.
- User data going into a pattern is wrapped in
Pattern.quote, and into a replacement string inMatcher.quoteReplacement.
Useful phrases for interviews
- “ReDoS doesn’t throw anything; the only symptom is a thread stuck at 100% CPU inside
java.util.regex.” - “A length limit, an unambiguous pattern and a time budget give us defence in depth.”
- “
Future.cancelonly sets the interrupt flag, and the regex engine never checks it.” - “The engine reads through
charAt, so a deadline-awareCharSequenceis the one place we can stop it.” - “
@Sizenext to@Patterndoesn’t short-circuit anything; constraint order isn’t guaranteed.” - “For user-supplied patterns I’d switch to RE2/J and accept losing backreferences and lookaround.”
- “Cloudflare’s lesson applies to us too: config like WAF rules needs a staged rollout, just like code.”
- “Capturing versus non-capturing barely matters for speed; I use non-capturing groups for readability.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.