Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!usc!ucsd!ucselx.sdsu.edu!polyslo!vlsi3b15!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: gnf3e@uvacs.cs.Virginia.EDU (Greg Fife) Newsgroups: comp.virus Subject: Re: Virus Modeling Message-ID: <0002.9002051554.AA01695@ge.sei.cmu.edu> Date: 2 Feb 90 15:46:01 GMT Sender: Virus Discussion List Lines: 37 Approved: krvw@sei.cmu.edu 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. :-) You may need to add a few more states to better model the input devices and the clock. >(well the whole universe has a finite number of states >but we're getting way beyond anything of practical use). Yep. Greg Fife gnf3e@virginia.edu , virginia.bitnet uunet!virginia!uvacs!gnf3e