FIRE: Flexible Intra-AS Routing Environment
Download
Report
Transcript FIRE: Flexible Intra-AS Routing Environment
Hash-Based IP Traceback
Alex C. Snoeren†, Craig Partridge,
Luis A. Sanchez, Christine E. Jones, Fabrice Tchakountio,
Stephen T. Kent, W. Timothy Strayer
BBN Technologies
†MIT Laboratory for Computer Science
Network Security Risks
• Tools readily available to attackers
network server attacks
performance degradation attacks
• DOS
• DDOS
Single packet attacks (Stop 0A in
TCPIP.sys, Teardrop, Ping-of-death)
• Accidental (unintentional) attacks
Approaches
• Firewalls - prevent attack packets from
reaching the victim
some attack packets look quite innocent
hard to predict all possible attacks
does not get at the source of the problem
continue to consume network resources
• Traceback - identify the source of attack
packets
For a given packet, find the path to source
Why Traceback is hard
• Internet Protocol permits anonymity
Attackers can “spoof” source address
• Fraggle/Smurf, etc
IP forwarding maintains no audit trails
• Some spoofing is legitimate (NATs,
mobile IP, etc)
• Attacks may be short-lived
• Packets change hop by hop
• Routing instability
Why Traceback is hard (continued)
• Network may carry multiple identical
packets (attacks, multicast, broadcast)
• Routers may be compromised
• Attackers may be aware they are being
traced
• Increasing packet size is frowned on
• Will consume network resources
• Ingress filtering of limited value
Traceback Goal
• Reconstruct the attack path of a packet
where the path consists of every router
on the path from the source to the victim
• Reconstruct the attack graph which may
result from multiple copies of an attack
packet injected by different sources
• Need to be able to detect false positives
with a high degree of accuracy
Approaches to Traceback
• Path data can be noted in several places
In the packet itself [Savage et al.],
At the destination [I-Trace], or
In the network infrastructure
• Logging: a naïve in-network approach
Record each packet forwarding event
Can trace a single packet to a source router,
ingress point, or subverted router(s)
Log-Based Traceback
R
R
R
A
R
R
R7
R4
R5
R
R6
R3
R1
R2
V
R
Challenges to Logging
• Attack path reconstruction is difficult
Packet may be transformed as it moves
through the network
• Full packet storage is problematic
Memory requirements are prohibitive at
high line speeds (OC-192 is ~10Mpkt/sec)
• Extensive packet logs are a privacy risk
Traffic repositories may aid eavesdroppers
Solution: Packet Digesting
• Record only invariant packet content
Mask dynamic fields (TTL, checksum, etc.)
Store information required to invert packet
transformations at performing router
• Compute packet digests instead
Use hash function to compute small digest
Store probabilistically in Bloom filters
• Impossible to retrieve stored packets
Invariant Content
Ver
HLen
TOS
Total Length
D M
F F
Identification
TTL
28
bytes
Protocol
Fragment Offset
Checksum
Source Address
Destination Address
Options
First 8 bytes of Payload
Remainder of Payload
Impact of Traffic Diversity
Fraction of Collided Packets
1
WAN (6031 hp)
LAN (2879 hp)
0.1
0.01
0.001
0.0001
1e-05
1e-06
20
22
24
26
28
30
32
34
Prefix Length (in bytes)
36
38
40
Bloom Filters
Uses bit array
Initialized to zeros
2n
• Insertion is easy
Use n-bit digest as
indices into bit array
Mitigate collisions by
using multiple digests
• Variable capacity
Easy to adjust
Page when full
n bits
H1(P)
1
1
H
H(P)
2(P)
2n
bits
H3(P)
1
...
• Fixed structure size
1
Hk(P)
Mistake Propagation is Limited
• Bloom filters may be mistaken
Mistake frequency can be controlled
Depends on capacity of full filters
• Neighboring routers won’t be fooled
Vary hash functions used in Bloom filters
Each router select hashes independently
• Long chains of mistakes highly unlikely
Probability drops exponentially with length
Adjusting Graph Accuracy
• False positives rate depends on:
Length of the attack path
Complexity of network topology
Capacity of Bloom filters
• Bloom filter capacity is easy to adjust
Required filter capacity varies with router
speed and number of neighbors
Appropriate capacity settings achieve
linear error growth with path length
Simulation Results
Expected Number of False Positives
1
Random Graph
Real ISP, 100% Utilization
Real ISP, Actual Utilization
Degree-Independent
0.8
0.6
0.4
0.2
0
0
5
10
15
20
Length of Attack Path (in hops)
25
30
How long can digests last?
• Filters require 0.5% of link capacity
Four OC-3s require 47MB per minute
A single drive can store a whole day
• Access times are equally important
Current drives can write >3GB per minute
OC-192 needs SRAM access times
• Still viable tomorrow
128 OC-192 links need <100GB per minute
Prototype Implementation
• Implemented on a FreeBSD PC router
Packet digesting on kernel forwarding path
Bloom filters stored in kernel space
Zero-copy kernel/user table move
• User-level query-support daemons
Supports topology discovery through gated
Queries automatically triggered by IDS
Summary
• Hash-based traceback is viable
With reasonable memory constraints
Supports common packet transforms
Timely tracing of individual packets
• Publicly Available Implementation
FreeBSD version will be available soon
Linux port coming shortly thereafter….
http://www.ir.bbn.com/projects/SPIE