当前位置:主页 > 科技论文 > 计算机论文 >

基于TCAM的高速可扩展的正则表达式匹配技术

发布时间:2018-01-08 15:01

  本文关键词:基于TCAM的高速可扩展的正则表达式匹配技术 出处:《中国科学技术大学》2013年博士论文 论文类型:学位论文


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


【摘要】:正则表达式匹配(Regular expression matching)是很多网络应用(如入侵检测、内容过滤、协议分析等)的核心引擎技术,随着互联网及网络应用的高速发展,对高速可扩展(fast and scalable)的正则表达式匹配的需求越来越大,但多年来如何实现高速可扩展的正则表达式这一难题一直困扰着研究者们。正则表达式用等价的有限自动机表示,包括非确定性有限自动机(non-deterministic finite automaton, NFA)和确定性有限自动机(deterministic finite automaton, DFA)。NFA所需存储空间很小但是匹配速度很慢;DFA由于匹配速度很快使得DFA方法成为了实现正则表达式匹配的普遍选择,但DFA的高匹配速度是以可呈指数膨胀的状态空间为代价的。高速可扩展的正则表达式匹配的终极目标就是实现像DFA一样的高匹配速度,即每匹配一个输入字符只需一次存储访问,并且实现像NFA一样的低存储空间,即所需存储空间随正则表达式规则集呈线性增长。因为三态内容可寻址存储器(ternary content addressable memory, TCAM)具有独特的并行查找、三态存储与模糊匹配的能力,最近研究者们提出了基于TCAM的DFA实现技术。然而,这些方法所需的TCAM条目数仍然高于呈指数增长的DFA状态数,因此其所需的存储空间仍然过于庞大。 本文提出一种基于TCAM的DFA压缩技术,该技术每处理一个输入字符仅需一次简单的TCAM查询,并且将所需的TCAM条目数降低到了DFA状态数以下。本文通过发现和利用NFA与DFA之间存在的结构联系,识别出源自相同NFA状态的DFA状态,这些DFA状态实际上是相同NFA状态在DFA中不同的副本结构。本文为DFA状态设计合适的TCAM编码和TCAM条目压缩算法,得以有效地将DFA中的这些相似的副本结构进行压缩。基于真实规则集的实验结果表明,本文方法所使用的TCAM条目数最多比DFA状态数小两个数量级。 在DFA实现方法之外,本文又提出首个基于TCAM的NFA实现方法,通过合适的TCAM编码,本文的NFA实现方法和DFA实现方法一样,每处理一个字符只需一次TCAM查找。NFA运行时,并非所有的状态都会同时活跃,通过将同时活跃的NFA状态划分到不同分组中进行编码,使得可以用较少的比特数表示一个NFA活跃状态集合。基于NFA活跃状态集的编码和相应的TCAM条目压缩算法,本文的NFA实现方法既具备和DFA完全一样的运行速度,同时所需存储空间又接近与正则表达式规则集大小呈线性增长的NFA大小。基于真实规则集的实验结果表明,相比基于TCAM的DFA实现方法,本文的NFA实现方法能将存储空间和匹配速度均各自减少和提高一个数量级。 此外,本文还设计出一种快速的DFA构造算法,以打破基于DFA的正则表达式匹配方法的一个瓶颈——DFA方法都需要预先从NFA构造一个与之等价的DFA。本文通过深入探索自动机内在运行特性——NFA状态间活跃关系和NFA中导致DFA空间膨胀的因素,设计了一种NFA状态子集的编码方法和查询方法,减少了DFA构造过程中状态子集的查询代价。实验结果表明,与传统的子集构造算法相比,本文的方法减少了88.33%~93.57%的DFA构造时间。
[Abstract]:Regular expression matching is the core engine technology of many network applications ( such as intrusion detection , content filtering , protocol analysis , etc . ) . With the high - speed development of Internet and network applications , the problem of fast and scalable regular expression matching is getting more and more , but how to realize the high - speed scalable regular expression for many years has puzzled researchers . Regular expressions are represented by equivalent finite automata , including non - deterministic finite automata ( NFA ) and deterministic finite automata ( DFA ) . Because the matching speed quickly makes the DFA approach a universal choice to achieve regular expression matching , the high matching speed of DFA is at the expense of state space which can be exponentially expanded . The ultimate goal of high - speed scalable regular expression matching is to realize high matching speed like DFA . In this paper , a kind of DFA compression technique is proposed based on the ternary association of DFA . In this paper , we find and use the structure link between NFA and DFA to identify the states of DFA which originate from the same NFA state . In this paper , we find and use the structure of NFA and DFA . These DFA states effectively compress these similar copy structures in DFA . Based on the experimental results of the real rule set , the results show that the maximum number of entries used in this method is two orders of magnitude smaller than the number of DFA states . In addition to the implementation method of DFA , this paper presents the first method of realizing NFA based on the ternary system , which is based on the NFA active state set . The NFA implementation method is not all the same as DFA . The NFA implementation method is based on NFA active state set and corresponding algorithm of the NFA . The NFA implementation method is based on the NFA active state set and the corresponding algorithm of the regular expression rule set . The NFA implementation method can reduce the storage space and the matching speed by one order of magnitude compared with the method of the regular expression . In addition , a fast DFA construction algorithm is designed to break a bottleneck _ DFA method based on DFA - based regular expression matching method .

【学位授予单位】:中国科学技术大学
【学位级别】:博士
【学位授予年份】:2013
【分类号】:TP333;TP393.08

【相似文献】

相关期刊论文 前10条

1 范新龙;张华;;探讨编程管理网络设备[J];电脑编程技巧与维护;2010年20期

2 张文典;LAG—一个词法分析程序的生成程序[J];小型微型计算机系统;1985年08期

