Transcript Simulating Worms

Simulating Worms
NRG 9/20/04
Nahur Fonseca
Niky Riga
Background
A computer worm is a program that self-propagates
across a network exploiting security or policy flows in
widely-used services [WPSC03]
A computer virus infects non-mobile files and
needs user’s help to propagate
target discovery
payloads
activation carrier
motivation
Worms in action …
Target discovery techniques
 Random, sequential, local
 Hitlist (external, internal)
Outline
Why to study?
 How to study?
 How to simulate?
 Case studies
 Conclusion

Why to study?

Worms can compromise very large numbers of
hosts in a short time







DDOS attacks
steal/corrupt data
disrupt network operation
cause hardware damage
Understand worms’ behavior
Design detection/removal systems
Estimate worst case scenario
How to study?

Mathematical Models
+ powerful prediction method
- hard to create a realistic model

Testbeds
+ observe actual behavior
- small scale
- use of real code

Real World Experiments
+ real measurements
- moral reasons

Simulations
+implement complex
mathematical models
+simulate mechanism
- Need for abstraction
- Is it feasible?
Epidemiological Spread Model
ds (t )
  s (t ) i (t )
dt
di (t )
 s (t ) i (t )   (t )i (t )
dt
dr (t )
  (t )i (t )
dt
 is the rate of infection. It
depends on two things:
• rate of probes by worm
(limited by the wire speed)
• ratio of vulnerable IP
addresses over total address
space
Where s(t), i(t) and r(t) are state
variables:
 s(t) – number of susceptible
 i(t) – number of infected
 r(t) – number of removed
The removed machines are only in the
SIR model. Some papers use only a SI
model, without removals.
γ is the rate of removal
•manual
•automatic
Difficulties in simulating worms…

Simulation on the Internet is
difficult.[FP01]



heterogeneity
today’s Internet is not tomorrow’s
Worm activity is inherently difficult




number of machines
abstraction level (slammer worm ~108 pps)
modeling worm’s strategy
granularity
Comparison classes

Network topology



Worm traffic



Direct: generated traffic
Indirect: impact on other protocols (BGP, ICMP)
Worm behavior



Full mesh | AS level | ?
With/without network properties (latency, bandwidth.)
Target discovery
Latency vs bandwidth limit
Validation

Compare to actual worm data or analytical model
Case 1 [MSVS03]



Problem: How to effectively contain worm spread?
Solution: Simulate to evaluate the effectiveness of
Blacklisting and Content filtering.
Topology:





Ideal case: Full mesh.
Practical deployment: AS level topology.
Worm traffic: not modeled at all.
Worm behavior: uniform scan.
Validation: well known epidemiological model.
Case 1: Simulation Details
Infected hosts contact vulnerable hosts with
a fixed rate   r N32 for all hosts.
2
 ‘Seed’ host infected at time 0 probes randly.
 First host infected at time t.
 After reaction time R all hosts are notified.
 And apply the containment strategy.
 First use ideal deployment scenario and
then a more realistic one.

Case 1: Simulation Parameters
Parameter
Probe rate r
Vulnerable population N
Reaction time R
Network model
Value
10 probes per second
360,000 (ideal)
338,652 (practical)
1 second to 1 day
Full mesh (ideal)
6,378 AS’es (practical)
Case 1: Ideal case’s results
Code Red
Case 1: Practical scenarios results
(with a reaction time of 2 hours)
Scenario
IP-IP path coverage
Infection after 24h
25% customers
34%
65%
50% customers
57%
45%
75% customers
75%
25%
Top 10 ASes
88%
70%
Top 20 ASes
95%
40%
Top 30 ASes
97%
10%
Top 40 ASes
98%
5%
Top 100 ASes
99%
2%
Case 1: AS selection
What should be the criteria of AS selection?
ineffective
In this plot, 50% of the customer ASes were selected for
deployment of the quarantine system.
Case2([LYPN02 ,LNBG03])



Problem: How to simulate realistic network traffic created
by the worm?
Use packet level simulator!
Slammer : infected hosts ≈75.000 hosts
simulate 3 108 pps
scan rate ≈ 4000 scans
Solution: Use a mixed abstraction level
Topology:




