Evil Regex Patterns: Nested Quantifiers and Alternation
You'll learn how to spot the most dangerous regex constructs that enable ReDoS attacks.
Why Certain Patterns Are "Evil"
In the previous lesson, you learned that catastrophic backtracking causes ReDoS. Now we'll identify the specific regex patterns that trigger this behavior. Think of these as "landmines" in your validation code—they look harmless but explode when given malicious input.
Nested Quantifiers: The Classic Trap
Nested quantifiers occur when you apply a quantifier inside another quantified group:
(a+)+
(.*)*
([0-9]+)*
Each of these creates exponential backtracking. The outer quantifier says "repeat this group," while the inner one says "repeat this character." When matching fails, the engine tries every possible way to distribute characters between the inner and outer loops—creating a combinatorial explosion.
Analogy: Imagine organizing books on shelves, where each shelf can hold multiple books, and you can have multiple shelves. If your arrangement doesn't work, you'd try moving books between shelves in every possible combination—that's exponential effort.
Overlapping Alternation
Overlapping alternation happens when alternatives can match the same input in multiple ways:
(a|a)*
(foo|foobar)+
(abc|abcd|abcde)*
The regex engine tries each branch, and when one fails late in the string, it backtracks to try other overlapping options—multiplying across repetitions.
Repetition Groups with Overlap
Patterns like (a*)* or (a|ab)* combine both problems: the group can match variably AND repeat. This maximizes backtracking opportunities.
Key Takeaway: Evil regex patterns share common traits—nested quantifiers (a+)+, overlapping alternations (a|a)*, or repeating groups with variable matches (a*)*. Always audit regex for these constructs, especially in user-facing validation code.