A Formal Framework for Program Anomaly Detection

Abstract. Program anomaly detection analyzes normal program be-haviors and discovers aberrant executions caused by attacks, miscon-figurations, program bugs, and unusual usage patterns. The merit of program anomaly detection is its independence from attack signatures, which enables proactive defense against new and unknown attacks. In this paper, we formalize the general program anomaly detection prob-lem and point out two of its key properties. We present a unified frame-work to present any program anomaly detection method in terms of its detection capability. We prove the theoretical accuracy limit for pro-gram anomaly detection with an abstract detection machine. We show how existing solutions are positioned in our framework and illustrate the gap between state-of-the-art methods and the theoretical accuracy limit. We also point out some potential modeling features for future program anomaly detection evolution