多模式匹配算法的FPGA实现.pdf
《多模式匹配算法的FPGA实现.pdf》由会员分享,可在线阅读,更多相关《多模式匹配算法的FPGA实现.pdf(4页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、计 算 机 系 统 应 用http:/www.c-s- 2011 年 第 20 卷 第 3 期90研究开发Research and Development多模式匹配算法的FPGA 实现孔利峰,李训根,厉海涛(杭州电子科技大学微电子 CAD 研究所,杭州 310018)摘 要:针对目前模式匹配算法多采用软件实现,而软件实现效率低下的弊端,提出了一种基于硬件实现模式匹配算法的设计方案。综合 Aho-Corasick(AC)算法原理和 FPGA 硬件特点,在 FPGA 上实现 AC 算法;然后利用Quartus II 对设计进行了验证和性能分析。实验结果表明,基于硬件实现的Aho-Corasick(
2、AC)算法的效率得到显著提升,有效解决了数据快速增长带来的处理速度缓慢的缺点。关键词:模式匹配算法;现场可编程门阵列;硬件描述语言Implementation of the Pattern Matching Technical on FPGA KONG Li-Feng,LI Xun-Gen,LI Hai-Tao(Institute of ICAD,Hangzhou Diangzi University,Hangzhou 310018,China)Abstract:The pattern matching algorithm was mostly implemented based on sof
3、tware,but software realized of low efficiency,a design was applied to make the pattern matching algorithm implementation on the hardware.This paper combines the principle of the Aho-Corasick(AC)algorithm and the characteristics of FPGA,implements the Aho-Corasick(AC)algorithm on the FPGA.Then,it use
4、s the Quartus II to validation and performance analysis for this design.The test results indicate that the design has high quality and is an effective solution to the fault of slow speed.Keywords:pattern matching algorithm;FPGA;hardware description language 1引 言随着 Internet 数据量爆炸式的增长,基于软件实现的入侵检测系统IDS
5、 的检查效率已经远远赶不上数据的增长1,2,成为入侵检测技术发展的瓶颈。基于硬件实现的模式匹配算法,其匹配时间仅取决于待匹配的串长度和硬件的工作速度,可以达到很高的检测速度,从而满足高速网络的实时检测需求3。FPGA 具有可重复烧写的功能,是目前硬件实现入侵检测的主流解决方案。本文针对入侵检测系统中的多模式匹配算法-AC 算法,结合 Altera 公司的 FPGA 产品,在硬件电路上实现 AC 算法,从而大大提高系统检测效率。2AC算法AC 算法是基于有穷状态自动机的,在进行匹配之前先对模式串集合SP进行预处理,形成树型有穷状态自动机,然后只需对文本串T 扫描一次就可以找出与 基金项目:浙江省
6、重大科技专项(2007C11069)收稿日期:2010-06-23;收到修改稿时间:2010-08-02 其匹配的所有模式串。图 1he,she,his,her,say的 goto 函数图预处理生成 3 个函数:goto(转移)函数,failure(失效)函数和 output(输出)函数。设 U=0,1,2为状态集合,转移函数的建立过程为:逐个取出 SP中模式串的每个字符,从状态0 出发,如果有标注该字符的矢线存在,则将矢线所指的状态赋为当前状态;否则,2011 年 第 20 卷 第 3 期http:/www.c-s- 计 算 机 系 统 应 用Research and Development
7、 研究开发91添加一个标号比已有状态标号大1 的新状态,并用一条矢线从当前状态指向新加入的状态,并将新加入的状态赋为当前状态。最后,画一条从0 状态到 0 状态的自返线。SP=he,she,his,her,say 的 goto函数如图 1所示。失效函数f 构造方法为:所有第一层状态的失效函数为0;对于非第一层状态s,若其父状态为r(即存在字符a,使 g(r,a)=s),则 f(s)=g(f(s*),a),其中状态s*为追溯s 的祖 先状态得到的第一个使g(f(s*),a)存在的状态。如f(4)=g(f(3),h)=g(0,h)=1,f(5)=g(f(4),e)=g(1,e)=2。具体的失效函数
8、如图2(a)所示。输出函数 output 的构造分两步,第一步是在构造转移函数 g 时,每处理完一个模式串,则将该模式串加 入 到 当 前 状 态s的 输 出 函 数 中,如output(2)=he,output(5)=she。第二步是构造失效函数 f 时,若 f(s)=s,则 output(s)=output(s)output(s),如 output(5)=output(5)output(2)=she,he。具体的输出函数如下图 2(b)所示:(a)失效函数图(b)输出函数图图 2失效函数图与输出函数图AC 算法实现如下:从状态 0 出发,每取出文本串中的一个字符,利用g 和 f 函数进入下
9、一状态。当某个状态的 output 函数不为空时输出其值,表示在文本串中找到该模式串。AC 算法模式匹配的时间复杂度是O(n),与模式集中模式串的个数和模式串的长度无关。3硬件实现根据 AC 算法的原理,利用verilog hdl 语言构建FSA,在硬件上设计和实现AC 算法的功能。采用可编程逻辑器件 FPGA 来实现算法,系统可靠性高,可维护性好,使用灵活。3.1 设计思路AC算法的核心就是FSM(有限状态机)的建立,所以硬件设计的核心问题就是如何把状态机固化到FPGA 的片内RAM 当中。由于片内RAM是可寻址的,也就可以把每个状态都划分到片内RAM中 特 定 的 地 址 上。一 个 状
10、态 占 据 了 片 内RAM 中 256 个单元的地址,例如状态0,它的地址就占据了标号为0 到 255 的片内ram 空间。在每个地址中都可以存储相应的数据,包括下一状态的地址(对应 goto 函数),是否有匹配项成功(对应 output 函数),如果失败要转到哪个状态(对应failure 函数)等。通过控制逻辑来产生相应的地址和数据的匹配,不占用CPU 的处理时间,大大的提高了数据的处理速度4-6。数据匹配的问题,也是应用RAM 来实现的,每个 FPGA 芯片,都可以搭载外部 RAM。因为 AC 算法是字符串的匹配方案,所以所有的字符都可以转化为ASCII 码值来进行表示。片内 RAM 中
11、每个状态的地址都是有编号的,每个状态都占据了256 个单元。基于这一点,可以对所要处理的字符串先进行转化,转变成 0,1 表示的字符串。对于0 状态而言,只需要根据输入字符的 ASCII 码值来对应 ram 中地址上的数据,并进行匹配;对于不是0 状态的状态,只需要在输入数据的 ASCII 码值所对应的地址值加上对应的状态数256 就可以进行寻址了。对于具体的控制,需要编写控制逻辑来实现。最后实现的原理图,如图3 所示:图 3设计原理图3.2 硬件实现步骤通过对 AC 算法的深入研究,并根据FPGA 的特点,提出了原理框图,具体如图4 所示。文档编码:CZ2P8R10A9B10 HR7R4T5
12、W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10
13、 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8
14、R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档
15、编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q
16、7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H1
17、0 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7
18、R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10文档编码:CZ2P8R10A9B10 HR7R4T5W6H10 ZN7Y5Q7A7P10计 算 机 系 统 应 用h
19、ttp:/www.c-s- 2011 年 第 20 卷 第 3 期92研究开发Research and Development图 4原理框图由图 4可以看出,整个电路结构主要由 3 部分构成:状态数目和跳转状态的计算,文本匹配和控制逻辑。进行文本匹配时,主串可以先放在寄存器中,或者外部RAM 中,然后由控制逻辑来读取主串中的字符。模式串由 FPGA 来控制生成状态机,用于模式的识别。对于控制逻辑,要实现的功能有两点:一是控制地址计数器,供主串读取数据;二是控制设计中的有限状态机的计数器和状态转换,保证有限状态机能够正确工作。3.3 设计实例分析根据上述设计思想,采用verilog hdl 语言
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模式 匹配 算法 FPGA 实现
限制150内