What Is ReDoS? Regular Expression Denial of Service

ReDoS, short for regular expression denial of service, is an attack in which a carefully crafted input string makes a regular expression take an enormous amount of time to evaluate. A pattern that matches normal input in microseconds can take seconds, minutes, or effectively forever on a string only a few dozen characters long. Because regex matching usually runs synchronously on the CPU, one malicious request can pin a core and, in single-threaded runtimes like Node.js, stall every other request the process is handling.

The root cause: backtracking engines

Most regex engines in popular languages, including those in JavaScript, Python, Java, Ruby, PHP, and .NET, are backtracking engines. When a pattern offers several ways to match, the engine tries one, and if the overall match fails later, it backs up and tries the next. That design makes features like backreferences and lookarounds possible, but it also means the number of paths explored can grow exponentially with input length.

Other engines take a different approach. Automaton-based engines, such as RE2 and the regex crate in Rust, simulate all possible paths at once and guarantee matching time linear in the input length. The trade-off is that they drop features that require backtracking, such as backreferences. The theory behind the two families is covered in how regex engines work with NFAs and DFAs.

What catastrophic backtracking looks like

The classic vulnerable pattern is a nested quantifier:

const re = /^(a+)+$/;

Against "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab", this pattern cannot match because of the trailing b. But before giving up, the engine tries every way to split the run of as between the inner a+ and the outer +. A string of n as can be divided in 2^(n-1) ways. Each extra character roughly doubles the work. At around 30 characters, the attempt takes noticeable time; a few characters more and it effectively never finishes.

The match succeeds quickly on valid input, which is why these bugs survive testing. The problem only appears on input that almost matches and then fails at the end, forcing the engine to exhaust every alternative. In Big O terms, the pattern’s worst case is exponential even though its typical case looks constant.

Patterns that cause trouble

Three shapes account for most ReDoS bugs:

• Nested quantifiers: (a+)+, (\w*)*, (.*a){10}. A repeated group whose contents can themselves repeat.
• Overlapping alternation under repetition: (a|a)*, (\w|\d)+, (a|ab)*c. Two alternatives can match the same characters, so the engine has multiple choices at each step.
• Adjacent overlapping quantifiers: \d+\d+$ or .*.*=.*. Two quantifiers compete for the same characters. These usually cause polynomial rather than exponential blowup, but quadratic or cubic time on a long input is still enough to take down a server.

Real-world examples tend to hide these shapes inside larger patterns, such as email validators, URL matchers, or log-line parsers with something like (\s*[\w.-]+\s*)+ buried inside.

Why the impact is outsized

A typical denial-of-service attack needs a lot of traffic. ReDoS needs one request. The asymmetry comes from the work being done on the server’s CPU, not the network.

• Node.js and other event-loop runtimes. A regex evaluation blocks the event loop. While it runs, the process cannot accept connections, respond to health checks, or finish other requests. A load balancer may then mark the instance unhealthy, shifting traffic onto others that receive the same payload.
• Thread-per-request servers. Each malicious request ties up a worker thread. A small number of requests can exhaust the pool.
• Clients and tools. Browsers, editors, linters, and CI pipelines that run user-supplied or untrusted patterns can hang just as easily.

Unlike volumetric attacks, ReDoS is not mitigated by a DDoS protection layer alone, since the traffic looks entirely normal.

How to prevent ReDoS

Rewrite ambiguous patterns. Most vulnerable regexes can be rewritten so each character has only one way to match. ^(a+)+$ is equivalent to ^a+$. (\w|\d)+ is equivalent to \w+, since digits are already word characters. Removing nesting and overlap removes the exponential search.

Use possessive quantifiers or atomic groups where supported. Some engines, including Java, PCRE, and recent versions of several others, support possessive quantifiers like a++ or atomic groups like (?>a+), which tell the engine not to backtrack into the group once it has matched. Support varies by language, so check your engine’s documentation before relying on it.

Use a linear-time engine for untrusted input. If users can supply patterns, or if patterns run on large untrusted input, a non-backtracking engine removes the problem class entirely. Bindings for RE2 exist for most major languages.

Limit input length. Exponential blowup needs a long enough input. Capping the length of fields before matching, such as a few hundred characters for a name or an email address, turns a potential hang into a bounded cost. This is a cheap layer that also supports good input validation.

Set timeouts. Some platforms, such as .NET, accept a match timeout directly. Elsewhere, run risky matching in a worker or subprocess that can be terminated.

Do not build regexes from user input. Concatenating user strings into a pattern lets an attacker inject their own nested quantifiers. If you must match a user string literally, escape it first.

Scan in CI. Static analysis tools and linters can flag nested quantifiers and overlapping alternation, catching the most common shapes before they ship.

Backtracking vs linear-time engines

	Backtracking engines	Linear-time engines
Examples	JavaScript, Python re, Java, PCRE, Ruby	RE2, Rust regex, Go regexp
Worst-case time	Exponential	Linear in input length
Backreferences	Supported	Not supported
Lookarounds	Supported	Limited or unsupported
ReDoS risk	Yes, pattern-dependent	No

The takeaway

ReDoS turns a regular expression into a denial-of-service weapon by feeding it input that forces a backtracking engine through an exponential number of paths. Watch for nested quantifiers and overlapping alternatives, rewrite patterns so each character has one way to match, cap input length, avoid building patterns from user input, and switch to a linear-time engine whenever untrusted data meets a pattern you cannot fully vet.