Study on Pattern Matching in Network Security

Dongliang Xu; Hongli Zhang; Lei Zhang; Chongchong Yao

doi:10.11959/j.issn.1000-0801.2015068

您当前的位置：

首页 >

文章列表页 >

Study on Pattern Matching in Network Security

summarize | 更新时间：2024-06-05

- Study on Pattern Matching in Network Security
- Telecommunications Science Vol. 31, Issue 3, Pages: 115-123(2015)
- 作者机构：
  
  1. 哈尔滨工业大学计算机科学与技术学院哈尔滨 150001
  2. 河南大学数据与知识工程研究所开封 475004
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2015068
  CLC：
- Published Online：2015-03，
  
  Published：20 March 2015
- 稿件说明：
移动端阅览
Dongliang Xu, Hongli Zhang, Lei Zhang, et al. Study on Pattern Matching in Network Security[J]. Telecommunications science, 2015, 31(3): 115-123.
DOI：

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

Views

862

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A network intrusion detection method designed for few-shot scenarios

Attack detection model based on stacking ensemble learning for Internet of vehicles

An intrusion detection model based on convolution neural network for Internet of vehicles

Research on the application of quantum-secure algorithms in 5G network

Research on new energy station network security assessment method based on improved LSTM network

Related Author

Weichen HU

Congyuan XU

Yong ZHAN

Guanghui CHEN

Siqing LIU

Zhiqiang WANG

Xiaolin WANG

XU Huibin

Related Institution

School of Information Engineering, Huzhou University

Department of Information Engineering, Zhumadian Vocatiomal and Technical College

National Engineering Research Center of Cloud and Network Infrastructure Security

China Telecom Research Institute

State Grid Shanxi Electric Power Company

⁰