改进的压缩边分段采样算法.pdf

2006 年 10 月 西安电子科技大学学报(自然科学版) Oct .2006 第 33 卷 第 5 期 JOURNAL OF XIDIAN UNIVERSITY Vol .33 No .5 改进的压缩边分段采样算法 1 ,2 2 2 闫 巧 , 夏树涛 , 吴建平 (1. 深圳大学 信息工程学院,广东深圳 518060 ; 2. 清华大学 深圳研究生院,广东 深圳 518055 ; 3. 清华大学计算机科学与技术系,北京 100084) 摘要 : 针对 Savage 等人的压缩边采样算法 ,提出一种改进的压缩边采样算法 ,该算法利用 IP 包头与分 段相关的字段作为重载字段 ,增加了边信息存储所需要的空间 ,降低了重构过程的计算复杂度 ,并采用 64 位 Hash 作为误差效验以显著降低多个攻击者同时存在时重构路径的虚警率 ,而且通过对重构过程 的算法优化进一步降低了计算复杂度 .对重构路径所需要的包数、计算量和重构路径的虚警率进行比 较 ,结果证明 ,改进算法远远超过原算法 .将原算法重构路径所需要的计算量(所需要计算的 Hash 次 8 2 数)从 m 降低到 3m (其中m 为在相同距离的攻击源个数)以下 .在同时有 20 个攻击者时 ,原算法虚警 率已经高达 0.99 ,使其不可用 .而改进算法在同时有1000个攻击者的情况下的虚警概率仍然近似为 0 . 因此改进的压缩边采样算法能够很好地应用到大规模DDoS 攻击源追踪中 . 关键词 : 压缩边分段采样 ;概率包标记 ; IP 追踪 ;拒绝服务攻击 ;分布式拒绝服务攻击 TP393 .08 文献标识码 :A 文章编号 :1001-2400(2006)05-0824-05 中图分类号 : Improved compressed edge fragment sampling algorithm 1 ,2 2 2 YAN Qiao , XIA Shu-tao , WU Jian-ping (1 .Shenzhen Univ ., Shenzhen 518060 , China ; 2 .Graduate School at Shenzhen , Tsinghua Univ ., Shenzhen 518055 ,China ; 3 .Dept .of Computer Science Technology ,Tsinghua Univ .,Beijing 100084 ,China) Abstract : A new encoding proposal which improves the compressed edge fragment sampling algorithm of Savage is proposed .In this new proposal ,we overload the IP header fi