Path: utzoo!yunexus!lethe!torsqnt!jarvis.csri.toronto.edu!mailrus!wuarchive!udel!haven!mimsy!tank!eecae!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: crocker@TIS.COM Newsgroups: comp.virus Subject: Undecidability of virus detection Message-ID: <0008.8911161543.AA03334@ge.sei.cmu.edu> Date: 11 Nov 89 17:25:00 GMT Article-I.D.: ge.0008.8911161543.AA03334 Sender: Virus Discussion List Lines: 37 Approved: krvw@sei.cmu.edu 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