ReDoS Testing: Regular Expression Denial of Service Vulnerabilities

Regular Expression Denial of Service (ReDoS) is one of those vulnerabilities that gets dismissed as theoretical until it takes down a production service. In 2016, a single ReDoS bug in the moment.js date parsing library caused Cloudflare's build pipeline to hang. In 2019, a regex in the ua-parser-js package — used by millions of Node.js applications — was found to allow a single malicious user-agent string to spike CPU usage to 100% for seconds at a time.

For web applications, the attack surface is real: any endpoint that applies a regex to user-supplied input is potentially vulnerable. Email validation, URL parsing, username format checking, log format parsing, markdown rendering — all of them. This guide covers how ReDoS works at the engine level, how to identify vulnerable patterns in code review and black-box testing, and what remediation looks like in practice.

How Regex Backtracking Creates the Vulnerability

Most regex engines use a Non-deterministic Finite Automaton (NFA) model with backtracking. When a match attempt fails partway through, the engine backtracks to try alternative paths. For simple patterns, backtracking is bounded and fast. For certain pattern structures — particularly those with nested quantifiers or overlapping alternatives — the number of backtracking steps can grow exponentially with input length.

The canonical dangerous pattern is nested quantifiers with overlapping character classes:

# This pattern is catastrophic with certain inputs
^(a+)+$

# Equivalent catastrophic forms
^(a|aa)+$
^(a*)*$
^(a+)*$

For the pattern ^(a+)+$ against the input aaaaaaaaaaaaaab (N a's followed by a non-matching character), the engine must try every possible way to partition the N a's into groups, each of which is a non-empty sequence of a's. The number of partitions is 2^(N-1), so each added character doubles the work. At N=30, this means over a billion backtracking steps on a single regex evaluation.

Linear vs. Exponential vs. Polynomial ReDoS

ReDoS severity depends on the growth rate of backtracking steps:

Exponential cases are the most dangerous in web applications because a short input (20-40 characters) can hang a thread for seconds, making even a low-rate attack effective. Polynomial cases typically require larger payloads and are harder to weaponize against rate-limited endpoints.

Common Vulnerable Patterns in Real Applications

Email Validation

Email validation is one of the most common sources of ReDoS in production code. Developers reach for complex regex patterns that attempt to handle all valid email formats, not realizing the backtracking implications:

# Vulnerable email regex (simplified version of patterns found in real codebases)
^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

# More dangerous version found in several open-source frameworks
^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$

# Crafted input that triggers backtracking on the second pattern:
aaaaaaaaaaaaaaaaaaaaaaaaaaaa!

URL Parsing

# Vulnerable URL validation pattern
^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$

# The ([\/\w \.-]*)* portion creates catastrophic backtracking
# Trigger input: /aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

HTML/Markdown Sanitisation

# Seen in custom HTML stripping implementations
(<.*?>)+

# Multiple consecutive tags with a trailing invalid character will spin

Log Format Validation

# Common in logging middleware validation
^\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}(\.\d+)? (\w+ )+\w+$

# The (\w+ )+ portion causes backtracking on long log lines that don't match

Finding ReDoS in Code Review

Static analysis is the most reliable way to find ReDoS vulnerabilities before they reach production. The key is identifying patterns that exhibit ambiguity — where the same string can be matched in multiple ways by the regex.

Vulnerable structural indicators to look for:

• Nested quantifiers: (X+)+, (X*)*, (X?)*
• Alternation where branches overlap: (a|a)+, (ab|a)+b
• Quantified groups containing alternation: (a|b+)+
• Multiple adjacent optional groups with shared characters: (a+)(a*)
• Greedy quantifiers applied to character classes that overlap with what follows: [a-z]+[a-z]

Tools that automate this analysis:

• vuln-regex-detector (University of Virginia) — static analysis, checks for super-linear patterns
• regexploit (Doyensec) — finds exploitable ReDoS patterns and generates proof-of-concept inputs
• safe-regex (npm) — quick programmatic check in Node.js codebases
• rexsa — regex static analysis with REDOS detection
• Semgrep with ReDoS rulesets — integrates into CI/CD

# Using regexploit to test a pattern
pip install regexploit
echo "^(a+)+$" | regexploit

# Output:
# Pattern: ^(a+)+$
# Exploitable with input: aaaaaaaaaaaaaaaaaaaaaaaaaaab
# Steps at length 10: 1024
# Steps at length 20: 1048576

Black-Box Testing for ReDoS

When you don't have source access, black-box testing requires identifying inputs that the application applies regex validation to and then crafting inputs designed to trigger backtracking. This is harder but feasible for common patterns.

Step 1: Identify Regex-Validated Inputs

Any field that returns a format validation error for unexpected characters is a candidate. Common targets:

• Email address fields (login, registration, newsletter signup)
• Username and display name fields with format restrictions
• URL fields (website, avatar URL, webhook URL)
• Phone number validation
• File path inputs in upload or storage interfaces
• Search fields with query syntax validation
• API endpoints that accept structured string inputs (dates, IDs, slugs)

Step 2: Construct Candidate Attack Strings

For each candidate field, construct inputs that are likely to trigger backtracking based on common patterns for that field type. The general form is: repeated characters from the valid set, followed by a single invalid character.

# Email field — target the local part validation
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!@example.com

# For URL fields
https://aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

# For username fields
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

