Modeling the Effects of Timing Parameters on Virus Propagation, Hacking and IT E-Book Dump Release
[ Pobierz całość w formacie PDF ]
Modeling the Effects of Timing Parameters on Virus
Propagation
Yang Wang, Chenxi Wang
Carnegie Mellon University
5000 Forbes Avenue, Pittsburgh, PA, 15213
yangwang, chenxi@andrew.cmu.edu
ABSTRACT
In this paper, we investigate epidemiological models to rea-
son about computer viral propagation. We extend the classi-
cal homogeneous models to incorporate two timing parame-
ters: Infection delay and user vigilance. We show that these
timing parameters greatly inuence the propagation of viral
epidemics, and that the explicit treatment of these parame-
ters gives rise to a more realistic and accurate propagation
model. We validate the new model with simulation analy-
sis.
(SIS) infection model or the Suscep-tible-Infected-Removed
(SIR) model. In the SIS model, a node is infected and cured
repeatedly, while in the SIR model, a node cannot be in-
fected more than once. In particular, Kephart and White
studied SIS virus propagation on homogeneous networks [11,
12], while Pastor-Satorras et al. [14, 15, 16] and Barabasi et
al. [4, 6] focused on virus propagation on various network
topologies under either SIS or SIR. Wang et al. [20] pro-
posed a topology-independent model along with a general
theory for epidemic threshold, but also assumed a vanilla
SIS propagation model.
The basic SIS and SIR propagation models are overly sim-
plistic in their treatment of timing factors during virus prop-
agation. As a result, the models mentioned above are lim-
ited in their accuracy. This work aims to extend previous
models by incorporating two specic \timing" parameters:
infection delay and user vigilance. Infection delay is a delay
in the spreading of virus from an infected node. User vigi-
lance is a period of time during which the user of a node is
vigilant against infections, which reduces the susceptibility
of that node. In this paper, we dene the vigilance period
to be a period of time immediately after the curing of an
infected node, since users in real life are more likely to be
vigilant immediately after having been notied of a poten-
tial or real infection. Both infection delay and user vigilance
were abstracted away in previous studies. We show in this
paper that studying the eects of these two parameters can
increase our understanding of the virus propagation process
and potentially leads to better defenses against computer
viruses.
The layout of this paper is as follows: In Section 2, we give
a background review of SIS and SIR. In Section 3, we de-
scribe our extensions to previous models (the homogeneous
model, in particular). In Section 4, we show that our models
accurately predict the eects of the timing parameters and
analyze our ndings. We discuss some implications of our
results and summarize in Section 6.
Categories and Subject Descriptors
C.2.3 [Computer-Communication Networks]: Network
Operations|Network monitoring, Public networks
General Terms
Security, Theory
Keywords
Computer Virus, Epidemiology, Anti-virus, Security
1. INTRODUCTION
Computer viruses and worms are a great threat to the
dependability of computer networks. The recent prolifera-
tion of malicious code that spreads with virus code exacer-
bates the problem [13, 17, 18, 1]. In order to understand
their propagation behavior and to devise eective strategies
against their propagation, we need to be able to model the
propagation process accurately. Unfortunately, with the ex-
ception of a few specialized modeling studies [11, 12, 14, 16,
20, 19], much still remains unknown about the factors that
inuence computer virus propagation.
In this paper, we examine viral propagation process through
epidemiological models. Epidemiological models have been
used in previous computer virus and worm studies. These
studies often use either the Susceptible-Infected-Susceptible
2.
INADEQUACIES OF SIS AND SIR
A model of virus propagation has primarily three results:
The rate of propagation determines how quickly the
virus spreads and is represented as a function of time
t.
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 prot or commercial advantage and that copies
bear this notice and the full citation on the rst page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specic
permission and/or a fee.
WORM’03,
October 27, 2003, Washington, DC, USA.
Copyright 2003 ACM 1-58113-785-0/03/0010 ...
$
5.00.
The nal epidemic state determines viral prevalence
as t!1. It can either converge into a steady state
value or be divergent.
3. MODELING INFECTION DELAY AND
USER VIGILANCE FOR SIS
A classical SIS model is the Kephart and White model (in
this paper, we refer to it as the KW model). The KW model
models node communication in a homogeneous or Erdos-
Renyi network [7] as a directed graph [11]. A directed edge
from node i to node j indicates that i can directly infect
j. A virus birth rate of is dened on every edge from an
infected node, and a virus death rate of is dened on every
infected node (as shown in Figure 1). Further, both and
are considered to be constant throughout time. If we denote
the density of infected nodes in a network at time t as
t
,
then the deterministic time evolution of
t
is
d
t
dt
The epidemic threshold condition is a critical value
such that when the ratio of virus birth rate to death
rate exceeds this value, an epidemic exists in the nal
epidemic state
In this paper, we represent the viral prevalence at time t as
a fraction of the total number of nodes on the network. We
can infer from the above the number of infected nodes at t.
An SIS model of infection assumes that a node on the
network is in one of two states: Infected and therefore in-
fectious, or healthy and susceptible. The model assumes
instantaneous state transitions. That is, as soon as a node
becomes infected, it becomes infectious. As soon as a node
is cured, it is susceptible to re-infection. An SIS model is
usually concerned with the rate of propagation and the -
nal epidemic state. An epidemic threshold condition can be
derived from the model [2, 5, 11, 12, 16, 20].
An SIR model assumes that a node on the network can
be in one of three states: Healthy (susceptible), infected
(infectious), and removed (immune or failed). Instead of cy-
cling between susceptible and infectious, a node is infected
only once before being removed from the network, either
due to acquired immunity or node failure. Since all suscep-
tible and infected nodes will eventually be removed, an epi-
demic model that assumes SIR always produces a zero nal
epidemic state. Therefore, such a model is only concerned
with the rate of propagation and the maximum density of
infected nodes present during the epidemic \run" [2, 22].
Both the SIR model and the SIS model assume that there
is zero delay between the dierent state transitions. In re-
ality, however, there may be a time lag between the arrival
of a virus on a node and further infections dispatched from
that node. For example, in the case of email viruses, some
users may not check their email as frequently as others, so a
virus could lie dormant in a user's inbox for a period of time
before it wreaks havoc. In addition, an active virus may be
delayed before propagating due to system conguration or
resource availability. Some viruses may purposely lay dor-
mant for a period of time prior to infecting other nodes for
stealth reasons.
Further, once a node has been infected by a virus and
subsequently cured, the user of that node may become more
vigilant against future infections. In the extreme case, per-
manent vigilance will mark the node as being immune to
re-infection attempts, thus reducing the infection model to
SIR.
One might suggest that parameters such as infection de-
lay and user vigilance can be incorporated into the infection
rate. We believe that this model is overly simplistic. For
instance, a resident but dormant virus might be detected,
but a virus in transit cannot. Similarly, as noted above, vig-
ilance in an SIS model can potentially change the infection
model to SIR, which results in a dierent epidemic model.
This paper is concentrated on modeling viruses that spread
in a similar fashion to email-based viruses. Specically, we
assume that a susceptible node can be infected by the same
virus repeatedly. In the remainder of the paper, we propose
extensions to previous models to incorporate the eects of
infection delay and user vigilance. In this paper, we consider
universal delay and vigilance. Delay and vigilance that vary
across the network require more complicated models and are
beyond the scope of this paper.
=
hki
t
(1
t
)
t
(1)
wherehkiis the average outgoing degree of nodes in the
network. We solve Equation 1 to yield
0
(1
0
)
0
+ (1
0
0
)e
(hki)t
t
=
(2)
with a steady state solution,
1
, of
1
= 1
0
(3)
where
0
=
hki
and
0
is the initial density of infected
nodes. If we denote the epidemic threshold as , which is
the ratio of
above which there is a steady state epidemic,
then by setting the right hand side of Equation 3 equal to
0, the KW model yields
1
hki
=
(4)
Equation 4 means that no epidemic will occur if the virus
death rate exceeds the product of the virus birth rate (per
edge) and the average number of edges connected to a node.
Figure 1: The KW model on a directed graph
In this section, we introduce a new epidemic model that
incorporates both infection delay and user vigilance. We
use the KW SIS model as a basis, but the model can be
extended to other SIS or SIR models. Delay and vigilance
are independent parameters. We present them separately at
rst, then combine the two into a single model.
3.1 Modeling the effects of infection delay
We dene infection delay
i
as the length of time between
the virus arrival on node i and the instant i becomes in-
fectious to its neighbors. For this paper, we assume
i
to
be universal and constant, and denote simply as . In this
model, we make a distinction between \infected nodes" and
\infectious nodes." Intuitively, infection delay slows the vi-
ral propagation and may allow curing to occur before a node
becomes infectious. The new equation incorporating delay
can be written as
d
t
dt
Intuitively, user vigilance makes a node less susceptible to
infections for a period of time after curing, which reduces
the susceptible population. This results in a Susceptible-
Infected-Immune-Susceptible (SIIS) model of infection. If
we assume a universal and constant vigilance coecient ,
then we obtain the following equation
d
t
dt
t
=
hki
t
(1
t
s
ds)
t
(8)
t
where
s
= 0 for s < 0. If we set to 1, then nodes simply
stay completely immune to infections during their vigilance
period and become fully susceptible again when the vigi-
lance period ends. In Equation 8, the population density of
susceptible nodes at time t is reduced by the fraction of the
nodes that are still in their vigilance period. For = 0 or
= 0, Equation 8 reduces to the original KW model.
Equation 8 is again a non-linear delay dierential equa-
tion. We obtain
1
for = 1 and t by setting the
left hand side of Equation 8 to 0 and
s
=
t
. Ignoring the
trivial solution of
t
= 0, we obtain
hki
t
e
(1
t
)
t
=
(5)
where
t
= 0 for t < . For t, the density of infectious
nodes is the density of infected nodes at time t, since all
nodes infected between t and t are still being delayed.
Curing a node during , the infection delay period, results
in the e
term. For 0t < , since all infected nodes
are being delayed, the infected population density simply
decreases at the rate of curing.
We note that the model in Equation 5 incorporates a new
state in the traditional SIS model: A susceptible node enters
the delayed state with the arrival of an infectious agent. A
delayed node becomes either cured or infectious by the end
of the delay period.
Equation 5 belongs to the class of non-linear delay dif-
ferential equations for which there rarely exist close-form
solutions. We solve for
1
by setting the left hand side of
Equation 5 to 0 and
t
=
t
.
1
0
1 +
hki
hki(1 + )
1
=
=
(9)
Equation 9 shows that, when = 1,
1
decreases toward
zero, and the rate of decrease diminishes as the value of
increases. If we set to zero, then Equation 9 simply yields
1
of the original KW model (see Equation 3). Equation 9
yields the same epidemic threshold as the basic KW model.
In other words, user vigilance does not aect the epidemic
threshold.
We now turn to a more complex form of the vigilance
model for which is no longer constant. Rather, the vig-
ilance coecient is a function
t
that decreases over time,
where
0
= 1 and
= 0. This model captures the notion of
dynamically degrading user vigilance. An example of such
a function is
t
= 2e
tln(2)
, as shown in Figure 2 (this
particular function was chosen for illustration purposes and
is not derived from real data). We believe that user vigi-
lance is typically at its maximum immediately following a
virus detection and cleansing operation, and then decreases
in some fashion over time before the node becomes fully sus-
ceptible to infections again. We call this model the dynamic
vigilance model. The time evolution of this model is
hkie
hkie
= 1
0
e
1
=
(6)
Equation 6 shows that the steady state of viral density de-
cays toward zero at an exponential rate as a function of the
length of infection delay. We can derive the epidemic thresh-
old by setting the right hand side of Equation 6 equal to 0,
which yields
e
hki
del
=
(7)
Equation 7 indicates that infection delay increases the epi-
demic threshold, which means that infection delay makes an
epidemic die out more easily.
3.2 Modeling the effects of user vigilance
We dene user vigilance as a period of time after cur-
ing during which the user of a node is vigilant against re-
infection of the node. We represent vigilance with two pa-
rameters:
t
d
t
dt
=
hki
t
(1
t
s
ts
ds)
t
t
(10)
where
s
= 0 for s < 0.
We solve Equation 10 for
1
, and obtain
The vigilance coecient,
i
, that indicates the suscep-
tibility of the node.
i
is a quantity between 0 and 1.
A
i
of 0 indicates full susceptibility, and 1 indicates
complete immunity.
hki
hki(1 +
1
=
t
t
ts
ds)
1
0
1 +
=
(11)
0
s
ds
The vigilance period,
i
, that indicates the length of
time after curing during which the node is vigilant
against re-infection attempts. At the end of that pe-
riod, the node becomes fully susceptible to infections
again.
Equation 11 shows that
1
decreases in a similar fashion as
in Equation 9, albeit at a slower rate. Again, vigilance has
no eect on epidemic threshold.
3.3 Combining delay and vigilance
We thus far have analyzed the eect of infection delay and
user vigilance separately. We note that the two factors are
In this paper, we assume
i
to be universal and constant,
and denote it as .
Figure 2: Example
t
= 2e
tln(2)
, where = 10 time
Figure 3: Infected population density for vari-
ous lengths of infection delay on 1000-node Erdos-
Renyi network
units
independent. A joint model can be written as
In a similar vein, Figure 4 shows three simulation results
plotted against the solution of the simple vigilance model
(Equation 8) for = 1. As shown, the simulation results
also conform fairly well with the predictions of the vigilance
model.
t
d
t
dt
hki
t
e
(1
t
=
s
ds)
t
t
(12)
where
t
= 0 for t < and
s
= 0 for s < 0. Assuming
= 1,
1
is
hkie
hkie
(1 + )
1
=
(13)
Note that the epidemic threshold for this model is exactly
the same as that of the delay model, since vigilance has no
eect on the epidemic threshold.
4. SIMULATION ANALYSIS
In this section, we present a set of simulation results that
demonstrate the accuracy of our models in describing vi-
ral propagation on homogeneous networks with delay and
vigilance.
We built a simulator on top of the Network Simulator [8]
to conduct our simulation experiments. Each simulation run
begins with one randomly chosen infected node on an Erdos-
Renyi network of 1000 nodes with an average connectivity of
approximately 4. Simulation proceeds in steps of one time
unit. During each step, every infectious node i attempts to
infect each of its neighbors j with probability . In addition,
every infectious node i is subject to a curing attempt with
probability . If the curing of i occurs before the infection
attempt, then i does not send out infections to j. If j is
already infected and the curing of j falls after the infection
attempt, then the infection attempt on j does not have any
eect. Infection delay and user vigilance periods are multi-
ples of the simulation time unit. Infection delay appears as
a period of viral dormancy on a node after each incoming
infection. User vigilance appears as decreased for a period
of time for a node after each curing. Each simulation plot
shown is averaged over 15 independent simulation runs.
We solve the delay model (Equation 5) numerically and
plot the solution with three simulations in Figure 3. The
delay periods for the simulations are 1, 2, and 3 time units,
respectively. As shown, the simulated virus propagation
with infection delay conform to the delay model reasonably
well.
Figure 4: Infected population density for vari-
ous lengths of user vigilance on 1000-node Erdos-
Renyi network
Figures 3 and 4 show that both delay and user vigilance
play an important role in reducing virus prevalence in the
network. However, while the rate of decay in
1
decreases
as the vigilance period increases, the rate of decay grows
exponentially with the length of delay. Simply stated, the
longer the delay, the faster
1
drops. In contrast, the longer
the vigilance period, the slower
1
drops. Figures 5 and 6
demonstrate the trends by plotting Equations 6 and 9 with
various lengths of delay and vigilance periods. For Figure 6,
= 1.
We note that the delay model assumes that delayed viruses
are removed at the same rate as the ones that have exposed
themselves by infecting others. This means that the local
virus detection tools need to be sophisticated enough to de-
tect the presence of possibly dormant viruses. If delayed
viruses are not detected and removed at rate , then the
dynamics of viral propagation is
d
t
dt
=
hki
t
(1
t
)
t
(14)
density of all nodes infected by the virus during its entire
lifetime. As shown, infection delays suppresses the infection
spread for the SIR model. In additiont o reducing the peak
t
, infection delays reduce dramatically the total number of
nodes ever infected. In Figure 7, a delay of unit 2 produced
a 40% drop in the total number of infected nodes.
Figure 5:
1
decays as delay increases
Figure 7: Density of currently infected nodes and
total aected nodes for various lengths of infection
delay on 1000-node Erdos-Renyi network
6. DISCUSSION AND CONCLUSION
Researchers have been exploring mechanisms such as vir-
tual execution environment [3], secure NIC [10], and limited
connection rates [21] to halt viral trac in computer net-
works. It has been suggested that introducing intentional
delays in these mechanisms would be an eective way to
stop viral propagations [9, 3]. Our models demonstrate that,
given suciently long delay, this strategy will indeed be ef-
fective. However, since articial delays will aect the per-
formance of the network, the problem then becomes one of
balancing reduced viral prevalence and system performance.
On one end of the spectrum are mission critical systems
that may not tolerate any delays. On the other are sys-
tems that do not require real time responses, and hence are
more amenable to delay-inducing mechanisms. Decisions on
the appropriate length of infection delay is best made on a
case-by-case basis.
The diminishing returns produced by a longer vigilance
period leads to a very practical question: at which point
does the cost of user vigilance outweigh the benet? The
answer to this question may provide useful guidelines to, for
instance, the time window after the detection and removal of
a virus during which a virus scan must be run frequently (af-
ter which the scan may be invoked less frequently). Present
policies governing the frequency of virus scans can be tuned
with our model.
Our study suggests that the most cost eective strategy
will need to employ a combination of infection delay and
user vigilance. Both rules that govern user behavior and
rules followed by the systems on the network can be tuned
according to the predictions provided by our models.
The models presented in this paper are based on the KW
SIS epidemic models for homogeneous and Erdos-Renyi net-
works. However, we can also incorporate infection delay and
user vigilance into other SIS (or SIR) models such as the
ones presented by Pastor-Satorras et al. [16] and Wang et
Figure 6:
1
decays as vigilance increases
where
t
= 0 for t < .
1
of Equation 14 is simply that
of the basic KW model (see Equation 3), since these delayed
infections only delay the process of reaching steady state.
5. MODELING DELAY AND VIGILANCE
FOR SIR
We thus far have analyzed delay and vigilance based on
the KW SIS model. In this section, we present our extended
models in the SIR context. In an SIR model, by denition,
vigilance is essentially innity ( =1). In other words,
only the delay extension is applicable. Restating Equation
12,
t
d
t
dt
hki
t
e
(1
t
=
s
ds)
0
t
(15)
where
t
= 0 for t < . Solving for
1
yields
hkie
hkie
(1 + 1)
1
=
= 0
(16)
Equation 16 conrms previous results that the nal epidemic
state for an SIR model is zero.
Since equation 15 does not have a close-form solution, we
plot simulation results only in Figure 7. Delays of 0, 1, and
2 time units are plotted. These simulations are run on a
1000-node homogeneous network with average connectivity
10. A node is marked immune after the rst curing. We plot
both
t
and the total density of aected nodes, which is the
[ Pobierz całość w formacie PDF ]