基于多维有限自动机的DFA改进算法

发布时间：2017-10-15 14:37

  本文关键词：基于多维有限自动机的DFA改进算法

  更多相关文章： 正则表达式 DFA 有限自动机 状态爆炸

【摘要】：多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA,multi-dimensional finite automata)。实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、m DFA、Hybrid-FA降低了1~2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和m DFA降低了1~2个数量级。
【作者单位】： 国家数字交换系统工程技术研究中心;中国石油大学化工学院;
【关键词】： 正则表达式 DFA 有限自动机 状态爆炸
【基金】：国家高技术研究发展计划(“863”计划)基金资助项目(2011AA01A103,2011AA01A101) 国家重点基础研究发展计划(“973”计划)基金资助项目(2012CB315901,2013CB329104) 国家科技支撑计划基金资助项目(2011BAH19B01)~~
【分类号】：TP301.1;TP393.08
【正文快照】： 1引言近年来,以“棱镜门”为代表的各类监控和攻击事件为各国的网络安全形势敲响了警钟。在网络信息安全领域,入侵检测系统(IDS,intrusion de-tection system)扮演着越来越重要的角色,IDS采用深度分组检测(DPI,deep packet inspection)进行病毒检测、入侵识别、协议分析等,网

【参考文献】

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

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

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

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

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

5 乔登科;王卿;柳厅文;孙永;郭莉;;基于状态分组的高效i-DFA构造技术[J];通信学报;2013年08期

6 贺炜;郭云飞;扈红超;;基于状态约束的大规模正则表达式匹配算法[J];通信学报;2013年10期

【共引文献】

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

1 金学成;孙炜;梁野;郭玉金;谢忠华;;电力二次系统内网安全监视平台的设计和实现[J];电力系统自动化;2011年16期

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

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

4 王奇敏;李训根;赵海斌;;基于FPGA的正则表达式匹配引擎设计[J];电子世界;2013年01期

5 吴君钦;王凯;;面向网络流的正则表达式匹配改进算法[J];电子技术应用;2013年08期

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

7 宫阳阳;刘勤让;邵翔宇;朱圣平;邢池强;彭志彬;贺业里;;基于多维立方体的正则表达式匹配算法[J];电子学报;2014年09期

8 周兴旺;;正则表达式中的与或非解析[J];计算机光盘软件与应用;2014年18期

9 王培凤;李莉;;一种改进的多模式匹配算法在Snort中的应用[J];计算机科学;2012年02期

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

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

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

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

3 胡侃;车身碰撞安全的若干关键技术研究[D];吉林大学;2013年

4 董永吉;面向资源优化的分层式高速报文解析技术研究[D];解放军信息工程大学;2013年

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

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

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

3 田健;IDS中VLDC模式匹配算法的研究与应用[D];吉林大学;2011年

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

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

6 李伦;针对大规模URL关键字的多模匹配算法的性能优化[D];哈尔滨工业大学;2011年

7 仇文娟;云计算中依赖任务动态并行调度机制的研究[D];大连理工大学;2011年

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

9 黄鹏;基于FPGA的高性能模式匹配引擎研究与设计[D];解放军信息工程大学;2011年

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

【二级参考文献】

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

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期

7 柳厅文;孙永;卜东波;郭莉;方滨兴;;正则表达式分组的1/(1-1/k)-近似算法[J];软件学报;2012年09期

【相似文献】

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

1 陈燕敏;邓培民;易忠;;有限自动机矩阵模型的应用——有限自动机r阶输入存贮性质判定新方法[J];计算机工程与应用;2007年29期

2 黄飞丹;蒙春凤;邓培民;易忠;;由单个状态生成的有限自动机的一些性质[J];工程数学学报;2011年01期

3 陈乾;涂道兴;莫智文;;模糊有限自动机的乘积覆盖性[J];模糊系统与数学;2011年02期

4 翁福利;舒兰;王泽文;;直觉模糊有限自动机的乘积[J];模糊系统与数学;2012年04期

5 陶仁骥,陈世华;关于延迟τ步(可)逆有限自动机结构的一些性质[J];计算机学报;1980年04期

6 陈有刚;有限自动机代数及其算法[J];计算机工程与设计;1990年01期

7 黄飞丹;邓培民;易忠;;有限自动机的同态[J];工程数学学报;2014年01期

8 丁春欣;有限自动机的最小化[J];高师理科学刊;2000年03期

9 沈整;函数映射与有限自动机关系及算法探讨[J];西南民族学院学报(自然科学版);2000年02期

10 ;自动化理论与技术[J];电子科技文摘;2003年01期

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

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

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

1 姚刚;有限自动机可逆性的若干结果[D];中国科学院研究生院（软件研究所）;2003年

2 王茂基;混沌同步中信息传递的研究[D];大连理工大学;2011年

3 莫智文;Fuzzy有限态自动机的最小化及其在心电图（ECG）识别中的应用[D];西南交通大学;2005年

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

1 张勇;一类有限自动机及其积的试验序列[D];广西师范大学;2008年

2 吴宗显;概率有限自动机的代数性质[D];广西师范大学;2008年

3 黄飞丹;循环有限自动机和有限自动机的路代数[D];广西师范大学;2008年

4 林添荣;量子有限自动机等价性判定研究[D];福建师范大学;2011年

5 辛公彩;交换幂等半环上的加权有限自动机的确定式[D];湖南科技大学;2007年

6 孙志强;基于半环代数理论的有限自动机的探讨[D];太原科技大学;2009年

7 刘跃霞;语言半环上的有限自动机的推广[D];太原科技大学;2010年

8 陈燕敏;关于矩阵模型表示下有限自动机的讨论[D];广西师范大学;2006年

9 程伟;模糊有限自动机的分类及其状态最小化算法研究[D];四川师范大学;2002年

10 杨楠;矩阵模型在有限自动机上的应用[D];广西师范大学;2007年

，

本文编号：1037676