🚀 go-pugleaf

>From:    ygoland@edison.SEAS.UCLA.EDU (The Jester)

>The question is:Given functions VX() and VY(), can I determine if
>they are both members of the same tree?

Yes, you can: they are!  *8) Consider V0, where V0(V0,K) produces a
completely random string of bytes, using K (derived from the current
machine state, or whatever) as a key.  Any other VX and VY are in the
tree leading from V0 (in fact, they're both on the very first level of
the tree).  That's a limiting case, of course, and rather silly, in
that most of the offspring of V0 aren't V's at all in any useful
sense.  But clearly for any VX and VY you could write a V<X,Y> which
produced either VX or VY depending on the parity of K.  So again any
pair VX VY are in the same tree.

A related problem which doesn't have a trivial answer is something
like: given VX and VY, is VY anywhere in the tree leading down from
VX?  That is, is VY a descendant of VX?  For the VXs that are existing
viruses, answering this question is trivial.  It's interesting to
think about how hard the question can be (I mention this in passing in
the beginning of my "Virus Verification and Removal..." paper, which I
think is available on VIRUS-L).

In Hoffman's "Rogue Programs", there's a paper by Len Adleman called
"An Abstract Theory of Computer Viruses".  It contains what seems to
be a proof that it's possible to design a virus so that given one
instance of an infected object, it's not decidable whether or not
another object might be a descendant of it.  However, I don't
understand the proof; I'd love to hear from someone that does!  The
next proof in the paper softens the blow: it seems to be a proof that
you can come close enough, by deciding whether or not another object
is EITHER a descendant of the captured virus OR an element of the
"germ set" for the virus, where the "germs" of a virus are the set
(roughly) of droppers of the vius.

- - -- -
David M. Chess                    \      Nothing moves;
High Integrity Computing Lab      \         where would it go?
IBM Watson Research               \