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 fields which are correlative with the IP packet fragment to increase marking amounts. Moreover, 64 parity-check bits generated by 2different 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⁸ and that of ICEFS is lower than 3m²(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 1000 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.

Key words: compressed edge fragment sampling, probabilistic packet marking(PPM), IP traceback, DoS, DDoS