文档介绍：田礼明 杨奕 王滨华(江南计算技术研究所,江苏 无锡 214083)    摘 要 报文内容过滤技术是防火墙、入侵检测系统和情报信息综合系统的重要技术之一。本文提出的算法充分发挥了硬件并行运算和流水线的优势,采用并行移位的匹配模块结构展宽了处理带宽,使用BloomFilter技术加速自动状态机转换,同时设计了高效的Hash硬件电路,提高了算法性能。。   关键字 报文内容过滤;FPGA;BloomFilter;自动状态机    所谓报文内容过滤,顾名思义是对IP包数据段的载荷进行过滤,过滤规则是字符串形式的数据内容。以IDS系统为例,管理员根据所掌握的入侵情况事先为系统设定入侵规则,这些规则的一个重要组成部分就是IP数据载荷的某些内容,具体表现为字符串。当系统接收到一个IP包后,IDS的内容过滤部分就会用自身的系统算法将规则库中的字符串逐一和包的内容匹配,一旦匹配了某个字符串,则证明匹配了相应的规则。   随着网络信息复杂化以及安全需求多样化,对报文内容过滤的需求也更加迫切。首先从安全角度来看,防火墙和入侵监测系统急需高效率的报文内容过滤算法。由于当今的入侵行为和攻击方式更具有复杂性,主要表现在数据载荷的内容中出现特征字符串,例如蠕虫病毒“Nimda”、“CodeRed”、“Slammer”都包含特殊的字符串;从网络应用来看,应用于深度报文分类的路由设备、流量控制等同样需要获得并且对IP数据内容分类,例如一些多媒体数据、P2P数据都含有特定的字符串信息作为本身的标识;另外从信息获取的角度来看,技侦领域和数据挖掘如何从海量数据中发掘有用信息和情报资源,同样需要内容过滤。1  AC算法   AC算法即由Aho和Corasick提出的多模式匹配算法(即一次搜索查找可以判定多个字符串匹配问题)。简单地说,AC算法使用了有限自动机的结构来接收并存储规则库中所有的字符串。自动机是结构化的,这样每个前缀都可用唯一的状态来标识,甚至是那些多个模式的前缀,这样复杂的前缀就可以简单的转化为状态机中的一个状态。当文本T中下一个字符不是模式中预期的下个字符中的一个时,会有一条失败链指向那个状态,代表最长的模式前缀,同时也是当前状态的相应后缀。在实践中,我们设定三个函数:状态转移函数goto()、成功匹配输出函数output()、匹配失败跳转函数failure()。 王的多模式匹配算法   王永成教授等人设计了更多关注了多模式匹配过程中字串之间的相互关系,对AC算法进行了改进0。算法在自动状态机思想的基础上,应用了BM算法0的跳转思想,即利用了匹配过程中匹配失败的信息,跳过尽可能多的字符。实现了快速的多模式匹配算法。在匹配的过程中,同样使用goto()函数转移当前状态,在找到匹配结果之后output()函数输出成功信息。而在匹配失败的时候,使用skip函数大幅度划文本T,减少goto()函数的调用次数,从而提高过滤效率。 BloomFilter算法   BloomFilter法最初多用于数据库存储和查询结构,近年来也应用于IP包内容过滤等领域。BloomFilter算法的原理是找到k个hash函数,其值域都是{1,2,…,m}同时设定一个模式矢量M,其长度为m。对于规则库P中的每个模式,计算hash1(p)、……、hashk(p),每次计算所得的hashx(p)根据其数值对应到模式矢量的相应位置。这样,一个模式经过k个hash函数计算所得k个值,进而对应到模式矢量的k个位置,形成一个模式矢量。在查找的过程中,在文本中取出同p相同长度的字符串,经过k个hash函数计算后生成其相应的模式矢量,用这个模式矢量和库中的各个模式矢量比较,可以确定是否匹配。 Dharmapurikar的算法   Dharmapurikar等人修改了基本的AC算法,并引入了Bloomfilter,设计了基于硬件的匹配方案。该算法拓展了AC状态机的输入带宽,从1byte扩展到Gbyte。相应的状态机内部对一个状态变化也要判断一组Gbyte的数据。而对于文本T尾部不足Gbyte的部分,采用并行的G-1个过滤单元,专用于过滤剩余长度为1、2、……、G-1的部分。而在状态转移的过程中,使用了BloomFilter过滤掉了不可能产生状态转移的输入,极大地提高了匹配效率。而对于数量很少的状态转移操作,通过查找off-chip的存储单元中的hash表来确定状态转移和相应的匹配结果。本文在此基础上作进一步研究。2  算法的并行结构   对于字符串匹配而言,一个匹配单元是1-byte,这样一个匹配模块一次的输入为1byte。如果可以将输入带宽从1-byte拓展到G-byte的话那么