2024/01/23 by Hiroya Fujinami, Ichiro Hasuo, Fujinami, Hiroya +1 · 2 citations
Computer Science · #FOS: Computer and information sciences #Network Packet Processing and Optimization #Programming Languages (cs.PL) #Software Testing and Debugging Techniques #Web Application Security Vulnerabilities
paper · pdf · doi:10.48550/arxiv.2401.12639
openalex publication_date 2024/01/23 · openalex created_date 2024/01/25 · openalex updated_date 2026/07/28
Regular expression (regex) matching is fundamental in many applications, especially in web services. However, matching by backtracking -- preferred by most real-world implementations for its practical performance and backward compatibility -- can suffer from so-called catastrophic backtracking, which makes the number of backtracking super-linear and leads to the well-known ReDoS vulnerability. Inspired by a recent algorithm by Davis et al. that runs in linear time for (non-extended) regexes, we study efficient backtracking matching for regexes with two common extensions, namely look-around and atomic grouping. We present linear-time backtracking matching algorithms for these extended regexes. Their efficiency relies on memoization, much like the one by Davis et al.; we also strive for smaller memoization tables by carefully trimming their range. Our experiments -- we used some real-world regexes with the aforementioned extensions -- confirm the performance advantage of our algorithms.