Understanding ReDoS: Regular Expression Denial of Service

1. Catastrophic backtracking: the cause of ReDoS

Most regular expression engines, including PHP's PCRE engine, work on the backtracking principle: if part of a pattern doesn't match the input at a given position, the engine systematically tries alternative ways the previous, already successfully matched parts of the pattern could have been split differently, to still find an overall match. For most patterns, this backtracking process is harmless and fast, since there are only a few plausible alternative splits.

For certain pattern constructions, especially nested quantifiers like `(a+)+` or several consecutive quantifiers that can match the same characters like `(a|a)*`, however, the number of possible alternative splits explodes exponentially with input length, because the engine has to try a new, separate possibility for every additional combination of "how many a's does the outer group match" and "how many a's does the inner group match". With twenty repeated characters that's already over a million combinations, with thirty characters more than a billion, causing execution time to explode exponentially as input length grows linearly.

2. A classic vulnerable pattern in practice

A vulnerable pattern found repeatedly in the wild is a naive email validation with nested quantifiers for the local part, attempting to combine several valid character classes with optional repetitions without considering that these character classes can overlap each other. A specially crafted input like a long run of "a" characters followed by a single invalid character forces the engine to try essentially every possible split of the "a" run across the nested groups before it finally determines that no match exists.

<?php
declare(strict_types=1);

// VULNERABLE: nested quantifiers, catastrophic backtracking
$vulnerablePattern = '/^([a-zA-Z0-9]+)+@[a-zA-Z0-9]+\.[a-zA-Z]+$/';

// Input: 30 "a" characters followed by an invalid character "!"
$attackerInput = str_repeat('a', 30) . '!';

// This single line can block the PHP process for a very long time:
preg_match($vulnerablePattern, $attackerInput);

3. Reliably recognizing dangerous regex patterns

Three base patterns are responsible for catastrophic backtracking almost every time: nested quantifiers like `(a+)+` or `(a*)*`, several consecutive quantifiers over overlapping character classes like `[a-z]+[a-zA-Z]+`, and alternations with overlapping options inside a repeated block like `(a|a)*` or `(a|ab)*`. The common denominator across all these patterns is that there are multiple different ways the pattern could internally have split up the same successfully matched substring, forcing the backtracking engine to try each of these ways individually on a failure.

Automated analysis tools like `safe-regex` (for Node.js) or comparable static regex analyzers reliably detect these three base patterns by breaking the regular expression down into its structure and searching for exactly these dangerous combinations, instead of relying on manual code review, where a nested quantifier in the middle of a complex pattern is easily overlooked.

4. A safe formulation without nested quantifiers

The most robust fix is to reformulate the pattern so that only exactly one possible internal split exists for every successfully matched substring, usually achievable by removing unnecessary nesting and by using mutually exclusive rather than overlapping character classes.

<?php
declare(strict_types=1);

// SAFE: no nested quantifiers, evaluates linearly
$safePattern = '/^[a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-zA-Z]+$/';

// For stricter email validation: use a dedicated, hardened library
// instead of a hand-written regex (e.g. egulias/email-validator).
preg_match($safePattern, $input);

5. Timeout and resource-limit strategies as a second line of defense

Even with carefully reviewed patterns, a second line of defense in the form of a hard time limit on regex execution is worthwhile, since new, unknown vulnerable patterns can be accidentally introduced at any time, say through a user-configurable regex filter rule. PHP's `pcre.backtrack_limit` ini setting caps the number of allowed backtracking steps and makes `preg_match()` fail with `false` and the error code `PREG_BACKTRACK_LIMIT_ERROR` once exceeded, instead of running indefinitely.

This ini setting is a global limit for the entire PHP process, however, and can't be set granularly per individual regex call, which is why an additional explicit timeout at the application level makes sense for especially critical, user-controlled patterns, say by offloading the regex evaluation to a separate process with a hard time limit when users are allowed to define their own search patterns.

6. Deliberately testing for ReDoS susceptibility

An effective test method for ReDoS susceptibility is to test every regex pattern occurring in the code against an automatically generated, long repetition of a single character characteristic for the pattern while measuring execution time, where a disproportionate, exponential rise in time as input length grows linearly is a clear warning sign. This test combines well with the coverage-guided fuzzing described in the fuzzing article, since a fuzzer automatically stumbles onto exactly such inputs without a human having had to identify the vulnerable pattern beforehand.

Specialized online tools and libraries for static ReDoS analysis can also be integrated directly into the CI pipeline to automatically check every newly added or changed regex pattern against known dangerous constructions before the code is even merged.

7. Framework-side protections in Symfony

Symfony's routing component and validator constraints like `Regex` also internally use PHP's PCRE engine and are therefore fundamentally just as susceptible to ReDoS as hand-written code, when a developer enters a dangerous pattern into a route requirement (`requirements`) or a `Regex` validation constraint. Since route patterns are typically evaluated on every single incoming request, a vulnerable route pattern is especially critical, since an attacker doesn't need to find a special endpoint but can hit any arbitrary URL with the crafted input.

A sensible safeguard is therefore to review all patterns used in `requirements` blocks and `Regex` constraints just as carefully as hand-written validation logic, since Symfony itself performs no automatic ReDoS check on these patterns.

8. Known real-world ReDoS incidents as a warning

ReDoS is not a purely theoretical danger: one especially well-known incident took down Cloudflare's entire content delivery infrastructure worldwide for about 30 minutes in 2019, triggered by a single, vulnerable regex pattern in a web application firewall rule that caused catastrophic backtracking on certain inputs, driving CPU usage on nearly all affected servers to 100 percent almost simultaneously. This incident strikingly shows that even companies with extensive security teams and mature testing processes can be affected by ReDoS if a single pattern slips through review.

Several popular npm packages and PHP libraries have also had documented ReDoS CVEs in the past, often in seemingly harmless helper functions like trim, URL, or date-parsing routines, which shows that ReDoS vulnerabilities don't only lurk in obviously complex, hand-written patterns, but can also occur in widely used, heavily relied-upon standard libraries.

9. Protective measures at a glance

The table below compares the protective measures against ReDoS presented.

10. Summary

11. FAQ: ReDoS: The Essentials at a Glance