Transcript Single-Packet IP Traceback

Introduction to IP Traceback
交通大學 電信系
李程輝 教授
2004/3/26
Outline





2004/3/26
Introduction
Ingress Filtering
Packet Marking
Packet Digesting
Summary
2
Introduction
2004/3/26
3
Introduction

Internet becomes ubiquitous


The impact of network attackers is getting more
and more significant
Two kind of attackers

A few well-targeted packets


Denial-of-service (DoS) & distributed DoS (DDoS)

2004/3/26
Ex: Teardrop attack
Typically conducted by flooding network links with large
amounts of traffics
4
DDoS
(a) Direct DDoS
2004/3/26
(b) reflector attacker
5
The Difficulty to Catch the Attacker

The anonymous feature of the IP protocol



Somewhere spoofed source address are legal


2004/3/26
Can’t identify the true source of an IP datagram if
the source wishes to conceal it
Solution：ingress filtering
Network address translators (NATs)
Mobile IP
6
IP Traceback Problem

IP traceback problem


The problem of identifying the source of the
offending packets
Source means





2004/3/26
Zombie
Reflector
Spoofed address
Ingress point to the traceback-enabled network
One or more compromised routers within the enabled
network
7
IP Traceback Problem - Solution

Packet marking




Packet digesting



2004/3/26
To cope with DDoS attacks
Router marks packets with it’s identifications
Victim can reconstruct the attack path if sufficient
number of packets are collected
For attacks that require only a few packets
Require storage of audit trails on the routers
Victim ask routers if the offending packet passed
before
8
Evaluation Metrics for IP Traceback
Technique (1)







2004/3/26
ISP Involvement
Number of Attacking Packets Needed for
Traceback
The Effect of Partial Deployment
Processing Overhead
Bandwidth Overhead
Memory Requirements
Ease of Evasion
9
Evaluation Metrics for IP Traceback
Technique (2)





Protection
Scalability
Number of Functions Needed to Implement
Ability to Handle Major DDoS Attacks
Ability to Trace Transformed Packets




2004/3/26
Network Address Translation (NAT)
Tunneling
ICMP packet
Duplication of a packet in multicast
10
Ingress Filtering
2004/3/26
11
Ingress Filtering


2004/3/26
Limit source addresses of IP datagrams from a network to
addresses belonging to that network
If ingress filtering is not deployed everywhere attackers can
still spoof any address on the Internet
12
Why Don’t People Run Ingress Filtering？

It is easy! It improves security! Why not run it?



Some people run it in current routers
It is implemented in the slow path in the software
not the hardware
It is easy
For the routers close to the edge of the networks where
addressing rules are well defined

It becomes complex and inefficient
For transit networks where packets with a different source
address can enter the network in multiple locations
2004/3/26
13
Packet Marking
2004/3/26
14
Packet Marking



2004/3/26
Probabilistic packet marking (PPM)
ICMP traceback (iTrace)
Deterministic packet marking (DPM)
15
Probabilistic Packet Marking


2004/3/26
Routers mark
packets that pass
through them
Packets for
marking are
selected with
probability p=0.04
16
Router Marking
2004/3/26
17
Pros & Cons

Pros





Cons



2004/3/26
High stability
Still can work under partial deployment
No bandwidth overhead
Low network processing overhead (decide which
packet should be marked)
Only for DoS & DDoS attacks
Victim requires high memory and high processing
overhead
Without authentication mark spoofing may happen
18
Ability to Trace Transformed Packets

Can handle packet modification transformation of the
packets directed to the victim

The ID field used for fragmentation is used for the
mark
If a single fragment of the original datagram is marked
 The reassembly function would fail at the destination
Solution: select a lower probability of marking for
fragmented packet


Tunneling may create a problem for reconstruction

2004/3/26
If marks are extracted before the outer header is
removed
19
ICMP Traceback (iTrace)

ICMP traceback
message (iTrace)





2004/3/26
Next hop
Previous hop
Timestamp
As many bytes of
the traced packet
TTL=255
20
“Intension-Driven” iTrace

Attack[V]


Intension[V]


How many iTrace messages from router R to victim V have
been received
Generated[R]


=1, victim V wants to receive ICMP traceback message
Received[R→V]


=1, victim V is attacked
The number of iTrace messages generated by router R for all
destinations
The value of ICMP packet can be a function of
Attack[V]  Intention[ V]  HopCount[R  V]
(Received[ R  V]  1)(Generat ed[R]  1)
2004/3/26
21
Architecture



Introduce a new bit – intension bit
The intension bit in routing table will set to 1 if one has
intension to receive ICMP packet
Decision Module


2004/3/26
“Choose” one from routing table
prefer the one with the highest value
22
Pros & Cons


The pros and cons of iTrace is similar to that
of PPM
Except


2004/3/26
iTrace has bandwidth overhead；PPM has no
bandwidth overhead
Without authentication fake ICMP packet may be
generated more easily
23
Deterministic Packet Marking
2004/3/26

Each packet is
marked when it
enters the network

Only mark
Incoming packets

Mark：address
information of this
interface

16 bit ID + 1 bit
Reserved Flag
24
The Information of Marks
Pad
Ideal hash
2004/3/26
25
Reconstruction Process


area

