What is a ReDoS attack, and how could a user-supplied regex or input take down a Java service?
answer
- cheap DoS: one small request, no flood
- regex is synchronous + uninterruptible on a request thread
- pins a core, exhausts the thread pool
- two surfaces: attacker controls pattern OR input
- fix pattern / bound length / timeout / RE2J
basics
~20 sReDoS (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 sReDoS 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
Knows ReDoS means a regex can hang the app and that user input touching regex is risky; would ask for help hardening it.
Explains the link to catastrophic backtracking and names basic mitigations like input-length limits and avoiding nested quantifiers.
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.
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.
saying these in an interview costs you the question
- 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