A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB001 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <s> Finding the source of forged Internet Protocol (IP) datagrams in a large, high-speed network is difficult due to the design of the IP protocol and the lack of sufficient capability in most high-speed, high-capacity router implementations. Typically, not enough of the routers in such a network are capable of performing the packet forwarding diagnostics required for this. As a result, tracking-down the source of a flood-type denial-of-service (DoS) attack is usually difficult or impossible in these networks. ::: ::: CenterTrack is an overlay network, consisting of IP tunnels or other connections, that is used to selectively reroute interesting datagrams directly from edge routers to special tracking routers. The tracking routers, or associated sniffers, can easily determine the ingress edge router by observing from which tunnel the datagrams arrive. The datagrams can be examined, then dropped or forwarded to the appropriate egress point. ::: ::: This system simplifies the work required to determine the ingress adjacency of a flood attack while bypassing any equipment which may be incapable of performing the necessary diagnostic functions. <s> BIB002 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> II. RELATED WORK <s> In this article we present the current state of the art in IP traceback. The rising threat of cyber attacks, especially DDoS, makes the IP traceback problem very relevant to today's Internet security. Each approach is evaluated in terms of its pros and cons. We also relate each approach to practical deployment issues on the existing Internet infrastructure. The functionality of each approach is discussed in detail and then evaluated. We conclude with a discussion on some legal implications of IP traceback. <s> BIB004 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <s> We propose a new approach for IP traceback which is scalable and simple to implement, and introduces no bandwidth and practically no processing overhead. It is backward compatible with equipment which does not implement it. The approach is capable of tracing back attacks, which are composed of just a few packets. In addition, a service provider can implement this scheme without revealing its internal network topology. <s> BIB005 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <s> Tracing attack packets to their sources, known as IP traceback, is an important step to counter distributed denial-of-service (DDoS) attacks. In this paper, we propose a novel packet logging based (i.e., hash-based) traceback scheme that requires an order of magnitude smaller processing and storage cost than the hash-based scheme proposed by Snoeren, et al. (2001), thereby being able to scalable to much higher link speed (e.g., OC-768). The baseline idea of our approach is to sample and log a small percentage (e.g., 3.3%) of packets. The challenge of this low sampling rate is that much more sophisticated techniques need to be used for traceback. Our solution is to construct the attack tree using the correlation between the attack packets sampled by neighboring routers. The scheme using naive independent random sampling does not perform well due to the low correlation between the packets sampled by neighboring routers. We invent a sampling scheme that improves this correlation and the overall efficiency significantly. Another major contribution of this work is that we introduce a novel information-theoretic framework for our traceback scheme to answer important questions on system parameter tuning and the fundamental trade-off between the resource used for traceback and the traceback accuracy. Simulation results based on real-world network topologies (e.g. Skitter) match very well with results from the information-theoretic analysis. The simulation results also demonstrate that our traceback scheme can achieve high accuracy, and scale very well to a large number of attackers (e.g., 5000+). <s> BIB006 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB007 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <s> The integrity of the Internet is severely impaired by rampant denial of service and distributed DoS attacks. It is by no means trivial to devise a countermeasure to address these attacks because of their anonymous and distributed nature. This article presents a brief survey of the most promising recently proposed schemes for tracing cyber attacks: IP traceback. Since IP traceback technology is evolving rapidly, for the community to better comprehend and capture the properties of disparate traceback approaches, we first classify these schemes from multiple aspects. From the perspective of practicality and feasibility, we then analyze and explore the advantages and disadvantages of these schemes in depth so that shortcomings and possible enhancements of each scheme are highlighted. Finally, open problems and future work are discussed, and concluding remarks are drawn. <s> BIB008 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB009 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB010 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB011 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB012 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB013 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <s> A low-rate distributed denial of service (DDoS) attack has significant ability of concealing its traffic because it is very much like normal traffic. It has the capacity to elude the current anomaly-based detection schemes. An information metric can quantify the differences of network traffic with various probability distributions. In this paper, we innovatively propose using two new information metrics such as the generalized entropy metric and the information distance metric to detect low-rate DDoS attacks by measuring the difference between legitimate traffic and attack traffic. The proposed generalized entropy metric can detect attacks several hops earlier (three hops earlier while the order α = 10 ) than the traditional Shannon metric. The proposed information distance metric outperforms (six hops earlier while the order α = 10) the popular Kullback-Leibler divergence approach as it can clearly enlarge the adjudication distance and then obtain the optimal detection sensitivity. The experimental results show that the proposed information metrics can effectively detect low-rate DDoS attacks and clearly reduce the false positive rate. Furthermore, the proposed IP traceback algorithm can find all attacks as well as attackers from their own local area networks (LANs) and discard attack traffic. <s> BIB014 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <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> BIB015 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> II. RELATED WORK <s> Because the Internet has been widely applied in various fields, more and more network security issues emerge and catch people's attention. However, adversaries often hide themselves by spoofing their own IP addresses and then launch attacks. For this reason, researchers have proposed a lot of traceback schemes to trace the source of these attacks. Some use only one packet in their packet logging schemes to achieve IP tracking. Others combine packet marking with packet logging and therefore create hybrid IP traceback schemes demanding less storage but requiring a longer search. In this paper, we propose a new hybrid IP traceback scheme with efficient packet logging aiming to have a fixed storage requirement for each router (under 320 KB, according to CAIDA's skitter data set) in packet logging without the need to refresh the logged tracking information and to achieve zero false positive and false negative rates in attack-path reconstruction. In addition, we use a packet's marking field to censor attack traffic on its upstream routers. Lastly, we simulate and analyze our scheme, in comparison with other related research, in the following aspects: storage requirement, computation, and accuracy. <s> BIB016
In this section, we describe and discuss a set of PPM-based IP traceback schemes for which we will provide an analysis in Section III. PPM-based schemes consist of a marking scheme and a reconstruction procedure, and are based on the assumption that large amounts of traffic are used in a (D)DoS attack BIB001 . In their original work, Savage et al. BIB001 propose that the PPM marking scheme is employed at all times in all the routers in the network, while the reconstruction procedure is employed by the victim in the event of an attack. The marking scheme ensures that every router embeds its own identity in packets randomly selected from the packets the routers process during routing. Since a large number of packets is received in an attack, there is a considerable chance that a victim will have received packets with markings from all the routers that were traversed by the attack packets. The victim then employs the reconstruction procedure which uses the received marked attack packets to map out the attack graph -the paths from the victim to the attackers. The total number of received packets required to trace the attackers is referred to as the scheme's convergence time. Multiple PPM-based schemes have since been introduced. One example is the Tabu Marking Scheme (TMS) BIB009 . The author points out that PPM is prone to information loss as a result of re-marking. Re-marking occurs when a router randomly selects a packet which already has marking information from an upstream router, and consequently overwrites this information. TMS tackles this problem by ensuring that their marking scheme forfeits the marking opportunity in the event that the randomly selected packet contains previous marking information. As a result, they report lower convergence times than PPM for DDoS attacks. Another example is the Prediction Based Scheme (PBS) which also avoids re-marking BIB015 . However, in contrast to TMS, the PBS marking scheme ensures that the router information is embedded in the next available packet if the randomly selected packet already has marking information. The PBS marking scheme requires extra space cost of 1 bit compared to PPM. Additionally, the reconstruction procedure utilizes both legitimate and attack traffic to reconstruct the attack graph. Wong et al. BIB010 present Rectified Probabilistic Packet Marking (RPPM). They point out that the reconstruction procedure used in PPM BIB001 and Advanced and Authenticated Marking schemes (AMS) BIB003 has an imprecise termination condition. They present a precise termination condition that enables complete attack graph reconstruction within a user-specified level of confidence. Multiple additional schemes have been proposed with the purpose to increase the efficiency of PPM BIB007 , BIB011 , BIB012 , BIB013 . Some of these schemes are analyzed in Table I . The table compares ten PPM-based schemes in terms of features such as convergence time, the metrics, underlying topologies, incremental deployment, re-marking, and upstream graph. The schemes considered therein are by no means an exhaustive study of all the PPM-based schemes, but the selection of schemes is large enough to show the discrepancy in both the metrics and underlying topologies as well as the inadequacy of the topologies that make their direct comparison difficult. The feature incremental deployment refers to whether the scheme would be successful if the marking scheme is deployed on a fraction of the routers in the network. Only a few schemes explicitly state that they would be successful when partially deployed BIB001 , BIB003 , BIB007 , BIB012 . Re-marking refers to whether the marking scheme at a router permits the overwriting of previous edge or router information in a packet. The majority of the considered schemes permit re-marking of packets BIB001 , BIB003 , BIB007 , BIB010 , BIB011 , BIB012 , BIB013 . Upstream graph refers to whether a scheme requires a previously obtained map of the network to successfully trace the specific path taken by attack traffic. Some of the works address how such a map can be obtained to aid in attack graph reconstruction BIB003 , BIB007 , BIB015 . Other features such as metrics, convergence time, and underlying topology are discussed in subsequent sections. It is important to point out that PPM-based schemes are not the only proposed approaches to IP traceback BIB004 , BIB008 . Alternatives include packet logging BIB006 , specialized routing BIB002 , Internet control message protocol (ICMP) traceback  , deterministic packet marking BIB005 and hybrid approaches which combine different traceback techniques BIB016 , or combine traceback with anomaly detection BIB014 .