# Escalate length to observe time impact:
# Start at 10 chars, then 20, 40, 80 — look for exponential response time growth

Step 3: Measure Response Time

The signature of ReDoS is response time that grows exponentially or polynomially with input length. Measure carefully:

# Using curl with timing
for len in 10 20 30 40 50; do
  input=$(python3 -c "print('a' * $len + '!')")
  time curl -s -o /dev/null -w "%{time_total}" \
    -X POST https://target.example.com/api/register \
    -H "Content-Type: application/json" \
    -d "{\"email\": \"${input}@example.com\"}"
  echo " (length: $len)"
done

# ReDoS present: 10→0.05s, 20→0.05s, 30→0.12s, 40→2.4s, 50→timeout
# Normal behavior: consistent ~0.05s regardless of length

Step 4: Distinguish ReDoS from Other Slow Responses

Not all slow responses are ReDoS. Eliminate competing explanations:

• Network latency: send short inputs first to establish baseline RTT
• Database queries: ReDoS typically manifests before any DB interaction (during input validation)
• Rate limiting: if responses get faster after a delay, suspect rate limiting, not regex
• Server-side caching: vary the exact payload to avoid cache hits

A true ReDoS finding will show exponential time growth that is consistent and reproducible, unaffected by caching, and isolated to the validation phase (not dependent on whether credentials are correct or the user exists).

Framework and Language-Specific Notes

Node.js deserves special attention: because the event loop is single-threaded, a single thread stuck in a ReDoS regex blocks all other requests on that process. A single crafted request can take a Node.js microservice to 0 requests per second.

Real-World ReDoS Examples

The moment.js Incident

In 2016, CVE-2016-4055 identified that moment.js's date string format validation was vulnerable to ReDoS. The vulnerable pattern matched common date format strings but exhibited exponential backtracking on crafted inputs. Impact: any application that called moment(userInput) was vulnerable — including Cloudflare's internal tooling.

ua-parser-js

CVE-2021-27292: the user-agent parser library used in millions of Node.js applications contained a regex that processed the User-Agent header. An attacker could send a single HTTP request with a crafted user-agent that caused the parsing regex to spin, blocking the event loop for seconds. Since virtually every web framework logs or parses the user-agent, the attack surface was enormous.

Validator.js Email Regex

Multiple versions of validator.js — the most popular Node.js input validation library — contained email validation regexes with super-linear backtracking characteristics. Any application using validator.isEmail() was potentially vulnerable to a crafted email input causing thread stalls.

Remediation

Rewrite the Regex

The correct fix is to rewrite vulnerable patterns to remove ambiguity. Techniques:

• Possessive quantifiers (PCRE/Java): (a++)+ prevents backtracking into matched groups
• Atomic groups (PCRE/Java): (?>a+)+ same effect as possessive
• Simplify character class overlap: ensure alternation branches are mutually exclusive
• Anchor aggressively: add ^ and $ so the engine fails fast on non-matches
• Limit repetition count: {1,100} instead of + or * where input length is bounded

# Vulnerable
^([a-z]+)*$

# Fixed — atomic group prevents backtracking
^(?>([a-z]+))*$

# Fixed — possessive quantifier (Java/PCRE)
^([a-z]++)*$

# Fixed — use a DFA-based library (Go, Rust) when possible

Set Regex Timeouts

As a defense-in-depth measure, set timeouts on regex evaluation where the language supports it:

# Python — use the timeout module (no built-in regex timeout in re)
import signal
def timeout_handler(signum, frame):
    raise TimeoutError()

signal.signal(signal.SIGALRM, timeout_handler)
signal.alarm(1)  # 1 second
try:
    result = re.match(pattern, user_input)
finally:
    signal.alarm(0)

# .NET 7+ — NonBacktracking engine
var options = RegexOptions.NonBacktracking;
var regex = new Regex(pattern, options);

# Java — use interruptible matching with a timeout thread

Use Validated Libraries

For common validation tasks, use well-maintained libraries that have been audited for ReDoS rather than writing your own regex:

• Email validation: prefer format-based validation (@ present, local part non-empty, domain non-empty) over complex regex
• URL validation: use the platform's built-in URL parser (URL in browsers/Node, urllib.parse in Python)
• HTML sanitisation: use DOMPurify, bleach, or similar purpose-built sanitisers, not regex

Input Length Limits

Enforce maximum length on all user-supplied inputs before regex evaluation. A 254-character cap on email fields matches the RFC maximum and limits the blast radius of any ReDoS pattern that might be lurking.

# Enforce before regex
if len(user_input) > 254:
    return validation_error("Input too long")

# Only then apply regex
if not re.match(EMAIL_PATTERN, user_input):
    return validation_error("Invalid format")

Practical Testing Checklist

1. Identify all fields in the application that apply format validation (email, username, URL, phone, etc.).
2. For each field, send a baseline request with a short valid input and record response time.
3. Construct candidate payloads: N repeated valid characters followed by an invalid character (N = 10, 20, 40).
4. Measure response time at each input length — look for exponential or polynomial growth.
5. If source access is available, use regexploit or vuln-regex-detector to analyse each regex statically.
6. Check all third-party libraries for known ReDoS CVEs (dependabot / npm audit / pip-audit).
7. For Node.js applications, verify event loop blocking — a stuck regex will delay all subsequent requests, not just the matched thread.
8. Confirm fixes: after remediation, the response time should be flat regardless of input length.