🚀 go-pugleaf

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

> The picture of this process is a tree graph where each node is a
> mutation of the root with a theoretically unlimited number of
> children (You can just increase K to some arbitrary size when you
> wish to increase the number of mutations) each of which is itself a
> node with children and so on and so forth. Further more the graph
> does NOT have to be directed. It is possible for a child to produce
> its parent given the appropriate key. 

The graph obviously IS directed, with the different keys marking the
directed edges. You probably mean that the graph does not have to be a
TREE, i.e., there might be loops.

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

More exactly, the question is: given nodes VX and VY, it there a way
to determine whether a node VZ exists, from which there are paths to
both VX and VY?

> The application of this problem is obviously to polymorphic viruses.
> V() is the polymorphic virus function and K is whatever the virus is
> using to determine its next mutation. So if I have some known virus
> VX() and I scan the system, I can compare code against VX() and
> determine membership.

Also, it might be possible to apply the solution to the problem of
measuring polymorphism... For instance, polymorphism could be measured
as average length of the loops in the graph, or as average
"valentness" of the nodes, etc.

Regards,
Vesselin
- -- 
Vesselin Vladimirov Bontchev          Virus Test Center, University of Hamburg
Tel.:+49-40-54715-224, Fax: +49-40-54715-226      Fachbereich Informatik - AGN
< PGP 2.1 public key available on request. > Vogt-Koelln-Strasse 30, rm. 107 C
e-mail: bontchev@fbihh.informatik.uni-hamburg.de    D-2000 Hamburg 54, Germany