A regex with catastrophic backtracking turns user input validation into a CPU drain - the confirming probe is a graduated timing oracle, not a large payload.
A regular expression with catastrophic backtracking turns user input validation into a CPU drain that can be sustained with trivial effort. The mechanism is deterministic: given a pattern that contains overlapping or nested quantifiers and a crafted string that forces the engine to explore every possible grouping before reporting no match, evaluation time grows exponentially with input length. The confirming probe is safe - a graduated timing oracle across inputs of 16, 32 and 64 characters exposes the growth curve without sending anything close to a damaging payload to a production endpoint.
The scan itself is lightweight. Three POST requests to the registration endpoint, each substituting a crafted email value of growing length. The baseline - a legitimate-looking address - returns in under 10 ms. The first crafted probe returns in over a second. The second exceeds 10 seconds. The third never returns at all within the timeout window. That curve is the artifact, not any error message or exception trace.
POST /api/auth/register email=user@example.com 200 OK 8 ms # baseline, legitimate input POST /api/auth/register email=aaaaaaaaaaaaaaab (16 a + b) 200 OK 1 840 ms # ~230x slower than baseline POST /api/auth/register email=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab (32 a + b) 200 OK 14 200 ms # ratio vs 16-char probe: 7.7x POST /api/auth/register email=aaaa...b (64 a + b) Timeout after 20 s (server CPU pegged) growth ratio 64-char / 16-char input: >1 000x # exponential confirmed
A naive probe that sends a 10 000-character string either hits the endpoint's request-size limit - returning 413 before any regex fires - or saturates the process so completely that the probe itself cannot distinguish a ReDoS from an overloaded server or a network timeout. Neither result is evidence. The graduated approach keeps every input below 100 characters, measures the ratio across the sequence, and uses that ratio as the confirming artifact rather than the raw timing.
All catastrophically backtracking patterns share one structural property: the same input character can satisfy more than one branch or repetition of the group, so the engine explores every valid assignment before declaring failure. The canonical cases below are the ones most commonly found in validation code.
| Vulnerable pattern | Why it backtracks | Safe rewrite |
|---|---|---|
| ^(a+)+$ | Outer and inner + can both consume the same characters in multiple combinations | ^a+$ (remove redundant outer quantifier) |
| ^(a|aa)+$ | Single and double 'a' overlap; engine tries both paths at every position | ^a+$ or ^(a{1,2})+$ with no overlap |
| ([\w.]+@)+[\w.]+ | \w and . each match the same character class; nested quantifier on both | Use a dedicated email validation library, not a regex |
| (.*a){N} for large N | .* can match zero to any chars before 'a'; exponential at each step | ([^a]*a){N} (negated class removes backtrack surface) |
| ^(\s*,\s*)+$ | Leading and trailing \s* each can match the separator gap | ^\s*(,\s*)+$ (anchor optional space outside quantifier) |
import requests, time, statistics # Evil input: N 'a' chars followed by 'b'. Never matches a well-formed email. # Forces full backtrack on any pattern that treats 'a' as a valid email char. def timed_probe(url, param, n, reps=5): payload = "a" * n + "b" times = [] for _ in range(reps): t0 = time.perf_counter() try: requests.post(url, data={param: payload}, timeout=20) except requests.exceptions.Timeout: times.append(20.0) # count as 20 s continue times.append(time.perf_counter() - t0) return statistics.median(times) t_base = timed_probe(TARGET, "email", 0) # empty + 'b' = baseline t16 = timed_probe(TARGET, "email", 16) t32 = timed_probe(TARGET, "email", 32) t64 = timed_probe(TARGET, "email", 64) ratio = t64 / t16 if t16 > 0.005 else 0 print(f"base={t_base:.3f}s t16={t16:.3f}s t32={t32:.3f}s t64={t64:.3f}s") print(f"ratio 64/16: {ratio:.1f}x") if ratio > 64: print("exponential confirmed") elif ratio > 8: print("super-linear confirmed - at minimum quadratic")
Severity follows how much of the event loop or thread pool a single request blocks and how accessible the endpoint is. An unauthenticated registration or search field where one 64-character request saturates a Node.js process for tens of seconds is high: the attacker needs no account, no token, and the cost is a single HTTP request. An authenticated, rate-limited path where each probe costs a session token is medium: real, but expensive to sustain. A regex that only runs in a background batch job behind a queue is low. Rating every instance critical because 'denial of service' reads as severe is the kind of over-claiming that makes the rest of the report less credible.
The remediation lives in the pattern, not the runtime. Removing the nested or overlapping quantifier eliminates the backtracking surface - a timeout shim only caps the damage. Where the runtime supports them, atomic groups ((?>...)) or possessive quantifiers (a++) commit the engine to the first match without backtracking. Python's re module does not support atomic groups; the regex package does. PCRE2, Rust's regex crate and RE2 use linear-time evaluation algorithms and reject catastrophically backtracking patterns at compile time - migrating to one of these eliminates the class at the engine level. SAST identifies the vulnerable pattern before any probe fires; DAST confirms the endpoint actually wires user input into it at real HTTP latency. A finding present in SAST but whose timing oracle never fires is rated reachable, not confirmed - the input may be sanitized upstream before it reaches the regex.