Skip to main content

SEC014-redos-regex — ReDoS-vulnerable regular expression

PropertyValue
DimensionSecurity
Default severityHigh
CWECWE-1333
LanguagesRust, Python, JavaScript, TypeScript

What it detects​

Flags regular expression patterns that contain structures known to cause catastrophic backtracking in backtracking-based regex engines:

  1. Nested repetition — a quantifier (+, *, ?, {n,m}) whose body itself contains a quantifier. The canonical example is (a+)+: on input like "aaaaab", a backtracking engine explores an exponential number of paths. More subtle variants include (.*)*, (\w+)+end, and ((a|b)+)+.

  2. Alternation with duplicate branches — an Alternation node where two or more branches stringify identically (e.g. (a|a)+, (foo|foo)). Combined with an outer repetition this produces polynomial or exponential work.

The check uses regex_syntax to parse the pattern and walk the AST. Patterns that fail to parse are silently skipped — they cannot be executed by a regex engine and flagging them would be a false positive.

Negative-case guards​

The rule does not fire when:

  • The pattern fails to parse (e.g. unbalanced ().
  • The repetition is over a character class ([a-z]+) with no nested quantifier.
  • The repetition is bounded (\d{1,5}) with no nested quantifier.
  • All alternation branches are distinct (e.g. (foo|bar)+).

Examples — flagged​

Python:

import re

re.compile(r"(a+)+")      # FLAGGED — nested repetition
re.compile(r"(.*)*")      # FLAGGED — nested repetition
re.match(r"(\w+)+end", s) # FLAGGED — nested repetition

Rust:

use regex::Regex;

Regex::new("(a+)+").unwrap();   // FLAGGED — nested repetition
Regex::new("(.*)*").unwrap();   // FLAGGED — nested repetition

JavaScript/TypeScript:

const r1 = /(a+)+/;              // FLAGGED — nested repetition
const r2 = new RegExp("(.*)*");  // FLAGGED — nested repetition

Examples — not flagged​

Python:

import re

re.compile(r"[a-z]+")    # OK — no nested quantifiers
re.compile(r"\d{1,5}")   # OK — bounded, no nesting
re.compile(r"^abc$")     # OK — no quantifiers
re.compile(r"(foo|bar)") # OK — distinct alternation branches

Rust:

use regex::Regex;

Regex::new("[a-z]+").unwrap();  // OK
Regex::new(r"\d{1,5}").unwrap(); // OK

Fix guidance​

  1. Rewrite to avoid nested quantifiers. Instead of (a+)+, use a+ or anchor the pattern with ^…$ so the engine cannot retry partial matches.
  2. Use atomic groups or possessive quantifiers if your engine supports them (Python's re2 / regex crate with the (?atomic:…) extension, PCRE (?>…) or ++ / *+).
  3. Limit input length at the call site before passing user-controlled data to the regex engine. Short inputs bound the worst case.
  4. Switch to a linear-time engine. The Rust regex crate and Google's RE2 guarantee O(n) matching and reject patterns that could catastrophically backtrack.

References​

Implementation​