A regex denial-of-service vulnerability is a pattern that runs in polynomial or exponential time against certain crafted inputs, even though it runs fast against typical ones — which is exactly why it's dangerous: it passes every normal test case and then takes down a service the moment someone feeds it an adversarial string. Because the vulnerability lives in the pattern's structure rather than the input, the same regex is vulnerable everywhere it's deployed, across every codebase that copy-pasted it.
The structural signature to look for is a quantified group whose contents can match the same substring in more than one way, itself wrapped in another quantifier — (a+)+, ([a-zA-Z]+)*, and (a|a)* are all variations on this theme. When the engine's backtracking matcher hits a string that almost matches but ultimately fails, it has to try every possible way of partitioning the repeated content between the inner and outer repetition before concluding failure, and the number of partitions grows exponentially with input length.
This is not a hypothetical: it's a named entry in the OWASP list of denial-of-service attack vectors, and it has caused real, documented production outages, including a widely-cited 2016 incident where a single vulnerable regex in a WAF rule took down a large swath of the internet for around half an hour. The attack requires no authentication and no elevated privileges — anywhere user input reaches a vulnerable pattern (email validators, URL validators, log parsers) is exploitable by anyone who can submit a form.
This checker parses the pattern's structure to find nested-quantifier-over-overlapping-content shapes, and when it finds one, algorithmically constructs a concrete attack string — typically N copies of a character that satisfies the inner group, followed by one character that breaks the match — sized to actually demonstrate superlinear slowdown, not just a theoretical warning.
Edge cases worth knowing
- A pattern with two ambiguous groups back to back
- (a+)(a+)$ has ambiguity in how a run of 'a' characters splits between the two groups even without either being separately quantified — the checker treats adjacent groups with overlapping content as its own (milder but still relevant) backtracking risk, not just nested-quantifier shapes.
- A vulnerable shape that's unreachable because of an earlier anchor
- If a literal prefix before the vulnerable group can never match the attack string's prefix, the vulnerability is technically present in the pattern but not reachable by realistic attacker-controlled input. This checker still flags the pattern (the risk is real if the prefix changes later) but notes when the generated attack string required stripping an unmatchable literal prefix to demonstrate it.
- The same vulnerable shape across different regex engine flavors
- PCRE, RE2, and JavaScript's regex engine don't all backtrack the same way — RE2, notably, guarantees linear time by construction and simply doesn't have this vulnerability class. The attack string generated here targets classic backtracking engines (JavaScript, Python re, PCRE, Java); it won't demonstrate anything against RE2-based engines, which is itself useful information.
Common mistakes
- Load-testing a regex only with well-formed, realistic input and never with adversarial near-matches designed to maximize backtracking.
- Assuming a regex that 'looks simple' can't be exponential — the vulnerable shapes are often shorter than their safe equivalents.
- Deploying user-input validation regexes without any execution timeout or engine-level backtracking limit as a defense in depth measure.
- Fixing a reported ReDoS by adding an anchor or a length cap without addressing the underlying ambiguous-partition structure, leaving it exploitable for slightly shorter inputs.