A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> Replication is a commonly proposed solution to problems of scale associated with distributed services. However, when a service is replicated, each client must be assigned a server. Prior work has generally assumed the assignment to be static. In contrast, we propose a dynamic server selection, and show that it enables application-level congestion avoidance. Using tools to measure the available bandwidth and round trip latency (RTT), we demonstrate the dynamic server selection and compare it to previous static approaches. We show that because of the variability of paths in the Internet, dynamic server selection consistently outperforms static policies, reducing response times by as much as 50%. However, we also must adopt a systems perspective and consider the impact of the measurement method on the network. Therefore, we look at alternative low-cost approximations and find that the careful measurements provided by our tools can be closely approximated by much lighter-weight measurements. We propose a protocol using this method which is limited to at most a 1% increase in network traffic but which often costs much less in practice. <s> BIB001 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back toward their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or “spoofed,” source addresses. In this paper, we describe a general purpose traceback mechanism based on probabilistic packet marking in the network. Our approach allows a victim to identify the network path(s) traversed by attack traffic without requiring interactive operational support from Internet Service Providers (ISPs). Moreover, this traceback can be performed “post mortem”—after an attack has completed. We present an implementation of this technology that is incrementally deployable, (mostly) backward compatible, and can be efficiently implemented using conventional technology. <s> BIB002 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> 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. <s> BIB003 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> A new scheme in probabilistic packet marking (PPM) for IP traceback against denial-of-service attack is presented. Non-preemptive PPM is performed while a marked packet is coming, but compensates the reduction of marking probability in marked-free packets. The nonpreemptive compensation makes the probability of each marked packet arrived at the victim is equal to its original marking probability. This scheme efficiently improves the convergent amount of marked packets required for reconstructing the complete attack path. <s> BIB004 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> 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. <s> BIB005 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> 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. <s> BIB006 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> This paper presents an approach to IP traceback based on the probabilistic packet marking paradigm. Our approach, which we call randomize-and-link, uses large checksum cords to ldquolinkrdquo message fragments in a way that is highly scalable, for the checksums serve both as associative addresses and data integrity verifiers. The main advantage of these checksum cords is that they spread the addresses of possible router messages across a spectrum that is too large for the attacker to easily create messages that collide with legitimate messages. <s> BIB007 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> 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. <s> BIB008 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> The probabilistic packet marking (PPM) algorithm is a promising way to discover the Internet map or an attack graph that the attack packets traversed during a distributed denial-of-service attack. However, the PPM algorithm is not perfect, as its termination condition is not well defined in the literature. More importantly, without a proper termination condition, the attack graph constructed by the PPM algorithm would be wrong. In this work, we provide a precise termination condition for the PPM algorithm and name the new algorithm the rectified PPM (RPPM) algorithm. The most significant merit 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 carry out simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) different probabilities that a router marks the attack packets and 2) different structures of the network graph. The RPPM algorithm provides an autonomous way for the original PPM algorithm to determine its termination, and it is a promising means of enhancing the reliability of the PPM algorithm. <s> BIB009 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> An improved dynamic probabilistic packet marking algorithm named IDPPM is presented, which not only can locate and attack a source rapidly and accurately, but also can reduce the marking overhead of routers near the attackers, which is its greatest contribution given by our technique. In contrast to previous work, the challenge of weakest node and weakest link is solved with the price of a little more numbers of packets to reconstruct the attack path. Theoretical analysis and NS2 simulation results in IPv4 and IPv6 testify that the approach is feasible and efficient respectively. Index Terms—Distributed Denial of Service (DDoS), IP traceback, Dynamic Probabilistic Packet Marking (DPPM), IPv6 <s> BIB010 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> Definition 4 (False positives). <s> 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. <s> BIB011
False positives are nodes incorrectly identified as belonging to the attack graph. Given an attack graph G act and a reconstructed attack graph G ret , the false positives are identified as all members of the set {G ret ∩ G ′ act }. Definition 5 (False negatives). False negatives are nodes in the attack graph that are not identified as such by the reconstruction procedure. Given an attack graph G act and a reconstructed attack graph G ret , the false negatives are identified as all members of the set {G act ∩ G ′ ret }. The expressions for convergence time shown in Table I are the analytical bounds for C = f (d, p) given G is the Single Path, Single attacker (SP/SA) topology and the reconstruction procedure has no prior knowledge of the underlying topology. The SP/SA topology occurs when all the attack traffic originates from a single source and takes the same path to the victim. The convergence time expressions shown in Table I are derived using the coupon collector's problem  . In randomize-and-link BIB007 , l is the number of fragments that each router splits its address into, and H nl is the nl th harmonic number. The schemes in BIB003 , BIB005 , BIB008 , BIB010 do not provide mathematical modeling of their convergence times in the SP/SA topology. Savage et al. BIB002 and Tseng et al. BIB004 point out that the ideal marking probability p depends on the attack path length d. In PPM BIB002 , the marking probability is p = 0.04. This value of p is based on the report that the path length d ≤ 25 for most Internet paths BIB001 . This value of p is maintained in AMS BIB003 , TMS BIB006 , RPPM BIB009 , and PBS BIB011 . Wong et al. BIB009 present a reconstruction procedure in which they count the number of packets required to construct a fully connected attack graph, and then count extra packets to guarantee with a certain level of confidence that all edges in the attack graph are in fact accounted for. To ensure uniformity across the schemes considered in our simulations, we use a simplified version of their reconstruction procedure in which the number of packets required to account for all edges in the complete attack path is counted. A large variety of graphs are used as the underlying topologies in the considered protocol performance analysis. The majority of uses tree-structured graphs G tree = {v, e; |v| = |e| + 1} BIB002 , BIB009 , BIB004 , BIB006 , BIB007 , BIB011 .