🚀 go-pugleaf

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