[ Pobierz całość w formacie PDF ]
Computers & Security, 11 (1992) 641-652
A Formal Definition
of Computer Worms
and Some Related
Results
F. 6. Cohen*
ASP,P.O.Box81270,Pitt.sburgh,PA1521?,
USA
lack of an adequate
and
standard
definition
of
In this
paper,
we
propose
a formal
definition
of ‘computer
worms”
and
discuss
some
of
their
properties.
We
begin
by
worms has created numerous misinterpretations
and wasted time, and few of the results on worms
have gone
reviewing
the
formal
definition
of
“computer
viruses”,
and
their
properties.
We
then
define
“computer
worms”
as a
sub-
beyond
the speculative
phase. In this
class of viruses,
and
show
that
many
of the interesting
ptop-
paper, we address this problem.
erties
derived
for
viruses
hold
for
worms.
Finally,
we
summarize
results,
draw
conclusions,
and
propose
further
We
begin
here
with
an informal
discussion
by
work.
presenting
a pseudo-code
example of a very simple
Keywords: Computer
viruses,
Computer
worms.
virus:
v: =
[F = RANDOM-FILE-NAME;
COPY v
TO F;]
1. Background
A
n informal
definition
of “computer
viruses”
This virus simply replicates into files with random
names, and is unlikely to be successful in any
current computing environment because the
chances are very poor that any of the replicas will
ever be run. Even if they were run, they would not
perform the functions the programs they replaced
performed prior to replication, and thus would be
rapidly detected. Since these replicas are of no
practical value, they would likely be destroyed.
More purposeful viruses, both malicious and
benevolent, have been shown to be quite powerful,
primarily due to their prodigious reliability and
ability to spread. Viruses have also caused quite a
problem in some environments.
Cohen [l], and
definition first
published in
1985 [2]
based on Turing’s model of
computation [3]. An alternative formal definition
was proposed by Adleman
[4]
in
1989
based on set
theory. In each of these cases, detection
was first published in
1984
b
was soon followed
by his forma r
of viruses
was shown
to be undecidable,
and several other
results were derived.
These definitions were quite general in scope, and
covered a broad range of replicating programs,
possibly including the as yet only poorly defined,
but widely used term *worm”. Unfortunately,
the
The
first published
scientific
references
to com-
puter
worms
that
we are aware
of came
from
*Funded
by ASP, P.O. Box 81270.
Pittsburgh,
PA 152 17, USA.
0167-4048/92/$5.00
0 1992, Elsevier Science Publishers Ltd.
641
E B. Cohen/A Formal Definition of Computer Worms
Shoch and Hupp [S], who described several experi-
ments with
which, in certain environments, replicates and
carries along the contents of the entire disk on
which it resides; product installation programs,
which replicate as part of their installation process;
and backup programs which make copies of them-
selves
rograms which replicated segments of
themselves or parallel processing over a network.
Unfortunately, no formal definition followed, and
no sample code was provided. This left an unfilled
void, and a host of informal but widely varying
discussions using the poorly defined term followed
in the literature.
4
and
other
programs
on
other
media
to
improve system reliability.
Another interesting feature of self-replicating pro-
grams is their resilience. In environments where
non-replicating programs often fail or are destroyed
through errors or omissions, viruses seem to thrive.
This is because of the natural redundancy
Recently, the term “worm” has been widely used to
describe programs that automatically replicate and
initialize interpretation of their replicas.’ By
contrast, the definition of viruses covers all self-
replicating programs but does not address the
manner in which replicas may be actuated. Here is
a pseudo-code
provided
by replication.
In this environment,
viruses seem to
be more fit than non-viral
programs.
example of a simple worm:
From a protection
standpoint,
viruses offer unique
problems. Their
resilience
makes then very hard to
W: =
[F = F&DO~~-FILE-NAME;C~IY
W
TO F;RUN
F;]
remove
from
an
operating
environment,
while
their transitive
spread bypasses most modern
pro-
With the ability to replicate comes a host of other
issues. The most obvious issue is that a replicating
program might exhaust all of the available
resources in a system, thus causing a system failure.
In
tection
methods.
General-purpose
detection
is
undecidable
[
1,2,
41,
while
special-purpose
methods
are not cost effective
[o]. There
are many
other
the
case
of
this
worm
in
a
uniprocessing
interesting
properties
of self-replicating
programs.
environment,
the system eternally
runs replicas
of
We
refer
the
interested
reader
to some
of
the
the worm,
and no other processing
can take place
recent literature
in this area
[6].
while
the
worm
runs.
In
a
multiprocessing
In the remainder
of this paper, we will formalize
environment,
well-designed
worms may be able to
the notion
of worms,
describe
how that formal-
coexist
safely
with
other
programs
if
they
are
ism leads very quickly
to a series of conclusions
limited
in their replication
and evolution
so as not
about
worm
properties,
show
how
these
results
to seriously impact performance.
impact
multiprocessing
and
multiprocessor
Another important aspect of viruses is their ability
to “carry” additional code with them. For example,
in the 1984 paper [l], pseudo-code was provided
for a compression virus, a denial of services virus,
and other examples.
environments,
discuss some
of the potentials
for
both malicious
and benevolent
worms,
describe
a
number
of historical
incidents,
summarize
results,
draw conclusions,
and propose further work
The
early worm
experiments
51 solved large problems
by including
subprob-
2.
Some Formalities
I
ems in replicas,
thus allowing
them to solve parts
Cohen [2] presents “Viral Sets” in terms of a set of
“histories” with respect to a given machine. A viral
set is a set of symbol sequences which, when inter-
preted, causes one or more elements
of the problem
using remote resources. More com-
monly
used viruses
include
the
‘diskcopy”
pro-
gram
provided
with
the
DOS
operating
system,
of the viral set
to be written
elsewhere
on the machine
in all of
‘This
idea
was
first
brought
to
my
attention
in
a
paper
the
histories
followin
the
interpretation.
We
published
in Computers
and
Security
in which
Thomas
A. Long-
include
here
some
o
B
the
relevant
definitions
staff and E. Eugene
Schultz
describe
several
Lwormsn.
642
Computer and Security, Vol. 11, No. 7
NM:
SMxIM+S,w 4,:
WG-+d)
M:(s~,
0,:
sMxIM-IM,
I~,
Jv=jo...
a}
“natural”
numbers)
positive
“integers”)
Y={l...=J}
states)
&={s
O,...JnI,
nfE.9
IM={i,,...,ij},
jE#
tape symbols)
where:
head motions)
d={-l,O,
+1}
S,:Af/l/-S,
¦
state over time)
,:&-xJv-+I,
tape contents
over time)
PM:JVN-N
(current
A!
cell at each time)
Box 1
I
[vcI*] Ufld
[ME&]
U#d
VOE
TnJHV&
jEJ
v]*
[[P!=j]
d
[S,=&] d
(‘I,j,...,‘i,,+~“~-I)=
3v’E
V,
3t’, t”,
j'%V
and
t’> t
(1)
(4
(3)
0r[(j+I4>~j’]l and
[[(j'+I4)Gj]
[(ql+‘P
I’Jy”f(-,)= v’] and
[3t”[t<r”<t’]
and
[P,.Ej',...,j'+Iv'I-
l]]
Box 2
required
for
the
remainder
of the
paper,
starting
M is halted
at time
twV’t’>
t, H,=
H,f, (t,t’~N);
with
the definition
of a set of Turing-like
[3] com-
puting
machines
“L# * as in Box
1.
that
HIM
is given
The
“history”
of
the
machine
by
M haltso3tE.&‘,
M is halted
at time
1;
0,
P),2
the
“initial
state”
is
described
by
07
¦
g9
,, PO), and
the
set of possible
AZ tape
sub-
that
p “runs”
at time
t-the
“initial
state”
occurs
at
¦
by
I*.
We say that;
sequences
is designated
when
PC, is such
that
p appears
,.,,“; and
that
p
runs@%EN,
p
runs
at
time
t. The
formal
set
( W)
is
given
of
the
viral
definition
in Box
2.
“For
convenience, we drop the
M
subscript when we are deal-
ing with a single machine
except at the first definition
of each
term.
is referred
co [2] for details.
The
interested
reader
643
17B. Cohen/A Formal Definition of Computer Worms
3. Definition of Computer Worms
We
define a “Worm
Set” w
as a viral set in which any worm (w) that is run at some move
i
results in a
worm
w’ being run at some subsequent
time
i’ (Box i).
’
VMVW(M,
W)EW-
[WI*] and [ME&q and
VWE WVHVC,jE.N
[[pl=j ] and[sl=sCJ]and
(‘l,j,‘..rOr.j+lw(-l)=
w]*
3w’E W3t’, t”, l”‘,j’EJV,f’>
I
0)
(2)
(3)
(4)
[[(j’+ Iw’I)q]
or
[(i+ M)q’]]
md
[(ot,;+.,
,~,j~+iru’i_,)=W’]
Und
W[t<r”<t’]
und[P,~Ej’,...,j’+Iw’(--l]
and
3t”‘[C’< t”‘] and [Pp
=j’]
and [Sp = So]
Box 3
Translated
into English, this means (approximately):
(M, W) is a “worm set” if and only if:
all worms in W are AZ sequences
-and-
M
is a A? -and-
for each worm
w in W, for all histories
of
M,
for all times t and
cells j
if the tape head is in front of cell j at time t -and-
A is in its initial state at time t -and-
the tape cells starting at j hold the worm w -then-
there is a worm w
’
in I+‘, a time t’ > t, and
place j
’
such that
(1)
at a place j
’
not overlapping worm w
(2) the tape cells starting at cell j
’
hold worm
w
’
-and-
(3) at time t” between t and t’, worm w’ is written by
M
-and-
(4) at some later time t”‘, worm w’ is run by
M
The definition of W is different from that of W
only in condition 4 being added, and because this
term is an “and” on the right side of an implica-
tion,
proofs about viruses [2] were not only viruses but
also worms by the present definition, and thus
the proofs apply directly. The remaining proofs
do not depend on the lack of condition 4 above,
and thus most of them arc also true for worms.
For the purpose of brevity, we list some of the
useful results for viruses that also hold for worms,
along with page numbers
WCW.
We
normally
refer
to elements
of
V,(M, V)E
Y
for a given machine
M as
“viruses”
on
M,
and in the same parlance
we will refer
to
of
W,(M,
W)E
W
for a given machine
members
M
as “worms”
on
M.
We
typically
drop the “on
M”
from the cited work:3
when we are referring
to a particular
M,
and make
statements like “all worms are viruses”.
‘Some
of these
require
a trivial
modification
to the sample
M
so
that
instead
of halting
after
replicarion,
M moves
the
tape
It turns
out that most
of the examples
used for
head
to rhe start
of the replica
and changes
to state S,,.
644
Computer and Security, Vol. 7I, No. 7
Theorem
A union of Ws is a W.
1
PI2
Lemma
3 “largest” W for any machine
M.
1.1
P13
Theorem
2
3
%mallestn Ws (
Wmin)
for some M.
P’4
3 Wminof every size iE9
for a universal ./%.
Theorem
3
P14
Theorem
4
There are uncountable
Ws
for some
M.
PI9
Theorem
5
Every sequence of symbols is a worm on some
M.
P21
Theorem
6
Worm
detection
is undecidable.
P23
Lemma 6.1
Detecting
evolutions
of a known worm is undecidable.
P25
Theorem
7
Worm
evolution
is as general as .& computation.
P26
Another
interesting
result of this definition
is that
is true for all time
t’ > t. By condition
3 of the
once
a worm
runs,
M
can
never
halt!
More
definition:
formally:4
VtEN,
2” > t: [& = So]
and If” > t: P,. # P,
Theorem
A:
so by definition, VH,M is not halted at time t, or in
other words,
M
never halts. Thus a system running
a worm has the “liveliness” property.
Vw E
W,(M, W)
C
W, w
runs =+
M
never halts.
This is because at all times after w runs, there
is always another WE W that must run at a sub-
sequent time. More formally, assume 3wG
W,(M,
W)C
W
and w is run at time t. Then by condition
4 in the definition:
Lemma A.
1:
VwE
W’,(M,W)E
W,
M
halts*jtEN,
w runs at
time t.
4.
Multiprocessing
Environments
31”’> t:[J+
=j ‘1 and [S,. = S”]
In a multiprocessing environment, worms are quite
different than in a uniprocessing environment. For
example, in a multiprocessing environment, a
worm need not dominate processing. With proper
controls on replication, a stable system can be put
in place to attain desirable levels of worm activity.
Here is a simple example in which a system func-
tion ok returns the number
and by condition
2 of the definition:
(o,.,,,, ,...) 0
t”‘.,‘+,lu’,-,)= w’
Thus w’ is run at time r”‘! But if any WE W is run
at any time t (specifically, w’ at time Y), we return
to the previous situation. By the induction
theorem, if a condition is true at some time 1 and if
being true at time t implies it is true at time
t +
1,
it
of currently
active
wk
worms:
‘We use letters for theorems and lemmas herein to avoid con-
flicts with the theorem numbering from cited works.
COPY W,TOFRUNFJF [Oh> @XT;]]
645
[ Pobierz całość w formacie PDF ]