Skip to content

CWE-1333: Inefficient Regular Expression Complexity

Overview

A regular expression can be logically correct - it matches exactly the strings it's supposed to - and still be exploitable if its worst-case matching time is exponential (or high-degree polynomial) in the length of the input. An attacker who controls the input sends a string engineered to trigger the pattern's worst case, causing catastrophic backtracking that pins a CPU core for seconds or longer. This is commonly called ReDoS (Regular Expression Denial of Service).

Relationship to Other CWEs

The entries below set out the scope of each:

  • CWE-1333 (this page) - a performance bug: the pattern matches the right set of strings, just too slowly on adversarial input.
  • CWE-407 (Inefficient Algorithmic Complexity) - CWE-1333 is ChildOf this, the regex-specific case of an algorithm whose worst-case cost is far higher than its typical-case cost.
  • CWE-185 (Incorrect Regular Expression) - easy to conflate, because both present as "the regex is bad". CWE-185 is a matching-logic bug: the pattern matches the wrong set of strings.

A pattern can have either problem independently, or both at once.

Risk

Medium-High: A single crafted request can consume disproportionate CPU time on a backtracking regex engine, degrading the application for every other user; a sustained rate of them is a denial-of-service lever. The cost is per-request and, for an exponential-time pattern, multiplies with every few extra characters of attacker-controlled input, so the payload stays small and cheap to send while the cost to the server does not.

Remediation Steps

Core Principle: Eliminate the backtracking blowup at the pattern level (the durable fix); use timeouts and input-length limits as defense in depth, not as the primary control.

Trace the Data Path

  • Source: where the string being matched comes from - request parameters, headers, uploaded file content, any attacker-influenced value.
  • Sink: the regex engine call itself (match, test, search) and how long it's allowed to run.
  • Missing controls: look for nested or overlapping quantifiers applied to attacker-controlled input with no length limit and no execution timeout.

Remove Catastrophic Backtracking from the Pattern (Primary Defense)

  • Avoid nested quantifiers on the same or overlapping character class: (a+)+, (a*)*, (a+)* all have exponential worst-case behavior on a backtracking engine.
  • Avoid overlapping alternatives that can match the same input in multiple ways: (a|a)*, (a|ab)* - ambiguity between alternatives is what drives backtracking.
  • Rewrite ambiguous repetition as an unambiguous single quantifier wherever the intent allows it (a+ instead of (a+)+).
  • Where the regex engine supports it, use possessive quantifiers or atomic groups to prevent backtracking into a subexpression once it has matched.
  • Prefer a non-backtracking (linear-time) regex engine for patterns built from or applied to untrusted input, where available for the language/runtime. Go's regexp and Rust's regex are linear by construction; .NET 7+ offers RegexOptions.NonBacktracking as a per-pattern switch, which returned the correct answer in 37ms against the input measured under A quantifier inside a quantifier below, where the default engine took 102 seconds. It is the strongest fix available without rewriting the pattern, though it does not support backreferences or lookaround.

Limit Input Length and Execution Time (Defense in Depth)

  • Reject input above a reasonable maximum length before it reaches the regex engine - most exponential-time patterns are only a practical problem once the input crosses a length threshold.
  • Set an execution timeout on the regex call and treat a timeout as a rejection, not a silent pass-through - where your runtime has one, which several do not. .NET takes a TimeSpan on the Regex constructor and raises RegexMatchTimeoutException (measured on .NET 10: a 100ms timeout on ^(a+)+$ threw at 117ms against input the same engine otherwise spent 102 seconds on). PHP bounds it by steps rather than time, through pcre.backtrack_limit. Java's java.util.regex, Python's built-in re and JavaScript's RegExp have no timeout at all: in those the only way to bound a match is to run it somewhere you can kill - a worker thread, a subprocess - or to use a library that offers one, such as Python's third-party regex module.

Test with Adversarial Input

  • Construct a worst-case string for the pattern under review (e.g., a long run of a character that satisfies an inner quantifier, followed by one character that fails the overall match) and measure matching time as input length grows.
  • Confirm matching time grows linearly with input length after the fix, not exponentially.
  • Re-scan with the security scanner or a regex-complexity linter to confirm the finding is resolved.

Common Vulnerable Patterns

All three depend on a backtracking engine, which is what most languages ship by default. Each is fast on inputs that match and slow only on ones that do not, so the cost appears exactly where an attacker puts it.

A quantifier inside a quantifier

// VULNERABLE - nested quantifier: exponential worst-case time
pattern = "^(a+)+$"
// Input "aaaaaaaaaaaaaaaaaaaaaaaa!" (24 a's + a non-matching character)
// forces the engine to try every way of partitioning the a's between
// the inner and outer "+" before concluding there's no match

Why this is vulnerable: the two quantifiers can divide the same run of characters between them in many ways, and a backtracking engine has to try all of them before it can report that no match exists. The number of ways grows exponentially with the length of the run, so the input that triggers it stays short while the cost does not.

