Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!polyslo!vlsi3b15!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: crocker@TIS.COM Newsgroups: comp.virus Subject: Re: Universal virus detector Message-ID: <0006.9002121947.AA15751@ge.sei.cmu.edu> Date: 10 Feb 90 22:59:43 GMT Sender: Virus Discussion List Lines: 23 Approved: krvw@sei.cmu.edu Robert Eachus explained quite lucidly why there is no possibility of building a universal virus checker WHICH PERFECTLY DISTINGUSIHES BETWEEN VIRUSES AND NON-VIRUSES [emphasis mine]. As with most theoretically intractable problems, a slight change in the question leads to remarkably different results. For example, it's entirely feasible to build a virus checker which errs on the safe side and throws out some good programs as well as all bad programs. Whether this is useful depends on how many good programs it throws out. At the extreme, you can postulate it throwing out ALL programs. This is, of course, the easiest filter to build, but also the least useful, i.e. completely useless. A more interesting challenge is whether you can build a checker that permits a usefully large set of good programs to be executed while excluding all bad programs. A related question is whether it's possible to define programming standards whic facilitate the checking process. If such standards existed, the burden of proving that a program is virus-free would fall back on the writer of the program. Programs not meeting the criteria would be treated the same as virus-laden programs and prohibited from execution. Maria Pozzo is working in this area, and she and I published a paper at the IEEE Symposium on Privacy and Security last year. I also posted a description of the basic ideas some time ago. (Perhaps the editor would be kind enough to supply the volume and number?)