Memory-Efficient Regular Expression Matching Algorithms For Deep Packet Inspection

Due to the rapid growth of network applications, network security is becoming more and more critical. Network Intrusion Detection and Prevention Systems (NIDS/NIPS) are emerging as a promising approach to protecting network security, which monitor real-time network traffic for inspecting and preventing network attacks. Deep Packet Inspection (DPI) is the core of NIDS/NIPS. DPI has a set of predefined signature rules, and scan both each packet's headers and payloads against the set of rules for identifying suspicious activities. As regular expressions are more flexible and powerful, contemporary NIDS/NIPS are using the regular expressions for known attack signatures. Traditional regular expression matching algorithms use a Nondeterministic Finite Automaton (NFA) or Deterministic Finite Automaton (DFA) to represent the regular expressions of signatures.Regular expression matching algorithms have a significant challenge of high performance. To achieve wire-speed packet processing, hardware-based regular expression matching algorithms have been proposed by using modern embedded memory. On the other hand, these hardware-based algorithms suffer from the limitation of small embedded memory that is not sufficient to hold the ever-increasing signature rules. Hence, it is crucial for high-performance DPI to design a fast and memory-efficient regular expression matching algorithm.This paper presents the state-of-art regular expression matching algorithms, and analyzes the reason that both NFA and DFA can not meet the performance needs of high-speed network. And the paper studies some memory-efficient regular expression matching algorithms. Recent studies lack a comprehensive performance evaluation of regular expression matching algorithms. This paper uses C++ to implement DFA and its variants such as mDFA, D2FA, CD2FA, and XFA for evaluating the performance on the Snort rules. Experimental results show that XFA achieves the best trade-off between time and space performance. In addition, we propose an Alphabet-Compress-based Finite Automaton (ACFA) to reduce the memory requirements of XFA. In practice, the ACFA uses heuristic algorithms to group XFA states into several state sets, in each of which an alphabet compression table is constructed to reduce the memory consumption. Experimental results show that the ACFA is a fast and memory-efficient regular expression matching algorithm.