A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking
---
paper_title: Topology-dependent performance of attack graph reconstruction in PPM-based IP traceback

paper_content:

A variety of schemes based on the technique of Probabilistic Packet Marking (PPM) have been proposed to identify Distributed Denial of Service (DDoS) attack traffic sources by IP traceback. These PPM-based schemes provide a way to reconstruct the attack graph – the network path taken by the attack traffic – hence identifying its sources. Despite the large amount of research in this area, the influence of the underlying topology on the performance of PPM-based schemes remains an open issue. In this paper, we identify three network-dependent factors that affect different PPM-based schemes uniquely giving rise to a variation in and discrepancy between scheme performance from one network to another. Using simulation, we also show the collective effect of these factors on the performance of selected schemes in an extensive set of 60 Internet-like networks. We find that scheme performance is dependent on the network on which it is implemented. We show how each of these factors contributes to a discrepancy in scheme performance in large scale networks. This discrepancy is exhibited independent of similarities or differences in the underlying models of the networks.
---
paper_title: On IP Traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: Secured node-to-node key agreement for wireless sensor networks

paper_content:

Sensor networks are mostly deployed in unsecured environments, thus protecting a sensor network from any attack is critical in order to maintain the health of the network. Recently, many researchers have focused on making security for sensor networks available and reliable. In this paper, a secured node-to-node key agreement protocol is proposed to generate secured communication among principle nodes A and B, a ticket granting server, and a key server. Since a sensor network is usually a resource-constrained infrastructure, it is not suitable for computationally expensive asymmetric key protocols such as public-private key cryptography. Therefore, setting up a shared key in our proposed protocol is based on a symmetric key protocol processed by two trusted agents, which are the ticket granting server and the key server. The data confidentiality, authentication, and freshness of the network security are also considered in the design of the proposed protocol.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: An Improved Dynamic Probabilistic Packet Marking for IP Traceback

paper_content:

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
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

paper_content:

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.
---
paper_title: Probabilistic packet marking with non-preemptive compensation

paper_content:

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.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Probabilistic Packet Marking for Large-Scale IP Traceback

paper_content:

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.
---
paper_title: Tabu marking scheme to speedup IP traceback

paper_content:

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.
---
paper_title: A prediction based approach to IP traceback

paper_content:

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.
---
paper_title: Using network motifs to investigate the influence of network topology on PPM-based IP traceback schemes

paper_content:

Abstract Multiple schemes that utilize Probabilistic Packet Marking (PPM) have been proposed to deal with Distributed Denial of Service (DDoS) attacks by reconstructing their attack graphs and identifying the attack sources. By analyzing a set of PPM-based schemes, we show that past researchers have evaluated the schemes using disparate and often inadequate underlying topologies, which makes a side-by-side comparison of the scheme performance a complex problem. To tackle this problem, we evaluate selected schemes on a large set of Internet-like topologies and adapt the network motif approach to provide a common ground for comparing the schemes’ performances in different network topologies. This approach allows us to determine the level of structural similarity between network topologies and consequently enables the comparison of scheme performance even when the schemes are implemented on different topologies. Our results reveal that both the value of the PPM-based schemes’ convergence times, and their rankings vary depending on the underlying network topology. However the variation is considerably less when the topologies are compared within superfamilies of structural similarity. More specifically, the standard deviation in convergence times across the networks drops to about a tenth of its original value when the set of 28 networks are arranged in four superfamilies. To complement our results, we present an analytical model showing a link between scheme performance in any superfamily, and the motifs exhibited by the networks in that superfamily. Our work proposes an effective way of comparing general network protocol performance in which the protocol is evaluated on specific representative networks instead of an entire set of networks.
---
paper_title: Tracing cyber attacks from the practical perspective

paper_content:

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.
---
paper_title: Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation ∗

paper_content:

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+).
---
paper_title: RIHT: A Novel Hybrid IP Traceback Scheme

paper_content:

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.
---
paper_title: On IP Traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: An Improved Dynamic Probabilistic Packet Marking for IP Traceback

paper_content:

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
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: Centertrack: An IP overlay network for tracking DoS floods

paper_content:

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.
---
paper_title: A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

paper_content:

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.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Probabilistic Packet Marking for Large-Scale IP Traceback

paper_content:

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.
---
paper_title: IP traceback with deterministic packet marking

