  DoS and DDoS attacks are widely used and pose a constant threat. Here we
explore Probability Packet Marking (PPM), one of the important methods for
reconstructing the attack-graph and detect the attackers. We present two
algorithms. Differently from others, their stopping time is not fixed a priori.
It rather depends on the actual distance of the attacker from the victim. Our
first algorithm returns the graph at the earliest feasible time, and turns out
to guarantee high success probability. The second algorithm enables attaining
any predetermined success probability at the expense of a longer runtime. We
study the performance of the two algorithms theoretically, and compare them to
other algorithms by simulation. Finally, we consider the order in which the
marks corresponding to the various edges of the attack graph are obtained by
the victim. We show that, although edges closer to the victim tend to be
discovered earlier in the process than farther edges, the differences are much
smaller than previously thought.

Cryptography and Security;Probability