一种快速的五元一维包分类算法

摘要:包分类算法在网络安全产品中至关重要,该文介绍常见的包分类算法,针对现有包分类算法的不足,构造了一种基于Hash函数的可快速查找、快速定位五元一维包分类算法,并给出算法准确性、快速性的理论证明。

关键词:包分类;Hash函数;线性查找算法

中图分类号:TP311文献标识码:A文章编号:1009-3044(2009)36-10568-03

A New Fast Five-to-one Dimensional Packet Classification Algorithm

PEI Lin

(The People's Bank of China, Urumqi Central Sub-Branch, 830002 Wulumuqi, China)

Abstract: The packet classification algorithm is important in product of network security. This paper introduces the common packet classification algorithms, analyses the flaws of these algorithms, and constructs a new five-to-one packet classification algorithm based on Hash function. At last, the accurancy and rapidity of the new packet classification algrithom is given.

Key words: packet classification; Hash fuction; sequential search algorithm

网络和信息技术已经日渐深入到人们的日常生活和工作中,社会信息化和信息网络化日益提高。在互联网带给我们便利的同时,也给我们带来了挥之不去的安全问题。例如黑客攻击、计算机病毒、特洛伊木马、拒绝服务器攻击、信息泄露或丢失等安全威胁,会给一些用户和企业带来了严重的经济损失。网络安全问题引起国内外的广泛关注。

作为最早、技术最成熟的网络安全技术,防火墙通过在网络间执行控制策略,保障网络安全,其核心技术[1]就是网络数据包的拦截与分类。其它一些网络安全技术,如入侵检测、网络监控、安全审计、虚拟专用网等,也是以数据包分类为基础的。数据包分类[2]就是把网络中数据包归属为某个流的过程,然后根据用户预先设置的过滤规则对每一类数据包进行相应的处理,这些过滤规则是依据数据包头的内容把数据包分为不同的类。数据包分类的正确性、快速性将直接影响安全产品的性能与效率。由此可见,对数据包分类算法的研究具有重要的现实意义。

1 常见的包分类算法

现在的包分类算法主要有以下四种类型[3]:

1)基于数据结构的算法

该类算法的主要特点是使用基本的数据结构来组织并优化流分类问题的查找、定位及匹配问题。主要的数据类型包括线性和树型结构等。最简单的基于线性结构的分类算法是顺序查找方法。其中,基于Tries树结构算法是一种常用算法。如Grid-of-Tries树、层次Tries树、多比特Tries树等。

2)基于几何空间的算法

主要思想是将整个搜索空间递归的按照某种规则分割成某些子空间,然后通过预处理计算这些子空间与规则之间的关系,根据这些信息构建决策树以进行搜索。如交叉乘积(cross-Product)、基于区间划分的四叉树(Area base Quadtree)、FIS算法(Fat Inverted Tree)等。

3)启发式的算法

启发式分类算法[4]是指针对特定应用环境的研究,利用规则库内的结构和兀余度,根据某种特点而设计出流分类问题的解决方案。如递归流分类算法(Recursive Floww Classification)、分层只能查找算法(Hierarchical Intelligent Cuttings)、元组空间查找算法(Tuplc Space Search)。

4)基于硬件的算法

该算法将所有的规则用硬件来实现,对硬件资源要求和存储空间要求都很大,只适用于对速率要求很高,规则维数和个数都很少的情况。如三元内容寻址存储器(Ternary Content Addressable Memory)、位图交集算法(Bitmap Intersection)等。

2 基于Hash函数的五元一维包分类算法

现有的包分类算法中[5],一维、二维分类算法比较成熟,应用广泛,而对于多维包分类算法由于对要求内存空间过大无法满足低成本的要求,或由于其分类的速度无法满足高速网络环境的应用需求。由于Hash函数具有快速查找和快速定位的特性,构造了一个包分类算法――基于Hash函数的五元一维包分类算法,不但提高了查找速度,而且减少了存储空间,并对算法的准确性和快速性给以证明。

2.1 Hash算法的特点

Hash算法[6]既是一种常见的存储方法,也是一种查找方法。Hash算法以关键字的值为自变量,通过一定的函数关系,计算出对应的函数值,把这个值解释为节点的存储地址――Hash地址,将节点存入到这个存储单元里去。查找时再根据查找的关键字用同样的Hash函数计算地址,然后到相应的地址单元里去取要找的节点。在理想情况下,不经过任何比较,一次Hash运算便可找到所要的节点。

2.2 算法设计

基于Hash函数的五元一维包分类算法包括两个部分:过滤规则库的建立过程和包分类的过程。下面定义几个相关定义:

