Regex DDoS (ReDoS): How Catastrophic Backtracking Takes Down a Service

A regex DDoS — more precisely a ReDoS, or Regular Expression Denial of Service — is an attack where a carefully chosen short input forces a vulnerable regular expression into exponential-time matching, consuming CPU and stalling the service. It needs no botnet and no volume. A single request with a few dozen crafted characters can pin a core for seconds, and a handful of concurrent requests can take an application offline. The root cause is a well-understood property of backtracking regex engines called catastrophic backtracking.

Why a regular expression can be slow

Most mainstream regex engines (in JavaScript, Java, Python, .NET, PCRE) use backtracking. When a pattern can match a piece of input in more than one way, the engine tries one path, and if the overall match fails, it backtracks and tries another. For certain pattern shapes, the number of paths grows exponentially with input length.

The classic dangerous shapes involve nested or overlapping quantifiers:

(a+)+$          # nested quantifiers
(a|a)*$         # overlapping alternation
([a-z]+)*$      # quantifier on a quantified group

Feed (a+)+$ a string of many a characters followed by one !, and the engine explores an astronomical number of ways to partition the a run before concluding there is no match. Matching time grows roughly as 2 raised to the input length. Twenty characters can already take noticeable time; thirty-five can take minutes.

This is not theoretical — it ships in popular packages

ReDoS shows up regularly in widely used libraries, which is what makes it a supply chain problem rather than just a coding hygiene one. A few verified examples:

• lodash was vulnerable to ReDoS in its toNumber, trim, and trimEnd functions in versions before 4.17.21 (CVE-2020-28500). An earlier date-parsing ReDoS was tracked as CVE-2019-1010266.
• marked, a popular Markdown parser, carried a ReDoS vulnerability tracked as CVE-2022-21681.

Because these are dependencies most projects pull in transitively, a ReDoS in a utility library becomes a ReDoS in your application without a single line of your own regex being at fault. An SCA scanner that resolves the transitive graph will flag a vulnerable lodash or marked version that a manifest read would miss.

Detecting vulnerable patterns in your own code

You do not need to run an exploit to find risk. Static checks and review catch most cases:

• Look for nested quantifiers ((x+)+, (x*)*), and quantified groups next to alternation that can match the same characters.
• Watch input from untrusted sources flowing into RegExp, matcher.matches(), re.match, or similar, especially where the pattern is complex.
• Run a linter rule dedicated to this. In JavaScript, eslint-plugin-security flags detect-unsafe-regex; dedicated analyzers can compute whether a pattern is vulnerable.

A quick illustration of the fix by rewriting the pattern to remove ambiguity:

// Vulnerable: nested quantifier over overlapping characters
const bad = /^(\d+)+$/;

// Safe: unambiguous, linear-time
const good = /^\d+$/;

The safe version cannot backtrack catastrophically because there is exactly one way to match digits.

Fixing and mitigating ReDoS

Several layers help, and you generally want more than one:

• Rewrite the pattern to eliminate nested and overlapping quantifiers. This is the real fix when the regex is yours.
• Bound the input with a length limit before it ever reaches the regex. A pattern that is exponential is still fast on short input, so capping length to what the field legitimately needs neutralizes most attacks cheaply.
• Use a non-backtracking engine where available. RE2 (and its bindings) guarantees linear-time matching by refusing to use backtracking, at the cost of some features like backreferences.
• Enforce timeouts. .NET supports a matchTimeout; other stacks can run the match in a worker with a deadline and kill it if it overruns.
• Update vulnerable dependencies to the patched versions, since much of your ReDoS exposure lives in third-party code.

Where it fits in a defense strategy

ReDoS sits at an awkward intersection: it is an availability bug that looks like a performance issue, so it slips past teams that only scan for injection and known CVEs. Treat it as a first-class denial-of-service risk. Add an unsafe-regex lint rule to CI, cap the length of any user-controlled string before regex processing, and keep dependencies current so you inherit upstream fixes. Our Academy covers input-validation patterns that close this and related classes at the boundary.

FAQ

What is a regex DDoS?

A regex DDoS, or ReDoS, is a denial-of-service attack that feeds a crafted short input to a vulnerable regular expression, triggering catastrophic backtracking that consumes CPU and stalls the service — no traffic volume required.

What causes catastrophic backtracking?

Backtracking regex engines explore multiple ways to match ambiguous patterns. Nested or overlapping quantifiers, such as (a+)+, create exponentially many match paths, so matching time explodes as input length grows.

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

Look for nested quantifiers and quantified groups over overlapping character sets, especially where untrusted input is matched. Linter rules like detect-unsafe-regex and dedicated analyzers can flag risky patterns automatically.

How do I prevent ReDoS?

Rewrite ambiguous patterns, cap input length before matching, use a linear-time engine such as RE2, enforce match timeouts, and keep dependencies updated to inherit upstream ReDoS fixes.