Multiple probabilistic packet marking (PPM) schemes for IP traceback have been proposed to deal with Distributed Denial of Service (DDoS) attacks by reconstructing their attack graphs and identifying the attack sources. In this paper, ten PPM-based IP traceback schemes are compared and analyzed in terms of features such as convergence time, performance evaluation, underlying topologies, incremental deployment, re-marking, and upstream graph. Our analysis shows that the considered schemes exhibit a significant discrepancy in performance as well as performance assessment. We concisely demonstrate this by providing a table showing that (a) different metrics are used for many schemes to measure their performance and, (b) most schemes are evaluated on different classes of underlying network topologies. Our results reveal that both the value and arrangement of the PPM-based scheme convergence times vary depending on exactly the underlying network topology. As a result, this paper shows that a side-by-side comparison of the scheme performance a complicated and turns out to be a crucial open problem in this research area.
Sources of a Distributed Denial of Service (DDoS) attack can be identified by the traffic they generate using the IP traceback technique. Because of its relevance, the Probabilistic Packet Marking (PPM) schemes for IP traceback is an intensively researched field. In these schemes, routers are given the extra function of randomly selecting packets from those that go through them, to embed their address information in those selected packets. During or after the attack, the paths that were traversed by the attack traffic can be identified based on the router information in the marked packets. Since these schemes require a large number of received packets to trace an attacker successfully, they usually demand a high time and space complexity to trace many attackers as is the case in DDoS attacks. This is partly because the marking scheme allows remarking, where routers can overwrite previous marking information in a selected packet, which leads to data loss. We present the Prediction Based Scheme (PBS), which is an addition to the PPM schemes for IP tracetrack. The proposed approach consists of two parts: (a) a marking scheme, that reduces the number of packets required to trace a DoS attacker and (b) an extension to a traceback algorithm, whose main feature is to return a complete attack graph with fewer received packets than the traditional algorithm. The proposed marking scheme alleviates the problem of data loss by ensuring previous marking information is not overwritten. Additionally, the proposed traceback algorithm uses graphs built using legitimate traffic to predict the path taken by attack traffic. Results show that the marking scheme in PBS, compared to PPM, ensures that traceback is possible with about 54 as many total packets to achieve complete attack path construction, while the traceback algorithm takes about 33 as many marked packets. Traceback mechanisms are a critical part of the defense against IP spoofing and DoS attacks, as well as being of forensic value to law enforcement. Currently proposed IP traceback mechanisms are inadequate to address the traceback problem for the following reasons: they require DDoS victims to gather thousands of packets to reconstruct a single attack path; they do not scale to large scale distributed DoS attacks; and they do not support incremental deployment. We propose fast Internet traceback (FIT), a new packet marking approach that significantly improves IP traceback in several dimensions: (1) victims can identify attack paths with high probability after receiving only tens of packets, a reduction of 1-3 orders of magnitude compared to previous packet marking schemes; (2) FIT performs well even in the presence of legacy routers, allowing every FIT-enabled router in path to be identified; and (3) FIT scales to large distributed attacks with thousands of attackers. Compared with previous packet marking schemes, FIT represents a step forward in performance and deployability. Defending against distributed denial-of-service attacks is one of the hardest security problems on the Internet today. One difficulty to thwart these attacks is to trace the source of the attacks because they often use incorrect, or spoofed IP source addresses to disguise the true origin. In this paper, we present two new schemes, the advanced marking scheme and the authenticated marking scheme, which allow the victim to trace-back the approximate origin of spoofed IP packets. Our techniques feature low network and router overhead, and support incremental deployment. In contrast to previous work, our techniques have significantly higher precision (lower false positive rate) and fewer computation overhead for the victim to reconstruct the attack paths under large scale distributed denial-of-service attacks. Furthermore the authenticated marking scheme provides efficient authentication of routers' markings such that even a compromised router cannot forge or tamper markings from other uncompromised routers.