2024/03/25 by Jincheng Zhong, Zhong, Jincheng, Shuhui Chen +3
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Network Packet Processing and Optimization #Network Security and Intrusion Detection #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.2403.16533
openalex publication_date 2024/03/25 · openalex created_date 2024/03/27 · openalex updated_date 2026/07/28
Regular expression matching is the core function of various network security applications such as network intrusion detection systems. With the network bandwidth increases, it is a great challenge to implement regular expression matching for line rate packet processing. To this end, a novel scheme named XAV targeting high-performance regular expression matching is proposed in this paper. XAV first employs anchor DFA to tackle the state explosion problem of DFA. Then based on anchor DFA, two techniques including pre-filtering and regex decomposition are utilized to improve the average time complexity. Through implementing XAV with an FPGA-CPU architecture, comprehensive experiments show that a high matching throughput of up to 75 Gbps can be achieved for the large and complex Snort rule-set. Compared to state-of-the-art software schemes, XAV achieves two orders of magnitude of performance improvement. While compared to state-of-the-art FPGA-based schemes, XAV achieves more than 2.5x performance improvement with the same hardware resource consumption.