skip to content

What is a ReDoS attack, and how could a user-supplied regex or input take down a Java service?

level: seniorimportance: must knowfreq 50%

answer

  1. cheap DoS: one small request, no flood
  2. regex is synchronous + uninterruptible on a request thread
  3. pins a core, exhausts the thread pool
  4. two surfaces: attacker controls pattern OR input
  5. fix pattern / bound length / timeout / RE2J

basics

~20 s

ReDoS (Regular-expression Denial of Service) is when an attacker sends an input that makes a vulnerable regex take a huge amount of time to evaluate, freezing the thread and starving the service of CPU until it can't serve real users.

solid answer

~50 s

ReDoS exploits catastrophic backtracking. A pattern with overlapping or nested quantifiers can take exponential time on a crafted input — typically a long matching-looking prefix plus one breaker character. In a Java service the regex usually runs synchronously on a request thread (e.g. validating an email or parsing a header). One malicious request pins that thread at 100% CPU for seconds or longer; a handful of them exhaust the request thread pool and the whole service stops responding — a denial of service with no traffic flood needed. The attack surface is worst when the PATTERN itself comes from the user (search filters, rules engines), but a fixed-but-vulnerable pattern fed attacker-controlled INPUT is equally exploitable. Mitigation: avoid vulnerable shapes, use possessive quantifiers/atomic groups, bound input length, run untrusted matching with a timeout, or use a non-backtracking engine like RE2J.

go deeper

for a junior

Knows ReDoS means a regex can hang the app and that user input touching regex is risky; would ask for help hardening it.

for a middle

Explains the link to catastrophic backtracking and names basic mitigations like input-length limits and avoiding nested quantifiers.

for a senior

Connects it to Java's synchronous uninterruptible matching on bounded request threads, identifies both attack surfaces, and chooses among possessive quantifiers, timeouts, input bounds, and RE2J.

for a principal

Sets org-wide policy: ban user-supplied patterns on the default engine, mandate RE2J or time-boxed execution for untrusted matching, add static analysis/linting for vulnerable shapes, and design event-loop services to never block on regex.

## Background: what a DoS is A **denial-of-service (DoS)** attack makes a system unavailable to legitimate users. The classic form floods the system with traffic. **ReDoS** (Regular-expression Denial of Service) is far cheaper: a *single small request* can consume enormous CPU, so you don't need a flood. ## The mechanism it abuses ReDoS weaponizes **catastrophic backtracking** (see the backtracking question). Java's `java.util.regex` engine is an NFA that backtracks. Certain pattern shapes — nested quantifiers `(a+)+`, overlapping alternations `(a|a)*`, etc. — let the same characters be matched in exponentially many ways. On an input that matches a long prefix and then fails (a **near-miss**), the engine must try every combination to prove no match exists. Time grows exponentially with input length: a ~30-character string can take seconds; ~40 can take minutes. ## Why this is fatal in a Java web service Important facts about how regex runs in Java: 1. **It is synchronous and blocking.** `matcher.matches()` runs to completion on the calling thread. There is no built-in timeout or cancellation. 2. **It runs on a request thread.** Servers (Tomcat, Netty event loop, etc.) use a bounded pool of threads to handle requests. A regex call sits on one of those threads. 3. **It pins a CPU core at 100%.** Backtracking is pure CPU work. Put together: one crafted request makes one request thread spin at 100% CPU for a long time and never return to the pool. Send as many requests as the pool is wide and **every** thread is stuck — new requests queue forever and the service is effectively dead. On a Netty/Reactor event loop it is worse: blocking the single event-loop thread stalls *all* connections at once. ## Two attack surfaces - **Attacker controls the PATTERN.** Search filters, business-rule editors, or any feature that compiles a user-supplied regex. The attacker just supplies `(a+)+$` plus a matching input. Most dangerous — treat user-supplied patterns as code. - **Attacker controls the INPUT to a fixed vulnerable pattern.** E.g. a validation regex for emails/URLs/dates that happens to be backtracking-prone; the attacker submits a crafted value. This is the common real-world case (CVE-laden validation libraries). ## Real-world examples Many high-profile ReDoS incidents involved a *built-in* validation regex (email validators, the Cloudflare 2019 outage from a regex in a WAF rule, vulnerable patterns shipped in popular libraries). The takeaway: even fixed, vendor-supplied patterns can be vulnerable. ## Mitigations (in order of preference) 1. **Don't use vulnerable shapes.** Refactor to remove nested/overlapping quantifiers. Often the simplest fix. 2. **Possessive quantifiers / atomic groups** (`a++`, `(?>a+)`) — disable backtracking for that subexpression so a failure fails fast instead of exploring (covered in the related question). 3. **Bound the input.** Reject overly long inputs *before* matching; exponential cost needs length to bite. 4. **Run untrusted matching with a hard timeout** — e.g. execute the match on a separate thread you can interrupt, or use a `CharSequence` wrapper whose `charAt` throws after a deadline, since `Matcher` checks it during scanning. 5. **Never compile user-supplied patterns** with the default engine; if you must, use a **linear-time, non-backtracking engine** such as **RE2J** (a Java port of Google's RE2), which guarantees linear time at the cost of backreferences/some lookaround. 6. **Defense in depth:** per-request CPU/time budgets, circuit breakers, rate limiting. ## First-principles summary ReDoS = catastrophic backtracking + the fact that Java regex runs synchronously, uninterruptibly, on a bounded request thread. A tiny input buys an attacker minutes of pinned CPU per thread, so a few requests starve the pool and the service goes down. Fix the pattern, bound the input, time-box the match, or switch engines.

  • How would you add a timeout to a Java regex match given there is no native one?
    Run the match on a separate executor thread and interrupt/cancel after a deadline, or wrap the input in a CharSequence whose charAt() throws once a time budget is exceeded — Matcher reads charAt during scanning, so it aborts. Or switch to RE2J, which is linear-time by construction.
  • Why is RE2J immune to ReDoS?
    RE2J uses an automaton-based (Thompson NFA/DFA-style) execution that runs in time linear in the input length and never backtracks, so no input can cause exponential blowup. The cost is dropping backreferences and some lookaround.

  • Assuming you need many requests / a traffic flood (one slow request per thread is enough)
  • Believing Pattern.matches has a built-in timeout (it does not)
  • Thinking only user-supplied PATTERNS are dangerous (fixed vulnerable patterns + attacker input are equally exploitable)
  • Suggesting 'just catch the exception' — backtracking does not throw, it just runs

context