基于中间点划分无冲突哈希的高速包处理:哈希冲突解决方法

　　摘要:通过在高速片上存储器上存储所有的攻击特征，实现对数据包的高速检测。针对有限的片上存储器空间，提出一种新的基于中间点划分无冲突哈希函数的trie树结构，将攻击特征串平均分配到trie树每层的多个组中，实现对片上存储器有效的控制。通过在同一个芯片中采用流水并行方式执行查询操作，获得更高的吞吐量。存储中间点的空间复杂度为�O(n)，�哈希表的构建时间随攻击特征数量线性增长。实验结果表明：该方法降低了片上存储空间需求，在片上存储器只需执行一次即可完成特征匹配操作。
　　关键词:高速包处理;无冲突哈希;中间点划分;trie树;片上存储
　　
　　中图分类号: TP393.06;TP311.12 文献标志码:A
　　�
　　High.speed packet processing by non.collision hash functions based on�
　　 middle.point partition
　　�
　　ZHANG Mo.hua��1�*�, LI Ge�2
　　
　　1.School of Computer and Information Engineering, Henan University of Economics and Laws, Zhengzhou Henan 450000, China
　　;�
　　2.Department of Information Engineer, Conservancy Vocational Institute of North China Institute of� Water Conservancy and Hydroelectric Power, Zhengzhou Henan 450000, China
　　Abstract:
　　
　　High.speed packet inspection can be achieved through storing attack signatures on the high.speed on.chip memory. Concerning the limited on.chip memory, this paper proposes a new trie structure with non.collision hash functions based on middle.point partition. The algorithm evenly partitiones attack signatures into mutiple groups at each layer in trie tree to achieve the effective control of memory. The trie.tree structure can be implemented on a single chip and perform query operations by pipelining and parallelism,thus achieves higher throughput. The space complex of storing middle.point is O(n) and the construction time of hash table is linearly growing with the number of attack signatures The experimental results show that the new structure decreases the demand of on.chip memory and can facilitate access to the attack signature on the on.chip memory while allowing to perform the signatures matching operations only once.
　　
　　High.speed packet inspection can be achieved through storing attack signatures on the high.speed on.chip memory. Concerning the limited on.chip memory, this paper proposed a new trie structure with non.collision hash functions based on middle.point partition. The algorithm evenly partitioned attack signatures into multiple groups at each layer in trie tree to achieve the effective control of memory. The trie.tree structure can be implemented on a single chip and perform query operations by pipelining and parallelism, thus achieving higher throughput. The space complex of storing middle.point is �O�(�n�) and the construction time of hash table is linearly growing with the number of attack signatures. The experimental results show that the new structure decreases the demand of on.chip memory and can facilitate access to the attack signature on the on.chip memory while allowing to perform the signatures matching operations only once.
　　�Key words:
　　high.speed packet processing;non.collision hash;middle.point partition;trie tree ;on.chip memory
　　�
　　
　　0 引言�
　　网络入侵检测技术是网络攻击防范的主要手段，数据包检测是其核心。数据包检测不仅检查数据包头部信息，而且要检查数据包有效载荷��［1］�。采用数据包预处理方法，依据数据包头部字段对其进行分类和查找，采用特征匹配算法，将每个数据包内容与一组预定义的特征串进行匹配。本质上来说，包检测是一种数据包内容过滤技术，不仅应用于网络入侵检测系统中，而且应用于网络取证系统、P2P流量识别以及基于上下文的流量计费等��［2］�。随着网络带宽和业务流量的迅猛增长，包处理正面临如何满足高速数据包处理的时间和空间需求的挑战。包处理通常部署在高速路由器的关键数据路径上，检查海量高速数据包，与大量预定义的规则进行匹配。由于基于软件的包处理难以适应高速数据包处理，当前研究者采用现代嵌入式存储器技术，例如
　　
　　【确认全称是否正确】
　　专用集成电路(Application Specific Integrated Circuit, ASIC)、现场可编程门阵列(Field.Programmable Gate Array, FPGA)、网络处理器(Network Processor, NP) 和三重内容可寻址存储器(Ternary Content Addressable Memory, TCAM)等，
　　
　　设计和实现了多种基于硬件的包处理技术，支持10�Gbps以上的线速数据包处理��［3］�。这些嵌入式存储器技术通常采用分层存储器体系结构，即由快速片上存储器和大容量片外存储器组成。基于硬件的方法通常被分为片外储器和片上存储器两种架构。考虑速度第一，片外存储架构并没有片上方法那么吸引人。片外架构的主要缺点在于需要与芯片上的匹配引擎进行物理连接。即使外部存储速度显著增加，但是仍然会妨碍引擎的并行性。这样，片外方法对于高速线速操作并不是很合适。例如片上SRAM存储的访问时间为1～2�ns，但是其存储空间受限，难以存储大量元素；而片外存储器提供更大容量存储空间，适合于存储大量元素，但是其查找速度较慢，例如片外DRAM的访问时间在60�ns左右��［4］�。因此，研究设计一种快速和存储高效的数据包预处理方法，不仅减少片外存储器访问次数，而且降低其存储空间需求，是高速数据包处理的关键所在。�
　　在包检测研究方面，当前主要着眼于两个方面提高检测性能:1)设计基于硬件的特征匹配算法,减少单个特征匹配的处理时间和存储空间需求；2)设计基于硬件的Hash表等数据包预处理方法，减少片外存储器访问次数和特征匹配次数��［4］�。王志佳等��［5］�提出了一种改进的基于确定有限自动机的深度包检测算法，该算法在牺牲少量运算时间的情况下，减少算法所需的运算空间。徐乾等��［6］�提出一种基于确定的有穷状态自动机的正则表达式压缩算法，采用选择性分群算法大幅度减少了状态机的个数，降低了包检测匹配算法的复杂性。Smith等��［7］�提出了XFA(eXtended FiniteAutomaton)模型，在状态上增加辅助变量及其操作指令,消除确定性有限自动机状态空间爆炸问题。Lu等��［8］�提出了多字符并行处理的Aho.Corasick算法，通过并行操作提高Aho.Corasick算法的吞吐量，并最小化其存储空间需求。总的来说，由于软件包检测系统运行在通用处理器上，不适合高速网络，很难在当今线速环境下完成检测。为了满足高速网络的需要，本文重点关注基于硬件的方法。Tan等��［9］�使用一种小型状态机来改进存储需求以适应Snort的特征库，使用了0.4�MB的存储空间，采用ASIC实现，可以运行在10�Gbps网络下。潘志浩等人提出了结合专用网络处理器(NP)的嵌入式深度包检测解决方案��［10］�。Jung��［11］�给出了文献［9］的FPGA的实现，获取了更低的吞吐率，但是存储空间更大。Hua等��［12］�用一次扫描可变步长的多个字符,提高字符串匹配的吞吐量,并减少其存储空间需求；Papadopoulos��［13］�使用了稀疏哈希表来存储特征串，尽管改进了存储空间，但存储利用率还是比较低。一些研究者尝试使用外部存储结构TCAM及SRAM，但是TCAM比较昂贵，而SRAM则受限于速度。Sourdis等采用一种混合的方法��［14］�，使用可配置的电路和片上存储器，采用无冲突哈希的方法，该方法与本文的方法类似，但与本文方法不同的是，该方法需要进行重配置，并且存储利用率低，因为其使用了无冲突哈希，而不是最小无冲突哈希。Lu等��［15］�提供了一种空间复杂度为�O(n)�的最小无冲突哈希方法，具有较快的构建时间，但这一方法需要复杂的地址方案，而且要求有附加的逻辑来计算哈希表的地址。�
　　
　　本文研究目标是提供一种低成本和节省空间的最小无冲突哈希函数，称之为中间点划分哈希，即易于构建，又适合在高速硬件平台下实现。该算法基于trie树，算法渐近地决定关键字集合中哪个关键字与数据包进行比较。算法开始从trie树的根节点开始将所有关键字集合划分为两个相等大小的组，�每个组中有n/2个关键字。新划分的组被置于根节点的左右孩子节点中，每个新组继续被划分成两个相同大小的组(每个组有n/4个关键字)。这种划分迭代重复执行，直至n个节点为止，分别对应于n个关键字。�为了查询关键字，算法遍历整个trie树，直到在某个叶子节点中找到候选关键字为止。当找到单个关键字，只需要进行一次匹配(即只比较查询关键字与候选关键字)，就可以决定被查询的关键字是否实际与候选关键字相同。�
　　1 最小无冲突哈希函数�
　　定义1
　　�最小无冲突哈希函数。对于具有n个元素的关键字集合S，一个无冲突的哈希函数f将S中每个关键字映射到值域［0，m-1］中的各不相同的唯一的数值(m≥n)。最小无冲突哈希函数指的是满足m=n的无冲突哈希函数。�
　　根据上述定义，函数f是最小无冲突哈希函数，当j，k∈S时，如果f(j)=f(k)，则必然是j=k，不存在j≠k而f(j)=f(k)的情况。最小无冲突哈希函数保证仅有一个关键字被保存在某一个哈希位置，这样只需要执行一次匹配操作就可以完成查询，换句话说是没有哈希冲突的。通过将哈希表的大小设置为与关键字的数量一致，可以达到最小的哈希表大小。值得注意的是，除了保存关键字外，哈希函数需要附加的空间来存储其自身。�
　　定义2
　　二分函数。对于具有n个关键字的集合S，S=｛sg�1，sg�2，…，sg�n｝，首先定义一个二分函数BF。该函数定义如下：�
　　BF�n(e,S)=
　　0,e∈S�l,S�l={sg�1,…,sg��n/2�}�
　　1,e∈S�r,S�r={sg��n/2+1�,…,sg�n}
　　
　　(1)�
　　其中e表示待查询的关键字。如果元素e属于左分组S�l，令BF�n(e,S)=0；如果e属于右分组S��r�，则令BF�n(e,S)=1。这样查询问题就变为查询元素隶属于左分组还是右分组，而不是具体的位置查询。S�l与S�r是S集合中两个互不相交的子集。当确定被查询关键字隶属于组S�l还是S�r后，可以在一个更小的具有n/4个关键字的组中进行查找，集合中包括被查询的关键字，通过应用BF��n/2�于被查询的关键字上。例如，如果BF�n(e,S)=0，即e∈S�l，可以应用BF��n/2�(e,S�l)在包含e有n/4个关键字的组中寻找。上述操作重复执行，直到结果组大小为1为止，即直到应用BF�2为止，它指出一个关键字集合可以匹配被查询关键字。定义一个�trie�树，节点N��l,i�是层l中第i个子集，大小n/2�l(【i=1,…,2�l，l=0,…,�lb�(n)-1)。l层每个节点使用二分函数BF�l��n/2�，有两个孩子节点，每个孩子节点具有n/2��l+1�个关键字。式(2)定义一个函数H�n(e)为�lb��n个二分函数{BF�n,BF��n/2�,BF��n/4�,…,BF�2}的连接。�
　　
　　H�n(e,S)=BF�n �&� BF��n/2� �&� BF��n/4�… �&� BF�2
　　(2)�
　　其中�&�符号是位连接符。令H�n［i］表示H�n的第i个位。�
　　定理1
　　函数H�n(e,S)定义了有n个关键字集合S的最小无冲突哈希函数。�
　　证明
　　BF�l��n/2�将层l的节点的关键字划分为两个不相交的子集，S�l和S�r。�sg�l∈S�l，H�n(l)=0，�sg�r∈S�r，H�n(l)=1。H�n(sg�l,S)与H�n(sg�r,S)至少有一个位是不同的(即在H�n［l］处)。这样不会有sg�l(sg�l∈S�l)与任何sg�r(sg�r∈S�r)冲突。这一原理可以迭代地应用到从根节点开始的所有节点中，直到到达最后一层ll(即�lb��n-1)。对于两个在层ll的两个不同节点中的特征串sg�i和sg�j，H�n(sg�i,S)和H�n(sg�j,S)至少有一位是不同的，这样不会有两个不同节点的两个不同的特征串发生冲突。在层ll中，BF�2划分一个节点到两个不相交的集合中，每个只有一个特征串，因为H�n［ll］对于这两个特征串是不同的。在层ll中相同节点中的特征串是没有冲突的。这样H�n是一个无冲突哈希函数。H�n的输出有�lb��n个位。因为有�lb��n个函数。这样，H�n的范围是［0..n-1］，所以H�n是集合S的最小无冲突哈希函数。�
　　推理1
　　在具有n个特征串的集合S上构建一个最小无冲突哈希函数等同于对集合S迭代地构建二分函数｛BF�n，BF��n/2�，…,BF�2｝。��
　　2 构建最小无冲突哈希函数�
　　
　　�假设一个无冲突哈希函数H，取值范围在［0..m-1］，用来存储和查询n个特征串，具有m个桶(m≥n)，并且没有冲突。每个特征串根据哈希函数值被插入到对应的存储桶中。在所有特征串被存储后，按照存储单元从左到右递增地次序给每个特征串赋一个序号。例如第一个关键是sg�1，最后一个是sg�n。图1示意有8个关键字，使用无冲突哈希函数H，插入到11个桶中。在查询关键字时计算H的值，读取对应的存储桶编号。��
　　
　　5 结语�
　　包检测是网络入侵检测系统的核心操作。本文提出基于中间点划分，实现一种节省存储适合硬件实现的最小无冲突哈希函数的构建。中间点哈希提供了一种新的具有较少空间的节点结构，适合于在将入侵特征信息以哈希表的方式存储于片上存储器中，提高了查找匹配速度。理论与实验证明，利用中间点构建最小无冲突哈希函数，存储中间点的空间复杂度在�O(n)，�整个中间点哈希表的构建时间随关键字呈线性增长。该方法可广泛应用于IP查找、数据包分类、深度包检测和流量监控、分析等高速数据包处理中。
　　
　　�参考文献:�
　　[1]
　　PAXSON V, ASANOVIC K, DHARMAPURIKAR S, et al. Rethinking hardware support for network analysis and intrusion prevention ［C］// Proceedings of USENIX Workshop on Hot Topics in Security. Boston: USENIX Association Berkeley, 2006: 63-68.

推荐访问:划分 冲突