一种基于FPGA的报文内容过滤算法

图2 一个4byte宽（B=4）的状态机

图3 B=4情况下的一个匹配模块

如前文所述，由于状态转移表占用很大的存储空间，需要使用off-chip的RAM来保存。而通常情况下外部存储器的读取带宽很小，不能支持一个模块的B个查表要求。其实在真实情况中只有很少的情况下才会有状态的转换，这时使用Bloom Filter来滤掉大量的不会产生状态变化的输入。一个状态转移关系可以表示成：

当前状态，输入字串 ==〉下个状态，输出信息

所以可以对2元组当前状态，输入字串进行hash运算，用结果搜索状态转移hash表，找到2元组下个状态，输出信息。Bloom Filter的作用就是滤掉大量不会查找到结果的元组，只在当前当前状态，输入字串有可能在hash表中查到结果的时候才允许对应项查找状态转移表。这样极大地减少了查表次数，提高了算法速率。

对于Bloom Filter中使用的hash函数，要求易于硬件，占用尽可能少的时钟周期。H3算法提供了一个很好的解决方案。设子串的第i个字节为bi1、bi2、……、bi8，则这个位置上的一个hash值为：

hi=di1•bi1⊕di2•bi2⊕……⊕di8•bi8

其中dij是一个预设的随机矩阵的一个值。这样，从1到i的hash值为：

Hi=Hi-1⊕hi

可见，位置i上的hash函数可以通过i-1位置上的hash函数简单的算出。并且如果dij=di+1j的话，可见t时刻的hi和t+1时刻的hi-1是相同的，这样所有Hi就可以通过并行的移位结构在一个时钟周期内完成，而不用等待Hi-1的计算结果。相应的结构如图4所示，算法可以在一个时钟周期内算出所有Hi的值，非常便捷。

图4 硬件Hash函数的逻辑结构

本文的实验系统使用的是Altera公司StratixII系列的EP2S60FPGA芯片。该芯片拥有2.5Mb的片内RAM空间，可以支持最多两个独立off-chip的DDR或QDR单元。输入信号是经过前端处理的POS信号，解为整载的IP报文数据。规则随机地取自IDS系统SNORT的2000条规则。

在实现的过程中使用8个并行的过滤模块，也就是每次输入8byte的数据。虽然更高的并行数量会提高系统的处理带宽，但是也相应需要占用更多的RAM空间，这里考虑到SNORT的规则相对较短（多分布在5-15byte），采用8byte并行的算法。Bloom Filter由6个并行的hash函数构成，每个hash函数对应的hash表采用2kbit，这样一共占用了2kbit*6*8*8=768kbit的片内RAM资源，约占总量的30%。经过计算，这样的Bloom Filter设计可以保证经过过滤操作之后，只有6e-10的假匹配存在（即对应的hash值表明当前元组当前状态，输入字串可以产生正确的状态转移，然而在off-chip的RAM中找不到对应项）。这里需要提一下，由于8个并行模块是同构的，其hash表也是相同的，如果使用时分的hash表查找方法或者Lucent memory core可以占用更少的RAM资源。

当实验系统FPGA工作在77MHz的情况下的时候，可以正确无误的过滤2.5Gpbs的IP报文数据。由于该算法使用的RAM和时钟频率都没有达到额定值，同时，内部Bloom Filter和状态转移表的构成同样有待进一步优化，所以本文算法具有进一步升级的潜力。

本文针对目前网络传播速率急剧增加，数据处理规则规模庞大的特点，提出了基于FPGA的IP报文内容过滤算法。本文在当前多种优秀的内容过滤技术的基础上，充分利用了FPGA芯片高速并行处理和流水线操作的特点，提出使用并行的移位模块来拓展过滤算法的处理带宽，使得算法支持的IP报文速率得到了很大的提高。同时，为解决off-chip的RAM读取带宽受限的瓶颈，以及在状态转移过程中读取下一个状态需要占用额外的时钟周期的问题，提出了用Bloom Filter过滤掉不会产生状态转移的输入字串，进一步提高处理速率。另外，设计了仅需要一个时钟周期就可以完成hash计算的硬件电路，并且通过改进，可以在一个时钟周期内得到所有后缀长度的hash值，使得算法在FPGA中的流水性能增强。最后通过在实验系统中的测试，在77MHz的时钟下可以正确的过滤2.5Gbps的IP报文，并且有进一步升级的潜力。

[1]Coit C J，Staniford S，McAlerney J．Towards faster pattern matching for intrusion detection or exceeding the speed of snort[C]．In：DARPA Information Survivability Conference and Exposition，2001

王永成，沈州，许一震．改进的多模式匹配算法．计算机研究与发展，2002，39(1)：55-60

，．A Fast String Searching Algorithm．Communication of the ACM，1977，20(10)：762～772

B. Bloom．Space/time trade-offs in hash coding with allowable errors．ACM，13(7)：422–426，May 1970

S. Dharmapurikar，P. Krishnamurthy，T. S. Sproull，and J. W. Lockwood．Deep Packet Inspection using Parallel Bloom Filters. IEEE Micro，24(1)：52–61，2004

Dharmapurikar S，Lockwood J．Fast and scalable pattern matching for content filtering．In：Berenbaum A，ed. Proc. of the 2005 Symp. on Architecture for Networking and Communications Systems. New York：ACM Press，2005. 183-192