The growth rate is what decides whether a length cap helps. Measured against this pattern, each extra pair of as multiplies the time by about four: Python 3.13 takes 0.04s at 20 characters, 0.66s at 24 and 2.9s at 26, and .NET 10 takes 102 seconds at 30. So the 24 in the comment above is under a second, a length any validator would wave through; six more characters, on .NET, is a pinned core for over a minute and a half. Engines differ by a large constant factor and the exponent is the same in all of them, which is why "cap the length" buys a few characters rather than a fix.

The trailing character is the part that matters. On a matching input the engine stops at the first success, so the pattern is fast for every legitimate value and every test written from one. The blow-up needs a long matching prefix followed by something that forces failure, which is why this is invisible until someone constructs it deliberately.

Alternatives that can match the same text

// VULNERABLE - overlapping alternation inside a quantifier
pattern = "^([a-zA-Z]+|[a-zA-Z0-9]+)*$"
// Both alternatives can match the same run of letters, so the engine
// backtracks through every possible split between them

Why this is vulnerable: the two branches are not disjoint - a run of letters satisfies either - so for each repetition of the outer * the engine has two viable choices that lead to the same position, and on failure it must explore both. The ambiguity is the defect, and it is present even though neither branch is individually wrong.

This is the form least likely to be recognised, because the pattern reads as deliberate: someone wrote the second alternative to allow digits and left the first in place. It is also the most expensive of the three - measured on Python 3.13, it takes 0.45s at 14 characters, 4.1s at 16 and 39s at 18, so each extra pair of characters multiplies the time by about nine where ^(a+)+$ multiplies it by four. The test to apply is whether any input can be consumed by more than one branch. Where it can, the alternation should be rewritten so the branches cannot overlap, which here means the single class and dropping the alternation altogether: ^[a-zA-Z0-9]+$. This is not quite the same language - ([a-zA-Z]+|[a-zA-Z0-9]+)* can repeat zero times and so matches the empty string, where [a-zA-Z0-9]+ requires at least one character. That is almost always the behaviour you wanted, but decide it rather than inherit it.

The same shape inside an ordinary-looking pattern

// VULNERABLE - nested quantifiers hidden inside a "simple-looking" email pattern
pattern = "^([a-zA-Z0-9._%+-]+)*@([a-zA-Z0-9.-]+)*$"

Why this is vulnerable: this is (x+)* twice over, wearing a familiar name. A character class followed by +, wrapped in a group followed by *, is the same construction as the first pattern on this page, and the fact that it is validating an email address does nothing to change the engine's behaviour on it.

What matters here is where these patterns come from. Patterns for emails, URLs, dates and version numbers are copied between projects far more often than they are written, and the copy carries the complexity with it - so a finding here is worth treating as a question about every other pattern that arrived the same way, not just the one reported.

Removing the outer * from each group is the fix, but it is not a no-op and the page it was copied from probably said it was. (x+)* can repeat zero times, so the original accepts @, a@ and @b - an address with no local part, no domain, or neither - and [a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+ rejects all three (measured on Python 3.13). The pattern was carrying a CWE-185 matching bug alongside the complexity one, which is common in exactly these copied patterns: the redundant quantifier that makes it slow is also what makes it accept the empty string. Check what the reduction stops accepting before shipping it, because occasionally something downstream depended on the loose behaviour.

Secure Patterns

// SECURE - single quantifier, linear-time
pattern = "^a+$"

// SECURE - length check before an expensive pattern, plus a simplified pattern
if length(input) > 254:
    reject(input)
pattern = "^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$"   // no nested quantifiers

// SECURE - execution timeout as defense in depth, on top of a linear pattern
result = matchWithTimeout(pattern, input, 100 /* ms */)
if result is TIMEOUT:
    reject(input)

Why this works: Removing the nested and overlapping quantifiers from these patterns eliminates the ambiguity that forces the backtracking engine to explore an exponential number of partitions of the input, so matching time grows linearly with input length. The length check and the timeout are there for patterns that can't be fully rewritten; neither substitutes for fixing the pattern.

Common Pitfalls

  • Adding a timeout without fixing the pattern: a 100ms timeout still means every attack request costs the server up to 100ms of pinned CPU - at any meaningful request rate, that's still a usable denial-of-service lever, just a bounded one instead of an unbounded one.
  • Simplifying the visible top-level pattern but leaving a nested quantifier inside a sub-pattern: a pattern built from smaller named sub-patterns (common in shared regex libraries) can still be exponential if any single sub-pattern has nested/overlapping quantifiers, even if the assembled pattern looks simple at the top level.
  • Testing only with normal-length input: a pattern's backtracking blowup is often invisible with inputs under a few dozen characters, so a test suite built from realistic values will not find it.
  • Assuming input length limits alone are sufficient: a length cap reduces the worst case but doesn't eliminate it - a cap of a few hundred characters can still be enough to hang an exponential-time pattern; the pattern itself still needs fixing.

Additional Resources