Leveraging Compression-Based Graph Mining for Behavior-Based Malware Detection

Behavior-based detection approaches commonly address the threat of statically obfuscated malware. Such approaches often use graphs to represent process or system behavior and typically employ frequency-based graph mining techniques to extract characteristic patterns from collections of malware graphs. Recent studies in the molecule mining domain suggest that frequency-based graph mining algorithms often perform sub-optimally in finding highly discriminating patterns. We propose a novel malware detection approach that uses so-called compression-based mining on quantitative data flow graphs to derive highly accurate detection models. Our evaluation on a large and diverse malware set shows that our approach outperforms frequency-based detection models in terms of detection effectiveness by more than 600 percent.