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

一种基于FPGA的报文内容过滤算法田礼明 杨奕 王滨华（江南计算技术研究所，江苏 无锡 214083） 摘 要 报文内容过滤技术是防火墙、入侵检测系统和情报信息综合系统的重要技术之一。本文提出的算法充分发挥了硬件并行运算和流水线的优势，采用并行移位的匹配模块结构展宽了处理带宽，使用Bloom Filter技术加速自动状态机转换，同时设计了高效的Hash硬件电路，提高了算法性能。实验证明该算法可以稳定的过滤2.5Gbps的IP报文数据。 关键字 报文内容过滤；FPGA；Bloom Filter；自动状态机 所谓报文内容过滤，顾名思义是对IP包数据段的载荷进行过滤，过滤规则是字符串形式的数据内容。以IDS系统为例，管理员根据所掌握的入侵情况事先为系统设定入侵规则，这些规则的一个重要组成部分就是IP数据载荷的某些内容，具体表现为字符串。当系统接收到一个IP包后，IDS的内容过滤部分就会用自身的系统算法将规则库中的字符串逐一和包的内容匹配，一旦匹配了某个字符串，则证明匹配了相应的规则。 随着网络信息复杂化以及安全需求多样化，对报文内容过滤的需求也更加迫切。首先从安全角度来看，防火墙和入侵监测系统急需高效率的报文内容过滤算法。由于当今的入侵行为和攻击方式更具有复杂性，主要表现在数据载荷的内容中出现特征字符串，例如蠕虫病毒“Nimda”、“Code Red”、“Slammer”都包含特殊的字符串；从网络应用来看，应用于深度报文分类的路由设备、流量控制等同样需要获得并且对IP数据内容分类，例如一些多媒体数据、P2P数据都含有特定的字符串信息作为本身的标识；另外从信息获取的角度来看，技侦领域和数据挖掘如何从海量数据中发掘有用信息和情报资源，同样需要内容过滤。1 内容过滤的代表算法1.1 AC算法 AC算法即由Aho和Corasick提出的多模式匹配算法（即一次搜索查找可以判定多个字符串匹配问题）。简单地说，AC 算法使用了有限自动机的结构来接收并存储规则库中所有的字符串。自动机是结构化的，这样每个前缀都可用唯一的状态来标识，甚至是那些多个模式的前缀，这样复杂的前缀就可以简单的转化为状态机中的一个状态。当文本T中下一个字符不是模式中预期的下个字符中的一个时，会有一条失败链指向那个状态，代表最长的模式前缀，同时也是当前状态的相应后缀。在实践中，我们设定三个函数：状态转移函数goto（）、成功匹配输出函数output（）、匹配失败跳转函数failure（）。1.2 王的多模式匹配算法 王永成教授等人设计了更多关注了多模式匹配过程中字串之间的相互关系，对AC算法进行了改进0。算法在自动状态机思想的基础上，应用了BM算法0的跳转思想，即利用了匹配过程中匹配失败的信息，跳过尽可能多的字符。实现了快速的多模式匹配算法。在匹配的过程中，同样使用goto（）函数转移当前状态，在找到匹配结果之后output（）函数输出成功信息。而在匹配失败的时候，使用skip函数大幅度划文本T，减少goto（）函数的调用次数，从而提高过滤效率。1.3 Bloom Filter算法 Bloom Filter法最初多用于数据库存储和查询结构，近年来也应用于IP包内容过滤等领域。Bloom Filter算法的原理是找到k个hash函数，其值域都是1，2，m同时设定一个模式矢量M，其长度为m。对于规则库P中的每个模式，计算 hash1（p）、hashk（p） ，每次计算所得的 hashx（p）根据其数值对应到模式矢量的相应位置。这样，一个模式经过k个hash函数计算所得k个值，进而对应到模式矢量的k个位置，形成一个模式矢量。在查找的过程中，在文本中取出同p相同长度的字符串，经过k个hash函数计算后生成其相应的模式矢量，用这个模式矢量和库中的各个模式矢量比较，可以确定是否匹配。1.4 Dharmapurikar的算法 Dharmapurikar 等人修改了基本的AC算法，并引入了Bloom filter，设计了基于硬件的匹配方案。该算法拓展了AC状态机的输入带宽，从1byte扩展到Gbyte。相应的状态机内部对一个状态变化也要判断一组Gbyte的数据。而对于文本T尾部不足Gbyte的部分，采用并行的G-1个过滤单元，专用于过滤剩余长度为1、2、G-1的部分。而在状态转移的过程中，使用了Bloom Filter过滤掉了不可能产生状态转移的输入，极大地提高了匹配效率。而对于数量很少的状态转移操作，通过查找off-chip的存储单元中的hash表来确定状态转移和相应的匹配结果。本文在此基础上作进一步研究。2 内容过滤算法描述2.1 算法的并行结构 对于字符串匹配而言，一个匹配单元是1-byte，这样一个匹配模块一次的输入为1byte。如果可以将输入带宽从1-byte拓展到G-byte的话那么过滤速率显然也相应的提高了G倍。图1 一个G=4的内容过滤器 图1以一个G=4的实例说明了并行内容过滤器的算法结构。过滤器由四个完全相同的过滤模块并行组成，其中每个模块一次接收一定长度（B）的字串，进行过滤计算，下个周期接收下一组B长的字串。而对于整个过滤器而言，每个周期流入Gbyte的数据，流出Gbyte的数据。以过滤模块1为例，当前窗口接收串为“abcde”，下一个周期窗口内的串为“efghi”。虽然对于每个模块而言，每次会改变G=4个字节，但是因为存在了并行的4个模块，且每个模块的判断窗口都间隔1byte，这样就不会漏掉数据流中的任何一个位置。如果规则集中含有字符串“cdefg”的话，那么显然模块3对当前窗口过滤之后会给出一个匹配结果，而其他三个模块都不会有匹配结果产生。这样的并行结构通过使用处理位置上相互比邻的G个匹配模块，解决了自动状态机模型中对于输入字串1byte的限制，展宽了过滤带宽，进而提高了过滤速率。2.2 匹配模块的内部结构 图1中的一个匹配模块是一个独立的内容过滤单元，也是一个独立的状态机转换单元。其内部根据输入的G-byte的字串计算状态转移以及匹配的命中结果。下面介绍一个匹配模块的原理结构。 图2所示的是一个4byte宽的状态机模型，状态的每次转移都需要4byte的数据（4）。例如，判断S6=“elephant”，在当前状态q0的情况下，输入串为“elep”时，状态转移q0q4，接着输入“hant”，状态转移到q7，此时有匹配的结果输出。而普通的状态机，需要8次的状态转移。 在过滤的过程中更多的规则串并不是B的倍数，例如“phone”，在第一次状态转移中由于“phon”的存在由q0转移到q3，此后至需要判断下个输入中是不是后缀“e*”就可以判断是否命中了s5，同样还有“technically”中的后缀“lly”等。对长度为1到B-1之间的后缀，采用并行的B-1个后缀判断子模块。同时注意到对于长度恰好是B的整数倍的规则串，可以理解成有一个长度为0的后缀，这样便于同上述并行的B-1个后缀判断子模块一同组成B个并行的运算结构。图3给出了一个B=4的情况下的一个匹配模块的结构，其中4个Bloom Filter分别处理后缀长度为0、1、2、3的情况。然后通过查表得到状态转移关系以及结果输出情况。图2 一个4byte宽（B=4）的状态机图3 B=4情况下的一个匹配模块2.3 使用Bloom Filter 如前文所述，由于状态转移表占用很大的存储空间，需要使用off-chip的RAM来保存。而通常情况下外部存储器的读取带宽很小，不能支持一个模块的B个查表要求。其实在真实情况中只有很少的情况下才会有状态的转换，这时使用Bloom Filter来滤掉大量的不会产生状态变化的输入。一个状态转移关系可以表示成： = 所以可以对2元组进行hash运算，用结果搜索状态转移hash表，找到2元组。Bloom Filter的作用就是滤掉大量不会查找到结果的元组，只在当前有可能在hash表中查到结果的时候才允许对应项查找状态转移表。这样极大地减少了查表次数，提高了算法速率。2.4 Hash函数的硬件实现方法 对于Bloom Filter中使用的hash函数，要求易于硬件，占用尽可能少的时钟周期。H3算法提供了一个很好的解决方案。设子串的第i个字节为，则这个位置上的一个hash值为：hi=di1bi1di2bi2di8bi8 其中dij是一个预设的随机矩阵的一个值。这样，从1到i的hash值为：Hi=Hi-1hi 可见，位置i上的hash函数可以通过i-1位置上的hash函数简单的算出。并且如果dij=di+1j的话，可见t时刻的hi和t+1时刻的hi-1是相同的，这样所有Hi就可以通过并行的移位结构在一个时钟周期内完成，而不用等待Hi-1的计算结果。相应的结构如图4所示，算法可以在一个时钟周期内算出所有Hi的值，非常便捷。图4 硬件Hash函数的逻辑结构3 FPGA实现 本文的实验系统使用的是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和状态转移表的构成同样有待进一步优化，所以本文算法具有进一步升级的潜力。4 结论 本文针对目前网络传播速率急剧增加，数据处理规则规模庞大的特点，提出了基于FPGA的IP报文内容过滤算法。本文在当前多种优秀的内容过滤技术的基础上，充分利用了FPGA芯片高速并行处理和流水线操作的特点，提出使用并行的移位模块来拓展过滤算法的处理带宽，使得算法支持的IP报文速率得到了很大的提高。同时，为解决off-chip的RAM读取带宽受限的瓶颈，以及在状态转移过程中读取下一个状态需要占用额外的时钟周期的问题，提出了用Bloom Filter过滤掉不会产生状态转移的输入字串，进一步提高处理速率。另外，设计了仅需要一个时钟周期就可以完成hash计算的硬件电路，并且通过改进，可以在一个时钟周期内得到所有后缀长度的hash值，使得算法在FPGA中的流水性能增强。最后通过在实验系统中的测试，在77MHz的时钟下可以正确的过滤2.5Gbps的IP报文，并且有进一步升级的潜力。参考文献1Coit C J，Staniford S，McAlerney JTowards faster pattern matching for intrusion detection or exceeding the speed of snortCIn：DARPA Information Survivability Conference and Exposition，20012王永成，沈州，许一震改进的多模式匹配算法计算机研究与发展，2002，39(1)：55-603R.S.Boyer，J.S.MooreA Fast String Searching AlgorithmCommunication of the ACM，1977，20(10)：7627724B. BloomSpace/time trade-offs in hash coding with allowable errorsACM，13(7)：422426，May 19705S. Dharmapurikar，P. Krishnamurthy，T. S. Sproull，and J. W. LockwoodDeep Packet Inspection using Parallel Bloom Filters. IEEE Micro，24(1)：5261，20046Dharmapurikar S，Lockwood JFast and scalable pattern matching for content filteringIn：Berenbaum A，ed. Proc. of the 2005 Symp. on Architecture for Networking and Communications Systems. New York：ACM Press，2005. 183-192