《多模式匹配算法及硬件实现.pdf》由会员分享，可在线阅读，更多相关《多模式匹配算法及硬件实现.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、ISSN 1000-9825,CODEN RUXUEW E-mail: Journal of Software,Vol.17,No.12,December 2006,pp.24032415 http:/ DOI:10.1360/jos172403 Tel/Fax:+86-10-62562563 2006 by Journal of Software.All rights reserved.多模式匹配算法及硬件实现 李伟男1,2+,鄂跃鹏1,2,葛敬国1,钱华林1 1(中国科学院 计算机网络信息中心,北京 100080)2(中国科学院 研究生院,北京 100049)Multi-Pattern M
2、atching Algorithms and Hardware Based Implementation LI Wei-Nan1,2+,E Yue-Peng1,2,GE Jing-Guo1,QIAN Hua-Lin1 1(Computer Network Information Center,The Chinese Academy of Sciences,Beijing 100080,China)2(Graduate School,The Chinese Academy of Sciences,Beijing 100049,China)+Corresponding author:Phn:+86
3、-10-58812364,Fax:+86-10-58812306,E-mail:,http:/ Li WN,E YP,Ge JG,Qian HL.Multi-Pattern matching algorithms and hardware based implementation.Journal of Software,2006,17(12):24032415.http:/ Abstract:This paper surveys the algorithms and hardware implementations of the multi-pattern matching.Firstly,t
4、wo commonly used multi-pattern algorithms,Aho-Corasicks automata based algorithm and Wu-Manbers hash based suffix matching with skipping algorithm are introduced.And then,some improving ways are referred.Next,time and space complexity of these algorithms are analyzed,and the experimental results sho
5、w their performances.Further,several hardware based implementations are taken as examples to demonstrate the general methods and strategies for the implementation on hardware.The developing trend is predicted in the end.Key words:multi-pattern matching;Aho-Corasick algorithm;finite state automata;Wu
6、-Manber algorithm;FPGA (field programmable gate array);TCAM(ternary content addressable memory);bloom filter 摘 要:介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法Aho-Corasick基于自动机的算法和 Wu-Manber 基于 hash 的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.关键词:多模式匹配;
7、Aho-Corasick 算法;有限状态自动机;Wu-Manber 算法;FPGA(现场可编程门阵列);TCAM(三态内容寻址存储器);bloom filter 中图法分类号:TP301 文献标识码:A 模式匹配问题是计算机科学中的一个基本问题,其研究内容在信息检索、模式识别等众多领域均有重要价值,在拼写检查、语言翻译、数据压缩、搜索引擎、入侵检测、内容过滤、计算机病毒特征码匹配以及基因序列比较等应用中起着重要的作用.模式匹配按照匹配模式的数目分为单模式匹配和多模式匹配两类.最初的单 Supported by the National Natural Science Foundation of
8、 China under Grant No.90412011(国家自然科学基金);the Special Foundation of President of the Chinese Academy of Sciences under Grant No.KGCX2-YW-106(中国科学院院长基金)Received 2006-05-16;Accepted 2006-08-18 2404 Journal of Software 软件学报 Vol.17,No.12,December 2006 模式匹配 KMP 算法、Commentz-Walter 算法以及 Boyer-Moore 算法等为后来多模
9、式的发展提供了一些借鉴与启发.因为多模式匹配通过一次扫描可以找到多个模式的所有出现,较之于单模式匹配实现复杂,应用范围也更广泛,所以本文主要围绕多模式匹配来展开.1 概 述 设集合 P=p1,p2,pk是一组模式的集合,每个模式 pi由来源于字符集合的字符串组成.给定长度为 n 的文本串 T=T1n,文本串的每个字符也来源于字符集集合.多模式匹配就是在文本 T 中找出模式集合 P 中的每个模式的所有出现.Aho 和 Corasick 于 1975 年最早提出了基于自动机的多模式匹配算法1,随后,围绕这一算法,一些改进的算法被提了出来,比如压缩存储空间基于位图的算法2、反向构建自动机引入跳跃的启
10、发式方法3等.而 Wu 和Manber 于 1994 年提出了采用 hash 方法的基于后缀匹配方法,同时采用移位来加速比较4,5.这两种方法是当前主流的软件实现的多模式匹配算法,本文主要介绍这两种基本算法及其相关的改进.随着各种新的应用的出现,基于软件的实现已经不能充分满足对匹配速度日益增长的需求,因此,基于硬件的多模式匹配的实现逐渐出现,并成为当前的研究热点.本文后面以 3 个具体的实现为例,介绍了基于硬件的实现方法和策略.本文第 2 节首先介绍基本的 Aho-Corasick 算法,而后依次介绍 3 种基于它的改进算法.第 3 节介绍Wu-Manber 算法.第 4 节给出实验数据,比较
11、上述算法的性能.第 5 节给出多模式匹配的一些硬件实现方法策略以及具体的实现.最后对多模式匹配的发展趋势进行了展望.2 Aho-Corasick 算法 2.1 基本的Aho-Corasick算法 Aho-Corasick 算法1是基于有穷状态自动机的,在进行匹配之前,先对模式串集合进行预处理,构建树型有限状态自动机 FSA(finite state automata),然后,依据该 FSA,只需对文本串 T 扫描一次就可以找出与其匹配的所有模式串.预处理生成 3 个函数:goto(转移)函数、failure(失效)函数和 output(输出)函数.转移函数 goto 表明,在当前状态下读入下一
12、个待比较文本的字符后到达的下一个状态.失效函数 failure 用来指明在某个状态下,当读入的字符不匹配时应转移到的下一个状态.输出函数 output 的作用是,在匹配过程中,当出现匹配时输出匹配到的模式.Aho-Corasick 算法的匹配过程是:从初始状态 0 出发,每次取出文本串中的一个字符,根据当前的状态和扫描到的字符,利用 goto 或 failure 函数进入下一状态.当某个状态的 output 函数不为空时,表明达到该状态时找到了匹配的模式,于是输出其值.下面首先介绍 3 个预处理函数的构建.为了构造 goto 函数,首先要根据模式构建 goto 图,设置一个初始状态0,然后依次
13、扫描各个模式,根据模式逐步为这个图添加新的边和顶点,构造出自动机:从状态 0 出发,由当前状态和读到的下一个字符决定下一状态.如果有从当前状态出发并标注该字符的矢线,则将矢线所指的状态赋为当前状态;否则,添加一个标号比已有状态标号大 1 的新状态,并用一条矢线从当前状态指向新加入的状态,并将新加入的状态赋为当前状态;所有模式串处理完毕后,再画一条 0 状态的自返矢线,标注的字符为不能从 0 开始的字符集.这样,每个模式都可以由一条从初始状态出发的路径标识出来.对模式串集合she,he,hers,his构建的goto 图如图 1 所示.失效函数 f 是逐层构造的,设某个状态的层深度为初始状态到该
14、状态的最短路径长度.令第 1 层状态的failure 函数值为 0,如 f(1)=f(3)=0;对于非第 1 层状态 s,若其父状态为 r,即存在字符 a 使 g(r,a)=s(这里,s 的层深度比 r 少 1),则 f(s)=g(f(s*),a),其中,状态 s*为追溯 s 的祖先状态得到的第 1 个使 g(f(s*),a)存在的状态,如 f(4)=g(f(3),h)=g(0,h)=1,f(5)=g(f(4),e)=g(1,e)=2.输出函数 output的作用是在匹配过程中输出匹配到的模式串.output的构造分两步:第1步是在构造转移函 李伟男 等:多模式匹配算法及硬件实现 2405 数
15、 g 时,每处理完一个模式串,则将该模式串加入到当前状态 s 的输出函数中,如 output(2)=he,output(5)=she.第 2步是在构造失效函数 f时,若f(s)=s,则 output(s)=output(s)output(s),如 output(5)=output(5)output(2)=she,he.Fig.1 The goto graph for the Aho-Corasic algorithm h erssihs e501 2863 74NOT h,s 9 图 1 依据 Aho-Corasick 算法构建的 goto 图 构造完 3 个函数以后,就可以依次扫描文本,逐个
16、读取输入字符.从状态 0 开始,根据当前状态和输入的字符,采用 goto 和 failure 函数转移到下一个状态,当到达状态的 output 函数不空时输出匹配模式.Aho-Corasick 算法模式匹配的时间复杂度是 O(n),而且与模式集中模式串的个数和每个模式串的长度无关.无论模式串 P 是否出现在 T 中,T 中的每个字符都必须输入状态机中,所以,无论是在最好情况还是最坏情况下,Aho-Corasick 算法模式匹配的时间复杂度都是 O(n).包括预处理时间在内,Aho-Corasick 算法总时间复杂度是 O(M+n),其中,M 为所有模式串的长度总和.2.2 基于Aho-Cora
17、sick算法的改进方法 2.2.1 去掉 failure 函数的改进 Aho-Corasick 算法 基于基本 Aho-Corasick 算法,通过修改转移函数,可以去掉 failure 函数,将其合并到 goto 函数中.这样,在对文本进行匹配的过程中,对于每个输入字符仅进行一次状态转移,而不必在调用 goto 函数失败的情况下,再去通过 failure 函数进行状态转移.对于长度为 d 的字符串,最坏情况可能进行 d1 次 failure 转移.文献1在给出基本A-C 实现后,提出了改进的方式,通过合并 failure 函数和 goto 函数,构建 next_move 函数.如果 g(s,
18、a)!=failure,那么 g(s,a)=(s,a);否则,(s,a)=(f(s),a).这样,整个转移过程就只根据函数进行.利用这个确定的有穷自动机(DFA)可以减少状态转移的次数,使得效率得到一定程度的提高.2.2.2 位图压缩的 Aho-Corasick 算法 对于 goto 函数的存储,基本 A-C 算法采用二维数组,然而,实际上,这个数组的很多元素是空的,因为每个状态的下一个有效转移状态通常是很少的几个,这样就浪费了大量的存储空间.假设字符集大小为 256,为了节约空间,仅仅为每个状态保存指向第一个下一个有效状态的指针以及 256 比特的位图,用以指示读入哪些字符可以跳转到下一个有
19、效状态,哪些导致失效.这里,每一个比特位对应一个输入的字符,如果输入相应的字符能够跳转到下一个有效状态,那么该位置“1”,否则置“0”.而对于所有指向有效的下一个状态的指针,采用连续的地址空间存储,这样,只要找到了第 1 个有效状态,再根据位图信息就可以找出对应的有效状态相对于第 1 个有效状态的偏移,于是就能够找到对应状态的指针,这就是基于位图压缩的 A-C 算法2.图 2 给出了表示每个状态的存储结构.failptr 指向当前匹配失效情况下应该转移到的下一个状态,功能上相当于原来的 failure 函数.patternptr 指向到达当前状态时匹配出的模式串,功能上相当于原来的 outpu
20、t 函数.nextptr 指向第 1 个下一个有效状态 1st valid state(所有的有效状态:1st valid state,2nd valid state,3rd valid state,在内存连续空间中存储).bitmap 位图每位标识一个字符,指示输入该字符能否达到有效状态.对于每次查询,首先根据位图判断当前状态下,读入的字符是否能够产生有效的状态转移,这里是通过测试 2406 Journal of Software 软件学报 Vol.17,No.12,December 2006 位图中该字符对应的比特位是否为“1”来实现的.如果为“0”表明失效,则通过 failptr 指针实
21、现失效状态下的转移;否则,计算该字符对应的转移状态前面还有多少个有效状态,这里就是计算位图中该字符对应的比特位之前还有多少个“1”,从而获得偏移量.由于有效状态是连续存储的,通过将偏移量加上第 1 个有效状态的地址,就能够找到当读入当前字符时,应该转到的下一个有效状态.3rd valid state 2nd valid state 1st valid state Pattern2Pattern1Bitmap NextptrPatternptr FailptrFig.2 The storage structure of each state in the bitmap based A-C alg
22、orithm 图 2 位图压缩 A-C 算法中的每个状态的存储结构 该算法压缩了存储空间,在指针长度为 32bit 的机器上,当字符集大小为 256 时,那么,位图占 32 字节,每个状态存储需要 44 字节的空间;而基本的 Aho-Corasick 算法每个状态需要存储对于所有字符所转移到的下一个状态,则需要 4256 字节的存储空间.即便考虑到位图压缩算法中为存储所有下一个有效状态提供的额外开销,存储空间的压缩也是相当可观的.但是,计算状态转移的过程引入了额外的开销,包括对于位图的测试以及计算 偏移.2.2.3 王方法 王永成等人3通过构建 goto 函数以及 skip 函数协助实现模式匹
23、配.该算法对于模式采取从右向左进行比较,在一般情况下,该算法不需要匹配目标文本串中的每个字符,并充分利用了匹配过程中本次匹配不成功的信息,采用“坏字符”启发式规则,跳过尽可能多的字符,加快处理速度.下面介绍两个主要的函数 goto 和 skip 的构造.对于 goto 函数的构造,与基本的 Aho-Corasick 算法类似,也是设初始状态为 0,因为算法是从右向左进行模式比较,进行逆向匹配,所以采用从后向前扫描模式串,构建逆向自动机,图 3 给出了对于模式串集合为her,where,redo构建出的 goto 图.owerehe r876NOTr,e,o5r12ed 10 1194 32 1
24、0hFig.3 The reversely constructed goto graph 图 3 反向构建的 goto 图 skip 函数是用来依据当前字符判断向后可以跳过扫描的字符数目.这里,假设模式集合中最短模式的长度为 minlen,那么+0 so move right immediately m SHIFTh B m Fig.4 Wu-Manber algorithm searching for match progress 图 4 Wu-Manber 算法的扫描匹配 Wu-Manber 算法的时间复杂度平均情况是 O(BN/m).B 是块字符的长度,而 N 是文本的长度,m 是模式的
25、最短长度.该算法对最短模式长度敏感,SHIFT 函数的最大值受最短模式长度的限制,如果最短模式长度很短,则移位的值不可能很大,因此对匹配过程的加速有限.4 实现的分析以及实验数据比较 4.1 预处理复杂度分析 上述这些算法都要进行预处理,生成相关的函数和表,可以在匹配之前独立完成.尽管它们的执行效率不影响匹配的速度,但它们也会占用一些资源,因此,我们先讨论一下各种算法的预处理的复杂度.对于基本的Aho-Corasick 算法,生成 goto 函数需要扫描所有模式的每个字符,所以,时间复杂度随着所有模式的总长度线性增加;而 failure 函数的生成时间也与所有模式的总长度成正比;output
26、函数在 goto 和 failure 函数中各生成了一部分,如果用链接表存放匹配的模式,那么,failure函数添加匹配模式时只需要常数时间,因此,整个 output函数的构造时间也是由所有模式的总长度决定的.而去掉了 failure 函数的 A-C 算法,基于位图压缩的 A-C 算法都需要利用基本 A-C 算法生成的 3 个函数,时间复杂度与基本 A-C 算法相同.Wang 方法逆向构建状态机,其 goto 函数的时间复杂度是与基本 A-C 算法相同的,但是它没有 failure 函数,取而代之的是 skip 函数,而 skip 函数的构造需要扫描所有的模式,从而获得所有字符的skip值,因
27、此,其时间复杂度随着所有模式的总长度而呈线性增加.对于Wu-Manber 算法,SHIFT 表的构建需要扫描模式的每个 B 块,因而需要计算 hash 值获得表的入口偏移,并判断读入该块时可以产生的移位数目,每个模式需要计算 mB+1 次,设有 k 个模式,则总共需要计算(mB+1)k 次;HASH 表里的模式链表每个表项放的是后 B 位 hash 值相同的模式,这个 hash 计算可以合并到上面 SHIFT 表的构建中,而每个模式的前缀 B的计算,如果令 B=B,则也可以在计算 SHIFT 表的同时获得每个模式的前缀,这样,整个预处理的时间复杂度受模式数目、最短模式长度和选取的每次匹配块大小
28、的影响.下面讨论空间的复杂度,对于基本 Aho-Corasick 算法,goto 函数的存放可以是一个由状态和输入字符构成的二维数组,但是当状态集和字符集很大的时候,因为有效转移状态有限,二维数组存储会浪费很多存储空间存 李伟男 等:多模式匹配算法及硬件实现 2409 放失效标记,所以,可以把非失效状态的转移用线性表存储起来,能够有效节省存储空间.而折衷的方案是:将频繁出现的状态(比如状态 0)存放在能通过输入字符和当前状态直接索引到的表中,以获取对这样的状态转换的常数访问时间,而将其他出现不频繁状态的状态转换放到线性表中.Failure 函数的存放可以采取一维数组,这样获取每个状态的 fai
29、lure 值的时间是常数.状态对应输出模式通常用链表连接起来,通常情况下,一个状态最多只有一个输出,但最坏情况是某个状态的输出为所有的模式.对于 output 函数,所需要的总存储空间通常就是所有模式的存储空间.去掉了 failure 函数的 A-C 算法,仅仅在 goto 函数上与基本的算法有区别,由于每个状态对于每个输入都有下一个有效状态,所以采用由状态和输入字符构成的二维数组存放其改进后的 goto 函数.而 Wang方法和基本 A-C 算法的 goto 函数存储方式基本相同,skip 表采用一维数组,大小为字符集的大小.基于位图压缩的 A-C 算法,前文已经分析过了存储格式、每个状态包
30、含失效时的下一个状态指针、第 1 个有效状态指针、状态位图以及对应模式的指针.Wu-Manber 中的 SHIFT 表和 HASH 表如果采用无冲突的 hash 生成表项索引,均至少需要|B个表项,而 HASH 表项指向所有的 k 个模式,这些模式的存储空间和所有模式的总长度成正比,同时,还有每个模式的前缀长度需要存储在 PREFIX 表中.4.2 算法的实现和结果分析 对上述的这些算法进行实验测试,选取人民日报2003 年前 4 个月的内容共计 21MB 的文本数据,在其中查找多个模式串,找到每个模式在文本中的所有出现.对于遇到的匹配模式,将对应的计数器加 1,除此外不再做任何其他处理.分析
31、模式长度变化和模式集合大小变化的情况下,各种算法的执行时间.预处理阶段在匹配之前完成,未包含在执行时间的统计中,统计只包含文本扫描匹配和计数的时间.设输入字符集合是值为 0255 的ASCII 字符.对于每一个汉字,将其识别为两个 ASCII 字符.实验运行于 Linux 平台,内核版本 2.4.20,CPU 为 Intel Pentium 4,2.8GHz,内存容量 512MB,所有算法均采用 C 来实现.以下用 AC 代表基本的 Aho-Corasick 算法,AC-Nofailure 代表去掉了 failure 函数的 Aho-Corasick 算法,AC-BM 代表基于位图压缩的 Ah
32、o-Corasick 算法,WANG 代表王永成等人的算法,WM 代表 Wu-Manber 算法.4.2.1 基于位图压缩的 A-C 算法实现的优化 对于基于位图压缩的 A-C 算法,我们这里采用优化策略来提高匹配的速度.根据前面的介绍可知:由于 A-C算法自身的特性,初始的 0 状态对于每个输入字符、转移函数 goto 都有有效输出要么跳转到下一个状态,要么返回到自身.这样,在位图压缩的 A-C 算法中,0 状态情况下,每个读入字符都能产生有效转移,从而不用测试位图字段中相应位是否置“1”,也不用计算当前状态前面还有多少个有效状态,而可以直接依据输入的字符对应的 ASCII 码作为偏移,再加
33、上第 1 个有效状态指向的地址,就能找到下一个状态的指针,从而减少计算开销.因为 0 状态在匹配过程中是出现得非常频繁的状态,所以,提高 0 状态下状态转换的性能能够在很大程度上提高整体匹配性能.表 1给出了待匹配模式数目为 10的情况下,优化前后的位图压缩的 A-C算法性能的比较.由此可以看出,优化以后,性能提升非常显著.Table 1 Execution time of the basic bitmap A-C and optimized bitmap A-C(s)表 1 优化前后位图压缩的 A-C 算法执行时间(秒)AC_BM 34.12 Opt_AC_BM 1.95 4.2.2 模式数
34、目和长度变化对算法的影响 对于模式数目不同的情况,表 2 给出了各种算法的性能比较.由于对遇到的每个匹配我们都将相应的计数器加 1,所以应该考虑模式数目的增加会带来相应的开销.AC 算法在匹配失效时会执行 failure 函数向前返回,多次执行 failure 会带来性能的下降.而去掉了 failure 函数的 AC 算法,没有了 failure 函数的执行,读入每个输入都能转移到下一个有效状态,匹配的执行时间只与文本长度有关,而与模式数目和长度没有关系.Wang 方法由于引入了启发式思想,不必扫描文本中的每个字符,能够跳过一些不可能匹配的字符,因此在性能上比其他方法都优越.Wu-Manber
35、 方法也引入了启发式方法,跳过不可能匹配的字符,但是由于用到了 hash 函数,增加了一定 2410 Journal of Software 软件学报 Vol.17,No.12,December 2006 的计算复杂性,而且即便 hash 值相同,还要进一步对模式逐字比较进行完全匹配,因而带来了一定的开销.Table 2 Execution time of all the multi-pattern matching algorithms(s)表 2 算法在不同模式数目下的执行时间(秒)AlgorithmPattern number 10 25 50 75 AC 0.47 0.57 0.64
36、0.67 AC_Nofailure 0.36 0.36 0.38 0.38 Opt_AC_BM 1.95 2.92 5.13 6.37 WANG 0.16 0.18 0.24 0.27 Wu-Manber 0.26 0.27 0.51 0.53 Wang 方法和 Wu-Manber 方法都是对最短字符长度敏感的,最短字符长度决定了它们可以跳过的字符的最大距离.所以,如果最短字符长度越短,则它们的性能就越差.表 3 给出了模式数目始终为 10、最短字符长度不同时,算法执行时间的比较.可以看出:AC-Nofailure 对最短模式长度不敏感;而 Wang 算法和 Wu-Manber 算法都因为最短
37、模式长度变短,性能逐步下降,所以,它们适合于最短模式长度较大的情况.Table 3 Execution time for the algorithms under different shortest patterns length(s)表 3 算法在不同最短模式长度下的执行时间(秒)AlgorithmLength of the shortest pattern 2 4 6 8 AC_Nofailure 0.35 0.36 0.37 0.37 WANG 0.21 0.15 0.13 0.12 Wu-Manber 0.46 0.25 0.19 0.16 5 硬件实现 在通用处理器上,软件实现的多
38、模式匹配吞吐量通常最快只能达到 100Kbps 左右,其性能速度已不能充分满足日益增长的应用需求.网络安全设备执行如入侵检测、内容过滤等功能要求数据包达到G比特的扫描速度,而以 FPGA,Bloom filter,TCAM 等为代表的硬件设备是用于构建专用的高速并行处理系统的首选.一些基于 FPGA 的技术利用片上逻辑资源将模式集合编译成状态机,用于模式的识别68,但是,这样会很快耗尽存储资源,单纯的基于 FPGA 的技术不能存储大规模的模式.FPGA 外加嵌入式存储器或者 ROM 的技术则可以满足大规模模式集合的情况911,而且存储器价格便宜.但是,基于存储器的设计访问延迟是潜在的性能瓶颈.
39、基于 Bloom filter的方法1214采用了片上存储器和片外存储器相结合的方式,能够实现高速环境下对大量字符串的扫描,先利用片上的 Bloom filter 判定是否可能产生匹配,只有在可能的情况下才访问延迟高的片外存储器,从而提高了扫描效率.TCAM 由于其自身特性,通过将各个模式保存在每个表项中,每个时钟周期就可以实现对多个模式的并行查询,但是,基于 TCAM 的实现15对于长模式需要多步处理,而且器件成本较高、功耗大.各种器件各有优缺点,即便是选取相同的器件,因为实现的方法不同,达到的速率也不一样.实现过程中通常采用下面的方法和策略:1)模式或表达式转化为自动机(NFA 或 DFA
40、),用于 FPGA 实现68.但是,因为每次比较一个字符并行性不好,只能采用多个子系统同时比较,并行的粒度很大,而且自动机状态转换受到所使用的组合逻辑的执行频率所限制,执行的速度不可能太高;2)预编码技术16,17能够更好地实现逻辑共享,使得相同的字符、字符串可以共享一个逻辑部件,减少逻辑器件的使用,但是预处理工作较为复杂;3)Hash 方法12,14,18避免了逐个比较所有可能的匹配,通过过滤掉不可能的匹配,能进一步缩小比较范围,减少访问和比较次数,加速匹配.往往在一个具体的实现中同时会用到多种方法,以期达到高速度、低成本,模式集合更新简便、快速等目的.下面分别介绍当前的结合 ROM 和存储
41、器的 FPGA 实现方案,基于 Bloom filter 的改良的自动机实现方案和基于 TCAM 的实现方案.李伟男 等:多模式匹配算法及硬件实现 2411 5.1 结合ROM和存储器的FPGA实现 最初的实现结合了字节比较器(byte comparator)和 ROM9,因为采用了可重写的 ROM 器件存储模式集合,从而减少了用于存储的逻辑器件,降低了器件成本.通过比较器先对字符串前缀部分进行比较,然后依据匹配的结果通过地址生成器找到 ROM 中存放相应后缀的地址,而后将后续字符串送入后缀比较器进行匹配.进一步的改进方案增加了 hash 单元10,这是为了过滤掉部分不可能的匹配,减少比较次数
42、.实现由 hash 函数单元、存储器和离散字符串比较器外加一个移位控制模块构成,如图 5 所示.每个时钟周期,一部分输入字符串送入 hash 单元生成索引值,该索引指向存储器中相应的模式段,然后将获取到的模式段和输入字符串进行比较,如果产生匹配,则将该索引值送到输出,指示产生了一个相关匹配.hash函数的输入字符串最大长度决定了该模式匹配模块可以探测的模式的最短长度,而 hash 得到的索引值的大小,决定了存储器中存放模式的表项的最大数目.Match signal Detected pattern index Comp.Pattern Index ShifterAligned patternM
43、emory Hash Input pattern Fig.5 Pattern detection module 图 5 模式检测模块 Hash 函数的输入可以选取输入串的任意子串,用一个偏移量指明该子串的起始位置,选取方式应尽量减少hash冲突.由于每个模式匹配模块存储的模式数目有限,在模式数目很大的情况下,一个模块不足以解决问题,往往需要有多个模块并行操作,同一个 hash 值要送到每个匹配模块中,从而可能不只产生一个匹配.这种情况只发生在某个模式是另一个模式的前缀的情况下,可以通过优先级的设置首先找到长的匹配.由于存在模式长度的差异,存储器宽度要能存放最大长度的模式,因而会导致存储器的浪费
44、,因为不是每个模式都需要那么大的空间.因此,在存储器宽度一定的情况下,需要将多个模式匹配模块进行串连用于识别超出该宽度的模式.把长模式进行切分,将切分后的子模式放在串联着的几个模式匹配模块中,并添加标记字段标识它们属于哪个长模式.一个有效的切分方式是依据 A-C 算法构造出的压缩路径的模式树1,2,既能减少存储空间,也可以减少匹配过程中潜在的模式数目.对于每次匹配,如果长模式状态机对于输入的字符串产生了匹配,那么会输出期望的后续子模式的索引,使得下一个周期继续比较后续的输入,从而判定是否产生匹配;否则不产生任何输出.实现时可以将当前的模式集合写入 ROM 中,而将增加的模式写入存储器中,降低成
45、本,同时也不失访问速度.对于模式集合更新,不需要重构的其他执行部件都可以采用 FPGA 或 ASIC 实现.由于对于模式规则的更新,不需要对整个设计进行逻辑重构,而仅更新存储器中的内容,所以能够有效提高更新的效率.文献10给出的实验表明:该方法采用 Virtex 4 LX15 实现,对于 Snort 的 2 851 条规则共计 32 384 字节,占用存储空间 276KB,达到 2Gbps 的扫描速度.5.2 基于Bloom filter改良的自动机实现 基本的 A-C 算法由于每次读入一个字符都需要访存获得下一个状态,因此需要频繁访问存储器,带来很大的访问延迟,而且缺乏并行性,只能采用增加多
46、个自动机同时进行扫描的简单方式提高性能.但是,这又要求保存多个相关表的拷贝,增加了存储空间.Dharmapurikar 等人修改了基本的 A-C 算法,并引入了 Bloom filter,设计了基于硬件的匹配方案12,14,19.匹配的步长从原来的 1 增加到 k 以提高比较的效率,每次可以扫描 k 个字符,因 2412 Journal of Software 软件学报 Vol.17,No.12,December 2006 此,修改基本 A-C 算法中的各个函数,构建步长为 k 的自动机,对于最后长度不足 k 的字符串也作为一个输入,对应一个状态.由于步长为k使得文本中模式出现的位置只有在与k
47、对齐边界的情况下才能被识别出来,于是就需要有 k 个自动机,它们分别从文本开始处偏移分别为 0,1,2,k1 的位置开始扫描,这样才不会漏掉任何出现的模式.而且,由于自动机的设计是基于硬件的,所以它们之间完全能够并行处理,加速扫描.依据模式集合构建的状态转换表存储以下信息:当前状态和输入字符串,到达的下一个状态,产生的匹配模式,失效状态链.对于每次匹配,设当前状态为 statej,读入长度为 k 的文本 x=Tii+k1,首先找到状态转换表中当前状态为statej、输入字符串为 x 的最长前缀的表项state,string,从而获得下一个有效状态或是转到失效状态,同时输出匹配到的模式.在查找最
48、长前缀的过程中,需要对状态转换表中状态 statej相关的每个可能的前缀进行搜索匹配,简单的逐个搜索的方法不可行,会带来很大的延迟,因此引入 hash 思想,以statej,x1i为关键字进行 hash,状态转换表中相关表项也进行 hash,通过比较 hash 值,判断是否存在对应的表项.即便这样,最坏情况下需要对输入串 x 从 1 到 k 的每个长度的子串都进行一次 hash,再逐个比较,开销很大.为此,引入片上 Bloom filter,过滤掉不成功的搜索.依据状态表中前缀字符长度将关键字statej,x1i分类,可以分为 k 类,长度分别对应 1,2,k,再将同一类的关键字放入同一个 B
49、loom filter.在查询片外存储器搜索statej,x1i对应的表项之前,首先探测长度 i 的 Bloom filter,而 k 个 Bloom filter 可以并行查询,因此,仅一个时钟周期就可以知道这 k 类中的哪些产生了匹配,再对可能的匹配进行 hash 匹配查询,查找状态转换表获得下一个状态和相关的输出.图 6 给出了该方案的框架.采用 Bloom filter 是基于匹配发生的概率低,通常不大可能产生匹配的情况下.因此,可以省略掉一些延迟较大的查表过程,获得很高的性能.但是,计算模式集合的状态转换表需要较复杂的预处理过程.Arbitration for Hash table
50、accessNext state matching strings failure chainState transition Hash table Current state Current symbol B4B3B2B1 Direction of text stream Fig.6 Bloom filter based matching framework 图 6 基于 Bloom filter 的匹配框架 文献14中的实验指出:使用 FPGA 器件 F=250MHz,片内存储器大小是 376Kbits,片外存储器频率是250MHz,64bit wide,QDRII-SRAM,采用入侵检测