redos

ReDoS Hunting Playbook

Regular Expression Denial of Service exploits O(2^n) or O(n^2) matching time in backtracking engines. One crafted string can peg a CPU thread for seconds or minutes against an otherwise tiny pattern.

1. Identify Backtracking Engines in Scope

Not all regex engines backtrack:

If the target uses RE2 or Go's regexp, skip this playbook — no backtracking, no ReDoS.

2. Source Patterns — Where Tainted Input Reaches Regex

# Python
grep -rn 're\.match\|re\.search\|re\.fullmatch\|re\.compile\|regex\.match' /workspace/src \
  | grep -v '#' | grep -v 'test_' | grep -v '_test\.py'

# Node.js / TypeScript
grep -rn 'new RegExp\|\.match(\|\.search(\|\.test(' /workspace/src \
  --include='*.js' --include='*.ts' | grep -v 'node_modules'

# Java
grep -rn 'Pattern\.compile\|\.matches(\|\.find(\|String\.matches' /workspace/src \
  --include='*.java'

# PHP
grep -rn 'preg_match\|preg_replace\|preg_split' /workspace/src --include='*.php'

# Ruby
grep -rn 'match\|=~\|Regexp\.new\|\.scan(' /workspace/src --include='*.rb' \
  | grep -v '#'

# Semgrep for tainted-input-to-regex-sink
semgrep --config p/regex /workspace/src --sarif -o /workspace/sem-redos.sarif 2>/dev/null

For each hit, determine whether the regex pattern is:

• Static (hardcoded string literal) → scan the pattern itself
• Dynamic (constructed from user input) → separate vuln class (regex injection); flag it and continue

3. Catastrophic Pattern Recognition