Transcript N, E - KAIST

Epidemiological Approach
to Network Security
13th KRNET 2005
2005.6.27.
Sue Moon
KAIST
Definitions
• An epidemic
– "an outbreak of sudden rapid spread, growth,
or development"
– what reproduces itself
• Epidemiology
– "a branch of medical science that deals with
the incidence, distribution, and control of
disease in a population"
– applies to human diseases, computer
viruses/worms, spreading of ideas and rumors
("gossip")
Epidemiologically Motivating Questions
• What are the factors that affect an
epidemic?
• What are known models of epidemic
spreading?
• How do computer viruses/worms fare in
light of known models?
• What can we do to increase network
security?
Definitions of Viruses/Worms
• Computer virus
– "A parasitic program written intentionally to
enter a computer without the users
permission or knowledge" (Symantec)
• Network worms
– "self-contained, self-replacing program that
spreads by inserting copies of itself into
other executable code or documents "
(Wikipedia)
– Require no human action to spread
Factors in Epidemiology
• Host state
– susceptible, infected, detected, removed
(immune or dead)
• Time constraints
– continuous, discrete
• Topological constraints
– well-mixed and constant
• a host meets another equally likely
• scanning strategies
– lattice, network
Simplest Epidemiological Model: SI Model
(Logistic Growth Equation)
Spreading under SI Model
Courtesy: Stanison, Paxson, Weaver.
Data fit with K = 1.8
SIR Model

“removal” rate
(Logistic Growth Equation)
dS
  I (t ) S (t )
dt
dI
 I (t ) S (t )  I (t )
dt
dR
 I (t )
