A fast automaton-based method for detecting anomalous program behaviors

Forrest et al introduced a new intrusion detection approach that identifies anomalous sequences of system calls executed by programs. Since their work, anomaly detection on system call sequences has become perhaps the most successful approach for detecting novel intrusions. A natural way for learning sequences is to use a finite-state automaton (FSA). However previous research seemed to indicate that FSA-learning is computationally expensive, that it cannot be completely automated or that the space usage of the FSA may be excessive, We present a new approach in this paper that overcomes these difficulties. Our approach builds a compact FSA in a fully automatic and efficient manner; without requiring access to source code for programs. The space requirements for the FSA is low - of the order of a few kilobytes for typical programs. The FSA uses only a constant time per system call during the learning as well as detection period. This factor leads to low overheads for intrusion detection. Unlike many of the previous techniques, our FSA-technique can capture both short term and long term temporal relationships among system calls, and thus perform more accurate detection. For instance, the FSA can capture common program structures such as branches, joins, loops etc. This enables our approach to generalize and predict future behaviors from past behaviors. For instance, if a program executed a loop once in an execution, the FSA approach can generalize and predict that the same loop may be executed zero or more times in subsequent executions. As a result, the training periods needed for our FSA based approach are shorter. Moreover false positives are reduced without increasing the likelihood of missing attacks. This paper describes our FSA based technique and presents a comprehensive experimental evaluation of the technique.