改进的压缩边分段采样算法 | |
闫巧 ; 夏树涛 ; 吴建平 ; YAN Qiao ; XIA Shu-tao ; WU Jian-ping | |
2010-06-07 ; 2010-06-07 | |
关键词 | 压缩边分段采样 概率包标记 IP追踪 拒绝服务攻击 分布式拒绝服务攻击 compressed edge fragment sampling probabilistic packet marking(PPM) IP traceback DoS DDoS TP393.08 |
其他题名 | Improved compressed edge fragment sampling algorithm |
中文摘要 | 针对Savage等人的压缩边采样算法,提出一种改进的压缩边采样算法,该算法利用IP包头与分段相关的字段作为重载字段,增加了边信息存储所需要的空间,降低了重构过程的计算复杂度,并采用64位Hash作为误差效验以显著降低多个攻击者同时存在时重构路径的虚警率,而且通过对重构过程的算法优化进一步降低了计算复杂度.对重构路径所需要的包数、计算量和重构路径的虚警率进行比较,结果证明,改进算法远远超过原算法.将原算法重构路径所需要的计算量(所需要计算的Hash次数)从m8降低到3m2(其中m为在相同距离的攻击源个数)以下.在同时有20个攻击者时,原算法虚警率已经高达0.99,使其不可用.而改进算法在同时有1 000个攻击者的情况下的虚警概率仍然近似为0.因此改进的压缩边采样算法能够很好地应用到大规模DDoS攻击源追踪中.; 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 fields which are correlative with the IP packet fragment to increase marking amounts.Moreover,64 parity-check bits generated by 2 different hash functions are employed to reduce the false positive alarm.Then,we further give some optimization procedures to reduce computational complexity during reconstruction.Finally,the two algorithms,i.e.,the compressed edge fragment sampling algorithm of Savage's(CEFS) and our new proposal named the improved compressed edge fragment sampling algorithm(ICEFS),are compared in three aspects,i.e.,the number of packets required for the victim to reconstruct the attack graph,computational complexity,and false positive alarm.The comparing results show that the new proposal ICEFS has much better performance than CEFS.For example the computational complexity during reconstruction of CEFS is m~8 and that of ICEFS is lower than 3m~2(where m is the number of attackers at the particular distance).When there are only 20 attackers at the same distance,the false positive rate of CEFS is nearly 0.99.When there are(1 000) attackers at the same distance,the false positive rate of ICEFS is still about zero.So ICEFS can be used in tracking large scale DDoS attacks.; 国家自然科学基金资助(60402031); 中国博士后基金资助(20040350027) |
语种 | 中文 ; 中文 |
内容类型 | 期刊论文 |
源URL | [http://hdl.handle.net/123456789/45226] ![]() |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | 闫巧,夏树涛,吴建平,等. 改进的压缩边分段采样算法[J],2010, 2010. |
APA | 闫巧,夏树涛,吴建平,YAN Qiao,XIA Shu-tao,&WU Jian-ping.(2010).改进的压缩边分段采样算法.. |
MLA | 闫巧,et al."改进的压缩边分段采样算法".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论