A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. > <s> BIB001 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. <s> BIB002 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. <s> BIB003 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. <s> BIB004 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB005 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. <s> BIB006 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB007 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. <s> BIB008 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB009 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> Tracing attack packets to their sources, known as IP traceback, is an important step to counter distributed denial-of-service (DDoS) attacks. In this paper, we propose a novel packet logging based (i.e., hash-based) traceback scheme that requires an order of magnitude smaller processing and storage cost than the hash-based scheme proposed by Snoeren, et al. (2001), thereby being able to scalable to much higher link speed (e.g., OC-768). The baseline idea of our approach is to sample and log a small percentage (e.g., 3.3%) of packets. The challenge of this low sampling rate is that much more sophisticated techniques need to be used for traceback. Our solution is to construct the attack tree using the correlation between the attack packets sampled by neighboring routers. The scheme using naive independent random sampling does not perform well due to the low correlation between the packets sampled by neighboring routers. We invent a sampling scheme that improves this correlation and the overall efficiency significantly. Another major contribution of this work is that we introduce a novel information-theoretic framework for our traceback scheme to answer important questions on system parameter tuning and the fundamental trade-off between the resource used for traceback and the traceback accuracy. Simulation results based on real-world network topologies (e.g. Skitter) match very well with results from the information-theoretic analysis. The simulation results also demonstrate that our traceback scheme can achieve high accuracy, and scale very well to a large number of attackers (e.g., 5000+). <s> BIB010 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB011 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB012 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <s> 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. <s> BIB013 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB014 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB015 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB016 </s> A Concise Network-Centric Survey of IP Traceback Schemes based on Probabilistic Packet Marking <s> D. Underlying topologies <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> BIB017
The performance of a PPM-based traceback scheme should be evaluated on the Internet itself. However, because of the very large-scale dynamic and heterogeneous structure of the Internet attempts to carry out empirical protocol evaluation are expensive and inflexible BIB003 . As a result, researchers resort to simulations implemented on underlying topologies which are considered to be simplified abstractions of the topology of the Internet BIB003 , BIB008 , BIB004 , BIB006 . An underlying topology is represented by a graph G(v, e) consisting of nodes v and edges e where the nodes represent either devices with routing capability or end hosts. An edge between any two nodes means that traffic can be directly transmitted between those two devices (cf. Fig. 1 ) BIB003 . As shown in Table I , a variety of underlying topologies have been used to evaluate the performance of PPM-based schemes. During set up, the marking algorithm is implemented in the nodes (routers) in the graph. To simulate the attack, packets are transmitted from one or more nodes (representing the attackers) to one specific node (representing the victim). A reconstruction procedure is then implemented at the victim to map out the attack graph G act . The attack graph consists of all nodes and edges in the underlying topology that were directly involved in transmitting the attack packets. The underlying topologies used in PPM-based schemes range from simplistic to complex. The single path, single attacker (SP/SA) is a simple topology consisting of a single attacker node sending packets along a single identical path to a single victim node. The length of the path varies with each work ranging from 3 hops to 32 hops BIB005 , BIB014 , BIB017 , BIB009 . This setup is used to simulate the performance of PPM schemes during a flooding style DoS attack. The Single Path, Multiple Attacker (SP/MA), and Multiple Paths, Multiple Attacker (MP/MA) topologies consist of multiple sources of attack traffic to simulate a DDoS attack. The SP/MA simulates a unique topology in which all the attackers are located at different distances from the victim but all along a single identical path BIB017 . The MP/MA simulates a more general topology where each attacker has a unique path linking it to the victim node. In some cases, the paths are completely independent BIB014 , while in other cases, the paths merge closer to the victim BIB012 , BIB014 , BIB015 , BIB017 . One unique MP/MA topology is a tree, e.g. a binary tree. In this case, the attack graph is modeled as a tree with some or all the leaves at a certain depth representing the attack nodes, and the root of the tree representing the victim node BIB012 , BIB014 , BIB015 . This setup ensures that different attack paths merge the closer they are to the victim. As with SP/SA and SP/MA, there is only one path in the attack graph from an attack node to the victim node. Schemes such as AMS, FIT, and TPM have been evaluated using actual data sets from the Internet BIB007 , BIB011 , BIB016 including traceroute data sets from Lucent Bell labs BIB007 and CAIDA's skitter map BIB011 , BIB016 . These data sets are used to produce topologies that are typically larger than the simple topologies mentioned thus far and provide better abstractions of the Internet structure. However, they do not provide an adequate description of the Internet since they are typically restricted to restricted snapshot of the Internet network BIB010 . Traceroute datasets have also been reported to be inaccurate when the network has asymmetric paths BIB011 . One common feature with these underlying topologies is their tree-like structure. A tree-structured topology G tree exhibits a single path from any given attacker to the victim. The choice of tree-structured topologies is based on the assumption that all attack traffic from one attacker will take the same path to the victim. This assumption is in turn based on the observation that Internet paths are largely invariant particularly over short periods of time BIB013 . These assumptions have allowed researchers to simplify the simulation process by ignoring the routing capabilities of the network and enforcing a predefined set of paths for attack traffic as evidenced in a tree-structured topology. However, because tree-structured topologies do not exhibit the alternative routes ubiquitous in the Internet, they can not be used as an appropriate abstraction of the Internet topology. In summary, network models used to simulate the Internet topology fall into three categories based on the properties that they emphasize, namely degree-based models, structural models and spatial models (cf. Fig. 1 ). The emphasis of degreebased models is the degree distribution of the nodes in an attempt to recreate the power law observations in the Internet BIB004 , BIB001 . The structural models arrange the nodes to mimic the hierarchical structure of the Internet, with Internet traffic being transmitted through routers located within autonomous systems BIB003 , BIB006 . The spatial models place emphasis on the location of the nodes with any two nodes being connected only if they are within a transmission range of each other BIB002 .