NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/virus/4981

Internet Message Format | 1993-01-27 | 5.0 KB

Path: sparky!uunet!ukma!darwin.sura.net!newsserver.jvnc.net!netnews.upenn.edu!netnews.cc.lehigh.edu!news
From: [e-mail] (Y. Radai)
Newsgroups: comp.virus
Subject: Re: On the definition of viruses
Message-ID: <[e-mail]>
Date: 18 Jan 93 15:06:10 GMT
Sender: [e-mail]
Lines: 78
Approved: [e-mail]


  Albert Lunde writes:
> Fred Cohen can point with justified pride to the mathematical theory
> of viruses.  At the same time, I think it is perfectly understandable
> that people will use more relative, subjective critera based on a
> perception of risk and intention. This is especially the case since
> one of the consequences of the mathematical theory is a proof that a
> general "unknown virus" detector is impossible!

You don't need Fred's mathematical theory to show that.  It's also a
consequence of any reasonable informal (natural-language) definition
of "virus", as Fred himself has shown.  Since his informal proof has
been presented on Virus-L/comp.virus at least five times, I won't
bother restating it here.  However, I'd like to present an argument
which I thought of a couple of years ago, which demonstrates (at least
for all practical purposes) the undecidability of whether a given
program contains a virus, in a completely different way from Fred's
proof (the one based on the proof of the undecidability of the Halting
Problem on a Turing Machine), a way which seems to me far more intui-
tive, even if it's not quite as conclusive.
  Suppose a program contains code for replication, but only within a
statement of the form "If <condition> then <replicate>", where
<condition> is something which depends on the run-time environment,
e.g. on the input which a user supplies.  Can a detection program
discover whether the program actually does replicate?
  To illustrate the generality of the situation, I'll even offer a
choice between three reasonable informal definitions of "virus":
(a) a virus is a sequence of instructions which replicates on *every*
    execution;
(b) a virus is a sequence of instructions which replicates on *at
    least one* execution;
(c) A sequence of instructions is a virus in a given run-time environ-
    ment if and only if it replicates in that environment.
  If the decision is to be made by appearance of the program alone,
then the simplest case is (c), for suppose that the program asks the
user to supply two numbers, x and y, and <condition> is "x < y".  Then
it is completely obvious that fulfillment of this condition cannot be
determined without actually running the program, hence whether the
program is a virus is undecidable by appearance of the program alone.
Note that this argument does not require the assumption that the
computer has an infinite amount of storage, as Fred's proof does.
  If the definition is (a) or (b), then we can do even better: we can
show that in some cases the question cannot be decided even by running
the program any finite number of times.  For example, suppose the
program asks the user to input four positive integers i, j, k, n
(where n must be > 2).  If you choose definition (b), I shall take
<condition> to be "i^n + j^n = k^n".
  Now for all anyone knows, it may be that this condition is *never*
actually satisfied.  (The statement that there are no such integers is
Fermat's "Last Theorem", for which he *claimed* he had found a proof,
but he didn't produce it and no mathematician since him has found
either a proof or a counter example.)  Not only can we not decide this
by appearance of the program, but even if we run this program a zil-
lion times and the program doesn't replicate, that doesn't prove that
it can *never* replicate; all one can say is that the program hasn't
replicated *so far*.
  If you choose definition (a) instead, I take <condition> to be the
negation of the above statement, and the same argument works.
  In any case, there are some situations in which you can't decide
whether a given program is a virus.  We can substitute for Fermat's
Theorem any other unsolved problem.  If you could write a program
which could decide whether the resulting programs are viruses, then
you would become famous for having solved all the world's heretofore
unsolved problems!!  (Well, at least those which can be expressed by a
computer program.)  Thus it is intuitively clear that the property of
virality is undecidable, at least for all practical purposes.
  Of course, one can take the position that it's just an historical
accident that these problems have not yet been solved, and that in
principle they may all be solved some day.  However, it can be shown
that there are infinitely many problems which can *never* be solved
(although that apparently requires use of one of those "paradoxical"-
type proofs which I've been trying to avoid here).
  Comments are welcome (especially Fred's).

                                     Y. Radai
                                     Hebrew Univ. of Jerusalem, Israel
                                     [e-mail]
                                     [e-mail]