prevent-redos

name	prevent-redos
description	Use when writing or reviewing regular expressions that process user-controlled input — especially patterns with nested quantifiers, alternation with overlapping cases, or patterns applied to long strings.
source	OWASP Regular Expression Denial of Service (ReDoS) Defense Cheat Sheet (owasp.org/www-project-cheat-sheets); CWE-1333; OWASP Top 10 2021 A06
tags	["security","owasp","redos","regex","denial-of-service","input-validation","developer"]

Prevent ReDoS

Eliminate catastrophic regex backtracking by using atomic groups, possessive quantifiers, or linear-time regex engines — preventing single-user input from consuming CPU for minutes or hours.

Why This Is Best Practice

Adopted by: CWE-1333 (Inefficient Regular Expression Complexity) is a named weakness tracked by NVD with hundreds of CVEs. Node.js, Cloudflare, and Stack Overflow have all experienced ReDoS outages. OWASP Top 10 2021 A06 (Vulnerable and Outdated Components) includes ReDoS in third-party regex libraries. Google's re2 library (used in Go's stdlib regex) is designed to guarantee linear-time matching. GitHub's CodeQL, Semgrep, and Snyk all include ReDoS detection rules. Impact: Stack Overflow's 2016 outage was caused by a single malicious regex ^\s*(\w+\s*)+$ consuming 100% CPU on a crafted input string — taking down the site for 34 minutes. Cloudflare's 2019 global outage lasted 27 minutes due to a ReDoS in a WAF regex. Node.js has had multiple ReDoS CVEs in the validator, marked, and moment packages. A single well-crafted string can freeze a single-threaded server. Why best: Input length limits alone are insufficient — catastrophic backtracking is exponential, so even 30-character inputs can cause seconds-long hangs. Rewriting to atomic/possessive patterns or using a linear-time engine eliminates the root cause.

Sources: OWASP ReDoS Cheat Sheet; Stack Overflow outage post-mortem (2016); Cloudflare outage post-mortem (2019); CWE-1333

Steps

1. Identify catastrophically vulnerable regex patterns — look for:

   • Nested quantifiers: (a+)+, (a*)*, ([ab]+)+
   • Alternation with overlapping options: (a|aa)+
   • Multiple optional groups applied to the same characters: (a+b?)+

   # VULNERABLE — exponential backtracking on "aaaaaaaaaaaaaaaax"
   import re
   pattern = re.compile(r'^(\w+\s*)+$')           # nested quantifier
   pattern = re.compile(r'^(a+)+$')               # classic evil regex
   pattern = re.compile(r'^([a-zA-Z]+)*$')        # same structure
   
   # Test: time how long this takes (should be microseconds, not seconds)
   import time
   start = time.time()
   re.match(r'^(\w+\s*)+$', 'a' * 30 + '!')
   print(f"{time.time() - start:.3f}s")  # > 1s = vulnerable
   

2. Use atomic groups or possessive quantifiers to prevent backtracking:

   # Python 3.11+ supports atomic groups (?>...) and possessive quantifiers
   import re
   
   # VULNERABLE
   pattern = re.compile(r'^(\w+\s*)+$')
   
   # FIXED — atomic group prevents backtracking into the group
   pattern = re.compile(r'^(?>\w+\s*)+$')   # Python 3.11+
   
   # Alternative for older Python — use regex module
   import regex
   pattern = regex.()  
   

Rules

• re2 does not support backreferences (\1), lookaheads, or lookbehinds — evaluate compatibility before switching.
• Possessive quantifiers (++, *+, ?+) in PCRE/Python regex module prevent backtracking into that group — they are safe but also change match semantics.
• Alternation with shared prefixes is safe — (abc|abd) — alternation with overlapping suffixes is dangerous — (a|aa)+.
• Testing a regex with crafted input in development is not sufficient — use static analysis tools.

Common Mistakes

• Assuming third-party library regexes are safe — npm packages like validator, path-to-regexp, and moment have had ReDoS CVEs. Check package.json deps with npx auditjs.
• Using complex regex for email validation — the RFC-compliant email regex is catastrophically backtracking. Use a simple \S+@\S+\.\S+ or a dedicated library.
• Not testing with adversarial input — a regex that works fine on valid inputs may still explode on malformed ones; always test with 'a' * 30 + '!' style inputs.
• Fixing ReDoS with length checks alone — catastrophic backtracking is exponential; even short inputs (20–50 chars) can take seconds.