paper_content:

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.
---
paper_title: Tabu marking scheme to speedup IP traceback

paper_content:

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.
---
paper_title: A prediction based approach to IP traceback

paper_content:

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.
---
paper_title: Low-Rate DDoS Attacks Detection and Traceback by Using New Information Metrics

paper_content:

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.
---
paper_title: Tracing cyber attacks from the practical perspective

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: An Improved Dynamic Probabilistic Packet Marking for IP Traceback

paper_content:

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
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

paper_content:

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.
---
paper_title: Probabilistic packet marking with non-preemptive compensation

paper_content:

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.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Probabilistic Packet Marking for Large-Scale IP Traceback

paper_content:

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.
---
paper_title: Server selection using dynamic path characterization in wide-area networks

paper_content:

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.
---
paper_title: Tabu marking scheme to speedup IP traceback

paper_content:

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.
---
paper_title: A prediction based approach to IP traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: Unit disk graphs

paper_content:

Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: An Improved Dynamic Probabilistic Packet Marking for IP Traceback

paper_content:

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
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

paper_content:

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.
---
paper_title: Probabilistic packet marking with non-preemptive compensation

paper_content:

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.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Probabilistic Packet Marking for Large-Scale IP Traceback

paper_content:

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.
---
paper_title: Tabu marking scheme to speedup IP traceback

paper_content:

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.
---
paper_title: A prediction based approach to IP traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: An Improved Dynamic Probabilistic Packet Marking for IP Traceback

paper_content:

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
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

paper_content:

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.
---
paper_title: Probabilistic packet marking with non-preemptive compensation

paper_content:

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.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Probabilistic Packet Marking for Large-Scale IP Traceback

paper_content:

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.
---
paper_title: Tabu marking scheme to speedup IP traceback

paper_content:

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.
---
paper_title: A prediction based approach to IP traceback

paper_content:

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.
---
paper_title: Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation ∗

paper_content:

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+).
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---
paper_title: Routing of multipoint connections

paper_content:

The author addresses the problem of routing connections in a large-scale packet-switched network supporting multipoint communications. He gives a formal definition of several versions of the multipoint problem, including both static and dynamic versions. He looks at the Steiner tree problem as an example of the static problem and considers the experimental performance of two approximation algorithms for this problem. A weighted greedy algorithm is considered for a version of the dynamic problem which allows endpoints to come and go during the life of a connection. One of the static algorithms serves as a reference to measure the performance of the proposed weighted greedy algorithm in a series of experiments. >
---
paper_title: BRITE: an approach to universal topology generation

paper_content:

Effective engineering of the Internet is predicated upon a detailed understanding of issues such as the large-scale structure of its underlying physical topology, the manner in which it evolves over time, and the way in which its constituent components contribute to its overall function. Unfortunately, developing a deep understanding of these issues has proven to be a challenging task, since it in turn involves solving difficult problems such as mapping the actual topology, characterizing it, and developing models that capture its emergent behavior. Consequently, even though there are a number of topology models, it is an open question as to how representative the generated topologies they generate are of the actual Internet. Our goal is to produce a topology generation framework which improves the state of the art and is based on the design principles of representativeness, inclusiveness, and interoperability. Representativeness leads to synthetic topologies that accurately reflect many aspects of the actual Internet topology (e.g. hierarchical structure, node degree distribution, etc.). Inclusiveness combines the strengths of as many generation models as possible in a single generation tool. Interoperability provides interfaces to widely-used simulation applications such as ns and SSF and visualization tools like otter. We call such a tool a universal topology generator.
---
paper_title: Unit disk graphs

paper_content:

Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.
---
paper_title: TTL Based Packet Marking for IP Traceback

paper_content:

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.
---
paper_title: FIT: fast Internet traceback

paper_content:

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.
---
paper_title: Network topologies, power laws, and hierarchy

paper_content:

