2100100110000000C1001111010010BA10010110100100001100100110000000B100111101001011010010000第30卷第13期Vol.30№13计算机工程ComputerEngineering2004年7月July2004·基金项目论文·文章编号：1000—3428(2004)13—0026—03文献标识码：A中图分类号：TP393.08一种基于Patricia树的检测SynFlood攻击的方法陈杰，薛质，单蓉胜（上海交通大学信息安全工程学院，上海200030）摘要：分析了Synflood攻击的原理、攻击的方式及其基本特征。利用Patricia树进行SYN流量统计，并提出了改进的TCP连接状态检测。试验表明，该检测算法在占用很少系统资源的情况下，准确检测到Synflood攻击。关键词：拒绝服务；Synflood；Patricia树；状态检测AMethodtoDetectSynFloodAttackBasedonPatriciaTreeCHENJie,XUEZhi,SHANRongsheng(InformationSecurityEngineeringSchool,ShanghaiJiaotongUniversity,Shanghai200030)【Abstract】Thispaperanalyzesthetheory,attackmodelandthebasiccharacterofSynflood.Patriciabinaryradixtreeisusedtocountthenumberofthesynpackets,checktheconnectionstatebyanimprovedmethod.Inthisway,theSynfloodattackcanbedetectedwithfewresources.【Keywords】DoS；Synflood；Patriciatree；StatecheckingDoS（拒绝服务）攻击是一种利用TCP/IP协议以及系统本身的弱点和漏洞，发送特定的数据包，使得被攻击的目标崩溃或者资源耗尽而不能响应正常服务请求的一种攻击方式。Synflood[3,4]是其中典型的一种。这种攻击方式利用了TCP/IP协议的弱点[8]，具有破坏力大、隐蔽性强、攻击简单的特点，是现有网络服务的一个严重的威胁。本文提出了一种基于流量统计和状态检测，同时又能有效降低检测负荷的检测Synflood的方法。Synflood攻击的方式根据源IP地址的不同可以有以下3种：(1)使用本机的IP发送syn包；(2)假冒本网段中未在线的若干台主机的IP发送syn包；(3)随机伪造任意的IP地址发送syn包。如果不想暴露攻击源的话，一般不采用第1种方法，除非发动攻击的主机是即使暴露也无所谓的傀儡机。这时，这个IP将发送大量的syn包。这种现象在服务器端看来与正常的由一个繁忙的代理服务器产生连接的情况相似。第2种方法发动攻击的IP数量有限，为了达到拒绝服务的目的，每个IP必然用大量不同的端口发送大量syn包。这种现象与正常的多个代理服务器产生连接的情况相似。第3种方法可以假冒任意多个IP，每个IP只需要发送一个或者数量很少的syn包。这种现象与一般多用户的正常连接情况相似。第3种攻击方法隐蔽性强，而且即使检测出来也难以应对。但是，如果在网段出口设置成禁止非本网IP向外发送数据包，则这种方法就失效了。针对Synflood攻击的检测已经进行了不少研究[6,7]。在被攻击端进行检测的手段不外乎两种：一种方法是对syn数据包的流量进行统计。例如统计一段时间内到达的syn数据包的数量，或者统计连续到达的syn数据包的数量。如果统计值超过了一定的阈值，就认为发生了Synflood攻击。这种方法的缺点在于，虽然可以检测出Synflood攻击，但是却无法将Synflood攻击与大流量的正常连接区分开来，虚警率很高。另一种方法是维护所有的连接状态。如果存在大量的半flood攻击很有效的方法，唯一的缺点就是维护所有的连接状态代价太大。在经受Synflood攻击时，数千乃至数万个半开连接的维护将会极大消耗CPU和内存资源[5]。本文提出一种基于以上两种方式，同时只消耗有限资源的有效的检测方式。1基于Patricia树的Syn检测方法1.1Patricia树基本原理[1]使用Patricia树是本检测方法的重要手段。Patricia树是一棵满二叉树，即所有的中间结点都有两个子节点。Patricia树的每一个节点的关键字是二进制字符串。兄弟节点的关键字一定有相同的前缀。父节点的关键字是两个子节点关键字的公共前缀。所有叶节点的关键字长度相同而且是最大关键字长度。图1中，由1至2为添加一个叶节点，2至1为删除一个叶节点。A图1Patricia树叶节点的添加(删除）Patricia树的优点：采用二进制序列作为关键字的方法非常适合以IP地址为观察对象的统计工作。这时Patricia树的最大关键字长度为32，每个叶结点对应一个IP地址，而每...