2004/3/26
2d
area
Each area
has k
segments
Each
segment has
2 a bits
26
PPM vs. DPM

Mark spoofing



The received information


2004/3/26
(PPM) Use coding technique (but not 100%)
(DPM) Spoofed mark will be overwritten
(PPM) Full path
(DPM) Address of the ingress router
27
Packet Digesting
Source Path Isolation Engine
(SPIE)
2004/3/26
28
Packet Digesting

Compute digest over



2004/3/26
The invariant portion of the IP header (16 bytes)
The first 8 bytes of the payload (8 bytes)
24 bytes  sufficient to differentiate all packets
29
Prefix Length & Collision Probability


2004/3/26
A WAN trace from an OC-3 gateway router
A LAN trace from an active 100Mb Ethernet segment
30
Bloom Filter (1)

A technique that simply stores the digests
＊For each packet
arrived
Step-1 Use k different
hash function computes
k independent n-bits
digests
Step-2 Set the
corresponding bits in
the 2 n bits digest table
2004/3/26
31
Bloom Filter (2)

If any one of them is zero


If all the bits are one



It is highly likely the packet was stored
It is possible that some set of other insertions caused all
the bits to be set
Restriction



2004/3/26
The packet was not stored in the table
Can only store a limited number of digests
Saturated filters can be swapped out for a new, empty
filter
Change to a new filter loss the previous digest
information
32
Architecture (1)



2004/3/26
Data Generation Agent (DGA)
SPIE Collection and Reduction Agents (SCARs)
SPIE Traceback Manager (STM)
33
Architecture (2)

DGA





SCARs


2004/3/26
SPIE enhanced router
1. produce packet digest
2. store digests
table annotated – time & hash function
Concentration points for several routers
1. produce local attack graph
34
Architecture (3)

STM







2004/3/26
Control the whole SPIE system
The interface to requesting packet trace
1. verifies the authenticity
2. dispatch the request to the appropriate SCARs
3. gather the resulting attack graphs
4. complete the attack graph
5. replies to the IDS
35
Traceback Processing
T’ – the packet enter
the region
P’ – the entering
packet
V’ – the border router
between the two
network
IDS
determine an exceptional event has occurred
packet, P ； victim, V ； time
of attack, T
STM
cryptographically verifies its authenticity
P； V；T
SCAR
another
SCAR
2004/3/26
no
poll its DGAs & produce partial attack graph
yes
terminate
36
Graph Construction

Reverse path
flooding





2004/3/26
R8；R9
R7
R4；S5；R5
R3；R2
The SCAR don’t
need to query
DGAs sequentially
37
Ability to Trace Transformed Packets (1)

Transform lookup table (TLT)

Record sufficient packet data at the time of
transformation to allow the original packet to be
reconstructed
1st field：a digest of the transformed packet
2nd field：the type of transformation (include a flag I)
3rd field：a variable amount of packet data
2004/3/26
38
Ability to Trace Transformed Packets (2)

Flag I (indirect flag)
(1)For some transformations, such as NAT, the 32bits
data field is not enough.
Set I=1, the third field is treated as a pointer
(2)In many case (e.g., tunneling or NAT), packets
undergoing a particular transformation are related
It is possible to reduce the storage requirement by
suppressing duplicate packet data
Flag I is used for flow caching, or at least
identification, so that the packets within the flow
can be correlated and stored appropriately.
2004/3/26
39
Summary
2004/3/26
40
Summary




In recent years much interest and consideration have
been paid to the topic of securing the Internet
infrastructure
To detect the offending packets IDS (Intrusion
Detection System) becomes more and more important
Detecting the offending packets (IDS) find out
attackers (IP traceback)
Several methods have been proposed



2004/3/26
Each has its own advantages and disadvantages
None of the methods described has been used on the
Internet
When economic or political incentives become strong
enough to justify deployment of IP traceback, some new
requirements and metrics for evaluation might emerge
41
References








2004/3/26
R. K. C. Chang, “Defending against Flooding-Based Distributed
Denial-of-Service Attacks: A Tutorial,” IEEE Commun. Mag., Oct. 2002,
pp. 42–51.
A. Belenky and N. Ansari, “On IP traceback,” IEEE Communications
Magazine, vol. 41, no. 7, July 2003
S. Savage et al., “Network Support for IP Traceback,” IEEE/ACM
Trans. Net., vol. 9, no. 3, June 2001, pp. 226–37.
D. X. Song and A. Perrig, “Advanced and Authenticated Marking
Schemes for IP Traceback,” Proc. INFOCOM,2001, vol. 2, pp. 878–86.
S. F. Wu et al., “On Design and Evaluation of ‘Intention-Driven’ ICMP
Traceback,” Proc. 10th Int’l. Conf. Comp. Commun. and Nets., 2001,
pp. 159–65.
A. Belenky and N. Ansari “IP Traceback With Deterministic Packet
Marking,” IEEE Communications Letters, Vol.7, NO. 4,April 2003
A. Belenky and N. Ansari “Tracing Multiple Attackers With
Deterministic Packet Marking,” IEEE PACRIM’03, August 2003
A. C. Snoeren et al., “Single-Packet IP Traceback,” IEEE/ACM Trans.
Net., vol. 10, no. 6, Dec. 2002, pp. 721–34.
42