RWALLACE@vax1.tcd.ie (02/01/90)
Opitz@DOCKMASTER.ARPA writes: > A co-worker of mine wrote: > One way to characterize a Trojan Horse or a virus is to build > mathematical, abstract models of them. Such a model may be an > n-tuple of interrelated subjects, objects, and operations. > Thereafter, abstracted audit data and host machine > characteristics can be organized to find if all the components of > such an n-tuple are present. > > My assignment was to help with the research in attempting to come up > with such a model. Now, from what I have been reading on the Virus > forum, I am wondering if this task is even possible. > ... > Is it possible to come up with such a model? Is it possible to list > ALL of the characteristics of a virus? If so, what might these > characteristics be? If not, why not? > > David T. Opitz - NSCS I would estimate that such a program would be only slightly easier than a program to pass the Turing test. As someone pointed out, a real computer isn't a finite state machine because it includes the person operating it (well the whole universe has a finite number of states but we're getting way beyond anything of practical use). Therefore there is no universal algorithm for detecting viruses a priori. How about a non-universal algorighm that will detect a virus say 95% of the time? I don't think that's possible either. Consider possible countermeasures: The virus inspects a component of the operating system or hardware (e.g. checks if files of certain names are present, the files in question being essential components of the operating system), and uses the result to generate a 32-bit number which it then uses to decrypt a chunk of data which contains the infector code. It then executes the infector code. Even a brute-force inspect all possible execution paths approach won't work here because infection depends on things outside the program itself .. unless you're going to simulate the suspect program in a simulation of an entire machine which isn't very practical. Consider: even a good human hacker would have great difficulty finding a cunningly-hidden virus in a big program. You're going to need something pretty close to true AI. "To summarize the summary of the summary: people are a problem" Russell Wallace, Trinity College, Dublin VMS: rwallace@vax1.tcd.ie UNIX: rwallace@unix1.tcd.ie
gnf3e@uvacs.cs.Virginia.EDU (Greg Fife) (02/02/90)
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
rwallace@vax1.tcd.ie (02/08/90)
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