Performance April 29, 2026

What is ReDoS? Regex denial-of-service explained

A short, badly-written regex can hang a server for hours on the right input. The attack is real and easy to trigger.

The short answer

ReDoS (Regex Denial of Service) is a class of vulnerability where a specially-crafted input causes a regex to take exponentially long to match. With the right pattern and input, a single match attempt can consume CPU for hours or indefinitely.

It's caused by catastrophic backtracking in NFA-based regex engines (used by JavaScript, Python, Java, .NET, Perl, PCRE).

How the attack works

Consider the regex ^(a+)+$ applied to aaaaaaaaaaaaaaaaaaaaaX (20 a's + non-matching X):

The outer + can match the inner group 1 time, 2 times, etc.
The inner a+ can match anywhere from 1 to all 20 a's.
There are 2^20 = ~1 million ways to split the a's between the two quantifiers.
The engine tries every combination because the final $ fails against the X.

With 30 a's: ~1 billion combinations. With 40: ~1 trillion. The runtime grows exponentially with input length.

Real vulnerabilities in production

ReDoS has shown up in major real-world systems:

Cloudflare 2019 — a regex in a WAF rule caused a 27-minute outage
Stack Overflow 2016 — slow regex took down the site for 34 minutes
npm packages — dozens of CVEs filed against popular libraries (lodash, ms, moment, marked) for ReDoS in their parsing regex

How to spot vulnerable patterns

Red flags in any regex that processes user input:

Nested quantifiers on overlapping content: (a+)+, (a*)*
Alternation with overlapping branches: (a|aa)+
Repeated optional patterns: (\w+)*
.*.* or similar repetitions of greedy quantifiers

Spot-checking

To check whether a regex is vulnerable:

Find a string that almost matches but fails at one position
Make the "almost matching" part progressively longer
If match time grows faster than linearly, you have a ReDoS bug

How to prevent ReDoS

1. Use a non-backtracking engine

The most robust fix. Engines like RE2 (used in Go regexp), Rust's regex crate, and Hyperscan guarantee linear-time matching:

Go: regexp stdlib — RE2-based
Node.js: node-re2 — RE2 bindings
Python: google-re2 — RE2 bindings

These engines don't support backreferences or lookarounds (because those features inherently require backtracking) — but for parsing, validation, and search, they're usually more than enough.

2. Use atomic groups / possessive quantifiers

In PCRE / Java / Python 3.11+:

Before:  ^(a+)+$
After:   ^(?>a+)+$       atomic group, won't backtrack
         ^(a++)+$         possessive +

3. Set a regex timeout

Java: Matcher doesn't natively support timeouts but you can run on a thread with a watchdog. .NET: Regex.Match(text, pattern, options, timeout) built in. Node.js: third-party packages like re2-wasm with timeout support.

A 100ms timeout is usually enough to abort runaway patterns without affecting normal matches.

4. Validate input length before matching

If you know inputs are bounded, enforce that:

if (input.length > 1000) throw new Error("Input too long");
const match = pattern.exec(input);

Capping length doesn't fix the underlying pattern, but it bounds the worst-case runtime.

5. Static analysis

Run automated tools that flag vulnerable patterns:

safe-regex (npm)
vuln-regex-detector (npm)
recheck (research tool, very thorough)
SonarQube, ESLint rules

Patterns to audit immediately

Any regex that:

Processes user-submitted input (form fields, URLs, request bodies)
Runs on uploaded files or scraped content
Comes from a configuration file or admin UI

Internal-only regex with controlled inputs is less risky but worth auditing too.

The takeaway

ReDoS is a real vulnerability with real production impact. The patterns that cause it are subtle — a developer might write (\w+\s*)+ for a name-validation field and not realize they've added a denial-of-service vector.

For any code handling untrusted input, either use a non-backtracking engine, audit your patterns with static analysis, or set match timeouts. Don't rely on patterns being "obviously safe" — most ReDoS bugs are subtle.