< draft-wu-itrace-intention-01.txt   draft-wu-itrace-intention-02.txt >
S. Felix Wu
INTERNET-DRAFT 20 November 2001
S. Felix Wu, W. Huang
UCDavis UCDavis
Dan Massey, Allison Mankin
USC/ISI
C.L. Wu, X.L. Zhao
NCSU
Lixia Zhang Lixia Zhang
UCLA UCLA
Dan Massey
USC/ISI
Allison Mankin
USC/ISI
Intention-Driven ICMP Trace-Back Intention-Driven ICMP Trace-Back
draft-wu-itrace-intention-01.txt draft-wu-itrace-intention-02.txt
Status of this memo Status of this memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts. other groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet- Drafts as reference any time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf*
http://www.ietf.org/ietf/lid-abstracts.txt */lid-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html http://www.ietf.org/shadow.html
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
Abstract Abstract
This draft describe an enhancement over the current iTrace This draft describe an enhancement over the current iTrace
proposal such that we can trace more closely to the DDoS proposal such that we can trace more closely to the DDoS
skipping to change at page 2, line 8 skipping to change at page 2, line 8
The probability of iTrace message generation on a particular router The probability of iTrace message generation on a particular router
in the current internet draft is static and small (about 1 over 20,000 in the current internet draft is static and small (about 1 over 20,000
packets) such that the overhead introduced by the iTrace messages packets) such that the overhead introduced by the iTrace messages
is small. However, if each DDoS slave produces a relatively small 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 amount of attack traffic, then, it might take a long time for a nearby
router to generate a valuable iTrace packet. Statistically, routers router to generate a valuable iTrace packet. Statistically, routers
closer to the victim will generate "useful" iTrace messages toward closer to the victim will generate "useful" iTrace messages toward
the true victim faster than the routers closer to the true slaves. 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 routers 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 forwarding DDoS traffic toward X. When the router R generates an
iTrace message, the iTrace probability 1/20,000 is for all the packets 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 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 per second, then, statistically one useful iTrace packet will be
generated in about 2 seconds. However, if the packet rate is 100 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 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 (attacking X) is in the campus of UCDavis, then routers closer to
X will statistically generate an iTrace message toward X right after X will statistically generate an iTrace message toward X right after
the attack. On the other hand, it will take maybe a few minutes 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 before the victim will see the first iTrace message from the border
skipping to change at page 2, line 46 skipping to change at page 2, line 46
remains the same. I.e., statistically still 1 over 20,000. remains the same. I.e., statistically still 1 over 20,000.
o The new mechanism is compatible with the current iTrace scheme o The new mechanism is compatible with the current iTrace scheme
such that we do not require every router to support the new such that we do not require every router to support the new
mechanism. mechanism.
o This new mechanism must be scaleable and simple to implement. o This new mechanism must be scaleable and simple to implement.
2 Intention-Driven iTrace: 2 Intention-Driven iTrace:
2.1 P_IIT: Probabilistic Control of Invoking "Intention" iTrace 2.1 Prob(iiT-Control): Probabilistic Control of Invoking "Intention"
iTrace
For each router, a probability P_IIT (probability for intention iTrace) For each router, a probability Prob(iiT-Control) (probability for
is given. Every time, when a packet is selected, through the standard intention iTrace) is given. Every time, when a packet is selected,
iTrace scheme (1/20,000 probability), we will flip another random through the standard iTrace scheme (1/20,000 probability), we will
coin, controlled by P_IIT, to determine whether this iTrace message flip another random coin, controlled by Prob(iiT-Control), to determine
should be sent "as it is" or we should invoke the "intention" iTrace whether this iTrace message should be sent "as it is" or we should
mechanism. invoke the "intention" iTrace mechanism.
For example, if P_IIT is 0.5, then 50used to handle the "original" For example, if Prob(iiT-Control) is 0.5, then 50% of the iTrace
iTrace scheme, while the rest will be used for only those who really messages will be used to handle the "original" iTrace scheme, while
want to receive iTrace messages. While we dedicate 50essentially the rest will be used for only those who really want to receive iTrace
reduce the 1/20,000 iTrace probability to 1/40,000 statistically for messages. While we dedicate 50essentially reduce the 1/20,000 iTrace
all the traffic. probability to 1/40,000 statistically for all the traffic.
2.2 iTrace Intention Bit (iiB) and iTrace Execution Bit (ieB) 2.2 iTrace Intention Bit (iiB) and iTrace Execution Bit (ieB)
A router conceptually has two tables: routing information table and A router conceptually has two tables: routing information table and
packet forwarding table. We propose to associate each routing entry packet forwarding table. We propose to associate each routing entry
with one extra bit called "iTrace intention bit (iiB)", and for each with one extra bit called "iTrace intention bit (iiB)", and for each
forwarding entry, we introduce a new bit called "iTrace execution forwarding entry, we introduce a new bit called "iTrace execution
bit (ieB)". In a routing table, more than one entry might have "iiB" bit (ieB)". In a routing table, more than one entries might have
on, while, in a forwarding table, at most one entry can have "ieB" "iiB" on, while, in a forwarding table, normally at most one entry
on. 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 The "iTrace intention bit (iiB)" will be distributed via routing
information protocols such as BGP. If the iiB for a particular route information protocols such as BGP. If the iiB for a particular route
entry is 1, then the network destination under this route entry indicates entry is 1, then the network destination under this route entry indicates
its desire to receive iTrace messages. For instance, some of them its desire in receiving iTrace messages. For instance, some of them
might be currently under serious DDoS attacks and they have running might be currently under serious DDoS attacks and they have running
applications that will utilize the information being carried by iTrace applications that will utilize the information being carried by iTrace
messages. On the other hand, if the iTrace intention bit is 0, then messages. On the other hand, if the iTrace intention bit is 0, then
it indicates that either the destination's intrusion detection system it indicates that either the destination's intrusion detection system
does not believe that its network is under DDoS attack or it believes 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. that iTrace messages would not help to handle the attacks it observed.
For instance, if an intrusion detection system detects that its network For instance, if an intrusion detection system detects that its network
is under reflective DDoS attacks, then the normal (so called) "forward" is under reflective DDoS attacks, then the normal (so called) "forward"
iTrace messages will not help because iTrace messages will only lead iTrace messages will not help because iTrace messages will only lead
to a hugh number of reflectors, but not to the real DDoS slaves. to a hugh number of reflectors, but not to the real DDoS slaves.
The "iTrace execution bit (ieB)" indicates that the very next data The "iTrace execution bit (ieB)" indicates that the very next data
packet going through that forwarding entry must be iTraced. And, packet going through that forwarding entry must be iTraced. And,
usually, right after this happens, this ieB bit will be cleared. usually, right after this happens, this ieB bit will be cleared.
Please note that the iTrace execution bit might be only conceptually Please note that the iTrace execution bit might be only conceptually
associated with the forwarding table. In implementation, this extra associated with the forwarding table. In implementation, this extra
bit might be completely outside of the packet forwarding process. bit might be completely outside of the packet forwarding process.
3 Packet Forwarding for Intention iTrace 3 Packet Forwarding for Intention iTrace
In the original iTrace proposal, an iTrace message will be generated In the original iTrace proposal, an iTrace message will be generated
with a small probability. If an iTrace message is about to be generated with a small probability. When an iTrace message is about to generate
and the P_IIT control determines to invoke intention iTrace, instead but the Prob(iiT-Control) control determines to invoke intention iTrace,
of sending a normal iTrace message, an "iTrace trigger" will be generated. instead of sending a normal iTrace message, an "iTrace trigger" will
The frequency of iTrace trigger can happen at most 1/20,000 (i.e., be generated. The frequency of iTrace trigger can happen at most
if P_IIT is 1.0). 1/20,000 (i.e., if Prob(iiT-Control) is 1.0).
Under the intention iTrace, we separate the implementation into two Under the intention iTrace, we separate the implementation into two
parts: the processing for each incoming data packet and the processing parts: the processing for each incoming data packet and the processing
for each iTrace trigger. Please note that it is desirable to have for each iTrace trigger. Please note that it is desirable to have
a very efficient per-data packet process, while it is more tolerable a very efficient per-data packet process, while it is more tolerable
to spend more processing time for per-iTrace trigger processing. to spend more processing time for per-iTrace trigger processing.
3.1 Per-Data Packet Processing: 3.1 Per-Data Packet Processing:
When an IP packet arrives, the router will first decide which forwarding When an IP packet arrives, the router will first decide which forwarding
skipping to change at page 4, line 36 skipping to change at page 4, line 42
sendiTrace(p); sendiTrace(p);
fe->ieB = 0; fe->ieB = 0;
} }
regularPacketForwarding(p, fe); regularPacketForwarding(p, fe);
return 0; return 0;
} }
3.2 Per-iTrace-Trigger Processing: 3.2 Per-iTrace-Trigger Processing:
When an iTrace trigger (i.e., a packet has been chosen for the regular When an iTrace trigger (i.e., a packet has been chosen for the regular
iTrace, but the P_IIT control determines to invoke intention iTrace) iTrace, but the Prob(iiT_Control) control determines to invoke intention
occurs, instead of directly sending an iTrace message, the router iTrace) occurs, instead of directly sending an iTrace message, the
will randomly choose one entry among all the "route" entries (not router will randomly choose one entry among all the "route" entries
"forwarding" entries) with the "iTrace intention bit (iiB)" on. This (not "forwarding" entries) with the "iTrace intention bit (iiB)" on.
random selection process can be as simple as a random number generation, This random selection process can be as simple as a random number
or a round-robin fashion of selection (maybe based on traffic distribution) generation, or a round-robin fashion of selection (maybe based on
to enhance fairness. traffic distribution) to enhance fairness.
The result of the selection process is a particular route entry with The result of the selection process is a particular route entry with
iiB on. Then, the corresponding forwarding entry will have its ieB iiB on. Then, the corresponding forwarding entry will have its ieB
set on. The following pseudo code is an "example" of how the selection set on. The following pseudo code is an "example" of how the selection
"might" work: "might" work:
int int
periTraceTriggerProcess periTraceTriggerProcess
(RouteEntry *RETable) (RouteEntry *RETable)
{ {
int i, iiB_count; int i, iiB_count;
int iTr_rand; int iTr_rand;
iiB_count = 0; iiB_count = 0;
for(i=0; i<N; i++) for(i=0; i<N; i++)
if (RETable[i].iiB == 1) iiB_count++; if (RETable[i].iiB == 1) iiB_count++;
if (iib_count == 0) if (iib_count == 0)
{ {
invokeRegulariTrace(); invokeRegulariTrace();
return 0; return 0;
} }
iTr_rand = rand() % iiB_count; iTr_rand = rand() % iiB_count;
for(i=0; i<N; i++) for(i=0; i<N; i++)
{ {
RouteEntry *re = &(RETable[i]); RouteEntry *re = &(RETable[i]);
if (re->iiB == 1) if (re->iiB == 1)
{ {
if (iTr_rand == 0) if (iTr_rand == 0)
{ {
re->fe->ieB = 1; re->fe->ieB = 1;
return 1; return 1;
} }
iTr_rand--; iTr_rand--;
} }
} }
return -1; 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? 4 How to Distribute the iTrace Intention Value?
In this section, we present a way to distribute the 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 for each router and for each route entry. We propose to have two
new BGP community string values for the iTrace intention. new BGP community string values for the iTrace intention.
The BGP community string, an existing BGP attribute, is a 32 bit BGP community string, an existing BGP attribute, is a 32 bit unsigned
unsigned integer. We would like to use two of the available values, integer. We would like to use one value to signal the positive intention
one for the positive intention to receive iTrace messages, and the to receive iTrace messages. In other words, including this intention
other for negative. For instance, 0x78B0 for not wanting any iTrace, commuity string means 1 for iiB. Only the originating AS may set
while 0x78B1 for the positive intention of iTrace. In other words, the intention community string. The originating AS MUST apply a
0x78B1 means 1 for iiB. local dampening rule to limit the frequency of changes in the intention
community string.
Note the above are only example values. The exact value of the new
community attribute strings will be given in the later version of
this draft.
When a BGP router advertises the reachability of some network address, When a BGP router advertises the reachability of some network address,
it will also attach the iTrace intention community value for that it will also attach the iTrace intention bit for that network. Therefore,
network. Therefore, when this BGP update is received by some downstream when this BGP update is received by some downstream BGP routers,
BGP routers, the intention value of the corresponding route entry the intention value of the corresponding route entry will be updated
will be updated the attached iiB. Furthermore, when BGP updates are the attached iiB. Furthermore, when BGP updates are aggregated, the
aggregated, the iiB will also be aggregated. iiB will also be aggregated.
Therefore, when a particular network is under DDoS attack, the intrusion Therefore, when a particular network is under DDoS attack, the intrusion
detection system will inform the BGP router to boost up its iTrace detection system will inform the BGP router to boost up its iTrace
receiving intention. This new iTrace intention bit will be distributed receiving intention. This new iTrace intention bit will be distributed
through the whole internet using BGP (or piggyback on BGP updates). 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: 5 Evaluation:
The proposed scheme will enhance the probability of receiving iTrace The proposed scheme will enhance the probability of receiving iTrace
messages closer to the DDoS slaves. messages closer to the DDoS slaves.
The new extension is fairly simple to implement (as shown in the The new extension is fairly simple to implement (as shown in the
pseudo code) and the per-data packet processing overhead is reasonably pseudo code) and the per-data packet processing overhead is reasonably
small - one comparison operation. The memory cost for ieB might small - one comparison operation. The memory cost for ieB might
be a concern as we conceptually need one bit for each forwarding be a concern as we conceptually need one bit for each forwarding
entry. However, we potentially can implement the same scheme without entry. However, we potentially can implement the same scheme without
skipping to change at page 8, line 14 skipping to change at page 9, line 14
10 Author Information 10 Author Information
S. Felix Wu <wu@cs.ucdavis.edu> S. Felix Wu <wu@cs.ucdavis.edu>
Computer Science Department Computer Science Department
University of California at Davis University of California at Davis
One Shields Avenue One Shields Avenue
Davis, CA 95616 Davis, CA 95616
phone: +1 530 754 7070 phone: +1 530 754 7070
Lixia Zhang <lixia@cs.ucla.edu> Wayne Huang <ywhuang@ucdavis.edu>
Computer Science Department Computer Science Department
UCLA University of California at Davis
Los Angeles, CA One Shields Avenue
phone +310 825 2695 Davis, CA 95616
Dan Massey <masseyd@isi.edu> Dan Massey <masseyd@isi.edu>
USC/ISI USC/ISI
3811 N. Fairfax Drive, Suite 200 3811 N. Fairfax Drive, Suite 200
Arlington VA 22203 Arlington VA 22203
Allison Mankin <mankin@isi.edu> Allison Mankin <mankin@isi.edu>
USC/ISI USC/ISI
3811 N. Fairfax Drive, Suite 200 3811 N. Fairfax Drive, Suite 200
Arlington VA 22203 Arlington VA 22203
Chien-Lung Wu <cwu4@unity.ncsu.edu>
NCSU
Box 7550, NCSU Centennial Campus
Raleigh, NC 27695
Xiaoliang Zhao <xzhao@unity.ncsu.edu>
NCSU
Box 7550, NCSU Centennial Campus
Raleigh, NC 27695
Lixia Zhang <lixia@cs.ucla.edu>
Computer Science Department
UCLA
Los Angeles, CA
Full Copyright Statement Full Copyright Statement
Copyright (C) The Internet Society (2001). All Rights Reserved. Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and fur- nished This document and translations of it may be copied and fur- nished
to others, and derivative works that comment on or oth- erwise explain to others, and derivative works that comment on or oth- erwise explain
it or assist in its implementation may be pre- pared, copied, published it or assist in its implementation may be pre- pared, copied, published
and distributed, in whole or in part, without restriction of any and distributed, in whole or in part, without restriction of any
kind, provided that the above copy- right notice and this paragraph kind, provided that the above copy- right notice and this paragraph
are included on all such copies and derivative works. However, this are included on all such copies and derivative works. However, this
 End of changes. 25 change blocks. 
70 lines changed or deleted 110 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/