Epidemic Profiles and Defense of Scale-Free Networks, Hacking and IT E-Book Dump Release
[ Pobierz całość w formacie PDF ]
Epidemic Profiles and Defense of Scale-Free Networks
Linda Briesemeister, Patrick Lincoln, Phillip Porras
SRI International
333 Ravenswood Avenue, Menlo Park, CA 94025, U.S.A.
firstname.lastname@sri.com
ABSTRACT
In this paper, we study the defensibility of large scale-free
networks against malicious rapidly self-propagating code such
as worms and viruses. We develop a framework to investi-
gate the proles of such code as it infects a large network.
Based on these proles and large-scale network percolation
studies, we investigate features of networks that render them
more or less defensible against worms. However, we wish
to preserve mission-relevant features of the network, such
as basic connectivity and resilience to normal nonmalicious
outages. We aim to develop methods to help design networks
that preserve critical functionality and enable more eective
defenses.
We report here on preliminary research aimed at building
a framework to help understand how to defend networks
with certain properties from worms. The starting points
of our research include three main points: (1) studies of
worms and viruses and the strategies they employ to infect
a given system, and more importantly, their strategies for
propagation (how they target new systems to attack), (2)
studies of percolation and epidemic spread in large networks
exhibiting key properties observed in intranets such as scale-
freeness, and (3) studies of preservation of mission critical
functionality for a network.
Obviously, relative safety from malicious worm outbreaks
is achievable through reduced network connectivity. In the
extreme case of truly disconnected networks, worms can-
not propagate from one partition of the network to another
(never mind that many network partitions claimed to be
\airgapped" suered from worm and virus outbreaks orig-
inating from other partitions. Forensic evidence that the
networks were connected in unauthorized ways suggest it
may be impractical to rely on this method of defense.) If
we presume networks are connected, defensibility consider-
ations motivate extremely sparse connectivity between net-
work partitions. However, random failures can, with un-
acceptably high probability, render such sparsely connected
networks disconnected, potentially compromising the mis-
sion.
We presume the mission of a given network includes preser-
vation of connectivity in some form (dened more formally
later). We assume that random, uncorrelated network out-
ages occur with a given probability P for all nodes. Fi-
nally, we assume that malicious rapidly propagating worms
will be released into the network. Under these assumptions,
we study network models and start to develop a framework
to analyze defensibility of networks against these kinds of
threats.
Categories and Subject Descriptors
C.2.0 [Computer-Communication Networks]: General|
security and protection
General Terms
Algorithms, Security
Keywords
Scale-free networks, computer epidemics, self-propagating
malicious code
1. INTRODUCTION
The escalating dependence in our nation on cyber infras-
tructure to control and transport valuable information has
left many in precarious situations, overdependent on unreli-
able and nonsurvivable systems. The disturbingly frequent
outbreak of malicious worms and viruses in the broader pub-
lic Internet often penetrate into even well-protected enter-
prise networks, or cause major disruption through targeted
or widespread denial of service attack. Thus we are mo-
tivated to study the problem of defending a large network
infrastructure from rapidly propagating malicious code.
2. RELATED WORK
Moore et al. [1] study the spread of CodeRed and related
worms through a large fraction of the actual machines in-
fected by CodeRed, under various scenarios involving con-
tent blocking and address blacklisting. They nd that un-
der reasonable assumptions, no response time is fast enough
to protect against widespread epidemic. Their model net-
work topology is based on actual Internet route maps during
the initial spread of CodeRed, but they eliminate redundant
routes from end-user machines. Thus their results are con-
servative, and the actual threat we face remains dire.
Albert et al. [2] study error and attack tolerance in scale-
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
WORM’03,
October 27, 2003, Washington, DC, USA.
Copyright 2003 ACM 1-58113-785-0/03/0010 ...
$
5.00.
67
free networks. The metrics of interest concern the connec-
tivity of networks (cluster size) after few nodes have been re-
moved. The authors nd scale-free networks robust against
random error, but not against deliberate attack of highly
connected nodes. The authors' approach has a dynamic
component of studying the network after repeated removal
of nodes, which could be seen as cascading failures.
Pastor-Satorras and Vespignani [3, 4, 5] and Eguluz
and Klemm [6] model spreading of infections under the
susceptible-infected-susceptible (SIS) model in scale-free net-
works. While Pastor-Satorras and Vespignani use the BA-
model (proposed by Barabasi and Albert), Eguluz and Klemm
use their KE-model for describing scale-free networks. Due
to dierent network models, the rst author pair nds the
absence of an epidemic threshold that determines preva-
lence, whereas the second author pair nds nite epidemic
thresholds. In our work we study both the BA-model and
KE-model of scale-free networks.
Eguluz et al. [7] characterize fractal properties of com-
plex networks. The authors derive analytical results, which
agree with numerical results obtained from simulation of
percolation in scale-free networks.
Dezso and Barabasi [8] study spreading of viruses un-
der the SIS model in scale-free BA-model networks with
randomly and deliberately (favor nodes with high degrees)
distributed cures. While randomly placed cures are ineec-
tive, policies protecting the hubs can restore the epidemic
threshold.
Leveille [9] proposes a new epidemiological model PSIDR
geared toward describing the behavior of computer worms.
The author simulates PSDIR in dierent homogeneous and
scale-free networks.
Newman et al. [10] employ a simple spreading algorithm
with 100% eciency on a graph model that they obtained
from referencing email address books. The resulting graph
is semi-directed and shows a strongly connected giant com-
ponent. Using this real topology, the authors show that the
outbreak size can be signicantly reduced when removing
up to 10% of nodes in decreasing order of their out-degree
from the giant component.
network computing environments may be highly resilient to
some forms of malicious contagions, while fatally susceptible
to others. Beyond a basic SI (Susceptible-Infected) infection
model, it is critical to understand the alignment of vulnera-
bility dependencies and host conguration.
Underlying this study is the notion that a specic epi-
demic may be proled suciently to allow an assessment
of the probability of susceptibility in end nodes. Further,
knowledge of the epidemic behavior may inuence the es-
timation of infection cost per node. In the future we plan
to bring these notions together to develop epidemic pro-
les, which assist in assessing and simulating the inherent
vulnerability or resilience of a network to known or hypoth-
esized epidemics before those epidemics are encountered in
the wild. The present paper is a rst step in that direction.
3.1 Infection Criteria
Worms and viruses have relied upon a number of infection
methods, including network service buer overows, macro
and script insertion, deception of binary code like time-of-
check-to-time-of-use (TOCTTOU) vulnerabilities, and argument-
driven subversion. The enumeration of vulnerability depen-
dencies relevant to successful infection include features such
as target operating system, enabled network services, patch
revisions, conguration settings, hardware architecture, and
resident applications. Although numerous infection tech-
niques may be applied against a wide set of vulnerabilities,
experience has shown that malicious applications have typ-
ically employed a limited set of exploit techniques, often
producing outbreaks that are highly OS or application spe-
cic.
However, the emerging \blended threat" attack mode il-
lustrates how a single contagion may employ numerous tech-
niques to infect a large heterogeneous population of hosts,
eectively producing a large infection criteria set. For ex-
ample, Nimda [11] exploited ve major infection methods,
increasing both its potential to propagate across even highly
segmented heterogeneous computing environments, and in-
creasing the overall cost of defense.
3.2 Infection Strategy
To date, there have been a number of infection strate-
gies documented, many of which have been experienced in
the wild. It is important to understand infection strategies
when evaluating security posture and formulating course of
action in the presents of an initial infection. For example,
highly segmented networks with strongly limited external
to internal availability may provide signicant channels to
topological worms, while imposing few constraints on mail
or contagion-based attacks. Further, whether a contagion-
based worm is propagating through a network service that
is critical or extraneous to the network mission will inu-
ence the cost deemed acceptable for responses that block
the channel.
A dominant strategy in worm and virus propagation has
been to employ a sequential process of scanning, in which an
infected host searches for a target victim, then propagating,
where the infected machine launches an infection attempt
against the discovered target, and iterating. Various tech-
niques have been used to explore the target space:
Mail-based { Such as the Melissa virus [12], employ
mail services and user address book information to
propagate
3. EPIDEMIC PROFILES
We are concerned with network security management in
defense of networks against fast moving malicious code epi-
demics. Success or failure of defense against malicious self-
propagating code depends greatly on the availability of com-
munication channels between susceptible nodes in the net-
work.
Networks that are inherently defendable can, with rela-
tively few alterations, prevent or signicantly delay an infec-
tion from reaching its maximum saturation potential. Sig-
nicant network segmentation, lack of communication chan-
nels among vulnerable nodes, and IP ltering to limit scan-
ning all play a role in the rate at which various epidemics
will nd targets of opportunity.
Infection strategy, meaning the method by which the epi-
demic seeks new targets, can be susceptible to variations
in network infrastructure such as the addition of content
ltering and address blacklisting. The size of the set of sus-
ceptible nodes relative to the entire target space is an impor-
tant issue in understanding spread rate, and mapping infec-
tion criteria to the network node congurations is another
important element in proling an epidemic. Homogeneous
68
Topological { Such as the Morris worm [13], leverage
substantial internal topological information on each
compromised target to seek additional new targets
and may in fact employ multiple infection strategies. To mo-
tivate the problem and illustrate our approach, we consider
a malicious code attack that spans multiple attack methods,
and can operate across a heterogeneous network.
Consider a DoD wide area network comprised of several lo-
cal area networks (LANs), all connected via a private leased
network. Each LAN contains a heterogeneous mix of many
Windows workstations and a few critical Unix servers that
host a minimal set of network services, such as DNS and
SMTP. LANs enforce strong ltering restrictions at their
gateways, while internally allow open connectivity policies.
In this scenario, the attacker seeks to maximize the sat-
uration of a malicious application across the organization,
which given the large distribution of Windows machines in
each LAN, would make a Windows exploit an important
part of the attack.
In this imagined network, between dierent autonomous
systems or LANs, Windows machines do not directly com-
municate. Rather, the primary ingress method for propagat-
ing across LANs will require the exploitation of intra-LAN
network communications, such as leveraging the SMTP chan-
nel via a technique like the Outlook MIME vulnerability
(CVE-2001-0154) to auto-launch the worm when a user views
an infected message, or an exploit against the DNS ser-
vice (CVE-2002-0374). As the DNS service does not require
human interaction via mail client, the attacker selects this
method of propagation across LANs. The location of suscep-
tible BIND servers may be discovered through typical prop-
agation methods such as the random scan, contagion-based,
or coordinated scanning techniques discussed previously.
Once inside a LAN, the attacker's objective is to satu-
rate Windows hosts with copies of the worm, potentially
enabling some payload to become active. Several meth-
ods may be employed to copy and execute the contagion on
Windows machines via exploitation of drive shares, as dis-
cussed in (CAN 1999-[0518|0519|0520]). Once invoked
on a Windows machine, the worm may continue to partici-
pate in replicating itself across drive shares until all available
shares have been infected.
We presume the worm is constructed using metamorphic
techniques which render usual antivirus signature checking
useless. Research at Symantec and elsewhere on detection
of polymorphic and metamorphic worms continues with suc-
cess, but the costs of defending against metamorphic worms
is high, and motivates the study of resource-constrained
short-term responses to outbreaks.
Contagion { \Surreptitious" malicious code propaga-
tion, which embed contagions within normal commu-
nication channels
Active Scanning { such as CodeRed [14], perform self-
propagation via random scanning to identify potential
contagion targets
Coordinated Scanning { An optimization of active scan-
ning, employ ecient segmentation of IP address space
to accelerate scan coverage, resulting in so-called Warhol
worms [15], famous for 15 minutes
Recently, an alternate strategy has been explored in which
the malicious application performs an extended scanning
phase without immediately attacking susceptible targets.
Rather, the application constructs a list of candidate suscep-
tible targets, and when this list is complete, may enter an
aggressive infection phase, in which all candidate susceptible
targets are attacked. Flash worms, hypothesized by Stani-
ford et al. [16], might employ this strategy together with
rough synchronization of infected hosts to achieve nearly
immediate pandemics in susceptible populations.
Single stage worms have also been developed, which con-
solidate the scanning and infection processes into a single
stage. For example, Sapphire [17] demonstrated that mali-
cious code propagation does not require the two-stage ap-
proach of scan and infect. Sapphire introduce a single packet
propagation strategy which merged the scan and infection
phases into a single UDP packet.
The speed of these attacks motivate the search for highly
automated defensive measures, and the study of network
topologies that are more defensible.
3.3 Epidemic Subgraph Partitioning
An epidemic subgraph represents the subgraph of a net-
work in which all end node systems possess the attributes
that satisfy the infection criteria, plus the intermediate in-
frastructure nodes that are within the traversal path of vul-
nerable end nodes employing the infection strategy. An epi-
demic tree is a subtree of an epidemic subgraph representing
a time series of rst infection events for each node, and their
interdependencies.
For example, the Sapphire worm's infection criteria in-
cludes only computers running Microsoft operating systems,
and running Microsoft SQL server 2000 or Microsoft SQL
server desktop MSDE as enabled services (most home ma-
chines running SQL server do not enable Internet access to
this service, and thus do not satisfy this infection criteria;
however many applications silently install MSDE 2000) not
running service pack SP3. The infection strategy uses UDP
port 1434 and attempts to connect to randomly generated
IP addresses, including broadcast addresses such as x.y.z.0.
The epidemic subgraph of Sapphire would include all hosts
matching the infection criteria and intermediate nodes pass-
ing UDP 1434 trac.
5. COMPUTER NETWORK TOPOLOGIES
In order to study propagation of worms with a given epi-
demic prole, we study articially generated network topolo-
gies. We endeavor to create model topologies close to ac-
tual network topologies in some key dimensions. We di-
vide models of network topologies into two categories. The
rst category contains network models exhibiting a homo-
geneous degree distribution. Regular graph topologies gen-
erally fall into this category but also notably the prominent
random graph model, which Erdos and Renyi (ER-model)
proposed [18]. The second category consists of network mod-
els with degree distributions following a power law, which is
commonly found in existing, large networks. Such models
are also known as scale-free networks.
4. EXAMPLE EPIDEMIC PROFILE
Self-propagating malicious code may span a range of capa-
bilities that increase the complexity of the infection criteria
69
5.1 Scale-Free Networks
Many real networks being studied - despite their dierent
natures - share some common features, namely scale-free dis-
tribution of degree (following a power law), high clustering,
and short average path length. We consider two scale-free
network models.
In the future, we will compare these model topologies with
actual enterprise network topologies, as well as Internet-
wide topology information such as connectivity advertised
through BGP (border gateway protocol) to route Internet
messages between Autonomous Systems.
5.2 Network Mission
We assume the network in question is built with some
purpose. For example, the provision of reliable access to
information. We model this network mission as the require-
ment that a majority of some set of C special clients be able
to communicate with the majority of some other set of S
clients. We assume that random failures or the malicious
worm prevents this mission communication on a node if it
has infected an S or C client, or if all communication paths
from an S machine to a C machine pass through at least
one down or infected node.
5.3 Fault Tolerance
KE networks, by their very nature, provide connectiv-
ity robust against random faults. In particular, all pairs of
nodes in a KE network are connected through m completely
disjoint paths. This pleasant property provides guarantees
of fault tolerant connectivity.
m
0
= 3, m = 2 (black: new node)
t = 1
t = 2
t = 3
Figure 1: Example of generating BA-model
Barabasi and Albert [19] gave a minimal model to gen-
erate scale-free networks. The BA-model takes three pa-
rameters: the number m
0
of initial nodes, the initial degree
m (m
0
) of every new node attached, and the number t
of time steps. In every time step, one new node with m
new edges is added to the graph. The new edges are con-
nected to existing nodes according to the rule of preferential
attachment. The probability to attach the new node to
an existing node i depends on the degree k
i
of this node,
Lemma 1. In a KE network with generation parameter m
there are m disjoint paths between any node in the original
set of m nodes and any other node.
such that (k
i
) = k
i
=
P
The proof of this lemma follows from results proved in [21,
22]. A sketch of the proof goes as follows. Assume coun-
terexample KE networks exist. Choose the smallest network
N with some node X disconnected from some original node
Y by removing m1 nodes. If X is an original node, then
since the original m nodes are completely connected there
can be no m1 cutset. If X is not an original node, exam-
ine the m older \parent" nodes X was connected to when X
was added to the network. Since at most m1 nodes are re-
moved from the network, one of these m parent nodes must
not be removed. If X is disconnected from Y in the modied
network, then so must its parent be. However, removing X
and considering the parent provides a new counterexample
violating our assumption of minimality.
j
k
j
. Hence, new nodes prefer to
attach to existing nodes with higher degrees. See Figure 1
for an example of generating a BA-model graph. The BA-
model produces graphs with a power law degree distribution
P (k) = 2m
2
k
3
(km).
m = 3 (A: active, I: inactive, black: new node)
A
I
A
I
A
I
A
A
A
A
A
A
I
I
I
Theorem 1. In a nontrivial KE network with generation
parameter m there are m disjoint paths between any pairs of
nodes.
t = 1
t = 2
t = 3
Figure 2: Example of generating KE-model
Theorem 1 can be proven by considering the smallest
counterexample represented by two nodes N1 and N2 dis-
connected by removal of m1 nodes. The m1 cutset
cannot disconnect the original set of m nodes, since they
are completely connected. Thus the m1 cutset must par-
tition the network such that a subset of original nodes and
N1 appear together, and N2 appears in another partition
without any original nodes. But this m1 cutset then
disconnects M2 from at least one of the original m nodes,
contradicting Lemma 1.
Theorem 1 can be used to bound the fault tolerance of
a KE network. If the chance of random failure causing a
node to be unavailable at a given time is .001 (that is 99.9%
uptime), then for our 1000 node server network, the chance
of random failures leading to no working paths existing be-
tween any two nodes in the KE network is less than 10
10
.
Klemm and Eguluz [20] introduced the KE-model to model
scale-free networks with a higher clustering coecient than
the BA-model. The authors also refer to their model as
structured or highly clustered scale-free networks. The KE-
model takes two parameters: the number of initial nodes m
and the number t of time steps. Start with m fully con-
nected, active nodes. In every time step, add one new node
and attach it to all active nodes. Make the new node active
as well. Then, choose one of the active nodes to be inacti-
vated according to a probability inversely proportional to
its current degree k
i
using (k
i
) = ((
P
j
k
j
)k
i
)
1
. See Fig-
ure 2 for an example of generating a KE-model graph. The
KE-model generates networks with the same degree distribu-
tion as the BA-model, but exhibits other network topology
features more similar to real computer networks.
70
BA networks provide much weaker guarantees, only m=2
connectivity in the worst case. However, BA networks on
average provide levels of fault tolerance equal to or greater
than KE networks.
For missions which require network connectivity, both KE
and BA networks provide adequate levels of average toler-
ance to random faults, under reasonable assumptions. Some
other obvious server network architectures (hub-and-spokes,
tree, ring, etc) provide much less resilience to random faults
and thus demand much higher levels of individual node re-
liability or provide much lower levels of delivered uptime.
Finally, guaranteed m-connectivity is also indicative of high
service provision levels during normal (non attack) opera-
tions. In future work we hope to better understand the
relationship between actual network architectures and these
simplied models.
the above discussion on epidemic criteria and epidemic pro-
les. The probability b
i
determines the chance to contract
the disease from an infected neighbor. We use = 1.
We determine b
i
from the degree d
i
of node i. We im-
plement a simple linear function that maps values between
min(d
i
) and max(d
i
) to susceptibilities 0 < b
i
< 1. We use
a descending function, so that nodes with small degrees are
more susceptible than those with higher degrees. To avoid
extreme susceptibilities of 0 and 1, we use the linear func-
tions that maps min(d
i
)1 to 1 and max(d
i
) + 1 to 0.
To motivate our simulated immunization, we consider de-
tection and mitigation techniques proposed in other research.
First we assume immunization may be triggered by a recog-
nition of malicious or anomalous content over network com-
munications through which the infection is transmitted. De-
tection may occur via techniques that recognize malicious
content embedded within known protocol trac [23]. Al-
ternatively, anomaly-based techniques may be employed to
dynamically prole normal message content [24, 25] or to
compare message content against abstract specications of
legal protocol content [26]. For this simulation we will con-
sider immunization to represent the dynamic introduction
of node-level blocking of message exchanges between those
network applications or services found to be in an alerted
state (e.g., detection may lead to the activation of a re-
sponse device described in [27]). In the general case, we
assume that while increased ltering of a network protocol
that is currently in use as an infection vector will promote
immunization, it may also impact other non-malicious net-
work functions. Thus, topologies that promote immuniza-
tion with minimal suppression of critical protocol communi-
cations could oer defensive advantage.
We compare unhindered epidemic spreading with increas-
ingly aggressive node-level blocking, and we alter our as-
sumptions of detection timeliness. In the latter setup, we
monitor the prevalence , which is the number of infected
nodes divided by the number of nodes. If the prevalence
exceeds a given response threshold
res
for the rst time,
we target the most connected nodes to be immunized (re-
gardless of them being infected or not). We study two cases
with 10 nodes (= 1% of all) and 100 nodes (= 10% of all)
being immunized when the threshold
res
is met. We con-
sider three dierent settings for this threshold: The response
is launched when at least 20%, 5%, or 1% of all nodes are
infected.
At the beginning of each simulation run, we select one
node at random to be infected. A simulation run performs
T = 25 time steps of epidemic spreading. For each set of
parameters, we carry out 50 simulation runs with dierent
seeds for the random number generator.
6. SIMULATION
Scale-free networks provide reasonable models of realis-
tic network topologies. Topological properties of scale-free
networks have been well-explored, though the dynamics of
interaction in scale-free networks are just emerging as a sub-
ject of the latest research [6, 3]. Here we study the dynamics
of malicious code propagation in various models of scale-free
networks using simulation.
Each simulated topology has N = 50; 000 nodes. We as-
sume the network architecture and epidemic prole as de-
scribed in Section 4: a large network containing N
W AN
=
1; 000 autonomous systems or LANs, where each LAN con-
tains 50 nodes, and a blended threat capable of rapidly
infecting topologically close client machines, or infecting a
server which then randomly selects other target servers for
infection. We consider both the BA- and the KE-models of
scale-free networks for the wide-area network, and we con-
sider only a simplied completely connected topology for
LANs. Assuming general node uptime (freedom from ran-
dom faults) exceeds 99% (achieved with even standard desk-
top congurations), provision of mission communications oc-
curs with very high probability. We use generating param-
eters m
0
, m, and t for the WAN models such that m
0
= m
and m = 10. Then, we perform t = N
W AN
m steps to
generate the topology.
Eguluz and Klemm [6] pointed out the divergent behavior
of epidemic spreading in the BA- and KE-model. These ana-
lytical results are based on the susceptible-infected-susceptible
(SIS) spreading model.
The SIS model has one parameter of infection probabil-
ity. Each individual of the population is either infected or
susceptible at any point in time. If individual A is infected
at time t1, it is susceptible at time t. If, otherwise, indi-
vidual A is susceptible and connected to at least one infected
individual at time t1, then with probability individual
A is infected at time t.
Here, we employ susceptible-infected (SI) spreading, which
behaves like SIS except that infected nodes stay infected and
do not change back to susceptible. In the real-world scenario
we imagine with rapidly spreading malcode, we assume that
machines do not become uninfected (but still susceptible to
the same contagion) as the SIS model assumes. Thus in our
SI-based simulations the infected nodes continue spreading
the disease.
As a variation of these spreading algorithms, we also in-
clude an individual susceptibility b
i
of nodes, motivated by
6.1 Simulation Results
Our simulation results are shown in Figures 3 and 4. The
left diagrams in Figure 3 present simulation results for a
50,000 node network where the 1,000 node WAN is con-
structed from the BA-model. The right diagrams in Figure
3 and the diagrams in Figure 4 present results for a 50,000
node network where the 1,000 node WAN is constructed us-
ing the KE approach. Each row of diagrams from top to
bottom denotes dierent settings for the response threshold
res
decreasing from 20% to 5% to 1% prevalence. The re-
sponse threshold
res
corresponds to the level of infection
in the network at which worm detection mechanisms are
71
[ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl upanicza.keep.pl
Epidemic Profiles and Defense of Scale-Free Networks
Linda Briesemeister, Patrick Lincoln, Phillip Porras
SRI International
333 Ravenswood Avenue, Menlo Park, CA 94025, U.S.A.
firstname.lastname@sri.com
ABSTRACT
In this paper, we study the defensibility of large scale-free
networks against malicious rapidly self-propagating code such
as worms and viruses. We develop a framework to investi-
gate the proles of such code as it infects a large network.
Based on these proles and large-scale network percolation
studies, we investigate features of networks that render them
more or less defensible against worms. However, we wish
to preserve mission-relevant features of the network, such
as basic connectivity and resilience to normal nonmalicious
outages. We aim to develop methods to help design networks
that preserve critical functionality and enable more eective
defenses.
We report here on preliminary research aimed at building
a framework to help understand how to defend networks
with certain properties from worms. The starting points
of our research include three main points: (1) studies of
worms and viruses and the strategies they employ to infect
a given system, and more importantly, their strategies for
propagation (how they target new systems to attack), (2)
studies of percolation and epidemic spread in large networks
exhibiting key properties observed in intranets such as scale-
freeness, and (3) studies of preservation of mission critical
functionality for a network.
Obviously, relative safety from malicious worm outbreaks
is achievable through reduced network connectivity. In the
extreme case of truly disconnected networks, worms can-
not propagate from one partition of the network to another
(never mind that many network partitions claimed to be
\airgapped" suered from worm and virus outbreaks orig-
inating from other partitions. Forensic evidence that the
networks were connected in unauthorized ways suggest it
may be impractical to rely on this method of defense.) If
we presume networks are connected, defensibility consider-
ations motivate extremely sparse connectivity between net-
work partitions. However, random failures can, with un-
acceptably high probability, render such sparsely connected
networks disconnected, potentially compromising the mis-
sion.
We presume the mission of a given network includes preser-
vation of connectivity in some form (dened more formally
later). We assume that random, uncorrelated network out-
ages occur with a given probability P for all nodes. Fi-
nally, we assume that malicious rapidly propagating worms
will be released into the network. Under these assumptions,
we study network models and start to develop a framework
to analyze defensibility of networks against these kinds of
threats.
Categories and Subject Descriptors
C.2.0 [Computer-Communication Networks]: General|
security and protection
General Terms
Algorithms, Security
Keywords
Scale-free networks, computer epidemics, self-propagating
malicious code
1. INTRODUCTION
The escalating dependence in our nation on cyber infras-
tructure to control and transport valuable information has
left many in precarious situations, overdependent on unreli-
able and nonsurvivable systems. The disturbingly frequent
outbreak of malicious worms and viruses in the broader pub-
lic Internet often penetrate into even well-protected enter-
prise networks, or cause major disruption through targeted
or widespread denial of service attack. Thus we are mo-
tivated to study the problem of defending a large network
infrastructure from rapidly propagating malicious code.
2. RELATED WORK
Moore et al. [1] study the spread of CodeRed and related
worms through a large fraction of the actual machines in-
fected by CodeRed, under various scenarios involving con-
tent blocking and address blacklisting. They nd that un-
der reasonable assumptions, no response time is fast enough
to protect against widespread epidemic. Their model net-
work topology is based on actual Internet route maps during
the initial spread of CodeRed, but they eliminate redundant
routes from end-user machines. Thus their results are con-
servative, and the actual threat we face remains dire.
Albert et al. [2] study error and attack tolerance in scale-
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
WORM’03,
October 27, 2003, Washington, DC, USA.
Copyright 2003 ACM 1-58113-785-0/03/0010 ...
$
5.00.
67
free networks. The metrics of interest concern the connec-
tivity of networks (cluster size) after few nodes have been re-
moved. The authors nd scale-free networks robust against
random error, but not against deliberate attack of highly
connected nodes. The authors' approach has a dynamic
component of studying the network after repeated removal
of nodes, which could be seen as cascading failures.
Pastor-Satorras and Vespignani [3, 4, 5] and Eguluz
and Klemm [6] model spreading of infections under the
susceptible-infected-susceptible (SIS) model in scale-free net-
works. While Pastor-Satorras and Vespignani use the BA-
model (proposed by Barabasi and Albert), Eguluz and Klemm
use their KE-model for describing scale-free networks. Due
to dierent network models, the rst author pair nds the
absence of an epidemic threshold that determines preva-
lence, whereas the second author pair nds nite epidemic
thresholds. In our work we study both the BA-model and
KE-model of scale-free networks.
Eguluz et al. [7] characterize fractal properties of com-
plex networks. The authors derive analytical results, which
agree with numerical results obtained from simulation of
percolation in scale-free networks.
Dezso and Barabasi [8] study spreading of viruses un-
der the SIS model in scale-free BA-model networks with
randomly and deliberately (favor nodes with high degrees)
distributed cures. While randomly placed cures are ineec-
tive, policies protecting the hubs can restore the epidemic
threshold.
Leveille [9] proposes a new epidemiological model PSIDR
geared toward describing the behavior of computer worms.
The author simulates PSDIR in dierent homogeneous and
scale-free networks.
Newman et al. [10] employ a simple spreading algorithm
with 100% eciency on a graph model that they obtained
from referencing email address books. The resulting graph
is semi-directed and shows a strongly connected giant com-
ponent. Using this real topology, the authors show that the
outbreak size can be signicantly reduced when removing
up to 10% of nodes in decreasing order of their out-degree
from the giant component.
network computing environments may be highly resilient to
some forms of malicious contagions, while fatally susceptible
to others. Beyond a basic SI (Susceptible-Infected) infection
model, it is critical to understand the alignment of vulnera-
bility dependencies and host conguration.
Underlying this study is the notion that a specic epi-
demic may be proled suciently to allow an assessment
of the probability of susceptibility in end nodes. Further,
knowledge of the epidemic behavior may inuence the es-
timation of infection cost per node. In the future we plan
to bring these notions together to develop epidemic pro-
les, which assist in assessing and simulating the inherent
vulnerability or resilience of a network to known or hypoth-
esized epidemics before those epidemics are encountered in
the wild. The present paper is a rst step in that direction.
3.1 Infection Criteria
Worms and viruses have relied upon a number of infection
methods, including network service buer overows, macro
and script insertion, deception of binary code like time-of-
check-to-time-of-use (TOCTTOU) vulnerabilities, and argument-
driven subversion. The enumeration of vulnerability depen-
dencies relevant to successful infection include features such
as target operating system, enabled network services, patch
revisions, conguration settings, hardware architecture, and
resident applications. Although numerous infection tech-
niques may be applied against a wide set of vulnerabilities,
experience has shown that malicious applications have typ-
ically employed a limited set of exploit techniques, often
producing outbreaks that are highly OS or application spe-
cic.
However, the emerging \blended threat" attack mode il-
lustrates how a single contagion may employ numerous tech-
niques to infect a large heterogeneous population of hosts,
eectively producing a large infection criteria set. For ex-
ample, Nimda [11] exploited ve major infection methods,
increasing both its potential to propagate across even highly
segmented heterogeneous computing environments, and in-
creasing the overall cost of defense.
3.2 Infection Strategy
To date, there have been a number of infection strate-
gies documented, many of which have been experienced in
the wild. It is important to understand infection strategies
when evaluating security posture and formulating course of
action in the presents of an initial infection. For example,
highly segmented networks with strongly limited external
to internal availability may provide signicant channels to
topological worms, while imposing few constraints on mail
or contagion-based attacks. Further, whether a contagion-
based worm is propagating through a network service that
is critical or extraneous to the network mission will inu-
ence the cost deemed acceptable for responses that block
the channel.
A dominant strategy in worm and virus propagation has
been to employ a sequential process of scanning, in which an
infected host searches for a target victim, then propagating,
where the infected machine launches an infection attempt
against the discovered target, and iterating. Various tech-
niques have been used to explore the target space:
Mail-based { Such as the Melissa virus [12], employ
mail services and user address book information to
propagate
3. EPIDEMIC PROFILES
We are concerned with network security management in
defense of networks against fast moving malicious code epi-
demics. Success or failure of defense against malicious self-
propagating code depends greatly on the availability of com-
munication channels between susceptible nodes in the net-
work.
Networks that are inherently defendable can, with rela-
tively few alterations, prevent or signicantly delay an infec-
tion from reaching its maximum saturation potential. Sig-
nicant network segmentation, lack of communication chan-
nels among vulnerable nodes, and IP ltering to limit scan-
ning all play a role in the rate at which various epidemics
will nd targets of opportunity.
Infection strategy, meaning the method by which the epi-
demic seeks new targets, can be susceptible to variations
in network infrastructure such as the addition of content
ltering and address blacklisting. The size of the set of sus-
ceptible nodes relative to the entire target space is an impor-
tant issue in understanding spread rate, and mapping infec-
tion criteria to the network node congurations is another
important element in proling an epidemic. Homogeneous
68
Topological { Such as the Morris worm [13], leverage
substantial internal topological information on each
compromised target to seek additional new targets
and may in fact employ multiple infection strategies. To mo-
tivate the problem and illustrate our approach, we consider
a malicious code attack that spans multiple attack methods,
and can operate across a heterogeneous network.
Consider a DoD wide area network comprised of several lo-
cal area networks (LANs), all connected via a private leased
network. Each LAN contains a heterogeneous mix of many
Windows workstations and a few critical Unix servers that
host a minimal set of network services, such as DNS and
SMTP. LANs enforce strong ltering restrictions at their
gateways, while internally allow open connectivity policies.
In this scenario, the attacker seeks to maximize the sat-
uration of a malicious application across the organization,
which given the large distribution of Windows machines in
each LAN, would make a Windows exploit an important
part of the attack.
In this imagined network, between dierent autonomous
systems or LANs, Windows machines do not directly com-
municate. Rather, the primary ingress method for propagat-
ing across LANs will require the exploitation of intra-LAN
network communications, such as leveraging the SMTP chan-
nel via a technique like the Outlook MIME vulnerability
(CVE-2001-0154) to auto-launch the worm when a user views
an infected message, or an exploit against the DNS ser-
vice (CVE-2002-0374). As the DNS service does not require
human interaction via mail client, the attacker selects this
method of propagation across LANs. The location of suscep-
tible BIND servers may be discovered through typical prop-
agation methods such as the random scan, contagion-based,
or coordinated scanning techniques discussed previously.
Once inside a LAN, the attacker's objective is to satu-
rate Windows hosts with copies of the worm, potentially
enabling some payload to become active. Several meth-
ods may be employed to copy and execute the contagion on
Windows machines via exploitation of drive shares, as dis-
cussed in (CAN 1999-[0518|0519|0520]). Once invoked
on a Windows machine, the worm may continue to partici-
pate in replicating itself across drive shares until all available
shares have been infected.
We presume the worm is constructed using metamorphic
techniques which render usual antivirus signature checking
useless. Research at Symantec and elsewhere on detection
of polymorphic and metamorphic worms continues with suc-
cess, but the costs of defending against metamorphic worms
is high, and motivates the study of resource-constrained
short-term responses to outbreaks.
Contagion { \Surreptitious" malicious code propaga-
tion, which embed contagions within normal commu-
nication channels
Active Scanning { such as CodeRed [14], perform self-
propagation via random scanning to identify potential
contagion targets
Coordinated Scanning { An optimization of active scan-
ning, employ ecient segmentation of IP address space
to accelerate scan coverage, resulting in so-called Warhol
worms [15], famous for 15 minutes
Recently, an alternate strategy has been explored in which
the malicious application performs an extended scanning
phase without immediately attacking susceptible targets.
Rather, the application constructs a list of candidate suscep-
tible targets, and when this list is complete, may enter an
aggressive infection phase, in which all candidate susceptible
targets are attacked. Flash worms, hypothesized by Stani-
ford et al. [16], might employ this strategy together with
rough synchronization of infected hosts to achieve nearly
immediate pandemics in susceptible populations.
Single stage worms have also been developed, which con-
solidate the scanning and infection processes into a single
stage. For example, Sapphire [17] demonstrated that mali-
cious code propagation does not require the two-stage ap-
proach of scan and infect. Sapphire introduce a single packet
propagation strategy which merged the scan and infection
phases into a single UDP packet.
The speed of these attacks motivate the search for highly
automated defensive measures, and the study of network
topologies that are more defensible.
3.3 Epidemic Subgraph Partitioning
An epidemic subgraph represents the subgraph of a net-
work in which all end node systems possess the attributes
that satisfy the infection criteria, plus the intermediate in-
frastructure nodes that are within the traversal path of vul-
nerable end nodes employing the infection strategy. An epi-
demic tree is a subtree of an epidemic subgraph representing
a time series of rst infection events for each node, and their
interdependencies.
For example, the Sapphire worm's infection criteria in-
cludes only computers running Microsoft operating systems,
and running Microsoft SQL server 2000 or Microsoft SQL
server desktop MSDE as enabled services (most home ma-
chines running SQL server do not enable Internet access to
this service, and thus do not satisfy this infection criteria;
however many applications silently install MSDE 2000) not
running service pack SP3. The infection strategy uses UDP
port 1434 and attempts to connect to randomly generated
IP addresses, including broadcast addresses such as x.y.z.0.
The epidemic subgraph of Sapphire would include all hosts
matching the infection criteria and intermediate nodes pass-
ing UDP 1434 trac.
5. COMPUTER NETWORK TOPOLOGIES
In order to study propagation of worms with a given epi-
demic prole, we study articially generated network topolo-
gies. We endeavor to create model topologies close to ac-
tual network topologies in some key dimensions. We di-
vide models of network topologies into two categories. The
rst category contains network models exhibiting a homo-
geneous degree distribution. Regular graph topologies gen-
erally fall into this category but also notably the prominent
random graph model, which Erdos and Renyi (ER-model)
proposed [18]. The second category consists of network mod-
els with degree distributions following a power law, which is
commonly found in existing, large networks. Such models
are also known as scale-free networks.
4. EXAMPLE EPIDEMIC PROFILE
Self-propagating malicious code may span a range of capa-
bilities that increase the complexity of the infection criteria
69
5.1 Scale-Free Networks
Many real networks being studied - despite their dierent
natures - share some common features, namely scale-free dis-
tribution of degree (following a power law), high clustering,
and short average path length. We consider two scale-free
network models.
In the future, we will compare these model topologies with
actual enterprise network topologies, as well as Internet-
wide topology information such as connectivity advertised
through BGP (border gateway protocol) to route Internet
messages between Autonomous Systems.
5.2 Network Mission
We assume the network in question is built with some
purpose. For example, the provision of reliable access to
information. We model this network mission as the require-
ment that a majority of some set of C special clients be able
to communicate with the majority of some other set of S
clients. We assume that random failures or the malicious
worm prevents this mission communication on a node if it
has infected an S or C client, or if all communication paths
from an S machine to a C machine pass through at least
one down or infected node.
5.3 Fault Tolerance
KE networks, by their very nature, provide connectiv-
ity robust against random faults. In particular, all pairs of
nodes in a KE network are connected through m completely
disjoint paths. This pleasant property provides guarantees
of fault tolerant connectivity.
m
0
= 3, m = 2 (black: new node)
t = 1
t = 2
t = 3
Figure 1: Example of generating BA-model
Barabasi and Albert [19] gave a minimal model to gen-
erate scale-free networks. The BA-model takes three pa-
rameters: the number m
0
of initial nodes, the initial degree
m (m
0
) of every new node attached, and the number t
of time steps. In every time step, one new node with m
new edges is added to the graph. The new edges are con-
nected to existing nodes according to the rule of preferential
attachment. The probability to attach the new node to
an existing node i depends on the degree k
i
of this node,
Lemma 1. In a KE network with generation parameter m
there are m disjoint paths between any node in the original
set of m nodes and any other node.
such that (k
i
) = k
i
=
P
The proof of this lemma follows from results proved in [21,
22]. A sketch of the proof goes as follows. Assume coun-
terexample KE networks exist. Choose the smallest network
N with some node X disconnected from some original node
Y by removing m1 nodes. If X is an original node, then
since the original m nodes are completely connected there
can be no m1 cutset. If X is not an original node, exam-
ine the m older \parent" nodes X was connected to when X
was added to the network. Since at most m1 nodes are re-
moved from the network, one of these m parent nodes must
not be removed. If X is disconnected from Y in the modied
network, then so must its parent be. However, removing X
and considering the parent provides a new counterexample
violating our assumption of minimality.
j
k
j
. Hence, new nodes prefer to
attach to existing nodes with higher degrees. See Figure 1
for an example of generating a BA-model graph. The BA-
model produces graphs with a power law degree distribution
P (k) = 2m
2
k
3
(km).
m = 3 (A: active, I: inactive, black: new node)
A
I
A
I
A
I
A
A
A
A
A
A
I
I
I
Theorem 1. In a nontrivial KE network with generation
parameter m there are m disjoint paths between any pairs of
nodes.
t = 1
t = 2
t = 3
Figure 2: Example of generating KE-model
Theorem 1 can be proven by considering the smallest
counterexample represented by two nodes N1 and N2 dis-
connected by removal of m1 nodes. The m1 cutset
cannot disconnect the original set of m nodes, since they
are completely connected. Thus the m1 cutset must par-
tition the network such that a subset of original nodes and
N1 appear together, and N2 appears in another partition
without any original nodes. But this m1 cutset then
disconnects M2 from at least one of the original m nodes,
contradicting Lemma 1.
Theorem 1 can be used to bound the fault tolerance of
a KE network. If the chance of random failure causing a
node to be unavailable at a given time is .001 (that is 99.9%
uptime), then for our 1000 node server network, the chance
of random failures leading to no working paths existing be-
tween any two nodes in the KE network is less than 10
10
.
Klemm and Eguluz [20] introduced the KE-model to model
scale-free networks with a higher clustering coecient than
the BA-model. The authors also refer to their model as
structured or highly clustered scale-free networks. The KE-
model takes two parameters: the number of initial nodes m
and the number t of time steps. Start with m fully con-
nected, active nodes. In every time step, add one new node
and attach it to all active nodes. Make the new node active
as well. Then, choose one of the active nodes to be inacti-
vated according to a probability inversely proportional to
its current degree k
i
using (k
i
) = ((
P
j
k
j
)k
i
)
1
. See Fig-
ure 2 for an example of generating a KE-model graph. The
KE-model generates networks with the same degree distribu-
tion as the BA-model, but exhibits other network topology
features more similar to real computer networks.
70
BA networks provide much weaker guarantees, only m=2
connectivity in the worst case. However, BA networks on
average provide levels of fault tolerance equal to or greater
than KE networks.
For missions which require network connectivity, both KE
and BA networks provide adequate levels of average toler-
ance to random faults, under reasonable assumptions. Some
other obvious server network architectures (hub-and-spokes,
tree, ring, etc) provide much less resilience to random faults
and thus demand much higher levels of individual node re-
liability or provide much lower levels of delivered uptime.
Finally, guaranteed m-connectivity is also indicative of high
service provision levels during normal (non attack) opera-
tions. In future work we hope to better understand the
relationship between actual network architectures and these
simplied models.
the above discussion on epidemic criteria and epidemic pro-
les. The probability b
i
determines the chance to contract
the disease from an infected neighbor. We use = 1.
We determine b
i
from the degree d
i
of node i. We im-
plement a simple linear function that maps values between
min(d
i
) and max(d
i
) to susceptibilities 0 < b
i
< 1. We use
a descending function, so that nodes with small degrees are
more susceptible than those with higher degrees. To avoid
extreme susceptibilities of 0 and 1, we use the linear func-
tions that maps min(d
i
)1 to 1 and max(d
i
) + 1 to 0.
To motivate our simulated immunization, we consider de-
tection and mitigation techniques proposed in other research.
First we assume immunization may be triggered by a recog-
nition of malicious or anomalous content over network com-
munications through which the infection is transmitted. De-
tection may occur via techniques that recognize malicious
content embedded within known protocol trac [23]. Al-
ternatively, anomaly-based techniques may be employed to
dynamically prole normal message content [24, 25] or to
compare message content against abstract specications of
legal protocol content [26]. For this simulation we will con-
sider immunization to represent the dynamic introduction
of node-level blocking of message exchanges between those
network applications or services found to be in an alerted
state (e.g., detection may lead to the activation of a re-
sponse device described in [27]). In the general case, we
assume that while increased ltering of a network protocol
that is currently in use as an infection vector will promote
immunization, it may also impact other non-malicious net-
work functions. Thus, topologies that promote immuniza-
tion with minimal suppression of critical protocol communi-
cations could oer defensive advantage.
We compare unhindered epidemic spreading with increas-
ingly aggressive node-level blocking, and we alter our as-
sumptions of detection timeliness. In the latter setup, we
monitor the prevalence , which is the number of infected
nodes divided by the number of nodes. If the prevalence
exceeds a given response threshold
res
for the rst time,
we target the most connected nodes to be immunized (re-
gardless of them being infected or not). We study two cases
with 10 nodes (= 1% of all) and 100 nodes (= 10% of all)
being immunized when the threshold
res
is met. We con-
sider three dierent settings for this threshold: The response
is launched when at least 20%, 5%, or 1% of all nodes are
infected.
At the beginning of each simulation run, we select one
node at random to be infected. A simulation run performs
T = 25 time steps of epidemic spreading. For each set of
parameters, we carry out 50 simulation runs with dierent
seeds for the random number generator.
6. SIMULATION
Scale-free networks provide reasonable models of realis-
tic network topologies. Topological properties of scale-free
networks have been well-explored, though the dynamics of
interaction in scale-free networks are just emerging as a sub-
ject of the latest research [6, 3]. Here we study the dynamics
of malicious code propagation in various models of scale-free
networks using simulation.
Each simulated topology has N = 50; 000 nodes. We as-
sume the network architecture and epidemic prole as de-
scribed in Section 4: a large network containing N
W AN
=
1; 000 autonomous systems or LANs, where each LAN con-
tains 50 nodes, and a blended threat capable of rapidly
infecting topologically close client machines, or infecting a
server which then randomly selects other target servers for
infection. We consider both the BA- and the KE-models of
scale-free networks for the wide-area network, and we con-
sider only a simplied completely connected topology for
LANs. Assuming general node uptime (freedom from ran-
dom faults) exceeds 99% (achieved with even standard desk-
top congurations), provision of mission communications oc-
curs with very high probability. We use generating param-
eters m
0
, m, and t for the WAN models such that m
0
= m
and m = 10. Then, we perform t = N
W AN
m steps to
generate the topology.
Eguluz and Klemm [6] pointed out the divergent behavior
of epidemic spreading in the BA- and KE-model. These ana-
lytical results are based on the susceptible-infected-susceptible
(SIS) spreading model.
The SIS model has one parameter of infection probabil-
ity. Each individual of the population is either infected or
susceptible at any point in time. If individual A is infected
at time t1, it is susceptible at time t. If, otherwise, indi-
vidual A is susceptible and connected to at least one infected
individual at time t1, then with probability individual
A is infected at time t.
Here, we employ susceptible-infected (SI) spreading, which
behaves like SIS except that infected nodes stay infected and
do not change back to susceptible. In the real-world scenario
we imagine with rapidly spreading malcode, we assume that
machines do not become uninfected (but still susceptible to
the same contagion) as the SIS model assumes. Thus in our
SI-based simulations the infected nodes continue spreading
the disease.
As a variation of these spreading algorithms, we also in-
clude an individual susceptibility b
i
of nodes, motivated by
6.1 Simulation Results
Our simulation results are shown in Figures 3 and 4. The
left diagrams in Figure 3 present simulation results for a
50,000 node network where the 1,000 node WAN is con-
structed from the BA-model. The right diagrams in Figure
3 and the diagrams in Figure 4 present results for a 50,000
node network where the 1,000 node WAN is constructed us-
ing the KE approach. Each row of diagrams from top to
bottom denotes dierent settings for the response threshold
res
decreasing from 20% to 5% to 1% prevalence. The re-
sponse threshold
res
corresponds to the level of infection
in the network at which worm detection mechanisms are
71
[ Pobierz całość w formacie PDF ]