ReDoS sits in the gap between “known vulnerability” and “actually fixed.” Most developers have heard of it. Few have audited their regex patterns for it. The reason is that vulnerable patterns look completely normal — the problem is invisible until an attacker (or a fuzzer) finds an input that triggers exponential backtracking.
The result: a single HTTP request with a malicious Content-Type header, email address, URL parameter, or log line can freeze an application thread for minutes. In single-threaded environments like Node.js event loops, this blocks all request handling for the duration.
Why Catastrophic Backtracking Happens
Standard regex engines use backtracking to try multiple paths through a pattern when an initial match fails. Most patterns produce linear or polynomial backtracking — fast enough to not matter. Vulnerable patterns produce exponential backtracking: the number of steps grows as 2^n or worse with input length.
The classic vulnerable structure is nested quantifiers — quantifiers applied to groups that themselves contain quantifiers — combined with a suffix that forces the engine to explore all possibilities before failing.
Vulnerable pattern: ^(a+)+$
Against the input aaaaaaaaaaaaaaaaaaaaab (20 a characters followed by b):
- The outer
+can split the inner group’s matches in 2^20 ways - The engine tries every combination before concluding the
bcannot match$ - Result: ~1 million backtracking steps for 20 characters
Vulnerable pattern: ^(\w+\s?)*$
Same issue — \w+ and \s? inside (\w+\s?)* creates ambiguity that causes exponential paths when the input contains a non-matching character at the end.
Identifying Vulnerable Patterns
The structural signatures of vulnerable patterns:
- Nested quantifiers:
(a+)+,(a*)*,(a|a)+ - Alternation with overlap:
(a|ab)+— the alternatives match overlapping substrings, creating ambiguous paths - Adjacent quantified groups:
(\d+)(\d+)+— when one quantified group can hand off to another
Tools for detection:
- vuln-regex-detector (GitHub: nicowillis/vuln-regex-detector) — static analysis tool that identifies catastrophic backtracking potential
- safe-regex (npm:
safe-regex) — Node.js library that tests a pattern for polynomial or exponential complexity - rexploiter — fuzzer-style tool that tries generated inputs against patterns to detect slowdown
- Semgrep has community rules for common ReDoS patterns in JavaScript and Python
Quick Node.js check:
const safeRegex = require('safe-regex');
const patterns = [
/^(a+)+$/, // vulnerable
/^(\w+\s?)*$/, // vulnerable
/^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$/ // check this
];
patterns.forEach(p => {
console.log(`${p} => ${safeRegex(p) ? 'safe' : 'VULNERABLE'}`);
});Common Vulnerable Patterns in Real Applications
These appear in production codebases regularly:
Email validation (vulnerable):
^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4}$The [a-zA-Z0-9.-]+ on the domain portion can trigger backtracking against inputs like a@aaaaaaaaaaaaaaa.
URL validation (vulnerable):
^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$The ([\/\w \.-]*)* at the end is a classic nested quantifier.
HTML tag matching (vulnerable):
<([a-z]+[a-z0-9]*)\s*([^>]*?)\s*\/?>The [^>]*? inside a group with adjacent quantifiers can misbehave with malformed HTML.
Log line parsing (vulnerable):
(\d+\.){3}\d+\s+(GET|POST|PUT|DELETE)\s+\/.*\s+HTTP\/\d+\.\d+The \/.* with .* and surrounding structure becomes vulnerable against very long path strings.
Safe Replacements and Patterns
Email validation — safe approach:
Don’t use regex for full RFC 5321 email validation. It’s genuinely difficult to do safely. Use a purpose-built library or a simple structural check:
# Python — simple safe check, not full RFC 5321
import re
def is_valid_email(email: str) -> bool:
if len(email) > 254:
return False
# Simple pattern with no nested quantifiers
pattern = r'^[^@\s]{1,64}@[^@\s]{1,255}$'
return bool(re.match(pattern, email))
# For production, use email-validator library instead
from email_validator import validate_email, EmailNotValidError
try:
validate_email(email)
except EmailNotValidError:
return False// Node.js — use validator.js for email validation
const validator = require('validator');
if (!validator.isEmail(input)) {
return res.status(400).json({ error: 'Invalid email' });
}URL validation — safe approach:
// Node.js — use the URL constructor instead of regex
function isSafeUrl(input) {
try {
const url = new URL(input);
return ['http:', 'https:'].includes(url.protocol);
} catch {
return false;
}
}// Java — use URI parsing
import java.net.URI;
import java.net.URISyntaxException;
public boolean isValidUrl(String input) {
try {
URI uri = new URI(input);
String scheme = uri.getScheme();
return "http".equals(scheme) || "https".equals(scheme);
} catch (URISyntaxException e) {
return false;
}
}Safe general-purpose pattern principles:
// Instead of (a+)+ — use possessive quantifiers or atomic groups if available
// JavaScript (Node.js 16+) supports possessive quantifiers:
const safe = /^(?>a+)+$/v; // atomic group prevents backtracking
// Or simply restructure to remove ambiguity:
// Instead of: /^(\w+\s?)*$/
// Use:
const safeWhitespace = /^[\w\s]+$/;# Python — use the 're2' or 'regex' module for RE2 engine (linear time guarantee)
# pip install google-re2
import re2
pattern = re2.compile(r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$')
# RE2 engine guarantees linear time matching — no backtrackingTimeouts as a Defence-in-Depth Control
Even with pattern review, timeouts catch regressions and supply-chain-introduced vulnerabilities:
// Node.js — enforce regex timeout using worker_threads
const { Worker, isMainThread, parentPort, workerData } = require('worker_threads');
function matchWithTimeout(pattern, input, timeoutMs = 50) {
return new Promise((resolve, reject) => {
const worker = new Worker(`
const { parentPort, workerData } = require('worker_threads');
const match = new RegExp(workerData.pattern).test(workerData.input);
parentPort.postMessage(match);
`, { eval: true, workerData: { pattern: pattern.source, input } });
const timer = setTimeout(() => {
worker.terminate();
reject(new Error('Regex timeout'));
}, timeoutMs);
worker.on('message', result => {
clearTimeout(timer);
resolve(result);
});
});
}// Java — ExecutorService timeout
import java.util.concurrent.*;
import java.util.regex.*;
public boolean matchWithTimeout(Pattern pattern, String input) throws Exception {
ExecutorService executor = Executors.newSingleThreadExecutor();
Future<Boolean> future = executor.submit(() -> pattern.matcher(input).matches());
try {
return future.get(100, TimeUnit.MILLISECONDS);
} catch (TimeoutException e) {
future.cancel(true);
throw new IllegalArgumentException("Input caused regex timeout");
} finally {
executor.shutdownNow();
}
}Where to Look in Your Codebase
ReDoS is most dangerous in input handling at system boundaries:
- HTTP header parsing: Content-Type, Accept, User-Agent validation
- Form input validation: email, phone, postcode, URL fields
- Log ingestion: regex-based log parsers processing external data
- API parameter validation: path parameters, query strings, JSON field validation
- Markdown/rich text parsing: if using regex-based parsers
- File path validation: upload filename sanitisation
Run safe-regex or vuln-regex-detector as part of your CI pipeline against all files containing regex literals. Most language ecosystems have linters or static analysis plugins that flag vulnerable patterns — add them to your existing SAST tool configuration.
The fix is almost always structural: remove nested quantifiers, add length limits before regex evaluation, or replace regex with purpose-built parsing for known formats (emails, URLs, dates).