模式匹配在网络安全中的研究

doi:10.11959/j.issn.1000-0801.2015068

Abstract

Abstract:

Pattern matching is the core module in network security system,it's the highest occupancy rate of system resources is more than 70%.According to problem and challenges of pattern matching in the network security system,taking 2000 as the boundary,the pattern matching was divided into the traditional pattern matching method and the new pattern matching method.Through the analysis of the principle and the computational complexity of different pattern matching method and the development and evolution of the new pattern matching method,applicable environment of different methods was concluded.A comprehensive review and evaluation of pattern matching in network security system was presented.Finally,a conclusion and some suggestions for future research were summarized and prospected.

Key words: pattern matching, intrusion detection, network security

Dongliang Xu,Hongli Zhang,Lei Zhang,Chongchong Yao. Study on Pattern Matching in Network Security[J]. Telecommunications Science, 2015, 31(3): 115-123.

Figures/Tables 7

References 54

1	Navarro G , Raffinot M . Flexible Pattern Matching in Strings:Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge: Cambridge University Press, 2002
2	Knuth D E , Morris J H , Pratt V R , et al. Fast pattern matching in strings. SIAM Journal on Computing, 1977,6（2）:323～350
3	Boyer R S , Moore J S . A fast string searching algorithm. Communications of the ACM, 1977,20（10）:762～772
4	Aho A V , Corasick M J . Efficient string matching:an aid to bibliographic search. Communications of the ACM, 1975,18（6）:333～340
5	Crochemore M , Czumaj A , Gasieniec L , et al. Speeding up two string-matching algorithms. Algorithmica, 1994,12（4～5）:247～267
6	Wu S , Manber U . A Fast Algorithm for Multi-Pattern Searching. Technical Report TR-94-17,University of Arizona, 1994
7	Ukkonen E . Finding approximate patterns in strings. Journal of Algorithms, 1985,6（1～3）:132～137
8	Wu S , Manber U . Fast text searching:allowing errors. Communications of the ACM, 1992,35（10）:83～91
9	Baeza-Yates R A , Gonnet G H . A new approach to text searching. Communications of the ACM, 1992,35（10）:74～82
10	Horspool R N . Practical fast searching in strings. Software:Practice and Experience, 1980,10（6）:501～506
11	Navarro G , Raffinot M . Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics, 2000,5（4）:1～36
12	Allauzen C , Crochemore M , Raffinot M . Efficient experimental string matching by weak factor recognition. Proceedings of 17th Annual Symposium on Combinatorial Pattern Matching, Barcelona,Spain, 2006:51～72
13	Morris J J , Pratt V R . A Linear Pattern-Matching Algorithm. Technical Report 40,University of California, 1970
14	Commentz-Walter B . A String Matching Algorithm Fast on the Average. Berlin:Springer Berlin Heidelberg, 1979
15	Allauzen C , Raffinot M . Factor Oracle of a Set of Words. Institute Gaspart-Monge,University de Marne-la-Vallee,TR-99-11, 1999
16	Blumer A , Blumer J , Haussler D , et al. Complete inverted files for efficient text retrieval and analysis. Journal of the ACM, 1987,34（3）:578～595
17	Sellers P H . On the theory and computation of evolutionary distances. SIAM Journal on Applied Mathematics, 1974,26（4）:787～793
18	Ukkonen E . Finding approximate patterns in strings. Journal of Algorithms, 1985,6（1）:132～137
19	Wu S , Manber U . Fast text searching:allowing errors. Communications of the ACM, 1992,35（10）:83～91
20	Cantone D , Faro S . Fast-search:a new efficient variant of the boyer-moore string matching algorithm. Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms, Ascona,Switzerland, 2003:247～267
21	Cantone D , Faro S . Forward-fast-search:another fast variant of the boyer-moore string matching algorithm. Proceedings of the Prague Stringology Conference, Prague,Czech Republic, 2003:10～24
22	Cantone D , Faro S . Searching for a substring with constant extra-space complexity. Proceedings of the 3rd International Conference on Fun with Algorithms, Isola d'Elba,Italy, 2004:118～131
23	Deusdado S , Carvalho P . GRASPm:an efficient algorithm for exact pattern-matching in genomic sequences. International Journal of Bioinformatics Research and Applications, 2009,5（4）:385～401
24	Fan H , Yao N , Chahed H . Fast variants of the backward-oracle-marching algorithm. Proceedings of the 4th International Conference on Internet Computing for Science and Engineering, Harbin,China, 2009:56～59
25	Faro S , Lecroq T . Efficient variants of the backward-oracle-matching algorithm. Proceedings of the Prague Stringology Conference, Prague,Czech Republic, 2008:146～160
26	Kumar S , Dharmapurikar S , Yu F , et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. Proceedings of SIGCOMM, Pisa,Italy, 2006:339～350
27	Smith R , Estan C , Jha S . XFA:Faster signature matching with extended automata. Proceedings of IEEE Symposium on Security and Privacy, Oakland,CA,USA, 2008:187～201
28	Abla A , Rodriguez-Kessler M , Arce-Santana E R , et al. Approximate string matching using phase correlation. Proceedings of the 34th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, San Diego,CA,USA, 2012:6309～6312
29	Kim Y , Shim K . Efficient top-k algorithms for approximate substring matching. Proceedings of ACM SIGMOD, New York,USA, 2013:385～396
30	Li C , Lu J H , Lu Y M . Efficient merging and filtering algorithms for approximate string searches. Proceedings of IEEE 24th International Conference on Data Engineering, Cancun,Mexico, 2008:257～266
31	Prasad R , Sharma A K , Singh A , et al. Efficient bit-parallel multi-patterns approximate string matching algorithms. Scientific Research and Essays, 2011,6（4）:876～881
32	Xu K , Cui W , Hu Y , et al. Bit-parallel multiple approximate string matching based on GPU. Procedia Computer Science, 2013,17（5）:523～529
33	马明 . 串匹配算法的并行实现策略（硕士学位论文）. 湖北大学， 2010 Ma M . The parallel implementation of string matching algorithm （master dissertation）. Hubei University, 2010
34	Tang Y , Jiang J , Wang X , et al. Independent parallel compact finite automatons for accelerating multi-string matching. Proceedings of IEEE Global Telecommunications Conference, Miami,FL,USA, 2010:1～5
35	Villa O , Sca rpazza D P , Petrini F . Accelerating real-time string searching with multicore processors.Computer. 2008,41（4）:42～50
36	Scarpazza D P , Villa O , Petrini F . Peak-performance DFA-based string matching on the cell processor. Proceedings of 21th International Parallel and Distributed Processing Symposium, Long Beach,USA, 2007:1～8
37	Tan G M , Liu P , Bu D B , et al. Revisiting multiple pattern matching algorithms for multi-core architecture. Journal of Computer Science and Technology, 2011,26（5）:866～874
38	Song H , Lockwood J W . Efficient packet classification for network intrusion detection using FPGA. Proceedings of the 13th International Symposium on Field-Programmable Gate Arrays, Monterey,CA,USA, 2005:238～245
39	Schuehler D V , Lockwood J W . A Modular System for FPGA-Based TCP Flow Processing in High-Speed Networks. Berlin:Springer Berlin Heidelberg, 2004:301～310
40	Katashita T , Maeda A , Toda K , et al. Highly efficient string matching circuit for IDS with FPGA. Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Napa,CA,USA, 2006:285～286
41	Dandass Y S , Burgess S C , Lawrence M , et al. Accelerating string set matching in FPGA hardware for bioinformatics research. BMC Bioinformatics, 2008,9（1）
42	Van Court T , Herbordt M C . Families of FPGA-based accelerators for approximate string matching. Microprocessors and Microsystems, 2007,31（2）:135～145
43	Meiners C R , Patel J , Norige E , et al. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems. Proceedings of the 19th USENIX Conference on Security, Washington,USA, 2010
44	Hua N , Song H , Lakshman T V . Variable-stride multi-pattern matching for scalable deep packet inspection. Proceedings of IEEE INFOCOM, Rio de Janeiro,Brazil, 2009:415～423
45	Bremler-Barr A , Hay D , Koral Y . CompactDFA:generic state machine compression for scalable pattern matching. Proceedings of IEEE INFOCOM, San Diego,CA,USA, 2010:1～9
46	张小山，赵国鸿，王勇军等. 基于TCAM的深度报文过滤技术研究. 2005全国网络与信息安全技术研讨会论文集， 2005:143～148 Zhang X S , Zhao G H , Wang Y J , et al. Research on deep packet filtering technology based on TCAM. 2005 National Conference on Network and Information Security Technology, Shanghai,China, 2005:143～148
47	Gan C G . FPGA based CAM architecture string matching for network intrusion detection （Ph D dissertation）. Universiti Teknologi Malaysia,Faculty of Electrical Engineering, 2012
48	Nigel J , Carla B . Offloading IDS computation to the GPU. Proceedings of the 22nd Computer Security Applications Conference, Miami Beach,FL,USA, 2006:371～380
49	Vasiliadis G , Polychronakis M , Ioannidis S . MIDeA:amulti-parallel intrusion detection architecture. Proceedings of the 18th ACM Conference on Computer and Communications Security, Chicago,USA, 2011
50	Zha X , Sahni S . GPU-to-GPU and host-to-host multipattern string matching on a GPU. IEEE Transactions on Computers, 2013,62（6）:1156～1169
51	Man D , Nakano K , Ito Y . The approximate string matching on the hierarchical memory machine,with performance evaluation. Proceedings of the 7th International Symposium on Embedded Multicore Socs, Tokyo,Japan, 2013:79～84
52	Le H , Prasanna V K . A memory-efficient and modular approach for large-scale string pattern matching. IEEE Transactions on Computers, 2013,62（5）:844～857
53	张宏莉，徐东亮，梁敏等. 海量模式高效匹配方法研究. 电子学报， 2014,42（6）:1220～1224 Zhang H L , Xu D L , Liang M , et al. Massive strings efficient matching method research. Acta Electronica Sinica, 2014,42（6）:1220～1224
54	杨天龙，张宏莉 . 一种关键字表达式的匹配优化方法. 电信科学， 2013,29（1）:39～45 Yang T L , Zhang H L . Optimization of expression matching for string matching. Telecommunications Science, 2013,29（1）:39～45

