home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / virus / 4997 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  2.4 KB
  1. Path: sparky!uunet!ukma!cs.widener.edu!dsinc!netnews.upenn.edu!netnews.cc.lehigh.edu!news
  2. From: chess@watson.ibm.com (David M. Chess (863-6665))
  3. Newsgroups: comp.virus
  4. Subject: re: Math Models of Polymorphic Viruses
  5. Message-ID: <0001.9301281842.AA17847@barnabas.cert.org>
  6. Date: 18 Jan 93 20:54:41 GMT
  7. Sender: virus-l@lehigh.edu
  8. Lines: 39
  9. Approved: news@netnews.cc.lehigh.edu
  10.  
  11. >From:    ygoland@edison.SEAS.UCLA.EDU (The Jester)
  12.  
  13. >The question is:Given functions VX() and VY(), can I determine if
  14. >they are both members of the same tree?
  15.  
  16. Yes, you can: they are!  *8) Consider V0, where V0(V0,K) produces a
  17. completely random string of bytes, using K (derived from the current
  18. machine state, or whatever) as a key.  Any other VX and VY are in the
  19. tree leading from V0 (in fact, they're both on the very first level of
  20. the tree).  That's a limiting case, of course, and rather silly, in
  21. that most of the offspring of V0 aren't V's at all in any useful
  22. sense.  But clearly for any VX and VY you could write a V<X,Y> which
  23. produced either VX or VY depending on the parity of K.  So again any
  24. pair VX VY are in the same tree.
  25.  
  26. A related problem which doesn't have a trivial answer is something
  27. like: given VX and VY, is VY anywhere in the tree leading down from
  28. VX?  That is, is VY a descendant of VX?  For the VXs that are existing
  29. viruses, answering this question is trivial.  It's interesting to
  30. think about how hard the question can be (I mention this in passing in
  31. the beginning of my "Virus Verification and Removal..." paper, which I
  32. think is available on VIRUS-L).
  33.  
  34. In Hoffman's "Rogue Programs", there's a paper by Len Adleman called
  35. "An Abstract Theory of Computer Viruses".  It contains what seems to
  36. be a proof that it's possible to design a virus so that given one
  37. instance of an infected object, it's not decidable whether or not
  38. another object might be a descendant of it.  However, I don't
  39. understand the proof; I'd love to hear from someone that does!  The
  40. next proof in the paper softens the blow: it seems to be a proof that
  41. you can come close enough, by deciding whether or not another object
  42. is EITHER a descendant of the captured virus OR an element of the
  43. "germ set" for the virus, where the "germs" of a virus are the set
  44. (roughly) of droppers of the vius.
  45.  
  46. - - -- -
  47. David M. Chess                    \      Nothing moves;
  48. High Integrity Computing Lab      \         where would it go?
  49. IBM Watson Research               \
  50.