基于状态子集编码的快速DFA构造算法

发布时间：2017-10-16 13:41

  本文关键词：基于状态子集编码的快速DFA构造算法

  更多相关文章： NFA DFA 正则表达式匹配 深度包检测

【摘要】：网络深度包检测等网络应用广泛采用正则表达式匹配技术检测网络中的传输内容,正则表达式用非确定性有限自动机(NFA)或者确定性有限自动机(DFA)实现.网络应用对匹配速度要求很高,相比NFA,DFA具有确定性的匹配速度,但所有基于DFA的方法需要预先从NFA构造一个与之等价的DFA,于是DFA的构造成为系统瓶颈之一.为此通过深入探索自动机内在运行特性———NFA状态间活跃关系和NFA中导致DFA空间膨胀的因素,设计了一种NFA状态子集的编码方法和查询方法,显著减少了DFA构造过程中状态子集的查询代价.基于入侵检测与防护系统Snort中的真实规则集的实验表明,与传统的子集构造算法相比,该方法减少了88.33%~93.57%的DFA构造时间.
【作者单位】： 中国科学技术大学计算机科学与技术学院;
【关键词】： NFA DFA 正则表达式匹配 深度包检测
【基金】：中国科学技术大学博士研究生学术新人项目资助
【分类号】：TP393.08
【正文快照】： 0引言正则表达式匹配(regular expressionmatching)技术是许多网络应用的一项核心基础技术,广泛应用于网络入侵检测与防护、恶意签名匹配、内容过滤、协议分析、基于内容的包转发等领域.该技术将待检测的模式用正则表达式表示,并深入对网络包的载荷进行匹配,以确定该网络包是

【相似文献】

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

1 郑金英;滕春霞;;概念格构造算法的现状与发展前景[J];硅谷;2011年22期

2 林春杰;普杰信;张瑞玲;;近似概念格及其增量构造算法研究[J];计算机应用研究;2012年01期

3 杜秋香;张继福;张素兰;;概念特化的概念格更新构造算法[J];智能系统学报;2008年05期

4 杜秋香;张继福;张素兰;;基于概念提升的概念格更新构造算法[J];太原科技大学学报;2009年01期

5 王欣欣;张素兰;;基于对象扩展的概念格批处理构造算法[J];太原科技大学学报;2009年05期

6 申锦标;吕跃进;;一种新颖的概念格构造算法[J];合肥工业大学学报(自然科学版);2010年02期

7 陈庆燕;崔娟;;概念格构造算法分析[J];福建电脑;2010年08期

8 田宏;王绍斐;;概念格的批处理构造算法[J];大连交通大学学报;2011年03期

9 王鑫;程立民;蒋华;刘建明;;使用选择因子的证书路径构造算法[J];计算机应用研究;2013年04期

10 沈夏炯,韩道军,刘宗田,马骏;概念格构造算法的改进[J];计算机工程与应用;2004年24期

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

1 曲立平;刘大昕;杨静;张万松;;基于属性的概念格快速渐进式构造算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

2 杨本良;;压缩候选的贝叶斯信念网络构造算法[A];广西计算机学会2005年学术年会论文集[C];2005年

3 申锦标;;一种新颖的概念格构造算法[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

4 高茜;周大均;李爱民;;Petri网改进的可覆盖性树的构造算法[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

5 韩锋;张鸿宾;;不连通模型上多尺度Reeb图的构造算法[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

6 汤志钢;胡学钢;简宋全;;量化概念格研究[A];全国第十四届计算机科学及其在仪器仪表中的应用学术交流会论文集[C];2001年

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

1 王绍斐;概念格构造算法的研究及其在本体中的应用[D];大连交通大学;2010年

2 刘晓今;概念三元格构造算法及应用研究[D];西安电子科技大学;2013年

3 吴新荣;全可逆递进网格构造算法研究[D];中南大学;2007年

4 黄永城;基于多核环境的基因贝叶斯网络构造算法研究与实现[D];上海交通大学;2012年

5 刘丹丹;无线传感器网络中拓扑构造算法的研究[D];曲阜师范大学;2014年

6 张海龙;协议缓冲区数据的构造与解析软件设计与实现[D];哈尔滨工业大学;2012年

7 赵男;基于MapReduce的分布式极图构造算法研究[D];北京交通大学;2013年

8 金梁;概念格Chein构造算法的改进[D];河南大学;2008年

9 张赛男;无线网状网络中基于粘液菌算法的子图构造算法的研究[D];北京邮电大学;2014年

10 王玮;概念格分布式构造算法研究[D];太原科技大学;2010年

，

本文编号：1042998