doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back towards 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) backwards compatible and can be efficiently implemented using conventional technology. <s> BIB001 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> Most denial-of-service attacks are characterized by a flood of packets with random, apparently valid source addresses. These addresses are spoofed, created by a malicious program running on an unknown host, and carried by packets that bear no clues that could be used to determine their originating host. Identifying the source of such an attack requires tracing the packets back to the source hop by hop. Current approaches for tracing these attacks require the tedious continued attention and cooperation of each intermediate Internet Service Provider (ISP). This is not always easy given the world-wide scope of the Internet.We outline a technique for tracing spoofed packets back to their actual source host without relying on the cooperation of intervening ISPs. First, we map the paths from the victim to all possible networks. Next, we locate sources of network load, usually hosts or networks offering the UDP chargen service [5]. Finally, we work back through the tree, loading lines or router, observing changes in the rate of invading packets. These observations often allow us to eliminate all but a handful of networks that could be the source of the attacking packet stream. Our technique assumes that routes are largely symmetric, can be discovered, are fairly consistent, and the attacking packet stream arrives from a single source network.We have run some simple and single-blind tests on Lucent's intranet, where our technique usually works, with better chances during busier network time periods; in several tests, we were able to determine the specific network containing the attacker.An attacker who is aware of our technique can easily thwart it, either by covering his traces on the attacking host, initiating a "whack-a-mole" attack from several sources, or using many sources. <s> BIB002 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> Defending against distributed denial-of-service attacks is one of the hardest security problems on the Internet today. One difficulty to thwart these attacks is to trace the source of the attacks because they often use incorrect, or spoofed IP source addresses to disguise the true origin. In this paper, we present two new schemes, the advanced marking scheme and the authenticated marking scheme, which allow the victim to trace-back the approximate origin of spoofed IP packets. Our techniques feature low network and router overhead, and support incremental deployment. In contrast to previous work, our techniques have significantly higher precision (lower false positive rate) and fewer computation overhead for the victim to reconstruct the attack paths under large scale distributed denial-of-service attacks. Furthermore the authenticated marking scheme provides efficient authentication of routers' markings such that even a compromised router cannot forge or tamper markings from other uncompromised routers. <s> BIB003 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. Even in the absence of any deliberate attempt to disguise a packet's origin, wide-spread packet forwarding techniques such as NAT and encapsulation may obscure the packet's true source. Techniques have been developed to determine the source of large packet flows, but, to date, no system has been presented to track individual packets in an efficient, scalable fashion.We present a hash-based technique for IP traceback that generates audit trails for traffic within the network, and can trace the origin of a single IP packet delivered by the network in the recent past. We demonstrate that the system is effective, space-efficient (requiring approximately 0.5% of the link capacity per unit time in storage), and implementable in current or next-generation routing hardware. We present both analytic and simulation results showing the system's effectiveness. <s> BIB004 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. Even in the absence of any deliberate attempt to disguise a packet's origin, widespread packet forwarding techniques such as NAT and encapsulation may obscure the packet's true source. Techniques have been developed to determine the source of large packet flows, but, to date, no system has been presented to track individual packets in an efficient, scalable fashion. We present a hash-based technique for IP traceback that generates audit trails for traffic within the network, and can trace the origin of a single IP packet delivered by the network in the recent past. We demonstrate that the system is effective, space efficient (requiring approximately 0.5% of the link capacity per unit time in storage), and implementable in current or next-generation routing hardware. We present both analytic and simulation results showing the system's effectiveness. <s> BIB005 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> We present a new solution to the problem of determining the path a packet traversed over the Internet (called the traceback problem) during a denial-of-service attack. This article reframes the traceback problem as a polynomial reconstruction problem and uses algebraic techniques from coding theory and learning theory to provide robust methods of transmission and reconstruction. <s> BIB006 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> Distributed denial of service (DDoS) is one of the most difficult security problems to address. While many existing techniques (e.g., IP traceback) focus on tracking the location of the attackers after-the-fact, little is done to mitigate the effect of an attack while it is raging on. We present a novel technique that can effectively filter out the majority of DDoS traffic, thus improving the overall throughput of the legitimate traffic. The proposed scheme leverages on and generalizes the IP traceback schemes to obtain the information concerning whether a network edge is on the attacking path of an attacker ("infected") or not ("clean"). We observe that while an attacker will have all the edges on its path marked as "infected", edges on the path of a legitimate client will mostly be "clean". By preferentially filtering out packets that are inscribed with the marks of "infected" edges, the proposed scheme removes most of the DDoS traffic while affecting legitimate traffic only slightly. Simulation results based on real-world network topologies (e.g., Skitter) all demonstrate that the proposed technique can improve the throughput of legitimate traffic by 3 to 7 times during DDoS attacks. <s> BIB007 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> The increasing frequency of malicious computer attacks on government agencies and Internet businesses has caused severe economic waste and unique social threats. IP traceback-the ability to trace IP packets to their origins-is a significant step toward identifying, and thus stopping, attackers. <s> BIB008 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> Today's Internet is extremely vulnerable to Distributed Denial of service (DDoS) attacks. There is tremendous pressure on the sites performing online business and ISP's to protect their networks from DDoS attacks. Recently, several novel traceback techniques have been proposed to trace the approximate spoofed source of attack. Each proposed traceback technique has some unique advantages and disadvantages over the others. In this paper we will consider some of the novel traceback techniques and focus our discussion i) to raise some of the real time issues that can be addressed in the further research and ii) from the attackers perspective on how to generate DDoS attacks and remain untraced even if any of the traceback technique is deployed in the Internet. We will also demonstrate how attacks can be further amplified if ICMP traceback technique is deployed in the Internet and discuss techniques to minimise the additional attack traffic. We believe that the networks tend to become complex and more vulnerable to DDoS attacks if some of the proposed traceback techniques are deployed in the Internet. <s> BIB009 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> The current Internet architecture allows malicious nodes to disguise their origin during denial-of-service attacks with IP spoofing. A well-known solution to identify these nodes is IP traceback. In this paper, we introduce and analyze a lightweight single-packet IP traceback system that does not store any data in the network core. The proposed system relies on a novel data structure called Generalized Bloom Filter, which is tamper resistant. In addition, an efficient improved path reconstruction procedure is introduced and evaluated. Analytical and simulation results are presented to show the effectiveness of the proposed scheme. The simulations are performed in an Internet-based scenario and the results show that the proposed system locates the real attack path with high accuracy. <s> BIB010 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> Tracing IP packets to their origins is an important step in defending Internet against denial-of-service attacks. Two kinds of IP traceback techniques have been proposed as packet marking and packet logging. In packet marking, routers probabilistically write their identification information into forwarded packets. This approach incurs little overhead but requires large flow of packets to collect the complete path information. In packet logging, routers record digests of the forwarded packets. This approach makes it possible to trace a single packet and is considered more powerful. At routers forwarding large volume of traffic, the high storage overhead and access time requirement for recording packet digests introduce practicality problems. In this paper, we present a novel scheme to improve the practicality of log-based IP traceback by reducing its overhead on routers. Our approach makes an intelligent use of packet marking to improve scalability of log-based IP traceback. We use mathematical analysis and simulations to evaluate our approach. Our evaluation results show that, compared to the state-of-the-art log-based approach called hash-based IP traceback, our approach maintains the ability to trace single IP packet while reducing the storage overhead by half and the access time overhead by a factor of the number of neighboring routers. <s> BIB011 </s> doi:10.1093/comjnl/bxh000 Protection against Denial of Service Attacks: A Survey <s> IDENTIFYING THE TRUE SOURCE OF AN ATTACK <s> Distributed denial of service attacks currently represent a serious threat to the appropriate operation of Internet services. To deal with this threat, we propose an overlay network that provides an IP-traceback scheme at the level of autonomous systems. Our proposed autonomous system-level IP-traceback system contrasts with previous works because it does not require a priori knowledge of the network topology and allows single-packet traceback and incremental deployment. Our first contribution is a new extension to the Border Gateway Protocol update-message community attribute that enables information to be passed across autonomous systems that are not necessarily involved in the overlay network. The second contribution is a new sequence-marking process to remove ambiguities in the traceback path. Two different strategies for incremental system deployment are investigated and evaluated. We show that strategic placement of the system on highly connected autonomous systems produces relevant results for IP traceback even if the system operates on only a few autonomous systems. The main conclusion is that the proposed system is suitable for large-scale networks such as the Internet because it provides efficient traceback and allows incremental deployment. <s> BIB012
Although identifying the source of an attack is not enough to respond against it, it can be part of a broader repertoire of countermeasures. One of the first measures proposed for limiting attacks from spoofed source addresses is Ingress Filtering, a technique based on configuring routers to drop arriving packets with IP addresses deemed to be outside a predetermined "acceptable" range  . In essence, packets are not allowed to leave a border network if their source address does not belong to this border network. The more widely deployed the better the protection that Ingress Filtering will offer. Of course, it requires that the receiving router has sufficient power and sufficient knowledge to examine the source address of each packet and distinguish between valid and invalid ones, while attackers can still overcome it by choosing legitimate addresses at random. Variations of Ingress Filtering are often used as a lightweight first step to identify part of the attacking traffic. It has been suggested that the actual IP address of an attacking agent can in fact be inferred by "IP traceback" BIB001 BIB003 BIB004 BIB006 BIB005 BIB007 , where it is proposed either to monitor the flows traversing the network and mark packets probabilistically or to attempt to infer the attacking flows' paths based on their impact on the network. Traceback needs to be done with minimal cost in time and storage and minimal false alarms, while respecting the privacy of the contents of the audited packets and not requiring interactive operational support from Internet Service Providers. A fairly accurate and widely deployed traceback mechanism can also act as a deterrent for attackers that are aware of its existence BIB008 . However, despite the elegant ideas and interesting implementations described in the literature, current traceback mechanisms are not effective deterrents. In most cases, not only they cannot be deployed widely enough, but they also suffer from a common inherent weakness, which is that fake traceback messages created The Computer Journal Vol. 00 No. 0, 2009 Protection against Denial of Service Attacks: A Survey 13 by attackers and included into the attack flows can help them hide their origin. However, even a rough estimate of the sources of attack packets usually does help in DDoS defence. IP traceback can also be applied "post-mortem", after the attack is over, to help protect against future attacks. The following is a more detailed description of the main traceback proposals in the literature. The first important work on determining the path that a packet traverses over the Internet in the context of a DoS attack BIB002 proposes to systematically flood links which potentially belong to attack paths, observe the variations in the received packet rates, and create a map of the routes from the victim to every network, then start with the closest router and apply a brief burst of load to each link attached to it. If the loaded link belongs to the attack path, the induced load will perturb the attacking stream. As the authors admit they assume that they can map the paths from the victim to all possible networks, that routes are all symmetric, can be discovered and are fairly consistent, and that the attacking packet stream arrives from a single source. However, this interesting approach to the traceback problem has very limited use in today's networks; not to mention that flooding networks with traffic to protect them against flooding may be inappropriate. It is usually referred to as controlled flooding or more generally as link-testing. In BIB001 , a Probabilistic Packet Marking (PPM) scheme is proposed for the first time. The scheme encodes partial attack path information and includes it in IP packets as they arrive in routers. The authors describe some basic marking algorithms, such as appending each node's address to the end of the packet, node sampling, where each router chooses to write its address in the node field with some low probability, and edge sampling of participating routers. The victim receives all marking information and reconstructs probabilistically the attack path. In BIB003 , it is shown that the reconstruction of the attack paths based on the original Probabilistic Packet Marking techniques is computationally extremely intensive even for only a few attack sources. Despite its weaknesses, PPM is the basis of several related proposals. A similar in concept Internet Draft  suggests the use of a new type of ICMP messages specifically generated by routers for traceback purposes. For one in every 20,000 packets, the router copies the contents of the packet and information about adjacent routers into these customised ICMP messages. Again the victim should potentially be able to reconstruct the approximate attack path. In BIB009 , however, a DoS technique is presented, which can render such ICMP traceback not only useless, but possibly harmful for the network. Some of the limitations of PPM are addressed in BIB003 , where two marking schemes for IP traceback, the advanced and the authenticated one, are proposed. Since almost all Internet routes have less than 32 hops, an 11-bit hash of the IP address and a 5-bit hop count can be encoded in the 16 bits of a packet's fragmentation field. The authors describe two different hashing functions with which the order of the routers can be inferred when the attack path is reconstructed at the victim node. Others follow a different approach to probabilistic packet marking BIB006 ; they reframe the IP traceback problem as a polynomial reconstruction problem and use algebraic techniques originally developed for coding theory and machine learning, and present a series of schemes, all based on the principle of reconstructing a polynomial in a prime field, to encode the probabilistic path information inside the IP header with the very few bits that are available or non-crucial. A strength of this approach is that it is expected to benefit automatically from the parallel ongoing research in its underlying mathematical techniques. However, there have not been reported any relevant improvements yet. The majority of the traceback solutions are targeted at high-speed attacks, where a large number of packets are sent during the detection phase. In BIB004 BIB005 , on the other hand, a scheme is proposed to trace even single-packet attacks, such as those which exploit vulnerabilities in the packet processing of TCP/IP stack implementations ("Teardrop" is one of them, as presented in Section 2). This "Source Path Isolation Engine" (SPIE) system, supports tracing by storing a few bits of unique information, essentially packet digests, for a period of time as the packets traverse the Internet. To minimise the storage needs for the digest tables, they use Bloom filters, which are spaceefficient data structures with independent uniform hash functions. The software implementations of SPIE perform adequately for slow to medium speed routers. To achieve better results for faster routers, in  a hardware implementation as a processing unit inserted into the router, or as stand-alone connected to the router through an external interface, is described. In our opinion, the implementation cost and computation overhead of this approach appear to be very high for a technique oriented against an uncommon family of DoS attacks. In BIB011 , a new approach is proposed, which makes use of packet marking to further improves scalability, while still being able to trace a single IP packet. Both storage time and access time are reduced in comparison to SPIE. Single-packet traceback has also been recently explored in BIB010 , where again packet marking is used to avoid storing information in the routers, while a generalised bloom filter provides the basis of the traceback mechanism. The authors of BIB012 follow a similar packet marking technique, but also introduce an approach that is based on an AS-level overlay network, so as to allow incremental deployment. Their proposal does not require a priori knowledge of the network topology and they show how it combines with the BGP protocol for practical deployment.