dt
History of the Internet Worms
• 1988: First Internet worm
– Morris Worm: exploited buffer overflow
vulnerabilities
• 2001: Resurgence of the worms
– Code Red, Klez, Sircam
• 2003: resulting in the largest down-time and
clean-up cost ever
– SQL Slammer Worm, Blaster Worm, and Sobig
• 2004: zombies, shortened time interval between
vulnerability announcement and worm emergence
– MyDoom, Witty Worm
Code Red Worm I v1
• Exploiting buffer-overflow vulnerability
of IIS
• Probing susceptible hosts using SYN packets
• Checking if the date is between 1st and 19th
– If so, generating random IP addresses to spread
– Else, launching DoS attacks against
www1.whitehouse.gov
• Using a static seed to generate IP addresses
• Memory resident (infected hosts recover after
rebooting)
Code Red Worms I v2 and II
• Code Red I v2
• Using a random seed to generate IP addresses
• Faster propagation speed
• Code Red II
•
•
•
•
•
Completely unrelated to the original Code Red
Containing the string “Code Red II” in source code
Setting up a backdoor in the infected machine
Not memory resident
More complex host-selection method
– 1/8: random IP address
– 1/2: IP address which has the same /8 with the host
– 3/8: IP address which has the same /16 with the host
Spreading Dynamics of Code Red I v2
• Host infection rate
Spreading Dynamics of Code Red I v2
• Deactivation due to phase transition
Propagation Models
• Scanning Model: models of the worms with
various scan techniques (Jiang Wu et al.)
• Topological Model: a model on arbitrary
network topologies (Yang Wang et al.)
Scanning Model
• AAWP Model
– Where,
•
•
•
•
N: # of vulnerable hosts
T: target size
s: scan rate (# of probes per time tick)
ni: # of infected hosts at time i
Scanning Model
• AAWP Model (Cont’d)
Scanning Model
• Selective Random Scan
– selected target addresses (unallocated or
reserved IP blocks are removed)
– propagation speed
• T = 2.7 * 10^9
Scanning Model
• Routable Scan
– routable target addresses (routable IP blocks from
global routers)
– finding how many routable IP prefixes
– 49K prefixes from BGP Tables (Route Views servers)
– merging continuous prefixes (17,918 blocks, 1.17x10^9
addresses)
– combining close blocks (1926 blocks, 1.31x10^9
addresses, threshold: one /16)
– Propagation speed
• T = 1.0 * 10^9
Scanning Model
• Divide-Conquer Scan
–
–
–
–
dividing target address when infecting a host
“single point of failure”
generating a hitlist to decide splitting point
propagation speed
Scanning Model
• Hybrid Scan
– combining routable scan with random scan at a later
stage of the propagation
– able to infect hidden and protected hosts
• Extreme Scan
– DNS Scan
• difficult to get a complete target addresses
• hosts that don’t have public domain name
• huge address list size
– Complete Scan
• using the complete list of assigned IP addresses
• list size: 400Mbytes
• slower than random scan
Comparison of Scanning Models
Scanning Model
• Comparison of the Worm Scan Methods (Cont’d)
Topological Model
• Proposed Model
– Assuming general connected graph G = (N, E),
where N is the number of nodes in the
network and E is the set of edges
Topological Model
• Experiments
– Real network graphs from Oregon router view
(10900 AS peers)
– Synthesized power-law graphs (1000-node BA
network)
Topological Model
Topological Model
• Epidemic threshold with a single
parameter
Topological Model
• Generality of the Threshold Condition
How to Mitigate the Worm Threat?
S(0) = N
 =/M
 probe rate of worm
M total population (=232 IPv4)
 “removal” rate
1. Reduce # of susceptible hosts
dS
  I (t ) S (t )
(prevention)
dt
2. Reduce rate of infection
dI
 I (t ) S (t )  I (t )
(suppression)
dt
3. Reduce # of infected hosts
dR
 I (t )
(containment)
dt
Countermeasures
• Containment (David Moore et al.)
• Worm-Killing Worm (Hyogon Kim et al.)
• An Architecture for Patch Distribution
(Stelios Sidiroglou et al.)
Containment
• Key Properties of Containment
– Time to detect and react
– Strategies for identifying and containing
the pathogen
– Deployment scenario
• Containment Technologies
– Content filtering
– IP blacklisting
Containment Infrastructure
• Idealized Deployment
– Idealized setting
• Universally deployed containment systems
• Simultaneous information distributions
– Simulation parameter
•
•
•
•
Code Red I v2 spread
360,000 total vulnerable hosts
Total population: 2^32
Probe rate: 10/sec
Effectiveness of Containment
• In Idealized Deployment
Effectiveness of Containment
Effectiveness of Containment
• Practical Deployment
– Practical setting
• System deployment on the AS level
– Simulation parameters
•
•
•
•
Code Red I v2
338,652 vulnerable hosts
6,378 Ases
Default reaction time: 2 hours
Effectiveness of Containment
• In Practical Deployment
Effectiveness of Containment
• In Practical Deployment
Worm-Killing Worm
• Behaving like typical worms
– Except that it cures and patches infected hosts
– Examples: Code Green and CRClean released against
Code Red Worm
• Experiment Setting
–
–
–
–
SQL Slammer Worm
100,000 vulnerable hosts
total population = 2^32
Higher scanning rate than that of SQL Slammer
Worm
– Default reaction time a = 10 sec
– k<v
Worm-Killing Worm
• Typical Spreading Dynamics
Impact of Reaction Time
by Worm-Killing Worm
Self-Destruction of Worm-Killing Worm
• Rumor-Monger threshold r : when the probe
success rate drops below r , then the killer
worm stops spreading
Architecture for Patch Distribution
• A Network Worm Vaccine Architecture
– Automatically generating and testing patches
– A combination of
•
•
•
•
Honeypots
Dynamic code analysis
Sandboxing
Software updates
V. Summary
• Insurgence of the worms with pervasive
network environment
• Approximated propagation models and
simulation on small data sets
• Co-evolution of attackers and defenders
• No comprehensive remedy yet
• Existing work mainly focusing on postoutbreak measures
Acknowledgements & References
[1] Ahn, Yong-yeol, "Epidemics on Networks: from Physics,"
unpublished, April 2005.
[2] Kang, Min Gyung, "The Internet Worms: Propagation
Models and Countermeasures," unpublished, April 2005.
[3] David Alderson, "Mitigating the Risk of Cyber Attack,"
Guest Lecture in MS&E293, Stanford, 2003.
[4] D. Moore et al, "Internet Quarantine: Requirements for
Containing Self-Propagating Code," INFOCOM 2002.
[5] Hyogon Kim et al., "On the functional validity of
the worm-killing worm," ICCC 2005.