Parallel Architecture for High Throughput DFA-Based Deep Packet Inspection
作者： J. Jiang , X. Wang , K. He , B. Liu
关键词: Throughput (business) 、 Finite-state machine 、 Parallel processing (DSP implementation) 、 Deterministic finite automaton 、 Parallel computing 、 Pattern matching 、 Deep packet inspection 、 Computer science 、 High memory 、 Intrusion detection system 、 Speedup 、 Regular expression
摘要: Multi-pattern matching is a key technique for implementing network security applications such as Network Intrusion Detection/Protection Systems (NIDS/NIPSes) where every packet inspected against predefined attack signatures written in regular expressions (regexes). To this end, Deterministic Finite Automaton (DFA) widely used multi-regex matching, but existing DFAbased researches have claimed high throughput at an expenses of extremely memory cost. In paper, we propose parallel architecture DFA called Parallel (PDFA), using multiple flow aggregations to increase the with nearly no extra The basic idea selectively store modules which can be accessed and explore potential parallelism. cost our system both average cases worst analyzed, optimized evaluated by numerical results. evaluation shows that obtain speedup about 0.5k 0.7k k number under synthetic trace compressed real statistical case, compared traditional DFA-based approaches.
sci-hub.se 参考文章(14)
Fang Yu, Zhifeng Chen, Yanlei Diao, T. V. Lakshman, Randy H. Katz, Fast and memory-efficient regular expression matching for deep packet inspection Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems - ANCS '06. pp. 93- 102 ,(2006) , 10.1145/1185347.1185360
Shijin Kong, Randy Smith, Cristian Estan, Efficient signature matching with multiple alphabet compression tables Proceedings of the 4th international conference on Security and privacy in communication netowrks - SecureComm '08. pp. 1- ,(2008) , 10.1145/1460877.1460879
Sailesh Kumar, Sarang Dharmapurikar, Fang Yu, Patrick Crowley, Jonathan Turner, Algorithms to accelerate multiple regular expressions matching for deep packet inspection acm special interest group on data communication. ,vol. 36, pp. 339- 350 ,(2006) , 10.1145/1151659.1159952
G.D. Hachtel, E. Macii, A. Pardo, F. Somenzi, Markovian analysis of large finite state machines IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 15, pp. 1479- 1493 ,(1996) , 10.1109/43.552081
Michela Becchi, Patrick Crowley, A hybrid finite automaton for practical deep packet inspection Proceedings of the 2007 ACM CoNEXT conference on - CoNEXT '07. pp. 1- ,(2007) , 10.1145/1364654.1364656
Ke Wang, Salvatore J. Stolfo, Anomalous Payload-Based Network Intrusion Detection recent advances in intrusion detection. pp. 203- 222 ,(2004) , 10.1007/978-3-540-30143-1_11
Michela Becchi, Patrick Crowley, An improved algorithm to accelerate regular expression evaluation Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems - ANCS '07. pp. 145- 154 ,(2007) , 10.1145/1323548.1323573
N. Hua, H. Song, T. V. Lakshman, Variable-Stride Multi-Pattern Matching For Scalable Deep Packet Inspection international conference on computer communications. pp. 415- 423 ,(2009) , 10.1109/INFCOM.2009.5061946
Sailesh Kumar, Jonathan Turner, John Williams, Advanced algorithms for fast and scalable deep packet inspection Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems - ANCS '06. pp. 81- 92 ,(2006) , 10.1145/1185347.1185359
Benjamin C. Brodie, David E. Taylor, Ron K. Cytron, A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching ACM SIGARCH Computer Architecture News. ,vol. 34, pp. 191- 202 ,(2006) , 10.1145/1150019.1136500