redoslisted

# 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?)