How One Regular Expression Can Freeze Your Server

How a backtracking engine actually searches

Most regex engines you use daily — PCRE, Java's java.util.regex, Python's re, .NET, and JavaScript's RegExp — are backtracking engines. They try one possible match, and when it fails they rewind to the most recent decision point and try the next alternative, exhaustively, until something matches or every possibility is exhausted.

For most patterns that is fast and gives you powerful features: backreferences, lookahead, lazy quantifiers. The cost appears when a pattern is ambiguous — when there is more than one way for the engine to divide the same input between parts of the pattern.

Take the canonical example:

/^(a+)+$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaX")

The inner a+ can consume one or more as. The outer + can repeat that group one or more times. So for 26 as the engine must consider every way of partitioning them into groups: [26], [25,1], [1,25], [24,2], [13,13], and so on. That is 2²⁵ partitions — about 33 million. Each one is tried, each one reaches the final X, and each one fails the $ anchor.

Add a single character to the input and the work doubles. At 30 as it is roughly a second. At 40 it is around 15 minutes. At 50, over a week. The pattern itself looks entirely harmless.

The three shapes to recognise

1. Nested quantifiers

A quantified group that itself contains a quantifier over overlapping characters:

(a+)+      (a*)*      (\d+)*     ([a-z]+)*    (\s+)+

These are exponential. Any time you see a + or * immediately outside a group whose contents can also repeat, treat it as a defect.

2. Ambiguous alternation under a quantifier

(a|a)*     (a|ab)*     (\w|\d)*    (.|\s)*

Here two branches can match the same input, so the engine has a genuine choice at every character — and must eventually try all combinations. (\w|\d)* is a common real-world instance, because \d is entirely contained within \w; every digit can be matched two ways.

3. Quantified overlapping sequences

\s*\s*     .*a.*      (\w+\s?)+$

That last one appears in countless "validate a full name" and "validate a sentence" patterns. The optional \s? inside a repeated group over \w+ creates exactly the ambiguity that kills. It is polynomial rather than exponential, which sounds reassuring until you realise polynomial with a large exponent on a 5,000-character input is still a multi-second stall per request.

This is a real CVE class, not a curiosity

ReDoS accounts for a steady stream of advisories in npm, PyPI and Maven packages, and the vulnerable patterns are almost always doing something unremarkable: validating an email address, parsing a User-Agent string, trimming whitespace, matching a semver range, parsing a Markdown link.

Email validation is the archetype. Patterns of this general shape circulate widely:

^([a-zA-Z0-9_\.\-])+\@(([a-zA-Z0-9\-])+\.)+([a-zA-Z0-9]{2,4})+$

There are three nested-quantifier defects in there. Given a local part of 40 characters followed by a character that cannot appear, it will not finish. And because email validation runs on the signup form, the attack surface is a public unauthenticated endpoint.

The deeper point is that a regex is code with a worst-case complexity, and unlike your other code nobody reviews it for that. It arrives by copy-paste from an answer site, passes every test you write for it, and its complexity characteristics are never examined.

Fixing the pattern

Remove the ambiguity

Most vulnerable patterns have an unambiguous equivalent that matches exactly the same language. (a+)+ accepts precisely the strings a+ accepts, so:

(a+)+      →  a+
(\w|\d)*   →  \w*
(\w+\s?)+  →  [\w\s]+        (if the exact grouping does not matter)
([a-z]+)*  →  [a-z]*

Ask "is there more than one way for the engine to match this input?" If yes, restructure until there is exactly one. For the name-validation case, make the separator mandatory between tokens rather than optional inside the repeat:

^\w+(\s\w+)*$        # unambiguous: each space is followed by a word
^(\w+\s?)+$          # ambiguous: trailing space optional at every step

Use atomic groups or possessive quantifiers

Where the language genuinely needs the structure, you can forbid backtracking into a group. An atomic group (?>...) commits to its first match; a possessive quantifier ++ does the same inline:

(?>a+)+$      # atomic - no backtracking into the group
a++$          # possessive - same effect

Support is uneven, and this is important to check before relying on it: available in PCRE, Java and Ruby; not available in JavaScript or Python's standard re module. Python users can install the third-party regex package, which supports both.

Switch to a linear-time engine

Some engines are immune by construction. RE2 (Google), Go's regexp package, and the Rust regex crate compile to automata and guarantee matching in time linear in the input length. There is no backtracking, so there is nothing to explode.

The trade-off is real: they cannot support backreferences or lookaround, because those features are what make linear-time matching impossible. If your pattern needs (\w)\1 or (?=...), you cannot use them. If it does not — and most validation patterns do not — a linear-time engine removes this entire class of bug permanently.

Impose a timeout

A timeout is a safety net rather than a fix, and availability varies sharply:

The JavaScript row deserves emphasis. A regex match in Node is synchronous and uninterruptible, so a single malicious request does not slow the process down — it stops it. No other request is served, health checks fail, and the orchestrator restarts a container that was never actually unhealthy. If you must run a risky pattern in Node, run it in a worker thread you can terminate.

Cap the input length

The mitigation that works everywhere, requires no library change, and takes one line:

if (input.length > 256) return false;   // before any matching
return EMAIL_RE.test(input);

Because the blow-up is a function of input length, a hard cap converts an unbounded worst case into a bounded one. No legitimate email address is 4,000 characters. No real postcode is 900. Validate length first, always — it is free, and it is the only defence that applies before the dangerous code runs.

What to look for in review

1. Any quantifier immediately outside a group containing a quantifier.
2. Alternation branches that can match the same character — especially \w with \d, or . with \s.
3. Optional separators inside repeated groups: (x+\s?)+.
4. Patterns applied to unbounded user input with no length check upstream.
5. Unanchored patterns on long input — without ^ the engine retries from every position, multiplying any per-position cost.
6. Patterns pasted in from anywhere, on principle. Validate the complexity, not just the behaviour.

Treat regular expressions as code with a worst case

The gap that makes ReDoS persistent is that regex correctness and regex complexity are entirely separate properties, and we only ever test the first. Your pattern matches valid input and rejects invalid input; both tests pass; the complexity was never on the agenda.

So add one test alongside the others: a long repeated run of the character your pattern loops on, followed by one character that guarantees failure. If that test does not return promptly, the pattern is a denial-of-service vector regardless of how correct it is.