基于多维立方体的正则表达式匹配算法

发布时间：2017-06-25 10:09

  本文关键词：基于多维立方体的正则表达式匹配算法，由笔耕文化传播整理发布。

【摘要】：针对特定条件下含有".*"的正则表达式规则相互作用产生的状态爆炸问题,本文提出一种基于多维立方体的确定性有限自动机(Deterministic Finite Automaton,DFA)结构,将冗余状态按维度划分并压缩,并设计相应的多维立方体确定性有限自动机(Multi-Dimension-Cube-DFA,M-D-Cube-DFA)算法,通过构造动态交点的方法实现等价的状态转移.理论分析和仿真实验表明,与DFA算法相比,在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩.
【作者单位】： 国家数字交换系统工程技术研究中心;65711部队司令部;
【关键词】： 正则表达式 特征匹配 自动机 确定性有限自动机 非确定性有限自动机 多维立方体
【基金】：国家863高技术研究发展计划(No.2011AA01A103、2011AA01A101) 国家973重点基础研究发展计划(No.2012CB315901,No.2013CB329104) 国家科技支撑计划(No.2011BAH19B01)
【分类号】：TP393.08
【正文快照】： 1引言目前,正则表达式匹配(Regular Expression Matc-hing,REM)技术广泛应用于网络入侵检测和防御系统,作为深度数据包检测的核心算法来进行非法内容检测、恶意代码检测、入侵检测、协议分析等.近年来,随着计算机网络的持续发展及网络带宽的逐年增加,REM面临如何满足高速网络

【参考文献】

中国期刊全文数据库 前3条

1 张大方;张洁坤;黄昆;;一种基于智能有限自动机的正则表达式匹配算法[J];电子学报;2012年08期

2 徐乾;鄂跃鹏;葛敬国;钱华林;;深度包检测中一种高效的正则表达式压缩算法[J];软件学报;2009年08期

3 张树壮;罗浩;方滨兴;;面向网络安全的正则表达式匹配技术[J];软件学报;2011年08期

【共引文献】

中国期刊全文数据库 前10条

1 韩光辉;曾诚;;正则表达式方程组的最小解[J];电脑与信息技术;2011年05期

2 肖武德;;一种正则表达式的高效分组算法[J];计算机安全;2010年04期

3 张宏莉;徐东亮;梁敏;刘宇峰;;海量模式高效匹配方法研究[J];电子学报;2014年06期

4 张树壮;罗浩;方滨兴;云晓春;;一种面向网络安全检测的高性能正则表达式匹配算法[J];计算机学报;2010年10期

5 张墨华;李戈;;基于中间点划分无冲突哈希的高速包处理[J];计算机应用;2012年04期

6 李鲲鹏;兰巨龙;李印海;;基于Bloom filter的高效正则表达式匹配算法[J];计算机应用研究;2012年03期

7 余平;胡玲;;深度包检测消息传递技术[J];内江师范学院学报;2010年08期

8 翟丽杰;段海生;;基于正则表达式的DFA拆分算法研究[J];计算机与数字工程;2012年08期

9 魏德志;洪联系;林丽娜;吴旭;;一种改进的XFA在深度包检测中的应用[J];计算机工程与应用;2012年34期

10 张宏武;;基于分布式高校网站站群管理系统的设计与实现[J];科教文汇(上旬刊);2013年09期

中国博士学位论文全文数据库 前2条

1 许宪成;基于网络处理器的入侵检测系统设计与性能优化研究[D];华南理工大学;2010年

2 张树壮;面向网络安全的高性能特征匹配技术研究[D];哈尔滨工业大学;2011年

中国硕士学位论文全文数据库 前10条

1 段海生;基于正则表达式的深度包压缩算法研究[D];西安电子科技大学;2010年

2 张辉;面向网络流识别的正则表达式匹配技术研究[D];首都师范大学;2011年

3 崔保良;基于稀疏表示的协同入侵检测[D];广东工业大学;2011年

4 刘鹏;面向存储的正则表达式匹配算法研究[D];解放军信息工程大学;2010年

5 曹鼎;文件类型识别技术研究[D];解放军信息工程大学;2011年

6 陈围;高速IP网络中深度包检测算法研究[D];解放军信息工程大学;2011年

7 张群羚;恶意代码检测系统的设计与测试[D];北京邮电大学;2012年

8 刘杰;云环境下网络深度包分析技术研究[D];北京邮电大学;2012年

9 张洁坤;时空高效的正则表达式匹配算法研究[D];湖南大学;2010年

10 金军航;面向深度包检测的存储高效的正则表达式匹配算法研究[D];湖南大学;2010年

【二级参考文献】

中国期刊全文数据库 前6条

1 陈曙晖;苏金树;范慧萍;侯婕;;一种基于深度报文检测的FSM状态表压缩技术[J];计算机研究与发展;2008年08期

2 曹京;谭建龙;刘萍;郭莉;;布尔表达式匹配问题研究[J];计算机应用研究;2007年09期

3 黄昆;张大方;谢高岗;金军航;;一种面向深度数据包检测的紧凑型正则表达式匹配算法[J];中国科学:信息科学;2010年02期

4 李伟男;鄂跃鹏;葛敬国;钱华林;;多模式匹配算法及硬件实现[J];软件学报;2006年12期

5 徐乾;鄂跃鹏;葛敬国;钱华林;;深度包检测中一种高效的正则表达式压缩算法[J];软件学报;2009年08期

6 曹京;刘燕兵;刘萍;谭建龙;郭莉;;定序窗口布尔表达式匹配技术研究[J];通信学报;2007年12期

【相似文献】

中国期刊全文数据库 前10条

1 鲍丰;关于弱可逆有限自动机延迟步数分解的两个结果[J];计算机学报;1993年08期

2 袁永升;兰亚坤;;有限自动机的逻辑流程图分析法[J];东北师大学报(自然科学版);1993年03期

3 王海峰,吕永波,张仲义;一种系统安全性的形式化验证方法[J];计算机工程与应用;2003年04期

4 王恺,靳简明,王庆人;西文OCR后处理中的有限自动机模型[J];计算机工程与应用;2004年23期

5 周德玉;有限自动机的变换半群和它识别的信息[J];重庆大学学报(自然科学版);1989年01期

6 吴浩敏,陈偕雄;有限自动机〈X,S,Z,F,G〉的一种MSI实现方法[J];浙江大学学报(理学版);1989年02期

7 彭召意,许中华,蒋伟进,杨伟丰;一种基于有限自动机的多线程软件设计方法[J];福建电脑;2004年04期

8 文敦伟,蔡自兴;空调系统多工况智能控制[J];计算技术与自动化;1997年03期

9 朱云飞,张衡,罗铸楷;有限自动机的线性化[J];湘潭大学自然科学学报;1999年01期

10 周晔,黄永忠,郭金庚;类信息的提取技术及应用[J];计算机应用研究;2001年09期

中国重要会议论文全文数据库 前10条

1 黎中文;张来顺;肖健鹏;;改进的UIO序列生成算法[A];计算机研究新进展（2010）——河南省计算机学会2010年学术年会论文集[C];2010年

2 闫继钢;武文忠;李汉文;蒙应杰;是W，

本文编号：481716