Skip to content
notes.vinhnq.com

Search

Java CoreSenior16 min read

ReDoS in Java: real outages, a home-made timeout and a defence checklist

Review 11 cards
On this page

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:

  • @Pattern on 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 every charAt costs a few dozen nanoseconds. If that matters, check only every 1,000 calls using a counter.
  • Catch RegexTimeoutException at 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.matches themselves.

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/redos and java/polynomial-redos queries, 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.matches recompiles on every call. A rough measurement of one million email validations: about 500 ns per call with String.matches, 240 ns with a static 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.cancel does 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 @Size doesn’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 now String.matches also recompiles the pattern for every record.
  • TODO (mask): secret is used as a pattern. If it contains . or + it matches the wrong text; if it contains ( it throws PatternSyntaxException. Use text.replace(secret, "***"), which replaces every occurrence literally, no regex involved.
  • NIT: ^...$ is redundant in @Pattern, since Hibernate Validator uses matches(), which already anchors the whole string; keeping it isn’t wrong, it just saves readers from wondering.

Remember

  • Explain why \s+$ with find() 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 @Size and Future.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 @Size next 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 CharSequence timeout.
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; no String.matches/replaceAll on 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 in Matcher.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.cancel only sets the interrupt flag, and the regex engine never checks it.”
  • “The engine reads through charAt, so a deadline-aware CharSequence is the one place we can stop it.”
  • “@Size next to @Pattern doesn’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.