Extraction of Statistically Significant Malware Behaviors

Traditionally, analysis of malicious software is only a semi-automated process, often requiring a skilled human analyst. As new malware appears at an increasingly alarming rate — now over 100 thousand new variants each day — there is a need for automated techniques for identifying suspicious be-havior in programs. In this paper, we propose a method for extracting statistically significant malicious behaviors from a system call dependency graph (obtained by running a bi-nary executable in a sandbox). Our approach is based on a new method for measuring the statistical significance of sub-graphs. Given a training set of graphs from two classes (e.g., goodware and malware system call dependency graphs), our method can assign p-values to subgraphs of new graph in-stances even if those subgraphs have not appeared before in the training data (thus possibly capturing new behaviors or disguised versions of existing behaviors). 1