Minimal contrast frequent pattern mining for malware detection

Currently, most of widely-used malware detection software products utilize signature-based algorithms to recognize threats. However, this approach is problematic because it relies on file hashes and byte (or instruction) signatures. Consequently, obfuscation techniques are straightforward ways to modify these features syntactically and evade detection. Since it is harder for an attacker to radically change the behavior of a malware than to morph its syntactic structure, behavior-based detection techniques are a promising solution to this problem. However behavior-based techniques can be applied using static analysis or dynamic analysis or hybrid analysis. While dynamic behavior-based detection methods are time consuming and fail to obtain all possible malicious execution traces, most of static behavior-based approaches suffer from a high growth rate in the number of behavioral signatures and suffer from high false positive rates. In this paper, we present a new graph mining method to detect variants of malware using static analysis, while covering the existing defects. We propose a novel algorithm, called minimal contrast frequent subgraph miner algorithm (MCFSM), for extracting minimal discriminative and widely employed malicious behavioral patterns which can identify precisely an entire family of malicious programs, in contrast to another set of benign programs. The proposed method shows high detection rates and low false positive rates and generates a limited number of behavioral malware signatures.