Hash-Based iP traceback Alex C. Snoerent, Craig Partridge, Luis A Sanchez, Christine E. Jones Fabrice Tchakountio, Stephen T. Kent, and w. timothy strayer BBN Technologies 10 Moulton Street, Cambridge, MA 138 Isnoeren,craigcej,ftchakou,kentstrayer@bbn.com ABSTRACT While distributed denial of service attacks, typically conducted by The design of the IP protocol makes it difficult to reliably ident flooding network links with large amounts of traffic, are the most widely reported, there are other forms of network attacks. Many the originator of an IP packet. Even in the absence of any delio erate attempt to disguise a packets origin, wide-spread packet for- other classes of attacks can be conducted with significantly smaller warding techniques such as NAT and encapsulation may obscure packet flows. In fact, there are a number of widely-deployed op- the packets true source. Techniques have been developed to deter erating systems and routers that can be disabled by a single argeted packet [13]. To institute accountability for these atta mine the source of large packet flows, but, to date, no system has the source of individual packets must be identified been presented to track individual packets in an efficient, scalable Unfortunately, the anonymous nature of the IP protocol makes it difficult to accurately identify the true source of an IP datagram if We present a hash-based technique for IP traceback that generates the source wishes to conceal it. The network routing infrastructure audit trails for traffic within the network, and can trace the origin of is stateless and based largely on destination addresses; no entity in single IP packet delivered by the network in the recent past. We an IP network is officially responsible for ensuring the source ad- emonstrate that the system is effective, space-efficient(requiring dress is correct. Many routers employ a technique called ingress approximately 0.5% of the link capacity per unit time in storage), filtering [9] to limit source addresses of IP datagrams from a stub We present both analytic and simulation results showing the sy network to addresses belonging to that network, but not all routers tems effectiveness have the resources necessary to examine the source address of each incoming packet, and ingress filtering provides no protection on transit networks. Furthermore, spoofed addresses are legiti- 1 INTRODUCTION mately used by network address transla ATs), Mobile IP, and Today's Internet infrastructure is extremely vulnerable to motivated various unidirectional link technologies hybrid satellite and well-equipped attackers. Tools are readily available, from chitectures covertly exchanged exploit programs to publicly released vulner- Accordingly, a well-placed attacker can generate offending IP pack ability assessment software, to degrade performance or even dis- ets that appear to have originated from almost anywhere. further- able vital network services. The consequences are serious and, in- more, while techniques such as ingress filtering increase the diffi creasingly, financially disastrous, as can be seen by all-too-frequent culty of mounting an attack, transit networks are dependent upon headlines naming the most recent victim of an attack. their peers to perform the appropriate filtering. This interdepen dence is clearly unacceptable from a liability perspective; each mo- t Alex C. Snoeren is also with the MIT Laboratory for Computer Science tivated network must be able to secure itself independent (snoeren @lcs, mit.edu) Systems that can reliably trace individual packets back to their lUis A. Sanchez was with BBN Technologies; he is now with Megisto a first and important step in making attackers(or, at least, the systems they use)accountable. There are a number of This work was sponsored by the Defense Advanced Research significant challenges in the construction of such a tracing system Agency(DARPA)under contract No. N66001-00-C-8038. Vi clusions contained in this document are those of the authors an ncluding determining which packets to trace, maintaining privacy be interpreted as representing official policies, either expressed or implied (a tracing system should not adversely impact the privacy of legit mate users), and minimizing cost( both in router time spent tracking Permission to make digital or hard copies of all or part of this work for rather than forwarding packets, and in storage used to keep infor- fee provided that copie ot made or distributed for profit or commercial advantage, and that copies We have developed a Source path lsolation Engine (SPIE)to en- ear this notice and the full citation on the first page. To copy otherwise, to able IP traceback, the ability to identify the source of a particular IP packet given a copy of the packet to be traced, its destination, and an ugust 27-31, 2001, San Diego, California, USA pproximate time of receipt. Historically, tracing individual pack ACMl58113-411-8/010008.S5 ets has required prohibitive amounts of memory; one of SPIE's key
Hash-Based IP Traceback Alex C. Snoeren†, Craig Partridge, Luis A. Sanchez‡, Christine E. Jones, Fabrice Tchakountio, Stephen T. Kent, and W. Timothy Strayer BBN Technologies 10 Moulton Street, Cambridge, MA 02138 {snoeren, craig, cej, ftchakou, kent, strayer}@bbn.com ABSTRACT 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. 1 INTRODUCTION Today’s Internet infrastructure is extremely vulnerable to motivated and well-equipped attackers. Tools are readily available, from covertly exchanged exploit programs to publicly released vulnerability assessment software, to degrade performance or even disable vital network services. The consequences are serious and, increasingly, financially disastrous, as can be seen by all-too-frequent headlines naming the most recent victim of an attack. †Alex C. Snoeren is also with the MIT Laboratory for Computer Science (snoeren@lcs.mit.edu). ‡Luis A. Sanchez was with BBN Technologies; he is now with Megisto Systems, Inc. (lsanchez@megisto.com). This work was sponsored by the Defense Advanced Research Projects Agency (DARPA) under contract No. N66001-00-C-8038. Views and conclusions contained in this document are those of the authors and should not be interpreted as representing official policies, either expressed or implied. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGCOMM’01, August 27-31, 2001, San Diego, California, USA. Copyright 2001 ACM 1-58113-411-8/01/0008...$5.00 While distributed denial of service attacks, typically conducted by flooding network links with large amounts of traffic, are the most widely reported, there are other forms of network attacks. Many other classes of attacks can be conducted with significantly smaller packet flows. In fact, there are a number of widely-deployed operating systems and routers that can be disabled by a single welltargeted packet [13]. To institute accountability for these attacks, the source of individual packets must be identified. Unfortunately, the anonymous nature of the IP protocol makes it difficult to accurately identify the true source of an IP datagram if the source wishes to conceal it. The network routing infrastructure is stateless and based largely on destination addresses; no entity in an IP network is officially responsible for ensuring the source address is correct. Many routers employ a technique called ingress filtering [9] to limit source addresses of IP datagrams from a stub network to addresses belonging to that network, but not all routers have the resources necessary to examine the source address of each incoming packet, and ingress filtering provides no protection on transit networks. Furthermore, spoofed source addresses are legitimately used by network address translators (NATs), Mobile IP, and various unidirectional link technologies such as hybrid satellite architectures. Accordingly, a well-placed attacker can generate offending IP packets that appear to have originated from almost anywhere. Furthermore, while techniques such as ingress filtering increase the diffi- culty of mounting an attack, transit networks are dependent upon their peers to perform the appropriate filtering. This interdependence is clearly unacceptable from a liability perspective; each motivated network must be able to secure itself independently. Systems that can reliably trace individual packets back to their sources are a first and important step in making attackers (or, at least, the systems they use) accountable. There are a number of significant challenges in the construction of such a tracing system including determining which packets to trace, maintaining privacy (a tracing system should not adversely impact the privacy of legitimate users), and minimizing cost (both in router time spent tracking rather than forwarding packets, and in storage used to keep information). We have developed a Source Path Isolation Engine (SPIE) to enable IP traceback, the ability to identify the source of a particular IP packet given a copy of the packet to be traced, its destination, and an approximate time of receipt. Historically, tracing individual packets has required prohibitive amounts of memory; one of SPIE’s key 3
innovations is to reduce the memory requirement( down to 0.5% attack. The traceback system must not be confounded by a moti- link bandwidth per unit time)through the use of Bloom filters. By vated attacker who subverts a router with the intent to subvert the storing only packet digests, and not the packets themselves, SPIe tracing system also does not increase a network's vulnerability to eavesdropping The instability of Internet routing is well known [15] and its impli SPie therefore allows routers to efficiently determine if they for- warded a particular packet within a specified time interval while cations for tracing are important. Two packets sent by the same host maintaining the privacy of unrelated traffic. to the same destination may traverse wildly different paths. As a re- sult, any system that seeks to determine origins using multi-packet The rest of this paper examines SPIE in detail. We begin by defin- analysis techniques must be prepared to make sense of divergent ing the problem of IP traceback in section 2, and articulate the de- path information sired features of a traceback system. We survey previous work in section 3, relating their feature sets against our requirements. Sec The assumption that the packet size should not grow is pi the most controversial. There are a number of protocols today that tion 4 describes the digesting process in detail. Section 5 presents cause the packet size to grow, for example technologies that rely on an overview of the SPIE architecture, while section 6 offers a prac- IP tunnels, such as IPsec and mobile IP. However ical implementation of the concepts. Section 7 provides both an- packet size causes MTU problems and increases overhead sharply alytic and simulation results evaluating SPIEs traceback success (each byte of additional overhead reduces system bandwidth by rates. We discuss the issues involved in deploying SPIE in section 8 before concluding in section 9 with a brief look at future work. about 1%, given the average packet size of about 128 bytes). It follows that an efficient traceback system should not cause packet size to grow. 2 IP TRACEBACK We assume that an end host, and in particular the victim of an at- The concept of IP traceback is not yet well defined. In an tack, may be resource-poor and unable to maintain substantial ad- to clarify the context in which SPIE was developed, this ditional administrative state regarding the routing state or the pack presents a detailed and rather formal definition of traceback ets it has previously received. This assumption comes from the ope that presenting a strawman definition of traceback will also observed rise in special purpose devices such as microscopes, cam- help the community better evaluate different traceback scheme eras, and printers that are attached to the Internet but have few inter In order to remain consistent with the terminology in the literature nal resources other than those devoted to performing their primary we will consider a packet of interest to be nefarious, and term it an attack packet; similarly, the destination of the packet is a victim. We The final assumption that traceback queries are infrequent has im- note,however,that there are many reasons to trace the source of a portant design implications. It implies queries can be handled by a acket; many packets of interest are sent with no ill intent whats routers control path, and need not be dealt with on the forwarding ever path at line speed. While there may be auditing tasks associated with packet forwarding to support traceback that must be executed 2.1 Assumptions while forwarding, the processing of the audit trails is infrequent There are several important assumptions that a traceback system should make about a network and the traffic it carries 2.2 The goal Packets may be addressed to more than one physical host Duplicate packets may exist in the networ Ideally, a traceback system should be able to identify the source Routers may be subverted, but not often of any piece of data sent across the network. In an IP framework, Attackers are aware they are being traced the packet is the smallest atomic unit of data. Any smaller division of data(a byte, for instance)is contained within a unique packet. The routing behavior of the network may be unstable Hence an optimal Ip traceback system would precisely identify the The packet size should not grow as a result of tracing ource of an arbitrary IP packet. Any larger data unit or stream can End hosts may be resource constrained be isolated by searching for any particular packet containing data Traceback is an infrequent operation The first two assumptions are simply characteristics of the Internet As with any auditing system, a traceback system can only be effec- Protocol. IP packets may contain a multicast or broadcast address tive in networks in which it has been deployed. Hence we consider as their destination, causing the routing infrastructure to duplicate the source of a packet to be one of them internally. An attacker can also inject multiple, identical pack ets itself, possibly at multiple locations. A tracing system must The ingress point to the traceback-enabled network be prepared for a situation where there are multiple sources of the The actual host or network of origin ame(identical) packet, or a single source of multiple(also typi- One or more compromised routers within the enabled network The next two assumptions speak to the capabilities of the assist in concealing a packet's source, it becomes obvious that one acker(s). An attacker may gain access to routers along(or adjacent to)the path from attacker to victim by a variety of means. Further,a INdeed, w argue that it is desirable to trace the individual pack- ets within ecause the individual packets may have originated at sophisticated attacker is aware of the characteristics of the network, different si only at the victim)and are likely to have followed including the possibility that the network is capable of tracing an different 1
innovations is to reduce the memory requirement (down to 0.5% of link bandwidth per unit time) through the use of Bloom filters. By storing only packet digests, and not the packets themselves, SPIE also does not increase a network’s vulnerability to eavesdropping. SPIE therefore allows routers to efficiently determine if they forwarded a particular packet within a specified time interval while maintaining the privacy of unrelated traffic. The rest of this paper examines SPIE in detail. We begin by defining the problem of IP traceback in section 2, and articulate the desired features of a traceback system. We survey previous work in section 3, relating their feature sets against our requirements. Section 4 describes the digesting process in detail. Section 5 presents an overview of the SPIE architecture, while section 6 offers a practical implementation of the concepts. Section 7 provides both analytic and simulation results evaluating SPIE’s traceback success rates. We discuss the issues involved in deploying SPIE in section 8 before concluding in section 9 with a brief look at future work. 2 IP TRACEBACK The concept of IP traceback is not yet well defined. In an attempt to clarify the context in which SPIE was developed, this section presents a detailed and rather formal definition of traceback. We hope that presenting a strawman definition of traceback will also help the community better evaluate different traceback schemes. In order to remain consistent with the terminology in the literature, we will consider a packet of interest to be nefarious, and term it an attack packet; similarly, the destination of the packet is a victim. We note, however, that there are many reasons to trace the source of a packet; many packets of interest are sent with no ill intent whatsoever. 2.1 Assumptions There are several important assumptions that a traceback system should make about a network and the traffic it carries: • Packets may be addressed to more than one physical host • Duplicate packets may exist in the network • Routers may be subverted, but not often • Attackers are aware they are being traced • The routing behavior of the network may be unstable • The packet size should not grow as a result of tracing • End hosts may be resource constrained • Traceback is an infrequent operation The first two assumptions are simply characteristics of the Internet Protocol. IP packets may contain a multicast or broadcast address as their destination, causing the routing infrastructure to duplicate them internally. An attacker can also inject multiple, identical packets itself, possibly at multiple locations. A tracing system must be prepared for a situation where there are multiple sources of the same (identical) packet, or a single source of multiple (also typically identical) packets. The next two assumptions speak to the capabilities of the attacker(s). An attacker may gain access to routers along (or adjacent to) the path from attacker to victim by a variety of means. Further, a sophisticated attacker is aware of the characteristics of the network, including the possibility that the network is capable of tracing an attack. The traceback system must not be confounded by a motivated attacker who subverts a router with the intent to subvert the tracing system. The instability of Internet routing is well known [15] and its implications for tracing are important. Two packets sent by the same host to the same destination may traverse wildly different paths. As a result, any system that seeks to determine origins using multi-packet analysis techniques must be prepared to make sense of divergent path information. The assumption that the packet size should not grow is probably the most controversial. There are a number of protocols today that cause the packet size to grow, for example technologies that rely on IP tunnels, such as IPsec and mobile IP. However, increasing the packet size causes MTU problems and increases overhead sharply (each byte of additional overhead reduces system bandwidth by about 1%, given the average packet size of about 128 bytes). It follows that an efficient traceback system should not cause packet size to grow. We assume that an end host, and in particular the victim of an attack, may be resource-poor and unable to maintain substantial additional administrative state regarding the routing state or the packets it has previously received. This assumption comes from the observed rise in special purpose devices such as microscopes, cameras, and printers that are attached to the Internet but have few internal resources other than those devoted to performing their primary task. The final assumption that traceback queries are infrequent has important design implications. It implies queries can be handled by a router’s control path, and need not be dealt with on the forwarding path at line speed. While there may be auditing tasks associated with packet forwarding to support traceback that must be executed while forwarding, the processing of the audit trails is infrequent with respect to their generation. 2.2 The goal Ideally, a traceback system should be able to identify the source of any piece of data sent across the network. In an IP framework, the packet is the smallest atomic unit of data. Any smaller division of data (a byte, for instance) is contained within a unique packet. Hence an optimal IP traceback system would precisely identify the source of an arbitrary IP packet. Any larger data unit or stream can be isolated by searching for any particular packet containing data within the stream.1 As with any auditing system, a traceback system can only be effective in networks in which it has been deployed. Hence we consider the source of a packet to be one of: • The ingress point to the traceback-enabled network • The actual host or network of origin • One or more compromised routers within the enabled network If one assumes that any router along the path may be co-opted to assist in concealing a packet’s source, it becomes obvious that one 1Indeed, we would argue that it is desirable to trace the individual packets within a stream because the individual packets may have originated at different sites (meeting only at the victim) and are likely to have followed different paths through the network. 4
time to live(TTL) field and checksum recomputation, IP packets may be further transformed by intermediate routers. Packet trans formation may be the result of valid processing, router error, or malicious intent. A traceback system need not concern itself with packet transformations resulting from error or malicious behavior. Packets resulting from such transformations only need be traced to the point of transformation, as the transforming node either needs to be fixed or can be considered a co-conspirator. An optimum tions, however, back to the source of the original packet Valid packet transformations are defined as a change of packet state that allows for or enhances network data delivery. Transformations occur due to such reasons as hardware needs, network management protocol requirements, and source request. Based on the transform Taining attack paths 1. Packet Encapsulation: A new packet is generated in which the tical packets injected by Al and A2 and received by the vic- original packet is encapsulated as the payload(e.g, IPsec) tim, V. The arrows indicate links traversed by the packet; The new packet is forwarded to an intermediate destination nodes on an attack path are shaded: A1, Rl, Ra, Rr, R9, v and {A2,R2,Rs,R7,R9,V} 2. Packer Generation: One or more packets are genera direct result of an action by the router on the origin must attempt to discern not only the packet's source, but its entire ath through the network. If a path can be traced through any num- (e.g. an ICMP Echo Reply sent in response to an ICl ber of non -subverted routers. then it must terminate at either the Request). The new packets are forwarded and processed in- dependent of the original packet. source of the flow or pass through a subverted router which can be considered to be a co-conspirator and treated appropriately. Hence, we are interested in constructing an attack path, where the path RFC 1812-compliant routers [u such as packet fragmentation, IP consists of each router traversed by the packet on Its ourney irom option processing, ICMP processing, and packet duplication. Net source to the victim. Because conspiring routers can fabricate trace work address translation(NAT) and both IP-in-IP and IPsec tunnel information, the path can only be guaranteed to be accurate on the portion from the victim to the first source--multiple sources may be ing are also notable forms of packet transformation. Many of these transformations result in an irrecoverable loss of the original packet identified if routers are subverted. Further, since multiple, indistin- uishable packets may be injected into the network from differen state due to the stateless nature of ip networks ources in the general case, a traceback system should construct an A study of wide-area traffic patterns conducted by the Cooperative attack graph composed of the attack paths for every instance of the Association for Internet Data Analysis(CAIDA)found less than attack packet that arrived at the victim. Figure I depicts the net- 3% of lP traffic undergoes common transformation and IP tunnel- work as viewed by the victim and a particular attack graph for that ing [12]. While this study did not encompass all forms of transfor- nat An attack graph may contain false positives in the presence of sub- fraction of the overall IP traffic traversing the Internet today. How. verted routers; that is, the attack graph may identify sources that ever, attackers may transmit packets engineered to experience trans- did not actually emit the packet. We argue this is an unavoidable formation. The ability to trace packets that undergo transformation consequence of admitting the possibility of subverted routers. An is, therefore, an essential feature of any viable traceback system attempting to minimize false positives; it must never exonerate an 3 RELATED WORK attacker by not including the attacker in the attack graph. Further, when a traceback system is deployed, it must not reduce the There are two approaches to the problem of determining the route privacy ofIP communications. In particular, entities not involved in of a packet flow one can audit the flow as it traverses the network, he generation, forwarding, or receipt of the original packet should or one can attempt to infer the route based upon its impact on the not be able to gain access to packet contents by either utilizing or state of the network. Both approaches become increasingly difficult as part of participating in the IP traceback system. An ideal IP as the size of the flow decreases but the latter becomes infeasible traceback system must not expand the eavesdropping capabilities when fow sizes approach a single packet because small flows gen of a malicious party Route inference was pioneered by Burch and Cheswick [5] who 2.3 Transformations considered the restricted problem of large flows and pro- posed a novel technique that systematically It is important to note that packets may be modified during the for- work links. By watching for variations in the received packet flow warding process. In addition to the standard decrementing of the due to the restricted link bandwidth, they are able to infer the flows
V R6 R8 R9 R7 S1 R1 A1 S3 R4 A2 S4 R2 R3 S5 R5 Figure 1: An attack graph containing attack paths for two identical packets injected by A1 and A2 and received by the victim, V . The arrows indicate links traversed by the packet; nodes on an attack path are shaded: {A1, R1, R4, R7, R9, V } and {A2, R2, R5, R7, R9, V }. must attempt to discern not only the packet’s source, but its entire path through the network. If a path can be traced through any number of non-subverted routers, then it must terminate at either the source of the flow or pass through a subverted router which can be considered to be a co-conspirator and treated appropriately. Hence, we are interested in constructing an attack path, where the path consists of each router traversed by the packet on its journey from source to the victim. Because conspiring routers can fabricate trace information, the path can only be guaranteed to be accurate on the portion from the victim to the first source—multiple sources may be identified if routers are subverted. Further, since multiple, indistinguishable packets may be injected into the network from different sources in the general case, a traceback system should construct an attack graph composed of the attack paths for every instance of the attack packet that arrived at the victim. Figure 1 depicts the network as viewed by the victim and a particular attack graph for that victim. An attack graph may contain false positives in the presence of subverted routers; that is, the attack graph may identify sources that did not actually emit the packet. We argue this is an unavoidable consequence of admitting the possibility of subverted routers. An ideal traceback system, however, produces no false negatives while attempting to minimize false positives; it must never exonerate an attacker by not including the attacker in the attack graph. Further, when a traceback system is deployed, it must not reduce the privacy of IP communications. In particular, entities not involved in the generation, forwarding, or receipt of the original packet should not be able to gain access to packet contents by either utilizing or as part of participating in the IP traceback system. An ideal IP traceback system must not expand the eavesdropping capabilities of a malicious party. 2.3 Transformations It is important to note that packets may be modified during the forwarding process. In addition to the standard decrementing of the time to live (TTL) field and checksum recomputation, IP packets may be further transformed by intermediate routers. Packet transformation may be the result of valid processing, router error, or malicious intent. A traceback system need not concern itself with packet transformations resulting from error or malicious behavior. Packets resulting from such transformations only need be traced to the point of transformation, as the transforming node either needs to be fixed or can be considered a co-conspirator. An optimum traceback system should trace packets through valid transformations, however, back to the source of the original packet. Valid packet transformations are defined as a change of packet state that allows for or enhances network data delivery. Transformations occur due to such reasons as hardware needs, network management, protocol requirements, and source request. Based on the transform produced, packet transformations are categorized as follows: 1. Packet Encapsulation: A new packet is generated in which the original packet is encapsulated as the payload (e.g., IPsec). The new packet is forwarded to an intermediate destination for de-encapsulation. 2. Packet Generation: One or more packets are generated as a direct result of an action by the router on the original packet (e.g. an ICMP Echo Reply sent in response to an ICMP Echo Request). The new packets are forwarded and processed independent of the original packet. Common packet transformations include those performed by RFC 1812-compliant routers [1] such as packet fragmentation, IP option processing, ICMP processing, and packet duplication. Network address translation (NAT) and both IP-in-IP and IPsec tunneling are also notable forms of packet transformation. Many of these transformations result in an irrecoverable loss of the original packet state due to the stateless nature of IP networks. A study of wide-area traffic patterns conducted by the Cooperative Association for Internet Data Analysis (CAIDA) found less than 3% of IP traffic undergoes common transformation and IP tunneling [12]. While this study did not encompass all forms of transformation (NAT processing being a notable omission), it seems safe to assume that packet transformations account for a relatively small fraction of the overall IP traffic traversing the Internet today. However, attackers may transmit packets engineered to experience transformation. The ability to trace packets that undergo transformation is, therefore, an essential feature of any viable traceback system. 3 RELATED WORK There are two approaches to the problem of determining the route of a packet flow: one can audit the flow as it traverses the network, or one can attempt to infer the route based upon its impact on the state of the network. Both approaches become increasingly difficult as the size of the flow decreases, but the latter becomes infeasible when flow sizes approach a single packet because small flows generally have no measurable impact on the network state. Route inference was pioneered by Burch and Cheswick [5] who considered the restricted problem of large packet flows and proposed a novel technique that systematically floods candidate network links. By watching for variations in the received packet flow due to the restricted link bandwidth, they are able to infer the flow’s 5
route. This requires considerable knowledge of network topology probability of detecting small flows and does not alleviate the se- and the ability to generate large packet floods on arbitrary network curity issues raised by storing complete packets in the router. The One can categorize auditing techniq ues into two c to the way in which they balance resource requirements across the Alternatively, routers can be tasked to perform more sophisticat network components. Some techniques require resources at both auditing in real time, extracting a smaller amount of information the end host and the routing infrastructure, others require resources as packets are forwarded. Many currently available routers support only within the network itself. Of those that require only infrastruc- input debugging a feature that identifies on which incoming port ure support, some add packet processing to the forwarding engine a particular outgoing packet(or set of packets) of interest arrived of the routers while others offload the computation to the control Since no history is stored, however, this process must be activated path of the routers before an attack packet passes by. Furthermore, due to the high overhead of this operation on many popular router architectures 3.1 End-host schemes activating it may have adverse effects on the trafic currently being serviced by the router. Some auditing approaches attempt to distribute the burden by stor ing state at the end hosts rather than in the network. Routers notify the packet destination of their presence on the route. Because IP 3.3 Specialized routing packets cannot grow arbitrarily large, schemes have been developed to reduce the amount of space required to send such information. One of the main problems with the link testing or logging meth Recently proposed techniques by Savage et al. [21]and Bellovin[2] ods above is the large amount of repetition required. A trace is explore in-band and out-of-band signaling, respectively Because of the high overhead involved, neither Savage nor Bellovin along the way. Once the incoming link or links have been identified attempt to provide audit information for every packet. Instead, each employs probabilistic methods that allow sufficiently large packet Several techniques have been developed to streamline and automate lows to be traced. By providing partial information on a subset this process. Some IsPs have developed their own ad hoc mecha packets in a flow, auditing routers enable an end host to recon- nisms for automatically conducting input debugging across their struct the entire path traversed by the packet flow after red eceiving a networks. Schnackenberg et al. [22I propose a special Intruder sufficient number of packets belonging to the flow Detection and Isolation Protocol (DiP)to facilitate interaction be The two schemes diverge in the methods used to communicate the tween routers involved in a traceback effort. IDiP does not specify information to the end host Savage et al. employ a packet marking how participating entities should track packet traffic; it simply re- heme that encodes the information in rarely-used fields within quires that they be able to determine whether or not they have seen the IP header itself. This approach has been improved upon by a component of an attack matching a certain description. Even with of paths automated tools, however, each router in the IsP must support input ticate the encodings (23). In order to avoid the backwards compat. debugging or logging which are not common in today s high-speed bility issues and increased computatio cated encoding schemes employed in the packet marking schemes In order to avoid this requirement, Stone [24] suggests constructing Bellovin's scheme(and later extensions by Wu et al. [25])simply an overlay network connecting all the edge routers of an ISP. By sends the audit information in an ICMP message using a deliberately simple topology of specialized routers, suspi- cious flows can be dynamically rerouted across the special tracking 3.2 Infrastructure approaches network for analysis. This approach has two major shortcomings First, the attack must be sufficiently long-lived to allow the Isto End-host schemes require the end hosts to log meta data in case an effect the rerouting before the relevant flow terminates.Second,the incoming packet proves to be offensive. Alternatively, the network itself can be charged with maintaining the audit trails routing change is perceptible by the attacker, and an especially mo- tivated attacker may be able to escape detection by taking appropri- The obvious approach to auditing packet flow is simply to log pack- ate action. While techniques exist to hide precisely what changed ets at various points throughout the network and then use appropri- about the route, changes in layer-three topology are hard to mask the pack network. Logging requires no computation on the router's fast path and, thus, can be implemented efficiently in today's router architec- 4 PACKET DIGESTING ture. Sager suggests such a monitoring approach [19]. However the effectiveness of the logs is limited by the amount of space avail- SPIe, the Source Path Isolation Engine, uses auditing techniques to able to store them. Given todays link speeds, packet logs quickly support the traceback of individual packets while reducing the stor- grow to intractable sizes, even over relatively short time frames. An age requirements by several orders of magnitude over current log oC-192 link is capable of transterring 1. 25GB per second. If one ing and storing 32-bit packet digests rather than storing the packets ds to conduct a query, a router with 16 links 1. 2TB of high-speed storage themselves. In addition to reducing storage requirements, storing packet digests instead of the actual packet contents preserves traf- These requirements can be reduced by sampling techniques similar fic confidentiality by preventing SPle from being used as a tool for to those of the end-host schemes, but down-sampling reduces the eavesdropping
route. This requires considerable knowledge of network topology and the ability to generate large packet floods on arbitrary network links. One can categorize auditing techniques into two classes according to the way in which they balance resource requirements across the network components. Some techniques require resources at both the end host and the routing infrastructure, others require resources only within the network itself. Of those that require only infrastructure support, some add packet processing to the forwarding engine of the routers while others offload the computation to the control path of the routers. 3.1 End-host schemes Some auditing approaches attempt to distribute the burden by storing state at the end hosts rather than in the network. Routers notify the packet destination of their presence on the route. Because IP packets cannot grow arbitrarily large, schemes have been developed to reduce the amount of space required to send such information. Recently proposed techniques by Savage et al. [21] and Bellovin [2] explore in-band and out-of-band signaling, respectively. Because of the high overhead involved, neither Savage nor Bellovin attempt to provide audit information for every packet. Instead, each employs probabilistic methods that allow sufficiently large packet flows to be traced. By providing partial information on a subset of packets in a flow, auditing routers enable an end host to reconstruct the entire path traversed by the packet flow after receiving a sufficient number of packets belonging to the flow. The two schemes diverge in the methods used to communicate the information to the end host. Savage et al. employ a packet marking scheme that encodes the information in rarely-used fields within the IP header itself. This approach has been improved upon by Song and Perrig to improve the reconstruction of paths and authenticate the encodings [23]. In order to avoid the backwards compatibility issues and increased computation required by the sophisticated encoding schemes employed in the packet marking schemes, Bellovin’s scheme (and later extensions by Wu et al. [25]) simply sends the audit information in an ICMP message. 3.2 Infrastructure approaches End-host schemes require the end hosts to log meta data in case an incoming packet proves to be offensive. Alternatively, the network itself can be charged with maintaining the audit trails. The obvious approach to auditing packet flow is simply to log packets at various points throughout the network and then use appropriate extraction techniques to discover the packet’s path through the network. Logging requires no computation on the router’s fast path and, thus, can be implemented efficiently in today’s router architecture. Sager suggests such a monitoring approach [19]. However, the effectiveness of the logs is limited by the amount of space available to store them. Given today’s link speeds, packet logs quickly grow to intractable sizes, even over relatively short time frames. An OC-192 link is capable of transferring 1.25GB per second. If one allows 60 seconds to conduct a query, a router with 16 links would require 1.2TB of high-speed storage. These requirements can be reduced by sampling techniques similar to those of the end-host schemes, but down-sampling reduces the probability of detecting small flows and does not alleviate the security issues raised by storing complete packets in the router. The ability of an attacker to break into a router and capture terrabytes of actual traffic has severe privacy implications. Alternatively, routers can be tasked to perform more sophisticated auditing in real time, extracting a smaller amount of information as packets are forwarded. Many currently available routers support input debugging, a feature that identifies on which incoming port a particular outgoing packet (or set of packets) of interest arrived. Since no history is stored, however, this process must be activated before an attack packet passes by. Furthermore, due to the high overhead of this operation on many popular router architectures, activating it may have adverse effects on the traffic currently being serviced by the router. 3.3 Specialized routing One of the main problems with the link testing or logging methods above is the large amount of repetition required. A trace is conducted in a hop-by-hop fashion requiring a query at each router along the way. Once the incoming link or links have been identified, the process must be repeated at the upstream router. Several techniques have been developed to streamline and automate this process. Some ISPs have developed their own ad hoc mechanisms for automatically conducting input debugging across their networks. Schnackenberg et al. [22] propose a special Intruder Detection and Isolation Protocol (IDIP) to facilitate interaction between routers involved in a traceback effort. IDIP does not specify how participating entities should track packet traffic; it simply requires that they be able to determine whether or not they have seen a component of an attack matching a certain description. Even with automated tools, however, each router in the ISP must support input debugging or logging which are not common in today’s high-speed routers for reasons discussed above. In order to avoid this requirement, Stone [24] suggests constructing an overlay network connecting all the edge routers of an ISP. By using a deliberately simple topology of specialized routers, suspicious flows can be dynamically rerouted across the special tracking network for analysis. This approach has two major shortcomings. First, the attack must be sufficiently long-lived to allow the ISP to effect the rerouting before the relevant flow terminates. Second, the routing change is perceptible by the attacker, and an especially motivated attacker may be able to escape detection by taking appropriate action. While techniques exist to hide precisely what changed about the route, changes in layer-three topology are hard to mask. 4 PACKET DIGESTING SPIE, the Source Path Isolation Engine, uses auditing techniques to support the traceback of individual packets while reducing the storage requirements by several orders of magnitude over current logbased techniques [19]. Traffic auditing is accomplished by computing and storing 32-bit packet digests rather than storing the packets themselves. In addition to reducing storage requirements, storing packet digests instead of the actual packet contents preserves traf- fic confidentiality by preventing SPIE from being used as a tool for eavesdropping. 6
Version Header Length ype of Service Identification Fragment Offset Checksum Source Address 3000 Destination Address 1e05 Payload 2022242628303234363840 Figure 2: The fields of an IP packet. Fields in gray are masked Figure 3: The fraction of packets that collide as a function of pre- out before digesting, including the Type of Service, Time to Live fix length. The WAN trace represents 985, 150 packets( with 5, 801 (TTL), IP checksum, and IP options fields duplicates removed) collected on July 20, 2000 at the University of Florida oC-3 gateway [14]. The lan trace consists of one million packets(317 duplicates removed)observed on an Ethernet segment 4.1 Hash input at the MIT Lab for Computer Science represent an IP packet and enable the identification of the packet wide area with identical prefixes indicates that packets with match- able to limit the size of the hash input both for performance and ng prefix lengths of 22 and 23 bytes are ICMP Time Exceeded for reasons discussed below (c f. section 5.3). Duffield and Gross- packets with matching prefixes between 24 and 31 bytes in leng glauser encountered similar requirements while sampling a subset are TCP packets with IP identifications also set to zero which are forwarded packets in an attempt to measure tratfic fiows [7]. We first differentiated by the TCP sequence number or acknowledg use a similar approach, masking variant packet content and select- ng an appropriate-length prefix of the packet to use as input to the digesting function. Our choice of invariant fields and prefix length The markedly higher collision rate in the local area is due to the lack is slightly different, however of address and traffic diversity. This expected result does not sig Figure 2 shows an IP packet and the fields included by the spie di- nificantly impact SPIEs performance, however. LANS are likely to exist at only two points in an attack gesting function. SPIE computes digests over the invariant portion ing the victim and the attacker(s). False positives on the victims of the IP header and the first 8 bytes of the payload. Frequently local network can be easily eliminated from the attack graph--they modified header fields are masked prior to digesting. Note that be- likely share the same gateway router in any event. False positives yond the obvious fields(TTL, TOS, and checksum), certain IP op- at the source are unlikely if the attacker is using spoofed source ad- tions cause routers to rewrite the option field at various intervals. To dresses dresses, as this provides the missing diversity in attack traffic, and ensure a packet appears identical at all steps along its route, SPIE remain in the immediate vicinity of the true attacker by definition masks or compensates for these fields when computing the packet Hence, for the purposes of SPIE, IP packets are effectively distin- digests.It is important to note that the invariant IP fields used for guished by the first 28 invariant bytes of the packet SPie digesting may occasionally be modified by a packet transform 4.2 Bloom filters Our research indicates that the first 28 invariant bytes of a packet masked IP header plus the first 8 bytes of payload) are sufficient Storing the set of digests for the traffic forwarded by the router to differentiate almost all non-identical packets. Figure 3 presents would require massive amounts of storage. Instead, SPie uses a the rate of packet collisions for an increasing prefix length for two space-efficient data structure known as a bloom filter to record representative traces: a Wan trace from an OC-3 gateway router, packet digests [4]. A Bloom filter computes k distinct packet di- and a Lan trace from an active 100Mb Ethernet segment (Results gests for each packet using independent uniform hash functions were similar for traces across a number of sites. )Two unique pack- nd uses the n-bit results to index into a 2-sized bit array. The ets which are identical up to the specified prefix length are termed array is initialized to all zeros, and bits are set to one as packets are a collision. A 28-byte prefix results in a collision rate of approxi- received. Figure 4 depicts a Bloom filter with k hash functions mately 0.00092% in the wide area and 0. 139% on the Lan Membership tests can be conducted simply by computing the k di Unlike similar results reported by duffield and Grossglauser [7, fig. gests on the packet in question and checking the indicated bit posi 41,our results include only unique packets, exact duplicates were ber of current operating systems, removed from the packet trace. Close inspection of packets in the including recent versions of Linux, frequently set the IP
Payload Options Destination Address Source Address TTL Protocol Checksum Identification D F M F Fragment Offset Version Header Length Type of Service Total Length Figure 2: The fields of an IP packet. Fields in gray are masked out before digesting, including the Type of Service, Time to Live (TTL), IP checksum, and IP options fields. 4.1 Hash input The packet content used as input to the hash function must uniquely represent an IP packet and enable the identification of the packet across hops in the forwarding path. At the same time, it is desirable to limit the size of the hash input both for performance and for reasons discussed below (c.f. section 5.3). Duffield and Grossglauser encountered similar requirements while sampling a subset of forwarded packets in an attempt to measure traffic flows [7]. We use a similar approach, masking variant packet content and selecting an appropriate-length prefix of the packet to use as input to the digesting function. Our choice of invariant fields and prefix length is slightly different, however. Figure 2 shows an IP packet and the fields included by the SPIE digesting function. SPIE computes digests over the invariant portion of the IP header and the first 8 bytes of the payload. Frequently modified header fields are masked prior to digesting. Note that beyond the obvious fields (TTL, TOS, and checksum), certain IP options cause routers to rewrite the option field at various intervals. To ensure a packet appears identical at all steps along its route, SPIE masks or compensates for these fields when computing the packet digests. It is important to note that the invariant IP fields used for SPIE digesting may occasionally be modified by a packet transform (c.f. section 5.3). Our research indicates that the first 28 invariant bytes of a packet (masked IP header plus the first 8 bytes of payload) are sufficient to differentiate almost all non-identical packets. Figure 3 presents the rate of packet collisions for an increasing prefix length for two representative traces: a WAN trace from an OC-3 gateway router, and a LAN trace from an active 100Mb Ethernet segment. (Results were similar for traces across a number of sites.) Two unique packets which are identical up to the specified prefix length are termed a collision. A 28-byte prefix results in a collision rate of approximately 0.00092% in the wide area and 0.139% on the LAN. Unlike similar results reported by Duffield and Grossglauser [7, fig. 4], our results include only unique packets; exact duplicates were removed from the packet trace. Close inspection of packets in the 1e-06 1e-05 0.0001 0.001 0.01 0.1 1 20 22 24 26 28 30 32 34 36 38 40 Fraction of Collided Packets Prefix Length (in bytes) WAN LAN Figure 3: The fraction of packets that collide as a function of pre- fix length. The WAN trace represents 985,150 packets (with 5,801 duplicates removed) collected on July 20, 2000 at the University of Florida OC-3 gateway [14]. The LAN trace consists of one million packets (317 duplicates removed) observed on an Ethernet segment at the MIT Lab for Computer Science. wide area with identical prefixes indicates that packets with matching prefix lengths of 22 and 23 bytes are ICMP Time Exceeded error packets with the IP identification field set to zero. Similarly, packets with matching prefixes between 24 and 31 bytes in length are TCP packets with IP identifications also set to zero which are first differentiated by the TCP sequence number or acknowledgment fields.2 The markedly higher collision rate in the local area is due to the lack of address and traffic diversity. This expected result does not significantly impact SPIE’s performance, however. LANs are likely to exist at only two points in an attack graph: immediately surrounding the victim and the attacker(s). False positives on the victim’s local network can be easily eliminated from the attack graph—they likely share the same gateway router in any event. False positives at the source are unlikely if the attacker is using spoofed source addresses, as this provides the missing diversity in attack traffic, and remain in the immediate vicinity of the true attacker by definition. Hence, for the purposes of SPIE, IP packets are effectively distinguished by the first 28 invariant bytes of the packet. 4.2 Bloom filters Storing the set of digests for the traffic forwarded by the router would require massive amounts of storage. Instead, SPIE uses a space-efficient data structure known as a Bloom filter to record packet digests [4]. A Bloom filter computes k distinct packet digests for each packet using independent uniform hash functions, and uses the n-bit results to index into a 2n-sized bit array. The array is initialized to all zeros, and bits are set to one as packets are received. Figure 4 depicts a Bloom filter with k hash functions. Membership tests can be conducted simply by computing the k digests on the packet in question and checking the indicated bit posi- 2Further investigation indicates a number of current operating systems, including recent versions of Linux, frequently set the IP ID to zero. 7