/redos

name: redos
description: "Detect Regular Expression Denial of Service (ReDoS) where crafted input causes catastrophic backtracking in regex patterns applied to user-controlled strings."
metadata:
  filePattern:
    - "**/*.js"
    - "**/*.ts"
    - "**/*.py"
    - "**/*.rb"
    - "**/*.php"
    - "**/*.java"
  bashPattern:
    - "grep.*(RegExp|regex|pattern|match)"
    - "semgrep.*redos"
  priority: 70

ReDoS Detection

When to Use

Audit input validation libraries, URL/email/date parsers, sanitization utilities, template engines, and any package that applies regular expressions to user-controlled strings.

Critical Rule

**MUST measure actual backtracking growth rate.** Do not report based on pattern structure alone. The validator.js lesson: assumed ReDoS from pattern complexity but could not confirm exponential growth. Always TIME IT.

Vulnerable Regex Patterns

Nested Quantifiers (Most Common)

(a+)+$          # Nested plus -- classic ReDoS
(a*)*$          # Nested star
(a+)*$          # Star of plus
(a*)+$          # Plus of star
(a{1,}){1,}$   # Nested bounded quantifiers

Overlapping Alternation

(a|a)+$         # Identical alternatives
(a|ab)+$        # Prefix overlap
(a|b|ab)+$      # Partial overlap
(\w|\d)+$       # \d is subset of \w -- overlap

Quantified Groups with Optional Elements

(a+b?)+$        # Optional between repeated groups
(\s*,\s*)+$     # Common in CSV/list parsing
([^"]*"[^"]*")*[^"]*$  # Quote matching

Dangerous Real-World Patterns

^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*$    # Email local part
^((https?|ftp):\/\/)?([\w.-]+)\.([a-z.]{2,6}).*$  # URL validation
^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$              # IP (safe but often combined)

Evil String Construction

| Pattern | Evil String | Growth | |---------|-------------|--------| | `(a+)+$` | `"a" * N + "!"` | O(2^N) | | `(a+b?)+$` | `"a" * N + "!"` | O(2^N) | | `(a\|aa)+$` | `"a" * N + "!"` | O(2^N) | | `([a-zA-Z]+)*$` | `"a" * N + "1"` | O(2^N) | | `(\s+$)` | `" " * N + "x"` | O(N^2) quadratic | | `(.*a){10}$` | `"a" * N + "!"` | O(N^10) polynomial |

**Key insight:** The evil string is N copies of a character the pattern CAN match, followed by one character it CANNOT. This forces the engine to try every possible split of the N characters across the quantifiers.

Process

Step 1: Find Regex Usage

# JavaScript/TypeScript
grep -rn "new RegExp\|RegExp(" . --include="*.js" --include="*.ts"
grep -rn "\.match(\|\.test(\|\.replace(\|\.search(\|\.split(" . --include="*.js" --include="*.ts"
grep -rn "/[^/]*[+*][^/]*[+*][^/]*/" . --include="*.js" --include="*.ts"

# Python
grep -rn "re\.compile\|re\.match\|re\.search\|re\.findall\|re\.sub" . --include="*.py"
grep -rn "re\.DOTALL\|re\.MULTILINE\|re\.VERBOSE" . --include="*.py"

# Ruby
grep -rn "Regexp\.new\|=~\|\.match\|\.scan\|\.gsub" . --include="*.rb"

# PHP
grep -rn "preg_match\|preg_replace\|preg_split" . --include="*.php"

# Java
grep -rn "Pattern\.compile\|\.matches(\|\.replaceAll(" . --include="*.java"

Step 2: Identify Potentially Vulnerable Patterns

Look for these red flags: 1. **Nested quantifiers:** `(X+)+`, `(X*)*`, `(X+)*`, `(X*)+` 2. **Overlapping alternation:** `(a|a)+`, `(a|ab)+` 3. **Quantified group with internal repetition:** `(\s*,\s*)+` 4. **Unbounded repetition with anchor failure:** Pattern ends with `$` and input doesn't match 5. **User-controlled regex:** `new RegExp(userInput)` -- always exploitable

Step 3: Mandatory Timing Measurement

// Node.js timing test -- REQUIRED before reporting
const regex = /VULNERABLE_PATTERN/;

console.log('Length | Time (ms) | Ratio');
let prevTime = 0;
for (let len = 15; len <= 35; len++) {
  const evil = 'a'.repeat(len) + '!';
  const start = performance.now();
  regex.test(evil);
  const elapsed = performance.now() - start;
  const ratio = prevTime > 0 ? (elapsed / prevTime).toFixed(1) : '-';
  console.log(`${String(len).padStart(6)} | ${elapsed.toFixed(2).padStart(9)} | ${ratio}`);
  prevTime = elapsed;
}

**Interpretation:**

• Ratio ~2.0 per character = exponential (O(2^N)) = CONFIRMED ReDoS
• Ratio ~1.0 but time grows = likely polynomial = needs larger input test
• Ratio ~1.0 and time flat = linear = NOT ReDoS

Step 4: Classify Severity

| Growth Rate | Ratio Pattern | Input for 1s Hang | Severity | |-------------|---------------|-------------------|----------| | O(2^N) exponential | ~2x per char | 25-30 chars | HIGH 7.5 | | O(N^3+) polynomial | grows with input | 10K-100K chars | MEDIUM 5.3-6.5 | | O(N^2) quadratic | grows slowly | 100K+ chars | LOW-MEDIUM | | O(N) linear | constant ratio | never | NOT ReDoS |

Step 5: Verify User Input Reaches Regex

The regex MUST be applied to user-controlled input. Check the full call chain: 1. Where does input enter? (HTTP param, form field, file content) 2. Is input truncated before regex? (length limit < 100 chars = likely safe) 3. Is there a regex timeout? (some libraries implement circuit breakers) 4. Is the regex applied in a worker/child process? (reduces impact to DoS of worker only)

Language-Specific Notes

JavaScript (V8 Engine)

• **No built-in regex timeout.** Catastrophic backtracking freezes the entire event loop.
• Single-threaded: one ReDoS hangs ALL request processing.
• `String.prototype.matchAll()` is lazy but still backtracks.
• V8 does NOT use RE2 for regex. All JS regex uses backtracking.

Python

• **GIL blocks all threads.** ReDoS in one thread freezes the entire process.
• `re` module uses backtracking. No built-in timeout.
• `re2` package (Google RE2 bindings) is safe but rarely used.
• Python 3.11+ has some regex optimizations but is still vulnerable.

Go

• **Uses RE2 engine.** Guarantees linear-time matching. NOT vulnerable to ReDoS.
• Exception: CGo bindings to PCRE (rare) ARE vulnerable.
• Skip Go targets unless they use PCRE bindings.

Ruby

• Uses Oniguruma engine (backtracking). Vulnerable to ReDoS.