Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!uwm.edu!ux1.cso.uiuc.edu!tank!eecae!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw
From: kerchen@iris.ucdavis.edu (Paul Kerchen)
Newsgroups: comp.virus
Subject: Re: virus problem undecidability
Message-ID: <0012.8911101233.AA16030@ge.sei.cmu.edu>
Date: 9 Nov 89 23:09:50 GMT
Sender: Virus Discussion List <VIRUS-L@IBM1.CC.Lehigh.EDU>
Lines: 21
Approved: krvw@sei.cmu.edu

OSPWD@EMUVM1.BITNET (Peter W. Day) writes:
>A note to the virus-l digest of 6-Nov-89 said that "the virus problem (at
>least detection anyway) is undecidable."  Does anyone know if there are
>any papers where this result is proved? Or where the problem is
>shown to not be NP complete? Or even where the problem is stated
>precisely?

(Sorry about the mail loop, Peter)

I base my arguments upon Fred Cohen's paper "Computer Viruses: Theory
and Experiments," which can be found in _Computer Security: A Global
Challenge_ ( a collection of security-related papers).  In this paper,
Cohen talks about the undecidability of detecting viruses in a program
and proves why this is the case (although, purists wouldn't call it a
proof).

Paul Kerchen				| kerchen@iris.ucdavis.edu

[Ed. The cited Cohen paper was also published in the _Computers and
Security_ journal (though I don't have an issue number), as well as
directly from Dr. Cohen.]