David_Conrad%Wayne-MTS@um.cc.umich.edu (02/21/90)
"David.M..Chess" <CHESS@YKTVMV.BITNET> writes: >> VDOS pseudo-executes the program, checking for >> every possible outcome and attempts to write to disk. > >Unlikely to be practical, I'm afraid? For instance, if the program >waits for user input, or looks at the time or date, or reads from a >file (I can't think of -any- program offhand that doesn't sometimes do >at least one of these), the pseudo-executor would have to >pseudo-execute a separate instance of the program for every possible >input/time/data-item. Not likely to finish within the life-expectancy >of the user! 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, so it would be necessary to rule out entire classes of operations where it is unacceptable for some parameters to be unknown (such as direct writes to the disk where the location to be written to is unknown). But many such activities would be 'suspicious' anyway. Another method of verification in which the values of data are unknown and which requires no seperate instances of a program is to examine the code as if all alternatives of a conditional structure are taken. Once again, it is necessary to rule out certain actions when data values are unknown. Remember, however, most instructions are not suspicious even when all parameters are unknown. Also, in conditionals in machine languages there are only two alternatives in a conditional branch (branch or don't!). Still, if one tried to simulate every possible path through any decently large program the number of instance doublings (every time there is a conditional jump you get two possible paths) would quickly eat up memory and it would take a *long* time. But since it isn't necessary to simulate every possible input, I think the simulation would terminate within the average user's lifetime. _________________________________________________________________ David Conrad BITNET: David_Conrad%Wayne-MTS@um.cc.umich.edu "He hates the sight of liquor. That's why he drinks so much. To get it out of sight quickly."
CHESS@YKTVMV.BITNET (David.M..Chess) (02/22/90)
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