redos

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.
• Ruby 3.2+ added Regexp.timeout= global setting -- check if configured.
• Regexp.timeout defaults to nil (no timeout) unless explicitly set.

PHP

• Uses PCRE (backtracking). Vulnerable to ReDoS.
• pcre.backtrack_limit defaults to 1,000,000 -- provides some protection.
• Check ini_get('pcre.backtrack_limit') -- if lowered, may limit impact.

Java

• Uses backtracking engine. Vulnerable to ReDoS.
• No built-in timeout in Pattern.compile().
• Can be mitigated with Thread.interrupt() but rarely done.

CVSS Guidance

• Exponential backtracking, user input, event loop blocking: HIGH 7.5
• Exponential backtracking, authenticated only: MEDIUM 6.5
• Quadratic on user input requiring large payload (>10KB): MEDIUM 5.3
• Regex on bounded input (< 100 chars): usually not exploitable
• Regex with timeout/circuit breaker configured: reduced severity
• User-controlled regex pattern (new RegExp(input)): HIGH 7.5 (always exploitable)

References

• [Sinks](references/sinks.md) -- Regex-heavy libraries and known vulnerable patterns
• [False Positive Indicators](references/false-positive-indicators.md)
• [PoC Skeleton](references/poc-skeleton.md)