Metrics

Recommended 0

No Suggested Reading articles found!

[1]	Le ZHANG, Hongyuan MA. Practice on edge cloud security of telecom operators [J]. Telecommunications Science, 2023, 39(4): 165-172.
[2]	Weixiong CHEN, Xiaochen YANG, Zengjun CHUN, Ruolan LI, Hua ZHANG. Research and practice of network security threat intelligence management system for power enterprise [J]. Telecommunications Science, 2022, 38(7): 184-189.
[3]	Yatian LIU, Bowen HU, Maofei CHEN, Dongxin LIU. Study on the 5GC security situational awareness system [J]. Telecommunications Science, 2022, 38(11): 73-85.
[4]	Yue GU, Dan LI, Kaihui GAO. Research on network traffic classification based on machine learning and deep learning [J]. Telecommunications Science, 2021, 37(3): 105-113.
[5]	Ming GAO,Jin LUO,Huiying ZHOU,Hai JIAO,Lili YING. A differential feedback scheduling decision algorithm based on mimic defense [J]. Telecommunications Science, 2020, 36(5): 73-82.
[6]	Yuanying XIAO,Yaodong YOU,Lixi XIANG. Causes and optimization of the false alarm rate of code review system [J]. Telecommunications Science, 2020, 36(12): 155-162.
[7]	Zhiqiang YANG,Li SU,Minpeng QI,Bo YANG. Overview and prospect of 5G security [J]. Telecommunications Science, 2020, 36(12): 1-19.
[8]	Guofeng HE. Application protection in 5G cloud network using zero trust architecture [J]. Telecommunications Science, 2020, 36(12): 123-132.
[9]	Ping XIE,Xiaosong LIU. Security of the deployment of SDN-based IoT using blockchain [J]. Telecommunications Science, 2020, 36(12): 139-146.
[10]	Hang YU,Shuai WANG,Huamin JIN. RASP based Web security detection method [J]. Telecommunications Science, 2020, 36(11): 113-120.
[11]	Junwen WANG. Technical requirement of future industrial internet [J]. Telecommunications Science, 2019, 35(8): 26-38.
[12]	Jianwu ZHANG,Jiasen HUANG,Di ZHOU. Intrusion detection model based on fuzzy theory and association rules [J]. Telecommunications Science, 2019, 35(5): 59-69.
[13]	Cong LI, Bo LEI, Chongfeng XIE, Yunhe LI. Trustworthy network based on blockchain technology [J]. Telecommunications Science, 2019, 35(10): 60-68.
[14]	Jianquan WANG,Zhangchao MA,Xinzhong LI,Lei SUN,Changwei HU. Quantum secure communication network architecture and mobile application solution [J]. Telecommunications Science, 2018, 34(9): 10-19.
[15]	Shigen SHEN,Sheng FENG,Haiping ZHOU,Longjun HUANG,Keli HU,Qiying CAO. Optimal approach of suppressing WSN malware propagation based on cloud computing and dynamic Bayesian game [J]. Telecommunications Science, 2018, 34(9): 78-86.

Study on Pattern Matching in Network Security

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 54

Related Articles 15

Metrics

Recommended 0