3 Gary Chan;Java咖啡馆(9)——一个压缩归档实用软件[J];电脑爱好者;2004年19期

4 张太芳;;基于正则表达式技术的数据验证及应用[J];甘肃科技纵横;2006年04期

5 项润华;段红勇;柳汉雄;;正则表达式的使用以及在VC6.0的应用[J];洛阳工业高等专科学校学报;2006年05期

6 梁里宁;;正则表达式在SQL Server 2000中的实现与应用[J];科技广场;2008年01期

7 李国晶;王景强;;浅析正则表达式[J];科技资讯;2010年04期

8 刘小平;;在Visual C++ 6.0中使用Boost正则表达式库[J];信息与电脑(理论版);2010年03期

9 张申媛;;正则表达式的实现[J];科技创新导报;2010年20期

10 胡海星;;DEL命令问题——2001年12期编程擂台题解[J];程序员;2002年02期

相关会议论文 前10条

1 王辉;丁明君;杨进;;正则表达式在企业信息管理开发中的应用[A];2010年MIS/S&A学术交流会议论文集(中国造船工程学会学术论文集)[C];2010年

2 曾雨薇;许向众;;基于正则表达式的税源数据解析方案的研究[A];2011高等职业教育电子信息类专业学术暨教学研讨会论文集[C];2011年

3 梁兴开;赵泽茂;黄亮;;Web应用中的ReDoS检测方法研究[A];浙江省电子学会2011学术年会论文集[C];2011年

4 袁真;;构造正则表达式的几种NFA算法的分析和比较[A];2006年全国理论计算机科学学术年会论文集[C];2006年

5 李佳;魏更宇;胡楠;王枞;杨义先;;基于特征自生成的畸形SIP信令检测算法[A];2010通信理论与技术新发展——第十五届全国青年通信学术会议论文集(下册)[C];2010年

6 刘琪;牛文静;;正则表达式在恶意代码动态分析中的应用[A];2009通信理论与技术新发展——第十四届全国青年通信学术会议论文集[C];2009年

7 余刘琅;汪彩萍;程克勤;;基于Snort的检测SQL注入和跨站脚本攻击的正则表达式的探讨[A];中国仪器仪表学会第九届青年学术会议论文集[C];2007年

8 何雪松;;Matlab和C#联合编程在雨滴谱仪数据处理中的应用[A];第十五届全国云降水与人工影响天气科学会议论文集(Ⅱ)[C];2008年

9 王春元;张韬;;一种获取网页主要中文信息的方法[A];全国计算机安全学术交流会论文集(第二十四卷)[C];2009年

10 钟涛;陈群秀;;基于层式有限状态自动机的灾难事件抽取系统[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

相关重要报纸文章 前10条

1 彭福祥 张钧;ASP.NET基本数值处理技巧[N];计算机世界;2006年

2 ;在论坛中自动显示超链接[N];计算机世界;2006年

3 清水编译;Apache 2.2.0带来了什么?[N];计算机世界;2006年

4 广东 子衿;认识Linux中的符号[N];电脑报;2004年

5 ;软件组[N];计算机世界;2004年

6 ;专用的平台 玛赛反垃圾邮件网关(ASMG)[N];网络世界;2002年

7 湖南 刘靓;软件水平考试备考宝典[N];中国电脑教育报;2004年

8 美国Watchfire公司战略研究总监 Danny ALLAN;应用扫描:从源头加固Web应用安全[N];中国计算机报;2007年

9 吴征;让Google为动态页面的站点服务[N];计算机世界;2004年

10 ;安氏实时监控入侵者[N];中国计算机报;2001年

相关博士学位论文 前10条

1 陈曙晖;基于内容分析的高速网络协议识别技术研究[D];国防科学技术大学;2007年

2 姜鲲鹏;高速串模式匹配算法研究[D];解放军信息工程大学;2012年

3 胡圣明;基于内存自动机与模式的动态引擎构造技术研究[D];西安电子科技大学;2009年

4 徐建国;网络化制造系统中虚拟加工若干关键技术研究[D];南京理工大学;2007年

5 彭坤杨;基于TCAM的高速可扩展的正则表达式匹配技术[D];中国科学技术大学;2013年

6 钱忠胜;基于模型的Web应用测试用例生成方法[D];上海大学;2008年

7 黄昆;高性能内容过滤与分发技术研究[D];湖南大学;2009年

8 胡燕;基于Web信息抽取的专业知识获取方法研究[D];武汉理工大学;2007年

9 孔宁;物联网资源寻址关键技术研究[D];中国科学院研究生院(计算机网络信息中心);2008年

10 孙伟;XML数据库查询优化及相关技术研究[D];哈尔滨工程大学;2006年

相关硕士学位论文 前10条

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

2 王飞龙;PBE技术在文本搜索中的应用[D];哈尔滨理工大学;2007年

3 刘俊超;基于正则表达式的应用层协议识别技术研究[D];国防科学技术大学;2008年

4 温源;基于FPGA的正则表达式匹配引擎的设计[D];哈尔滨工程大学;2009年

5 刘子乾;基于攻击模式的系统漏洞检测工具的设计与实现[D];天津大学;2008年

6 刘一兰;基于SNMP MIB编译器的实现及其生成器技术的研究[D];华中师范大学;2004年

7 杨琨;反垃圾邮件技术研究及应用[D];四川大学;2005年

8 王小朋;基于代理的元搜索引擎的研究[D];辽宁工程技术大学;2005年

9 吴蓓;LINUX环境下IDS与防火墙联动系统的设计与实现[D];四川师范大学;2008年

10 张娜;基于正则表达式的深度包检测研究[D];华东师范大学;2007年



本文编号:1397560

资料下载
论文发表

本文链接:https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/1397560.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户549fe***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com