Modeling Epidemic Spreading in Mobile Environments, Hacking and IT E-Book Dump Release
[ Pobierz całość w formacie PDF ]
Modeling Epidemic Spreading in Mobile Environments
James W. Mickens and Brian D. Noble
EECS Department, University of Michigan
Ann Arbor, MI, 48103
jmickens,bnoble@eecs.umich.edu
ABSTRACT
The growing popularity of mobile networks makes them increas-
ingly attractive to virus writers, and malicious code targeting mo-
bile devices has already begun to appear. Unfortunately, standard
techniques for modeling computer virus propagation cannot be ap-
plied to mobile settings. We describe why these models fail and in-
troduce a new framework called
probabilistic queuing
which treats
node mobility as a first-order concern. A network is modeled by
multiple queues which emulate the skewed connectivity levels com-
mon in mobile environments. Each queue represents a separate
epidemiological population, and as nodes shuttle between queues,
they bring their infections with them. Simulations show that for
realistic mobility parameters, our model is more accurate than the
standard Kephart-White framework.
Categories and Subject Descriptors:
C.2.0 [Computer Systems
Organization]: Computer-Communication Networks —
Security
and Protection
, C.4 [Performance of Systems]: Modeling Tech-
niques, G.3 [Mathematics of Computing]: Probability and Statis-
tics
General Terms:
Security, Theory, Algorithms
Keywords:
Mobile networks, computer viruses, proximity attacks
devices would be an increasingly dangerous problem [10]. Devis-
ing epidemiological models for mobile environments is therefore
an important research area.
Malicious code targeting mobile devices has already begun to
emerge. For example, the Brador virus [21] infects Pocket PCs
running Windows CE, installing a backdoor which allows a remote
attacker unlimited access to the device. The Cabir worm [9] in-
fects cell phones running the Symbian operating system. Taking
control of the phone’s Bluetooth interface, Cabir continually scans
for other Bluetooth-enabled devices and tries to infect any such de-
vice which enters the scanning range. The Mabir [7] and Sym-
bos Comwar [15] worms use similar scanning techniques and also
propagate via MMS messages.
Brador only spreads through traditional application-level vec-
tors like email attachments and downloadable web objects. But
via Bluetooth scanning, Cabir, Mabir, and Symbos Comwar can
launch
proximity attacks
upon vulnerable machines that are phys-
ically nearby. This means that epidemiological models for mobile
networks must treat the movement of devices as a first-class con-
cern. These models must also consider that, as shown in Figure 1,
some geographic locations may be more heavily visited than others.
These “hot spots” generate skewed connectivity distributions, since
a node in a hot spot will have many more neighbors in communi-
cation range than a node in an unpopular location. Hot spots there-
fore represent more fertile breeding grounds for malicious code that
uses proximity attacks. Viral propagation is also influenced by bor-
der effects. Since walls and physical obstacles can exclude nodes
from large geographical areas, devices near these objects often have
low connectivity and thus are poor vectors for viral infection. Epi-
demiological models for mobile networks must capture such wall
phenomenon as well.
In this work, we investigate the behavior of malicious code like
Cabir which spreads via proximity-based, point-to-point wireless
links; we focus on this method of infection because it is unique
to mobile environments and has received little research attention
from the security community. This paper makes three primary con-
tributions. First, it shows that naive application of standard epi-
demiological models to mobile environments leads to erroneous
predictions. These mispredictions are often as severe as forecast-
ing an endemic network-wide infection when the virus will actu-
ally die out quickly. Second, this paper explains why the stan-
dard models fail, namely, because they ignore node velocity and
the non-homogeneous connectivity distributions that often arise in
mobile environments. Third, this work proposes a new framework
for understanding epidemics in mobile environments. This new
model, called
probabilistic queuing
, explicitly incorporates notions
of node mobility and connectivity skew. It provides an accurate
threshold condition which relates the virulence of malicious code
to the likelihood that it will cause an endemic network-wide infec-
tion. It also provides accurate estimates of these persistent infection
levels.
1.
INTRODUCTION
With the continuing proliferation of portable wireless devices
such as laptops and PDAs, mobile networks are becoming an im-
portant part of our everyday networking infrastructure. However,
the growth of mobile networking is leading to new security chal-
lenges. As the wired Internet became more popular, there was a
corresponding surge in the amount of malicious code which used
the Internet as its transmission mechanism. Similarly, as mobile
networks become more common, they too will become attractive
targets for virus writers. Just as boot sector viruses were supplanted
by viruses that spread through email attachments and other Internet
vectors [4], the emergence of widespread mobile networking will
lead to new types of malicious code. Indeed, IBM’s 2004 Business
Security Report forecast th
at malware propagation amongst mobile
This work was sponsored in part by NSF Grant CNS-0509089.
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.
WiSE’05,
September 2, 2005, Cologne, Germany.
Copyright 2005 ACM 1-59593-142-2/05/0009 ...
$
5.00.
2.5e-06
2.5e-06
2e-06
2e-06
1.5e-06
1.5e-06
1e-06
1e-06
5e-07
5e-07
0
0
500
500
250
250
-500
-500
0
0
-250
-250
0
0
-250
-250
250
250
500
500
(a) In the random waypoint model, large pause times
result in an effectively flat spatial distribution of nodes.
(b) As pause times shrink, the spatial distribution de-
velops a pronounced peak; such peaks result in non-
homogeneous connectivity distributions. In environ-
ments that are not governed by the random waypoint
model, spatial peaks can arise because of obstacles or
“popular content” regions that are frequently visited.
Figure 1: Spatial Distributions for a Square Arena Using the Random Waypoint Model
2. WHY THE KEPHART-WHITE MODEL
FAILS
Before introducing our new framework, we describe the Kephart-
White epidemiological model [13]. We then provide several exam-
ples that demonstrate the failure of the Kephart-White model in
mobile environments. Our analysis of these failures will guide the
design of probabilistic queuing.
2.1 The Kephart-White Model
The classic Kephart-White model [13] uses a differential equa-
tion to describe computer virus propagation. The model assumes
a susceptible-infected-susceptible environment—a machine enters
the system in a healthy state, and it can catch and subsequently be
cured of the infection an infinite number of times. The Kephart-
White (KW) model also assumes a homogeneous network topol-
ogy in which all nodes have similar levels of connectivity or “out-
degree.” Thus, the network can be succinctly described by a single
parameter
hki
which represents the average connectivity of a node.
Defining
I
as the fraction of nodes infected at a particular mo-
ment, the KW model uses the following equation to describe viral
propagation:
In the mobile setting,
hki
represents the average number of de-
vices within wireless communication range of an arbitrary node.
¯
represents the probability that a diseased node transmits the in-
fection to a healthy neighbor during some small time period
¢
t
.
±
represents the probability that an infected node is cured during
¢
t
. When we graph the global percentage of infected nodes versus
time, the time axis will be in units of the viral time scale
¢
t
. In this
paper, we always use a
¢
t
of 100 milliseconds.
2.2 The Kephart-White Model in Mobile
Environments
Suppose that each mobile device has a communication range of
100 meters and travels in a square arena with 1000 meter sides.
Further suppose that node movement is guided by the random way-
point model [5], pause time is 0, and that through simulation or
mathematical analysis, we can derive
hki
for the network. Fig-
ures 2 and 3 demonstrate several ways in which the KW model will
be inaccurate for this mobile environment. Note that each simula-
tion result represents the average of five runs, and all simulations
began with node speeds and locations drawn from the appropriate
steady-state distributions [16].
First consider Figure 2, which shows results for a 30 node and 60
node mobile network. In both networks, node speeds were drawn
from the range
[5
m/s,
20
m/s
]
. After 200,000 simulated seconds,
we find that
hki
N
=30
is 1.22 and
hki
N
=60
is 2.37. Given these
connectivities, a virus with
¯
=0.7 and
±
=0.25, and 10% of nodes
initially infected, the KW model predicts high endemic infection
rates in both networks. However, the simulation results disagree. In
the 30 node network the KW model predicts an endemic infection
of 70.7%, but the infection actually dies out completely. In the 60
node network a persistent infection emerges, but it has a level of
roughly 64%, not 84.9% as predicted by the KW model.
In this example, the failure of the KW model is largely due to
its strict reliance on the average connectivity statistic. Only con-
sidering mean connectivity discards useful information when the
underlying distribution has significant variance. Figure 4 shows
the connectivity distributions for the 30 node and 60 node sce-
dI
dt
=
¯hkiI
(1
−I
)
−±I
(1)
where
t
is time,
¯
is the viral birth rate along every edge from an
infected node, and
±
is the cure rate at each infected node.
¯
,
±
,
and
hki
are assumed to be constant. The KW equation has a steady
state solution of:
I
=1
−
±
¯hki
(2)
However, such an endemic infection occurs only if:
¯hki>±
(3)
In other words, an epidemic arises only when the expected viral
output of an infected node is greater than the probability that an
infected node will be cured.
100%
80%
60%
40%
KW prediction,
<k>=1.22
Simulation, N=30
(<k>=1.22)
20%
0%
0
10
20
30
40
50
Time
The KW model does not have a parameter for node speed. Thus, it
cannot distinguish between two networks with the same connectiv-
ity distribution but different node velocities. Higher node velocities
lead to greater node mixing and more virulent epidemics.
(a) In many cases, the KW model predicts a high
endemic infection level when the virus will actu-
ally die out rapidly.
Figure 3: The failure of KW predictions — no conception of
node speed
100%
50%
80%
40%
60%
N=30
N=60
30%
40%
20%
KW prediction,
<k>=2.37
Simulation, N=60
(<k>=2.37)
20%
10%
0%
0%
k=0
k=1
k=2
k=3
k=4
k=5
k=6
k=7
k²8
0
500
1000
1500
2000
2500
3000
Connectivity Degree
Time
These are the connectivity probabilities for random waypoint mo-
bile networks with 30 and 60 nodes; each node has a 100 meter
communication range, and the arena is 1000 meters by 1000 meters.
Each probability represents the likelihood that a node has the given
connectivity at an arbitrary moment; alternatively, it represents the
amount of time that a node spends with the given connectivity.
(b)
In
other
situations,
the
KW
model
correctly
forecasts
a
persistent
infection
but
overpredicts
its magnitude.
Figure 2: The failure of KW predictions — over-reliance on
connectivity averages
Figure 4: Connectivity Distributions for N=30 and N=60
narios; these distributions were generated analytically using tech-
niques from Bettstetter [1] that we summarize in Section 3.1. We
see that in the 30 node network, a device spends 42.1% of its time
with no neighbors. In contrast, a device in the 60 node scenario
is neighborless for only 26.6% of the time. These differences in
disconnected time lead to differences in epidemic behavior. As the
disconnected fraction grows, sick nodes have more opportunities to
be cured without threat of concurrent reinfection. Similarly, there
are fewer opportunities for sick nodes to infect healthy ones.
The KW model cannot detect this difference in disconnected
fraction—it only sees a reduced
hki
in the 30 node network relative
to the 60 node network. However, the homogeneity assumption of
the KW model is broken by the distributions shown in Figure 4.
Sometimes a node will have more neighbors than
hki
, but other
times it will have fewer or, importantly, none at all. Due to this lat-
ter occurrence, the predicted endemic infection rates from the KW
model are depressed or even reduced to zero in real life.
In Figure 3, we show another problem with applying the KW
model to mobile environments.
and
net
fast
in which the arena size and virus profile are the same
as in the previous examples. Each network has 60 nodes, but in
net
slow
node speeds are drawn from
[1
,
2]
, while in
net
fast
speeds
are taken from the range
[350
,
400]
. The KW model has no param-
eter for node velocity and predicts a steady state infection level of
84.9% for both networks. However,
net
slow
actually has an en-
demic infection level of about 56%, whereas
net
fast
has an en-
demic infection level of about 74%. This is despite the fact that
the two networks have the same connectivity distribution, and de-
spite the fact that they are being attacked by malicious code with
the same
¯
and
±
.
How can we explain such velocity-dependent differences in ef-
fective virulence? Intuitively speaking, nodes in
net
fast
are “bet-
ter mixed” than nodes in
net
slow
— during a given stretch of time,
they communicate with a wider variety of neighbors than the de-
vices in
net
slow
. Higher mixing rates boost viral propagation,
since diseased nodes will have more opportunities to communicate
with healthy ones. Also note that while nodes in the two networks
spend the same percentage of time with zero neighbors, devices in
We study two networks
net
slow
net
slow
have longer
uninterrupted
periods of disconnection. When
velocities are low, a node that wanders into an empty part of the
arena will stay there for a while. This gives the node many con-
secutive opportunities to be cured without the threat of concurrent
infection. In
net
fast
, such windows are much smaller in terms of
raw temporal duration.
In summary, the examples from Figures 2 and 3 demonstrate the
two problems with applying the KW model to mobile networks.
First, since the KW model relies on mean connectivity as its sole
topological metric, it cannot capture the non-trivial connectivity
variances found in mobile environments. Second, the KW model is
insensitive to node speed, which is an essential parameter in mobile
networks.
arena that two randomly placed nodes will be within communica-
tion range is:
R
a/
2
−a/
2
R
a/
2
−a/
2
c
(
x,y
)
dxdy
a
2
¯
c
=
(8)
The probability that a node at location
(
x,y
)
has
k
i
neighbors is
given by:
Ã
!
N−
1
k
c
(
x,y
)
k
(1
−c
(
x,y
))
N−k−
1
(9)
Pr
(
x,y,k
=
k
i
)=
where
N
is the total number of mobile nodes. The average proba-
bility over the entire arena that a node has
k
neighbors is:
R
a/
2
−a/
2
R
a/
2
−a/
2
Pr
(
x,y,k
=
k
i
)
dxdy
a
2
3. A NEW MODEL FOR EPIDEMICS IN
MOBILE NETWORKS
To remedy the problems with applying the KW model to mobile
environments, we propose a new analytic framework. Our
prob-
abilistic queuing
model explicitly accounts for both node veloc-
ities and the non-homogeneous connectivity patterns induced by
this mobility.
3.1 Mathematical Background
To create a probabilistic queuing system, we first must charac-
terize the mobility parameters of the underlying network. As a
concrete example, we summarize Bettstetter’s framework for de-
scribing mobility in random waypoint networks [1, 2, 5]. However,
we emphasize that probabilistic queuing is agnostic to the choice
of mobility model, and we show in Section 4.3 that it still outper-
forms the KW model for networks that are not governed by random
waypoint movement.
In the random waypoint model, nodes travel within a large arena,
typically either a rectangle or a circle. Each node iteratively picks a
random destination, travels there, pauses for a constant time
t
pause
,
and then picks another random destination. Each waypoint is inde-
pendently chosen, and before leaving for a new waypoint, a node
chooses a random speed from the uniform distribution
[
v
min
,v
max
]
.
Given a square arena having sides of length
a
, the average trip
length is:
Pr
(
k
=
k
i
)=
(10)
We can interpret
Pr
(
k
=
k
i
)
for
k
i
2
[0
,N−
1]
as the percentage
of time that a node has
k
i
neighbors.
3.2 A New Epidemic Threshold
Given a set of mobility parameters which describe an ad hoc
communication topology, our most basic question involves the epi-
demic threshold: how virulent must malicious code be to create an
endemic infection amongst the mobile devices? More specifically,
given values for
a
,
N
,
v
min
,
v
max
, and
r
, what values of
¯
and
±
lead to persistent global infections?
The standard Kephart-White model predicts endemic infection
when
¯hki>±
; in other words, epidemics occur when the infec-
tion pressure overwhelms the cure pressure. As shown in Figure 2,
this epidemic threshold is not always accurate in mobile networks.
The key problem is that the KW threshold ignores mobility and
thus misses the impact of node speed on infection dynamics.
To remedy this problem, we must explicitly consider the connec-
tivity fluctuations induced by mobility. Consider a particular node
traveling in an arena containing many other nodes.
E{T}
repre-
sents the expected time that it takes the node to travel between two
waypoints. The line segment between consecutive waypoints can
be conceptualized as a queue or pipe which takes
E{T}
seconds to
traverse. Using Equation 10, we can determine the expected per-
centage of queue time that is spent with a given number of neigh-
bors. More specifically, for
E{T}¤Pr
(
k
=0)
time units, the
node has no neighbors and is only subject to curing attempts
1
. For
E{T}¤Pr
(
k
=(
k
i
>
0))
time units, the node is subjected to in-
fection pressure proportional to
¯k
i
and cure pressure proportional
to
±
. If the cumulative infection pressure in a queue is greater than
the cumulative cure pressure, the node will likely be sick for the
majority of its queue time, and it will be capable of infecting its
neighbors for the majority of its queue time. Conversely, if the
cumulative infection pressure is less than the cumulative cure pres-
sure, we expect the node to spend the majority of its queue time in
a healthy state.
These observations suggest that for an epidemic to occur in a
mobile network, the following condition must be true:
E{L}
=0
.
5214
a
(4)
and the average time needed to complete such a trip is:
E{T}
=
ln
(
v
max
/v
min
)
v
max
−v
min
E{L}
+
t
pause
(5)
Allowing
p
p
=
t
pause
E{T}
, the spatial distribution function over
−a/
2
·
x,y·a/
2
is:
a
6
(
x
2
−
a
2
4
)(
y
2
−
a
2
sdf
(
x,y
)
¼
p
p
a
2
+(1
−p
p
)
36
4
)
(6)
Examples of this function are depicted in Figure 1. Given that a
node is at some location
(
x
i
,y
i
)
, the probability that it is within
communication range of another random node is:
N−
1
X
Z
x
i
+
p
r
2
−
(
y−y
i
)
2
Z
y
i
+
r
¯k
i
Pr
(
k
=
k
i
)
E{T}>c±E{T}
(11)
p
r
2
−
(
y−y
i
)
2
sdf
(
x,y
)
dxdy
(7)
where
r
is the communication radius of a wireless radio and is
the same for all nodes.
c
(
x
i
,y
i
)=
k
i
=0
y
i
−r
x
i
−
1
Note that
E{T}
must be expressed in terms of the viral time scale.
For example, if the infection and cure probabilities are defined over
100 millisecond intervals, then
E{T}
must be expressed in units of
100 milliseconds.
The average probability over the entire
where the left-hand side represents the infection pressure over a
travel segment and the right-hand side represents the cure pressure.
The small constant
c
accounts for stochastic fluctuations in global
connectivity. Since node movement is random and uncoordinated,
there will be punctuated periods of time during which most nodes
have very few neighbors or none at all. For an epidemic to persist,
the virus must be strong enough to ensure that a critical mass of
diseased nodes will emerge from such periods with their infections
intact. In Section 4.1, we empirically observe that
c¼
3
.
5
for
random waypoint networks.
Reconsider our examples of
net
slow
and
net
fast
. Although both
networks have the same connectivity distribution,
net
slow
has a
larger
E{T}
than
net
fast
and thus longer travel queues. Now we
can capture the fact that, for a given connectivity level, nodes in
net
slow
have this level for a longer absolute time period per seg-
ment traversal.
3.3 Making Steady-State Predictions
Having established an epidemic threshold condition for mobile
networks, our next task is to predict what the endemic infection
level will be. More specifically, given a virus profile (
¯
,
±
) and
mobility parameters
a
,
N
,
v
min
,
v
max
, and
r
, what is the global
steady-state infection level?
To answer this question, we extend the concept of travel queues.
In the previous section, we investigated the behavior of an indi-
vidual node. To travel between two waypoints, the node entered
a queue at some time
t
and exited the queue at time
t
+
E{T}
.
Using the connectivity distribution generated by Equation 10, we
considered the fraction of
E{T}
that was devoted to a particular
connectivity level. However, we can interpret the connectivity dis-
tribution in an alternate way, using it to tell us the global percent-
age of nodes having a given connectivity level at an arbitrary mo-
ment. From this perspective, there are
N¤Pr
(
k
=
k
i
)
nodes with
connectivity
k
i
at any given time. If we make the simplifying as-
sumption that the uninterrupted stretches of time that a node has a
particular connectivity level are large relative to the viral
¢
t
, we
can model the mobile network as a set of
N
queues. Each queue
Q
k
i
contains
N¤Pr
(
k
=
k
i
)
nodes. Upon entering
Q
k
i
, a node
spends
E{T}¤Pr
(
k
=
k
i
)
time units in it before exiting.
Epidemiologically, we treat each queue as a separate Kephart-
White population described by the global (
¯
,
±
) and a local
hki
equal to
k
i
. Such assumptions of local connectivity homogeneity
are intuitively justifiable—if a mobile node has
k
i
neighbors, many
of these neighbors are likely to be in communication range with
each other and have roughly
k
i
neighbors as well. The connec-
tivity distribution from Equation 10 tells us both the size of these
“neighborhoods” and the length of time that a node stays in each
neighborhood.
To initialize the queuing model, we set the integer system time
to 0 and insert
N¤Pr
(
k
=
k
i
)
nodes into each
Q
k
i
. We stamp
each queue’s initial node set with an exit time of
E{T}¤Pr
(
k
=
k
i
)
. Each queue’s infection level is then set to some
I
initial
2
[0
.
0
,
1
.
0]
. After this initialization, we iteratively update the system
clock in increments of the viral
¢
t
, performing two tasks after each
update. First, we simulate Kephart-White dynamics in each queue,
such that
dI
Q
k
i
/dt
=
¯k
i
I
Q
k
i
(1
−I
Q
k
i
)
−±I
Q
k
i
. Second, we
check whether any node sets have exit times less than or equal to the
current time. If so, we remove the node set from its queue, divide
it into
N
equally sized pieces, and enqueue one of these pieces into
each
Q
k
i
. Finally, each queue updates its infected percentage
I
Q
k
i
to reflect its newly enlarged population and the infection percent-
age of the just-enqueued nodes. At any moment, the global number
This is the steady state of a probabilistic queuing system for
N
=60,
a
=1000,
r
=100,
v2
[5
,
20]
,
¯
=0.7, and
±
=0.25. The number of
squares in a queue corresponds to the number of nodes it contains.
The proportion of dark squares to light squares represents the ratio
of infected nodes to healthy nodes in the queue. For example,
Q
k
=0
stores 15.86 nodes, of which 0.39 are infected;
Q
k
=7
only stores
1.59 nodes, but 1.41 of them are infected. The global number of
infected nodes is the sum of the infected count in each queue. In
this example, 37.57 out of 60 nodes are infected.
Figure 5: Modeling epidemics using probabilistic queues
of infected nodes is equal to
P
N−
1
k
i
=0
[[
I
Q
k
i
]
¤
[
Q
k
i
.length
]]
. To
predict the steady state infection percentage, we simply iterate the
queue maintenance algorithm until the global number of infected
nodes has stabilized. Figure 5 provides a visual depiction of a prob-
abilistic queuing system.
Although we partition dequeued node sets into equally sized
pieces, each piece will spend a different time waiting in its next
queue. Since the time spent in
Q
k
i
is proportional to
Pr
(
k
=
k
i
)
, our partitioning scheme simulates the effects of mobility and
non-homogeneous connectivity distributions. For very large
k
i
,
E{T}¤Pr
(
k
=
k
i
)
may be shorter than the viral timescale, i.e.,
nodes pushed into such queues should stay in the queues for less
than the viral
¢
t
. Since the maintenance algorithm steps in incre-
ments of
¢
t
, it cannot accurately model such queues. Thus, we
collapse the queues for such large
k
high
1
,k
high
2
...,k
N−
1
into a
single queue whose connectivity is the average of these values and
whose traversal time is
[
E{T}¤Pr
(
k¸k
high
1
)]
>
¢
t
.
4. EVALUATION
To evaluate probabilistic queuing and the KW model in mobile
environments, we wrote a custom simulator which gave us fine-
grained control over mobility parameters and viral profiles. Each
simulation took place in a square arena with 1000 meter sides. Un-
less otherwise noted, node movement was guided by the random
waypoint model. To emphasize the impact of mobility on viral
propagation, we typically used pause times of zero. Each mobile
device had a 100 meter communication radius, which corresponds
to the range of a Class 1 Bluetooth radio. The simulator did not
model path effects or transmission interference. For each (
¯,±
)
pair, the viral
¢
t
was 100 milliseconds. In the figures presented
in this section, each simulation result represents the average of five
trials. Each trial ran for a maximum of 200,000 virtual seconds, ter-
[ Pobierz całość w formacie PDF ]