Most regex bugs are loud. The pattern matches the wrong thing, or it doesn't match at all, and you can see the problem immediately. The scarier kind is quiet: a build step, a form validator, or an API request just hangs, CPU pegged at 100%, with no error message pointing at the regex at all. This is catastrophic backtracking, and it's worth knowing how to recognize and fix it.
Step 1: Recognize the Shape of the Problem
Catastrophic backtracking happens when a regex engine, faced with a failing match, tries an exponential number of ways to make the pattern fit before giving up. It's almost always caused by nested or overlapping quantifiers, patterns like (a+)+b, (a*)*b, or ([a-zA-Z]+)*$. Each of these has an inner quantifier and an outer quantifier both trying to consume the same characters, which means there are many different ways to split up a matching string, and the engine tries all of them before concluding there's no match.
The tell is usually a request or script that works fine on short or well-formed input, then suddenly hangs on a longer or slightly malformed string. If your regex is running against user-controlled input, like a password field or a URL, and something starts timing out under load, a pathological regex pattern is worth checking before you assume it's a network or database issue.
Step 2: Isolate the Pattern and the Input
Before touching the pattern, reproduce the hang in isolation. Pull the exact regex and the exact input string out of your application code and run them somewhere you can kill the process safely, not inside a live request handler. If you don't have the exact triggering input, a long repeated character followed by a character that can't complete the match, something like forty a characters followed by a !, is a common way to trigger the exponential blowup in a pattern with nested quantifiers.
Step 3: Find the Nested Quantifier
Read through the pattern specifically looking for a quantifier applied to a group that itself contains a quantifier: (x+)+, (x*)+, (x+)*. These are the shapes that cause exponential backtracking. A single quantifier, even a greedy one over a long string, is not the problem by itself. It's the combination of two quantifiers that can both absorb the same characters that creates the exponential blowup.
Step 4: Rewrite to Remove the Ambiguity
Once you've found the nested quantifier, the fix is almost always to make the inner and outer quantifiers mutually exclusive, so there's only one way to split the string instead of many. (a+)+ matching a run of a characters can usually be rewritten as a single a+, since the outer + isn't adding anything the inner one doesn't already cover. For more complex cases, an atomic group or a possessive quantifier, where supported by your engine, tells the engine not to backtrack into that group at all once it's matched, which eliminates the exponential blowup directly rather than restructuring the pattern.
Step 5: Test Against a Deliberately Adversarial Input
Once you've rewritten the pattern, don't just confirm it still matches the input it's supposed to match. Test it against the pathological input that triggered the hang in the first place, and confirm it now fails fast instead of hanging. A pattern that matches correctly but is still exponentially slow on bad input hasn't actually been fixed, it just hasn't been triggered yet in production.
The Regex Tester at EvvyTools is useful here specifically because it shows you the match (or lack of one) instantly against whatever you paste in, so you can quickly compare the original pattern's behavior against the rewritten one on the same adversarial string.
Why This Matters More With User-Controlled Input
A pathological pattern that only ever runs against input you control, like a fixed config file your own code generates, is mostly a curiosity. The risk becomes serious the moment the string being matched comes from outside your system: a password field, a search query, a URL parameter, an uploaded filename. If an attacker can predict or influence what string gets tested against your regex, and your regex has a nested-quantifier vulnerability, they have a way to hang your server with a single crafted request, no exploit chain required beyond finding the vulnerable pattern. This is exactly why ReDoS shows up in security audits and dependency vulnerability scanners, not just as a performance nitpick.
How Different Engines Handle This Differently
Not every regex engine is equally vulnerable to catastrophic backtracking. Traditional backtracking engines, which cover most mainstream languages including JavaScript, Python's re module, Java, and PCRE, are the ones susceptible to exponential blowup from nested quantifiers, because they explore possible matches one path at a time and can end up retrying exponentially many paths on a failing match.
Some engines take a fundamentally different approach. Google's RE2 library, and Rust's regex crate, use algorithms that guarantee linear-time matching regardless of the pattern, by giving up certain features (like backreferences and some lookaround assertions) that make linear-time matching impossible to guarantee. If you're processing regex patterns that come from untrusted sources, rather than ones you wrote yourself, using a linear-time engine is a structural fix that eliminates the entire class of problem rather than relying on catching every dangerous pattern by manual review.
A Real Example Worth Studying
A pattern like ^([a-zA-Z0-9_.-]+)*$, meant to validate an identifier made of letters, numbers, dots, underscores, and hyphens, looks completely reasonable at first glance. The problem is the outer * wrapping an already-quantified inner group, [a-zA-Z0-9_.-]+. Against a long valid string, it matches fine and quickly, since there's no ambiguity, only one way for the string to satisfy the pattern. Against a long string that's almost valid but has one invalid character near the end, the engine has to try an exponential number of ways of splitting the valid prefix across repetitions of the outer group before concluding there's no match, and that's exactly the shape of input that takes microseconds to succeed on and can take minutes or hours to fail on, depending on the string length.
The fix here is straightforward once you see it: ^[a-zA-Z0-9_.-]+$ with no outer grouping at all does the identical job, since a single quantified character class already handles "one or more of these characters" without needing to be wrapped in another quantified group.
A Quick Mental Checklist
Before shipping a new regex pattern that will run against anything resembling user input, it's worth running through a short checklist: does any group with a quantifier contain another quantified group inside it, is the pattern going to run against strings whose length or content you don't fully control, and have you tested it against a long, deliberately non-matching input rather than only the input it's supposed to match. Catching a catastrophic backtracking pattern in a code review takes seconds once you know what to look for. Catching it after it's caused an incident takes considerably longer.
Further Reading
Wikipedia's article on ReDoS covers the underlying mechanics of catastrophic backtracking and how different regex engines are affected differently. OWASP's cheat sheet series covers this as a category of denial-of-service risk if you're validating regex patterns that come from user input rather than ones you wrote yourself. And regular-expressions.info's page on catastrophic backtracking walks through several more pattern shapes that trigger the same problem, beyond the two or three covered here.
If you want a deeper look at structuring regex patterns generally, EvvyTools has a longer guide on named versus numbered capture groups that's a useful next read once your patterns get more complex than a simple validation check.
Top comments (0)