APP下载

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

2017-04-20麦涛涛潘晓中王亚奇

计算机应用 2017年2期
关键词:规则

麦涛涛,潘晓中,王亚奇,苏 阳

(1.武警工程大学 电子技术系,西安 710086; 2.武警部队网络与信息安全保密重点实验室,西安 710086)

(*通信作者电子邮箱wj_maitao@126.com)

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

麦涛涛1,2*,潘晓中1,2,王亚奇1,2,苏 阳1,2

(1.武警工程大学 电子技术系,西安 710086; 2.武警部队网络与信息安全保密重点实验室,西安 710086)

(*通信作者电子邮箱wj_maitao@126.com)

针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战,结合扩展有限自动机(XFA)正则表达式匹配算法,提出了一种预定义类的压缩自动机匹配算法(Pre-Class CFA)。通过预定义类,算法既可以实现正则表达式中类字符匹配,又能够通过优先级的设定匹配特殊字符集,并在XFA消除确定性有限状态机(DFA)状态爆炸问题的基础上进一步压缩了迁移边数目;同时算法根据现场可编程门阵列(FPGA)和迁移边的特征,设计了一种基于并联只读存储器(ROM)结构的迁移边存取方法,可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2- 70上对算法进行测试,实验中系统吞吐量为1.3 Gb/s,可实现千兆网络下的入侵检测和垃圾过滤。

正则表达式匹配;扩展有限自动机;现场可编程门阵列

0 引言

随着海量信息处理和大数据处理等技术的发展,网络应用对海量信息下匹配引擎的性能提出了更高的要求[1]。深度包过滤(Deep Packet Inspection, DPI)技术作为网络过滤系统的核心,采用特征匹配算法将数据包中的数据与预定义的恶意数据特征码进行匹配,从而滤除恶意数据包。……

登录APP查看全文

猜你喜欢

规则
拼写规则歌
撑竿跳规则的制定
数独的规则和演变
依据规则的推理
善用首次销售规则
规则的正确打开方式
颠覆传统规则
让规则不规则
TPP反腐败规则对我国的启示
啦啦操2010—2013版与2013—2016版规则的对比分析