A single badly shaped regular expression can let one short request pin a CPU core for seconds or minutes, and in single-threaded runtimes such as Node.js that stalls every other user on the process. Regular expression denial of service (ReDoS) is catalogued by MITRE as CWE-1333 Inefficient Regular Expression Complexity and by CAPEC as CAPEC-492 Regular Expression Exponential Blowup. It affects every language whose default engine backtracks, which includes JavaScript, Java, Python, .NET, Ruby, PHP (PCRE) and Perl. This guide is for developers, AppSec engineers and platform teams: it explains why backtracking blows up, how to recognise risky patterns, which engines and settings remove the problem, and how to find, test and monitor regex risk across a codebase and its dependencies. It goes deeper than the general Input Validation and Output Encoding Guide and does not repeat it.
Key takeaways
- The cause is the engine, not just the pattern. Backtracking engines can take exponential or high polynomial time on near-matching input; linear-time engines such as RE2, Go regexp and the Rust regex crate cannot.
- Three shapes cause most ReDoS: nested quantifiers such as
(a+)+, alternation with overlapping branches inside a repetition such as(a|aa)+, and adjacent unbounded wildcards that can match the same text. - Bound everything: cap input length before matching, set a match timeout or backtrack limit where the engine supports one, and treat a timeout as a validation failure.
- Find it with tooling, prove it with tests: SAST rules (CodeQL, linters such as safe-regex) catch many risky patterns but not all, so add near-match performance tests to CI for every regex on an untrusted input path.
- Dependencies and infrastructure count: many published ReDoS CVEs sit in libraries (parsers, validators, user-agent and date libraries), and the Cloudflare outage of 2 July 2019 came from a WAF rule, not application code.
Why backtracking regex engines blow up
Most regex engines in mainstream languages compile a pattern into a nondeterministic finite automaton and explore it with backtracking: when the current path fails, the engine returns to the last choice point and tries another way of matching. OWASP's ReDoS page uses ^(a+)+$ to show the effect: an input of four letters followed by a non-matching character has 16 possible paths, and an input of sixteen letters followed by a non-matching character has 65,536, doubling with every extra character. The engine must try them all before it can report "no match".
Three practical consequences follow:
- Failure is the expensive case: the Node.js documentation notes that the exponential behaviour typically appears on a mismatch, so a vulnerable pattern can pass functional tests that only use valid input.
- Short input is enough: GitHub's CodeQL query help explains that for an exponential pattern, adding ten characters can make matching roughly 1,000 times slower. Request size limits in the tens of kilobytes do not protect you.
- Polynomial cases matter too: patterns that are only quadratic or cubic (for example two adjacent
.*segments with a required suffix) are slower to hurt, but large inputs such as log lines, headers or uploaded documents make them practical.
Microsoft's .NET documentation puts it bluntly: with excessive backtracking, execution time can double for each additional character and a short input string can take hours or days to process. In Node.js that means the event loop is blocked, and the whole process stops serving every client until the match finishes.
Recognising risky patterns
OWASP defines an "evil regex" as one with a grouping with repetition, where inside the repeated group there is either another repetition or an alternation whose branches overlap. The table below lists the shapes to look for in review and the safer rewrite in each case.
| Risky shape | Example pattern | Why it is risky | Safer approach |
|---|---|---|---|
| Nested quantifier | (a+)+, ([a-zA-Z]+)* | Inner and outer repetition can split the same run of characters in exponentially many ways | Flatten to a single quantifier: a+, [a-zA-Z]* |
| Overlapping alternation in a repetition | (a|aa)+, (a|a?)+, (__|.)+ | Each character can be consumed by more than one branch | Make branches mutually exclusive, e.g. CodeQL's rewrite (__|[^_])+ |
| Repeated group with optional separator | (\w+[-.]?)+@ style e-mail checks | Optional separator lets the group boundary fall anywhere | Require the separator, or validate with a parser and a length limit |
| Adjacent unbounded wildcards | .*x.*=.* | Polynomial time as each wildcard trades characters with the next | Anchor, use negated character classes ([^=]*), or split the string first |
| Backreferences and look-around | (a.*)\1 | No engine can guarantee linear time for backreferences (Node.js docs) | Avoid on untrusted input; do the comparison in code |
| Regex built from user input | new RegExp(userValue) | The attacker supplies the pattern itself (regex injection) | Escape metacharacters (OWASP ASVS 5.0 V1.2.9) or use plain string search |
Two simpler rules from the Node.js guidance remove a large share of risk: if you only need a literal substring, use indexOf, includes, startsWith or the local equivalent, which never exceed linear time; and for common formats such as URLs, IP addresses and file paths, use a maintained parser rather than a hand-written expression.
Choosing a regex engine
The most robust fix is an engine that cannot backtrack exponentially. The trade-off is features: linear-time engines drop backreferences and, in most cases, look-around.
| Language or runtime | Default engine behaviour | Linear-time or bounded option | Notes |
|---|---|---|---|
| Go | regexp package is guaranteed to run in time linear in the size of the input | Default | Uses RE2 syntax (except \C); no backreferences |
| Rust | regex crate: worst case O(m * n) for regex size m and input size n | Default | No look-around or backreferences by design |
| C++ and bindings | RE2 guarantees match time linear in input length and works within a memory budget | RE2 (bindings exist for many languages, e.g. node-re2) | Designed to accept patterns from untrusted users |
| .NET 7 and later | Backtracking by default, default timeout is Regex.InfiniteMatchTimeout | RegexOptions.NonBacktracking (linear time); matchTimeout parameter; process-wide REGEX_DEFAULT_MATCH_TIMEOUT | Timeout raises RegexMatchTimeoutException; Microsoft says these are not a security boundary against malicious patterns |
| JavaScript (V8, Node.js) | Irregexp backtracking engine | Experimental linear engine behind V8 flags (--enable-experimental-regexp-engine for the l flag, or fallback on excessive backtracks, default threshold 50,000); RE2 bindings | V8 flags are experimental and exclude backreferences, look-around and some flags; prefer RE2 bindings or worker isolation in production |
| Python | re backtracks | Atomic groups (?>...) and possessive quantifiers (*+, ++) since Python 3.11; RE2 bindings | No built-in match timeout in re; enforce limits by input length or by running matches in a separate worker |
| PHP (PCRE) | Backtracking | pcre.backtrack_limit (cited by CWE-1333) | Check the return value: hitting the limit is an error, not "no match" |
| Java | java.util.regex backtracks; no built-in timeout | Possessive quantifiers and atomic groups; RE2/J; bounded input | Run untrusted matching with an input cap; consider a linear engine library |
Decision guidance:
- Patterns supplied by users or tenants (search filters, routing rules, custom detection rules): use a linear-time engine. CWE-1333 notes this is one of the few effective mitigations for user-provided expressions, and Microsoft states its timeout and non-backtracking features are not intended as a security boundary against malicious patterns.
- Developer-authored patterns on untrusted input: a linear engine where the feature set allows; otherwise rewrite the pattern, add atomic groups or possessive quantifiers, cap input length and set a timeout.
- Patterns that need backreferences or look-around: keep them off untrusted paths, or parse in code. A timeout plus a length cap is the minimum.
- Small teams: the cheapest high-value step is a length cap at the edge plus a SAST rule. Large organisations: standardise a safe regex wrapper per language (engine, timeout, logging) and block raw constructors through lint rules.
Secure coding controls
- Cap length first: the OWASP Input Validation Cheat Sheet says to bound input length before matching. Apply the cap per field (an e-mail address does not need more than a few hundred characters), not only per request.
- Anchor and match the whole value: use
^...$or an API such as Python'sfullmatch, which also reduces the search space the engine explores. - Remove ambiguity: make alternation branches mutually exclusive, replace
.*with negated classes, and use atomic groups or possessive quantifiers where the engine has them (.NET(?>...), Python 3.11 and later, Java). - Set timeouts and fail closed: in .NET pass a
matchTimeoutor set the application default; in PHP handle backtrack-limit errors. OWASP's guidance is to treat a timeout as a validation failure, never as success. - Escape dynamic input: when part of a pattern must come from data, escape it (
Regex.Escape, Pythonre.escape, or an equivalent helper in JavaScript). OWASP ASVS 5.0 V1.2.9 (Level 2) requires escaping regex metacharacters. - Isolate expensive matching: in Node.js, never run heavy regex on the event loop for untrusted input; move it to a worker thread or a separate service with its own CPU limit and kill switch.
- Keep regex out of security-critical parsing: URL, HTML and e-mail parsing need maintained parsers. The OWASP cheat sheet is explicit that regular expressions cannot replace HTML sanitisation.
OWASP ASVS 5.0 requirement V1.3.12 (Level 3) asks verifiers to confirm that regular expressions are free from elements causing exponential backtracking and that untrusted input is sanitised to mitigate ReDoS. Use it as the acceptance criterion in code review. See the Secure Code Review Guide.
Finding ReDoS in code and dependencies
| Method | What it finds | Limits |
|---|---|---|
SAST queries (for example CodeQL js/redos and js/polynomial-redos, Java ReDoS queries) | Ambiguous repetitions and data flow from request sources to the regex | False negatives on dynamically built patterns; needs triage |
| Pattern linters (safe-regex, recommended in the Express security best practices; rxxr2) | Star height and known risky shapes in literal patterns | The Node.js docs warn neither tool catches all vulnerable patterns |
| Software composition analysis | Known ReDoS CVEs in dependencies (CWE-1333 lists examples such as CVE-2020-5243 and CVE-2021-21317) | Only finds disclosed issues; prioritise reachable paths |
| Performance unit tests | Super-linear growth on near-matching inputs of increasing length | Only covers patterns someone wrote a test for |
| Fuzzing with time budgets | Slow inputs that no reviewer predicted | Needs a harness and a per-input time threshold |
| Rule-set profiling (WAF, log parsing, detection rules) | Expensive rules in infrastructure configuration | Often owned outside AppSec; must be included in scope |
For performance tests, generate inputs that nearly match (valid prefix, invalid final character) at lengths such as 10, 20, 40 and 80 characters and assert that time grows roughly linearly. Microsoft's guidance recommends testing with near-matching input for exactly this reason. Keep the generator inside the test suite; you do not need to publish attack strings. See the Fuzzing Guide and the Dependency Update Automation Guide.
How to implement: a phased rollout
- Inventory (week 1 to 2): run SAST and a linter across all repositories and list every regex that sees untrusted input: request handlers, validators, routing, log and document parsers, and configuration such as WAF or gateway rules.
- Set the edge controls: add per-field length limits at the API gateway or framework validation layer. This is low risk and immediately shrinks the exploitable input size.
- Fix the high-risk patterns: rewrite exponential patterns first, then user-supplied patterns (move to a linear engine), then polynomial patterns on large inputs. Track each fix to a test.
- Introduce a safe wrapper: one helper per language that applies the chosen engine, a timeout, a length cap and structured logging. Add a lint rule that flags direct regex constructors on request data.
- Gate in CI: start the ReDoS SAST rule in report-only mode for two to four weeks, tune false positives, then make high-severity findings blocking for new code.
- Test before switching engines: RE2 and .NET NonBacktracking do not accept every construct, and the Node.js docs warn that RE2 is not fully compatible with V8 regexps. Run the full test suite, ship behind a feature flag, and roll back by toggling the flag to the previous engine.
- Cover infrastructure rules: add CPU profiling of every rule to the test suite for WAF, IDS and log-pipeline rule sets, and deploy rule changes in stages.
Detection and measurement
- Log timeouts: every
RegexMatchTimeoutException, PCRE backtrack-limit error or wrapper timeout should emit a structured event with the pattern identifier (not the raw input), the route and the caller identity. - Watch latency shape: a ReDoS looks like a few requests with extreme latency on one route, high CPU on one core and event-loop lag in Node.js, rather than a volume flood. Alert on event-loop delay and per-route p99 latency.
- Correlate with callers: repeated timeouts from one API client or token suggest probing. For machine clients, tie the event to the API key or workload identity so it can be throttled or revoked. See the Rate Limiting and API Abuse Guide.
| Metric | Target |
|---|---|
| Regexes on untrusted paths with a length cap and timeout or linear engine | 100% for internet-facing services |
| Open ReDoS SAST findings (high severity) older than 30 days | Zero |
| Dependencies with known CWE-1333 CVEs on reachable paths | Zero past the patch SLA |
| Regex timeout events per million requests | Stable baseline; investigate spikes |
| Rule-set changes deployed with CPU profiling and staged rollout | 100% |
Framework mapping
| Framework | Reference | How it applies |
|---|---|---|
| MITRE CWE | CWE-1333 Inefficient Regular Expression Complexity | Weakness class for SAST findings and CVE triage |
| MITRE CAPEC | CAPEC-492 Regular Expression Exponential Blowup | Attack pattern for threat modelling |
| MITRE ATT&CK | T1499.004 Application or System Exploitation | Endpoint denial of service by exploiting application weaknesses |
| OWASP ASVS 5.0 | V1.3.12 (ReDoS), V1.2.9 (escaping regex metacharacters) | Verification requirements for review and testing |
| NIST SP 800-53 Rev. 5 | SI-10 Information Input Validation; SC-5 Denial-of-service Protection; SA-11 Developer Testing and Evaluation | Input checks, DoS resilience and developer testing |
| NIST CSF 2.0 | PR.PS-06 secure software development; ID.RA-01 vulnerabilities identified | Programme-level outcomes |
| CIS Controls v8.1 | Control 16 Application Software Security | Secure coding and application testing safeguards |
| ISO/IEC 27001:2022 | Annex A 8.28 Secure coding | Coding standards that include regex rules |
Common failure patterns
- Testing only valid input: functional tests pass because matches are fast; the cost is on near-misses that nobody tested.
- Copying validation patterns from the internet: OWASP's ReDoS page shows that published e-mail and class-name patterns in regex libraries, including an old OWASP repository entry, were themselves vulnerable.
- Treating a timeout as a match or ignoring it: code that catches the exception and continues turns a DoS into a validation bypass.
- Forgetting infrastructure regex: on 2 July 2019 a Cloudflare WAF Managed Rules update contained a regular expression that backtracked heavily and exhausted CPU used for HTTP and HTTPS serving, causing 502 errors for about 27 minutes. Cloudflare's post-incident review lists a global rather than staged push, tests that checked correctness but not CPU, and a CPU-protection safeguard removed weeks earlier.
- Relying on one linter: safe-regex style tools miss polynomial cases and dynamically assembled patterns.
- Switching engines without regression tests: unsupported constructs or behaviour differences break validation silently or throw at start-up.
Lessons from incidents
Cloudflare's own review of the July 2019 outage is the clearest public case study of ReDoS in production. Its corrective actions map directly to controls on this page: reintroduce the CPU-usage protection, manually review all 3,868 WAF Managed Rules for backtracking risk, add performance profiling for every rule to the test suite, move to the re2 or Rust regex engine for their run-time guarantees, and introduce staged rollouts for rule changes while keeping an emergency global path. The lesson for application teams is that a regex is code: it needs performance tests, a safe engine and a staged deployment like any other change. See the Denial of Service at Application Layer Guide.
Practitioner checklist
- Inventory every regex that processes untrusted input, including WAF, gateway and log-parsing rules.
- Enforce per-field length limits before any regex runs.
- Rewrite nested quantifiers and overlapping alternations; anchor patterns and match the whole value.
- Use a linear-time engine (RE2, Go, Rust, .NET NonBacktracking) for user-supplied patterns.
- Set match timeouts or backtrack limits and treat any timeout as a validation failure.
- Escape all data inserted into dynamic patterns.
- Run ReDoS SAST rules in CI and add near-match performance tests for each risky pattern.
- Track CWE-1333 CVEs in dependencies and patch reachable ones within SLA.
- Log regex timeouts with route and caller identity, and alert on event-loop lag and p99 latency.
- Deploy regex-heavy rule sets in stages with CPU profiling.
Standards and references
- OWASP: Regular expression Denial of Service - ReDoS
- MITRE: CWE-1333 Inefficient Regular Expression Complexity
- MITRE CAPEC: Regular Expression Exponential Blowup
- OWASP: Input Validation Cheat Sheet
- OWASP: Application Security Verification Standard 5.0
- Microsoft Learn: Best practices for regular expressions in .NET
- Node.js: Don't Block the Event Loop (or the Worker Pool)
- Cloudflare: Details of the Cloudflare outage on July 2, 2019
Related NHI Mgmt Group resources: Input Validation and Output Encoding Guide · Node.js Security Guide · Secure Coding Guide · Denial of Service at Application Layer Guide · WAF and WAAP Buyer's Guide