ReDoS Protection: Fix Fatal Regex Flaws In 5 Minutes

The 27-Minute Outage: When One Regex Took Down 13% of the Internet

In July 2019, a single regular expression in Cloudflare's WAF ruleset caused a global outage that dropped 13% of the company's traffic for 27 minutes straight. The culprit wasn't a bug in the code—it was a regex pattern that, under specific input conditions, triggered catastrophic backtracking. A pattern designed to detect malicious cross-site scripting attempts instead became the attack vector itself.

That event crystallized what those of us building regex validation tools already understood: regular expressions aren't just pattern-matching utilities. They're computational functions that can be weaponized against the systems running them. ReDoS—Regular Expression Denial of Service—is the class of vulnerability that exploits this reality, and if you're shipping regex patterns to production without testing for it, you're operating without a seatbelt.

The 10-Second Threshold: Understanding How ReDoS Actually Works

Most production systems enforce request timeouts somewhere between 5 and 30 seconds. A ReDoS attack succeeds when an attacker crafts an input string that forces your regex engine into a backtracking loop exceeding that threshold. The request hangs, the thread pool exhausts, and legitimate traffic queues up behind it until the system collapses under its own weight.

Here's the mechanism. Most regex engines use NFA (Nondeterministic Finite Automaton) matching, which means they try multiple paths through the pattern when a match fails. When you write a pattern like (a+)+b and feed it a string of 30 'a' characters without a trailing 'b', the engine doesn't just fail once. It tries every possible combination of group repetitions before concluding no match exists. That's not linear time—it's exponential.

The Math Behind Catastrophic Backtracking

Let's make this concrete with numbers. The pattern ^(a+)+$ evaluated against a string of 25 'a' characters requires approximately 2^25—roughly 33 million—backtracking steps. On a modern CPU doing 10 million steps per second, that's about 3.3 seconds for a 25-character string. Add just 5 more characters and you're at 2^30 steps: over a billion operations, roughly 107 seconds. One more character doubles it again.

This is why ReDoS protection matters. The difference between "instant match" and "system down" can literally be a single character in the input string.

The 99% Problem: Three Pattern Structures That Cause Almost All ReDoS Vulnerabilities

After analyzing thousands of regex patterns through validation tools, the data is clear: nearly all ReDoS vulnerabilities fall into three structural categories. Eliminate these from your patterns and you eliminate the vast majority of risk.

Mistake 1: Nested Quantifiers Like (a+)+

The classic offender. When you nest a quantifier inside another quantifier, you create an exponential number of ways the engine can partition the input string. The pattern (a+)+b looks harmless—it's trying to match one or more groups of one or more 'a' characters followed by 'b'. But for a string like "aaaaaa" with no 'b', the engine tries: one group of 6, two groups of 3+3, two groups of 2+4, three groups of 2+2+2, and so on. Every partition becomes a separate path.

The fix: Flatten the quantifier. (a+)+b becomes a+b. They match the same strings, but the second version has exactly one path through the input. No backtracking explosion possible.

Mistake 2: Overlapping Alternation Like (a|a)*

When alternation branches can match the same input, the engine tries both. The pattern (a|a)*b against "aaaa" without 'b' forces the engine to explore 2^n paths, where n is the string length. At 30 characters, that's over a billion steps.

This mistake often appears in disguised forms: (\s|\t)*, ([0-9]+|\d+), (\w+|[a-zA-Z0-9_]+). Each has overlapping branches creating the same exponential behavior.

The fix:

Collapse overlapping branches into a single character class or equivalent. (a|a)*b becomes a*b. (\s|\t)* becomes \s*, since \s already includes the tab character as a subset. ([0-9]+|\d+) becomes \d+. (\w+|[a-zA-Z0-9_]+) becomes \w+. The principle is straightforward: if two alternation branches can match the same character, merge them into one. If you genuinely need alternation for distinct cases, ensure each branch matches a disjoint set of inputs so the engine never has a reason to backtrack between them.

Mistake 3: Quantified Groups That Can Match Empty Strings

The subtler offender. When a group inside a quantifier can match zero characters, the engine faces ambiguity: it cannot decide how many times to repeat the group versus how much each repetition should consume. The pattern (a?)* looks innocent—it is trying to match zero or more groups of an optional 'a'. But feed it a string of 'a' characters without a terminator, and the engine explores exponentially many ways to partition the string into repetitions where some groups match an 'a' and others match nothing.

This structure appears frequently in real-world patterns: (.*)*, (\s*)*, (\w*)*, (a*)*. Each allows the inner group to match empty, creating the same exponential blowup as nested quantifiers. The engine cannot distinguish between "repeat the group 5 times, each matching 2 characters" and "repeat the group 10 times, alternating between matching 2 characters and matching nothing."

The fix: Ensure quantified groups cannot match empty strings. If you need (a?)*, rewrite it as a*. If you need (\s*)*, collapse it to \s*. If you genuinely need a quantified group, make sure the group requires at least one character to match—use (a+)* only when the outer quantifier is truly necessary, and even then, test it with adversarial input before shipping.

