Regex Performance Optimization: Avoiding ReDoS and Boosting Speed
While regex is powerful, poorly written patterns can cause severe performance issues or even enable Regular Expression Denial of Service (ReDoS) attacks. This article explores performance considerations and optimization strategies.
What is ReDoS?
ReDoS exploits the backtracking mechanism of regex engines. With specially crafted input strings, matching time can grow exponentially, exhausting CPU resources.
Dangerous Regex Patterns
| Dangerous Pattern | Problem | Safe Alternative |
|---|---|---|
(a+)+ | Nested quantifiers | a+ |
(a|a)+ | Overlapping alternation | a+ |
(.*a){n} | Greedy quantifier backtracking | Limit repetitions |
Safety Rule: Avoid nested quantifiers (like (a+)+) and alternation patterns with overlap. These are the most common sources of ReDoS vulnerabilities.
Optimization Techniques
1. Use Non-Capturing Groups
When you only need grouping without capturing, use (?:...) instead of (...). Non-capturing groups skip storing match results, improving performance.
2. Anchor Your Patterns
Use ^ and $ to anchor regex start and end positions whenever possible, reducing the number of starting positions the engine needs to try.
3. Prefer Character Classes Over Alternation
Use [abc] instead of a|b|c. Character classes are much more efficient than alternation.
4. Be Specific, Avoid Wildcards
Use specific character classes (like \d, \w) instead of . to reduce unnecessary match attempts.
Test Your Pattern's Performance
Try the Regex Tester Tool →Conclusion
Writing performant regex is both a performance concern and a security requirement. By understanding backtracking and avoiding dangerous patterns, you can write regex that is both efficient and safe.
References
- OWASP Foundation. "Regular expression Denial of Service - ReDoS." OWASP. https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
- Cox, R. "Regular Expression Matching Can Be Simple And Fast." swtch.com, 2007. https://swtch.com/~rsc/regexp/regexp1.html
- Davis, J. et al. "The Impact of Regular Expression Denial of Service (ReDoS) in Practice." ACM ESEC/FSE, 2018.