Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!jarthur!polyslo!vlsi3b15!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: CHESS@YKTVMV.BITNET (David.M..Chess) Newsgroups: comp.virus Subject: re: UVD Message-ID: <0002.9002231213.AA10580@ge.sei.cmu.edu> Date: 22 Feb 90 00:00:00 GMT Sender: Virus Discussion List Lines: 30 Approved: krvw@sei.cmu.edu David_Conrad%Wayne-MTS@um.cc.umich.edu writes, in response to my suggestion that a "pseudo-executor" would take lifetimes to run: > A seperate instance for every possible input? Nonsense. > All that is required is a seperate instance for every alternative > in a conditional structure. Of course, that can still require a > large number of instances, and some data will be undefined... Mea Culpa, at least partly. I was assuming the simplest possible implementation of the proposed "VDOS". A more sophisticated system like the one Mr. Conrad describes might well be able to pseudo-execute a typical program much more quickly (finishing in perhaps only a few years, or even months/weeks/days). I'd guess that it'd still be too long to be practical, but I've been wrong before! I also suspect that a sophisticated pseudo-executor would turn out to be (1) very hard to write, and (2) extremely useful for other purposes as well as virus-checking. I know various research groups (wish I had references handy!) have done considerable work on "symbolic execution" systems, which essentially take a program P as input, and (try to) produce as output a function that gives the output of P for given inputs to P. It's hard to do well, and I think still poses some unsolved problems. The virus-checking pseudo-executor has a somewhat easier job (it only has to answer "does the output of P include anything nefarious, for *any* value of the input?"), but I'm not sure if it can avoid the hardest problems. Interesting field for speculation! DC