关键词: 拒绝服务攻击（DoS）, IP追踪, 包标记, 压缩边分片采样算法, 自适应概率分片标记算法

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 fragment marking algorithm（NFMS） is proposed.By enlarging marking space and using adaptive probability for packet marking，the NFMS algorithm reduces the number of packets needed for path reconstruction.Moreover，the algorithm reduces computation and false positive number in reconstructing multiple path by labeling fragment.Then the algorithm strengthens the anti-interference capability by initializing marking space of packets which are not marked by Border Router.Finally the algorithm deposits node fragment and edge fragment separately，which can confirm the accuracy of the obtained node in attack path.Compared with other algorithms，the NFMS algorithm has better performance in the aspect of the number of packets needed for attack path reconstruction.

Key words: Denial of Service attack（DoS）, IP traceback, packet marking, Compressed Edge Fragment Sampling algorithm（CEFS）, adaptive probability fragment marking algorithm