| Many host-based anomaly detection systems monitor a process by observing the system calls it makes, and comparing these calls to a model of normal behavior for the program that the process is executing. In this thesis we explore two novel approaches for constructing the normal behavior model for anomaly detection.; We introduce execution graph, which is the first model that both requires no static analysis of the program source or binary, and conforms to the control flow graph of the program. When used as the model in an anomaly detection system monitoring system calls, it (i) accepts only system call sequences that are consistent with the control flow graph of the program; (ii) is maximal given a set of training data, meaning that any extensions to the execution graph could permit some intrusions to go undetected. We formalize and prove these claims, and evaluate the performance of an anomaly detector using execution graphs.; Behavioral distance compares the behavior of a process to the behavior of another process that is executing on the same input but that either runs on a different operating system or runs a different program that has similar functionality. Assuming their diversity renders these processes vulnerable only to different attacks, a successful attack on one of them should induce a detectable increase in the "distance" between the behavior of the two processes. We propose two black-box approaches for measuring behavioral distance, the first inspired by evolutionary distance and the second using a new type of Hidden Markov Model.; We additionally build and evaluate a replicated system, which uses behavioral distance to protect Internet servers. Through trace-driven evaluations we show that we can achieve low false-alarm rates and moderate performance costs even when the system is tuned to detect very stealthy mimicry attacks. |
