高性能正则表达式匹配算法综述

被引：19

作者：

付哲 ^{[1
,2
]}

李军 ^{[2
]}

机构：

[1] 清华大学自动化系

[2] 清华大学信息技术研究院

来源：

计算机工程与应用 | 2018年 / 54卷 / 20期

基金：

国家重点研发计划;

关键词：

正则表达式匹配; 有穷自动机; 算法; 评测;

D O I：

暂无

中图分类号：

TP393.08 [];

学科分类号：

0839 ; 1402 ;

摘要：

深度检测在维护网络安全、保证服务质量等方面扮演着重要的角色。正则表达式匹配算法作为高性能深度检测的核心技术,具有重要的研究价值和实践意义。随着网络流量不断增长、规则数目持续增多以及网络结构日趋灵活和动态,现有的正则表达式匹配算法面临着匹配速度、内存占用和更新能力等多方面的挑战。介绍了正则表达式匹配算法的研究背景,从空间压缩、匹配加速、新型自动机设计以及规则拆分和分组四个角度入手,分类总结了学术界具有影响力的研究成果。通过基于真实网络流量的评测,比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标,并给出了不同需求场景下高效正则表达式匹配算法的选择建议,归纳了高性能正则表达式匹配算法的下一步发展方向。

引用

页码：1 / 13

页数：13

共 21 条

[11] TFA: A Tunable Finite Automaton for Pattern Matching in Network Intrusion Detection Systems[J] . Yang Xu,Junchen Jiang,Rihua Wei,Yang Song,H. Jonathan Chao.IEEE Journal on Selected Areas in Communications . 2014 (10)
[12] PiDFA:a practical multistride regular expression matching engine based on FPGA .2 Yang J,Jiang L,Tang Q,et al. 2016 IEEE International Conference on Communications (ICC) . 2016
[13] Speculative Parallel Pattern Matching
Luchaup, Daniel
Smith, Randy
Estan, Cristian
Jha, Somesh
[J]. IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, 2011, 6 (02) : 438 - 451
[14] An Improved DFA for Fast Regular Expression Matching
Ficara, Domenico
Giordano, Stefano
Procissi, Gregorio
Vitucci, Fabio
Antichi, Gianni
Di Pietro, Andrea
[J]. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2008, 38 (05) : 31 - 40
[15] Deflating the big bang[J] . Randy Smith,Cristian Estan,Somesh Jha,Shijin Kong.ACM SIGCOMM Computer Communication Review . 2008 (4)
[16] A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching[J] . Benjamin C. Brodie,David E. Taylor,Ron K. Cytron.ACM SIGARCH Computer Architecture News . 2006 (2)
[17] Introduction to automata theory, languages, and computation, 2nd edition[J] . John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman.ACM SIGACT News . 2001 (1)
[18] A fast string searching algorithm[J] . Robert S. Boyer,J. Strother Moore.Communications of the ACM . 1977 (10)
[19] Fast Pattern Matching in Strings[J] . Donald E. Knuth,James H. Morris,Jr.,Vaughan R. Pratt.SIAM Journal on Computing . 1977 (2)
[20] Efficient string matching[J] . Alfred V. Aho,Margaret J. Corasick.Communications of the ACM . 1975 (6)

← 1 2 3 →