期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于DoLFA的高效正则表达式匹配算法

Efficient Regular Expression Matching Algorithm Based on DoLFA
下载PDF
导出
摘要 随着规则数量的急剧增长,表示正则表达式的DFA(Deterministic Finite Automata,确定型有限自动机)容易引起状态空间爆炸,难以满足高速网络的实时处理需求。提出一种高效的正则表达式匹配算法,该算法通过将正则表达式分割为精确串、字符集合以及重复字符3个子集,分别对其进行分区优化及检测,然后再利用结点信息对匹配信号进行连接,即构建一种特殊的状态机DoLFA(Divide-optimize-Link Finite Automata)。理论分析和仿真结果表明,该算法可以大大节省存储空间,并获得较高的吞吐量,且具有较强的扩展性。 With the rapid increase of the number of rules,the DFA used to present regular expression often results in states explosion,so it is very hard to satisfy the requirement of high speed network online processing.This paper proposed an efficient regular expression matching algorithm,which first divides an expression into three subsets：exact string,character class and character repetition,and then optimizes and detects the corresponding blocks,at last links them together with auxiliary node data structure,namely constructing a special state machine DoLFA.Theoretical analysis and simulation shows that this algorithm not only can save more memory space,but also provide high throughput performance and scalability.
作者 杜文超 陈庶樵 胡宇翔
机构地区 国家数字交换系统工程技术研究中心
出处 《计算机科学》 CSCD 北大核心 2012年第9期14-19,共6页 Computer Science
基金 国家重点基础研究发展计划(2012CB315901) 国家科技支撑计划(2011BAH19B01)资助
关键词 深度包检测 正则表达式 有限自动机 编码 计数器 Deep packet inspection Regular expression Finite automata Coding Counter
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献16

  • 1Aho A V, Corasick M J. Efficient String Matching: An Aid to Bibliographic Search[J]. Communications of the ACM, 1975,18, (6) : 333-340.
  • 2Kumar S,Dharmapurikar S, Yu Fang, et al. Algorithms to acce: lerate multiple regular expressions matching for deep packet in- spection[A]//Proc, of SIGCOMM[C]. Pisa, IT ACM Press, 2006:339-350.
  • 3Becchi M, Cadambi S. Memory-effident regular expression search using state merging[A]//Proc, of INFOCOMEC2. Anchorage, USA: IEEE Press, 2007 : 1064 1072.
  • 4Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection[A]//Proc, of the 2007 ACM CoNEXT Conference[C]. New York, USA~ ACM Press, 2007 : 1 12.
  • 5Yu F,Chen Z, Diao Y, et al. Fast and memory-efficient regular expression matching for deep packet inspection [M]. ANCS, 2006 : 93-1 02.
  • 6Smith R,Estan C,Jha S, et al. Deflating the big bang: fast andscalable deep packet inspection with extended finite automata [A]//Proc. of SICA;OMM[C]. Seattle, USA: ACM Press, 2008: 207-218.
  • 7Kumar S, Chandrasekaran B,Turner J, et al. Curing regular ex- pressions matching algorithms from insomnia, amnesia and aeal- culia[A]//Proe, of ANCS[C]. Princeton, USA: ACM Press, 2007:155 164.
  • 8Bando M, Arran N S, Chao H J, et al. LaFA: Lookahead Finite Automata for Scalable Regular Expression Detection [A] /// Proc. of ANCS[C]. Princeton, USA: ACM Press, 2009 : 40-49.
  • 9Bando M, Artan N S, Mehta N, et al. Hardware implementation for scalable Iookahead regular expression deteetion[M]. RAW, 2010.
  • 10Cormen T H, Leiserson C E, Rivest R L, et al. Stein, Introduc- tion to Algorithms (Second Edition)[M]. The MIT Press, 2002.

二级参考文献57

  • 1李伟男,鄂跃鹏,葛敬国,钱华林.多模式匹配算法及硬件实现[J].软件学报,2006,17(12):2403-2415. 被引量：42
  • 2Aho AV, Corasick MJ. Efficient string matching: An aid to bibliographic search. Communications of the ACM, 1975,18(6): 333-340. [doi: 10.1145/360825.360855].
  • 3Li WN, E YP, Ge JG, Qian HL. Multi-Pattern matching algorithms and hardware based implementation. Journal of Software, 2006, 17(12):2403-2415 (in Chinese with English abstract), http://www.j os.org.cn/1000-9825/17/2403.htm [doi: 10.1360/j os 172403 ].
  • 4Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages, and Computation. 3rd ed., Reading: Addison Wesley, 2006.
  • 5Hopcroft J. An O(n log n) algorithm for minimizing states in a finite automaton. Technical Report, STAN-CS-TR-71-190, Stanford: Stanford University, 1971.
  • 6Yu F, Chen ZF, Diao YL, Lakshman TV, Katz RH. Fast and memory-efficient regular expression matching for deep packet inspection. In: Bhuyan LN, Dubois M, Eatherton W, eds. Proe. of the 2006 ACM/IEEE Symp. on Architecture for Networking and Communications Systems. New York: ACM, 2006.93-102. [doi: 10.1145/1185347.1185360].
  • 7AbuHmed T, Mohaisen A, Nyang D. A survey on deep packet inspection for intrusion detection systems. Magazine of Korea Telecommunication Society, 2007,24(11):25-36.
  • 8BrodieBC, Cytron RK, Taylor DE. A scalable architecture for high-throughput regular-expression pattern matching. In: Kaeli D, ed. Proc. of the 33rd Int'l Symp. on Computer Architecture. New York: ACM, 2006. 191-202. [doi: 10.1109/ISCA.2006.7].
  • 9Becchi M, Crowley P. An improved algorithm to accelerate regular expression evaluation. In: Yavatkar R, Grunwald D, Ramakrishnan KK, eds. Proc. of the 2007 ACM/IEEE Symp. on Architecture for Networking and Communications Systems. New York: Association for Computing Machinery, 2007. 145-154. [doi: 10.1145/1323548.1323573].
  • 10Kumar S, Dharmapurikar S, Yu F, Crowley P, Turner J. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Rizzo L, Anderson T, McKeown N, eds. Proc. of the 2006 Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: Association for Computing Machinery, 2006. 339-350. [doi: 10.1145/1159913.1159952].

共引文献24

计算机科学
2012年 第9期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部