Draft S. Felix Wu Internet Engineering Task Force UCDavis File: draft-wu-itrace-intention-00.txt Lixia Zhang Expires August 2001 UCLA Dan Massey, Allison Mankin USC/ISI Febuary 2001 Intention-Driven ICMP Trace-Back <draft-wu-itrace-intention-00.txt> Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/lid-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Distribution of this memo is unlimited. This Internet Draft expires August 23, 2001. 1. Abstract This draft describe an enhancement over the current iTrace proposal such that we can dynamically trace more closely to the DDoS slaves with the same number of ICMP trace-back messages. Wu, Zhang, Massey and Mankin [Page 1]
Internet Draft Intention-Driven iTrace Feburary 2000 1. Introduction: The probability of iTrace message generation on a particular router in the current internet draft is static and small (about 1 over 20,000) such that the overhead introduced by the iTrace messages is small. However, if each DDoS slave produces a relatively small amount of attack traffic, then, the probability for a nearby router to generate a valuable iTrace packet is very small. Statistically, the routers closer to the victim have higher probability to send iTrace messages toward the true victim, while the routers closer to the true slaves might send the iTrace messages to non-victim. We use the following example to illustrate our point: An BGP router R_B has N entries in its routing table, e[1], e[2],..., e[N]. When R_B forwards an IP packet, it will check the destination IP address and decides which routing entry should be used. The probability for using routing entry e[i] is Prob(e[i]), which represents R_B's traffic distribution toward e[i] (an IP address or a range of IP addresses). Certainly, the sum of Prob(e[i]) is 1. We assume that we have one DDoS victim, X, and from R_B's point of view, the routing entry e[x] should be used to reach X. Therefore, when the router R_B generates an iTrace message, the probability that this message will be delivered to the true victim X is no more than Prob(e[x]). Please note that since some of the routing entries at R_B possibly represent aggregated IP addresses. Thus, even if the routing entry e[x] is used to forward an IP packet, it might not be for the true victim X. Under this simple statistical model, if R_B dedicates K units of its resources to produce iTrace messages, then at least (1 - Prob(e[x])) * K units of resources are wasted statistically. In practice, if the attacker uses a large number of slaves and each of them generates a small amount of DDoS traffic, then it is not very likely for a close-by router to generate the "valuable" iTrace message. For instance, if a slave is in NCSU and the victim is eBay, then the victim eBay might receive an iTrace message from its upstream ISP, but the chance from NCSU can be very small. In this proposal, we introduce a new mechanism "intention-driven" iTrace to resolve the above problem. Our objectives are: (a) The probability for generating "valuable" iTrace messages is significantly higher than the original static iTrace scheme. (b) The number of iTrace messages generated by each router remains the same. (c) The new mechanism is compatible with the current iTrace scheme such that we do not require every router to support the new mechanism. (d) The design and implementation of the new mechanism is simple, efficient, secure and scaleable. 2. Intention-Driven iTrace: We propose to associate each routing entry with an extra attribute called "intention." If the value of "intention" for a particular route entry is high, then the network nodes under this route entry together have high desire to receive iTrace messages. In other words, some of them are under serious DDoS attacks. On the other hand, if a low intention value implies that either the network nodes are NOT under DDoS attacks or they are indeed under DDoS attacks but they do not care about iTrace messages. The intention value for route entry e[x] is I(e[x]), which is a number between 1 and I-MAX (e.g., I-MAX can be 10,000). With this new attribute I(e[x]), the iTrace message generation is different: we multiply the traffic distribution probability with the intention value of the same route entry: Prob(e[x]) * I(e[x]). Based on this new value, the router will decide which route entry should receive the next iTrace message. For instance, R_b has four entries in the routing table, and Prob(e[1]) = Prob(e[2]) = Prob(e[3]) = Prob(e[4]) = 0.25. We assume that e[1] contains the real victim. Without intention-driven, the chance that the real victim will receive iTrace messages from R_b is no more than 0.25. Let us set the intention values: I(e[1]) = 7, while I(e[2]) = I(e[3]) = I(e[4]) = 1. Therefore, the chance is increased to 0.7 for e[1]. 3. How to implement Intention-Driven iTrace on a Router? In the original iTrace proposal, an iTrace message will be generated with a small probability and, when this happens, we call it a "iTrace trigger." Under the intention driven iTrace, we separate the implementation into two parts: the processing for each incoming data packet and the processing for each iTrace trigger. Please note that it is desirable to have a very efficient per-data packet process, while it is more tolerable to spend more processing time for per-iTrace packet processing. 3.1. Routing Table Extensions: We totally need to introduce three new attributes for each route entry, e[x]: the intention value, I(e[x]), an iTrace bit, iTr(e[x]), and a packet count, Count(e[x]). The default values for these three new attributes are 1, 0, 0, respectively. The iTr(e[x]) bit represents whether an iTrace message should be sent through e[x]. If iTr(e[x]) is equal to 1, then an iTrace should be sent toward x. Otherwise, no iTrace message should be sent through e[x]. Count(e[x]) represents the number of IP packets that have been forwarded through the route entry e[x]. It is used to compute the traffic distribution. In section 4, we will discuss how to the value of intention. In this section, we will focus on how the other two attributes, iTr(e[x]) and Count(e[x]), are updated and used. 3.2. Per-Data Packet Processing: When an IP packet arrives, the router will first decide which routing entry should be used to forward this packet. If the iTr(e[x]) bit is 1, then an iTrace message is generated toward the destination IP address of this packet. After the iTrace message is sent, the iTr(e[x]) bit is reset to 0 and Count(e[x]) is incremented by 1. On the other hand, if the iTr(e[x]) bit is 0, then we just increment the value of Count(e[x]) by 1. The following is the pseudo code for this part of processing: int perDataPacketProcess (IP *p) { RouteEntry *re = findRouteEntry(p->destinationIPaddr); if (re == NULL) return -1; if (re->iTr == 1) { sendiTrace(p); re->iTr = 0; } re->count++; regularPacketForwarding(p, re); return 0; } 3.3. Per-iTrace Trigger Processing: When an iTrace trigger occurs, instead of directly sending an iTrace message, the router will compute a value, for each route entry, representing the multiplication of the intention value (I(e[x])) and the packet distribution (Count(e[x])). Then, the router will flip a coin, based on the values we just computed, to decide which route entry should generate the next iTrace message. Once it is decided, the iTrace bit for the selected entry will be set to 1. In any case, the Count(e[x]) value for all the entries will be cleared to zero. The following is the pseudo for per-itrace trigger processing. int periTraceTriggerProcess (RouteEntry *RETable) { int i; long long sum = 0; long long iTr_rand; for(i=0; i<N; i++) { RouteEntry *re = &(RETable[i]); re->value = re->count * re->intention; sum += re->value; re->count = 0; } iTr_rand = myrand(0, sum); i = randomRouteEntry(RETable, iTr_rand); re->iTr = 1; return 0; } 3.4. iTrace De-aggregation Option: This option is useful to enhance the probability further under route aggregation. When a router R_B receives an IP packet with ICMP Traceback from a upstream router (i.e., some other router R_origin generated this iTrace message), the R_B will call the periTraceTriggerProcess function immediately. Likewise, one route entry of R_B will have the iTr(e[x]) bit set to 1. Later, when a data packet for this particular route entry comes, a iTrace message will be generated. But, under this option, the originator of this iTrace message should be R_origin as the iTrace message was originated by R_origin, not R_B. 4. How to Set the Intention Value? In this section, we present a way to set the Intention value for each router and for each route entry. We propose to have a new BGP extension: the Intention attribute. When a BGP router advertises the reachability of some network address, it will also attach the Intention value for that network. Therefore, when this BGP update is received by some downstream BGP routers, the intention value of the corresponding route entry will be updated the attached value. Furthermore, when BGP updates are aggregated, the intention values will also be aggregated. Therefore, when a particular network is under DDoS attack, the intrusion detection system will inform the BGP router to boost up its iTrace receiving intention. This new intention value will be distributed through the whole internet using BGP (or piggyback on BGP updates). The details of the proposed BGP extension will be given in the later version of this draft. 5. Evaluation: The proposed scheme will enhance the probability of receiving iTrace messages closer to the DDoS slaves. The new extension is fairly simple to implement (as shown in the pseudo code) and the per-data packet processing overhead is reasonably small - one comparison operation and one memory addition operation. The per-iTrace trigger process part is more expensive then the original iTrace proposal. While the overhead here mainly involves a random number generation (hardware can certainly speed up), this process will happen very rarely (e.g., 1 in 20,000 packets). Our proposal to distribute the intention values requires a small extension to BGP. And, because of BGP route aggregation, our proposal will not increase the number of entries in the routing table. However, we do need to introduce three new attributes: the iTr bit, intention value, and packet count. 6. Security Consideration: Since our scheme will introduce exactly the same amount of iTrace messages as the original iTrace proposal, our proposal will not introduce any new vulnerability related to denial of service attacks based on the iTrace messages themselves. Since we propose using BGP to distribute the intention values, our scheme is subject to the same security risks as BGP. The risks with respect to intention values would be that an attacker who can tamper with the BGP contents could modify the behavior of itrace to divert itrace away from the attacker's location. This attack seems as if it would be very difficult to accomplish, but the issue should be considered in more detail in a subsequent version of this draft. 7. Intellectual Property The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the tech- nology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to iden- tify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards- related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Sec- retariat. The IETF invites any interested party to bring to its atten- tion any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the infor- mation to the IETF Executive Director. 8. References [iTrace] S. Bellovin, "ICMP Trace-Back", Internet-Draft 2000. 9. Acknowledgements Our research is sponsored by DARPA under the fault tolerant networking program. 10. Author Information S. Felix Wu Computer Science Department University of California at Davis One Shields Avenue Davis, CA 95616 phone: +1 530 754 7070 email: wu@cs.ucdavis.edu Lixia Zhang Computer Science Department UCLA Los Angeles, CA phone +310 825 2695 email: lixia@cs.ucla.edu Dan Massey USC/ISI 4350 N. Fairfax Drive, Suite 620 Arlington VA 22203 phone +703 812 3731 email: masseyd@isi.edu Allison Mankin USC/ISI 4350 N. Fairfax Drive, Suite 620 Arlington VA 22203 phone +703 812 3706 email: mankin@isi.edu 11. Full Copyright Statement Copyright (C) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and fur- nished to others, and derivative works that comment on or oth- erwise explain it or assist in its implementation may be pre- pared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copy- right notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copy- right notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."