定义3.1 分类规则是一个六元组{sip,dip,sp,dp,pt,act},其中sip代表数据包的源IP地址,dip代表数据包的目的IP地址,sp代表数据包的源端口,dp代表数据包的目的端口,pt代表数据包的协议类型,act代表符合前面条件的数据包对应的动作。act动作可以简单的分为“允许”和“拒绝”,即让符合规则的数据包进入系统,或者丢弃。

定义3.2 主机IP地址:即使用本数据包分类系统的主机IP地址。

定义3.3 本地IP地址:即本主机所对应的IP地址,当发送数据时,包头中对应的源地址为本地IP 地址;当接收数据时,包头中对应的目的IP地址。

定义3.4 外地IP地址:即发送数据时,包头中对应的目的IP地址;接收数据时,包头中对应源IP地址。

定义3.5 哈希冲突:当{sp1,dp1,pt1}∩{sp2,dp2,pt1}=φ时,若Hash{sp1,dp1,pt1}≠Hash{sp2,dp2,pt1},则不存在哈希冲突,即不同结点存储在不同的地址;否则,若 ,则存在哈希冲突,即不同结点存储在相同的地址。

本算法构造的Hash函数如下:

Hash{sp1,dp1,pt1}+Hash{sp2,dp2,pt1}%M=HashAdd

Hash函数的输入为数据包头的源端口sp目的端口dp、协议类型pt,Hash运算是源端口sp和目的端口dp分别与协议类型pt异或相加,最后结果对M取模运算,M比规则库实际存储的规则数N大20%左右的素数,模运算的结果即为结点存储的地址――Hash地址HashAdd。

本文构造的基于Hash函数的五元一维包分类算法包括两个部分:规则库的建立过程、数据包分类过程。

算法3.1 规则库的建立算法

假设规则库中实际存储N条规则,为了减少Hash冲突,规则库的实际大小为M(M比N大20%左右的素数)。规则库的建立过程如下:

1) 分配存储空间,能容纳M条分类规则的规则库;

2) 初始化规则库,每条规则置空NULL;

3) Hash运算,得到存储规则的Hash地址;

4) 在Hash地址存储对应的外地IP地址;

i) 如果无哈希冲突时,外地IP地址直接存储在已计算的Hash地址中;

ii) 如果有哈希冲突,外地IP地址存储在已计算的Hash地址对应的单链表的尾部;

5) 重复 3)、4)步骤存储所有的规则;

6) 返回规则库的首地址,规则库的建立完毕。

算法3.2数据包的分类算法

1) 取出数据包的本地IP地址;

2) 本地IP地址与主机地址相比较;

3) 取出数据包的源端口sp、目的端口dp、协议类型pt;

i) 如果相等,则是本机要接收的,或本主机要发送的数据包,进入下一步;

ii) 如果不相等,则不是本机要接收的,或本主机不允许发送的数据包,丢弃该数据包。

4) Hash运算,得到Hash表的入口地址;

5) 取出数据包的外地IP地址与Hash表中存储的信息相比较;

i) 如果对应Hash地址的值为NULL,则丢弃该数据包;

ii) 如果对应Hash地址中只存入一个外地IP 地址,则数据包的外地IP地址直接与其相比,匹配则按照预先设置的规则对数据包进行处理,不匹配则丢弃该数据包;

iii) 如果对应Hash地址中存入多个外地IP地址,则数据包的外地IP 地址依次与其相比,直到匹配为止则按照预先设置的规则对数据包进行处理,不匹配则丢弃该数据包。

规则库的建立和数据包分类过程两个部分是不可分割的整体,规则库的建立是数据包分类的前提,两个过程都用到了相同的Hash函数,前者由Hash运算得到存储外地IP地址的Hash地址,后者由Hash运算来定位Hash地址,判断这个地址是否存储了与之相比较的外地IP地址,如果有则数据包被预置规则分类。

下面给出理论证明,证明该算法的准确性。

定理3.1 由算法3.1建立规则库,凡是进出主机的数据包依据算法3.2,都能被已建立的规则库分类。

证明:符号约定:inip代表本地IP地址,outip代表外地IP地址,sp代表源端口,dp代表目的端口,pt代表协议类型,p代表数据包,hostip代表主机IP地址。假设规则库R存储N条规则,为了减少哈希冲突,采用拉链法,规则库实际大小为M(M比N大20%左右的素数)

1)规则库的建立

R={outip1, outip2, …… ,outipN}

p=

Np={p1, p2, ……, pN}

对于任意Pi∈Np, 1?燮i?燮N;

Hash(spi,dpi,pti)+(spi^pti+dpi^pti)=HashAddi //得到Hash表的地址

