01 //Introduction
Regex Denial of Service (ReDoS) is a server-side availability bug where a single crafted input forces a regular-expression engine into exponential or polynomial work, pinning a CPU core and blocking the event loop or thread. The carrier is almost always a pattern with nested quantifiers ((a+)+$), overlapping alternation ((a|ab)+$), or a quantified optional group ((a?){50}a{50}) running on user-controlled input. The bug class was formalised by Crosby and Wallach in 2003, has hit Cloudflare, Stack Overflow, Express, npm packages with tens of millions of weekly downloads, and still ships fresh CVEs every quarter because the vulnerable pattern, an innocent-looking regex over user input, is the most natural way to write a validator.
The bug sits in the gap between the regex an author thinks they wrote and the work the engine actually performs. Most mainstream engines (PCRE, Perl, JavaScript, Python re, Java java.util.regex, .NET Regex, Ruby Onigmo) use a backtracking NFA: when a quantifier fails to match, the engine rewinds and tries other partitionings. For a benign input, this is fast. For an adversarial input against a vulnerable pattern, the engine explores 2^n partitionings before giving up. CWE-1333 (Inefficient Regular Expression Complexity) is the canonical reference; OWASP ReDoS is the introduction.
regexp (RE2-based) and Rust's regex crate are linear-time by construction, but the entire JavaScript, Python, Java, Ruby, .NET, and PCRE ecosystem still ships backtracking engines because backreferences and lookaround are widely used and not expressible in a pure NFA. .NET added Regex.MatchTimeout in 4.5 and a non-backtracking option in .NET 7, Java added java.util.regex improvements in 9 and 11, and V8 added a non-backtracking experimental engine, but none of these are defaults. Every code reviewer still has to read each regex on user input and verify it does not contain the evil shapes, or sandbox it behind RE2 / timeouts / a length cap.OWASP catalogues the issue on its ReDoS page and the Denial of Service Cheat Sheet. The defensive recipe is identical across languages: do not run untrusted regex on user input; if the pattern is hard-coded, prove it is linear-time (no nested quantifiers, no overlapping alternation, anchored where possible); cap input length before the regex runs; and prefer a linear-time engine (RE2, Hyperscan, Rust's regex crate) for any production path that touches attacker-controlled bytes. This module walks through the catastrophic backtracking mechanism, the canonical evil-regex shapes, real CVEs from production systems, and the per-language fix that removes the bug class properly.
A Node.js endpoint validates email addresses with /^([a-zA-Z0-9])(([\\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]\\w{2,}$/. An attacker submits 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!'. What happens?
02 //The Attack Flow
Every ReDoS exploit follows the same four-stage flow: the attacker identifies a vulnerable pattern on a user-input path, crafts a small string (often under 100 bytes) that maximises backtracking, sends it to the endpoint, and waits for the worker process to consume CPU until either the request times out, the OOM killer fires, or the autoscaler gives up. With a single-threaded runtime like Node.js, one request blocks every other in-flight request on the same process; with a thread-per-request runtime like classic Java servlets, it blocks one thread but a few hundred concurrent requests blocks the whole pool.
2^n match paths through nested quantifiersReDoS is not a memory bug, an injection bug, or a logic bug. The regex is doing exactly what the engine was asked to do: enumerate every possible match path. With a vulnerable pattern, the number of paths grows exponentially in the length of the input, so a 50-byte string can pin a CPU core for minutes. On single-threaded runtimes (Node.js, single-worker Python ASGI, classic PHP-FPM with one worker), one request takes the whole process down.
The shape of a realistic exploit depends on where the regex sits in the request path. A regex inside a body parser fires before any application code, so the attacker does not need to authenticate. A regex inside a logger fires after the request returns, so the attack is invisible to the request timeout. A regex inside a search-filter compilation fires once per query, so a paid attacker with a free tier can amplify cost. Almost every disclosed ReDoS sits in one of these three positions, body parsing, logging, or filter compilation, because each one is reached by attacker bytes on every request.
Common Sink Surfaces in Real Applications
| Where the regex lives | Typical attacker payload |
|---|---|
| Email / phone / URL validators in form handlers | A 50-byte string matching the prefix but failing the final anchor |
| Express path-to-regexp route compilation | Routes like /:foo(((a+)+)+)b that compile slowly at startup or per-mount |
| Body / cookie / header parsers | Crafted Content-Type, Accept-Language, or Set-Cookie strings |
| Log parsers (Pino, Winston, structlog, Logstash grok) | A log line embedded in a user field that defeats the parser |
| Markdown / BBCode / syntax highlighters | A code block or link that triggers a vulnerable tokeniser regex |
| HTML sanitisers and CSS validators | Crafted style attribute or selector with overlapping alternation |
| WAF / SIEM / SOAR correlation rules | A request body that defeats a rule maintained by a different team |
| User-submitted alerting rules (Prometheus, Datadog, Sentry) | A label matcher regex the user controls directly |
| Auto-link / mention extraction in chat / forum software | A long string of @ signs and periods that thrash the URL detector |
/users/:id into regular expressions. In 2024, two CVEs (CVE-2024-45296 and the follow-up CVE-2024-52798) shipped because the compiled regex for certain parameter patterns was exponential in the input length. The fix took two releases: clamp the parameter regex to a non-backtracking shape and then move to a hand-written parser that does not use regex at all. Almost every JavaScript router on the planet picked up the patch within a week.1// VULNERABLE, the regex runs in the request thread (Node.js single-threaded
2// event loop) and a 60-byte adversarial input pins the CPU for minutes.
3
4const express = require('express');
5const app = express();
6
7// BAD, classic Stack-Overflow email pattern. Nested quantifiers around the
8// local-part create catastrophic backtracking on inputs that almost match.
9const EMAIL = /^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]\w{2,}$/;
10
11app.post('/signup', express.json(), (req, res) => {
12 // No length cap, no timeout, no linear-time engine.
13 if (!EMAIL.test(req.body.email)) return res.status(400).json({ error: 'bad email' });
14 // ...
15 res.json({ ok: true });
16});
17
18// Attacker payload: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"
19// (30 a's followed by a non-matching char). The local-part regex tries
20// to partition the a-string across (([\-.]|[_]+)?([a-zA-Z0-9]+))* in
21// 2^30 different ways before giving up. CPU usage on the process: 100%.
22// Concurrent requests: stuck. Event loop: frozen.The team adds a 5-second request timeout in nginx in front of the Node.js process. A pentester reports the service still goes offline under ReDoS attack. Why?
03 //Payload Anatomy & Evil Regex Shapes
A regular expression becomes a ReDoS sink the moment it has an ambiguous parse over some input prefix, meaning more than one way for the engine to assign characters to quantified groups, combined with a final mismatch that forces the engine to try them all. The canonical shapes are nested quantifiers ((a+)+), overlapping alternation ((a|aa)+, (a|ab)+), and quantified optional groups ((a?){n}a{n}). Each shape produces exponential or polynomial blowup depending on the engine and the input.
- Nested quantifiers:
(a+)+$,(a*)*$,(a|a)*$ - Overlapping alternation:
(a|aa)+$,(a|ab)+$ - Quantified groups with optional content:
(a?)50a50 - Greedy + lazy collisions inside the same group:
(.*?)* - Email-validation patterns copied from Stack Overflow circa 2010
- CSS selectors, URL validators, and HTML tag scrubbers built with one big regex
- Body parsers and Express middleware (path-to-regexp, body-parser)
- Log parsers and Loki / Grafana label matchers
- WAF rules, SIEM correlation rules, and SOAR playbooks
- Markdown renderers and syntax highlighters (Prism, highlight.js)
- Validation libraries (joi, yup, zod refinements with custom regex)
- User-submitted regex (search filters, alerting rules, label selectors)
The shape to grep for is a quantifier inside a group followed by another quantifier on the group itself: (X+)+, (X*)*, (X+)*, or any alternation where two branches can match the same prefix ((a|a)+, (a|ab)+). If the regex runs on user input, treat the file as a finding until someone proves the pattern is linear-time on adversarial input.
Payload Catalogue, What an Attacker Actually Submits
| Vulnerable regex | Attacker input | Behaviour |
|---|---|---|
| /^(a+)+$/ | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" | Exponential 2^n: 30 a's plus one non-matching char takes seconds; 35 a's takes minutes |
| /^(a*)*$/ | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" | Same exponential blowup; empty matches make the inner quantifier explore all splits |
| /^(a|aa)+$/ | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" | Overlapping alternation: each a can match either branch, giving 2^n parses |
| /^(a|ab)+b$/ | "aaaaaaaaaaaaaaaaaaaaaaaaaaab" | Exponential before the trailing b is reached |
| /^.*a.*a.*a.*a.*a.*$/ | "aaaaaaaaaaaaaaaaaaaaaaaaaab" | Polynomial O(n^5); generalises to O(n^k) for k repeated .* patterns |
| /^\s*([a-z]+\s*)+$/i | "a a a a a a a a a a a a a a a a a a a a!" | Greedy whitespace + greedy word causes ambiguous splits at every space |
| /^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*@/ | "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!" | The classic email validator; nested quantifiers in the local part |
| /^(\d+)*$/ | "1111111111111111111111111111x" | Numeric variant of (a+)+; identical exponential behaviour |
1// 1) The textbook evil regex. Nested quantifier on the same character class.
2// Input length 30 takes seconds, 35 takes minutes, 40 takes hours.
3const EVIL_1 = /^(a+)+$/;
4
5// 2) Overlapping alternation. Two branches that can match the same prefix.
6// Same exponential profile because each character has two parse choices.
7const EVIL_2 = /^(a|ab)+b$/;
8
9// 3) Polynomial ReDoS, less dramatic but harder to spot in code review.
10// Each .* doubles the parse choices; five .* groups give O(n^5) work.
11const EVIL_3 = /^.*a.*a.*a.*a.*a.*$/;
12
13// Reproduce the blowup in a REPL (do not run on a production process):
14// const start = Date.now();
15// EVIL_1.test('a'.repeat(35) + '!');
16// console.log(`elapsed: ${Date.now() - start} ms`);
17//
18// On a 2025 laptop, n=30 takes ~1s, n=35 takes ~30s, n=40 takes ~15 min.setTimeout fires after the current synchronous block completes. The same is true of Python's default re module: the GIL is held throughout the match, signal-based timeouts only work on the main thread on Unix, and there is no portable way to cancel a regex in flight. A "timeout" implemented in user-land is a no-op against ReDoS. The only ways to enforce a timeout are (a) move the regex into a worker thread or subprocess and kill it, (b) switch to a linear-time engine, or (c) cap the input length before the regex runs.A reviewer says 'we cap user input at 10 KB, so we are safe from ReDoS'. A teammate replies 'the exponential regex /^(a+)+$/ takes minutes on 40 bytes of input'. Who is right and what is the minimal correct rule?
04 //Mitigation Patterns
There are four correct mitigations, in rough order of preference. Use a linear-time regex engine (RE2 via re2, node-re2, or Go's standard regexp) for any pattern that runs on user-controlled input; rewrite the pattern to be unambiguous (no nested quantifiers, no overlapping alternation, anchored where possible); cap input length before the regex runs to the smallest value the feature needs; and run the regex inside a worker thread or subprocess with a hard wall-clock timeout that the runtime can actually enforce. Each one is a few lines of code; the discipline is to apply them at every user-input regex, not just the obvious ones.
Mitigation Options at a Glance
| Strategy | How | When to use |
|---|---|---|
| Switch to a linear-time engine | node-re2 / re2 in JS, google-re2 in Python, Hyperscan in C/C++, Rust regex crate, Go regexp | Always, for any regex that runs on attacker bytes. Linear-time engines do not backtrack and cannot be DoSed. |
| Rewrite the pattern | Remove nested quantifiers, possessive quantifiers where supported, atomic groups, character classes instead of alternation | When you must use the default engine (regex includes backreferences, lookaround, or non-trivial features RE2 lacks). |
| Cap input length | Express body-parser limit, validator.js isLength, or a guard at the controller before the regex runs | Backstop for polynomial patterns. Useless alone against exponential blowup but reduces blast radius. |
| Wall-clock timeout in a sandbox | worker_threads + Atomics.wait, child_process.execFile, .NET Regex.MatchTimeout, Java JDK 9+ patterns | When the regex genuinely needs backtracking features and rewriting is not an option. |
| Static analysis in CI | safe-regex, regexp-tree, recheck, rxxr, ReScue, Cody on regex literals | Always. Catches the most common evil shapes at code-review time before the regex ever ships. |
| Ban user-submitted regex | If users need search filters, expose a structured DSL or compile through RE2; do not pass user regex to /.../ | Anywhere user-supplied patterns reach a regex engine: alerting rules, log filters, search boxes. |
1// lib/safe-regex.js, the only allowed regex constructor for user-input patterns.
2//
3// Strategy: every regex that runs on user input is constructed through RE2,
4// a linear-time engine without backtracking. The default JavaScript engine
5// is still allowed for hard-coded patterns proven safe by safe-regex in CI.
6
7const RE2 = require('re2');
8
9// USE THIS for any regex that touches user input. RE2 refuses to compile
10// patterns it cannot run in linear time, so /(a+)+$/ throws at construction
11// instead of pinning the CPU at request time.
12function safeRegex(source, flags = '') {
13 try {
14 return new RE2(source, flags);
15 } catch (err) {
16 // RE2 throws on patterns it cannot run linearly. That is the correct
17 // outcome: the pattern is rejected at construction time, in CI or at
18 // service startup, instead of blowing up at runtime on adversarial input.
19 throw new Error(`regex rejected by RE2: ${err.message}`);
20 }
21}
22
23// Pre-compile at module load. If a pattern is unsafe, the service fails to
24// start, which surfaces the bug in CI rather than in production.
25const EMAIL_RE = safeRegex('^[^\\s@]+@[^\\s@]+\\.[^\\s@]+$');
26
27function validateEmail(input) {
28 if (typeof input !== 'string') return false;
29 if (input.length > 254) return false; // RFC 5321 cap, applied BEFORE the regex.
30 return EMAIL_RE.test(input);
31}
32
33module.exports = { safeRegex, validateEmail };(\w+)\s+\1), lookbehind ((?<=foo)bar), or lookahead (foo(?=bar)) do not compile in RE2. That is usually a good thing: if the regex needs a backreference, it is probably trying to do something a parser would handle better. When you absolutely need lookaround, accept the engine limitation by either (a) splitting the regex into two linear passes that achieve the same effect, or (b) keeping the backtracking engine but running the regex in a sandboxed worker with a wall-clock timeout that the OS can enforce.1// Before: catastrophic backtracking on near-misses.
2const BAD_EMAIL = /^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]\w{2,}$/;
3
4// After: anchored, no nested quantifier, no overlapping alternation. Each
5// character has exactly one parse path, so the engine runs in O(n).
6const GOOD_EMAIL = /^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}$/;
7
8// Better yet: use a real email parser (e.g., RFC 5321 implementation) for
9// authoritative validation, and reserve regex for cheap structural checks.
10function isStructurallyValidEmail(s) {
11 if (typeof s !== 'string') return false;
12 if (s.length > 254) return false; // RFC cap.
13 if (s.indexOf('@') !== s.lastIndexOf('@')) return false; // Reject multiple @.
14 return GOOD_EMAIL.test(s);
15}
16
17// The two-pass form: split before regex to remove ambiguity.
18// Bad: /^(\w+)+\s+(\w+)+$/ (nested + overlapping)
19// Good:
20function parsePair(s) {
21 const parts = s.trim().split(/\s+/, 3);
22 if (parts.length !== 2) return null;
23 if (!/^\w+$/.test(parts[0]) || !/^\w+$/.test(parts[1])) return null;
24 return { first: parts[0], second: parts[1] };
25}1# safe_regex.py, the only allowed regex constructor for user-input patterns.
2#
3# google-re2 wraps the same RE2 engine used by Go. It refuses to compile
4# patterns that cannot run in linear time, surfacing unsafe regex in CI
5# instead of in production.
6
7import re2 # pip install google-re2
8
9MAX_LEN = 1024
10
11EMAIL_RE = re2.compile(r"^[^\s@]+@[^\s@]+\.[^\s@]+$")
12
13def validate_email(value: str) -> bool:
14 if not isinstance(value, str):
15 return False
16 if len(value) > 254: # RFC 5321 cap BEFORE the regex.
17 return False
18 return EMAIL_RE.fullmatch(value) is not None
19
20# If google-re2 cannot be installed (some platforms), fall back to the
21# stdlib re module but ONLY for patterns audited offline with safe-regex
22# or a similar static analyser, AND with a strict length cap.
23import re
24
25def safe_match(pattern: "re.Pattern[str]", value: str, max_len: int = MAX_LEN) -> bool:
26 if len(value) > max_len:
27 return False
28 return pattern.fullmatch(value) is not None1// SafeRegex.java, runs the regex in a fork-join task with a hard wall-clock
2// timeout. Java does not interrupt running regex by default,
3// but explicit Thread.interrupt() at safe points works on
4// modern JDKs combined with cooperative cancellation.
5//
6// For production, prefer Google's RE2/J library (com.google.re2j:re2j) which
7// is a drop-in replacement that runs in linear time.
8
9import com.google.re2j.Pattern;
10import com.google.re2j.Matcher;
11
12public final class SafeRegex {
13 private static final int MAX_INPUT = 1024;
14 private static final Pattern EMAIL =
15 Pattern.compile("^[^\\s@]+@[^\\s@]+\\.[^\\s@]+$");
16
17 public static boolean validateEmail(String input) {
18 if (input == null) return false;
19 if (input.length() > 254) return false; // RFC cap.
20 if (input.length() > MAX_INPUT) return false; // Defensive cap.
21 Matcher m = EMAIL.matcher(input);
22 return m.matches();
23 }
24}
25
26// RE2/J trades backreferences and lookaround for linear-time guarantees.
27// If you need those features, run java.util.regex inside an ExecutorService
28// task with a future.get(timeout, MILLISECONDS) and Thread.interrupt() on
29// timeout. java.util.regex respects the interrupt at backtracking points
30// on JDK 9+, though the cancellation can lag by milliseconds.1// Go's standard regexp package is built on RE2 and is linear-time by
2// construction. There is no ReDoS in idiomatic Go regex usage. The trade-off
3// is the same as RE2 in other languages: no backreferences, no lookaround.
4
5package validate
6
7import (
8 "regexp"
9)
10
11var emailRe = regexp.MustCompile(`^[^\s@]+@[^\s@]+\.[^\s@]+$`)
12
13func IsEmail(s string) bool {
14 if len(s) > 254 {
15 return false
16 }
17 return emailRe.MatchString(s)
18}
19
20// If you import a third-party regex library (rare but possible, e.g., for
21// PCRE compatibility via github.com/dlclark/regexp2), you re-introduce
22// backtracking and lose the linear-time guarantee. Stay on the standard
23// library unless you have a specific reason to leave it.1// The Rust regex crate is linear-time by construction (NFA + lazy DFA).
2// Like RE2, it does not support backreferences or arbitrary lookaround.
3// For PCRE-compatible patterns the fancy-regex crate is available but
4// re-introduces backtracking and ReDoS risk; do not use it on user input.
5
6use once_cell::sync::Lazy;
7use regex::Regex;
8
9static EMAIL: Lazy<Regex> = Lazy::new(|| {
10 Regex::new(r"^[^\s@]+@[^\s@]+\.[^\s@]+$").expect("valid pattern")
11});
12
13pub fn is_email(s: &str) -> bool {
14 if s.len() > 254 {
15 return false;
16 }
17 EMAIL.is_match(s)
18}
19
20// The crate also exposes RegexBuilder::size_limit and dfa_size_limit, which
21// bound memory rather than time. Set them on every Regex built from user
22// input (e.g., search-filter compilation) to bound compile-time DoS.A developer says 'we use Go, so we are immune to ReDoS'. Is that correct?
05 //Format-Specific Concerns: Routes, Logs, and User-Submitted Regex
Switching to a linear-time engine in your own code is necessary but not sufficient. ReDoS has several format-specific subtleties that produce real, exploitable bypasses: routers that compile user-influenced paths to regex (path-to-regexp), loggers that parse fields with embedded regex (grok, regex-based redaction), validation libraries that wrap a default backtracking engine (joi, yup, validator.js), and user-facing surfaces where the user submits the regex directly (Prometheus alerting, Grafana label matchers, Sentry inbound filters). Each one has produced disclosures in mainstream products.
Per-Surface Behaviour and Required Defense
| Surface | Bypass pattern | Correct defense |
|---|---|---|
| Express / Koa / Next.js routers (path-to-regexp) | Route params like /:foo(((a+)+)+)b compile to exponential regex | Pin path-to-regexp to a patched version (>= 6.3.0 / 8.0.0); avoid custom param regex |
| Validation libraries (joi, yup, validator.js, zod refinements) | Built-in email / URL / slug validators built on backtracking patterns | Audit the library version; prefer .max() length caps and structural checks over regex; swap to RE2-backed validators |
| Log parsers (grok, Logstash, Loki, Vector) | A log field crafted to defeat a grok pattern pins the ingest worker | Use Hyperscan in Vector / Loki; cap label values; reject log lines beyond N bytes pre-parse |
| Markdown / BBCode renderers | Crafted code blocks defeat the tokeniser regex | Use a non-regex parser (commonmark, remark) or constrain block sizes; run rendering in a worker thread |
| CSS / HTML sanitisers | Style attribute or selector triggers exponential alternation in the parser | Use sanitize-html / DOMPurify which use DOM walks not regex; audit any "regex-only" sanitiser |
| WAF / SIEM correlation rules | A request body that defeats a rule built by another team takes down ingest | Compile WAF rules through Hyperscan or RE2; load-test every new rule with adversarial inputs |
| User-submitted alerting rules and label matchers | A Prometheus selector =~ "(a+)+" pinned the rule evaluator (real bug, CVE-2019-3826) | Compile user regex through RE2; reject any rule the linear-time engine refuses to compile |
| Search filters in business apps | A "search by regex" feature where user input becomes /input/ | Switch to substring / fuzzy search; expose a structured filter DSL; compile via RE2 only |
1// app.js, pin path-to-regexp to a patched version and avoid custom regex
2// in route parameters. Custom param regex is the historical source
3// of every path-to-regexp ReDoS CVE.
4
5const express = require('express');
6const app = express();
7
8// SAFE, standard parameter (compiles to a simple non-backtracking pattern).
9app.get('/users/:id', handler);
10
11// SAFE, simple character-class restriction (still linear).
12app.get('/users/:id([a-z0-9-]+)', handler);
13
14// DANGEROUS, nested or unbounded custom regex in a route param. Avoid
15// completely; do the validation in the handler with RE2 instead.
16// app.get('/users/:id((a+)+)', handler); // <- never write this
17
18// In package.json, pin to a patched release:
19// "path-to-regexp": "^8.2.0"
20// and run `npm audit` in CI. Routers that share path-to-regexp (Koa,
21// Vercel edge, Next.js) inherit the patch through the same dependency.1// lib/user-regex.js, every user-supplied pattern flows through here.
2//
3// Strategy: compile through RE2, which refuses unsafe patterns at construction.
4// If RE2 throws, return a structured error to the user explaining that the
5// pattern is too expensive. Never fall back to the default JS engine.
6
7const RE2 = require('re2');
8
9const MAX_PATTERN_LEN = 1024;
10const MAX_INPUT_LEN = 64 * 1024;
11
12class UserRegexError extends Error {
13 constructor(message, code) {
14 super(message);
15 this.code = code;
16 }
17}
18
19function compileUserRegex(pattern, flags = '') {
20 if (typeof pattern !== 'string') {
21 throw new UserRegexError('pattern must be a string', 'invalid');
22 }
23 if (pattern.length > MAX_PATTERN_LEN) {
24 throw new UserRegexError('pattern too long', 'too_long');
25 }
26 try {
27 return new RE2(pattern, flags);
28 } catch (err) {
29 // RE2 rejects backreferences, lookaround, and patterns it cannot run
30 // in linear time. Surface a clean error so the UI can explain the
31 // restriction; do NOT fall back to the default engine.
32 throw new UserRegexError(`unsupported pattern: ${err.message}`, 'unsafe');
33 }
34}
35
36function testUserRegex(regex, input) {
37 if (typeof input !== 'string' || input.length > MAX_INPUT_LEN) {
38 throw new UserRegexError('input too large', 'too_large');
39 }
40 return regex.test(input);
41}
42
43module.exports = { compileUserRegex, testUserRegex, UserRegexError };1// lib/sandbox-regex.js, for patterns that genuinely need backtracking.
2//
3// Runs the regex in a worker thread, kills the worker on timeout. Because
4// the worker has its own event loop, the synchronous regex executes on a
5// separate OS thread and the main process keeps serving traffic.
6
7const { Worker } = require('worker_threads');
8const path = require('path');
9
10function execWithTimeout(pattern, flags, input, timeoutMs = 100) {
11 return new Promise((resolve, reject) => {
12 const worker = new Worker(path.join(__dirname, 'regex-worker.js'), {
13 workerData: { pattern, flags, input },
14 });
15 const timer = setTimeout(() => {
16 worker.terminate();
17 reject(new Error('regex timeout'));
18 }, timeoutMs);
19 worker.once('message', (result) => {
20 clearTimeout(timer);
21 resolve(result);
22 });
23 worker.once('error', (err) => {
24 clearTimeout(timer);
25 reject(err);
26 });
27 });
28}
29
30module.exports = { execWithTimeout };
31
32// regex-worker.js
33// const { workerData, parentPort } = require('worker_threads');
34// const { pattern, flags, input } = workerData;
35// const re = new RegExp(pattern, flags);
36// parentPort.postMessage(re.test(input));A team migrates a validation hot path to node-re2. CI passes. A week later, a new endpoint silently ships /^(\\w+)+@/ using the default RegExp because the developer forgot the helper. What is the structural fix?
06 //Detection in Code Review
ReDoS has a narrow, well-known surface: every regex literal and dynamic RegExp constructor that runs on attacker-controlled input. Grep gets you most of the way; the rest is reading the pattern to confirm it does not contain nested quantifiers, overlapping alternation, or quantified optional groups. SAST tools have improving coverage; the better tooling parses the regex AST, looks for the canonical evil shapes, and proves a pattern is or is not in the safe class (recheck, safe-regex, regexp-tree, ReScue).
1# Find every regex literal and every dynamic regex constructor in the repo.
2# Each one is a place to verify the pattern is linear-time on adversarial input.
3
4# JS / TS regex literals (anchored variants of the evil shapes)
5rg -nP "\((?:[^()]+)\+\)\+" --type=ts --type=js
6rg -nP "\((?:[^()]+)\*\)\*" --type=ts --type=js
7rg -nP "\((?:[^()|]+)\|(?:[^()]+)\)\+" --type=ts --type=js
8
9# Dynamic RegExp construction, every one needs to run through safeRegex
10rg -n "new RegExp\(" --type=ts --type=js
11
12# Python re.compile and re.match (audit against re2 alternative)
13rg -n "re\.(compile|match|search|fullmatch|findall)\(" --type=py
14
15# Java Pattern.compile (audit against RE2/J)
16rg -n "Pattern\.compile\(" --type=java
17
18# .NET Regex / RegexOptions (does it set MatchTimeout?)
19rg -nP "new Regex\(" --type=cs
20rg -n "RegexOptions\.NonBacktracking" --type=cs # the good pattern
21
22# Route parameters with custom regex (path-to-regexp surface)
23rg -nE "app\.(get|post|put|delete|patch)\([^,]+\(.*[\+\*]" --type=js
24
25# User-submitted regex (the highest-risk surface)
26rg -n "userRegex|filterRegex|new RegExp\(req\.|new RegExp\(input"
27
28# The right pattern, a shared helper
29rg -n "safeRegex|UserRegex|RE2|node-re2|google-re2"SAST / Linter Coverage
| Tool | Rule | Catches |
|---|---|---|
| eslint-plugin-redos | redos/no-vulnerable | JS/TS regex literals statically classified as vulnerable using recheck |
| safe-regex (npm) | CLI / programmatic | Star-height heuristic; flags nested quantifiers and overlapping alternation |
| recheck (ReScue successor) | CLI / VS Code extension | AST-based analysis with attack-string synthesis; lower false-positive rate than safe-regex |
| Semgrep | javascript.lang.security.audit.regex.regex-redos | Pattern-based detection of evil-regex shapes across JS, TS, Python, Java |
| CodeQL | js/redos and py/redos query suites | Polynomial and exponential ReDoS detection through static analysis of regex literals |
| Snyk Code | CWE-1333 rule family | Multi-language detection of vulnerable regex; cross-references known CVE patterns |
| GitHub Code Scanning | redos default queries | Runs CodeQL queries on every push; surfaces findings in PR reviews |
1# semgrep-rules/redos.yaml
2rules:
3 - id: nested-quantifier-redos
4 languages: [javascript, typescript]
5 severity: ERROR
6 message: >-
7 Regex with a nested quantifier (e.g. (X+)+, (X*)*) is exponential
8 on adversarial input. Use RE2 (node-re2) for any pattern on user input,
9 or rewrite the regex to be unambiguous.
10 patterns:
11 - pattern-either:
12 - pattern: /$X+\)\+/
13 - pattern: /$X*\)\*/
14 - pattern: /$X+\)\*/
15 - pattern: /$X*\)\+/
16 metadata:
17 cwe: 'CWE-1333'
18 owasp: 'A06:2021 - Vulnerable and Outdated Components'
19
20 - id: regexp-on-user-input
21 languages: [javascript, typescript]
22 severity: WARNING
23 message: >-
24 new RegExp() built from user input is a direct ReDoS sink. Compile
25 through compileUserRegex (RE2) and reject patterns the engine refuses.
26 patterns:
27 - pattern-either:
28 - pattern: new RegExp(req.$X, ...)
29 - pattern: new RegExp(req.body.$X)
30 - pattern: new RegExp($INPUT)
31 - pattern-not-inside: |
32 function compileUserRegex(...) { ... }
33 metadata:
34 cwe: 'CWE-1333'(X+)+, (X*)*) or overlapping alternation ((a|aa)+, (a|ab)+)? (2) Is the input length capped before the regex runs? (3) Is the regex compiled through a linear-time engine (RE2 / RE2J / Hyperscan / stdlib Go / Rust regex crate)? (4) For dynamic new RegExp(userInput), does it flow through the user-regex helper? (5) Are router param regexes (path-to-regexp) on patched library versions? (6) Are validation libraries (joi, yup, validator.js) on patched versions? (7) Does CI run safe-regex, recheck, or CodeQL's ReDoS queries? Any "no" is a finding.1// __tests__/redos.spec.js, characterisation test for the validator.
2// Confirms (a) correctness on benign input and
3// (b) bounded runtime on adversarial input.
4
5const { validateEmail } = require('../lib/safe-regex');
6
7describe('validateEmail', () => {
8 it('accepts a well-formed email', () => {
9 expect(validateEmail('alice@example.com')).toBe(true);
10 });
11
12 it('rejects a malformed email', () => {
13 expect(validateEmail('not-an-email')).toBe(false);
14 });
15
16 it('runs in bounded time on the canonical ReDoS payload', () => {
17 const adversarial = 'a'.repeat(80) + '!';
18 const start = Date.now();
19 expect(validateEmail(adversarial)).toBe(false);
20 const elapsed = Date.now() - start;
21 // RE2 is linear; this should finish in well under 50 ms on any host.
22 expect(elapsed).toBeLessThan(50);
23 });
24
25 it('rejects oversized input before running the regex', () => {
26 const oversized = 'a'.repeat(500);
27 const start = Date.now();
28 expect(validateEmail(oversized)).toBe(false);
29 expect(Date.now() - start).toBeLessThan(5);
30 });
31});A code review finds 14 regex literals scattered across handlers. The team lead suggests banning bare RegExp and /.../ on user-input files in lint, forcing them through safeRegex (RE2). Is that a good control?
07 //Real-World Case Studies
ReDoS has a long and dramatic disclosure history. The pattern is monotonous: a critical service runs a regex on user input, an adversarial payload pins the CPU, the service goes offline. The interesting part is how often the bug appears in infrastructure software where one incident takes a meaningful fraction of the public internet with it.
- Cloudflare global outage (July 2, 2019), a single WAF rule update introduced the regex
(?:(?:\"|\'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|\{\}|\|\||\+)*.*(?:.*=.*)))with a catastrophic nested-quantifier shape. The rule was deployed globally and pinned 100% of CPU on Cloudflare's edge workers for 27 minutes, causing a global 502 storm. Postmortem: Cloudflare blog. Fix: switched the WAF engine to compile through a non-backtracking engine and added staged rollout with canary monitoring. - Stack Overflow outage (July 20, 2016), a Markdown post containing a long whitespace string hit a backtracking regex in the home-page question renderer. The regex was used to trim leading and trailing whitespace; a post with several hundred space characters caused a 30-minute global outage. Postmortem: Stack Status. Fix: replaced the regex with a simple character-class trim and added length caps.
- Express path-to-regexp CVE-2024-45296, the path-to-regexp library (default router in Express, Koa, Next.js Pages router, Vercel edge) compiled certain parameter patterns to exponentially-backtracking regex. A crafted route with a parameter like
/:foo(((a+)+)+)bcompiled in seconds and matched in minutes. Patched in 6.3.0 / 8.0.0. Every JavaScript router on npm picked up the patch within a week. - marked CVE-2022-21680 / CVE-2022-21681, the popular Markdown library shipped two ReDoS bugs in 4.0.10. The vulnerable patterns lived in the block-grammar lexer for fenced code blocks and inline tables; an attacker submitting a long crafted Markdown post pinned the renderer. Patched in 4.0.10 and 4.0.12.
- npm minimatch / micromatch (multiple), glob matching is implemented by translating glob syntax to regex. Several CVEs (CVE-2022-3517, CVE-2024-21538) shipped where the translated regex was exponential on certain crafted glob patterns. Because glob is used everywhere (npm itself, lerna, every build tool), the blast radius of each CVE touched the entire JavaScript ecosystem.
- moment.js CVE-2017-18214, the date-parsing logic used a regex that was polynomial on certain crafted date strings. moment was already deprecated by 2024, but the regex sat in production for years, illustrating how long unmaintained patterns continue to ship.
- Prometheus CVE-2019-3826, Prometheus label selectors accepted user-supplied regex (
=~operator). A crafted selector likelabel=~"(a+)+"in a recording rule pinned the rule evaluator. Fixed by compiling user regex through RE2 and rejecting non-linear patterns. - nf-core / nextflow workflow regex DoS (2023), scientific compute pipelines that accept user-submitted glob and regex filters were repeatedly DoSed by crafted inputs. The fix in each workflow was to compile filters through RE2/J before evaluating against the file index.
Across the case studies, what is the recurring root cause?
08 //Beyond the Code: Process Isolation, Length Caps, and Runtime Posture
The pattern-level fix removes the immediate sink. The runtime-level fix limits the blast radius when a future regression slips through. Process and thread isolation, hard wall-clock timeouts on regex workers, body-size caps in the reverse proxy, and per-endpoint CPU budgets in the runtime turn a ReDoS bug from a service-wide outage into a single failed request. Treat runtime posture as part of the defense, not a separate ops concern.
Runtime Hardening Recommendations
| Control | What it does | Why it limits ReDoS impact |
|---|---|---|
| Per-request body-size limit at the proxy | nginx client_max_body_size, Envoy max_request_bytes, CloudFront body cap | Caps the attacker's payload before any regex runs; reduces the polynomial constant and outright defeats some patterns. |
| Per-endpoint input length cap in middleware | Express body-parser limit option, FastAPI Pydantic max_length, Spring @Size constraint | Closer to the regex than the proxy; rejects oversized fields before the validator even fires. |
| Worker-thread or subprocess sandbox | worker_threads in Node, multiprocessing in Python, Goroutine + context.WithTimeout, separate JVM thread pool | Lets the runtime actually enforce a wall-clock timeout the OS can kill, which user-land setTimeout cannot. |
| Concurrency cap per endpoint | Tokio semaphores, k8s HorizontalPodAutoscaler with CPU-based scaling, async-aware rate limiter | Prevents a single endpoint from monopolising the fleet during an attack; healthchecks can recover. |
| Per-worker request budget and restart | PM2 max_memory_restart, gunicorn max_requests, uvicorn worker recycling | Recovers a stuck worker on its own without operator intervention; turns a permanent stall into a transient blip. |
| CPU-time observability | Per-request CPU sampling, eBPF on the regex syscall path, Sentry performance traces with custom spans | Surfaces the bug as a latency anomaly during canary deploys, before adversaries find it. |
1// server.js, the runtime-level defenses that sit alongside RE2 in code.
2
3const express = require('express');
4const app = express();
5
6// 1) Hard body-size limit. Body-parser respects this BEFORE any validator runs.
7app.use(express.json({ limit: '32kb' }));
8
9// 2) Per-endpoint length caps inside the controller, before regex.
10app.post('/signup', (req, res) => {
11 const email = String(req.body.email ?? '');
12 if (email.length > 254) return res.status(400).json({ error: 'too long' });
13 // ... then validateEmail(email) which uses RE2.
14});
15
16// 3) Concurrency cap on expensive endpoints (a custom middleware or
17// express-rate-limit at the gateway).
18// Limits the number of simultaneous validator calls so a partial
19// regression cannot stall every worker.
20
21// 4) Worker restart policy. In PM2 or systemd, set max_memory_restart and
22// a sensible max_old_space_size so a stuck worker can be recycled.
23//
24// 5) Observability. Pino with auto-redact and a sampled CPU profiler in
25// canary; surface p99.9 latency anomalies in pre-prod before they reach
26// production traffic.
27
28app.listen(3000);1// lib/regex.ts, the one and only allowed regex entry point.
2//
3// Everything goes through this module. Direct RegExp / /.../ usage is banned
4// by lint on any file under src/handlers, src/middleware, or src/validators.
5// The module guarantees:
6// * RE2 (linear time, no backtracking, no ReDoS)
7// * Length caps applied before the regex runs
8// * Compile-time rejection of patterns RE2 refuses (backreferences, lookaround)
9// * Optional sandbox path for the rare case where backtracking is required
10
11import RE2 from 're2';
12
13const MAX_INPUT = 64 * 1024;
14
15interface SafeRegex {
16 test: (input: string) => boolean;
17 exec: (input: string) => RegExpExecArray | null;
18}
19
20export function compile(source: string, flags = ''): SafeRegex {
21 // RE2 throws at construction if the pattern cannot run in linear time.
22 // That failure is the correct outcome: it surfaces in CI or at startup,
23 // never on the request path under adversarial input.
24 const re = new RE2(source, flags);
25 return {
26 test(input: string) {
27 if (typeof input !== 'string') return false;
28 if (input.length > MAX_INPUT) return false;
29 return re.test(input);
30 },
31 exec(input: string) {
32 if (typeof input !== 'string') return null;
33 if (input.length > MAX_INPUT) return null;
34 return re.exec(input) as RegExpExecArray | null;
35 },
36 };
37}
38
39// Pre-compile every pattern at module load. If any pattern is unsafe, the
40// service fails to start.
41export const EMAIL = compile('^[^\\s@]+@[^\\s@]+\\.[^\\s@]+$');
42export const SLUG = compile('^[a-z0-9-]{1,64}$');
43export const UUID = compile('^[0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12}$', 'i');
44
45// Use it everywhere a validator runs:
46// import { EMAIL } from '../lib/regex';
47// if (!EMAIL.test(req.body.email)) return res.status(400).end();09 //Conclusion
ReDoS is a textbook case of trust transferred from the regex author to the regex engine. The application is correct, the engine is correct, the operating system is correct. The vulnerability lives in the moment a backtracking engine is handed a pattern with ambiguous parses and an input that maximises them. Fix it the same way every adjacent bug class is fixed: a single helper backed by a linear-time engine, applied at every user-input regex, paired with length caps, static analysis in CI, and a runtime posture that contains the worst case.
new RegExp(userInput) outside a vetted user-regex helper · Pin path-to-regexp, marked, minimatch, and other regex-heavy libraries to patched versions · Run safe-regex, recheck, or CodeQL's ReDoS queries in CI on every change · Run risky regex inside a worker-thread or subprocess with a wall-clock timeout the OS can enforce · Pair with body-size limits at the proxy, concurrency caps per endpoint, and worker restart policies.When you see a new regex in a diff, the first question is not "does it match the right strings", it is "what is the worst-case runtime on adversarial input, and what engine will run it?" If the answer involves a backtracking engine on user-controlled bytes without a linear-time wrapper, every byte the user can submit is potentially a CPU-exhaustion primitive. The fix is one helper away. Pair this module with the Command Injection, SQL Injection, and Rate Limiting guides for the adjacent classes where the bug is "an input parser hands the attacker more work than they paid for."