A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back toward their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or “spoofed,” source addresses. In this paper, we describe a general purpose traceback mechanism based on probabilistic packet marking in the network. Our approach allows a victim to identify the network path(s) traversed by attack traffic without requiring interactive operational support from Internet Service Providers (ISPs). Moreover, this traceback can be performed “post mortem”—after an attack has completed. We present an implementation of this technology that is incrementally deployable, (mostly) backward compatible, and can be efficiently implemented using conventional technology. <s> BIB001 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> Defending against distributed denial-of-service attacks is one of the hardest security problems on the Internet today. One difficulty to thwart these attacks is to trace the source of the attacks because they often use incorrect, or spoofed IP source addresses to disguise the true origin. In this paper, we present two new schemes, the advanced marking scheme and the authenticated marking scheme, which allow the victim to trace-back the approximate origin of spoofed IP packets. Our techniques feature low network and router overhead, and support incremental deployment. In contrast to previous work, our techniques have significantly higher precision (lower false positive rate) and fewer computation overhead for the victim to reconstruct the attack paths under large scale distributed denial-of-service attacks. Furthermore the authenticated marking scheme provides efficient authentication of routers' markings such that even a compromised router cannot forge or tamper markings from other uncompromised routers. <s> BIB002 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> In this article we present the current state of the art in IP traceback. The rising threat of cyber attacks, especially DDoS, makes the IP traceback problem very relevant to today's Internet security. Each approach is evaluated in terms of its pros and cons. We also relate each approach to practical deployment issues on the existing Internet infrastructure. The functionality of each approach is discussed in detail and then evaluated. We conclude with a discussion on some legal implications of IP traceback. <s> BIB003 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> A new scheme in probabilistic packet marking (PPM) for IP traceback against denial-of-service attack is presented. Non-preemptive PPM is performed while a marked packet is coming, but compensates the reduction of marking probability in marked-free packets. The nonpreemptive compensation makes the probability of each marked packet arrived at the victim is equal to its original marking probability. This scheme efficiently improves the convergent amount of marked packets required for reconstructing the complete attack path. <s> BIB004 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> The integrity of the Internet is severely impaired by rampant denial of service and distributed DoS attacks. It is by no means trivial to devise a countermeasure to address these attacks because of their anonymous and distributed nature. This article presents a brief survey of the most promising recently proposed schemes for tracing cyber attacks: IP traceback. Since IP traceback technology is evolving rapidly, for the community to better comprehend and capture the properties of disparate traceback approaches, we first classify these schemes from multiple aspects. From the perspective of practicality and feasibility, we then analyze and explore the advantages and disadvantages of these schemes in depth so that shortcomings and possible enhancements of each scheme are highlighted. Finally, open problems and future work are discussed, and concluding remarks are drawn. <s> BIB005 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> Traceback mechanisms are a critical part of the defense against IP spoofing and DoS attacks, as well as being of forensic value to law enforcement. Currently proposed IP traceback mechanisms are inadequate to address the traceback problem for the following reasons: they require DDoS victims to gather thousands of packets to reconstruct a single attack path; they do not scale to large scale distributed DoS attacks; and they do not support incremental deployment. We propose fast Internet traceback (FIT), a new packet marking approach that significantly improves IP traceback in several dimensions: (1) victims can identify attack paths with high probability after receiving only tens of packets, a reduction of 1-3 orders of magnitude compared to previous packet marking schemes; (2) FIT performs well even in the presence of legacy routers, allowing every FIT-enabled router in path to be identified; and (3) FIT scales to large distributed attacks with thousands of attackers. Compared with previous packet marking schemes, FIT represents a step forward in performance and deployability. <s> BIB006 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> The IP traceback is an important mechanism in defending against distributed denial-of-service (DDoS) attacks. In this paper, we propose a probabilistic packet marking (PPM) scheme, Tabu Marking Scheme (TMS), to speedup IP traceback. The key idea of "tabu mark" is that, a router still marks packets probabilistically, but regards a packet marked by an upstream router as a tabu and does not mark it again. We study the impact of the traffic aggregation on the convergence behavior of PPM schemes. Furthermore we derive a new analytical result on the partial coupon collection problem, which is a powerful tool applicable for computing the mean convergence time of any PPM scheme. Our study shows that the idea of "tabu mark" not only helps a PPM scheme that allows overwriting to reduce the convergence time under a DDoS attack, but also ensures the authentication of the routers' markings. <s> BIB007 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> The probabilistic packet marking (PPM) algorithm is a promising way to discover the Internet map or an attack graph that the attack packets traversed during a distributed denial-of-service attack. However, the PPM algorithm is not perfect, as its termination condition is not well defined in the literature. More importantly, without a proper termination condition, the attack graph constructed by the PPM algorithm would be wrong. In this work, we provide a precise termination condition for the PPM algorithm and name the new algorithm the rectified PPM (RPPM) algorithm. The most significant merit of the RPPM algorithm is that when the algorithm terminates, the algorithm guarantees that the constructed attack graph is correct, with a specified level of confidence. We carry out simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) different probabilities that a router marks the attack packets and 2) different structures of the network graph. The RPPM algorithm provides an autonomous way for the original PPM algorithm to determine its termination, and it is a promising means of enhancing the reliability of the PPM algorithm. <s> BIB008 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> Distributed denial of service attacks continue to pose major threats to the Internet. In order to traceback attack sources (i.e., IP addresses), a well studied approach is probabilistic packet marking (PPM), where each intermediate router of a packet marks it with a certain probability, enabling a victim host to traceback the attack source. In a recent study, we showed how attackers can take advantage of probabilistic nature of packet markings in existing PPM schemes to create spoofed marks, hence compromising traceback. In this paper, we propose a new PPM scheme called TTL-based PPM (TPM) scheme, where each packet is marked with a probability inversely proportional to the distance traversed by the packet so far. Thus, packets that have to traverse longer distances are marked with higher probability, compared to those that have to traverse shorter distances. This ensures that a packet is marked with much higher probability by intermediate routers than by traditional mechanisms, hence reducing the effectiveness of spoofed packets reaching victims. Using formal analysis and simulations using real Internet topology maps, we show how our TPM scheme can effectively trace DDoS attackers even in presence of spoofing when compared to existing schemes. <s> BIB009 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> This paper presents an approach to IP traceback based on the probabilistic packet marking paradigm. Our approach, which we call randomize-and-link, uses large checksum cords to ldquolinkrdquo message fragments in a way that is highly scalable, for the checksums serve both as associative addresses and data integrity verifiers. The main advantage of these checksum cords is that they spread the addresses of possible router messages across a spectrum that is too large for the attacker to easily create messages that collide with legitimate messages. <s> BIB010 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> An improved dynamic probabilistic packet marking algorithm named IDPPM is presented, which not only can locate and attack a source rapidly and accurately, but also can reduce the marking overhead of routers near the attackers, which is its greatest contribution given by our technique. In contrast to previous work, the challenge of weakest node and weakest link is solved with the price of a little more numbers of packets to reconstruct the attack path. Theoretical analysis and NS2 simulation results in IPv4 and IPv6 testify that the approach is feasible and efficient respectively. Index Terms—Distributed Denial of Service (DDoS), IP traceback, Dynamic Probabilistic Packet Marking (DPPM), IPv6 <s> BIB011 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> Sources of a Distributed Denial of Service (DDoS) attack can be identified by the traffic they generate using the IP traceback technique. Because of its relevance, the Probabilistic Packet Marking (PPM) schemes for IP traceback is an intensively researched field. In these schemes, routers are given the extra function of randomly selecting packets from those that go through them, to embed their address information in those selected packets. During or after the attack, the paths that were traversed by the attack traffic can be identified based on the router information in the marked packets. Since these schemes require a large number of received packets to trace an attacker successfully, they usually demand a high time and space complexity to trace many attackers as is the case in DDoS attacks. This is partly because the marking scheme allows remarking, where routers can overwrite previous marking information in a selected packet, which leads to data loss. We present the Prediction Based Scheme (PBS), which is an addition to the PPM schemes for IP tracetrack. The proposed approach consists of two parts: (a) a marking scheme, that reduces the number of packets required to trace a DoS attacker and (b) an extension to a traceback algorithm, whose main feature is to return a complete attack graph with fewer received packets than the traditional algorithm. The proposed marking scheme alleviates the problem of data loss by ensuring previous marking information is not overwritten. Additionally, the proposed traceback algorithm uses graphs built using legitimate traffic to predict the path taken by attack traffic. Results show that the marking scheme in PBS, compared to PPM, ensures that traceback is possible with about 54% as many total packets to achieve complete attack path construction, while the traceback algorithm takes about 33% as many marked packets. <s> BIB012 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> 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. <s> BIB013 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> 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. <s> BIB014 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> I. INTRODUCTION <s> 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. <s> BIB015
Internet Protocol (IP) traceback is a method to deal with Distributed Denial of Service (DDoS) attacks BIB003 , BIB005 . Using IP traceback, sources of attack traffic can be identified from the network traffic they generate. A prominent IP traceback technique for identification of flooding style DDoS attacks is Probabilistic Packet Marking (PPM). In PPM-based IP traceback, network routers embed their own identities in packets randomly selected from all the network traffic that the routers process BIB001 . In the event of an attack, the routers' identity markings present in the attack packets can be used to reconstruct the attack graph -the paths taken by attack traffic -and establish its sources BIB002 , BIB015 . The technique of probabilistically marking packets for IP traceback is the basis of many schemes hereafter referred to as PPM-based schemes BIB002 , BIB006 , BIB008 , BIB009 . Multiple additional schemes have been proposed with the purpose to increase the efficiency of PPM-based schemes BIB006 , BIB009 , BIB010 , BIB011 . Tracing the paths of IP packets back to their origin, known as IP traceback, is an important step in defending against DoS attacks employing IP spoofing. IP traceback facilitates holding attackers accountable and improving the efficacy of mitigation measures. The existing approaches for IP traceback can be grouped into two orthogonal dimensions: packet marking and packet logging. The main idea behind packet marking is to record network path information in packets. In mark based IP traceback, routers write their identification information (e.g., IP addresses) into a header field of forwarded packets. The destination node then retrieves the marking information from the received packets and determines the network path. Due to the limited space of the marking field, routers probabilistically decide to mark packets so that each marked packet carries only partial path information. The network path can be constructed by combining the marking information collected from a number of received packets. This approach is also known as probabilistic packet marking (PPM) BIB001 . PPM incurs little overhead at routers. However, it requires a flow of marked packets to construct the network path toward their origin. In this paper, we present a concise network-centric analysis of a selected set of PPM-based schemes. Ten PPM-based schemes are compared in terms of features such as convergence time, the metrics, underlying topologies, incremental deployment, re-marking, and upstream graph. These schemes are PPM BIB001 , AMS BIB002 , PPM-NPC BIB004 , TMS BIB007 , FIT BIB006 , RPPM BIB008 , TPM BIB009 , Randomize-and-link BIB010 , IDPPM BIB011 , and PBS BIB012 . The schemes considered therein are by no means an exhaustive study of all the PPM-based schemes in existence. However, the collection of schemes is large enough to show the discrepancy in both the metrics and underlying topologies as well as the inadequacy of the topologies that make their direct comparison difficult BIB013 , BIB014 . Thus, this paper shows that the direct performance comparison of the schemes is complicated or not feasible at all. As our analysis show the reasons for this is (a) many schemes utilize different metrics to measure their performance and, (b) the many schemes are simulated on different kinds of underlying network topologies, the majority of which do not provide an adequate abstraction of the topology of the Internet or focus on different characteristics of it BIB008 , BIB004 , BIB007 . In detail, the underlying topologies are typically treestructured with a single path from an attacker to the victim. In contrast, the topology of the Internet exhibits alternative routes that make it both resilient and scalable. Both the disparity in metrics and underlying topologies, as well as the inadequacy of the topologies, raise questions about the performances of these schemes in the Internet and the comparability between them. Figure 1 . Internet topology can be captured by a variety of models which include spatial, structural and degree-based models. Each model emphasizes different properties of the Internet and can be used to evaluate network protocols when employed in the Internet. The nodes in these topologies represent devices operating at the Internet layer of the TCP/IP model or the network layer of the OSI model (e.g. routers, switches, hosts). Two nodes are connected by an edge if Internet traffic can be directly transmitted between them without being forwarded by any intermediate nodes. This shows that there is a need to evaluate and compare the schemes on common and appropriate networks. The results of this evaluation can then be used to determine which schemes are the most promising candidates for Internet deployment. In summary, the contribution of this paper is threefold: (a) an analysis of PPM-based schemes is presented, (b) providing a taxonomy for PPM-based IP traceback schemes, and (c) an analytical model to argue that different underlying topologies inhibit a direct comparison between the performance of the PPM-based schemes. The remainder of this paper is arranged as follows. Related work, in which the selected set of PPM-based protocols is discussed, is presented in Section II. The analysis of PPMbased schemes as well as additional background is presented in Section III, including considerations on definitions, metrics, and underlying topologies. The theory and system model behind our work is analyzed in Section IV. We discuss outcomes of this paper and conclude in Section V.