# Presentation: 616447

## David M. Nicol
Assoc. Director R&D, ISTS
Professor of Computer Science, Dartmouth

- Assoc. Director R&D, ISTS
- Professor of Computer Science, Dartmouth

- Network Security Research Using
- High Performance Simulation

## My First Car 

- 1967 VW Microbus
- Mine was yellow, with spots of black primer
- Car repair, Control Data Corporation style

## We Count Tera-Xs Too (courtesy of George Riley)

**Packet view of Internet:**
- 110M hosts, 1.1M routers
- 50%/50% modem/10Mpbs ethernet connectivity by hosts
- Router-Router
- 50% 10Mbs, 40% 100Mbs
- 5% 655Mpbs, 5% 2.4Gbs
- Link utilization
- 50% host-router
- 10% router-router
- 1% hosts “connected” at a time
- Avg packet size 5000 bits

**These assumptions imply**
- 0.3 Tera-events/sec
- At 1M evts/sec/CPU, 300K execution secs/model second
- 290 Terabytes memory, just for traffic in flight
- This analysis is
- 	conservative
- 	already 1.5 years old

## Internet Scale Problems Require Supercomputing

- Major DoD networks use commercial infrastructure
- Vulnerable to co-location, e.g. peering hotels, shared fiber
- Large set of heterogeneous networks, analysis requires detailed representation
- Securing Routing Infrastructure
- Each router has entry for every announced network prefix
- Memory demands grow as a square of network size
- Routing convergence depends on topology
- Assessing cyber-attack effects on routing
- Recent worms use entire Internet, must be represented at some level

## Large-scale Network Simulation using SSF

- SSF - scalable simulation framework
- Java and C++ APIs
- Framework for domains
- Execution on shared memory clusters
- Widely used, ported to many platforms
- Applications
- DDoS attacks/defenses
- BGP black-hole attacks
- Worm propagation and effect on routing
- Security of BGP

## Speedup : DaSSF (C++)

- Figure of merit tied to rate of network simulation work.
- 640K concurrent TCP sessions delivered (one per host)
- Many more TCP sessions possible by colocation
- Linear speedup on COTS cluster computer. Speedup is nearly 31 of 32

## BGP Primer

- Internet is a confederation of “Autonomous Systems” (each AS *originates *various *prefixes* of Internet addressing space)
- Traffic flow between them is dynamically maintained : Boundary Gateway Protocol is the glue
- Every BGP router is supposed to know how to get to every advertised prefix
- A BGP router bases the routes it *advertises* on the routes its *peers* advertise
- A *Session reset* is the re-establishment of a relationship between two peers---happens following a router reboot, or re-establishment of a TCP session between them
- Global information propagation
- Any AS being “difficult to get to” will cause a great deal of BGP update traffic.

## Efficient Securing of BGP Path Advertisements

- Problem : Efficient authentication of BGP path in advertisement
- 			   202.128.0.0/14 703 17 34
- Without authentication, AS path can be spoofed
- By an intruder masquerading as a peer
- Prefix origination can be spoofed
- Various attacks : block hole, sniffing, economic, DoS
- A solution is to apply authentication at every hop in the path
- 			      202.128.0.0/14 703 17 34
-                s(h(703 17)) s(h(17 34)) s(h(202.128.0.0/14 34))
- Source/destination must be signed to defeat “cut and paste” attack
- A rogue peer R observes announcement  A ->B, copies it and sends to D
- Multiple signatures every announcement

## S-BGP : Cost analysis

- Crypto costs (RSA, 1024-bit modulus,SHA-1 hash)
- Signature: approx. 512 modular exponentiations and 1024 squaring
- Verification : 2 large exponentiations and small (17) squarings
- Hash : linear in the length of the hashed data
- Outbound crypto operation costs
*Separate hash & signature for every peer*
- Inbound crypto operation costs
-  hash and verification of each hop
**High connectivity** and long paths make this very costly

## The Cost of Crypto Matters

- Convergence time is affected by extra cost each advertisement
- Experiment (using SSFNet)
- 110 AS graph reduced from internet topology, avg degree 5.2, max degree 20
- Max degree AS crashes, reboots
- Measure time needed for paths to AS to all settle
- Behavior as function of MRAI considered
- Timing costs of crypto operations obtained from instrumentation

## Signature Amortization : Reduction of Crypto Operations

- Outbound cost reduction:
- Aggregation across peers
- Describe output set of peers with a bit vector
- Sign one message : extension+bit vector, send to all peers
- Aggregation across UPDATES
- Each MRAI release, use hash-tree to sign all unsigned UPDATES that are waiting
- Inbound cost reduction
- Lazy verification

## Behavior of Convergence time

## S-BGP Simulation on Cluster Computers

- Run on COTS cluster
- 16 2-CPU nodes, 1GB/node
- 512 AS model : 7.6Gb memory needed
- Run on ORNL Eagle and Cheetah clusters
- 8 Cheetah nodes (used 14 cpus @)
- 8 Eagle nodes (4 cpus @)
- Probably a uniquely inefficient use of these machines!
- Implementation Issues
- BGP simulator is in Java : communication, garbage collection

## Interaction of Worms and Routing Infrastructure

## Motivation

- Is there a causal connection between large-scale worm infestations and BGP update message surges?

- Observed correlation [Cowie et al., ’02]
- Globally visible BGP update bursts
- Correlated with Code Red v2 & Nimda
- Similar occurrence during Slammer

**Notes:**
NOTE: We’re aware of upcoming IMW’02 paper “Observation and Analysis of BGP Behavior under Stress” and will comment on it later in the talk.

## Application:  Explanation of worm/BGP interaction

- Variable resolution modeling of worm propagation and effect on BGP
- Diversity of scan traffic explains empirical observations

- Worm
- Epidemic

- Router
- stress

- BGP

- scan
- traffic

- session
- resets

- BGP
- updates

- Increasing model resolution

## Worm/BGP experiments:BGP when worm spreads : worm->reset->advertisements 

- Global infection growth curve closely matches reality

## Worm/BGP experiments: reverberating advertisements

- Cascading lengths due to cycling through backup paths

## High Performance Simulation : Summary

- We have a mature toolset designed to study large-scale systems.
- Designed to scale up with problem size and execution engine
- Proven on large-scale problems and large-scale machines
- Used on a number of networking studies
- DDoS attack analysis
- Worm propagation / BGP
- BGP convergence
- BGP black hole attacks