Maximize
Bookmark

VX Heaven

Library Collection Sources Engines Constructors Simulators Utilities Links Forum

A comment on Cohen's theorem about undecidability of viral detection

Franz Steinparz
Alive Vol I, Issue 0
October 1991

[Back to index] [Comments]
Dr Franz X. Steinparz
Johannes Kepler University, Linz
October, 1991.

Abstract

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

Introduction

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.."

Discussion

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.

References

  1. R. Burger: Das Grosse Computer-Viren Buch, ISBN 3-89011-200-5, DATA BECKER, Duesseldorf, 1987.
  2. F. Cohen: Computer Viruses Theory and Experiments, Computers & Security 6 (1987) pp 22-35, North-Holland, 1987.
  3. G. Futschek: Computerviren fuer LOGO Programme Bauanleitung, Wirkungsweise und Abwehrmechanismen, interner Bericht, Technische Universitat Wien, 1988.
  4. F. Hoffmeister: Sicherheitsrisken durch Computerviren - erste Losungansatze, Bericht Nr. 232 der Abteilung Informatik der Universitat Dortmund, Dortmund, 1987.
  5. C.A. Neumann: Computerviren und verwandte Anomalien, GI Symposium "PC's in kleineren und mittleren Unternehmungen", Leipzig 17-19 September 1991., Tagungsbad der Fachgruppe 2.0.1. Personal Computing der GI, 1991.
By accessing, viewing, downloading or otherwise using this content you agree to be bound by the Terms of Use! vxer.org aka vx.netlux.org
deenesitfrplruua