Regular Expression Denial of Service (ReDoS)

Description

Regular Expression Denial of Service (ReDoS) is a vulnerability class where an attacker submits a specially crafted input string that triggers catastrophic backtracking in a regular expression engine, causing the matching process to take exponential time relative to the input length. A single request with a few hundred characters can consume 100% of a CPU core for seconds or minutes, and a modest request rate can take a single-threaded Node.js or Python application entirely offline.

CWE-1333 — Inefficient Regular Expression Complexity captures this class of issue. It arises from a design problem in the application's regex patterns rather than a configuration error, which is why OWASP classifies it under A04:2021 — Insecure Design. The vulnerability is in the regex itself — specifically in patterns that contain nested quantifiers or overlapping alternation groups that allow the engine's backtracking algorithm to explore an exponentially large number of matching paths.

The severity is most acute in Node.js applications because the event loop is single-threaded: one ReDoS request blocks all other request processing until the regex either matches or exhausts backtracking. Multi-threaded environments are still affected but can absorb attacks on multiple threads simultaneously.

How It Works

A classic vulnerable pattern is an email validator that uses nested quantifiers:

// Vulnerable regex — nested quantifier (a+)+ pattern
const emailRegex = /^([a-zA-Z0-9]+)*@example\.com$/;

// Benign input: fast match
emailRegex.test('user@example.com');        // ~0ms

// Malicious input: catastrophic backtracking
emailRegex.test('aaaaaaaaaaaaaaaaaaaaaa!'); // 10+ seconds

The ([a-zA-Z0-9]+)* pattern is ambiguous: the engine tries every possible way to distribute the characters between the outer * groups and the inner +, resulting in 2^n possible match paths for an input of length n.

A real-world example: the moment npm package's date parsing regex was vulnerable to ReDoS until patched. An attacker could stall a Node.js server processing date inputs with a request body like:

POST /api/events
{"date": "2023-01-AAAAAAAAAAAAAAAAAAAAAAAAA!"}

Tools like vuln-regex-detector and safe-regex (npm) statically analyse patterns for catastrophic backtracking before deployment:

# Check a pattern for ReDoS vulnerability
npx safe-regex '([a-zA-Z0-9]+)*@example\.com'
# Output: VULNERABLE

The OWASP-recommended tool regexploit generates proof-of-concept inputs for vulnerable patterns automatically.

Impact

• Denial of service — a single request with a crafted payload can block a Node.js event loop entirely for several seconds, causing a timeout for all concurrent users.
• Sustained service outage — an attacker sending 1-2 requests per second with ReDoS payloads can maintain near-total CPU saturation continuously without triggering volume-based rate limits.
• Cascading service failures — in microservice architectures, a single service DoS can cause request queuing and timeout failures in upstream services that depend on it.
• Amplification via public inputs — any input that reaches a vulnerable regex (search boxes, form fields, URL parameters) can be a DoS vector accessible without authentication.

Detection

1. Audit all regex patterns statically — run safe-regex, rxxr2, or regexploit against every regex in the application codebase and in installed dependencies' validation schemas.
2. Check known-vulnerable versions of validation libraries — run npm audit or pip-audit and check for known ReDoS CVEs in packages like validator, moment, urllib, and re2.
3. Test with long repetitive inputs — send inputs consisting of repeated characters followed by a character that cannot match (e.g., "A" * 100 + "!") to all fields that undergo regex validation and measure server response time.
4. Monitor CPU metrics during testing — use top or application performance monitoring (APM) to observe CPU spikes correlated with specific inputs.
5. Use regexploit for targeted payload generation — provide the tool with suspected vulnerable patterns to generate minimum-length proof-of-concept inputs.

Remediation

Rewrite patterns to eliminate ambiguity. The core fix is removing nested quantifiers and overlapping alternation. Use atomic groups where supported, or restructure the regex to ensure each character can only be matched by one part of the pattern.

// Vulnerable
/^([a-zA-Z0-9]+)*@/

// Fixed — no nested quantifier
/^[a-zA-Z0-9]+@/

Use the re2 library for untrusted input. Google's RE2 library enforces linear-time matching by design, making catastrophic backtracking impossible. Node.js bindings are available via the re2 npm package:

const RE2 = require('re2');
const safe = new RE2('^[a-zA-Z0-9]+@example\\.com$');
safe.test(untrustedInput); // Guaranteed linear time

Set regex timeout limits. Some platforms allow configuring a maximum execution time for regex operations. Use this as a backstop, not a primary defence.

Apply request-level rate limiting and timeouts. Implement request timeout middleware (e.g., connect-timeout in Express) to terminate requests that take longer than expected, preventing one ReDoS request from blocking the event loop indefinitely.