王亚南，徐周波，古天龙

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林　541004)



基于OBDD的模式匹配算法硬件实现

王亚南，徐周波，古天龙

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林541004)

针对模式匹配算法硬件实现过程中成本高的问题，提出一种基于OBDD的模式匹配算法。该算法通过OBDD刻画所有模式串，利用OBDD技术的S-删除规则与合并规则简化OBDD规模，并利用FPGA技术对OBDD结构进行硬件实现。实验结果表明，该算法硬件实现较为简单，不消耗CAM资源，并可通过OBDD简化规则减小电路规模。

OBDD；FPGA；模式匹配算法；CAM

模式匹配是数据结构中的一种基本运算，被广泛应用于入侵检测、信息检索等众多领域。根据单次匹配的模式串数量的不同分为单模式和多模式匹配。早期的模式匹配算法多为单模式匹配，如KMP算法[1]、BM算法等。因单模式匹配算法一次只有一个模式串参与匹配，匹配效率较低，虽然实现较为简单，但较低的匹配效率只适合模式集较少的匹配判定，限制了单模式匹配算法的应用[2]。相比单模式匹配算法，AC算法[3]、WM算法[4]等多模式匹配算法在匹配效率上有很大提高，但远不能满足实际需求对模式匹配算法性能的要求。

近年来，针对传统基于软件实现的模式匹配算法，研究人员开始尝试进行硬件实现。Park等[5]提出针对字符串匹配的高效并行硬件算法，利用数据流算法开发脉动阵列结构，并提出特殊用途超大规模集成电路设计方案。李伟男等[6]对传统AC算法与WM算法进行了改进，并通过硬件实例介绍了多模式匹配算法的硬件实现方法及策略，对今后多模式匹配算法的发展趋势进行了展望。嵩天等[7]提出了一种针对ACC算法的硬件体系结构，将当前状态保存至状态寄存器，将当前缓存状态保存至状态缓存寄存器，通过片上或片外存储器存储所有转换规则，根据当前状态与当前输入字符查找转换规则实现跳转，此算法单硬件结构实现可达到11 Gbit/s的匹配速度。

相比传统基于软件实现的模式匹配算法，基于硬件实现的模式匹配算法速度大大提高，可解决数据增加带来的处理速度缓慢等问题。但基于FPGA等硬件器件的模式匹配算法，因硬件器件的存储空间有限，难以满足大规模模式集对存储空间的要求，且FPGA等硬件集成电路芯片中内容可寻址存储器(content addressable memory，简称CAM)等存储的价格较为昂贵。为满足大规模模式匹配算法对存储空间的要求，很多基于硬件实现的模式匹配算法不得不添加外部存储器，这不仅增加了硬件实现的复杂性，还在一定程度上增加了额外开支。为此，通过引入有序二叉决策图(ordered binary decision diagram，简称OBDD)结构及其相关简化技术，无需或仅需较少的存储空间来实现模式匹配算法。将模式集整合到OBDD结构中，通过OBDD的S-删除规则与合并规则，简化OBDD结构，最后通过二选一多路选择器搭建基于OBDD的硬件电路，实现模式匹配算法。

1　OBDD

OBDD是一种新型的数据结构，是布尔函数的表述和运算中最有效的技术。有关OBDD的研究最早可追溯至20世纪50年代Lee的二叉决策程序与70年代Akers的二叉决策图的概念[8]。OBDD的定义如下。

定义1[9]布尔函数f(x1,x2,…,xn)从{0,1}n到{0,1}，变量序为π，利用二叉决策图表示布尔函数族#f(x1,x2,…,xn)，若任一有向路径上的变量x1,x2,…,xn都按变量序π的顺序出现，则此BDD即为布尔函数f(x1,x2,…,xn)的有序二叉决策图。

定义2[9]u为OBDD上的节点，fu为从{0,1}n到{0,1}的布尔函数，满足：

1)若u是终端节点，则fu=var(u)。

2)若u是非终端节点，则

定义3[9]OBDD中，若内部节点满足：

1)对于节点u，low(u)≠high(u)；

