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

徐东亮; 张宏莉; 张磊; 姚崇崇

doi:10.11959/j.issn.1000-0801.2015068

您当前的位置：

首页 >

文章列表页 >

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

综述 | 更新时间：2024-06-05

- 模式匹配在网络安全中的研究
- Study on Pattern Matching in Network Security
- 电信科学 2015年31卷第3期页码：115-123
- 作者机构：
  
  1. 哈尔滨工业大学计算机科学与技术学院哈尔滨 150001
  2. 河南大学数据与知识工程研究所开封 475004
- 作者简介：
  
  [ "徐东亮，男，哈尔滨工业大学计算机科学与技术学院博士生，主要研究方向为模式匹配、入侵检测和信息安全等。" ]
  [ "张宏莉，女，博士，哈尔滨工业大学计算机科学与技术学院教授、博士生导师，主要研究方向为网络与信息安全、网络测量与建模、网络计算、并行处理等。" ]
  [ "张磊，男，河南大学数据与知识工程研究所博士生，主要研究方向为概念格分析、数据挖掘和信息安全。" ]
  [ "姚崇崇，男，哈尔滨工业大学计算机科学与技术学院硕士生，主要研究方向为字符串匹配、入侵检测。" ]
- 基金信息：
  
  国家重点基础研究发展计划（“973”计划）基金资助项目;The National Basic Research Program of China （973 Program）(2011CB302605);国家高技术研究发展计划（“863”计划）基金资助项目;The National High Technology Research and Development Program of China（863 Program）(2011AA010705);国家高技术研究发展计划（“863”计划）基金资助项目;The National High Technology Research and Development Program of China（863 Program）(2012AA012502);国家高技术研究发展计划（“863”计划）基金资助项目;The National High Technology Research and Development Program of China（863 Program）(2012AA012506);国家科技支撑计划基金资助项目;The National Key Technology R＆D Program(2012BAH37B01);国家自然科学基金资助项目;The National Natural Science Foundation of China(61202457);国家自然科学基金资助项目;The National Natural Science Foundation of China(61402149)
- DOI：10.11959/j.issn.1000-0801.2015068
  中图分类号：
- 网络出版日期：2015-03，
  
  纸质出版日期：2015-03-20
- 稿件说明：
移动端阅览
徐东亮, 张宏莉, 张磊, 等. 模式匹配在网络安全中的研究[J]. 电信科学, 2015,31(3):115-123.

Dongliang Xu, Hongli Zhang, Lei Zhang, et al. Study on Pattern Matching in Network Security[J]. Telecommunications science, 2015, 31(3): 115-123.
徐东亮, 张宏莉, 张磊, 等. 模式匹配在网络安全中的研究[J]. 电信科学, 2015,31(3):115-123. DOI： 10.11959/j.issn.1000-0801.2015068.

Dongliang Xu, Hongli Zhang, Lei Zhang, et al. Study on Pattern Matching in Network Security[J]. Telecommunications science, 2015, 31(3): 115-123. DOI： 10.11959/j.issn.1000-0801.2015068.

摘要

模式匹配模块是网络安全系统的核心模块，其系统资源占用率最高时可达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.

关键词

Keywords

references

Navarro G , Raffinot M . Flexible Pattern Matching in Strings:Practical On-Line Search Algorithms for Texts and Biological Sequences . Cambridge : Cambridge University Press , 2002

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

Boyer R S , Moore J S . A fast string searching algorithm . Communications of the ACM , 1977 , 20 （ 10 ）: 762 ～ 772

Aho A V , Corasick M J . Efficient string matching:an aid to bibliographic search . Communications of the ACM , 1975 , 18 （ 6 ）: 333 ～ 340

Crochemore M , Czumaj A , Gasieniec L , et al . Speeding up two string-matching algorithms . Algorithmica , 1994 , 12 （ 4～5 ）: 247 ～ 267

Wu S , Manber U . A Fast Algorithm for Multi-Pattern Searching . Technical Report TR-94-17,University of Arizona , 1994

Ukkonen E . Finding approximate patterns in strings . Journal of Algorithms , 1985 , 6 （ 1～3 ）: 132 ～ 137

Wu S , Manber U . Fast text searching:allowing errors . Communications of the ACM , 1992 , 35 （ 10 ）: 83 ～ 91

Baeza-Yates R A , Gonnet G H . A new approach to text searching . Communications of the ACM , 1992 , 35 （ 10 ）: 74 ～ 82

Horspool R N . Practical fast searching in strings . Software:Practice and Experience , 1980 , 10 （ 6 ）: 501 ～ 506

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

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

Morris J J , Pratt V R . A Linear Pattern-Matching Algorithm . Technical Report 40,University of California , 1970

Commentz-Walter B . A String Matching Algorithm Fast on the Average . Berlin:Springer Berlin Heidelberg , 1979

Allauzen C , Raffinot M . Factor Oracle of a Set of Words . Institute Gaspart-Monge,University de Marne-la-Vallee,TR-99-11 , 1999

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

Sellers P H . On the theory and computation of evolutionary distances . SIAM Journal on Applied Mathematics , 1974 , 26 （ 4 ）: 787 ～ 793

Ukkonen E . Finding approximate patterns in strings . Journal of Algorithms , 1985 , 6 （ 1 ）: 132 ～ 137

Wu S , Manber U . Fast text searching:allowing errors . Communications of the ACM , 1992 , 35 （ 10 ）: 83 ～ 91

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

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

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

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

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

Faro S , Lecroq T . Efficient variants of the backward-oracle-matching algorithm . Proceedings of the Prague Stringology Conference , Prague,Czech Republic , 2008 : 146 ～ 160

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

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

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

Kim Y , Shim K . Efficient top-k algorithms for approximate substring matching . Proceedings of ACM SIGMOD , New York,USA , 2013 : 385 ～ 396

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

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

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

马明 . 串匹配算法的并行实现策略（硕士学位论文） . 湖北大学， 2010

Ma M . The parallel implementation of string matching algorithm （master dissertation） . Hubei University , 2010

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

Villa O , Sca rpazza D P , Petrini F . Accelerating real-time string searching with multicore processors.Computer . 2008 , 41 （ 4 ）: 42 ～ 50

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

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

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

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

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

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 ）

Van Court T , Herbordt M C . Families of FPGA-based accelerators for approximate string matching . Microprocessors and Microsystems , 2007 , 31 （ 2 ）: 135 ～ 145

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

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

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

张小山，赵国鸿，王勇军等 . 基于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

Gan C G . FPGA based CAM architecture string matching for network intrusion detection （Ph D dissertation） . Universiti Teknologi Malaysia,Faculty of Electrical Engineering , 2012

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

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

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

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

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

张宏莉，徐东亮，梁敏等 . 海量模式高效匹配方法研究 . 电子学报， 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

杨天龙，张宏莉 . 一种关键字表达式的匹配优化方法 . 电信科学， 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

浏览量

862

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种适用于小样本条件的网络入侵检测方法

车联网中基于stacking集成学习的攻击检测模型

面向车联网的基于卷积神经网络的入侵检测模型

5G网络量子安全算法应用研究

基于改进长短期记忆网络的新能源场站网络安全评估方法研究