Towards an Effective Method of ReDoS Detection for Non-backtracking Engines
Weihao Su, Haiming Chen, Tingjian Ge
33rd USENIX Security Symposium · Day 1 · USENIX Security '24
Regular expression Denial of Service (**ReDoS**) attacks represent a significant threat to applications that rely on regular expressions for pattern matching, often leading to severe performance degradation or complete service unavailability. This talk, presented by Tingjian Ge from the University of Michigan, delves into a critical, yet often overlooked, vulnerability vector in modern regular expression engines: those that employ non-backtracking algorithms. Traditionally, non-backtracking engines were heralded as a safer and faster alternative to their backtracking counterparts, largely due to their perceived linear time complexity. However, this research challenges that assumption, demonstrating that these engines are far from immune to ReDoS, exhibiting super-linear performance in specific, crafted scenarios.
AI review
This research definitively debunks the long-held myth that non-backtracking regex engines are immune to ReDoS, revealing critical vulnerabilities rooted in determinization blow-up and Unicode handling. EvilStringGen, a novel tool, effectively identifies these complex issues, demonstrating significant real-world impact by uncovering flaws in widely-used open-source projects. This work demands immediate attention from anyone building or defending systems.