ABSTRACT:

The probabilistic packet marking (PPM briefly) algorithm may be a promising way to discover the Internet map, or an attack graph, that the attack packets traversed during a distributed denial-of-service attack. Nonetheless, the PPM algorithm isn't prefect as its termination condition is not well-outlined in the literature. More importantly, while not a correct termination condition, the attack graph constructed by the PPM algorithm would be wrong with a terribly high probability. In this work, we tend to offer a particular termination condition for the PPM algorithm and name the new algorithm the rectified probabilistic packet marking (RPPM briefly) algorithm. The most significant advantage of the RPPM algorithm is that when the algorithm terminates, the algorithm guarantees that the constructed attack graph is correct with a specified level of confidence. We tend to do simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) completely different possibilities that a router marks the attack packets, and 2) different structures of the network graph. The RPPM algorithm provides an autonomous manner for the original PPM algorithm to see its termination, and it's a promising mean to reinforce the reliability of the PPM algorithm.