jer@ida.org (Eric Roskos) (01/12/90)
> I am told that in the November '89 issue of the American Mathematical > Monthly, to the effect that no completely safe computer virus test is > possible. The proof is suppose to be short, and along the lines of > the various proofs of the Halting problem. Of course. Just replace the "halt" instruction with a sequence of code to insert a virus (or to perform any malicious action). The approach to addressing the problem of viruses is not to automatically analyze code, but rather to prevent the propagation of viruses. This aside, turning to what I'd intended to say when I started this reply (I get easily sidetracked by computing theory :-)): > The Desktop Fractal Design System by Michael F. Barnsley, Iterated Systems, > Inc. (1989) is infected with a virus. This surprises me, since I bought a copy of this program at Reiter's Scientific Bookstore in Washington DC last November, and used it on my PC for a couple of days (before getting inspired by it to write my own programs... some of his algorithms he gives in the manual are really hard to figure out, since he's optimized them for integer arithmetic and he doesn't show all the simplifications he did, only the final result)... since then I have used the PC everyday, and have run one of the virus-checking programs on it several times, without any indication of a problem! Does anyone have details on which particular virus this is, or what is added to the end of the object files that one can check for? I'll run the virus-checking program on the disk itself this evening to make sure, but from the (very limited) evidence it looks like either not all the copies of the program are infected, or this is not one of the standard viruses.
T762102@DM0LRZ01.BITNET (01/17/90)
> I am told that in the November '89 issue of the American Mathematical > Monthly, to the effect that no completely safe computer virus test is > possible. The proof is suppose to be short, and along the lines of > the various proofs of the Halting problem. Yes, the problem whether a program is a virus or not, is in general undecidable. The (informal) proof follows: Let's define a virus as a program which can infect other programs. (For a more complete definition, see [1].) Let A(P) be an algorithm which applied to the program P returns a boolean value (true when P is a virus and false if it isn't). Now we can construct the program P1 in the following way: program P1; begin if A(P1) then (* do nothing *) else infect_other_programs; end. In other words, if A reports that P1 is a virus, then P1 does not infect programs, i.e. is not a virus. Otherwise (if A reports that P1 is not a virus), P1 infects programs, i.e. it is a virus. Therefore, A cannot decide whether P1 is a virus or not. Q.E.D. Vesselin [1] Cohen F., "Computer Viruses. Theory and Experiments", COMPUTER SECURITY: A Global Challenge, J.H. Finch and E.G. Dougall (eds.), Elsevier Science Publishers B.V. (North-Holland), 1984.