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"