It has long been thought that the Internet, and its constituent networks, are hierarchical in nature. Consequently, the network topology generators most widely used by the Internet research community, GT-ITM [7] and Tiers [11], create networks with a deliberately hierarchical structure. However, recent work by Faloutsos et al. [13] revealed that the Internet’s degree distribution — the distribution of the number of connections routers or Autonomous Systems (ASs) have — is a power-law. The degree distributions produced by the GT-ITM and Tiers generators are not power-laws. To rectify this problem, several new network generators have recently been proposed that produce more realistic degree distributions; these new generators do not attempt to create a hierarchical structure but instead focus solely on the degree distribution. There are thus two families of network generators, structural generators that treat hierarchy as fundamental and degree-based generators that treat the degree distribution as fundamental. In this paper we use several topology metrics to compare the networks produced by these two families of generators to current measurements of the Internet graph. We find that the degree-based generators produce better models, at least according to our topology metrics, of both the AS-level and router-level Internet graphs. We then seek to resolve the seeming paradox that while the Internet certainly has hierarchy, it appears that the Internet graphs are better modeled by generators that do not explicitly construct hierarchies. We conclude our paper with a brief study of other network structures, such as the pointer structure in the web and the set of airline routes, some of which turn out to have metric properties similar to that of the Internet.
---
paper_title: A Precise Termination Condition of the Probabilistic Packet Marking Algorithm

paper_content:

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.
---
paper_title: On power-law relationships of the Internet topology

paper_content:

Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher.Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.
---
paper_title: Probabilistic packet marking with non-preemptive compensation

paper_content:

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.
---
paper_title: End-to-end routing behavior in the internet

paper_content:

The large-scale behavior of routing in the Internet has gone virtually without any formal study, the exception being Chinoy's analysis of the dynamics of Internet routing information [Ch93]. We report on an analysis of 40,000 end-to-end route measurements conducted using repeated "traceroutes" between 37 Internet sites. We analyze the routing behavior for pathological conditions, routing stability, and routing symmetry. For pathologies, we characterize the prevalence of routing loops, erroneous routing, infrastructure failures, and temporary outages. We find that the likelihood of encountering a major routing pathology more than doubled between the end of 1994 and the end of 1995, rising from 1.5% to 3.4%. For routing stability, we define two separate types of stability, "prevalence," meaning the overall likelihood that a particular route is encountered, and "persistence," the likelihood that a route remains unchanged over a long period of time. We find that Internet paths are heavily dominated by a single prevalent route, but that the time periods over which routes persist show wide variation, ranging from seconds up to days. About 2/3's of the Internet paths had routes persisting for either days or weeks. For routing symmetry, we look at the likelihood that a path through the Internet visits at least one different city in the two directions. At the end of 1995, this was the case half the time, and at least one different autonomous system was visited 30% of the time.
---
paper_title: Advanced and authenticated marking schemes for IP traceback

paper_content:

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.
---
paper_title: Probabilistic Packet Marking for Large-Scale IP Traceback

paper_content:

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.
---
paper_title: Modeling Internet topology

paper_content:

The topology of a network, or a group of networks such as the Internet, has a strong bearing on many management and performance issues. Good models of the topological structure of a network are essential for developing and analyzing internetworking technology. This article discusses how graph-based models can be used to represent the topology of large networks, particularly aspects of locality and hierarchy present in the Internet. Two implementations that generate networks whose topology resembles that of typical internetworks are described, together with publicly available source code.
---
paper_title: Tabu marking scheme to speedup IP traceback

paper_content:

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.
---
paper_title: A prediction based approach to IP traceback

paper_content:

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.
---
paper_title: Practical network support for IP traceback

paper_content:

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.
---

Title: A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking

Section 1: INTRODUCTION
Description 1: This section introduces the concept of IP traceback and focuses on the relevance and mechanisms of Probabilistic Packet Marking (PPM) in identifying the sources of Distributed Denial of Service (DDoS) attacks.

Section 2: RELATED WORK
Description 2: This section describes and discusses a variety of PPM-based IP traceback schemes, providing background information necessary for the analysis presented in the subsequent sections.

Section 3: PROTOCOL ANALYSIS
Description 3: This section provides a detailed analysis of the discussed PPM-based schemes, categorized according to definitions, metrics, and underlying topologies.

Section 4: TOPOLOGY INFLUENCE ANALYSIS: A DEMONSTRATION
Description 4: This section discusses how differences in network topologies can influence the performance comparison of PPM-based schemes and give an analytical demonstration of this impact.

Section 5: CONCLUSION
Description 5: This section concludes the paper by summarizing the key findings and implications of the analysis, emphasizing the need for a standardized evaluation framework for PPM-based schemes.