William Dowling
American Mathematical Monthly, v.96 n.9, p.835-836, Nov. 1989.
ISSN 0002-9890
November 1989
Download PDF (208.72Kb) (You need to be registered on forum)This note gives a proof that no program can both test its input for the presence of a virus and simultaneously be guaranteed not to spread a virus itself. (You may define " virus" any way you please, as long as the definition is extensional.) This immediate corollary of Rice's Theorem [1] is proved by a direct diagonalization and offered as an antidote (not a vaccine) to boredom in the elementary computability course during the presentation of the halting problem.
Programs running on modern computers, unlike the executions of Turing machine programs, as usually conceived, run "in an environment." This is to say that when a program is executed, it is run as a subprogram of the logically independent program, the operating system, which is responsible for such bookkeeping chores as primary and secondary memory management, process management, recording statistics, and so on. A program that, when run, alters the code of the operating system, is called a virus. (When a new version of the operating system is written legitimately, it replaces, not alters, the former operating system.) This is a somewhat less restrictive definition of virus than others have proposed [2], in that no particular behavior is required of the modified operating system. For instance, it is frequently required that a virus have the effect of inserting its own code into other executable programs. Such restrictions are unnecessary for the result we seek.
It would be nice if we could detect automatically which programs are viruses and which are not by submitting them to a filter program, thus avoiding the expense and inconvenience of unwittingly and possibly harmfully altering our operating system. We now show there can be no program that does this correctly for every possible input, while guaranteed not to spread a virus itself.
We begin by fixing an operating system OS, and making a definition.
DEFINITION 1.
Program 
spreads a virus on input 
if running under operating system OS on input alters OS. Otherwise it is safe on input . A program is safe if it is safe for all inputs.
We also make the assumption that there exist viruses for OS, otherwise there would be no necessity for our test. Now for the sake of contradiction, let us assume there is some safe program 
that decides the safety of running an arbitrary program on arbitrary input . Thus
Given such a program and our assumption that there exist viruses, it is easy to write a program 
of one argument that has the following behavior:
We can now show that cannot be both safe and correct by examining the behavior of 
on input . If is safe on input this can only be because it has not executed the otherwise clause, that is, because 
thus showing that is not correct. On the other hand, if alters OS on input , there are two possibilities. On one hand, the call to 
may be returning "yes" so the otherwise clause in is being executed, in which case is not correct. On the other hand, if returns "no" (so simply prints "Have a nice day") the assumption that is unsafe on input means that the call to must be the culprit, that is, is not safe. We conclude that the assumption of the existence of a safe, correct program that runs on OS and checks the safety of its input must be incorrect; there can be no such program .