| This dissertation demonstrates that it is possible to learn a finite state automata representation of program behavior, without the state explosion that had been feared by some when learning a real program's behavior. The resulting representation can be used to monitor program behavior for intrusions. When used for intrusion detection, the representation is shown to produce few false positives while detecting most program abuses. The representation is small, the monitoring has little overhead, and detection is immediate, so the approach is an ideal candidate for implementation as a real-time intrusion detection system. If implemented properly, such a system could prevent unexpected actions (so that it could be used for sand boxing) or increase monitoring of the suspect process and user for later analysis (for use in forensics).; An algorithm is introduced that efficiently learns this representation from examples of program behavior. This algorithm is shown to have a number of properties that make it appropriate for this task. Unlike many techniques for learning finite automata, it is efficient in terms of the memory used. The number of false positives never increases with additional training and training can be continued even after on-line use for intrusion detection. In particular, if there is a false positive, the representation can learn to accept that run (and ones like it) in the future without negatively impacting the performance on other runs.; Heuristics are explored based on common programming techniques. These are shown to yield improvements in the finite automata generated by the algorithm, and therefore improvements in intrusion detection performance.; Experimentation has shown that all programs tried to date can be approximated using the techniques described in this dissertation. The approach has been tested on three datasets, allowing for a better understanding of the learning algorithm, how the parameters affect performance, and the influence of the heuristics. The results indicate the promise of the approach, which is the first intrusion detection technique that can immediately detect novel attacks as they occur, without manual specification of program behavior or attack signatures. |
