Synthesizing near-optimal malware specifications from suspicious behaviors

Behavior-based detection techniques are a promising solution to the problem of malware proliferation. However, they require precise specifications of malicious behavior that do not result in an excessive number of false alarms, while still remaining general enough to detect new variants before traditional signatures can be created and distributed. In this paper, we present an automatic technique for extracting optimally discriminative specifications, which uniquely identify a class of programs. Such a discriminative specification can be used by a behavior-based malware detector. Our technique, based on graph mining and stochastic optimization, scales to large classes of programs. When this work was originally published, the technique yielded favorable results on malware targeted towards workstations (~86% detection rates on new malware). We believe that it can be brought to bear on emerging malware-based threats for new platforms, and discuss several promising avenues for future work in this direction.