OSPWD%EMUVM1.BITNET@VMA.CC.CMU.EDU (Peter W. Day) (11/09/89)
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? Thanks, Peter Day Emory University
kerchen@iris.ucdavis.edu (Paul Kerchen) (11/10/89)
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.]