crocker@TIS.COM (11/12/89)
In VIRUS-L Digest Thursday, 9 Nov 1989 Volume 2 : Issue 237,
Peter Day writes
`A note to the virus-l digest of 6-Nov-89 said that "the virus
problem (at least detection anyway) is undecidable." Does
anyone know if there are any papers where this result is
proved? Or where the problem is shown to not be NP complete?
Or even where the problem is stated precisely?'
There are two parts to this question. First, precisely what is a
virus and second, how hard is it computationally to determine whether
a candidate program contains a virus. Precise specification of
viruses is an open-ended discussion, but almost any reasonable
definition will lead to the same conclusion. For the sake of this
discussion, let's agree that a virus modifies something it shouldn't.
(A program which makes undesired modifications does not necessarily
contain a virus, but all viruses make undesired modifications.)
Determining whether a program makes undesired modifications is
equivalent to determining whether it ever computes a particular
result, which is equivalent to the halting problem. Hence
determination of the presence of a virus is undecidable. This is not
a formal proof, of course, but a student in a first course in formal
systems ought to be able to supply the necessary framework and details.
Undecidability is unfortunate, but not the end of the world.
Approximate virus detectors are entirely feasible. The undecidability
result simply guarantees that any detector must err sometimes. It may
err by failing to find some viruses, or it may err by falsely finding
viruses where they aren't. (Or it can hang up in a loop and never
terminate.) Most virus-finding programs in use today err on the side
of missing some viruses. Maria Pozzo and I are conducting research
along the alternate line. (See our paper in the 1989 IEEE Symposium
on Security and Privacy, Oakland, CA, if you want further details.)
Steve Crocker