Franz Steinparz
Alive Vol I, Issue 0
October 1991
This paper shows that Cohen's Theorem, stating the undecidability of viral detection does not hold. It is shown that each algorithm discerning a virus from other program by examining its code must be a virus itself.
Keywords: computer viruses
In [2] Cohen introduces Computer Viruses and summarizes some work he did on this topic. Aside other results of his work, he gives a rather informal definition of Computer Viruses and the proof of his well known theorem stating that a program discerning a virus from any other program by examining its appearance is infeasible. In [1] Burger expressed his doubt about this theorem. However, to our knowledge, no fault in Cohen's proof has been published, and in discussions about viruses, the theorem is widely ([3], [4], [5] and others) referred to.
Cohen's Theorem:
In Section 2 of [2] Cohen defines:
"..a computer virus as a program that can 'infect' other programs by modifying them to include a possibly evolved copy of itself."
In Section 4.1. of [2] Cohen states the undecidability of viral detection. His proof follows a well known proof technique. He argues:
"In order to determine that a given program 'P' is a virus, it must be determined that P infects other programs. This is undecidable since P could invoke any proposed decision procedure 'D' and infect other programs if and only if D determines that P is not a virus. We conclude that a program that precisely discerns a virus from any other program by examining its appearance is infeasible. In the following ... program ..., we use the hypothetical decision procedure D which returns "true" if its argument is a virus to exemplify the undecidability of viral detection.
....., we have assured that, if the decision procedure D determines (the following program contradictory-virus) CV to be a virus, CV will not infect other programs and thus will not act as a virus. If D determines that CV is not a virus, CV will infect other programs and thus be a virus. Therefore, the hypothetical decision procedure D is self contradictory, and precise determination of a virus by its appearance is undecidable.
program contradictory-virus := {.... main-program := {if D(contradictory-virus) then {infect-executable; if trigger-pulled then do-damage; } goto next; } }Fig..Contradiction of decidability of a virus.."
First, we notice an inaccuracy in Cohen's paper in defining a virus as a program, which can infect other programs and using this term in his proof for a program which actually does it. However, this inaccuracy can be corrected by adjusting the definition.
But even if we adjust the definition, the proof in its generality is wrong: It is based on the implicit assumption that the decision procedure D is not a virus itself.
Suppose the decision procedure D is a virus itself. Then contradictory-virus infects an executable by calling D and consequently is a virus too. Now D, when deciding that contradictory-virus is a virus, gives a correct result even if contradictory-virus, based on D's decision does not execute its own viral code.
However, under the restriction, that only non-virus decision procedures are permitted, Cohen's proof holds. Consequently, each decision procedure D must be a virus.