home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / virus / 4959 < prev    next >
Encoding:
Internet Message Format  |  1993-01-23  |  2.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!cis.ohio-state.edu!news.sei.cmu.edu!cert!netnews.upenn.edu!netnews.cc.lehigh.edu!news
  2. From: bontchev@fbihh.informatik.uni-hamburg.de (Vesselin Bontchev)
  3. Newsgroups: comp.virus
  4. Subject: Re: Math Models of Polymorphic Viruses
  5. Message-ID: <0004.9301221631.AA12947@barnabas.cert.org>
  6. Date: 14 Jan 93 11:25:41 GMT
  7. Sender: virus-l@lehigh.edu
  8. Lines: 39
  9. Approved: news@netnews.cc.lehigh.edu
  10.  
  11. ygoland@edison.SEAS.UCLA.EDU (The Jester) writes:
  12.  
  13. > The picture of this process is a tree graph where each node is a
  14. > mutation of the root with a theoretically unlimited number of
  15. > children (You can just increase K to some arbitrary size when you
  16. > wish to increase the number of mutations) each of which is itself a
  17. > node with children and so on and so forth. Further more the graph
  18. > does NOT have to be directed. It is possible for a child to produce
  19. > its parent given the appropriate key. 
  20.  
  21. The graph obviously IS directed, with the different keys marking the
  22. directed edges. You probably mean that the graph does not have to be a
  23. TREE, i.e., there might be loops.
  24.  
  25. > The question is:Given functions VX() and VY(), can I determine if
  26. > they are both members of the same tree? Further, if this problem
  27.  
  28. More exactly, the question is: given nodes VX and VY, it there a way
  29. to determine whether a node VZ exists, from which there are paths to
  30. both VX and VY?
  31.  
  32. > The application of this problem is obviously to polymorphic viruses.
  33. > V() is the polymorphic virus function and K is whatever the virus is
  34. > using to determine its next mutation. So if I have some known virus
  35. > VX() and I scan the system, I can compare code against VX() and
  36. > determine membership.
  37.  
  38. Also, it might be possible to apply the solution to the problem of
  39. measuring polymorphism... For instance, polymorphism could be measured
  40. as average length of the loops in the graph, or as average
  41. "valentness" of the nodes, etc.
  42.  
  43. Regards,
  44. Vesselin
  45. - -- 
  46. Vesselin Vladimirov Bontchev          Virus Test Center, University of Hamburg
  47. Tel.:+49-40-54715-224, Fax: +49-40-54715-226      Fachbereich Informatik - AGN
  48. < PGP 2.1 public key available on request. > Vogt-Koelln-Strasse 30, rm. 107 C
  49. e-mail: bontchev@fbihh.informatik.uni-hamburg.de    D-2000 Hamburg 54, Germany
  50.