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

一种用于深度包检测的正则表达式分组算法 被引量：1

A Regular Expression Grouping Algorithm for Deep Packet Inspection
下载PDF
导出
摘要 当前深度包检测算法通常需要将正则表达式转换为NFA或者DFA,但是随着网络带宽的不断增加,NFA和DFA状态占用的存储空间越来越大,极大地考验着系统的存储能力。为了应对这个问题,提出一种基于正则表达式相性的分组算法来对表达式进行分组,实验证明该算法能减少NFA和DFA状态的数量,提高匹配的效率。 The current Deep Packet Inspection （DPI） algorithm usually need to transform regular expres- sions into NFA or DFA. But with network bandwidth＇s increase, states of NFA and DFA take more and more memory space. It tests greatly system＇s memory capacity. In order to deal with this problem, puts forward a new concept： regular expression compatibility. And we divide regu- lar expressions into groups through a new grouping algorithm. The experiment shows it could re- duce the number of states of NFA and DFA and improve matching efficiency.
作者 杜江 王希
机构地区 重庆邮电大学计算机科学与技术学院 重庆邮电大学通信与信息工程学院
出处 《现代计算机》 2012年第12期3-5,9,共4页 Modern Computer
关键词 深度包检测 正则表达式 NFA DFA 相性 DPI Regular Expression NFA DFA Compatibility
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献12

  • 1Knuth, D E Morris, J H Partt, V R. Fast Pattern Matching in Strings[J]. SIAM Journal on Computer, 1977, 6:323-350.
  • 2Boyer, Robert S Moore, J Strother. A Fast String Searching Algorithm[C]. Communications of the ACM, 1977, 20: 762- 772.
  • 3DM Sunday. A Very Fast Substring Search Algorithm [C]. Communications of the ACM, 1990, 33(8):132-142.
  • 4Corasick, Margaret. Efficient String Matching: An Aid to Bib- liographic Search[C]. Communications of the ACM, 1975, 18: 333-340.
  • 5Wu Sun, Manber U. A Fast Algorithm for Multi-Pattern Searching[R]. The University of Arizona: The Computer Science Department, 1994.
  • 6AV Aho, Margaret J. Efficient String Matching: An Aid to Bibliographic Search[C]. Communications of the ACM, 1975, 18(6): 333-340.
  • 7Robin Sommer, Vern Paxson. Enhancing Byte-Level Network Intrusion Detection Signatures with Context [J]. CCS' 03Pro- ceedings of the lOth ACM Conference on Computer and Communications Security, 2003.9:262-271.
  • 8Fang Yu, Zhifeng Chen, Yanlei Diao. Fast and Memory-Effi- cient Regular Expression Matching for Deep Packet Inspec- tion [M]. Architecture for Networking and Communications Systems, 2006.
  • 9肖武德.一种正则表达式的高效分组算法[J].计算机安全,2010(4):57-59. 被引量：4
  • 10张树壮,罗浩,方滨兴,云晓春.一种面向网络安全检测的高性能正则表达式匹配算法[J].计算机学报,2010,33(10):1976-1986. 被引量：27

二级参考文献20

  • 1J. Levandoski, E. Sommer, and M. Strait. Application Layer Packet Classifier for Linux. 网址: http://17-filter. sourceforge. net/.
  • 2SNORT Network Intrusion Detection System. 网址: http:// www. snort. org.
  • 3中科院计算所网络信息安全研究组译.柔性字符串匹配,电子工业出版社,2007.
  • 4Fang YU, Zhifeng Chen, Yanlei Diao, T. V. Lakshman. Randy H. Katz, Fast and memory-efficient regular expression matching for deep packet inspection. Proceedings of the 2006ACM/IEEE symposium on ANCS, December 03 05, 2006, San Jose, California, USA.
  • 5S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley and J. Turner. Algorithms to accelerate mul-tiple regular expressions matching for deep packet inspection. ACM SIGCOMM ComputerCommunication R, eview, 56(4): 339 - 350, 2006.
  • 6Yu Fang, Chen Zhifeng, Diao Yanlei et al. Fast and memory-efficient regular expression matching for deep packet in spection//Proceedings of the IEEE/ACM ANCS. San Jose California, 2006:93-102.
  • 7Kumar S, Dharmapurikar S, Yu F et al. Algorithms to accelerate multiple regular expressions matching for deep pack et inspection//Proceedings of the ACM SIGCOMM. Pisa, Italy, 2006:339-350.
  • 8Becchi M, Cadambi S. Memory-efficient regular expression search using state merging/ /Proceedings of the IEEE Infocom. Anchorage, Alaska, 2007:1064-1072.
  • 9Kumar S, Chandrasekaran G, Turner Jet al. Curing regular expressions matching from insomnia, amnesia and acalculia// Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems. Orlando, Florida, USA, 2007. 155-164.
  • 10Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection//Proceedings of the ACM CoNEXT. New York, 2007:1-12.

共引文献27

同被引文献3

引证文献1

现代计算机
2012年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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