（计算机应用技术专业论文）动静态结合的概率包标记技术研究.pdf

r 一 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：盔盘塾日期：兰! ! ! 年上月生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 作者签名：壅墨鳖导品签名垦型墨堡日期：丝年上月业日， r 一 摘要 随着互联网的普及，拒绝服务攻击已经成为网络安全的一个严重威 胁。如何精确定位网络攻击源具有非常积极的意义，目前已成为网络安 全研究的热点之一。论文主要研究概率包标记中的标记概率，解决了已 有的静态概率包标记方法不能快速重构攻击路径的问题。 论文在深入分析国内外概率包标记技术的基础上，提出了一种动一静 态结合的概率包标记方案。该方案在组内的各路由器之间具有静态概率 包标记的特性，而在组与组之间又具有动态概率包标记的特性，很好的 结合了两者各自的优点。从理论上证明了动一静态结合的概率包标记方案 在收敛性上比起已有的静态概率包标记方案有了很大的改进，路由器负 担比已有的动态概率包标记方案也有了明显的改善，而最弱链问题仍没 有得到解决。因此，进一步提出了一种改进了的动一静态结合的概率包标 记方案。该方案中每组中的路由器个数由四个改为两个。该方案很好的 解决了已有的静态概率包标记方案存在的最弱链问题。除了上述的收敛 性、路由器负担和最弱链问题这三个性能指标外，还提出了第四个性能 指标路由器上存放标记概率所需的存储空间。并证明了在储存和查 询路由器的标记概率时，动一静态结合的概率包标记方案要优于动态概率 包标记方案。 通过实验证明了动一静态结合的概率包标记方案在收敛性上虽然比 起动态概率包标记方案仍有不足，但比起静态概率包标记方案有了较好 的改进。实验结果表明与理论结果是基本上相吻合的，进一步验证了动一 静态结合的概率包标记方案的合理性和有效性。 关键词概率包标记，收敛性，最弱链，存储空间，路由器负担 a bs t r a c t w i t ht h ep o p u l a r i t yo ft h ei n t e r a c t ，d e n i a lo fs e r v i c ea t t a c k sh a sb e c o m e as e r i o u st h r e a tt on e t w o r ks e c u r i t y i t sn e c e s s a r yf o ru st op i n p o i n tt h es o u r c e o fn e t w o r ka t t a c k s ，w h i c hh a sb e c o m eo n eo ft h eh o ts p o tf o rn e t w o r ks e c u r i t y r e s e a r c hc u r r e n t l y t h ep a p e rf o c u so nt h ep r o b a b i l i s t i cp a c k e tm a r k i n gi nt h e m a r k i n gp r o b a b i l i t y s o l v e dt h ep r o b l e mt h a t e x i s t i n gs t a t i cp r o b a b i l i s t i c p a c k e tm a r k i n g s c h e m ec a l ln o tb eq u i c k l yr e c o n s t r u c tt h ea t t a c kp a t h f i r s to fa l l ，t h ep a p e ra n a l y s i sf u n d a m e n t a lt h e o r yr e l a t e dt ot h e p r o b a b i l i s t i cp a c k e tm a r k i n gt e c h n i q u e sa th o m ea n da b r o a d s e c o n d ，t h e p r o g r a mi sp r e s e n t e dac o m b i n e dd y n a m i ca n ds t a t i cp r o b a b i l i s t i cp a c k e t m a r k i n gs c h e m e t h es c h e m en o to n l yh a st h ec h a r a c t e r i s t i c so fs t a t i c p r o b a b i l i s t i cp a c k e tm a r k i n gb e t w e e nt h e v a r i o u sr o u t e r si nt h eg r o u p ，b u t a l s oh a st h ec h a r a c t e r i s t i c so fd y n a m i cp r o b a b i l i s t i cp a c k e tm a r k i n gb e t w e e n t h ed i f f e r e n tg r o u p s ，i tc o m b i n e dt h e i rr e s p e c t i v e a d v a n t a g e sv e r y w e l l c o m p a r e dw i t ht h ee x i s t i n gs c h e m e s ，w ep r o v e dt h a tt h en e ws c h e m eh a s b e e ng r e a t l yi m p r o v e do nt h ec o n v e r g e n c e ，t h eb u r d e no fr o u t e rh a sg r e a t l y i m p r o v e da l s o t h i r d ，c o n s i d e r i n gt h ew e a k e s tl i n kh a sn o tb e e nr e s o l v e dy e t a ni m p r o v e dd y n a m i c s t a t i cc o m b i n a t i o no ft h e p r o b a b i l i s t i cp a c k e t m a r k i n gs c h e m ew a sp r e s e n t e d i nt h i ss c h e m e ，i ne a c hg r o u pt h en u m b e ro f r o u t e rf r o mf o u rt ot w o t h es c h e m eh a ss o l v e dt h ew e a k e s tl i n kp r o b l e m st o t h es t a t i c p r o b a b i l i s t i cp a c k e tm a r k i n g s c h e m e s s u c c e s s f u l l y b e s i d e s c o n v e r g e n c e ，r o u t e r sb u r d e na n dt h ew e a k e s tl i n ko ft h et h r e ep e r f o r m a n c e i n d i c a t o r s c h a i np r o b l e m s ，t h ep r o g r a mp r e s e n t e dt h ef o u r t hc h a r a c t e r i s t i ct o t a r g e t t h es t o r a g es p a c ew h i c hr o u t e rm a r k i n gp r o b a b i l i t yo fs t o r i n gr e q u i r e d t h ep a p e rp r o v e dt h a ti nt h e s t o r a g e a n dr e t r i e v a lo fr o u t e r m a r k i n g p r o b a b i l i t y , d y n a m i c - s t a t i cc o m b i n a t i o no ft h ep r o b a b i l i s t i cp a c k e tm a r k i n g s c h e m ei ss u p e r i o rt od y n a m i c p r o b a b i l i s t i cp a c k e tm a r k i n gs c h e m e t h er e s u l to fe x p e r i m e n t sp r o v e dt h a t a l t h o u g hc o m p a r e dw i t ht h e d y n a m i cp r o b a b i l i s t i cp a c k e tm a r k i n g ，t h en e ws c h e m ei ss t i l lh a v ew e a k n e s s o nt h ec o n v e r g e n c e ，b u tc o m p a r e dw i t ht h es t a t i cp r o b a b i l i s t i cp a c k e tm a r k i n g ， t h en e ws c h e m eh a si m p r o v e dg r e a t l y e x p e r i m e n t a la n dt h e o r e t i c a lr e s u l t s s h o wt h a tt h er e s u l ti s b a s i c a l l yc o i n c i d e ，a n df u r t h e rv a l i d a t e sd y n a m i c s t a t i cc o m b i n a t i o no ft h ep r o b a b i l i s t i cp a c k e tm a r k i n gt h es c h e m e sl e g i t i m a c y h a n de f f e c t i v e n e s s k e yw o r d s p r o b a b i l i s t i cp a c k e tm a r k i n g ，c o n v e r g e n c e ，w e a k e s tl i n k ， s t o r a g es p a c e ，b u r d e no f r o u t e r 11一 1 i i 目录 摘要i a b s t r a c t ：】 i 第一章绪论一1 1 1 研究背景一1 1 2 国内外研究现状2 1 2 1 国外研究现状：2 1 2 2 国内研究现状4 1 3 本文的工作与组织结构5 第二章相关理论和技术7 2 1 概率包标记的标记与重构7 2 1 1 概率包标记的标记过程7 2 1 2 概率包标记的重构过程；8 2 2 概率包标记的标记概率与性能指标9 2 2 1 静态概率包标记的标记概率1 0 2 2 2 动态概率包标记的标记概率1 1 2 2 3 概率包标记的性能指标1 2 2 3 本章小结1 2 第三章动一静态结合的概率包标记方案1 3 3 1 动一静态结合的概率包标记方案的基本思想1 3 3 1 1 传统概率包标记的性能比较：1 3 3 1 2 一种动一静态结合的概率包标记方案1 4 3 2 动一静态结合的概率包标记方案的标记概率1 7 3 2 1 常用的确定路由器标记概率的方法1 7 3 2 2 采用距离域来确定攻击路径长度1 9 3 3 动一静态结合的概率包标记方案的标记算法与重构算法2 0 3 3 1 标记算法2 0 3 3 2 重构算法2 2 3 4 本章小结2 3 第四章动一静态结合的概率包标记方案的性能分析2 4 4 1 算法的性能指标一，2 4 4 1 1 最弱链问题2 4 4 1 2 收敛性2 9 4 2 路由器的性能指标3 5 4 2 1 路由器负担一3 5 4 2 2 路由器所需的存储空间3 6 4 3 本章小结3 8 第五章实验设计与结果分析3 9 5 1 实验设计3 9 5 2 实验及其结果分析4 1 5 3 本章小结：4 6 第六章总结和展望4 7 6 1 论文总结? 4 7 6 2 进一步的研究方向：4 8 参考文献4 9 致谢5 5 攻读学位期间主要的研究成果5 7 i l 硕七学位论文第一章绪论 1 1 研究背景 第一章绪论 从2 0 世纪6 0 年代术，美国军方开始建设的a r p a n e t ，到1 9 7 4 年问世的 t c p i p 协议，再到1 9 8 6 年美国国家科学基金会( n s f ) 在a r p a n e t 基础上组 建的n s f n e t ，都是形成因特网( i n t e m e t ) 的基础l l 】。随着信息技术的飞速发展， i n t e m e t 早已经成为一个覆盖全世界的“全球网 。如今，i n t e r n e t 已成为“信息 社会 的重要基础设施，和我们的日常生活联系得越来越紧密。人们对i n t e m e t 的依赖性也越来越强，它已经成为人们生活中不可缺少的一个部分。据中国互联 网络信息中心2 0 1 0 年中国互联网络发展状况统计报告，截至2 0 0 9 年1 2 月 3 1 日，中国网民规模达到3 8 4 亿人，较2 0 0 8 年底增长2 8 9 0 , 6 ，上网普及率达到 2 8 9 。网民规模持续扩大，互联网普及率平稳上升。网民每周上网时长继续增 加，人均增加2 1 小时【2 1 。目前网民的网络应用行为主要有网络新闻、搜索引擎、 。 即时通信、博客、网络游戏、网络音乐、网络购物、网上支付、网络金融等具体 应用类型。 调查显示：5 6 6 的网民遭遇过木马病毒的攻击，3 1 5 的网民遭遇过帐号 密码被盗的问题；调查同时显示：6 5 9 的网民认为“网络交易不安全”。这些问 题无疑制约着网络消费类应用的深度发展1 2 1 。 据报道，韩国政府部门网站在内的许多韩国网站在2 0 0 9 年7 月9 日傍晚再 次遭到黑客攻击，已有多个网站瘫痪，韩国方面认为，这是自7 日晚开始的分布 式拒绝服务( d i s t r i b u t e dd e n i a l o f - s e r v i c e ，d d o s ) 攻击的第三波行动【3 1 。韩国 有关部门宣布，从9 日下午6 时开始，韩国国家情报院和国民银行网站无法被访 问。韩国国会、国防部、外交通商部等机构的网站一度无法打开，或打开速度极 慢。此外，驻韩美军网站也出现链接不稳定的现象。7 日晚间发生的d d o s 攻击， 同时对韩国总统府、国会、国情院和国防部等国家机关，以及金融界、媒体和防 火墙企业网站进行了攻击【3 】。由此可见，网络安全己成为关系国家安全的重大战 略问题，研究网络安全的问题是极为重要的。 从学术意义角度讲，网络安全可以看成是攻击者和防御者之间的竞争和比 赛。按照攻击的性质、手段、结果等可以将网络攻击大致分为窃取机密攻击、非 法访问、计算机病毒、恶意攻击等几大类1 4 1 。而恶意攻击一类中最为突出的就是 拒绝服务( d e n i a l o f - s e r v i c e ，d o s ) 攻击【5 l 。 d o s 攻击是在一定时间段内直接或者通过跳板向目标网络发送大量的特定 起到威慑的作用，具有主动的意义。追踪的结果既可以作为继续追踪真正攻击者 的基础，又可以为其他的对策( 如过滤) 提供信息，增强防范效果，还可以作为 从法律上追究攻击者责任的证据。i p 追踪研究的基本思路是：大多数i p 包头源 地址是虚假的，但每个i p 包都必须经过从攻击者到受害者之间的路由器转发。 借助路由器对数据包进行标记，从而根据收到的数据包重构出攻击路径1 9 j 。 研究表明很多入侵者常常会因为责任追究的危险而受到威慑，他们非常害怕 失去匿名性1 1 0 1 。如果能追踪到攻击者，攻击事件就会少很多。但由于攻击者目 前大多利用傀儡机发起攻击，要找到真正的攻击者是很困难的。因此，我们主要 考虑的是追踪到攻击的发出点( 攻击性数据包的源头) 。而要找到真正的攻击者 那是跳板追踪需要考虑的范畴 7 1 。关于跳板( s t e p p i n gs t o n e ) 追踪，可以参考文 献【l1 1 1 2 。 如今，高速广泛连接的网络给大家带来了方便，同时也为d d o s 攻击创造了 极为有利的条件。d d o s 攻击现已经成为i n t e r a c t 安全的一个严重威胁【1 3 7 1 。如 何精确定位网络攻击源在实时阻断或隔离攻击、追究相关责任、提供法律举证、 威慑攻击者等方面具有非常积极的意义1 1 8 1 。因此，如何在有限的资源环境下， 成功的追踪到d d o s 攻击源头已经成为目前研究人员研究的热点l i 蚴】。 1 2 国内外研究现状 1 2 1 国外研究现状 近年来，i p 追踪研究工作主要分为“单独生成追踪信息专用数据包”和“p 数 2 硕士学位论文 第一章绪论 据包标记”两大类1 9 j 。 2 0 0 0 年r o b e r ts t o n e 就提出了i c m p 定位报文法，该方法是单独生成追踪信 息专用数据包的方法之一1 2 引。其基本原理是引入新的i c m p 定位报文( i c m p t r a c e b a c km e s s a g e ) ，当路由器转发报文时，以极小的概率p 发送对数据包的一个 特殊形式的拷贝，该拷贝是一种特殊定义的i c m p 数据包i 2 6 1 。这种方法有两个缺 点，一是被追踪的数据包与追踪包是分开的，他们可能因为路由策略或防火墙策 略而使其中一个被丢弃，另一个被传输到受害者，从而使得追踪出现误差；二是 在受害者获得攻击路径中所有路由器的t r a c e 信息之前，其需从攻击者接收大量 的数据包1 27 1 。此外，单独生成追踪信息专用数据包会增加网络带宽负荷，不易 升级，反而充当了一种d o s 攻击行为1 9 l 。 而i p 数据包标记则经历了数据包标记、基于边采样的概率包标记、基于日 志记录的追踪技术、静态概率包标记和动态概率包标记几个发展阶段。 早在1 9 9 9 年，b u r c h 和c h e s w i c k 就提出将路由器的地址信息标记到数据包 中，以追踪风暴型拒绝服务攻击来源1 2 引。他们认为当数据包通过路由器时，路 由器将路由器地址信息填入包中，而当受害者收到一定数量的攻击包后，就可以 通过这些攻击包中的路由器地址信息获得从攻击者到受害者之间的路径信息，即 攻击路径信息1 2 9 j 。 2 0 0 0 年，s a v a g e 等人提出了边采样标记方法【3 0 1 。该方法将“边”的信息写入报 文，它在报文头罩预留3 个区域：起点、终点和距离。当路由器转发报文时，以 概率p 进行采样标记，将自己的i p 地址写入起点域，距离置0 。当路由器检测到距 离值为0 时，将自己的i p 地址写入终点域，同时将距离加l ，这样就代表了自己和 前一个路由器之间的“边”。如果路由器不对报文进行标记，就将其距离加l ，这 样距离值就代表对报文进行标记的路由器到目的地所经过的路由器的个数【3 0 1 。 自从2 0 0 0 年s a v a g e 等人提出“边采样”标记方法之后，主流的i p 追踪技术 进入了“基于日志记录的追踪技术”和“基于边采样的概率包标记( p r o b a b i l i t y p a c k e tm a r k i n g ，下称p p m ) 技术”两大阵营的时代【3 l 删l 。 p p m 由于实现技术简单、不增加网络负载、效率高等优点近年来得到了广 泛研究和探讨1 2 9 1 。很多研究者使用p p m 方法，努力减少i p 头部存储标记位数、 提高执行速度、降低误报率和提高精确度等。可以分为以下三种：基本p p m 及 其改进、利用上游拓扑图推测、和攻击响应方法结刽3 5 1 。 s a v a g e 等人首先提出了p p m 方法( f m s ) 【3 6 】。p a r k 和l e e 等人分析了这种方 法的有效性，建议在标记概率、恢复路径长度和接收到的包之间进行权衡，可应 用于任何随机标记方案1 3 7 3 9 1 。d e a n 等人在s a v a g e 等观点的基础上使用代数方法 十学位论文第一章绪论 进设计灵活性和功能，可过滤攻击者产生的噪音并分开多重路径，但在d d o s ，推测攻击路径需要过多的数据刨3 2 l 。 s o n g 等人改进了s a v a g e 等人的方法，利用上游路径和多个路径编码散列函 可以高效安全处理多重攻击【3 6 1 。除以上方法在随机包标记时使用固定相等概 外，p e n g 等人提出了根据跳数、t t l 等参数动态变化标记概率的方法，但它 要多个路由器之间协作并存在安全隐患1 4 0 , 4 1 , 4 2 j 。 x u 等人让受害者参与过滤，在标记大部分包的同时让一小部分包中携带i p 踪信息，在推测攻击路径的同时过滤攻击流量，但不能减少推测路径所需的包 1 4 3 l 。y a r r 等人利用路径信息而不是路由器标记来推测路径，可以主动过滤攻 流量i 4 4 1 。 为了寻求一种更可靠、更有效的方法来弥补p p m 的不足。j e n s h i u hl i u 提出 动态概率包标记方案( d y n a m i cp r o b a b i l i s t i cp a c k e tm a r k i n g ，下称d p p m ) 4 5 j 。 该方案是根据攻击包所经过的路由器跳数即距离攻击者的距离来动态确定标记 概率的值。 1 2 2 国内研究现状 p p m 已成为i p 追踪研究的一个主要方向，国内许多研究人员在p p m 标记 概率、标记信息分片、防止伪造包的加密和认证技术等领域开展了研究工作，其 中具有代表性的有： 2 0 0 2 年，北京航空航天大学的夏春和等人对攻击源定位问题进行了深入的 分析，对每一种方法进行了算法抽象，对当前定位方法进行了比较和归纳，指出 了各种方法的优缺点 4 6 1 。 。 2 0 0 3 年，中国科学技术大学的田海涛等人提出一种新的基于消息鉴别码的 随机数据包标记算法m p p m 。在该算法中路由器随机标记转发的数据包，标记 信息包括路由器自身及其下游路由器组成的边标记的分片以及m a c 值，d o s 攻击的受害者利用m a c 把不同攻击数据包中的边标记分片重组以得到边标记及 攻击路径，并可鉴别标记的真伪1 4 。 2 0 0 3 年，中科院软件所的李德全等人提出一种自适应的标记策略，该策略 使受害者用较少的数据包即可重构攻击路径，这不仅为受害者及早地响应攻击争 取更多的时间，还限制了攻击者的伪造能力1 4 8 】。 2 0 0 4 年，中科院软件所的曲海鹏等人在概率包标记的基础上，提出了一种 分块包标记方案，该方案与概率包标记方案相比具有较低的误报率和较低的计算 复杂度，具有更高的实际应用意义1 2 9 1 。 2 0 0 5 年曲海鹏等人又提出了一种基于有序标记的i p 包追踪方案，该方案通 4 硕士学位论文 第一章绪论 过存储每个目标i p 地址的标记状态，对包标记的分片进行有序发送，使得在d o s 发送时，受害者重构路径所需收到的标记包的数目大大降低，从而提高了对d o s 攻击的响应时间和追踪准确度【4 引。 2 0 0 6 年，中科院研究生院的魏军等人提出了一种新型的边采样方法“路由 器矢量边采样”( r v e s ) ，使得概率包标记设备容易实现和部署【9 】。 2 0 0 7 年，华中科技大学的胡汉平等人提出了次性可变概率分片标记方法， 即对每一数据包从接入到受害主机的传输路径上的所有路由器至多对其进行一 次标记，由此能够避免对任一数据包的重复标记，并提出了压缩一次性可变概率 分片标记方法，使反向追踪攻击源所需的数据包的数目显著减岁s o l 。 1 二3 本文的工作与组织结构 本节主要介绍在现有概率包标记技术的不同研究方向和性能指标中，本文所 主要关注的问题，和本文的工作。并且就论文的组织结构进行简要介绍。 。 现有的概率包标记技术的研究方向主要有：标记概率、标记信息分片、防止 伪造包的加密和认证技术等1 2 5 1 2 7 11 3 7 】。由于如何获取适当的标记概率，对能够快 速、高效的定位攻击者所在的位置，进而对网络攻击进行有效的响应，为系统提 供主动的防御手段以及法律起诉的依据具有重要的意义。因此，本文主要关注的 问题是如何确定适当的标记概率。 现有的概率包标记技术的性能指标主要有：收敛性、最弱链问题、路由器负 担、误报率、重构的计算量和安全性等。由于误报率和重构的计算量与标记信息 分片有关，而安全性又与防止伪造包的加密和认证技术等有关1 7 l 。因此，性能指 标中的收敛性、最弱链问题和路由器负担是本文主要关注的问题。 针对上述两个方面的原因，本文的工作主要分为以下四部分： 首先，通过分析p p m 算法的研究现状和标记概率的确定过程，发现p p m 存 在弱收敛性和最弱链等问题。 其次，通过对d p p m 算法的分析，可以得出，d p p m 算法比p p m 算法在收 敛性和最弱链问题上有优越性，但仍存在路由器负担过重等问题。 再次，通过对p p m 和d p p m 的分析，注意到并且进一步深入挖掘了它们两 者在如何确定标记概率上的关系，结合它们各自的优点，提出了一种动静态结 合的概率包标记方案( d y n a m i c s t m i cp r o b a b i l i s t i cp a c k e tm a r k i n g ，下称d s p p m ) 。 该方案在组内的各路由器之间具有p p m 的特性，而在组与组之问又具有d p p m 的特性，很好的结合了p p m 和d p p m 的优点。并从理论上分别证明了d s p p m 在最弱链问题、收敛性、路由器负担等性能指标上与p p m 和d p p m 相比的优劣 5 硕士学位论文 第一章绪论 情况。此外，本文在上述三个性能指标的基础上还提出了第四个性能指标路 由器上存放标记概率所需的存储空间。把标记概率存放在路由器上，路由器不再 计算标记概率，只需查询即可，从而减轻了路由器的计算负担。 最后，对于所设计的d s p p m 算法进行了编程实现，通过对实验结果的比较 及分析，得出该算法与p p m 和d p p m 相比，哪些方面得到了改进，哪些方面还 存在不足。并对本文所做工作进行总结和下一步的研究工作进行探讨。 本文共分为六章，各章的内容如下： 第一章绪论。介绍了基于d d o s 的概率包标记i p 追踪方案的研究背景、国 内外研究现状、本文的工作和组织结构。 第二章概率包标记的相关理论和技术。分别介绍了p p m 和d p p m 两种算 法的概率包标记与重构过程、标记概率的确定过程和性能指标。 第三章d s p p m 算法设计思想和算法描述。首先分析了p p m 和d p p m 各自 的性能指标。然后提出了一种结合上述两种算法优点的方案d s p p m 。并描 述了该方案的标记概率的确定过程、概率包标记过程和攻击路径的重构过程。 第四章d s p p m 算法的性能分析。通过理论证明了d s p p m 算法与p p m 方 案相比，对最弱链问题有了较好的解决，并且弱收敛性有很大的改善；与d p p m 方案相比，存储空间、查询速度方面有了很大的提高，并且很好的解决了路由器 的负担过重的问题。 第五章实验结果分析。通过对d s p p m 算法进行了编程实现和实验结果比 较分析，验证了d s p p m 算法与p p m 算法相比，弱收敛性有很大的改善，但比 起d p p m 算法仍有改进的空间。 第六章总结和展望。对本文所做工作进行了全面的总结，分析了工作中存 在的不足，并对下一步的研究工作进行了探讨。 6 硕士学位论文 第二章相关理论和技术 第二章相关理论和技术 2 1 概率包标记的标记与重构 包标记的主要思想是当数据包通过路由器时，路由器将其地址信息填入包 中，从而使得受害者能通过这些信息获得从攻击者到受害者之间的路径信息即攻 击性数据包所经历的路径信息【3 。包标记不需要i s p ( 网络服务提供商) 的合作， 大大减小了管理成本；可以实现自动标记自动追踪，减少了人工参与；可移植， 可以随着协议的升级而更新；追踪的准确性和效率较高【3 0 l 。因此，已成为该领 域的一大研究热点。现有的概率包标记技术的研究方向主要有：标记概率、标记 信息分片、防止伪造包的加密和认证技术等。 2 1 1 概率包标记的标记过程 由包标记的主要思想可知，当数据包通过路由器时，路由器将自己的i p 地 址追加到数据包中适当的位置。在i p v 4 中，数据包头的标识符域( 如图2 1 ) 是在 分段数据包的重组时用于识别同一个数据包的不同分段的，由于数据包在途中经 分段处理的情况是很少出现的( 不超过o 2 5 ) ，所以i p 头中的标识符域也很少使 用，利用该域不会影响到绝大多数的网络使用【5 1 1 。 。 o237 8 1 5 图2 ：1 以i p 包头的标识符域作为标记域 文献1 3 0 1 建议将路径信息嵌入到1 6 比特的标识符域中，并把标识符域分为 偏移量、距离和边分块三个域( 如图2 1 ) 。为了减少组合错误的发生，采用一个 3 2 比特的h a s h 作为校验码，将i p 与其3 2 比特的h a s h 校验码以比特为单位间 7 2 1 2 概率包标记的重构过程 当受害者收到足够多的数据包后，首先对数据包按距离域分类，将具有相同 距离值的数据包按偏移量顺序进行组合。如图2 3 所示，对所得到的8 个分块的 组合按比特间隔分离，分别得到奇数位比特组成的m 地址和偶数位比特组成的 8 硕十学位论文第二章相关理论和技术 h a s h 校验码。然后对所得到的i p 地址用最初的h a s h 函数进行h a s h 运算得到新 的h a s h 校验码，用新的h a s h 校验码与分离出来的h a s h 校验码进行比较，相等 则构成对应的边，否则丢弃该组合。 上 按比特间隔分离 土 图2 - 3 边信息的重组 i p 地址 根据图2 3 ，重复边的构造，直到距离值达到最大值，构造出从攻击者到受 害者的所有路由器的边( 相邻两个路由器i p 地址的异或) 。把最后所得的边与 离受害者最近的路由器的i p 地址进行异或，得到与离受害者最近的路由器相邻 的路由器的i p 地址。以此类推，可得到攻击路径上的所有的路由器的i p 地址， 把这些l p 地址按距离值的大小按顺序排列，即为攻击路径。 2 2 概率包标记的标记概率与性能指标 由于标记概率在标记过程具有关键性的作用，恰当的标记概率能快速、高效 的定位攻击者所在的位置。因此，如何确定适当的标记概率具有重要的意义。 9 理论和技术 赠券收集问题：有n 种类型的赠券，每次从中取一件，然后放回，要将n 种赠券都至少取出一次需要取的期望次数是n l n ( n ) + d ( 以) 次。如果某次取出的赠 券在以前从没取出过，则认为这次“取是成功的。很显然，我们需要1 1 次成功 的“取 。 与c o u p o nc o l l e c t o r 类似，假设一条攻击路径的长度为d ，该路径上的所有节 点都以概率p 对数据包进行标记，假设路由器离攻击者的跳数为i ，则标记包到 达受害者v 的概率是p ( 1 一p ) 。易知随着i 增大，这个值单调增大。所以当i - 1 时概率值最小，而其倒数最大。假设所有路由器的标记包到达受害者v 的概率 都为p ( 1 一p ) 扣1 ，由于每一个路由器标记数据包的可能性是相互独立的，那么一 个给定的数据包被某一路由器标记成样本的可能性至少为d p ( 1 一p ) 扣1 。根据赠券 收集问题，受害者要收集到所有d 个路由器的不同的标记包的期望为 d ( 1 n d + d ( 1 ) ) 次。所以，受害者用它来重构一条长度为d 的攻击路径所需的数据 包数量n 的期望有： 删) 钟 万i n d + 矿0 ( 1 ) ( 2 1 ) 忽略常数项伏1 ) ，得到： 删， ) d t ( 4 - 2 ) 因为在p p m 、d p p m 和d s p p m 中 。 口1 ( p ) = p ( 1 一p ) 3 2 一 m ，= 密一扣壶 所以分别把口1 ( 夕) ，彳( p ) ，口：( p ) 带入公式( 4 2 ) 中，可得在p p m 、d p p m 和d s p p m 中为获得最弱链标记所需接收包的数量的数学期望分别为 巨( 删) = f e - a t p ) d t 、互( 腑蹦) = f e - o h p ) , d t 、蜀( 删) = f e - o ；v ) , d t 。 又因为 口l ( p ) = p ( 1 - p ) d = 0 0 4 ( 1 0 0 4 ) 3 2 一= o o l1 2 8 4 1 p 愈8p 一 0 。n m p 职 矽 一 0船p = 、，p n 图4 - 1d s p p m l 算法中的路由器分组 受害者v 硕士学位论文 第四章动一静态结合的概率包标记方案的性能分析 对图4 一l 中的b r l ，b r 2 ，b r 3 ，b r 4 ，b r 5 ，b r 6 ，b r 7 ，b r 8 ，b r 9 ，b r l 0 ， b r il ，b r l 2 ，b r l 3 ，b r l 4 ，b r l 5 ，b r l 6 ，这1 6 个大路由器用d p p m 的方法 来确定每个大路由器的标记概率，即p j = 1 d1 4 5 l 。 因为每一个大路由器中的小路由器的d 是不一样的，为了要找到一个d 来代 表这些同一组中的不同的路由器的d ，则我们用它们的平均值来代表这一组的d 。 从以上的计算过程可以得出每一个大路由器的标记数据包的概率，因此在每一个 大路由器中的小路由器的概率也就能够得到，只需知道这个小路由器属于哪一个 大路由器即可得出小路由器的包标记概率( 如表4 1 ) 。 在表4 1 中，b r i 表示第几个大的路由器( 即第几个分组) ；d 表示的是各 个大路由器中包含的路由器离攻击者的距离范围，通过d 就可以判断小路由器属 于哪一个大路由器，从而得n d , 路由器的包标记概率；d 腑表示的是各个大路由 器到攻击者的距离；只胁表示的是各个大路由器对应的标记概率。 表4 - 1i ) s p p m l 算法中各个路由器标记数据包的概率表 第四章动一静态结合的概率包标记方案的性能分析 s p p m l 中，数据包在第i 个标记路由器硒被标记且不被 后续的标记路由器所覆盖并最终到达受害者v 的概率，根据表4 1 可得 1 6 1 6 a i ( p ) = p 劂( 1 - p 朋1 ) 兀( 1 ) 2 = o 6 6 7 ( 1 - 0 6 6 7 ) 兀( 1 一) 2 = o 0 1 4 2 5 i = 2i = 2 所以 又因为 e i ( 删1 ) = fp 1 ：p 7 衍= f e - o 0 1 4 2 5 t d t = 7 0 1 7 5 4 4 巨( 删) = f e - o , ( p ) , d t = f e - o 0 1 1 2 9 4 1 t d t = 8 8 6 2 0 2 7 可得 巨( 删) 巨( 删) 由上述计算结果可得d s p p m i 的值为7 0 1 7 5 4 4 ，比前面计算的d s p p m 的 值8 9 4 9 7 4 7 要小，同时也小于p p m 的值8 8 6 2 0 2 7 。因此，d s p p m l 对最弱链 问题比p p m 和d s p p m 有了较好的改进。 根据上述的计算过程可以得到当每一组路由器中的路由器个数为8 的时候， 各个路由器标记数据包的标记概率如表4 - 2 所示。 表4 - 2 每一组路由器中的路由器个数为8 时各个路由器标记数据包的概率表 用a i ( p ) 。表示在每一组路由器中的路由器个数为8 时，数据包在第i 个标记 路由器硒被标记且不被后续的标记路由器所覆盖并最终到达受害者v 的概率， 根据表4 2 可得 44 a i ( p ) 。= p b e , ( 1 - p 劂) 7 兀( 1 - p 腩) 3 = o 2 2 2 ( 1 - 0 2 2 2 ) 7 兀( 1 一p 劂) 8 = o 0 0 9 8 9 t=2扣0 所以 巨( 8 ) = f p 一西p 7 d t = f p m 唧柳d t = 1 0 1 1 1 2 2 3 硕士学位论文第四章动一静态结合的概率包标记方案的性能分析 同理，根据上述的计算过程可以得到当每一组路由器中的路由器个数为1 6 的时候，各个路由器标记数据包的标记概率如表4 3 所示。 表4 - 3 每一组路由器中的路由器个数为16 时各个路由器标记数据包的概率表 用口：( p ) “表示在每一组路由器中的路由器个数为1 6 时，数据包在第i 个标 记路由器硒被标记且不被后续的标记路由器所覆盖并最终到达受害者v 的概 率，根据表4 3 可得 a i ( p ) 。= p 觥l ( 1 一p 肌1 ) 1 5 ( 1 一p 肷2 ) 怕= o 118 ( 1 一o 11 8 ) 1 5 ( 1 0 0 4 1 ) = 0 0 0 9 18 所以 局( 1 6 ) = j c o p 一矗，几a t = f e - n 。9 1 8 t d t = 1 0 8 9 3 2 4 6 因此，可得 互( 删) 置( 8 ) 互( 1 6 ) 从上述的计算结果可以看出，每一组路由器由8 个或1 6 个路由器构成都不 能改进p p m 中的最弱链问题，并且由8 个或1 6 个路由器构成一个路由器组时， 组与组之间的动态效果没有d s p p m 和d s p p m l 好。所以，对每一组路由器由8 个或1 6 个路由器构成的情况不再做进一步的研究。 4 1 2 收敛性 从上述的动静态结合的概率包标记方案的最弱链问题可知，在p p m 算法中， 口，( p ) 表示的是数据包在第i 个标记路由器r i 被标记且不被后续的标记路由器所 覆盖并最终到达受害者v 的概率【捌。因此，在各个路由器上的计算公式为 a 1 ( p ) = p ( 1 - p ) 3 2 _ a 2 ( p ) = p ( 1 - p ) 3 2 2 a 3 2 ( p ) = p 在d p p m 算法中，西( p ) 表示的是数据包在第i 个标记路由器r i 被标记且不 和d s p p m l 上的