pj∈Np, 1?燮j?燮N, 且j≠i//outipi存储在HashAddi

如果 Hash(spj,dpj,ptj)≠Hash(spi, dpi,pti)//无哈希冲突

则HashAddi=outipi//在HashAddi仅存储outipi①

如果Hash(spj,dpj,ptj)=Hash(spi,dpi,pti)//哈希冲突

则HashAddi={outipi, outipj} 在HashAddi仅存储outipi,outipj两面条规则,且outipj链接在outipi后面,依此类推,有多少哈希地址相同的就在同一地址存储多少规则②

其它哈希地址置空NULL

规则库建立完毕

2)数据包的分类

对于进出主机的任意数据包p,取出包头的五元组信息,即

P=;

如果inip≠hostip //丢弃该数据包

如果inip=hostip //进行下步处理

Hash(sp,dp,pt)+(sp^pt+dp^pt)%M=HashAdd //得到Hash地址

如果HashAdd=HashAddi

由①得,必然有HashAddi=outipi,如果outip=outipi, 则该数据包被规则分类,否则丢弃该数据包

由②得,必然有HashAddi {outipi, outipj, ……},如果outip∈{outipi, outipj, ……},则该数据包被规则分类,否则丢弃该数据包

证明完毕

上述证明了该算法可以准确的对数据包进行分类,另外也可以看出虽然在包分类的过程中,用到了数据包的五元信息,通过一次比较和一次Hash运算,最终在规则库中只存储了外地IP地址,因此不但从五元降到了一维,也减小了存储空间,提高了包分类的效率。

定理3.2 基于Hash函数的五元一维包分类算法优于线性查找算法

证明:假设规则库中存储了N条规则,线性查找的平均查找长度为

ASLSS=P1+2P2+ … +(n-1)Pn-1+nPn

在等概率的条件下:pi=1/n, 即ASLSS=1/n(1+2+ … +n) C (n+1)/2

假设规则库的Hash表无哈希冲突,可一次定位,则基于Hash函数的五元一维包分类算法的平均查找长度为:ASLSS=1

假设规则库的Hash表存在哈希冲突,在最坏情况下,m个无哈希冲突(1

那么,

因为n>m>1,所以,即基于Hash函数的五元一维包分类算法优于线性查找算法成立。

3 算法性能分析

数据包分类算法的性能评价,通常从空间复杂度、时间复杂度和是否易于更新等多个方面去考虑。下面从这三个方面分析本文设计的算法性能。

3.1 时间复杂度

Hash算法在理论上,它的时间复杂度是O(1),但实际上由于冲突的存在,它的平均查找长度将会1大。该算法采用拉链法解决冲突,由于拉链法查找就是在单链表上查找,单链表中第一个结点查找1次,第2个结点查找2次,其余依次类推。由于在构造Hash函数时,充分考虑了第个域的信息,降低了Hash冲突的概率,因此在同一哈希地址存储的规则个数也不会太多。

3.2 空间复杂度

本文的算法占用空间主要是用来存储32bit的外地IP地址,空间大小主要与哈希冲突的数目有关,哈希冲突越多点用空间越多。由于存在哈希冲突的情况,所以空间大小不能精确预计。但是坏蛋其它算法把五元组都存储相比,还是有了质的提高。

3.3 是否易于更新

由于Hash函数具有一步定们的特点,所以该算法易于更新。当增加或者删除规则时,只需要进行局部操作,不会影响整个结构。更新实际上是对Hash链表进行操作,所以更新的时间复杂度为O(1),具有更新速度快的特点。

4 结束语

本文根据Hash函数快速查找、快速定位的特性,提出了一种基于Hash函数的五元一维包分类算法。虽然此算法是基于数据包的五元组,但最终存储在规则库中的只有外地IP地址,减小了存储空间,提高了包分类效率,并且给出了算法准确性、快速性的理论分析。

参考文献:

[1] 朱雁辉.Windows防火墙与网络封包截获技术[M].北京:电子工业出版社,2002:119-131.

[2] Pankaj Gupta,Nick Mckcown.Algorithms for Packet Classification[C].IEEE Network.March,2001.

[3] Xue hong.IP Address Lookup and Packet Classification Alogrithms[D].Ottawa,Ontario,Carleton University,2003:43-45.

[4] 林闯,单志广,任丰源.计算机网络的服务质量(Qos)[M].北京:清华大学出版社,2004:119-120.

[5] 徐恪,徐明伟,吴建平,喻中越.IP分类技术研究综述[J].电子学报,2001(2):773-779.

[6] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2004:214-262.