Information Technology Reference
In-Depth Information
is true for all hosts
h
0
,h
1
,...,h
n−
1
for some
n
, and consider host
h
n
.Let
e
be the labeled infection edge coming into
h
n
whose label defines
S
(
b
)
(
h
n
), and
consider its manifestation
e
in
G
a
. By the construction of SPG's, an infection
edge may appear labeled in the SPG of one defense
D
u
and not another
D
v
if
its target
h
y
has a smaller value
C
(
h
y
)in
G
v
than in
G
u
,orif
G
v
is nullifying
and scans a countering host. In all cases the only way a labeled edge appears in
G
u
and not
G
v
is when
u<v
.Consequently
e
appears labeled in
G
a
.Thisin
turn implies that the node
h
m
from which
e
is directed satisfies
m<n
,asitis
directed from the same node in both
G
a
and
G
b
. By the induction hypothesis
S
(
a
)
(
h
m
)
S
(
b
)
(
h
m
), which implies that the label on
e
≤
is no larger than the
label on
e
, and thus, that
S
(
a
)
(
h
n
)
S
(
b
)
(
h
n
). A similar argument shows that
the labeled countering edge
g
which defines
C
(
a
)
(
h
n
) (when this exists) has a
labeled counter-part
g
≤
in
C
(
b
)
(
h
n
), whose label is no larger in
G
b
than it is in
G
a
, and thus that
C
(
b
)
(
h
n
)
C
(
a
)
(
h
n
). This completes the induction.
≤
From this result comes the main result.
Theorem 1.
For defense
D
i
and every time
t
,let
I
(
D
i
,t
)
denote the number
of hosts infected by time
t
(including those that later become nullified). Then for
a<b
,
I
(
D
a
,t
)
≥
st
I
(
D
b
,t
)
for every
t
≥
0
.
Proof.
Lemma 1 shows that for any sample path of scans and every time
t
,the
number of hosts
h
with
S
(
a
)
(
h
)
≤
t
is greater than or equal to the number of
hosts
h
with
S
(
b
)
(
h
)
t
. For any sample path these counts define the random
variables
I
(
D
a
,t
)and
I
(
D
b
,t
). Coupling results in [9] establish the result.
≤
These results show that the difference between defenses is structural, and
strong. The results are very general, free of distributional assumptions other
than independent of sampling from network state. However, they don't give
much insight into how well these defenses perform.
There is one exception, in the special case where the counter-worm has the
same scanning characteristics as the worm. Then we may assume that whenever
a host is entered either by a worm, or a counter-worm, its pattern of scans (inter-
scan delays, sequence of targets scanned) is the same under any defense. From
the point of view of the same path analysis we've done, it means that whenever a
node is triggered to scan we may assume it does so with exactly the same pattern
regardless of if that is an infection or countering scan. This means that any host
that scans in an empty defense also does so in a spreading patch defense, only
possibly earlier (if the scan is a countering scan).
These observations establish the theorem.
Theorem 2.
Suppose that the scanning structure of the counter-worm is iden-
tical to the worm. For every time
t
let
λ
(
D
0
,t
)
and
λ
(
D
2
,t
)
denote the instan-
taneous number of hosts scanning under the empty defense and spreading patch
defense, respectively. Then for every
t
,
λ
(
D
2
,t
)
≥
st
λ
(
D
0
,t
)
.
This theorem is a strong statement about a condition when adding defense is
worse, from the point of view of the network. Increasing functions of
λ
(
D, t
)in-
clude the peak number of hosts scanning over an interval, the space-time product
