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

doi:10.11959/j.issn.1000-0801.2015068

摘要/Abstract

摘要：

模式匹配模块是网络安全系统的核心模块，其系统资源占用率最高时可达70%以上。针对模式匹配在当前网络安全系统中面临的问题和挑战，以2000年为界将模式匹配方法分为传统模式匹配方法和新模式匹配方法，通过分析不同模式匹配方法的原理、计算复杂度和新模式匹配方法的发展与演化过程，得出不同方法的适用环境，对模式匹配技术在网络安全系统中的作用进行了全面综述和评价，最后对未来的研究方向进行了总结和展望。

关键词: 模式匹配, 入侵检测, 网络安全

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

徐东亮,张宏莉,张磊,姚崇崇. 模式匹配在网络安全中的研究[J]. 电信科学, 2015, 31(3): 115-123.

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

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 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

[1]	周胜利, 蒋可怡, 徐博, 徐睿, 张熙康, 赵泉喆, 徐阳东. 面向电信网络诈骗治理的网络安全课程构建效能评估研究[J]. 电信科学, 2023, 39(6): 122-128.
[2]	张乐, 马洪源. 运营商网络边缘云安全实践[J]. 电信科学, 2023, 39(4): 165-172.
[3]	陈伟雄, 杨晓晨, 春增军, 李若兰, 张华. 电力企业网络安全威胁情报管理体系的研究与实践[J]. 电信科学, 2022, 38(7): 184-189.
[4]	刘亚天, 呼博文, 陈茂飞, 刘东鑫. 5GC安全态势感知系统研究[J]. 电信科学, 2022, 38(11): 73-85.
[5]	顾玥, 李丹, 高凯辉. 基于机器学习和深度学习的网络流量分类研究[J]. 电信科学, 2021, 37(3): 105-113.
[6]	高明,罗锦,周慧颖,焦海,应丽莉. 一种基于拟态防御的差异化反馈调度判决算法[J]. 电信科学, 2020, 36(5): 73-82.
[7]	李玉峰,陆肖元,曹晨红,李江涛,朱泓艺,孟楠. 智能网联汽车网络安全浅析[J]. 电信科学, 2020, 36(4): 36-45.
[8]	杨志强,粟栗,齐旻鹏,杨波. 5G安全技术与标准[J]. 电信科学, 2020, 36(12): 1-19.
[9]	何国锋. 零信任架构在5G云网中应用防护的研究[J]. 电信科学, 2020, 36(12): 123-132.
[10]	谢萍,刘孝颂. 基于区块链的SDN物联网部署安全[J]. 电信科学, 2020, 36(12): 139-146.
[11]	肖芫莹,游耀东,向黎希. 代码审计系统的误报率成因和优化[J]. 电信科学, 2020, 36(12): 155-162.
[12]	余航,王帅,金华敏. 基于RASP的Web安全检测方法[J]. 电信科学, 2020, 36(11): 113-120.
[13]	王俊文. 未来工业互联网发展的技术需求[J]. 电信科学, 2019, 35(8): 26-38.
[14]	章坚武,黄佳森,周迪. 基于模糊理论与关联规则的入侵检测模型[J]. 电信科学, 2019, 35(5): 59-69.
[15]	李聪, 雷波, 解冲锋, 李云鹤. 基于区块链技术的可信网络[J]. 电信科学, 2019, 35(10): 60-68.