Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!uwm.edu!rutgers!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw
From: rwallace@vax1.tcd.ie
Newsgroups: comp.virus
Subject: Re: Virus Modeling
Message-ID: <0004.9002081228.AA07034@ge.sei.cmu.edu>
Date: 7 Feb 90 19:41:17 GMT
Sender: Virus Discussion List <VIRUS-L@IBM1.CC.Lehigh.EDU>
Lines: 44
Approved: krvw@sei.cmu.edu

gnf3e@uvacs.cs.Virginia.EDU (Greg Fife) writes:
> RWALLACE@vax1.tcd.ie writes:
>>                                        As someone pointed out, a real
>>computer isn't a finite state machine because it includes the person
>>operating it
>
> A human being may or may not be a finite state machine, but the
> effect he he has on a computer system is merely to add a finite
> number of transitions to the computer. (Striking one of the finite
> number of keys changes the interrupt state on a PC, putting in
> a new disk changes many of the bits on that mass storage device).
>
> You can't model exactly which inputs the human will provide, but
> you can reason about behavior under any possible set of inputs.
> In effect, a person at a computer is running a huge finite
> automata through an input string consisting of his actions.
>
> Take the initial state to be one of the finite number of
> states which represents the introduction of the virus into
> the system.  Mark the finite number of states which represent
> "infection" as final states.  The question: "can infection occur"
> is merely the question "does this FA have a nonempty language."
> That question can be settled in finite time by testing the FA
> on every input string of length less than or equal to the number
> of states in the FA.  Do this once for every initial "infection"
> state, and the result follows. :-)

Take a binary file editor. Or an interactive assembler. Or uudecode
reading from stdin. Any of these programs will take input from the
user and based on this input can reach most of the possible states of
the system, including those in which replication of the program can
occur. (I'm using "almost" in a loose sense: 2^990,000 is almost
2^1,000,000). So are these viruses? By your rationale they are. Or a
terminal emulator which based on input from the outside world could
cause infection (it could download an infected program from a bulletin
board). And what about a worm program that transmits itself to another
machine but does not infect other programs on the current machine?

Having said that, your method would be OK for most software, if you
only want to check for viruses not worms.

"To summarize the summary of the summary: people are a problem"
Russell Wallace, Trinity College, Dublin
rwallace@vax1.tcd.ie