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.
It is important to point out that PPM-based schemes are not the only proposed approaches to IP traceback @cite_4 @cite_11 . Alternatives include packet logging @cite_0 , specialized routing @cite_12 , Internet control message protocol (ICMP) traceback @cite_2 , deterministic packet marking @cite_25 and hybrid approaches which combine different traceback techniques @cite_22 , or combine traceback with anomaly detection @cite_27 .
@cite_4 @cite_22 @cite_0 @cite_27 @cite_2 @cite_25 @cite_12 @cite_11
2064328472 2017648294 2038212958 2095726404
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. In this paper, we model Probabilistic Packet Marking (PPM) schemes for IP traceback as an identification problem of a large number of markers. Each potential marker is associated with a distribution on tags, which are short binary strings. To mark a packet, a marker follows its associated distribution in choosing the tag to write in the IP header. Since there are a large number of (for example, over 4,000) markers, what the victim receives are samples from a mixture of distributions. Essentially, traceback aims to identify individual distribution contributing to the mixture. Guided by this model, we propose Random Packet Marking (RPM), a scheme that uses a simple but effective approach. RPM does not require sophisticated structure relationship among the tags, and employs a hop-by-hop reconstruction similar to AMS [16]. Simulations show improved scalability and traceback accuracy over prior works. For example, in a large network with over 100K nodes, 4,650 markers induce 63 of false positives in terms of edges identification using the AMS marking scheme; while RPM lowers it to 2 . The effectiveness of RPM demonstrates that with prior knowledge of neighboring nodes, a simple and properly designed marking scheme suffices in identifying large number of markers with high accuracy. The IP traceback is an important mechanism in defending against distributed denial-of-service (DDoS) attacks. In this paper, we propose a probabilistic packet marking (PPM) scheme, Tabu Marking Scheme (TMS), to speedup IP traceback. The key idea of "tabu mark" is that, a router still marks packets probabilistically, but regards a packet marked by an upstream router as a tabu and does not mark it again. We study the impact of the traffic aggregation on the convergence behavior of PPM schemes. Furthermore we derive a new analytical result on the partial coupon collection problem, which is a powerful tool applicable for computing the mean convergence time of any PPM scheme. Our study shows that the idea of "tabu mark" not only helps a PPM scheme that allows overwriting to reduce the convergence time under a DDoS attack, but also ensures the authentication of the routers' markings. Distributed denial of service attacks continue to pose major threats to the Internet. In order to traceback attack sources (i.e., IP addresses), a well studied approach is probabilistic packet marking (PPM), where each intermediate router of a packet marks it with a certain probability, enabling a victim host to traceback the attack source. In a recent study, we showed how attackers can take advantage of probabilistic nature of packet markings in existing PPM schemes to create spoofed marks, hence compromising traceback. In this paper, we propose a new PPM scheme called TTL-based PPM (TPM) scheme, where each packet is marked with a probability inversely proportional to the distance traversed by the packet so far. Thus, packets that have to traverse longer distances are marked with higher probability, compared to those that have to traverse shorter distances. This ensures that a packet is marked with much higher probability by intermediate routers than by traditional mechanisms, hence reducing the effectiveness of spoofed packets reaching victims. Using formal analysis and simulations using real Internet topology maps, we show how our TPM scheme can effectively trace DDoS attackers even in presence of spoofing when compared to existing schemes.