Skip to main content

ReDoS: the regular expressions that freeze a server

Most denial-of-service attacks need volume. ReDoS needs one request. A regular expression with the wrong shape, given a carefully chosen string of a few dozen characters, can keep a CPU core busy for seconds or minutes. In Node.js that core is the event loop, so every other request waits too.

This post explains why some patterns blow up, shows the shapes to look for, and covers the fixes: rewriting the pattern, limiting input, never compiling user patterns, and moving to a linear-time engine. MITRE tracks the class as CWE-1333, inefficient regular expression complexity.

What is catastrophic backtracking?

The regex engines in JavaScript, Java, Python, PHP, Ruby and .NET (by default) are backtracking engines. They try one way to match, and when that fails they back up and try the next. For most patterns the number of alternatives is small. For some, it grows exponentially with input length.

The textbook case:

const re = /^(a+)+$/;
re.test('a'.repeat(30) + '!'); // runs for a very long time

The input almost matches. It is 30 a characters and then a ! that makes the final $ fail. Before giving up, the engine tries every way to split those 30 characters between the inner a+ and the outer +: one group of 30, a group of 29 and a group of 1, and so on. That is on the order of 2^30 attempts. Each extra a roughly doubles the time.

The danger comes from ambiguity: more than one way for the pattern to consume the same text. Three shapes produce it:

  • Nested quantifiers, such as (a+)+, (.*)* or ([a-z]+)*. The inner and outer loops can divide the same run of characters many ways.
  • Overlapping alternation under a quantifier, such as (\w|\d)+. Each digit can be matched by either branch, so every digit doubles the choices.
  • Adjacent overlapping quantifiers, such as \s*.*\s* or .*=.*. Several unbounded pieces compete for the same characters.

The last shape is subtler. It is often polynomial rather than exponential, but quadratic or cubic time on a long input is still enough to take down a service.

Real patterns that look harmless

Nobody writes (a+)+ on purpose. They write things like this:

// "words separated by optional spaces"
const words = /^(\w+\s?)+$/;

// a hand-rolled email check
const email = /^([a-zA-Z0-9_.-]+)+@[a-zA-Z0-9-]+\.[a-z]{2,}$/;

Both contain a quantified group whose body is itself quantified. Feed the first 'a'.repeat(40) + '!' and it stalls. The second stalls on a long local part with no @.

Big operators have been caught by this. On July 2, 2019 a single WAF rule with a badly backtracking regular expression exhausted CPU across Cloudflare's network and took its HTTP service down for 27 minutes. Its post-incident report identifies .*(?:.*=.*) as the critical part of the pattern, and one of the remediations was moving to regex engines with run-time guarantees.

How to fix ReDoS

1. Rewrite the pattern so it is unambiguous

Make every character matchable in only one way.

// Before: nested quantifier
const words = /^(\w+\s?)+$/;
// After: a word, then (one space and a word) repeated
const wordsSafe = /^\w+(?:\s\w+)*$/;

// Before: quantified group of a quantified class
const email = /^([a-zA-Z0-9_.-]+)+@[a-zA-Z0-9-]+\.[a-z]{2,}$/;
// After: the group adds nothing, so drop it
const emailSafe = /^[a-zA-Z0-9_.-]+@[a-zA-Z0-9-]+\.[a-z]{2,}$/;

In wordsSafe, a space is required between repetitions, so there is exactly one way to divide the input. Where your engine supports them, atomic groups (?>...) and possessive quantifiers ++ and *+ tell the engine not to backtrack into a piece once it has matched. Java has long supported them, and Python added both in 3.11 (What's New in Python 3.11). JavaScript does not have them.

2. Cap the input length before matching

Exponential blowup needs a long enough input. A field that should be 64 characters should be rejected at 65, before any regex runs:

if (typeof input !== 'string' || input.length > 254) {
  return res.status(400).json({ error: 'Email is too long' });
}

This does not fix a quadratic pattern on a large body, but it removes most of the exponential cases, and it costs one line.

3. Never compile a caller-supplied pattern

new RegExp(req.query.q) lets the caller supply (a+)+$ directly, along with any metacharacter they like. If you want literal search, escape the input or skip regex:

// Vulnerable
const hits = items.filter((s) => new RegExp(req.query.q, 'i').test(s));

// Fixed: literal match
const q = String(req.query.q ?? '').slice(0, 100).toLowerCase();
const hitsSafe = items.filter((s) => s.toLowerCase().includes(q));

In Java, Pattern.quote(value) makes a value literal. If users genuinely need regex search, run their patterns on a linear-time engine with a length limit.

4. Use a linear-time engine

Engines based on automata rather than backtracking guarantee time linear in the input size, at the cost of features such as backreferences and lookaround:

  • Go: the standard regexp package "is guaranteed to run in time linear in the size of the input" and uses RE2 syntax. Go services are largely immune to this class.
  • Rust: the regex crate makes the same guarantee.
  • .NET: RegexOptions.NonBacktracking, available in .NET 7 and later, guarantees linear-time processing (.NET regex options). .NET also supports a match timeout on the default engine.
  • Node.js and Python: bindings to Google's RE2 library are available as packages (re2 on npm, for example).

5. Contain what you cannot fix

Run expensive matching in a worker thread or separate process with a time budget, so a stuck match kills a worker rather than the server. This is containment, not a fix.

How to find vulnerable regexes

Search your code for the shapes listed above: a + or * applied to a group whose body ends in + or *, and quantified alternations with overlapping branches. Pay particular attention to patterns that run on request data (validation, routing, parsing headers) and to every new RegExp(...) or Pattern.compile(...) whose argument is not a literal. Then test the suspicious ones with a near-match input: a long run of the repeated character followed by one character that forces failure. If doubling the length roughly doubles the time or worse, you have found one.

Do not forget dependencies. Many published ReDoS advisories are in small parsing and validation packages, which is a reason to keep them updated.

What Vulkro checks

In JavaScript and TypeScript, js-taint-redos-001 reports a request value compiled as a regular expression pattern, with the hops from the route to the new RegExp call. In Java, JAVA-REDOS-001 covers both a request-derived value passed to Pattern.compile and a static pattern with a nested quantifier such as (a+)+ or (.*)*; a Pattern.quote escaped value does not fire. Vulnerable dependency versions come through dependency matching against the local CVE bundle. vulkro explain <ID> prints what each rule flags and how to fix it.

FAQ

What is ReDoS?

Regular expression denial of service: a crafted input makes a backtracking regex engine take exponential or polynomial time, so one request can occupy a CPU core and stall the service.

How do I know if a regex is vulnerable to ReDoS?

Look for nested quantifiers like (a+)+, quantified alternations with overlapping branches like (\w|\d)+, and several adjacent unbounded pieces like .*=.*. Then time it against a long near-match input. Sharp growth as the input lengthens confirms it.

Does Go have ReDoS?

The standard Go regexp package runs in time linear in the input, so classic catastrophic backtracking does not apply. Go code can still burn CPU on very large inputs or third-party backtracking libraries, so input limits still matter.

Start a 14-day trial at /start/. Related reading: Taint analysis: sources, sinks and sanitizers and Ranking dependency alerts by real risk.