🚀 go-pugleaf

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