Beckman@DOCKMASTER.ARPA (Joseph M. Beckman) (11/10/89)
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