Multiple instance learning for malware classification

Jan Stiborek, Tomás Pevný, Martin Rehák

Introduction

Malware detection remains a persistent challenge as authors increasingly employ obfuscation and randomization to evade traditional security measures. This paper introduces a robust classification system that shifts the focus from static code analysis to dynamic behavioral modeling. By utilizing a Multiple Instance Learning (MIL) framework, the authors model how programs interact with system resources—such as files, registry keys, and network domains—to create a resilient "vocabulary" of behavior that strips away common evasion techniques.

The Challenge: Evasion and Dimensionality

Traditional malware detection often relies on static analysis, which is easily defeated by polymorphism and encryption. Dynamic analysis, which observes code execution in a sandbox, is more robust but frequently focuses on system calls that can be "gamed" through injection attacks.

Furthermore, many machine learning approaches utilize a "Bag-of-Words" (BoW) model where every unique resource name is a feature. This leads to "dimension explosion," where millions of features are generated from randomized strings (e.g., temp_a8f2.exe). Such high dimensionality makes it difficult for classifiers to generalize across different samples from the same malware family.

Methodology: Multiple Instance Learning

The authors frame malware detection as a Multiple Instance Learning problem. In this model, a single binary is treated as a "bag," and every interaction it has with a system resource is an "instance" within that bag. The approach follows three primary steps:

  1. Custom Similarity Metrics: Instead of simple string matching, the system uses specialized similarity functions. For example, a file path metric distinguishes between "known folders" (like \Windows\System32) and "general folders" (like random temporary directories).
  2. Approximative Clustering: To manage millions of unique resource names, a modified Louvain clustering algorithm groups similar behaviors into "artifact clusters." This effectively "de-randomizes" the data by mapping various randomized filenames to a single behavioral cluster.
  3. Vocabulary-Based Projection: Each binary is represented as a fixed-length binary vector based on the artifact clusters it interacts with. This low-dimensional representation is then processed by a Random Forest classifier.
This table illustrates how raw, randomized filenames are mapped to consistent behavioral artifact clusters, effectively de-randomizing the input data.

Key Results and Performance

The proposed MIL approach was evaluated against a massive real-world dataset of over 250,000 files. It consistently outperformed state-of-the-art models like Rieck (a high-dimensional BoW model) and AMAL (a system using hand-crafted features).

  • Accuracy: The MIL approach achieved a True Positive Rate (TPR) of 0.954 and a False Positive Rate (FPR) of 0.067, surpassing the Rieck model's performance.
  • Data Efficiency: Most notably, the MIL model achieved a lower False Negative Rate (FNR) using only 5% of the training data than the Rieck model did using 100% of the training data.
  • Generalization: The system showed a significantly smaller gap between training and testing accuracy, suggesting it is less prone to overfitting on transient malware strings.
Comparison of False Negative Rate (FNR) and False Positive Rate (FPR) across different training set sizes, demonstrating the superior data efficiency of the proposed approach.

Discussion and Future Work

While highly effective, the system has limitations. It cannot detect "resource-light" malware (like memory-only miners) that performs no file or network actions, and it remains susceptible to anti-VM techniques where malware refuses to execute in a sandbox. Additionally, some legitimate installers can trigger false positives due to their complex file-dropping behavior.

Future research aims to expand the behavioral vocabulary to include more diverse signals and refine clustering techniques to better distinguish between legitimate software installers and malicious droppers.

Summary updated

Abstract

This work addresses classification of unknown binaries executed in sandbox by modeling their interaction with system resources (files, mutexes, registry keys and communication with servers over the network) and error messages provided by the operating system, using vocabulary-based method from the multiple instance learning paradigm. It introduces similarities suitable for individual resource types that combined with an approximative clustering method efficiently group the system resources and define features directly from data. This approach effectively removes randomization often employed by malware authors and projects samples into low-dimensional feature space suitable for common classifiers. An extensive comparison to the state of the art on a large corpus of binaries demonstrates that the proposed solution achieves superior results using only a fraction of training samples. Moreover, it makes use of a source of information different than most of the prior art, which increases the diversity of tools detecting the malware, hence making detection evasion more difficult.
BibTeX
@article{stiborek2018multiple,
  author = {Jan Stiborek and Tomás Pevný and Martin Rehák},
  title = {{Multiple instance learning for malware classification}},
  journal = {Expert Systems with Applications},
  year = {2018},
  doi = {10.1016/j.eswa.2017.10.036},
}
Figure