Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!rutgers!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw
From: T762102@DM0LRZ01.BITNET
Newsgroups: comp.virus
Subject: Re: virus scanning
Message-ID: <0010.9001171419.AA13242@ge.sei.cmu.edu>
Date: 17 Jan 90 08:07:00 GMT
Sender: Virus Discussion List <VIRUS-L@IBM1.CC.Lehigh.EDU>
Lines: 32
Approved: krvw@sei.cmu.edu

> I am told that in the November '89 issue of the American Mathematical
> Monthly, to the effect that no completely safe computer virus test is
> possible.  The proof is suppose to be short, and along the lines of
> the various proofs of the Halting problem.

Yes, the problem whether a program is a virus or not, is in general
undecidable. The (informal) proof follows:

Let's define a virus as a program which can infect other programs. (For a
more complete definition, see [1].) Let A(P) be an algorithm which applied
to the program P returns a boolean value (true when P is a virus and false
if it isn't). Now we can construct the program P1 in the following way:

        program P1;
        begin
                if A(P1)
                then (* do nothing *)
                else infect_other_programs;
        end.

In other words, if A reports that P1 is a virus, then P1 does not infect
programs, i.e. is not a virus. Otherwise (if A reports that P1 is not a
virus), P1 infects programs, i.e. it is a virus.

Therefore, A cannot decide whether P1 is a virus or not.
                                        Q.E.D.

                        Vesselin

[1] Cohen F., "Computer Viruses. Theory and Experiments", COMPUTER
    SECURITY: A Global Challenge, J.H. Finch and E.G. Dougall (eds.),
    Elsevier Science Publishers B.V. (North-Holland), 1984.