Transcript Jun Li presentation at USC/ISI

SAVE: Source Address Validity
Enforcement Protocol
Jun Li, Jelena Mirković, Mengqiu Wang,
Peter Reiher and Lixia Zhang
UCLA Computer Science Dept
10/04/2001
{lijun, sunshine, wangmq, reiher, lixia}@cs.ucla.edu
Outline
 Motivation
 The Idea
 Handling Routing Changes
 Security and Deployment
 Simulation and Implementation
 Related Work
 Ongoing Work
 Conclusions
Motivation
 Provide routers with information on the valid
incoming interface for a given source address
 Filter out packets with invalid source
addresses
 Would be helpful for
 Many security issues
 Building multicast trees
 Network problem debugging
 Services relying on accurate source addresses . . .
The Idea
 Build an incoming table at a router that
specifies valid incoming interfaces for
address spaces
 Cannot be derived from forwarding table due to
routing asymmetry
 Cannot be designed by reversing routing protocol
• Should be designed to inform routers about the path
that has ALREADY been chosen
 Cannot augment routing updates to carry SAVE
info
 So, how?
Desired Properties of SAVE
 Routing protocol independence
 Immediate response to routing changes
 Security
 Incremental deployment
 Low overhead
Architecture
SAVE
updates
incoming table
forwarding table
updating
incoming
tree
generating SAVE
updates
SAVE
updates
final
stop?
yes
end
no
forwarding SAVE
updates
Example
X A
A
1
B
2
3
4
X AB
5
6
XX AAA
X
X AAA
X
X
X AAA
X
X
X AAA
X
X
XXX AAA
Y
X
4
But the green
SAVE
7
Y
3
8
incoming table
update
J
3
The says
greenmessages
router now
AB
5
A
1
knowsfrom
thatAmessages
come onfrom
X
B
2
A andinterface
B should5,arrive
not on
Forwarding table
interface
Incoming table
interface 56
Example
AB
A
10
Y AB
1
2
B
X
4
Y
3
J
3
A
1
B
2
Forwarding table
3
9
Y AB
9
11
13
14
4
12
AB
X
Y
13
Example
AB
9
P
A
Y AB
1
B
10
2
3
Y ABP
9
11
13
14
4
12
ABP 13
X
Y
Handling Routing Changes
1
C
2 D3
A
C
2
1
C
D
3
A
B
A
B
Handling Routing Changes
1
C
2 D3
A
C
2
1
C
D
3
A
B
A
B
Handling Routing Changes
1
C
D
A
2
1
C
3
B
D
C
3
A
A
B
Security of SAVE itself
 Essentially the same problem as securing
routing protocol
 Requirements
SAVE updates must only be exchanged between
routers, excluding hosts
Trust relationship between routers must be
established beforehand
SAVE updates must be signed or encrypted
Processing of SAVE updates must be lightweight
Deployment
 Can only be incremental
 Have to deal with legacy routers
 Incoming table will not cover the whole Internet
 Deployment at different location has different
impact
 Some real issues
 Mobile IP
 Tunnelling
 Multipath routing
......
Simulation
 All routers run SAVE protocol + routing
protocols
 Transit-stub topology generated using
GT-ITM
 BGP as inter-domain routing protocol
 RIP as intra-domain routing protocol
 Some asymmetric routes
Simulation Goals
 Effectiveness - are all spoofing packets
successfully detected and dropped?
 Correctness - are some valid packets dropped
erroneously?
 Transient behavior
 Cost
Effectiveness and Correctness
 Each packet source generates both valid and
spoofing packets
 Spoofing source addresses randomly chosen from
a pool of all source addresses in the network
 Every router is under an average load condition
 Results:
 In all scenarios all spoofing packets were detected and
dropped
 Without routing changes no valid packets were
dropped
Transient Behavior
 Route changes introduce a transient period for
SAVE to adjust every incoming table along the new
route
 During this period valid packets can be dropped on
new route
 Assuming that SAVE packets have same
propagation delay as data packets, inconsistency
occurs if:
 data packet is sent out on new route BEFORE new
SAVE update validating this route
 data packet is filtered at a router on the path
BEFORE new SAVE update is processed
Cost of SAVE
 Compared cost of SAVE with costs of
routing protocols (BGP and RIP)
 Bandwidth cost:
 compared bandwidth consumed by SAVE
updates with that consumed by routing updates
 Storage cost:
 compared the size of incoming table with the
size of forwarding table
Storage Cost
(single domain)
storage cost (kilobytes)
80000
70000
60000
50000
40000
30000
20000
10000
0
10
20
30
40
50
60
70
80
90
# of routers
forwarding table built by RIP
incoming table built by SAVE
optimized incoming table built by SAVE
Storage Cost
(multiple domains)
storage cost (kilobytes)
80000
70000
60000
50000
40000
30000
20000
10000
0
12
24
32
40
52
64
70
80
90
# of routers
forwarding table built by BGP
incoming table built by SAVE
optimized incoming table built by SAVE
Implementation in Linux
ROUTING
PROTOCOL
SAVE
SAVEd
ZEBRAd
BGPd OSPFd RIPd
FTABLE ITABLE
ITREE
NETLINK INTERFACE
FORWARDING
TABLE
KERNEL
FIREWALL
IP NEIGHBOR
MAP
INTMAP
Related Work
 Cryptographic Methods
 High computation overhead of cryptographic
operations
 Forwarding-table-based filtering
 Routing asymmetry leads to erroneous packet
dropping
Related Work
 Ingress and egress filtering
 Very ineffective if partially deployed
 Packet tracing
 Complex and expensive
 Ineffective when the volume of attack
traffic is small or the attack is distributed
 Reactive, not preventive
On-going Work
 Cooperation with Purdue University
on partial deployment investigation
 Implementation
 IXP router implementation
 Cisco router implementation
 Testing
 FTN testbed
 Utah testbed
 IETF draft
Conclusions
 Filtering improperly addressed packets is
worthwhile
 Asymmetric network routing demands an
incoming table
 SAVE builds incoming tables correctly with
low bandwidth and storage overhead
 SAVE has demonstrated its correctness
and effectiveness through simulation
 Implementation is under way