🚀 go-pugleaf

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?)