Abstract: IP traceback is an important measure to defend against Denial of Service (DoS) attack.Based on Compressed Edge Fragment Sampling algorithm (CEFS) for IP traceback, a new algorithm is proposed, called Lable fragment adaptive probability packet marking (LFAPPM) .By enlarging marking space and using adaptive probability for packet marking, the LFAPPM algorithm reduces the number of packets needed for attack path reconstruction.Moreover, the algorithm reduces computation and false positive number in reconstructing multiple attack path by labeling fragment.Then the algorithm strengthens the anti-interference capability by initializing marking space of packets which are not marked by Boder Router.Compared with other algorithms, the LFAPPM algorithm has better performance.