What is ReDoS (Regular Expression Denial of Service)?

Regular expressions are so routine that nobody thinks of them as attack surface. Then a request with a few dozen carefully chosen characters pins a CPU core to 100% for minutes, requests queue up, health checks fail, and the service falls over. No memory corruption, no injected code — just a pathological match. That is Regular Expression Denial of Service, and it has caused global outages at companies that write excellent code.

The definition

ReDoS (Regular Expression Denial of Service, CWE-1333) is a vulnerability where a regular expression can be forced into catastrophic backtracking by a crafted input, causing matching time to grow exponentially (or high-polynomially) with input length and consuming enough CPU to deny service. It affects any language whose regex engine uses backtracking — which includes the default engines in JavaScript, Python, Java, .NET, Ruby, and PHP.

Why regex backtracking explodes

Backtracking engines try to match a pattern by exploring possibilities and reversing course when a path fails. Certain pattern shapes create an enormous number of ways to match the same substring. The classic danger sign is nested or adjacent quantifiers over overlapping character classes — patterns like (a+)+$, (a|a)*, or (\d+)*. When such a pattern meets an input that almost matches but ultimately fails (for example, a long run of a followed by a !), the engine tries every possible way to partition the run before giving up. The number of partitions grows exponentially with the input length, so a 30-character string can take seconds and a 40-character string can take minutes.

Real, well-run engineering teams have been hit by this:

• Cloudflare, July 2, 2019. A single regex deployed in a WAF managed rule contained catastrophic backtracking and drove CPU to exhaustion across the global network, causing a widespread outage. Cloudflare's own post-incident writeup identifies the backtracking regex as the root cause.
• Stack Overflow, July 20, 2016. A regex used to trim whitespace from posts backtracked catastrophically on a post with a very long line of consecutive spaces, taking the site down.

Both were availability incidents caused by one line of pattern.

Vulnerable vs. fixed

A validator meant to check that a string is a sequence of words:

// VULNERABLE — nested quantifier over overlapping classes => catastrophic backtracking
const RE = /^(\w+\s*)*$/;

function isWordList(input) {
  return RE.test(input);   // "aaaa...aaaa!" (40+ chars) hangs the event loop
}

The fix is to rewrite the pattern so there is only one way to match each character, remove the nested quantifier, and anchor precisely:

// FIXED — no nested quantifiers; linear-time match
const RE = /^\w+(?:\s+\w+)*$/;

function isWordList(input) {
  if (input.length > 1000) return false;   // bound the input as defense in depth
  return RE.test(input);
}

The rewritten pattern matches a word, then zero or more (whitespace + word) groups — every character has exactly one role, so there is nothing to backtrack over. Bounding input length is a cheap, high-value backstop regardless of the pattern.

Prevention checklist

• Avoid nested quantifiers ((x+)+, (x*)*) and quantified alternations with overlapping branches ((a|a)*). These are the primary ReDoS shapes.
• Rewrite for a single match path. Use atomic groups or possessive quantifiers where your engine supports them (Java, PCRE, .NET) to prevent backtracking.
• Bound input length before matching. A short maximum on any user-supplied string that hits a regex removes most exploitability.
• Prefer linear-time engines for untrusted input — Go's regexp (RE2), Rust's regex, or RE2 bindings guarantee linear time and cannot backtrack.
• Enforce timeouts. .NET's Regex accepts a matchTimeout; run untrusted matching under a watchdog elsewhere.
• Audit dependencies. ReDoS frequently arrives through a library's internal regex (validation, parsing, sanitization), not your own patterns.
• Test with adversarial inputs. Fuzz patterns with long, near-matching strings and measure worst-case time, not just correctness.

How to spot a dangerous pattern in review

You do not need tooling to catch the most common ReDoS shapes in code review — you need to recognize three red flags. First, a quantifier applied to a group that itself contains a quantifier, such as (a+)+ or (\d*)*. Second, alternations whose branches can match the same text, like (a|a)* or (\w|\d)*, since the engine can match a given character more than one way. Third, any of the above followed by an anchor or a character the input frequently fails to satisfy, which forces the engine to exhaust every path before it can conclude the match failed. When you see these constructs applied to input whose length you do not control, treat the pattern as a denial-of-service bug until proven otherwise, and rewrite it so each character has exactly one role.

How Safeguard helps

ReDoS hides in two places: the regexes you write and the regexes your dependencies ship. Griffin AI code review analyzes regular expressions in your codebase for dangerous constructs — nested quantifiers, overlapping alternations, unbounded input reaching a backtracking engine — and explains why a given pattern is exploitable rather than just flagging it. Safeguard's software composition analysis maps published ReDoS advisories against your dependency graph, so when a popular validation or parsing library ships a catastrophic pattern, you learn whether the affected version is actually in your build. Safeguard's DAST engine can exercise input-validation endpoints with pathological strings to confirm real latency amplification at runtime. When the remediation is upgrading a library with a patched pattern, Safeguard's auto-fix opens the pull request, and the Safeguard CLI brings the checks into local development.

Comparing approaches to noise reduction? See Safeguard vs Veracode.

Run a free scan at app.safeguard.sh/register, and read the ReDoS hardening notes at docs.safeguard.sh.