[comp.virus] virus scanning

jer@ida.org (Eric Roskos) (01/12/90)

> 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.

Of course.  Just replace the "halt" instruction with a sequence of code
to insert a virus (or to perform any malicious action).

The approach to addressing the problem of viruses is not to automatically
analyze code, but rather to prevent the propagation of viruses.

This aside, turning to what I'd intended to say when I started this
reply (I get easily sidetracked by computing theory :-)):

> The Desktop Fractal Design System by Michael F. Barnsley, Iterated Systems,
> Inc. (1989) is infected with a virus.

This surprises me, since I bought a copy of this program at Reiter's
Scientific Bookstore in Washington DC last November, and used it on my
PC for a couple of days (before getting inspired by it to write my own
programs...  some of his algorithms he gives in the manual are really
hard to figure out, since he's optimized them for integer arithmetic and
he doesn't show all the simplifications he did, only the final
result)...  since then I have used the PC everyday, and have run one of
the virus-checking programs on it several times, without any indication
of a problem! Does anyone have details on which particular virus this
is, or what is added to the end of the object files that one can check
for? I'll run the virus-checking program on the disk itself this evening
to make sure, but from the (very limited) evidence it looks like either
not all the copies of the program are infected, or this is not one of
the standard viruses.

T762102@DM0LRZ01.BITNET (01/17/90)

> 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.