Transcript Packet Tracing and Distributed Denial of Service Attacks

Intention-Driven iTrace
S. Felix “Last Minutes” Wu
UC Davis
http://www.cs.ucdavis.edu/~wu
[email protected]
Lixia Zhang
UCLA
Allison Mankin, Dan Massey
USC/ISI
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
1
A Statistic Problem with iTrace
• Routers closer to the victims have higher
probability to generate iTrace packets
toward the true victims.
• Routers closer to the DDoS slaves might
have relatively small probability (smaller
than the routers around the victims) to
generate “useful” iTrace packets.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
2
Two measures
• P(U-iTrace)
– When an iTrace message is generated, what is
the probability that this iTrace message is
“useful” (i.e., it carries an attack packet)?
• P(U-iT-sec)
– What is probability for a router to generate at
least ONE “useful” iTrace message in a
second?
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
3
Example: Multi-S Single-V
1K attack-pkt/sec
19K normal-pkt/sec
P(U-iTrace) = 5%
#iTrace/sec = 1
P(U-iT-sec) = 5%
Slave
200K attack-pkt/sec
200K normal-pkt/sec
P(U-iTrace) = 50%
#iTrace/sec = 20
P(U-iT-sec) = 99.999%
R1
R2
4K attack-pkt/sec
196K normal-pkt/sec
P(U-iTrace) = 2%
#iTrace/sec = 10
P(U-iT-sec) = 18%
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
Victim
980K attack-pkt/sec
20K normal-pkt/sec
P(U-iTrace) = 98%
#iTrace/sec = 50
P(U-iT-sec) = 100%
4
Motivation
• About (K* 0.005%) of our network
resources will be spent on iTrace packets.
• Then, we hope we can spend the resources
on more “useful” iTrace packets.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
5
Three Types of Nodes
• DDoS victim with the intention to trace the
slaves.
• DDoS victim without the intention.
• non-DDoS victims (assuming they do not
have the intention as well -- and very likely
they hope they won’t receive ones).
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
6
Intention-driven iTrace
• Different destination hosts, networks,
domains/ASs have different “intention
levels” in receiving iTrace packets.
– We propose to add one “iTrace-intention” bit.
• Some of them might not care about iTrace,
and some of them might not be under DDoS
attacks, for example.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
7
a little mathematics...
Intention for
receiving iTrace.
S2V: 2%
S2B:48%
S2C:25%
S2D:25%
I:
I:
I:
I:
1
0
0
1
V’s probability to receive iTrace packets: 7.41%
0.02 / (0.02 + 0 + 0 + 0.25) = 0.0741
PiTrace(V) = (Ptraffic(V) * I(V)) /
03/19/2001
 (Ptraffic(n) * I(n))
dst
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
8
Example: Multi-S Two-V
Slave
R1
R2
Victim
4K att-v1-pkt/sec
50K att-v2-pkt/sec
146K normal-pkt/sec
P(U-iTrace) = 2%
#iTrace/sec = 10
P(U-iT-sec) = 18%
P(U-iTrace) =
#iTrace/sec =
P(U-iT-sec) =
I(Victim-1) = 1
P(U-iTrace) = 7.4%
P(U-iT-sec) = 53.7%
I(Victim-2) =
1
P(U-iTrace) = 92.6%
P(U-iT-sec) = 100.0%
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
25%
10
95%
9
Issues
• How to determine the intention bit?
– Policy to set the bit.
• How to distribute the intention bits to
routers globally?
– Utilize/extend BGP!
• How to use the intention bits at each router?
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
10
How to distribute I(n)?
• YABE: (Yet Another BGP Extension)
– For every BGP route update, we include I(n) as
a new community attribute:
• 0x[iTrace-Intention]:0x[0-1]
– These I(n) values will be forwarded or even
aggregated by the routers who understand this
new community attribute.
• aggregation: I(new) = max {I(n)}
– Rate-Limiting on Intention Update:
• should not be more frequent than Keep-Alive
messages.
• should not trigger any major route computation.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
11
The iTrace Statistics Model
Packet
buffering
Routing
table
lookup
Forward
process
Should this packet be iTraced?
iTrace
Stochastic
Process
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
Yes, we should
generate an iTrace
for this packet?
12
iTrace Trigger
Packet
buffering
Routing
table
lookup
Forward
process
iTrace If yes, pick the Nth packet
Trigger in the buffer….
iTrace
Stochastic
Process
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
Should we generate
an iTrace message
now?
13
A simple design
BGP table I(n) iTrace
bit
iTrace
Process
per ~20K pkts
Add two bits to the routing table:
(1). I(n): Intention Bit Value associated with this entry
(2). iTrace bit: whether we need to generate an
iTrace message for this entry now.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
14
Handling an iTrace Trigger
BGP table
I(n) iTrace
bit
iTrace
Process
• If all I(n)’s are zero, shut-off the iTrace trigger
process.
• Set the iTrace bit on all the entries with I(n) = 1.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
15
(1).
Before
iTrace
trigger:
152.1.23.0/24
169.20.3.0/24
192.1.0.0/16
207.3.4.183/20
152.1.0.0/16
155.0.0.0/16
1
0
0
1
1
0
0
0
0
0
0
0
(2).
After
iTrace
trigger:
152.1.23.0/24
169.20.3.0/24
192.1.0.0/16
207.3.4.183/20
152.1.0.0/16
155.0.0.0/16
1
0
0
1
1
0
1
0
0
1
1
0
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
16
(3).
After
iTrace
sent:
03/19/2001
152.1.23.0/24
169.20.3.0/24
192.1.0.0/16
207.3.4.183/20
152.1.0.0/16
155.0.0.0/16
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
1
0
0
1
1
0
0
0
0
0
0
0
17
Processing Overhead
1/20K iTrace message trigger occurs:
1. Set all the iTrace bits on if I(n) = 1.
Processing for each data packet:
1. if the iTrace flag bit is 1,
(1). send an iTrace message for this data packet.
(2). reset all the iTrace bits to 0.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
18
The Aggregation Problem
Slave
R1
4K att-v1-pkt/sec
50K att-v2-pkt/sec
146K normal-pkt/sec
R2
4K
16K
50K
130K
att-v1-pkt/sec
agg-v1-pkt/sec
att-v2-pkt/sec
normal-pkt/sec
P(U-iTrace) = 2%
#iTrace/sec = 10
P(U-iT-sec) = 18%
P(U-iTrace) = 2%
#iTrace/sec = 10
P(U-iT-sec) = 18%
I(Victim-1) = 1
P(U-iTrace) = 7.4%
for 4K traffic.
P(U-iT-sec) = 53.7%
I(Victim-1) = 1
P(U-iTrace) = 5.7%
for 20K traffic.
P(U-iT-sec) = 44.4%
03/19/2001
Victim
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
19
Summary for Intention iTrace
• Improve the probability of “useful” iTrace.
• Require some “minor” changes to the router
forwarding process.
• Require another BGP extension.
– We need to verify that this extension will be
interoperable well with existing BGP nodes.
• The amount of generated iTrace messages
should be no more than the current iTrace
proposal.
03/19/2001
ICMP Traceback Working Group,
IETF'50, Minneapolis, MN
20