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

基于状态约束的大规模正则表达式匹配算法 被引量：3

States constrain-based algorithm for large scale regular expression matching
下载PDF
导出
摘要 通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程,分析内存增长的原因,提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组,利用状态间的约束关系,将原始NFA转化为NFA和DFA的混合结构。实验表明,在保持一定处理速率的前提下,Group2-DFA能够有效地减少内存占用。在300条规则下,Group2-DFA吞吐率能够达到1Gbps,并且减少约75%的状态数。 By analysis of state explosion in deterministic finite automata DFA, a novel algorithm Group2-DFA based on state constrains was proposed to reduce the memory usage. With the state constrains, states in NFA were classified into several groups. Group2-DFA introduces two-level classification and merges NFA and DFA together to a hybrid FA construction. The experiments show that G-roup2-DFA can reduce memory usage efficiently and keep high throughput with a small increase of memory reading time. With 300 regex rules, Group2-DFA can cut 75% states and achieve 1Gbps throughput.
作者 贺炜 郭云飞 扈红超
机构地区 国家数字交换系统工程技术研究中心
出处 《通信学报》 EI CSCD 北大核心 2013年第10期183-190,共8页 Journal on Communications
基金 国家科技支撑计划基金资助项目(2012BAH02B03 2012BAH02B01) 国家高技术研究发展计划("863"计划)基金资助项目(2011AA01A103 2011AA01A101 2011BAH19B04)~~
关键词 正则表达式 状态爆炸 自动机转化 状态约束 regular expression state explosion automata convert state constrains
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献16

  • 1JIANG L, TAN J, LIU Y. ClusterFA: a memory-efficient DFA struc- ture for network intrusion detection[A]. Proceedings of the 7th ACM Symposium on Computer and Communications Security Informa- tion[C]. New York,USA, 2012.65-66.
  • 2BECCHI M, CROWLEY P. Efficient regular expression evaluation: theory to practice[A]. Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. Colorado: ACM, 2008.50-59.
  • 3YANG Y H E, JIANG W, PRASANNA V K. Compact architecture for high-throughput regular expression matching on FPGA[A]. Pro- ceedings of the 4th ACM/IEEE Symposium on Architecturea for Net- working and Communications Systems[C]. San Jose, California,USA, 2008.30-39.
  • 4ZHENG K, ZHANG X, CAI Z, et al. Scalable NIDS via negative pattern matching and exclusive pattern matching[A]. Proceeding IEEE International Conference on Computer Communications, Join Conference of the IEEE Computer and Communications Societies[C[.[ San Dieg12010. 1-9. /.
  • 5LIN C H, HUANG C T, JIANG C P, et al. Optimization of regular expression pattern matching circuits on FPGA[A]. Proceedings of De- sign, Automation and Test in Europe[C]. Germany, 2006. 1-6.
  • 6LE H, PRASANNA V. A memory-efficient and modular approach for large-scale string pattern matching[J]. IEEE Transactions on Com- puters, 2013,62(5):844-857.
  • 7BECCHI M, CROWLEY P. A hybrid f'mite automaton for practical deep packet inspection[A]. Proceedings of ACM CoNEXT Confer- ence[C]. New York,USA, 2007.1-12.
  • 8YU F, CHEN Z, DIAO Y, et al. Fast and memory-efficient regular expression matching for deep packet inspection[A]. ACM/IEEE Sym- posium on Architecture for Networking and Communications Sys- temiC]. San Jose, California,USA, 2006.93-102.
  • 9PASETTO D, PETRINI F, AGARWAL V. Tools for very fast regular expression matching[J]. Computer, 2010, 43(3):50-58.
  • 10QI Y, WANG K, FONG J, et al. FEACAN: from-end acceleration for content-aware network processing[A]. Proceedings of 30th IEEE In- ternational Conference on Computer Communications, Joint Confer- ence of the IEEE Computer and Communications Societies[C]. Shanghai, China, 2011.2114-2122.

同被引文献25

  • 1HOPCROFT J E, ULLMANJ D. Introduction to Automata Theory, Lan- guages and Computation 2nd Edition[M]. US: Addison Wesley, 2001.
  • 2YU F, CHEN Z F, DIAO Y L, et al. Fast and memory-efficient regular expression matching for deep packet inspection[A]. Proceedings of the IEEE/ACM Symposium on Architectures for Networking and Com- munications Systems[C]. San Jose, Canada, 2006.93-102.
  • 3BECCHI M, CROWLEY E A hybrid finite automaton for practical deep packet inspection [A].Proceedings of the 2007 ACM CoNEXT conference[C]. New York, USA, 2007. 1.
  • 4YANG Y H E, PRASANNA V K. Space-time tradeoff in regular ex- pression matching with semi-deterministic finite automata[A]. IN- FOCOM, 2011 Proceedings IEEE[C]. Shanghai, China, 2011. 1853-1861.
  • 5KUMAR S, CHANDRASEKARAN B, TURNER J, et al. Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia[A]. Proceedings of the 3rd ACM/IEEE Symposium on Ar- chitecture for Networking and Communications Systems[C]. Orlando, USA, 2007. 155-164.
  • 6SMITH R, ESTAN C, JHA S, et al. Deflating the big bang: fast and scalable deep packet inspection with extended f'mite automata [A].SIGCOMM '08 Proceedings of the ACM SIGCOMM 2008 con- ference on Data communication [C]. Seattle, USA, 2008. 207-218.
  • 7KUMAR S, DHARMAPURIKAR crate multiple regular expressions tion[A]. Proceedings of the 2006 S, YU F, et al. Algorithms to accel- matching for deep packet inspec- Conference on Applications, Toch- nologies, Architectures, and Protocols for Computer Communica- tions[C]. Pisa, Italy, 2006. 339-350.
  • 8BECCHI M, CADAMBI S. Memory-efficient regular expression search using state merging[A]. INFOCOM 2007, the 26th IEEE Inter- national Conference on Computer Communications[C]. Anchorage, USA, 2007. 1064-1072.
  • 9FICARA D, GIORDANO S, PROCISSI C~ et al. An improved DFA for fast regular expression matching[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(5): 29-40.
  • 10FICARA D, DI P1ETRO A, GIORDANO S, et al. Differential encod- ing of DFA for fast regular expression matching[J]. IEEE/ACM Transactions on Networking, 2011, 19(3): 683-694.

引证文献3

二级引证文献5

通信学报
2013年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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