2)对于var(u)=var(v)的不同节点u、v，low(u)≠low(v)∪high(u)≠high(v)∪low(u)≠low(v)∩high(u)≠high(v)，则称此OBDD为简化有序二叉决策图(reduced ordered binary decision diagram，简称ROBDD)。

OBDD或ROBDD为布尔函数族#f(x1,x2,…,xn)中布尔函数的多根图描述，也就是多个布尔函数的共享图形描述，所以，OBDD或ROBDD也称共享二叉决策图(shared binary decision diagram，简称SOBDD)。

布尔函数f(x1,x2,x3)=x1x2x3，在变量序π：x1

图1　OBDDFig.1　OBDD

图2　简化OBDDFig.2　Simplified OBDD

任何的OBDD均可利用S-删除规则与合并规则进行简化，得到简化的OBDD。给定变量序π，布尔函数族#πf(x1,x2,…,xn)中的所有布尔函数仅有唯一的ROBDD表示。简化规则的主要思想是删除OBDD中的冗余节点，使其符合定义3。简化规则包括S-删除规则与合并规则。

规则1(S-删除规则)[9]对OBDD中的节点u，若low(u)=high(u)，则删除节点u，并将节点u的父节点直接连接至low(u)所对应的节点。

规则2(合并规则)[9]对于OBDD中的节点u、v，若var(u)=var(v)，low(u)=low(v)，且high(u)=high(v)，则删除节点u，并将节点u的父节点直接连接至节点v。

S-删除规则与合并规则如图3所示。

图3　简化规则Fig.3　Simplified rules

从图3可看出，当节点u的2条输出边均指向同一节点w时，可应用规则1所述的S-删除规则删除节点u。删除节点u并不改变OBDD所表示的布尔函数。若节点u、v的标记变量相同，且其0、1分支节点也相同，就可对节点u、v应用规则2的合并规则删除节点u或v。删除任一节点不会改变OBDD所表示的布尔函数。

2　模式集的OBDD表示

利用OBDD刻画模式集，首先需要将模式串表示为布尔表达式。当模式集中模式串的最大长度为m时，字符编码表中二进制数位长为k，n(n=m×k)位二进制数的不同取值即可表示模式集中所有模式串。设布尔函数f(x1,x2,…,xn)，变量序π：x1

设模式集{ab, ac, ad, af, ao, ba, bc, bd, cf, mc, mh, mn}，通过ASCII码编码，将字符相应的ASCII码值转化成二进制数值。对于布尔函数f(x1,x2,…,x16)，变量序π：x1

表1　模式串对应的布尔表达式

图4　模式集的OBDDFig.4　OBDD of patterns set

3　基于OBDD的模式匹配算法硬件实现

基于OBDD的模式匹配算法的硬件实现系统主要包括串转并模块、移位寄存器模块、OBDD电路模块，如图5所示。串转并模块的输入端为被测试的数据(比特流)，输出端为N位并行输出，N的大小由字符表的大小决定，如字符表大小为256，只需8位二进制数即可，则N=8。移位寄存器模块为N位并行输入，M位并行输出。其中M=N×k，k为模式集中最长模式串的长度，N为步长。OBDD电路模块是由FPGA多路选择器搭建的OBDD结构的电路。

经S-删除规则与合并规则简化后的OBDD结构，利用二选一多路选择器搭建OBDD结构的硬件电路。OBDD每个节点有2个分支，二选一多路选择器符合OBDD节点的规则要求。

布尔函数f(x1,x2,x3)=(x1+x2)·x3，变量序

图5　基于OBDD的模式匹配算法硬件系统Fig.5　Hardware system of the pattern matching algorithm based on OBDD

π：x1

通过多路选择器搭建基于图6的OBDD结构硬件电路(图7)。其中：OUT为输出；MUX为多路选择器。

图6　OBDD的简化Fig.6　The simplification of OBDD

图7　OBDD的多路选择器组合电路Fig.7　Multi-channel selector combinational circuits of OBDD

从图6可看出，经S-删除规则与合并规则简化后的OBDD规模大为减小。由图7可知，硬件实现过程中，所需硬件电路的规模同样大为减小，节省了逻辑门电路数量。在基于OBDD的多路选择器组合电路中，布尔变量值通过移位寄存器赋值，当输出位OUT为1时，匹配成功，此时输出移位寄存器中相应的数据为检测出存在匹配的位段；当输出位OUT为0时，不匹配。

