Daniel Berend

Despite their frequency, denial-of-service (DoS⁵) and distributed-denial-of-service (DDoS) attacks are difficult to prevent and trace, thus posing a constant threat. One of the main defense techniques is to identify the source of the attack by reconstructing the attack graph, and then filtering the messages arriving from this source. One of the most common methods for reconstructing the attack graph is Probabilistic Packet Marking (PPM). We focus on edge sampling, which is the most common method. Here, we study the time, in terms of the number of packets, the victim needs to reconstruct the attack graph when there is a single attacker. This random variable plays an important role in the reconstruction algorithm. We mention in passing that the process of reconstructing the attack graph is analogous to a version of the well-known coupon collector's problem (with coupons having distinct probabilities). Thus, the results may be used in other applications of this problem. Our main theoretical results determine the asymptotic distribution and expected value of the reconstruction time. We present simulations, demonstrating that the approximations, obtained for short real-world attack paths, are pretty accurate.