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

摘要： 拒绝服务攻击（DoS）是难以解决的网络安全问题。IP追踪技术是确定DoS攻击源的有效方法。针对用于IP追踪的压缩边分片采样算法（CEFS）存在的不足，提出了新分片标记算法（NFMS），该算法通过扩大标记空间和采用自适应概率的方法，减少了重构路径所需数据包数，并通过给分片加标注，减少了重构路径的计算量和误报率，并且将点分片（路由器分片）、边分片（该路由器分片与同偏移值的下游相邻路由器分片的异或值）分开存放，可验证重构路径时所得攻击路径中节点的正确性。分析和仿真结果表明NFMS算法的性能较优。

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