Draft Dan Massey, Allison Mankin Internet Engineering Task Force USC/ISI File: draft-ietf-itrace-intention-00.txt C.L. Wu X.L. Zhao Expires May 2002 NCSU S. Felix Wu, W. Huang UC Davis Lixia Zhang UCLA November 2001 Intention-Driven ICMP Trace-Back <draft-ietf-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 January 31, 2002. 1. Abstract This draft describe an enhancement over the current iTrace proposal such that we can trace more closely to the DDoS slaves faster. Wu, Zhang, Massey and Mankin [Page 1]
Internet Draft Intention-Driven iTrace July 2001 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 packets) 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, it might take a long time for a nearby router to generate a valuable iTrace packet. Statistically, routers closer to the victim will generate "useful" iTrace messages toward the true victim faster than the routers closer to the true slaves. For example, we have one DDoS victim, X and R is one of the router forwarding DDoS traffic toward X. When the router R generates an iTrace message, the iTrace probability 1/20,000 is for all the packets being sent through e[x]. If the packet rate for e[x] is 10,000 packets per second, then, statistically one useful iTrace packet will be generated in about 2 seconds. However, if the packet rate is 100 packets per second, then the time will be 200 seconds. If a slave (attacking X) is in the campus of UCDavis, then routers closer to X will statistically generate an iTrace message toward X right after the attack. On the other hand, it will take maybe a few minutes before the victim will see the first iTrace message from the border router of UCDavis. A related problem to the above scenario is that many "useless" iTrace messages might be generated. While it might not be a big problem for a non-victim to receive iTrace messages, resources (CPU cycles, for example) are wasted and the tracing activities toward the true victim are delayed. We propose a mechanism, "intention-driven" iTrace, to enhance the iTrace performance. Our objectives are: (a) With a specified probability, the resources for generating iTrace messages will be spent, more likely, on packets toward DDoS victims. In other words, a selected set of destinations will have more than 1/20,000 probability to get iTrace messages. (b) The total number of iTrace messages generated by each router remains the same. I.e., statistically still 1 over 20,000. (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) This new mechanism must be scaleable and simple to implement. 2. Intention-Driven iTrace: 2.1. Prob(iiT-Control): Probabilistic Control of Invoking "Intention" iTrace For each router, a probability Prob(iiT-Control) (probability for intention iTrace) is given. Every time, when a packet is selected, through the standard iTrace scheme (1/20,000 probability), we will flip another random coin, controlled by Prob(iiT-Control), to determine whether this iTrace message should be sent "as it is" or we should invoke the "intention" iTrace mechanism. For example, if Prob(iiT-Control) is 0.5, then 50% of the iTrace messages will be used to handle the "original" iTrace scheme, while the rest will be used for only those who really want to receive iTrace messages. While we dedicate 50% of the iTrace resources for the true victims, we essentially reduce the 1/20,000 iTrace probability to 1/40,000 statistically for all the traffic. 2.2. iTrace Intention Bit (iiB) and iTrace Execution Bit (ieB) A router conceptually has two tables: routing information table and packet forwarding table. We propose to associate each routing entry with one extra bit called "iTrace intention bit (iiB)", and for each forwarding entry, we introduce a new bit called "iTrace execution bit (ieB)". In a routing table, more than one entries might have "iiB" on, while, in a forwarding table, normally at most one entry can have "ieB" on. However, if the ieB of a particular forwarding table entry is on but no data packets use this entry before the next iTrace trigger, then it is possible to have multiple one's in the forwarding table as well. The "iTrace intention bit (iiB)" will be distributed via routing information protocols such as BGP. If the iiB for a particular route entry is 1, then the network destination under this route entry indicates its desire in receiving iTrace messages. For instance, some of them might be currently under serious DDoS attacks and they have running applications that will utilize the information being carried by iTrace messages. On the other hand, if the iTrace intention bit is 0, then it indicates that either the destination's intrusion detection system does not believe that its network is under DDoS attacks or it believes that iTrace messages would not help to handle the attacks it observed. For instance, if an intrusion detection system detects that its network is under reflective DDoS attacks, then the normal (so called) "forward" iTrace messages will not help because iTrace messages will only lead to a hugh number of reflectors, but not to the real DDoS slaves. The "iTrace execution bit (ieB)" indicates that the very next data packet going through that forwarding entry must be iTraced. And, usually, right after this happens, this ieB bit will be cleared. Please note that the iTrace execution bit might be only conceptually associated with the forwarding table. In implementation, this extra bit might be completely outside of the packet forwarding process. 3. Packet Forwarding for Intention iTrace In the original iTrace proposal, an iTrace message will be generated with a small probability. When an iTrace message is about to generate but the Prob(iiT-Control) control determines to invoke intention iTrace, instead of sending a normal iTrace message, an "iTrace trigger" will be generated. The frequency of iTrace trigger can happen at most 1/20,000 (i.e., if Prob(iiT-Control) is 1.0). Under the intention 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 trigger processing. 3.1. Per-Data Packet Processing: When an IP packet arrives, the router will first decide which forwarding entry should be used to forward this packet. If the iTrace execution bit for this route entry is 1, then an iTrace message is generated toward this particular packet. After the iTrace message is sent, the ieB bit for this entry will be set to 0 again. The following is the pseudo code (in C) for this part of processing: int perDataPacketProcess (IP *p) { ForwardEntry *fe = findForwardEntry(p->destinationIPaddr); if (fe == NULL) return -1; if (fe->ieB == 1) { sendiTrace(p); fe->ieB = 0; } regularPacketForwarding(p, fe); return 0; } 3.2. Per-iTrace-Trigger Processing: When an iTrace trigger (i.e., a packet has been chosen for the regular iTrace, but the Prob(iiT_Control) control determines to invoke intention iTrace) occurs, instead of directly sending an iTrace message, the router will randomly choose one entry among all the "route" entries (not "forwarding" entries) with the "iTrace intention bit (iiB)" on. This random selection process can be as simple as a random number generation, or a round-robin fashion of selection (maybe based on traffic distribution) to enhance fairness. The result of the selection process is a particular route entry with iiB on. Then, the corresponding forwarding entry will have its ieB set on. The following pseudo code is an "example" of how the selection "might" work: int periTraceTriggerProcess (RouteEntry *RETable) { int i, iiB_count; int iTr_rand; iiB_count = 0; for(i=0; i<N; i++) if (RETable[i].iiB == 1) iiB_count++; if (iib_count == 0) { invokeRegulariTrace(); return 0; } iTr_rand = rand() % iiB_count; for(i=0; i<N; i++) { RouteEntry *re = &(RETable[i]); if (re->iiB == 1) { if (iTr_rand == 0) { re->fe->ieB = 1; return 1; } iTr_rand--; } } return -1; } 3.3. The iTrace probability attribute Instead of one constant probability, Prob(iiT-Normal), (e.g., 1/20000) in the normal iTrace, two different probability values are defined for intention driven iTrace: Prob(iiT-Intention) and Prob(iiT-Other). To "approximately" obtain these values, we propose the following method: (1). Assume that the traffic ratio for iiT-intention and iiT-other is Ratio(intention) and Ratio(other), respectively. Ratio(intention) + Ratio(other) = 1.0. (2). Prob(iiT-Other) = Prob(iiT-Normal) * (1 - Prob(iiT-Control)) (3). Prob(iiT-Intention) = (Prob(iiT-Noraml) - Ratio(other) * Prob(iiT-Other)) /Ratio(intention) 4. How to Distribute the iTrace Intention Value? In this section, we present a way to distribute the Intention value for each router and for each route entry. We propose to have two new BGP community string values for the iTrace intention. BGP community string, an existing BGP attribute, is a 32 bit unsigned integer. We would like to use one value to signal the positive intention to receive iTrace messages. In other words, including this intention commuity string means 1 for iiB. Only the originating AS may set the intention community string. The originating AS MUST apply a local dampening rule to limit the frequency of changes in the intention community string. When a BGP router advertises the reachability of some network address, it will also attach the iTrace intention bit 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 iiB. Furthermore, when BGP updates are aggregated, the iiB 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 iTrace intention bit will be distributed through the whole internet using BGP (or piggyback on BGP updates). The exact value of the new community attribute values 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. The memory cost for ieB might be a concern as we conceptually need one bit for each forwarding entry. However, we potentially can implement the same scheme without the requirement of adding one bit to the forwarding table. For example, we can choose a packet to iTrace among a pool of logged packets. 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 at most). Our proposal to distribute the intention values requires a small change to BGP. Furthermore, because of the nature of community string, it is not necessary to have all the routers supporting the new feature. I.e., even if we have sparsely a few new BGP routers supporting intention iTrace, these routers can still utilize the intention bits, while others traditional routers will still pass the intention bits around, Because of BGP route aggregation, our proposal will not increase the number of entries in the routing or forwarding tables. 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. With the P_IIT control, destinations without the intention iTrace support can still receive iTrace messages but with a smaller probability such as 1 over 40,000. A malicious destination can distribute positive intention bits to attract more intention iTrace messages, but it still need to compete probabilistically against other DDoS victim over about 50% of the iTrace messages. 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, M. Leech, "ICMP Trace-Back", Internet-Draft, July 2001. 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."
