拒绝服务攻击下的概率包标记IP追踪算法研究

拒绝服务攻击下的概率包标记IP追踪算法研究 工 7‘支698 学校代号:10532 学 号:S07102029 密 级:普通 湖南大学硕士学位论文 拒绝服务攻击下的概率包标记 IP追踪算法研究 -_-_II??r o ResearchonProbab订istic Packet ForIPTraceback Algorithm Marking UnderDenialofServiceAttack by SONG Donghui o??rLr--?(‘lf’。L;’‘70【-lr’ B(E( HuazhongAgricultureUniVersity 2007 Athesissubmittedin of satisfactionthe partial forthe of Requirementsdegree Masterof Engineering 1n Scienceand Conlputer Technology inthe GraduateSchool of Hunan UniVersity SuperVisor ProfessorLI uan Lij May，2010 ???―??1( j，((-―?((， 湖南大学 学位论文原创性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所 取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名:阜垂督 日期:砌年‘月?日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1、保密口，在 年解密后适用本授权书。 2、不保密团。 请在以上相应方框内打“,” 作者签名:1袈垂獬 日期: 如卜年占月二日 刷币签名(李肋晤 日期:弘fo年‘月?日 拒绝服务攻击F的概率包标记IP追踪算’法研究 摘 要 人类进入二十一世纪以来，随着科学技术的发展，网络信息技术也得到了飞 速发展。与此同时，网络中各种各样的安全隐患也层出不穷。尤其是近几年来， 由于拒绝服务攻击易于实施，破坏性大，已经成为了网络中最具威胁性的攻击方 式之一。为了从源头上制止拒绝服务攻击的发生，IP追踪技术作为应对拒绝服务 攻击的重要手段已经成为目前网络信息安全领域的一个研究热点。 本文首先介绍了拒绝服务攻击的原理，以及一些具有代表性的拒绝服务攻击 方式。随后对目前的各种IP追踪技术进行了概述，并对现有的IP追踪技术进行分 类比较，分析了各自的优缺点。 本文对IP追踪技术中的包标记技术进行了深入的研究。在对各种概率包标记 技术进行重点分析的基础上，结合压缩边采样和自适应概率包标记技术提出了一 种改进的包标记 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。改进方案最大限度的利用了IP数据包包头的空间作为标记 域。在以往的包标记方案中，都有一个distance域同来记录数据包经过的路由器数 T0 目。改进方案充分利用了TTL TimeLive 域的功能，既将它用来代替以往包标 记方案中的distance域，也将它用来动态确定标记数据包的概率。由于算法只需要 两个有效分片就能就可以确定一条边，大大降低了算法的计算量，并且重构攻击 路径时无需事先知道上游网络拓扑信息。对该方案的收敛率，误报率等性能进行 了充分的分析后表明，该方案减少了能重构出路径时所需的数据包数量，具有很 好的收敛性能和较低的误报率。同时，为了进一步降低路径重构时的误报率，利 用多个hash函数，给出了算法的进一步改进，减少了IP地址验证时碰撞的 概率。 本文还通过减小边界路由器的标记概率，给出了算法的第三步改进，降低了自适 应概率包标记方案中边界路由器的标记负载，??并且不会降低自适应包标记方案的 收敛率。 最后，为了验证和评估改进方案的性能，本文在NS2网络仿真软件上对其进行 了模拟实验，并与其他包标记方案进行了分析对比。实验结果验证了方案的可行 性。 关键词:网络安全;拒绝服务攻击;IP追踪;包标记 II 硕上学位论文 ll-_l_l-_Il_ _l __ Abstract Withthe ofscienceand hasbeen deVelopment technology;network technology sinceweentered the the deVeloped same the rapidly twenty-firstcentury(At time，in networkVarietiesof in potentialsafetyproblemsemerge endlessly(Inparticular’in recent of is years，denial oneofthemost serVice DoS attack becoming threatening becauseitis to has problems destructiveness(Inorderto easylaunch，andgreat stop theoccurrenceof DoSattacksatthe traceback asan source，IP technologyimportant meanstodealwith DoSattackhasbec锄eahot inthenetworkinf(0mation topic field( security Inthis ofDoSattackandsome DoSattacksare paper，thetheory typical introduced current ofIPtraceback firstly(Then，the aresumma“zedand technologies classified( andtheir and are respectiVeadVantagesdisadVantages analyzed( Inthis schemesf(0rIP paper，packetmarking tracebackarestudied especially(Af(ter an that， schemeswhich improVedpacketmarking combinesofcompressededge fragment schemeand scheme sampling adaptiVe is probabilitypacketmarking basedonwe Variousof proposed f(ullyanalyzed kinds schemes(The packetmarking schemeimizestheuseoftheIP improVed headerasthe neld( packet space marking Inthe isadistance preVious fieldwhichisusedtorecord packetmarkingscheme，there thenumberof routers data new schemetakesI’ull of passedby packets(The advantage thefunctionof Tlo intheIP header(ItusesTTL TTL TimeLive neldpacket fieldnot to thedistance alsouseitto onlyreplace field，but setthe f(or probabilitynlarking newschemereduces packet the becauseit dynamically(The computationgreatly only needstwo efficient tobuildone andit doesn’tneedto fragments edge， the get network infomationinadvancewhen upstream topology theattack reconstmctingpath( Afjcerwe the ofthe showsthatthenew fullyanalyzedperfonnancescheme，it sCheme decreases thenumberof in andithas packetsrequired reconstruction， path good rateand10wfalse rate(In ordertofurtherreduce conVergence positive thefalse ratewhen the positiVe use ofhash reconstructing functionsto path，wemultiples further the reduces thec01lision when improVealgorithm(It probability IP verifying addresses(Thisalso the paper improVes the packetmarkingalgorithm byreducing oftheborderrouter(Itcan reducethe load markingprobability oftheborder making itdoesn’treduce router，and rateofthe conVergence adjustedprobabilistic packet scheme( marking ( orderto and eValuatethe the Finally，in Verify of perfo珊ance improvedscheme， III 于r 绝服务攻击下的概率包标记IP追踪笄法研究 this simulatestheschemewithsimulation we paper soRware，NS2(Andit compare with otherschemes(Thesimulations’resultsvalidate this paper’sfeasibility( Words:Network of Key Service Security;DenialAttack;IPTrackeback;Packet Marking IV 目 录 学位论文原创性声明和学位论文版权使用授权 书„„„„„„„„„„„„„((I 摘 要„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„II Abstract„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„((III 插图索 引„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„VII 第l章 绪论„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„一1 1(1 研究背 景„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„l 1(2 研究目的及意 义„„„„„„„„„„„„„„„„„„„„„„((1 1(3 国内外研究现 状„„„„„„„„„„„„„„„„„„„„„„„(2 1(4 本文的主要工 作„„„„„„„„„„„„„„„„„„„„„„„„„„(3 1(5 本文的结 构„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„4 1(6 ,J、结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„(5 第2章 拒绝服务攻击概述„„„„„„„„„„„„„„„„„„„„„6 2(1 什么是拒绝服务攻 击„„„„„„„„„„„„„„„„„„„„„(6 2(2 拒绝服务攻击的分 类„„„„„„„„„„„„„„„„„„„„„„„7 2(3 拒绝服务攻击的形 式„„„„„„„„„„„„„„„„„„„„„„„„„„(8 2(4 拒绝服务攻击的发展与防范技 术„„„„„„„„„„„„„„„„9 2(5 小结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„((11 第3章 IP追踪技术研 究„„„„„„„„„„„„„„„„„„„„„„„((12 3(1 IP追踪的定 义„„„„„„„„„„„„„„„„„„„„„„„„:„„„„„„12 3(2 IP追踪技术的分类方 法„„„„„„„„„„„„„„„„„„„(13 3(3 各种IP追踪方法介绍与分 析„„„„„„„„„„„„„„„„„14 3(3(1 包日志 1099ing „„„„„„„„„„„„„„„„„„„„14 3(3(2 ICMP报文消息 ICMPTraceback „„„„„„„„„„„„„„„„((15 3(3(3 链接测试法 LinkTesting „„„„„„„„„„„„„„„„16 3(3(4 重叠网络 OverlayNetwork „„„„„„„„„„„„„„„„„„„((18 3(4 数据包标记方法的研究„„„„„„„„„„„„„„„„„„„19 3(4(1 节点采样方 法„„„„„„„„„„„„„„„„„„„„„20 3(4(2 边采样和压缩边采样方 法„„„„„„„„„„„„„„„((21 3(4(3 高级包标记和认证包标记方 法„„„„„„„„„„„„„„25 3(4(4 自适应的包标记方 法„„„„„„„„„„„„„„„„„„„„26 3(5 小结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„((28 第4章 概率包标记方法的改进„„„„„„„„„ _„„„„„„„„„(29 V 扣绝服务攻击下的概j簪包标记IP追踪算法研究 4(1 改进方案的介绍与分 析„„„„„„„„„„„„„„„„„„„(29 4(1(1 4(1(2 IP包头编码方 案„„„„„„„„„„„(„„„„„„„„„3l 4(1(3 标记算法„„„„„„„„„„„„„„„„„„„„„„„„„„„„„32 4(1(4 受害者处的重构算 法„„„„„„„„„„„„„„„„„„„33 4(2算法性能分 析„„„„„„„„„„„„„„„„„„„„„„„„„„„„((34 4(2(1 计算量„„„„„„„„„„„„„„„„„„„„„„„(35 4(2(2 收敛率„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„(36 4(2(3 误报率„„„„„„„„„„„„„„„„„„„„„„„„36 4(3 算法的进一步改 进„„„„„„„„„„„„„„„„„„„„„37 4(3(1 进一步降低误报 率„„„„„„„„„„„„„„„„„„„„37 4(3(2 减轻动态概率包标记时边界路由的负担„„„„„„„„„„„38 4(4 小结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„((39 第5章 模拟实 验„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„41 5(1 NS2仿真环境„„„„„„„„„„„„„„„„„„„„„„„41 5(2 仿真过 程„„„„„„„„„„„„„„„„„„„„„„„„„„„„(42 5(2(1 对NS2进行修改„„„„„„„„„„„„„„„„„„„(42 5(2。2 网络拓扑„„„„„„„„„„„„„„„„„„„„„„一45 5(3 实验分 析„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„47 5(3(1 收敛性能„„„„„„„„„„„„„„„„„„„„„„„„„47 5(3(2 计算负载„„„„„„„„„„„„„„„„„„„„„„(47 5(3(3 误报性能„„„„„„„„„„„„„„„„„„„„„„„„„48 5(4 小结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„((49 总结与展 望„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„ „一50 本文的工作重点与创新 点„„„„„„„„„„„„„„„„„„„„(50 研究展 望„„„„„„„„„„„„„„„„„„„„„„„„„„„一51 参考文 献„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„(52 致 谤 „„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„56 附录A攻读学位期间所发表的学术论文目 录„„„„„„„„„„„„„„57 VI 硕J二学位论文 插图索引 1(1全文组织结构 图„„„„„„„„„„„„„„„„„„„„„„„„(4 2(1攻击原理示意 图„„„„„„„„„„„„„„„„„„„„„„(6 2(2DDoS攻击示意 图„„„„„„„„„„„„„„„„„„„„„„„„„„„„7 2(3DDoS攻击的分类„„„„„„„„„„„„„„„„„„„„„(7 2(4DoS攻击的层 次„„„„„„„„„„„„„„„„„„„„„„„„„(8 2(5三步握手协议和TCPFlood对比图„„„„„„„„„„„„„„(9 3(1网络攻击示意图„„„„„„„„„„„„„„„„„„„„„13 3(2按追踪的时间对IP追踪技术分 类„„„„„„„„„„„„„„(14 3(3 5 SPIE结构 图„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„(1 3(4输入调试ID算法流程图„„„„„„„„„„„„„„„„„„(16 3(5可控泛洪CF算法流程图„„„„„„„„„„„„„„„„„„17 3(6重叠网 络„„„„„„„„„„„„„„„„„„„„„„„„„„„一18 3(7节点采样算法流程图„„„„„„„„„„„„„„„„„„„20 3(8边采样算法流程 图„„„„„„„„„„„„„„„„„„„„(22 3(9以异或形式表示边信 息„„„„„„„„„„„„„„„„„„„„„„23 3(10标记信息的分片„„„„„„„„„„„„„„„„„„„„„23 3(1 1利用标记域记录边信息„„„„„„„„„„„„„„„„„„24 4(1算法IP头标记域示意图„„„„„„„„„„„„„„„„„„„„„„„一3l 4(2标记算法流 程„„„„„„„„„„„„„„„„„„„„„„((33 4(3路径重构流程 图„„„„„„„„„„„„„„„„„„„„„„„„(35 5(1NS2的体系结 构„„„„„„„„„„„„„„„„„„„„„„„一42 5(2NS2网络模拟的基本流 程„„„„„„„„„„„„„„„„„„(42 5(3NS2中节点的结 构„„„„„„„„„„„„„„„„„„„„„„„„„„((44 5(4网络仿真拓扑 图„„„„„„„„„„„„„„„„„„„„„„„„(45 5(5几种方案路径重构所需数据包数目的比 较„„„„„„„„„„((47 5(6算法的收敛时间比 较„„„„„„„„„„„„„„„„„„„„„„„„„(48 图图图图图图图图图图图图图图图图图图图图图图图图图图图 5(7误报率比较„„„„„„„„„„„„„„„„„„„„„„„„48 VII 硕二l:学位论文 第1章绪 论 1(1研究背景 人类进入21世纪以来，随着科学技术的迅速发展，Internet已经深入到我们生 半年，我国宽带接入用户总数达到9348(2万户;截至2009年6月底，我国网民规模 已达3(38亿，居世界首位。近几年来，我国的互联网产业发展势头迅猛，各种各样 的网络新业务不断出现，人们的日常生活已经和互联网紧密地结合了起来，对互 联网信息的依赖越来越大，但与此同时，网络中潜在的安全隐患也层出不穷。所 以网络安全就成为了我们要面临的一个非常严峻的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。如何保护通信网络中的 数据和信息已经变得越来越重要。 表1(1显示了在互联网中各种不同攻击所占据的比例，从表中显示的数据可见， 当今的Intemet从底层的基础结构到上层的应用层无时不刻都在受到安全威胁，经 常受到恶意攻击?。根据2009年中国互联网网络安全报告显示，2009年，针对我 国境内互联网基础运行设施的攻击主要是拒绝服务攻击。仅根据l0月份辽宁、河 北等地运营商通报的情况来看，拒绝服务攻击中一般流量攻击次数约占86,，较大 流量攻击次数约占12,，大流量攻击次数约为2,;上述攻击目标多指向IDC的服 Date 务器，其中较大或较大以上流量攻击通常会对lDC IntemetCenter 业务以及 其承载互联网增值业务信息系统造成影响。防范拒绝服务攻击特别是分布式拒绝 服务攻 DDoS 是互联网企业安全运营亟需解决的一个难题心1。 表1(1互联网各种安全问题的发生比率 1(2研究目的及意义 of 在互联网中各式各样的攻击方式中，拒绝服务 DenialService，DoS 攻击以 Denialof 及分布式拒绝服务 Distributed 造成的后果往往非常严重。根据CERT ComputerResponse EmergencyTeam 的统 于fj绝服务攻。打下的概:钲包标记IP追踪算法研究 计，拒绝服务攻击的发生率在近几年有明显的增加，根据2006年美国计算机安全 研究所 ComputerSecurity 损失。其中，DoS攻击占据了25,口1。 2009年7月，发生了一系列劫持美国和韩国常用网站的攻击事件。在长达一周 的分布式拒绝服务攻击中涉及了从成百上千台计算机向大量网站发送大量请求， 使得网站变得不堪重负而导致瘫痪。在这周中由于受到攻击而导致在某一时间脱 机的网站有美国运输部和财政部网站，美国联邦贸易委员会网站，韩国总统的家 庭网页，韩国国民大会和美国空军网站。事后证明，黑客采用的就是DDoS攻击。 展，DoS,DDoS攻击也呈现出一些新的特点。急需有效的防御措施。 对于各种不同的网络攻击方法，DDoS攻击由于其实现容易、追踪困难、后果 严重，而成为网络安全的重大威胁。要想迅速地解决该问题，找到攻击源是很重 要的，同时这也有利于法律部门调查取证、追究攻击者的法律 责任 安全质量包保责任状安全管理目标责任状8安全事故责任追究制幼儿园安全责任状占有损害赔偿请求权 。学术界对其 展开了广泛的研究。但是，要准确的确定一个数据包的源地址是非常困难的。由 于IP协议中最脆弱的策略就是允许源主机自己填写IP报文的源地址域， 而在TCP,IP 协议中并没有提供一种机制来验证源IP地址的真实性。还有，目前网络体系的无 状态特性，以及路由体系基于目标地址，导致数据包的源地址并不能确保可靠。 而路由器转发数据包时不 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 源地址的有效性，且在转发后也并不做任何记录， 又使得对于DDoS攻击的防御，无论是追踪攻击源还是过滤都很难进行。这就给攻 击者以可乘之机。 在研究人员提出的各种方案中，IP追踪作为对付DDoS攻击的重要手段之一， 逐步成为研究的焦点。所以，为了从源头上制止攻击的发生，也为了法律部门调 查取证追究攻击者的相关责任，对攻击者起到威慑作用，追踪攻击源的研究成为 目前网络信息安全领域的一个研究热点。 1(3国内外研究现状 IP追踪又称IP回溯，英文为IPTraceback，即通过各种方法确定攻击数据流 的路径从而确定攻击源的过程。在互联网安全领域中，追踪DoS攻击源属于非常 困难的问题之一。国内对于IP追踪的研究起步较晚，主要以高校科研机构为代表 对国外较为成熟的技术进行了研究与改进。国外的研究则有了广度和深度上的提 高，主要集中在数据包的攻击路由追踪算法方面。主要分数据包标记和路由器记 录两大类。数据包标记算法的策略有很多，有基于概率统计的节点采样策略、边 采样策略等方案。路由器记录类主要有基于散列摘要的IP追踪算法。还有的研究 人员提出了重叠网络的概念，为路由器建立一个路由器专门用于追踪。但是，IP追 2 硕J二学位论文 踪的相关 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 或协议尚未形成。从理论到付诸于实际应用还在继续探索之中。 ‘ 1(4本文的主要工作 论文的主要工作从拒绝服务攻击的追踪方法上入手，主要介绍了现有的各种 IP追踪方案。重点深入研究了IP追踪研究领域中的重点:数据包标记方案。现有的 固定概率包标记方案中，每个路由器标记数据包的概率是一个固定值，路由器在 标记数据包时，后面的路由器可能会覆盖掉上游路由器的标记信息，这样一来， 里受害者收到的离攻击者最近的那跳路由器标记的数据包的概率就会很小，这就 是所谓的“最弱链"。由于“最弱链”的存在，受害者需要收到更多的攻击包才 能重构出攻击路径，这样不利于及时对拒绝服务攻击做出响应。虽然可变概率包 标记方案能够减小“最弱链"带来的问题，但是每个路由器标记数据报的概率的 计算要根据此路由器距离攻击者的距离来计算。所以针对这些问题，本文做了有 针对性的研究，全文主要的研究工作包括以下3个方面。 1(从拒绝服务攻击的追踪方法上入手，研究了现有的各种IP追踪方案，特别 是各种包标记方案。并分析了他们各自的优缺点。 2(为了包标记方案在重构路径时的收敛率，误报率，计算量等性能中找到一 个更好的平衡点，本文结合可变概率包标记和压缩边采样标记方案，提出了对现 有包标记方案的三点改 进: ( 1 充分利用了IP数据包包头的TTL域空间，提高了路径重构的收敛率。 在现有的包标记算法中，TTL域要么是用来动态确定标记数据包的 概率， 要么就是用来确定标记包经过的路由器跳数。本文结合可变概率包标记方案， 来动态确定路由器标记数据包的概率，这样就能在IP数据包包头中节省出更 多空间来记录标记信息，提高重构路径时的收敛率。 2 进一步降低了路径重构时的误报率。 本文采用多个hash函数对标记算法做了进一步改进。数路由器在标记数据 包的时候，采用多个hash函数来对IP值进行处理，重构路径时，利用多个hash 函数对重构得到的边信息进行验证，这样就降低了hash函数的碰撞概率，减 小了误报率。 3 降低了可变概率包标记方案中边界路由器的标记负担。 本文在不降低可变概率标记方案重构路径时的收敛性能的情况下，采用 减小边界路由器的标记概率，降低了边界路由器的工作负载。 3(为了对改进方案作出进一步验证，本文采用NS2网络模拟软件对其进行了 模拟分析。NS2是国内外学者最为常用的网络模拟工具，但是具体介绍实验方法 的文献不多。本文详细介绍了使用NS2模拟概率包标记方案的过程。 扣绝服务攻击下的概率包标记II】追踪算法研究 1(5本文的结构 本文共分为五章，文章结构和各章内容简介如下: 第一章为本文的相关研究背景和研究目的，分析了当前互联网的安全状况和 威胁，以此引出了本文的研究内容，研究目标和研究意义。同时简单地介绍了本 文的主要研究工作，并给出了本文的组织结构。 第二章讨论了拒绝服务攻击的原理、机制，简要介绍了DoS,DDoS攻击的防范 和对策。 第三章对IP追踪方案进行了详细的分析比较，重点对各种概率包标记方案进 行了研究，对各个方案的原理进行了理论分析，并对各自的性能和优缺点进行了 对比。 第四章在第三章的基础上，提出一种新的概率包标记方案，它能有效的 减小 了重构攻击路径时的收敛时间以及计算开销，大大提高了路径重构的效率。并对 其各项性能指标进行了理论分析。并且为了进一步降低改进方案在路径重构时的 误报率和及降低边界路由器的标记负担，给出了第二种和第三种改进方法。 第五章通过NS2网络模拟软件对本文的改进方案进行了模拟，并与以往的方 案进行了对比分析，模拟实验结果验证了方案的可行性。 最后一部分为总结与展望，对全文所作的工作进行了总结，对以后还需进一 步完善和研究的地方做了介绍。全文的组织结构如图1(1所示。 图1(1全文组织结构图 4 硕1:学位论文 1(6小-结 本章主要对目前网络安全的现状进行了简要的介绍，具体指出拒绝服务攻击 是当今乃至未来网络安全中威胁最大的攻击方式之一。对其作出有效防范是具有 很大意义的。IP追踪技术作为防范拒绝服务攻击的一种有效手段成为了网络安全 研究领域的热点，我们简要介绍了IP追踪技术的现状和发展趋势。大致介绍了全 文的主要工作，在本章最后给出了全文的组织结构。 5 拒绝服务攻击下的概率包标“IP追踪算法研究 第2章拒绝服务攻击概述 2(1什么是拒绝服务攻击 ofService。拒绝服务攻击的原理是攻击者 拒绝服务 DoS 的英文全称是Denial 发送带有伪造源地址的数据包给受害者，根据TCP,IP协议的规定，受害者收到数 据包之后发出回复信息并等待确认，这个时候，受害者处于半连接状态。由于数 据包中的源地址是伪造的，确认信息不会发送到真正的攻击者，就会有大量的资 源浪费在半连接状态中，从而无法响应其它合法的请求，这就是拒绝服务。原理 图如图2(1所示: 受 害 者 图2(1攻击原理示意图 凡是能导致合法用户不能正常进行网络服务的行为都算是拒绝服务攻击。拒 绝服务攻击就是要拒绝合法用户对正常网络资源的服务访问，破坏网络活动的正 常运行，最终会使你的部分网络连接和网络系统失效，从而达到破坏的目的。简 言之，拒绝服务就是用超出受害者处理能力的大量数据包消耗可用资源，致使网 络服务瘫痪的一种攻击手段。在早期，拒绝服务攻击主要是针对处理能力比较弱 的主机，如个人PC，或是窄带宽连接的网站，对拥有高带宽连接，高性能设备的 网站影响不大。 但是在l999年底，伴随着分布式拒绝服务攻击的出现，高性能设备网站也面 临遭受严重的损失威胁。DDoS攻击是攻击者联合多个攻击站点利用一批受控制的 机器向一台机器机器发起的攻击，且具有交大的破坏性因此，这就是分布式拒绝 服务攻击 DDoS ，分布式拒绝服务也被称之为“洪水攻击”。图2(2是一个典型的 DDoS攻击网络结构图，该图说明了在攻击中攻击者为了掩饰自己不被发现， 首先 入侵一些主控端，在其中植入DDoS的攻击程序，然后主控端继续控制大量的傀儡 机，发动对受害者的攻击。傀儡机向受害者发送大量的伪造或随机的源地址网络 数据流，??由于攻击流中的源地址是伪造的，所以攻击者可以很好的隐藏在主控端 之后。 6 硕一L学位论文 者 图2(2DDoS攻击示意图 2(2拒绝服务攻击的分类 拒绝服务的攻击方式有很多种，如图2(3所示。 DDoS攻击 按影响分 入侵的脆弱性分 l按 徊艟 破坏服务 J速 型 降低服务 曼堂!:鱼堡曼1 分 叱LIJ按 按扫描秉略分 按包内容和受害者 ,速率的变 I服务的关系分 化机制分 M囹 咂塑亟 ?不葡面目 r蕊 r 堕鳖塑塞I 直接 兰一磋一 按繁殖机制分 主机资源耗尽 反弹 一圃圈团圈圃卿一 图2(3DDoS攻击的分类 一般我们根据其攻击的手法和目的不同，分为两种不同的形式。一种是以消 耗目标主机的可用资源为目的，使目标服务器忙于应付大量非法无用的连接请求， 占用了服务器绝大多数的资源，使服务器无法对正常的请求再做出及时响应。这 种攻击主要利用的是网络协议或者是系统上的一些特点和漏洞进行攻击的，主要 Flood、Land等H1。针对这些漏洞的攻击，目前在 的攻击方法有死亡之ping、SYN 网络中有大量的现成工具可以利用。另一种拒绝服务攻击是以消耗服务器链路的 有效带宽为目的的，攻击者通过发送大量的有用或无用数据包将整体链路的带宽 全部占用，从而使正常的合法用户请求无法通过链路到达服务器。 7 拒绝服务攻击下的概牢包标记lP追踪算法研究 2(3拒绝服务攻击的形式 DoS攻击通常在以下5个层次上进行哺1，如图2(4所示。 图2(4DoS攻击的层次 1(消耗设备资源:攻击者消耗掉诸如CPU利用率、内存之类的系统资源来达 到攻击的目的。如果攻击者拥有一定的系统资源的合法访问权，那他就可能会滥 用这个权利来消耗掉额外的资源。例如:发送垃圾邮件。攻击者发送大量的垃圾 邮件，直到邮箱服务器被塞满。还有让日志记录满载等方式。 2(利用操作系统的漏洞:例如，一般服务器都有关于账号锁定的安全 策略， 如果某个账户连续3次登陆失败，那么这个账户将被锁定。攻击者利用合法账户去 错误操作造成登陆失败使合法账号被锁定，那么真正的合法用户就不能再正常使 用这个账号了。 3(应用程序漏洞:再优秀的程序员也会出现失误，编写程序代码时难免会有 疏漏。目前许多流行的攻击工具都是利用软件的开发缺陷和漏洞实施攻击的，比 如溢出攻击就是利用程序员没有应用严格对变量进行定义，可以使赋值超出规定 而造成内存的溢出。 4(网络带宽的消耗:这类攻击方式使用大量符合协议的正常服务请求， 消耗 掉某个网络的所有可用带宽。如HTTP协议是无状态协议，攻击者构造大量搜索 请求，这些请求耗费大量服务器资源，导致无法响应合法用户的正常请求。 5(利用协议漏洞的攻击:攻击者利用网络通信协议在最初设计时的局限性导 致的不足实施攻击，如SYNnood攻击就是通过破坏TCP三次握手过程来进行拒绝 服务攻击哺1。 目前最常见的就是洪水攻击，它是向目标发送大量数据包，使目标无法处理 ?? 正常的数据包，(DDoS攻击就一般表现为洪水攻击。典型的攻击有以下几种: 1(TCP Flood，这是目前最常见的DDoS攻击的方法。 8 硕上学位论文 SYN 伪 客 服 攻 SYN服 造 S?呵从CK SYN,ACK 户 一 务 击 务 IP 端 ACK 器 者 器 源 A 正常的握手情况 B TCPFlood 图2(5三步握手协议和TCPFlood对比图 DDoS攻击中，使用TCPFlood的比例占到攻击总量的90,以上，TCP Flood利 用的是TCP中的三步握手协议 图2(5A 。攻击者会伪造源IP向服务器发送大量的 TCP连接请求，服务器在应答SYN,ACK的同时保存一个半开的TCP连接 图2(5B ， 当打开的半开TCP连接达到最大限制数时，服务器将无法响应正常的TCP连接请 求，这样就达到了攻击的目的"]。 的网络的广播地址发送一个Ping分组 echo请求 ，同时把源地址伪造成受害者的地 址，目的地址设这个网络的广播地址，这个网络中的所有主机收到这个请求报文 后，会向受害者发出echo应答包，这样大量同时返回的响应数据包会造成目标主 机带宽严重拥塞，甚至完全不可用?】。 3(UDP nood攻击，UDP 行攻击的，又可称为UDP Dos攻击。它的原理与Smur瞰击相同，都是发往广播地 址的反射式攻击。只不过其发送的是UDP echo消息。攻击者伪造源IP地址，向服 务器发送大量的无用请求数据包，占用服务器的网络和主机资源，如果服务器提 供这项服务，那么将产生大量应答包，否则也会产生ICMP端口不可达报文，阻塞 网络，达到拒绝服务攻击的目的?1。其他的DDoS攻击类型还有ICMPFlood和分布 式反射拒绝服务攻击 DRDoS 等等。这里就不再进行赘述。 2(4拒绝服务攻击的发展与防范技术 随着技术的发展，时代的进步，攻击技术也在不断更新变化，目前呈现出如 下几个趋势: 1(自动化程度越来越高。 攻击者在DDoS攻击技术的多个方面都提高了自动化的程度。实现了大范围 地自动扫描，对扫描到的较弱的系统进行自动攻击并安装DDoS攻击的工具，最 后自动发动攻击。比如，攻击者已经开发出了能够使用脚本自动扫描自动挖掘自 动安装的攻击工具。 2(目标范围更大。 以往的攻击更多的针对UNIX系统，而现在基于Windows的系统的攻击出现的 9 拒绝服务攻-li下的概j笨包标记JP追踪算法研究 越来越多，与其他的网络用户的管理员相比，Windows的终端用户通常在技术上更 低，安全意识更淡薄，保护他们的系统不被攻破的能力较低。 路由器和其他的网络设施也逐渐成为被攻击的目标，近些年，攻击者利用路 由器的情况越来越多。攻击者利用销售商提供的默认口令获得对一些配置和管理 比较差的路由器的非法访问。人们一般认为路由器不容易攻破，所以路由器受到 的监控较少。其他网络基础设施如域名服务器等也开始成为攻击者的攻击目标。 3(漏洞的发现到该漏洞被攻击者成功利用之间的时间间隔越来越短。 当系统的漏洞发布以后，攻击者能够很快研究出有效的攻击方法，编写出针 便利条件，大大缩短了DoS,DDoS攻击的准备时间; 与拒绝服务攻击的快速发展趋势相对应，拒绝服务攻击的防范面临如下的现 状: 1(由于互联网结构采用分布式的管理方式，在其上建立灵活合适的响应机制 比较麻烦。不同管理域之间还要进行进行合作，这带来了很大的困难。 2(缺乏DDoS防御系统的测试基准和平台。比较各种DDoS防御系统优劣需要 基准攻击数据库或者一套评估测试方法，目前这些方面还很不成熟，也没有一个 支持大规模DDoS攻击检测防御的实际环境存在。 3(由于DDoS攻击的源网络或中间网络没有直接受到DDoS攻击，如果需要配置 防御系统，会面临着许多协调方面的问题。 4(僵尸网络为DDos攻击建立了新的平台n们。 由于攻击者的攻击手段花样繁多，拒绝服务攻击的特点决定了防御它是一件 非常困难的事情。针对拒绝服务攻击的特点与破坏性，为了减小决绝服务攻击带 来的危害，拒绝服务攻击的对策主要可以分为三方面: Detection 和误用检测 Misuse 细的综述?利，这里就不再赘述。 2(减轻DoS攻击危害的目的主要在于缓解DoS攻击对受害者的影响，可以采取 两种方法达到此目的。一是过滤攻击性数据流，二是增强受害者的容忍性。 1 攻击过滤 攻击过滤是指在攻击发生时对攻击性流量进行过滤。Ferguson等提出的入口过 滤n朝 Ingress DistributedPacket 41。 Route-based Filtering 都属于攻击过滤策略n 2 增强受害者的容忍性 它的目的是增强受害者在受到攻击时的承受能力。此类方法在终端系统上使 用比较广泛。包括随机释放，SYNcookie，SYNcache，以及Client Puzzles，除了 以上方法外，缩短TCP握手的超时设置、增大TCP的半开连接栈的大小等均 属于增 lO 硕lj学位论文 强容忍性的方法n钉。通过增强容忍来应对拒绝服务攻击的方法不是太有用，因为 设备的资源有限，所以它的效果也非常有限。 3(IP Traceback技术。在攻击发生时和发生后，利用沿途路由器对攻击者的数 据包相关信息进行记录，再把记录提供给受害者进行分析，对真实的攻击源进行 追踪。这个方向也是当前研究的热点，同时也是本文研究的重点。各种IP追踪的 算法相继被提出，具体在第三章将有详细的讨论。 2(5小结 本章首先研究了拒绝服务攻击的原理，讨论了拒绝服务攻击的分类方法，对 一些典型的拒绝服务攻击方式进行了介绍和分析。根据网络安全技术的发展状况 给出了拒绝服务攻击在将来的发展趋势和特点以及相应的防范技术所面临的挑 战。 拒绝服务攻击下的概牢包标记IP追踪锋法研究 第3章IP追踪技术研究 由于IP协议自身的原因，IP包的源地址域没有做任何安全措施，人们可以在其 中填写任何内容。这一点就被攻击者充分利用，创造了DoS攻击。使用目前IP包 头的信息，想要追查到攻击者很困难。因为我们能确认攻击者的惟一信息就是源 IP地址，而这个地址又是伪造的，按照这个地址找到的肯定不是真正的攻击者。 IP追踪技术的目的就是要找到一个能追踪到发送数据包的源地址的方案。IP 追踪技术的设计目标是:定位攻击流的转发路径;在此基础上尽量减少路由器的 工作量;能向受害者提供有用的信息。本文中使用的追踪这个词，其英文翻译为 等，其实他们都是表达的一个内容。 3(1 I P追踪的定义 广义上来说，IP追踪并不局限于DoS,DDoS攻击，对于网络上的任一数据包， 中的IP追踪。它指当DoS,DDoS攻击发生时或攻击完成后，根据现有的信息以及 一定的机制、手段，识别出完整的攻击路径并且确定攻击来源。IP追踪可以对攻 击者的真实位置进行识别，对攻击者是一种威慑，也为追究攻击者的法律责任提 供了有利证据。如果IP追踪技术成熟的话，那么除了可以用它追踪和抑制DDoS攻 击外，它也能减少数据包欺骗、给互联网带来一个更和谐的环境。 为了更直观的说明IP追踪技术，我们先给出一个简单的攻击图 图3(1 来阐述 攻击模型。图中有三个攻击者 Ai ，7台路由器 硝 ，和一个受害者 V 。距离攻击 者最近的路由器分别是R5、R6和R7，大部分的IP追踪技术认为:找到这三个 路由器，就算找到了攻击者。 图中树根V代表拒绝服务攻击的受害者，V可以是一台主机，也可以是一个局 域网的边界设备。受害者V上游的路由器为Rl，是树根的第一层节点。对于每一 个路由器Ri，我们定义其直接上游节点为其子节点，如R2的子节点就有R3，R4两 个。树的叶子Ai代表潜在的攻击源。从叶子节点到树根V代表攻击包经过的路径， 至受害者V的攻击路径，攻击路径图就是由所有的攻击路径构成的图，IP追踪的目 标就是构造出这样一个攻击路径图。 12 硕十学位论义 Al 图3(1网络攻击示意图 61。 为了方便研究，IP追踪技术中有一些基本的假设n 1(一个攻击者可以生成任何数据包，同时会向攻击者发送大量数据包。 2(多个攻击者可能攻击同一个目标。 3(攻击者可能知道自己正被追踪。 4(数据包在传输过程中可能会丢失也可能失序。 5(攻击者到受害者之间的路由器是基本稳定的。 6(路由器的CPU和内存是有限的，所以处理是有开销的。 7(绝大部分的路由器是可信的。 3(2l P追踪技术的分类方法 目前，研究人员已经提出了多个追踪方案，这多种方案可以从多种不同角度 对其进行分类。如按照追踪的时间可分为在DoS攻击时进行追踪和在DoS攻击完成 后追踪。根据DoS攻击网络结构和准确度的高低，可分为定位到发起攻击的网络、 网络的边界路由器、攻击代理主机、攻击机、攻击用户，图3(2是按照追踪的时间 对IP追踪方案进行分类的一种方法n"。 拒绝服务攻-li下的概j钲包标记IP追踪算法桫f 究 路由器日志 数据包日志记录方法 基于haSh函数路径追踪sPIE 确定包标记DPM „„ IP 樱率璺婴PM 鬻 数据包标记 入口包标记 追 踪 基于代数多项式求解 方 攻击完成后追踪 法 -c脚报文消息 蒜笺裂,删 分 基于IPSec的动态安全关联法 类 链接测试 裟 重叠网络 攻击进行时追踪 图3(2按追踪的时间对IP追踪技术分类 根据IP追踪的主动程度，可以将现有的IP追踪技术分为两大类:主动追踪和反 应追踪。主动追踪技术为了追踪IP源地址，需要在传输数据包时准备一些信息， 并利用这些信息识别攻击源H1。主动追踪方法在数据包通过网络时记录追踪信息， 受害主机可以使用产生的追踪数据重建攻击路径，并最终识别攻击者。主动追踪 包括数据包记录、消息传递和数据包标记。而反应追踪却是在检测到攻击之后， 才开始利用各种技术从攻击目标反向追踪到攻击的发起点。必须在攻击还在实施 时完成它们，否则，一旦攻击停止，反应追踪技术就会无效。输入调试和可控泛 洪属于反应追踪措施。大部分反应追踪需要很大程度的ISP合作，这样会造成大量 的管理负担以及法律和政策问题，因此有效的IP追踪方法应该需要最少的或者根 本不需要ISP合作。 IP追踪技术的关键需求包括H引: 1(与现有网络协议的兼容;网络业务开销可以忽略;支持新增的实现; 2(与现有的路由器和网络结构兼容; 3(对付DDoS攻击的有效性; 4(在时间和资源方面的最小开销; 5(应该不需要ISP合作;追踪的成功不应该取决于攻击的持续时间。 3(3各种IP追踪方法介绍与分析 i 3(3(1包日志 1 oggng 的方法是在通过Intemet的关键路由器上记录数据包，(路由器具有日志功 能，可以 使用数据挖掘等技术从大量的记录日志中来确定这些数据包所经过的路径n引。后 14 硕士学位论文 来AlexSnoeren等提出了一个改进的数据包记录方法，称源路径隔离引擎 Path Isolation SPIE Source Engine 。他们不是存储整个数据包，而是只存储它的相 应固定部分的32位hash摘要。为了完成IP追踪请求，数据搜集网络和遍布不同网 络的分析代理可以提取重要的数据包，从而识别攻击的源头心叫。 踪管理端 STM 。DGA的功能是在路由器中用某种过滤器记录经过该路由器的每 个包的某些特定信息。SCAR负责处理网络中某一区域，它连接到该区域中的每 个DGA。STM是个中央管理者，它负责处理受害者的请求并从相关的SCAR中获 得路径信息。结构图3(3所示。 ’ 图3(3SPIE结构图 当服务器或者网络收到攻击时，通过自己的入侵管理系统来确认攻击包的特 收集本区内每个路由器的日志信息，并分析攻击包是否通过本区。如果是的话， SCAR判定攻击包经过的路由器并在本区内重构攻击路径。所有相关的SCAR把 重构好的那部分的路经传给STM，然后STM通过分析这些结果来重构出每条路 径。 该方案具有很好的事后处理能力，并且能够追踪单个IP数据包，但该方案要 求路由器记录经过的每个包的信息，路由器负担较重，路由器还要有足够的处理 能力和存储日志的空间，对网络资源的需求非常大。Tatsuya也提出了一种和SPIE 类似的IP Traceback方案，但需要相当大的存储容量并且难以用于高速网络瞳?。然 而，由于网络结构的分散性的特点，SPIE在整个网络中推广较难。 3(3(2l CMP CMP报文消息 ITraceback 产生ICMP信息包，把该数据包所经过的邻近路由器的内容复制进去。该ICMP 包拥有和被跟踪包相同的目的地址、相同的IP头以及路由器的入口和出口IP地 15 扣绝服务攻击下的概牢包标记IP追踪算法研究 址。这些信息就把数据包和其经过的路径上的一条边联系起来，只要受害者获得 足够的ICMP包，就能得出整个攻击路径。 但在当攻击进行时，发送ICMP报文消息会增加网络流量，随着ICMP流量的不 断变化增加或于与正常流量的差异性，它很可能会被路由器过滤掉或被速度限制 九。ICMP报文消息是建立在路由器的输入调试能力基础上的 指一个数据包与它所 到达的端口、MAC地址的联系能力 ，但有的路由器不支持该能力瞳们。 i nkTesti 3(3(3链接测试法 L ng 现在许多IP追踪技术都是从离受害者最近的路由器开始与其多个上游路由器 相互测试直到确定攻击流量来自哪个上游路由器，然后这个上游路由器再和它自 己的上游路由器重复这个测试过程，直至找出攻击源点。但这个方法只能用在攻 击进行时。 链接测试有输入调试 InputDebugging 和可控泛洪 Controlled Flooding 两种 常用的方案。 1(输入调试 InputDebugging 许多路由器都提供输入调试的功能。它允许管理员在一些出口点过滤特定的 数据包，并决定它们来自哪个入口点。这种特性可以被用来用IP追踪。图3(4给出 了输入调试的工作流程。 广莉n 来自于路由器 , ?僦言多一 ,, 王 : 上 覆疆丽面丽丽 根据输入端口和路由表 确定上游路由器IP I塞竺型坚皇塑I ? ? 图3(4输入调试ID工作流程图 输入调试的过程如下乜引: 1 首先受害者确定自己受到了攻击，通过分析这些攻击数据包的类型，产生 16 硕上学位论文 一个能描述大多数攻击数据包特征的攻击指示信号。 2 受害者以这个攻击指示信号不断地用电话与各个上游路由器的网络操作 者联系，让他们在自己的路由器安装相应的输入调试过滤功能。这个过滤器与受 害者的输入端口相对应。通过这种方式确定攻击流量所经过的上游路由器。接着 在上行路由器继续入流量调试过程。直到找到最终的攻击源或者到达攻击源所在 的ISP边界。 该方案的一个最大缺点就是管理负担太重。对网络管理人员的技术要求很高。 即使在自动跟踪的情况下，多个ISP间的通信和协调也是个问题，如果在进行追 踪的时候，某一网络的管理员不在或不愿意提供帮助，有时候就无法完成追踪。 2(可控泛洪法 Contr011edF100ding 该方法采用向连接发送大量报文 即洪水 来观察对攻击报文传输产生的影响。 受害者需要预先得到网络拓扑信息，强制处于上行路由的主机或者路由器向每一 个连接分别发送洪水。由于路由器的缓冲区是共享的，因此来自负载较重的某个 连接上的报文，丢失的概率会更大。这样，通过向某个连接发送“洪水”后， 观 察各连接上攻击报文减少的变化，就可以大致知道某条连接是否存在攻击报文乜们。 可控泛洪的工作流程如图3(5所示。 广翮 N 鼙 延否对受害者蔓勤, N 巡三三乡, j Y 磊丽霜莉习砸嗣 确定【二游路由器IP I I里竺型坚妻塑I - n翮 图3(5可控泛洪CF工作流程图 同其他的连接测试一样，与它的上游路由器重复这过程直至攻击源点。可控 泛洪技术虽然有他的优点和创新，但还是存在以下缺点: 1(这种方法最大的缺点是本身就是一种DoS攻击，对某些非攻击路径也进行 扣绝服务攻击下的概率包标记II 追踪算法研究 DoS攻击，可能会造成网络的拥塞甚至瘫痪。 ( 2(要求事先有网络的拓扑细节信息。 3(与所有连接测试一样，该技术只有在攻击正在进行时才有效。 4(连接测试本身操作就比较繁杂，当某一路由器在攻击路径中有着多个上游 连接时，选择哪条链路进行测试也很困难。 ‘ l Network 3(3(4重叠网络 Overay 重叠网络是由Stone等人心53提出的一种新方法。该方法利用物理连接、IP隧道 或第二层虚拟连接的方式将网络与边界路由相连。在网络中引入一个追踪路由器 TR Tracking 态配置网络所有接入路由器与TR之间建立IP通道，这样逻辑上TR与所有 边界路由 器形成一个星型网络 逻辑上的网络与真实网络重叠，故称重叠网络，如图3(6所 示 。然后这些可能的攻击包就被边界路由器直发到TR。重叠网络根据数据包进入 网络的入口来判断它来自于哪个边界路由器。数据包还会经过进一步检查，然后 决定丢弃或是转发。在数据包的终端，受害者通过重叠网络查到转发攻击数据包 进入追踪网络的那个边界路由器。 图3(6重叠网络 此方案的优点:不仅能追踪，还能通过丢弃攻击包起到防范的作用;从TR追 踪到接入路由器只有一跳的距离，与接入调试的方法相比，大大缩短了追踪 距离。 由于使用了动态路由技术，重叠网络方法可以适应网络内部结构的变化。 缺点是:需要接入调试，管理负担大，需要ISP之间的协作，如果攻击者控制 了边界路由器或与重叠网络连接的路由器，那么这些边界路由器可以不将攻击数 据包路由到重叠网络，从而追踪失效。 根据以上的介绍分析，表3(1给出了目前的IP追踪方案迸的直观比较。 18 硕，L学位论文 表3(1部分IP追踪技术性能比较 以上各种追踪方案各有优缺点，大都需要ISP运营商的直接支持，有的需要完 全掌握网络拓扑结信息。但是大多数的ISP供应商都不愿透露其网络拓扑结构信 息。ICMP追踪不需要事先知道网络拓扑信息，但是它会额外的增加网络负担:所 以，现在大多数实用的IP源追踪方案都建立在数据包标记算法的基础之上。本文 将在下面一节对现有的数据包标记技术进行详细介绍与分析。 3(4数据包标记方法的研究 包标记的主要思想是当数据包通过路由器时，路由器转发数据包的同时以一 定的概率在数据包中写入路由器的信息，这样虽然每个数据包只包括了路径的部 分信息，但是当攻击发生时会有大量的攻击数据包，从而使得受害者接收到攻击 路径上所有路由器的标记信息后能通过这些信息获得从攻击者到受害者之间的路 径信息，达到IP追踪的目的n8J。包标记方案是目前IP追踪研究的热点。该方法的 优点是网络负担不大，允许事后分析。缺点是部分技术需要修改协议，对接收的 攻击包有数量要求，存在攻击路径的误报。最早由SaVage等人做了比较深入系统 Packet 的研究，他们提出了一个叫做概率包标记 Probabilistic 法，该方法不论在路由器开销，实现难易还是与IP协议的兼容性等方面都有突出 的优势四。后来很多研究人员都是在此基础上进行研究，如，Song等人又在此基 ProbabilisticPacket 础上，提出了两个分别称为高级包标记 Advanced Marking 和带 ProbabilisticPacket 认证的包标记 Authenticated 61。 所以概率包标 Marking 的方法n 记方法也被称为基本包标记算法。 包标记算法由两部分构成:一部分是路由器上的算法，一部分是受害端 的算 包里的标记信息从离受害者处最近的路由器向上追踪，一级级的算出攻击包 所经 过的路由器。重构形象的描述了重新构造攻击路径的过程。下面本文将介绍 现有 的一些包标记方法。 19 打i绝服务攻击下的概率包标记IP追踪算法(|iJf究 3(4(1节点采样方法 节点采样标记方法的思想是路由器以一定的概率p将自己的IP地址填入到 数据包的某个相应位置，具体来说就是将IP地址写入IP报文头里预留的一个4字节 的“节点域"。假设数据包从路由器到达受害者需要d跳，对于到达受害者的攻 击性数据包，其包含攻击路径中离受害者距离d的路由器信息的概率为p 1垆 d。 它是一个严格递减函数，也就是说受害者收到的某个路由器标记的数据包的数量 随路由器离受害者地距离的增加而减少，因此，受害者将收到的带有标记信息的 数据包按照不同的标记按个数大小进行排序，就可以得出攻击路径。节点采样算 法在路由器和受害端的工作流程图如图3(7所示。 产生 0，1 范围 内的一个随机数x 人 , ,N V YI l将路由器IP地址写 l入报文头的节点域 1( ‘ 转发数据包 A 路由器上的工作流程 B 受害者的工作流程 图3(7节点采样算法流程图 示受害者，攻击路径的长度d表示攻击路径上的路由器个数。若路由器以固定概 率p标记数据包，攻击者发送的数据包总数为N。那么，怎么得出重构路径所需的 数据包数目呢?这就需要使用到概率论中的一个概率结论:赠券收集问题 coupon Collector ，下面给出证券收集问题的说明心引。 20 硕l:学位论文 有n种不同类型的赠券，每次从中取出一个，然后再放回去，需要把n种赠 券都至少取出一次所需要的期望次数为力ln 拧 +D n 次。如果某一次取出的赠券 在之前是从来没有取到过，那么这次取出就认为是成功的，这就意味着需要n次成 功的取出动作。我们把这n次的取出动作作为分界点，在这之间的取的次数定义为 xi，i的取值从l到n。总共取了x ?置次。我们可以得出x取成功的概率 为: 2―― BB:竺型 3(1 【j(I X服从以扔为参数的几何分布。所以有 E 置 二 3(2 p 从而得出 3(3 E x 喜E 五 喜i舞 行喜 刀111疗+。 刀 受害者收到一个距离攻击者为f跳的路由器标记的数据包的概率是 p 1一p 如7，当卢1时概率最小，假设攻击路径上所有路由器的标记包到达受害者的 概率都为p 1一p 如1，由于每个路由器的标记都是相互独立的，则一个确定的数据 包被攻击路径上一个路由器标记的概率至少是咖 1一p “，根据赠券收集问题我们 可以得出如下结论:受害者需要收到攻击路径上所有价路由器的不同标记包的期 望为d 1lld+D 1 。所以受害者重构出这条攻击路径所需的数据包的期望为: 、’ B4，、 7 咖 1一p 扣1 删， 篇 筹署p 1一p d-1 忽略常数D 1 ，得到 以? 芸知 3(5 我们可以看出，受害者要重构出攻击路径则要收受到足够多的攻击包的才行。 路由器采样过的报文。还有一点，节点采样不适合多个攻击者的情况，如果一个 路由器同时处于多条攻击路径中，并且在不同攻击路径中该路由器与受害者的距 离不同，那么在受害主机处无法根据采样特性进行路径重构。 3(4(2边采样和压缩边采样方法 由于节点采样只记录了路由器节点信息，没有记录路由器之间的连接信息。 Savage等又提出了边采样方法，该方法还确定路由器之间的连接信息来确定两个 路由器之间的传送方向。边采样算法还要在IP数据包包头中增加staIrt域和end 域用来存储边的两个相邻路由器的IP地址，另外再加一个distance域存储此条边 2l 打i绝服务攻击下的概率包标记IP追踪算:法研究 到受害者的距离n印，?引。 路由器以概率p标记数据包。如果路由器决定标记数据包，则把它的IP地 域的值为O，就说明上一跳的路由器刚刚标记了start域，那么这个路由器就把自己 构成了一条边信息。如果路由器不标记数据包且distance域不为0，则只需要把 ol。 distance域加1【3 边采样算法与节点采样算法在收敛率上的分析是一致的。我们对公式 3(5 一 阶求导可知，当p 1,d时，E?的上限最小，重构攻击路径所需的以攻击包数量 最少。p 1,d是概率包标记算法的最优概率。图3(8给出了便采样方案边采样方案 的流程图: 以受害者IP为根节 点，和三元组 起 点，重点，距离 构 造攻击路径树 1r 将一条边 P的起 点，终点，距离 插入到树T中 ’ r 对生成的树进行修剪 』 在T中，从根节 点 到每个叶子节点的 分支即为攻击路径 A 路由器上的工作流程 B 受害者的工作流程 图3(8边采样算法流程图 特，因为数据包在网络传输中，经过的路径一般不超过30跳，5比特空间可以满 有16比特，无法满足需要。为了压缩标记信息，Savage等人又提出了一个压缩边 界采样算法 CompressedEdgeFragmentSampling 。用一条边的两个路由器IP的异 硕(jj学位论文 或值 也称边ID 来代替边信息。如图3(9所示。 口n口n口n?n口 。口 Du 0 口“ ”? o D o n : a n D 0 ? ? 口 口 ? 口 圆础a口b aBb b 圆皿b口 C d 圆皿c? ?，。(( 叭鼢上 虮鼢c,, ?太 螋? 圆圆d 图3(9以异或形式表示边信息 压缩边界采样算法将一个边ID进一步分成8个8比特的分片，让一个数据包只 携带一个分片以及它在边ID中的偏移值和距离值。这种方法当面对多个攻击者时， 可能会有多个块具有同样的距离、同样的偏移信息。那么最终可能会出现错误组 合的组合。为了减少这种情况，用一个32比特的hash值作为校验码。把IP值与其 32比特的校验码间隔穿插得到64比特，奇数位为IP值，偶数位为校验码?引。然 后将这64比特信息分为8片，并将其分别编号为0、1、„„、7 偏移量 。 如图3(10 所示。 +IP地址 H嬲h校验码