基于预定义类的紧凑型正则表达式匹配算法

发布时间：2018-07-31 12:28

【摘要】：针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战,结合扩展有限自动机(XFA)正则表达式匹配算法,提出了一种预定义类的压缩自动机匹配算法(Pre-Class CFA)。通过预定义类,算法既可以实现正则表达式中类字符匹配,又能够通过优先级的设定匹配特殊字符集,并在XFA消除确定性有限状态机(DFA)状态爆炸问题的基础上进一步压缩了迁移边数目;同时算法根据现场可编程门阵列(FPGA)和迁移边的特征,设计了一种基于并联只读存储器(ROM)结构的迁移边存取方法,可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2-70上对算法进行测试,实验中系统吞吐量为1.3 Gb/s,可实现千兆网络下的入侵检测和垃圾过滤。
[Abstract]:Aiming at the challenges of hardware regular expression matching algorithm in storage space and throughput, combined with extended finite automata (XFA) regular expression matching algorithm, a predefined class compression automata matching algorithm (Pre-Class CFA).) is proposed. By using predefined classes, the algorithm can not only match class characters in regular expressions, but also match special character sets by setting priority. The number of migration edges is further compressed on the basis of eliminating the (DFA) state explosion problem of deterministic finite state machine by XFA, and the algorithm is based on the characteristics of (FPGA) and migration edge of field programmable gate array. In this paper, a parallel access method based on parallel read-only memory (ROM) architecture is proposed, which can realize parallel reading and matching of multiple migration edges in the same state. The algorithm is tested on the low and low performance FPGA platform ALTERA DE2-70. The system throughput is 1.3 GB / s, which can realize intrusion detection and garbage filtering in gigabit networks.
【作者单位】： 武警工程大学电子技术系;武警部队网络与信息安全保密重点实验室;
【基金】：国家自然科学基金资助项目(61402531) 陕西省自然科学基金资助项目(2014JQ8307,2015JQ6231)~~
【分类号】：TP393.08;TP301.1

【参考文献】

相关期刊论文 前4条

1 褚衍杰;李云照;魏强;;一种改进的多模式匹配算法[J];西安电子科技大学学报;2014年06期

2 嵩天;李冬妮;汪东升;薛一波;;存储有效的多模式匹配算法和体系结构[J];软件学报;2013年07期

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

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

【共引文献】

相关期刊论文 前10条

1 麦涛涛;潘晓中;王亚奇;苏阳;;基于预定义类的紧凑型正则表达式匹配算法[J];计算机应用;2017年02期

2 耿卫江;;基于HoneyGate入侵诱控监测数字化网络平台的设计与实现[J];现代电子技术;2016年20期

3 薛朋强;努尔布力;吾守尔·斯拉木;;基于网络文本信息的敏感信息过滤算法[J];计算机工程与设计;2016年09期

4 王亚南;徐周波;古天龙;;基于OBDD的模式匹配算法硬件实现[J];桂林电子科技大学学报;2016年03期

5 邵翔宇;刘勤让;孙淼;;基于模板有限自动机的正则表达式匹配算法[J];计算机应用研究;2016年07期

6 王磊;孙帆;陈旭东;;RESTFUL、SOAP、ICAP在移动网络中的应用[J];邮电设计技术;2015年09期

7 张晓煜;林晓;王志杰;;面向大数据库正则表达式查询的有效算法[J];河南科技大学学报(自然科学版);2015年04期

8 宫阳阳;刘勤让;杨镇西;邵翔宇;邢池强;焦慧娟;彭志彬;;基于多维有限自动机的DFA改进算法[J];通信学报;2015年05期

9 才让卓玛;李永明;才智杰;;基于Mealy机的藏文字构件分解[J];电子学报;2015年05期

10 褚衍杰;李云照;魏强;;一种改进的多模式匹配算法[J];西安电子科技大学学报;2014年06期

【二级参考文献】

相关期刊论文 前5条

1 嵩天;李冬妮;汪东升;薛一波;;存储有效的多模式匹配算法和体系结构[J];软件学报;2013年07期

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

3 刘卫国;胡勇刚;;DHSWM:一种改进的WM多模式匹配算法[J];中南大学学报(自然科学版);2011年12期

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

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

【相似文献】

相关期刊论文 前10条

1 王甲春;;正则表达式的五个良好习惯[J];中文信息;2003年11期

2 白红哲,马立勇;基于正则表达式的话务报告处理软件的实现[J];通信管理与技术;2005年02期

3 孟岩;;一夫当关——《精通正则表达式》书评[J];程序员;2007年08期

4 ;新书上架[J];程序员;2007年10期

5 路个的;;请个伙伴,助你成长为正则表达式高手[J];电脑爱好者;2008年23期

6 余晟;;正则表达式随笔[J];程序员;2008年03期

7 余晟;;正则表达式随笔(续)[J];程序员;2008年09期

8 周健锋;;正则表达式的强大功能[J];电脑知识与技术;2009年16期

9 夏阳阳;李建华;;新疆勘探生产经营管理系统中正则表达式的应用[J];办公自动化;2009年20期

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

相关会议论文 前4条

1 管杰裕;;正则表达式在气象信息处理中的应用[A];2005年广西气象学会学术年会论文集[C];2005年

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

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

4 田珂;赵国鸿;;利用TCAM与正则表达式对邮件协议进行二次识别的思想研究[A];第十六届计算机工程与工艺年会暨第二届微处理器技术论坛论文集[C];2012年

相关重要报纸文章 前1条

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

相关博士学位论文 前1条

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

相关硕士学位论文 前10条

1 韩家宝;图数据搜索引擎Trinity中正则表达式匹配子系统的设计与实现[D];哈尔滨工业大学;2015年

2 徐成成;基于两级存储的正则表达式匹配技术研究[D];国防科学技术大学;2013年

3 宫阳阳;面向网络安全的多维正则表达式匹配算法研究[D];解放军信息工程大学;2014年

4 邵翔宇;正则表达式匹配存储优化技术研究[D];解放军信息工程大学;2015年

5 历博源;面向网络入侵检测的正则表达式DFA优化技术研究[D];吉林大学;2016年

6 陈航宇;正则表达式匹配算法研究[D];燕山大学;2016年

7 卓艳男;软硬件协同设计的正则表达式匹配技术研究[D];东北石油大学;2016年

8 江彬;基于FPGA的可配置正则表达式匹配引擎的设计[D];东北大学;2014年

9 李哲夫;正则表达式在电信业务处理中的应用研究[D];暨南大学;2008年

10 范慧萍;基于正则表达式的协议识别研究与实现[D];国防科学技术大学;2007年

，

本文编号：2155585