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

针对Savage等人的压缩边采样算法，提出一种改进的压缩边采样算法，该算法利用IP包头与分段相关的字段作为重载字段，增加了边信息存储所需要的空间，降低了重构过程的计算复杂度，并采用64位Hash作为误差效验以显著降低多个攻击者同时存在时重构路径的虚警率，而且通过对重构过程的算法优化进一步降低了计算复杂度，对重构路径所需要的包数、计算量和重构路径的虚警率进行比较．结果证明．改进算法远远超过原算法．将原算法重构路径所需要的计算量（所需要计算的Hash次数）从m^8降低到3m^2（其中m为在相同距离的攻击源个数）以下，在同时有20个攻击者时．原算法虚警率已经高达0．99，使其不可用，而改进算法在同时有1000个攻击者的情况下的虚警概率仍然近似为0，因此改进的压缩边采样算法能够很好地应用到大规模DDoS攻击源追踪中。

Improved compressed edge fragment sampling algorithm

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.