AS level topology
Worm traffic: spatial epidemiological model +
+ packet level simulation
Worm behavior: uniform scan
Validation: comparison with real measurements
Case 2: Evidence of BGP instabilities
caused by worm traffic
Number of advertised prefixes in 30 seconds windows versus time.
Nimda
Code red II
Case 2: Network model
AS level topology.
 One router per AS.
 AS size is drawn empirically as obtained
from Route Views.
 Number of vulnerable machines/AS is
drawn empirically as observed in CR II.
 Topology is reduced from an approximate
graph derived from Route Views.

Case 2: Stratified SIR math model
ds j (t )
dt
di j (t )
dt
drj (t )
dt
  s j (t ).( 1 j i1 (t )  ...   mjim (t ))
 s j (t ).( 1 j i1 (t )  ...   mjim (t ))   j i j (t )
  j i j (t )
where,  ij   j   .
ip ( A j )
iptotal
Rate of infection is
proportional to the
advertised IP address
space of each AS.
Case 2: Mixed Abstraction Level
Macroscopic Level
Epidemic Model
Spatial epidemic model
j
AS Topology
Network
Vulnerable hosts
Border router
mapping
Packet level
simulation
Microscopic level
Mapping



Packets entering subnetwork j: Poisson process with λj(t) = σingrj(t)
An address exists in network j w/ probability uj
Realistic simulation of traffic (TCP, ICMP, BGP, etc)
Case 2: Validation (Code Red II)
Comparison with real data from a /16 network
At the peak real data 50% higher
scanning rate
Network Translation Gateways
Reinfections
Imperfection in random number
generation
Case 2: Validation (Sapphire)
Comparison with real data
Linear scale
Logarithmic scale
+ estimated TRIUMF Canada
… simulated
infections
infections
+ estimated TRIUMF Canada
… simulated
time
Model not accurate:
1. Sapphire was bandwidth limited
Bandwidth not modeled in the simulation
2. Faulty random generator
time
Case3([WDPH03])



Problem: How can we create a generic worm
propagation simulator?
Solution: Model as many aspect possible
Topology:





Internet Model
Full Mesh
Worm traffic: Simulate UDP/TCP messages
Worm behavior: tunable
Validation: comparison with real measurements
Case3: Internet Model



Divide the network into different groups
Each group shares the same characteristics
Create a full mesh
How to make this model realistic?
Use client connection
measurements from P2P
systems (Napster, Gnutella)
Bandwidth
64 kbit/s
128 kbit/s
1Mbit/s
3Mbit/s
Napst.
32%
5%
38%
25%
Gnut.
10%
14%
38%
38%
Latency
1,000 ms
300 ms
100 ms
60 ms
Case3: Simulator Parameters
Worm parameter
Hosts in the Internet
Vulnerable hosts
Start population
Simulation time span
Transport protocol
TCP resend on timeout
TCP timeout
Worm size (no header)
Parallel scans (TCP)
Unit
hosts
hosts
hosts
seconds
TCP or UDP
enable/disable
milliseconds
bytes
–
Lower limit
1
1
1
0
–
–
0
0
0
Upper limit
4,294,967,296
hosts in the Internet
vulnerable hosts
no limit
–
–
no limit
65535
no limit
Additional time to infect a host
Hitlist
Hitlist length
Probability a hitlisted
host is vulnerable
milliseconds
enable/disable
hosts
-
0
–
0
0%
no limit
–
hosts in the Internet
100%
or scans per second (UDP)
Limitations
Even
distribution of vulnerable hosts in the groups
Countermeasures are not modeled
Case 3: Validation (Sapphire)
Original Network Model
Adjusted Network Model
90%
10mins
More than 90% in ten minutes
Need to update the parameters of the model
Case 3: Validation (Code Red II)
Measurements by CAIDA
Simulation results
4 group Napster model
No modeling of the administrator’s actions
Conclusion

Simulating in large scale

needs simplifications



needs to ask the right questions about the problem




limited resources, limited information, easier to understand
and interpret
not only the ones showed here
Case1: stop the spread
Case2: worm traffic side effects
Case3: simulate your own worm
need to validate


Hard to obtain real measurements
what else can be done?
Thank you
Questions?
Conclusion
References
A taxonomy of computer worms
How to own the internet in your spare time
Difficulties in simulating the Internet
Experiences with Worm Propagation
Simulations
Simulating Realistic Network Worm Traffic
for Worm Warning System Design and
Testing