4　实验验证及结果分析

实验用Altera公司的Quartus II9.0进行硬件仿真，利用verilog HDL语言与原理图输入方式，在硬件电路上实现基于OBDD的模式匹配算法。FPGA芯片选用cyclone系列，时钟频率为200 MHz。利用Quartus II9.0开发环境中的波形仿真器实现时序仿真。时序仿真如图8所示。

图8　时序仿真Fig.8　Timing simulation

当输入的数据流中存在与OBDD结构电路中所包含的某模式串相同时，匹配标志端bool_out输出高电平，其余时刻bool_out输出低电平。

实验结果表明，在时钟频率200 MHz，M=8时，8位数据只需一个时钟周期即可完成匹配判定，匹配速度为1.6 Gbit/s。通过并行处理，算法速度可进一步提高k倍(k为最长模式串长度)，基于OBDD的模式匹配算法硬件实现相比其他算法的硬件实现，在速度方面大体相当。但基于OBDD的模式匹配算法硬件实现的优势在于，无需消耗FPGA较为昂贵的CAM，只需通过构建基于OBDD结构的多路选择器组合电路，即可实现模式匹配，因此算法结构简单，利于硬件实现。

5　结束语

针对模式匹配算法在硬件实现过程中所需存储空间较大的问题，将OBDD技术应用到模式匹配算法的硬件实现过程中，提出一种针对硬件实现的模式匹配算法。通过OBDD结构表示模式集中所有模式串，进一步利用OBDD简化规则，简化OBDD结构，并通过二选一多路选择器构建基于OBDD结构的硬件电路，从而达到无需存储器即可实现模式匹配算法的目的，且算法实现过程较为简单。

[1]NAVARRO G,KIMMO F.Average complexity of exact and approximate multiple string matching[J].Theoretical Computer Science,2004,321:283-290.

[2]范洪博，姚念民.一种高速精确单模式串匹配算法[J].计算机研究与发展，2009,46(8):1341-1348.

[3]AHO A V,CORASICK M J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18(6):333-340.

[4]WU S,MANBER U.A fast algorithm for multi-pattern searching[R].Tucson:University of Arizona,1994:1-10.

[5]PARK J H,GEORGE K M.Efficient parallel hardware algorithms for string matching[J].Microprocessors and Microsystems,1999,23(3):155-168.

[6]李伟男，鄂跃鹏，葛敬国，等.多模式匹配算法及硬件实现[J].软件学报，2006,17(12):2403-2415.

[7]嵩天，李冬妮，汪东升，等.存储有效的多模式匹配算法和体系结构[J].软件学报，2013,24(4):1650-1665.

[8]古天龙.一类新型抽象数据类型：有序二叉决策图[J].桂林电子科技大学学报，2010,30(5):374-388.

[9]古天龙，徐周波.有序二叉决策图及应用[M].北京：科学出版社，2009:23-50.

编辑：张所滨

Hardware implementation of pattern matching algorithm based on OBDD

WANG Yanan， XU Zhoubo， GU Tianlong

(Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541000, China)

In the process of the hardware implementation of pattern matching algorithm, the cost is high. A pattern matching algorithm based on OBDD is proposed. The algorithm is represented by OBDD for all pattern strings. The size of OBDD is simplified by S-deletion rule and the merging rule, and the hardware implementation of OBDD structure is realized by FPGA technology. Experimental results show that this algorithm is relatively simple and does not consume CAM resource. The circuit size of the algorithm can be reduced by using the simplified OBDD.

OBDD; FPGA; pattern matching algorithm; CAM

2016-03-21

国家自然科学基金(61262030,61572146,61363030,U1501252)；广西自然科学基金(2015GXNSFAA139285,2014GXNSFAA118354)

古天龙(1964―)，男，山西芮城人，教授，博士，研究方向为形式化方法、符号计算。E-mail:cctlgu@guet.edu.cn

TP393

A

1673-808X(2016)03-0204-06

引文格式： 王亚南，徐周波，古天龙.基于OBDD的模式匹配算法硬件实现[J].桂林电子科技大学学报，2016,36(3):204-109.