3.1- Kill SignalsIn all epidemiological models of which we are aware, an individual's cure takes place independently of that of any other individual. However, consider the following scenario. One day, Alice discovers that one of the programs she uses on her PC is infected with a virus. She eradicates it by any one of a number of procedures. In most models, this would be the end of the story. However, in this case Alice takes it upon herself to inform her friends Bob, Carol, and Dave, with whom she remembers having exchanged software sometime during the last few weeks. Bob already has a virus scanner, so he runs it and finds that, lo and behold, he has the virus, too. Carol and Dave install anti-virus software on their machines, whereupon Carol finds that she is infected, too. Fortunately for Dave, he turns out not to be infected. Bob and Carol, after cleaning up their PCs and diskettes, follow Alice's example and tell their friends, and the process continues until finally no one who receives the ``kill signal'' (the warning about possible viral infection) finds that they have the virus. Various assumptions can be made about how the kill signal works. If one assumes that the kill signal is delivered and acted upon much more rapidly than the virus can spread, it can be shown that the virus can be pushed below the epidemic threshold even if the infected individual only delivers the kill signal to a fraction of its associates.
Figure 2 summarizes the results of
nearly 200,000 simulation runs on random graphs of 100 nodes
with average degree 10 (i.e. on average, each node
had 10 neighbors). The ratio
Figure 2: Kill signals can be extremely effective, even when only a fraction of the neighbors of an infected node receive and heed them. Each point summarizes the result of 2500 simulation runs on random graphs of 100 nodes with average degree 10, and indicates the fraction of those runs which resulted in epidemics. The ratio  was 0.2.
What if the kill signal is not transmitted
instantaneously? One way to model this is to treat the kill
signal as an epi-epidemic -- a sort of anti-virus epidemic
of species K riding on the back of the virus epidemic (species V).
We can then assign the kill signal K its own intrinsic
``adequate contact'' and ``death''
rates. Specifically, a kill signal is born at a node whenever the virus
dies there. Adequate contact among nodes occurs at the rate
In a homogeneous system, deterministic analysis (valid for sufficiently large systems) leads to the following coupled pair of nonlinear differential equations:
Equation 1 can be solved numerically to yield v(t) and k(t), the fraction of nodes occupied by V and K, respectively.
Analysis of the solution shows that the epidemic threshold for the
virus is unaffected by the kill signal parameters;
it remains at
The kill signal parameters
Figure 3a illustrates the population dynamics of V and K
for a particular set of parameters for which V is above the epidemic threshold:
What is the effect of kill signals in non-homogeneous topologies?
In sparse topologies,
epidemics can be eliminated entirely, as illustrated by the simulation
run shown in Fig. 3b.
In this case, all parameters are the same
as in Fig. 3a, but the topology is a random
graph of 10,000 nodes with average degree 2.0.
After a short-lived growth spurt,
the virus population becomes extinct near t=16.4. Their supply of viruses
having run out, the kill signal population decays exponentially due to the
death rate
Figure 3: The effect of various topologies on the population dynamics of viruses and kill signals: a) homogeneous mixing model, b) 10000-node random graph with d=2.0, and c) 100-by-100 square lattice wrapped around to form a torus. The rates are  ,
 ,
 , and
 in all cases. The homogeneous mixing
curves are numerical solutions of a coupled pair of differential equations in which the
initial fractional populations of V and K were 0.0001 and 0.0, respectively.
The 2-D square lattice and random graph curves were obtained from typical simulation runs
in which initially just one node
(out of 10000 total) was occupied with V and none with K.
(Recall that a K is born whenever a V dies.)
In local topologies, kill signals introduce some interesting new effects.
Fig. 3c shows the populations of V and K for a typical simulation
run on a 100-by-100 square lattice (wrapped around in both dimensions to form a torus).
Each node (vertex) of the lattice is only able to infect its eight nearest neighbors.
Although the rates
These theoretical results on kill signals are exciting because they suggest a very cost-effective technique for thwarting viral spread. A number of different implementations can be considered, including user education (getting people to tell their friends if they discover a computer virus) and organizational policies which encourage users to report virus incidents to a central agency, which can then ensure that machines in the vicinity of the infected machine are scanned for viruses (and cleaned up if necessary). We are currently examining the feasibility of a technological implementation of kill signals for use in networks and other multi-user systems.
|
. Upon successful
receipt of the signal, an infected node would immediately
become cured and would instantly try to send a kill signal to
each of its neighbors. Any uninfected node would remain
uninfected, and would not send the signal on to its
neighbors. Given the relatively high degree of the graph and the random
nature of the connections, the homogeneous approximation gives a
good estimate of the epidemic probability when
:
. As the kill signal probability
, beyond which
the probability for there to be an epidemic drops abruptly to zero.
In other words, for these parameters, extinction of the virus
is inevitable if more than 2.5 or 3 out of a typical
node's 10 neighbors receive and heed the kill signal.
.
In order for adequate contact to result in infection by
a K, the intended victim must be infected with V.
In order to prevent the kill signal from
ricocheting around the system and using up computational resources
long after V has been eradicated,
we introduce a death rate
. The properties of V remain essentially the
same as in standard models; V can only infect nodes that are not infected
with K or with V.
.
The kill signal has no intrinsic epidemic threshold; it
can survive as long as there are viruses upon which to feed,
regardless of the relative values of
has a simple interpretation: each individual acquires permanent immunity
after exposure to and recovery from the virus V. The standard SIR models
of mathematical epidemiology (susceptible
infected
. In this case, K isn't really a signal passed
among neighboring nodes; it just
appears spontaneously whenever a node is cured of V and
remains there for eternity, protecting that node from infection by V.
In such models, the equilibrium virus population is always zero; the
question of interest is how many nodes ever become infected; this
is determined by the virus rates
and
[
, the kill signal becomes instantaneous.
If
limit in
the first kill-signal model.
,
but the life cycle of K is ten times slower than that of V. In the absence
of the kill signals, the fraction of nodes infected with the virus in equilibrium
would have been
in a D-dimensional lattice (t represents time). However, after a while,
large undamped oscillations develop in the populations of V and K, and they are
centered at a value which is substantially lower than in the homogeneous topology.
Large undamped oscillations are not peculiar to spatial topologies; simulations
on other topologies suggest that this phenomenon is generally characteristic of local topologies.
Locality
allows separate pockets of V and K to periodically develop, interact, separate,
and then interact again [