评价网 > 科教论文 > 工学毕业论文 > 计算机应用论文 > 正文

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

2013-09-13 02:38 摘 要 报文内容过滤技术是防火墙、入侵检测系统和情报信息综合系统的重要技术之一。本文提出的算法充分发挥了硬件并行运算和流水线的优势，采用并行移位的匹配模块结构展宽了处理带宽，使用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”时，状态转移q0—〉q4，接着输入“hant”，状态转移到q7，此时有匹配的结果输出。而普通的状态机，需要8次的状态转移。 在过滤的过程中更多的规则串并不是B的倍数，例如“phone”，在第一次状态转移中由于“phon”的存在由q0转移到q3，此后至需要判断下个输入中共2页: 1 [2] 下一页 论文出处(作者):