Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!usc!elroy.jpl.nasa.gov!jarthur!polyslo!vlsi3b15!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: USERGSVE@LNCC.BITNET (GEORGE SVETLICHNY) Newsgroups: comp.virus Subject: Re universal detectors. Message-ID: <0012.9002121648.AA15294@ge.sei.cmu.edu> Date: 10 Feb 90 03:39:54 GMT Sender: Virus Discussion List Lines: 63 Approved: krvw@sei.cmu.edu Enough has been said on this list to convince most people that a universal virus detector (UVD) is impossible, and I've given my own two cent's worth in favor of this position. If by "virus" we mean to include a whole range of "nasty" programs, then one also runs into problems of correctness of code and bugs, and gets tangled up in questions of human intent, which makes the discussion, though still mathematically viable, (given sufficient abstraction) rather trivial in the end. The answer is that no UVD exists. Even defining viruses as some types (not all) of "self-duplicating codes" and leaving trojans and other nasties aside will not improve the situation much, as one still faces quite general undecidability theorems. As I have tried to point out, almost any question about a program's performance is undecidable. In Virus-L v3, issue20 russ@Alliant.COM (Russell McFatter) argues that one should not try to determine what a program *will* do but what it *might* do and just not run those that might infect others. In principle this sounds like a good idea, since a-priori such a rephrasing of the problem could make it decidable. What makes it totally unviable is the present hardware (at least on PC-type machines, I'm not that familiar with Macs) as I tried to point out in Virus-L v3 issue22. Now there just _*MAY*_ (note the triple enphasis) be a theorem of the following type: I. Given such-and-such memory and microprocessor architecture, then any program containing a virus (however that is defined) will necessarily have a certain patern P in the object code. II. Any program that does not contain a virus can be written in a way that does not lead to pattern P in the object code. This would not conflict with the undecidability theorem since the presence of pattern P is not a UUV as having the pattern does not mean that the program *is* a virus, only that it *might be*. And part II allows any honest program to be written and not be dubbed dangerous. I'm actually mixing mathematics and technology in the above. The purely mathematical conjecture would be (having defined "virus" in some appropriate useful way): There is a decidable set W such that 1) all programs containing viruses are in W and 2) all programs that do not contain viruses *have an equivalent* (identical input-output behaviour) that is not in W. Program equivalence is undecidable so this does not contradict the undecidability of virus detection. The technological part would consiuAof expressing W in some convenient way through hardware architecture. Is this plausible? Frankly, it doesn't sound so to me, but I wouldn't discard it off hand. It's the only hope I see of some general mathematical result being useful for anti-viral strategies, so maybe we should look at it more closely. ---------------------------------------------------------------------- George Svetlichny | When it is not your mother who is Department of Mathematics | in danger of being eaten by a Pontificia Universidade Catolica | wild animal, the matter can wait Rio de Janeiro, Brasil | until the morrow. | usergsve@lncc.bitnet Fido 4:4/998 | Baganda Proverb ----------------------------------------------------------------------