Question 1

What is ReDoS (Regular Expression Denial of Service)?

Accepted Answer

ReDoS is a class of denial-of-service vulnerability where a maliciously crafted input string causes a regex engine to take exponential or polynomial time to evaluate, effectively hanging or crashing the process. It arises from a combination of two factors: (1) backtracking — most regex engines use backtracking to explore all possible match paths when a match fails, and (2) ambiguous patterns — regexes where multiple paths through the pattern can match the same input characters, causing the backtracking to explore exponentially many combinations before concluding no match exists.

Question 2

What regex patterns are most vulnerable to ReDoS?

Accepted Answer

The most dangerous patterns involve nested quantifiers and alternation where sub-patterns can overlap. The classic example is (a+)+ or (a|aa)+ — each has exponential blowup on an input like 'aaaaaaaab'. Other risky patterns: (.*)* (nested Kleene star), (a*b?c*)+ (overlapping groups), and patterns with multiple adjacent .* or .+ operators. Any pattern where the same character can be matched by two or more different paths in the pattern tree is a potential ReDoS vector.

Question 3

How does a ReDoS detector identify vulnerable patterns?

Accepted Answer

Static analysis tools detect ReDoS by analyzing the regex's internal structure — specifically looking for: (1) Nested quantifiers: an expression inside a quantifier that is itself repeated (e.g., (X+)+). (2) Exponential ambiguity: paths through the NFA (Nondeterministic Finite Automaton) that can match the same string in multiple ways — this is detected by running the NFA on specific attack strings or via formal analysis of the state graph. Tools like safe-regex, vuln-regex-detector, and rxxr2 use these techniques.

Question 4

How do I fix a ReDoS-vulnerable regex?

Accepted Answer

Common fixes: (1) Remove nested quantifiers — rewrite (a+)+ as a+. (2) Make alternation non-overlapping — instead of (cat|catch), use catch|cat (longest first) or (cat)(?:ch)?. (3) Use possessive quantifiers or atomic groups where the regex engine supports them — (?>a+) never backtracks. (4) Use a linear-time regex engine like RE2, Hyperscan, or Go's regexp package, which guarantees O(n) matching by using DFA/NFA evaluation without backtracking. (5) Validate or limit the length of user-supplied input before matching.

Question 5

Which programming language regex engines are vulnerable to ReDoS?

Accepted Answer

Backtracking engines (vulnerable): JavaScript (V8), Python (re module), Java (java.util.regex), PHP (PCRE), Ruby, .NET — all can exhibit exponential blowup. Non-backtracking engines (safe): RE2 (Google), Go regexp, Rust regex crate, Hyperscan — these guarantee linear O(n) time but do not support lookaheads/lookbehinds or backreferences. Node.js 21+ includes experimental RE2 support. For security-sensitive input validation, RE2 or similar linear-time engines should be strongly preferred.

Regex ReDoS Detector

Frequently Asked Questions

Comments & Feedback