ReDoS: How Catastrophic Backtracking in a Single Regex Can Take Down a Server

Catastrophic backtracking is how a single regex can take down a server

ReDoS — Regular Expression Denial of Service — is an attack where a carefully crafted input causes a regular expression to consume exponential time. Unlike most DoS vulnerabilities that require large amounts of traffic, a ReDoS attack needs only a single request with a specifically crafted string. The regex processes it for minutes, hours, or indefinitely, consuming 100% of a CPU core.

It's not theoretical. The Stack Overflow website was knocked offline for 34 minutes in 2016 by a ReDoS exploit in their Markdown parser. Cloudflare had a global outage in 2019 from a single ReDoS in a WAF rule.

How catastrophic backtracking works

Most regex engines use a backtracking algorithm. When a pattern fails to match at one position, the engine tries alternative branches. This is fine for most patterns. The problem arises with ambiguous patterns where the engine can explore exponentially many paths before concluding there's no match.

The classic evil regex:

(a+)+

This pattern is ambiguous for input like aaaaaaaaab. The engine tries:

• All as in one group: (aaaaaaaaaa) → fails on b
• Split: (aaaaaaaaa)(a) → fails on b
• Split: (aaaaaaaa)(aa) → fails on b
• (aaaaaaaa)(a)(a) → fails on b
• ...

For n characters followed by b, the number of ways to split the string into groups is 2^(n-1). With 30 as followed by b, that's about 500 million paths. With 40 as, half a trillion.

Common vulnerable regex patterns

Nested quantifiers on the same character class:

(a+)+
(a*)* 
(a+)*
(a|aa)+  (alternatives that can match the same string)

Overlapping alternatives:

(a|a)+
(\w+\s?)+  (word followed by optional space, repeated)

Real-world vulnerable patterns:

Email validation (a classic source of ReDoS):

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

This has nested groups with ambiguous matching. A 30-character string that partially matches before failing can produce millions of backtrack states.

The Stack Overflow and Cloudflare incidents

Stack Overflow (2016): Their Markdown parser used a regex for URL detection. An accidentally crafted post (not a malicious attack) contained text that triggered catastrophic backtracking. The CPU maxe out on one server, which caused the load balancer to shift traffic, eventually overloading all servers. 34 minutes of downtime.

Cloudflare (2019): A new WAF rule deployed globally contained:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|\{\}|\|\||\+)*.*(?:.*=.*))

This rule had catastrophic backtracking on certain inputs. Since Cloudflare processes every HTTP request through its WAF, the rule caused global CPU spikes, dropping 80% of HTTP traffic worldwide for ~27 minutes.

How to test for ReDoS vulnerability

The key test: does matching time grow exponentially as input size grows?

Manual testing:

import re, time

pattern = re.compile(r'(\w+\s?)+b')  # Potentially vulnerable

for length in [10, 20, 25, 30]:
    test_input = 'a' * length + 'b!'
    start = time.time()
    try:
        re.match(pattern, test_input)  # timeout would be better
    except Exception:
        pass
    elapsed = time.time() - start
    print(f"Length {length}: {elapsed:.3f}s")

If time doubles (or more) with each increment, the pattern is vulnerable.

Automated detection tools:

• safe-regex (Node.js npm package): static analysis for vulnerable patterns
• regexploit: Python tool that generates PoC inputs for vulnerable patterns
• reDOS-detector: multiple language support

Writing ReDoS-resistant patterns

Principle 1: Avoid nested quantifiers on the same class

Vulnerable:

(\w+)+     # outer + applied to a group with inner +
(a|b)*     # can match the same string many ways

Safe alternatives:

\w+        # not nested
[ab]*      # character class instead of alternation

Principle 2: Use possessive quantifiers or atomic groups (when available)

Possessive quantifiers (a++) or atomic groups (?>a+) prevent backtracking by committing to the first match. Supported in PCRE, Java, but not in JavaScript or Python's re module.

JavaScript alternative: use \w+ instead of (\w+)+, or avoid patterns that can match the same position multiple ways.

Principle 3: Limit scope with anchors

^\w+$      # anchored — can't backtrack into the string

Anchored patterns reduce the number of positions the engine can try.

Principle 4: Use linear-time regex engines

RE2 (Google's regex library) and Rust's regex crate guarantee linear-time matching for all regular expressions by using NFA/DFA algorithms that don't backtrack. The trade-off: no support for backreferences (\1) or lookaheads.

Node.js's @google/re2 npm package brings RE2's safety to JavaScript. Python's re2 package wraps the C++ library.

Timeouts as a safety net

Even with best practices, a ReDoS-resistant pattern might be introduced over time. Applying timeouts to regex operations provides a safety net:

import re, signal

def timeout_handler(signum, frame):
    raise TimeoutError("Regex timeout")

signal.signal(signal.SIGALRM, timeout_handler)
signal.alarm(1)  # 1 second timeout
try:
    result = re.match(pattern, input_string)
finally:
    signal.alarm(0)

More portable in Python 3.11+:

import re
# Python's re module doesn't natively support timeouts
# Use concurrent.futures with a timeout wrapper

How to use the Regex Tester on sadiqbd.com

1. Enter your pattern and test inputs
2. Test with progressively longer inputs that partially match before failing — specifically looking for exponential time growth
3. Test worst-case inputs — strings that look like they should match but don't, particularly at the boundary

Frequently Asked Questions

Is JavaScript vulnerable to ReDoS? Yes — JavaScript's regex engine uses backtracking. Several high-profile Node.js library vulnerabilities involved ReDoS (including vulnerabilities in path-to-regexp, used by Express.js). Modern V8 has some backtracking protections for specific patterns, but doesn't eliminate ReDoS.

How does Google's RE2 prevent ReDoS? RE2 uses Thompson NFA simulation, which tracks all possible states simultaneously. Instead of backtracking, it processes each input character once, guaranteeing O(n×m) worst case (n = input length, m = pattern length). The trade-off is no support for backreferences, which require exponential worst-case handling.

Is the Regex Tester free? Yes — completely free, no sign-up required.

ReDoS vulnerabilities are common, practically exploitable, and often introduced by code that looks reasonable. Testing for exponential growth in match time is a quick, practical check before deploying any complex regex pattern.

Try the Regex Tester free at sadiqbd.com — test your regex patterns against arbitrary inputs with live highlighting.