The 5-Minute Audit: How to Detect ReDoS Vulnerabilities Before They Ship

Now that you know the three structural patterns responsible for nearly all ReDoS vulnerabilities, the question becomes: how do you find them in your codebase quickly? Here is a practical audit process that takes roughly five minutes per pattern.

Step 1: Search for Nested Quantifiers

Run a search for patterns containing a quantifier (+, *, ?, {n,}) immediately followed by another quantifier, or a quantified group containing a quantifier. The regex \([^)]*[+*?][^)]*\)[+*?] catches the most common forms like (a+)+, (a*)*, and (a?)+. Review every match manually—some may be safe, but each one warrants scrutiny.

Step 2: Search for Overlapping Alternation

Look for alternation within quantified groups: (...|...)*, (...|...)+. For each match, ask whether the branches are disjoint. If branch A can match a string that branch B can also match, you have overlap. Common culprits include (\s|\t), (\d|[0-9]), (\w|[a-zA-Z0-9_]), and (http|https)—the second branch matches a subset of the first when followed by additional characters.

Step 3: Search for Empty-Matching Quantified Groups

Find quantified groups where the inner content is optional or can match zero characters. Look for (...?)*, (...*)*, (.*)*, (\s*)*. Each of these creates the ambiguity that leads to exponential backtracking. These patterns are easy to miss because they often appear inside larger expressions where the dangerous subpattern is buried among legitimate matching logic.

Step 4: Run an Automated ReDoS Scanner

Manual review catches the obvious patterns, but subtle vulnerabilities can hide in complex expressions with 50 or more characters. Use an automated scanner that applies static analysis to detect ambiguous patterns and dynamic testing to verify them with adversarial input. Tools like safe-regex for Node.js, Google's RE2 engine, and dedicated regex validation platforms can flag dangerous patterns in seconds. The scanner should report the specific subpattern causing the vulnerability and suggest a safe alternative.

Step 5: Test With Adversarial Input

For every regex that handles user input, generate a test string designed to trigger backtracking. If the pattern contains (a+)+, feed it 30 'a' characters without the expected terminator. If it contains (a|a)*, do the same. Measure the execution time. If it exceeds 100 milliseconds, you have a vulnerability. In production under load, that same pattern will take down your service.

Prevention by Design: Building ReDoS-Resistant Patterns

Detection is reactive. Prevention is proactive. The following design principles keep ReDoS out of your patterns from the start.

Use Possessive Quantifiers and Atomic Groups

If your regex engine supports them, possessive quantifiers (a++, a*+, a?+) and atomic groups ((?>a+)) prevent backtracking by locking in a match once it is made. The pattern (?>a+)+b cannot backtrack into the inner group, eliminating the exponential path. Not all engines support these features—JavaScript's built-in RegExp does not—but many server-side engines do, including PCRE, Java's java.util.regex, and .NET's System.Text.RegularExpressions.

Switch to a Linear-Time Engine

Google's RE2 engine guarantees linear-time matching by using a Thompson NFA algorithm that does not backtrack. It is available as a library for Go, Python, C++, and Node.js. If you are processing untrusted input with regex, RE2 eliminates ReDoS by construction. The trade-off is that RE2 does not support backreferences or lookahead and lookbehind assertions. For most input validation patterns, you do not need those features anyway.

Set Match Timeouts

As a defense-in-depth measure, configure your regex engine to abort matching after a timeout. .NET supports this natively via Regex.Match(input, pattern, options, TimeSpan). Java does not have built-in timeout, but you can run the match in a separate thread and interrupt it. This does not fix the vulnerability—it merely limits the blast radius. A timed-out request still consumes a thread for the duration of the timeout window, so under sufficient load, timeouts alone will not save you.

Anchor Your Patterns

Unanchored patterns force the engine to try matching at every position in the input string. A pattern like (a+)+b without anchors against a 1000-character string means the engine attempts the exponential match starting at position 0, then position 1, then position 2, and so on. Anchoring with ^ and $ ensures the engine attempts the match once. This does not eliminate the backtracking problem, but it prevents multiplying it across every position in the input.

The Bottom Line

ReDoS is not a theoretical vulnerability class. It has taken down Cloudflare, Stack Exchange, and countless applications that never made the news. The structural patterns that cause it—nested quantifiers, overlapping alternation, and quantified empty-matching groups—are well understood, easily identifiable, and straightforward to fix. The five-minute audit described above will catch the vast majority of vulnerabilities in your codebase. The design principles will keep them from coming back.

If you are shipping regex patterns that process user input without testing for catastrophic backtracking, you are accepting a vulnerability that is trivial to exploit and devastating in impact. The attacker does not need to find a zero-day or bypass your authentication. They just need to send a 30-character string to the right endpoint. Run the audit. Fix the patterns. Sleep better.