2022年多模式匹配算法的FPGA实现 .pdf

《2022年多模式匹配算法的FPGA实现 .pdf》由会员分享，可在线阅读，更多相关《2022年多模式匹配算法的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-Corasic

2、k(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 ba

3、sed on software, 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 th

4、e FPGA. Then, it uses 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 数

5、据量爆炸式的增长， 基于软件实现的入侵检测系统IDS 的检查效率已经远远赶不上数据的增长1,2，成为入侵检测技术发展的瓶颈。基于硬件实现的模式匹配算法，其匹配时间仅取决于待匹配的串长度和硬件的工作速度， 可以达到很高的检测速度，从而满足高速网络的实时检测需求3。FPGA 具有可重复烧写的功能，是目前硬件实现入侵检测的主流解决方案。本文针对入侵检测系统中的多模式匹配算法-AC 算法，结合 Altera 公司的 FPGA 产品，在硬件电路上实现 AC 算法，从而大大提高系统检测效率。2AC算法AC 算法是基于有穷状态自动机的， 在进行匹配之前先对模式串集合SP进行预处理，形成树型有穷状态自动机，然

6、后只需对文本串T 扫描一次就可以找出与 基金项目 :浙江省重大科技专项(2007C11069) 收稿日期 :2010-06-23;收到修改稿时间 :2010-08-02 其匹配的所有模式串。图 1he,she,his,her,say的 goto 函数图预处理生成 3 个函数：goto(转移)函数，failure(失效)函数和 output(输出 )函数。设 U=0 ，1，2为状态集合，转移函数的建立过程为： 逐个取出 SP中模式串的每个字符，从状态0 出发，如果有标注该字符的矢线存在，则将矢线所指的状态赋为当前状态；否则，名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

7、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 2011 年 第 20 卷 第 3 期http:/www.c-s- 计 算 机 系 统 应 用Research and Development 研究开发91添加一个标号比已有状态标号大1 的新状态，并用一条矢线从当前状态指向新加入的状态，并将新加入的状态赋为当前状态。最后，画一条从0 状态到 0 状态的自返线。 SP= he,she,his,her,say 的 goto函数如图 1所示。失效函数f 构造方法为：所有第一层状态的失效函数为0；对于非第一层

8、状态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 。具体的失效函数如图2(a)所示。输出函数 output 的构造分两步，第一步是在构造转移函数 g 时，每处理完一个模式串，则将该模式串加 入 到 当 前 状 态s的 输 出 函 数 中 ， 如output(2)=he,output(5)=she 。第二步是构造失效函数 f 时，若 f(s)=s,则 output(s

9、)=output(s)output(s),如 output(5)=output(5)output(2)=she,he。具体的输出函数如下图 2(b)所示: (a)失效函数图(b)输出函数图图 2失效函数图与输出函数图AC 算法实现如下： 从状态 0 出发，每取出文本串中的一个字符，利用g 和 f 函数进入下一状态。当某个状态的 output 函数不为空时输出其值，表示在文本串中找到该模式串。AC 算法模式匹配的时间复杂度是O(n)，与模式集中模式串的个数和模式串的长度无关。3硬件实现根据 AC 算法的原理，利用verilog hdl 语言构建FSA，在硬件上设计和实现AC 算法的功能。采用可编

10、程逻辑器件 FPGA 来实现算法，系统可靠性高，可维护性好，使用灵活。3.1 设计思路AC算法的核心就是FSM( 有限状态机)的建立，所以硬件设计的核心问题就是如何把状态机固化到FPGA 的片内RAM 当中。由于片内RAM是可寻址的，也就可以把每个状态都划分到片内RAM中 特 定 的地 址 上 。 一个 状 态 占 据 了片 内RAM 中 256 个单元的地址，例如状态0，它的地址就占据了标号为0 到 255 的片内ram 空间。在每个地址中都可以存储相应的数据，包括下一状态的地址 (对应 goto 函数 )，是否有匹配项成功(对应 output 函数 )，如果失败要转到哪个状态(对应fail

11、ure 函数 )等。通过控制逻辑来产生相应的地址和数据的匹配，不占用CPU 的处理时间，大大的提高了数据的处理速度4-6。数据匹配的问题，也是应用RAM 来实现的，每个 FPGA 芯片，都可以搭载外部 RAM 。因为 AC 算法是字符串的匹配方案，所以所有的字符都可以转化为ASCII 码值来进行表示。片内 RAM 中每个状态的地址都是有编号的，每个状态都占据了256 个单元。基于这一点，可以对所要处理的字符串先进行转化，转变成 0，1 表示的字符串。对于0 状态而言，只需要根据输入字符的 ASCII 码值来对应 ram 中地址上的数据，并进行匹配；对于不是0 状态的状态，只需要在输入数据的 A

12、SCII 码值所对应的地址值加上对应的状态数256 就可以进行寻址了。对于具体的控制，需要编写控制逻辑来实现。最后实现的原理图，如图3 所示: 图 3设计原理图3.2 硬件实现步骤通过对 AC 算法的深入研究，并根据FPGA 的特点，提出了原理框图，具体如图4 所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 计 算 机 系 统 应 用http:/www.c-s- 2011 年 第 20 卷 第 3 期92研究开发Resea

13、rch and Development图 4原理框图由图 4可以看出， 整个电路结构主要由 3 部分构成：状态数目和跳转状态的计算，文本匹配和控制逻辑。进行文本匹配时，主串可以先放在寄存器中，或者外部RAM 中，然后由控制逻辑来读取主串中的字符。 模式串由 FPGA 来控制生成状态机，用于模式的识别。对于控制逻辑，要实现的功能有两点：一是控制地址计数器，供主串读取数据；二是控制设计中的有限状态机的计数器和状态转换，保证有限状态机能够正确工作。3.3 设计实例分析根据上述设计思想，采用verilog hdl 语言设计实现图 4 中的模式匹配电路，开发环境为Altera 公司的Quartus II

14、8.1 ， 目 标 板为 Altera 的cyclone 系 列EP1C6Q240C8型 FPGA，由 Quartus II8.1 对设计实例进行了前仿真、逻辑综合、功能验证和时序验证，并在目标板上进行了功能性验证， 证明了方法的可行性。(1) 用 Quartus II自带的波形仿真器进行波形仿真，输入的 Pattern(模式)为“BOY” ， “GIRAFFE”，待匹配的主串为 BBBOYGIRLBOY，从主串中寻找Pattern可能出现的情况。大约6 个时钟周期以后得到输出，输出标示符为flag，包括初始化的将近2 个时钟周期。当 flag 输出不为 0 时，表明匹配成功。抓取前仿真的波形

15、图如图5 所示。图 5Quartus II 前仿真的波形图(2) 经 Quartus II 布局布线和综合仿真后，进行时序验证，也得到正确的结果，如图6所示。图 6Quartus II 后仿真的波形图3.4 性能总结由于 AC 算法的时间复杂度是O(n)，而且与模式集中模式串的个数和每个模式串的长度无关。即无论模式串 SP是否出现在 T 中， T 中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O(n)。这样，对于模式串超多的模式匹配过程，有很好的检测效率，也就很好的解决了规则集数目呈指数形式发展所带来的影响。由于 AC 算法出色的性能，在短时期

16、内不会处在淘汰的边缘。有以下性能分析，在相同时钟频率，相同模式串长度下，随着模式串长度和个数的增加，比较该模块匹配的时间有何变化。经过时序仿真验证，得出的数据如表 1所示。表 1不同主串长度下的性能分析由表 1 看出，在相同的主串长度下， AC 算法的匹配时间并不随着模式串的改变而改变。与 BM 算法和 KMP 算法进行比较，选取2.46M的英文文本，在其中查找多个模式串，找出所有出现的位置从文本中选取不同长度的模式串，测试在相同模式集和模式长度下算法的性能测试机使用P4电脑，CPU 为 1.8 GHz ，内存 1O G ，操作系统为windows XP，系统工作频率为 50HZ，实验结果如表

17、 2所示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 2011 年 第 20 卷 第 3 期http:/www.c-s- 计 算 机 系 统 应 用Research and Development 研究开发93表 2不同算法的比较结果从表 2 中可以看出，硬件化的AC 算法于其他算法有着非常明显的优势， 并且随着模式串长度的增加，优势更加明显。4结束语本文设计了一个模式匹配的硬件模块，主要应用在网络数据当中的字符串匹配问题上

18、。从性能上看，在 75MHz 时钟频率下仿真，一个时钟就可以匹配一个字符，输出结果完全由主串当中出现的Pattern位置所决定。对于后续的工作，可以再进行代码的优化和硬件产品的升级来提高匹配性能。如把本文中应用的cyclone 系列的 FPGA 换成 cyclone III 系列的 FPGA，再进行布局布线的优化，估计可以很大程度的提高系统性能。参考文献1 邰晓英 .信息检索技术导论.北京 :科学出版社 ,2006.4060. 2 晓妍 ,戴冠中 ,杨黎斌 .改进的多模式字符串匹配算法.计算机应用 ,2007,27(6):14151417. 3 黄栋 ,余综 .模式匹配算法在FPGA 芯片上的

19、设计与实现.计算机工程与设计 ,2006,27(17):32733276. 4 夏宇闻 .Verilog数字系统设计教程.北京 :北京航空航天大学出版社 ,2003:8995. 5 Yu F, Chen Z. Fast and memory efficient regular expression matching for deep packet inspection. Tech Rep: UCB/EECS -2006-76. University of California Berkeley, 2006:93102. 6 郭军 ,笹尾勤 .入侵检测中模式匹配算法的FPGA 实现 .系统仿真学报 ,2007,19(14):32153229. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -