Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!uakari.primate.wisc.edu!unmvax!ncar!tank!eecae!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw
From: Beckman@DOCKMASTER.ARPA (Joseph M. Beckman)
Newsgroups: comp.virus
Subject: Undecidability
Message-ID: <0005.8911101233.AA16030@ge.sei.cmu.edu>
Date: 9 Nov 89 17:52:00 GMT
Sender: Virus Discussion List <VIRUS-L@IBM1.CC.Lehigh.EDU>
Lines: 21
Approved: krvw@sei.cmu.edu

The hypothesis of viral detection is that it is an undecidable task to
determine whether an arbitrary program on an arbitrary "machine"
contains a virus or not.  This does not mean the viral detection
question is undecidable.

First, one is primarily interested in a subclass of the question.  This
subclass is a Type II error, or false acceptance (saying a program is
virus free when it is not).  Crocker & Pozzo have argued that it is
feasible to create a filter which has a Type II error rate of 0.
Naturally, some programs without viruses are rejected by a filter of
this type.  See their paper in the 1989 IEEE Security & Privacy
Conference Proceedings.

Second, neither programs nor machines are arbitrary in the real world.
One can certainly think of machines (and then of programs running on
those machines) where it can be trivially and without error shown
whether a particular program is infected with a virus or not.

All of this assumes that one has a definition of "virus."

Joseph