Poisoning Behavioral Malware Clustering

Battista Biggio; Konrad Rieck; Davide Ariu; Christian Wressnegger; Igino Corona; Giorgio Giacinto; Fabio Roli

Source-linked AI summary

Poisoning Behavioral Malware Clustering

Battista Biggio, Konrad Rieck, Davide Ariu, Christian Wressnegger, Igino Corona, Giorgio Giacinto, Fabio Roli

arXiv:1811.09985v1Nov 25, 2018cs.LGcs.CRstat.ML

TL;DR

Behavioral malware clustering is vulnerable because standard clustering algorithms were not designed for adversarial input data. The paper adapts poisoning attacks to Malheur and finds that carefully crafted injections, even at small fractions, can largely disrupt clustering, underscoring the need for more robust algorithms.

Problem
Standard clustering algorithms used for malware analysis were not designed to handle malicious noise, leaving their security under poisoning attacks in question.
Method
The paper adapts previously proposed poisoning attacks to Malheur’s behavioral feature representation and evaluates them through a case study.
Results
2% of injected samples reduced Malheur’s clusters from 40 to 5, while 5% produced a single cluster merging all initial clusters.
Takeaways & Limitations
The findings cast doubt on the security of some malware-analysis clustering algorithms and motivate algorithms robust to poisoning and malicious noise.
Takeaways & Limitations
Creating behavioral features artificially may be more or less difficult depending on the underlying sandbox environment.

Abstract

from arXiv · show

Clustering algorithms have become a popular tool in computer security to analyze the behavior of malware variants, identify novel malware families, and generate signatures for antivirus systems. However, the suitability of clustering algorithms for security-sensitive settings has been recently questioned by showing that they can be significantly compromised if an attacker can exercise some control over the input data. In this paper, we revisit this problem by focusing on behavioral malware clustering approaches, and investigate whether and to what extent an attacker may be able to subvert these approaches through a careful injection of samples with poisoning behavior. To this end, we present a case study on Malheur, an open-source tool for behavioral malware clustering. Our experiments not only demonstrate that this tool is vulnerable to poisoning attacks, but also that it can be significantly compromised even if the attacker can only inject a very small percentage of attacks into the input data. As a remedy, we discuss possible countermeasures and highlight the need for more secure clustering algorithms.

1. INTRODUCTION

Behavioral malware clustering helps analyze polymorphic and novel malware by grouping samples with similar execution behavior, but adversaries may poison inputs and compromise the clustering process. This paper adapts poisoning attacks to Malheur and shows that a small injected fraction can subvert clustering.

1. INTRODUCTION: These techniques support malware analysis, detection, mitigation, family identification, and discovery of novel attack types.They can reduce the analysis burden by orders of magnitude.
1. INTRODUCTION: Behavioral clustering groups malware variants by similar host-level events or network traffic observed in monitored sandboxes.The approach relies on the assumption that polymorphic variants retain similar behavior despite packing and obfuscation.
1. INTRODUCTION: Clustering algorithms were not designed for adversarial data, allowing carefully crafted inputs to compromise clustering and invalidate subsequent analyses.This vulnerability applies regardless of which behavioral features are used.
1. INTRODUCTION: The paper adapts poisoning attacks to Malheur by injecting specially crafted actions while preserving the original malicious goals of malware samples.The study reviews an existing attacker model and evaluates a worst-case attack against this open-source tool.
1. INTRODUCTION: 3% of poisoning samples may completely subvert clustering, producing poor clustering results and motivating more robust techniques.The authors characterize secure application of clustering for malware analysis as an open research issue.

2. MALWARE CLUSTERING

Malware clustering uses network traffic and program behavior to organize related samples, scale analysis, and support signature generation. However, these approaches generally rely on standard clustering algorithms that do not explicitly handle malicious noise.

2. MALWARE CLUSTERING: Malware clustering approaches primarily analyze network traffic or program behavior to group related samples automatically.These two strands address different observable aspects of malware activity.
Clustering of network traffic: Network-traffic methods use hierarchical clustering to characterize botnet communication and generate malware network signatures.Examples include q-grams over activity logs and multi-stage single-linkage clustering.
Clustering of program behavior: Program-behavior methods exploit similarities that often persist across polymorphic and obfuscated variants of the same malware family.They compute similarities from host-level event sequences or use approximate clustering to scale analysis.
Clustering of program behavior: Malheur is a behavioral clustering tool that uses program behavior monitored by CWSandbox in MIST Format.It is presented as the case-study tool for evaluating poisoning attacks.
2. MALWARE CLUSTERING: Extensions improve scalability, calibration, or integration with static analysis, but the approaches still use standard clustering algorithms not designed for malicious noise.The paper argues that its attacks may therefore be adapted to several approaches with minor modifications.

3. SECURITY EVALUATION OF CLUSTERING ALGORITHMS

The security-evaluation framework models clustering attacks through the adversary’s goal, knowledge, and data-manipulation capability. It formalizes optimal attacks while recognizing that translating optimized feature vectors into real malware samples is application-specific and may be difficult.

3. SECURITY EVALUATION OF CLUSTERING ALGORITHMS: The framework evaluates unsupervised learning security by defining the adversary’s goal, system knowledge, and input-data manipulation capability.These components formalize an optimal attack strategy.
3. SECURITY EVALUATION OF CLUSTERING ALGORITHMS: A clustering algorithm is modeled as a function f that maps dataset D to a clustering result C.The framework leaves the structure of C unspecified because it depends on the clustering algorithm.
3.1 Adversary’s Goal: Adversary goals are classified by security violation and specificity, including integrity, availability, and privacy attacks that may be targeted or indiscriminate.In unsupervised learning, availability attacks seek to alter the clustering result as much as possible.
3.2 Adversary’s Knowledge: The attacker may know the full dataset, a subset, or a surrogate dataset, and may know or reproduce the feature-extraction process.For open-source tools such as Malheur, the feature set may be fully known.
3.2 Adversary’s Knowledge: Perfect knowledge means knowing the data, feature space, clustering algorithm, and its initialization.This defines the worst-case knowledge assumption used in the framework.
3.3 Adversary’s Capability: The attacker may add a bounded number of manipulated samples, while malware-preserving constraints can restrict how samples and feature values are changed.The appropriate constraint depends on the application and feature representation.
3.4 Attack Strategy: The optimal attack strategy maximizes the expected attack objective over uncertainty about system parameters and allowable manipulations.The parameter vector θ represents information about the data, algorithm, and parameters; Ω(A) represents permitted manipulations.
3.4 Attack Strategy: The optimization is posed in feature space, so constructing corresponding real samples is an application-specific step that may be nontrivial.Manipulation constraints can mitigate this difficulty when defining the allowable set.

4. POISONING ATTACKS WITH PERFECT KNOWLEDGE

The paper models poisoning as injecting constrained malware samples to maximize changes in clustering assignments on untainted data. For single-linkage clustering, it develops bridge-based heuristics because the optimization is generally not analytically solvable.

Attack formulation: Poisoning attacks inject up to m constrained samples to maximally alter clustering on the original, untainted data.The attack samples are excluded from the objective evaluation, which focuses on changes to the original inputs.
Attack formulation: The attack objective measures disagreement between clustering results before and after poisoning using a distance between clusterings.Clusterings are represented through sample-to-cluster assignments and pairwise co-membership matrices.
Attack formulation: The optimization is generally not analytically solvable because clustering outputs are usually not analytically predictable.The paper therefore uses clustering-algorithm-specific heuristics for effective attacks.
Bridge-based attacks: Bridge-based attacks generate k−1 candidate samples corresponding to the shortest connections separating the current k clusters.Each candidate is designed to bridge a pair of adjacent clusters in the hierarchy.
Bridge-based attacks: Bridge (Best) evaluates every candidate by rerunning clustering, whereas Bridge (Hard) estimates the result by assuming the candidate merges adjacent clusters.The Best strategy is computationally intensive; Hard avoids k clustering reruns per iteration.
Bridge-based attacks: Bridge (Soft) uses KDE-based posterior assignments to seek connections that may merge large clusters with multiple attack samples.Its bandwidth controls whether assignments are nearly uniform or approach hard assignments.

5. A CASE STUDY: MALHEUR

The Malheur case study applies poisoning attacks to a behavioral malware-clustering pipeline based on sandbox traces, q-gram embeddings, hierarchical clustering, and classification. The setup uses single-linkage clustering without prototype-based approximation.

Malheur pipeline: Malheur analyzes malware behavior through four steps: MIST representation, embedding, clustering, and classification.The pipeline begins with monitored sandbox behavior and ends with assigning unknown behavior to discovered clusters.
Malheur pipeline: MIST representation records sandboxed program behavior as sequential reports of monitored system calls and arguments.Execution flows of threads and processes are grouped into a single report.
Malheur pipeline: Embedding maps behavior into a binary high-dimensional q-gram vector and normalizes each vector to unit ℓ2-norm.Each dimension indicates whether a short sequence of q events occurs in the monitored behavior.
Malheur pipeline: Malheur supports single-linkage and complete-linkage hierarchical clustering, with prototype-based approximation available to reduce quadratic runtime.The case study disables prototype-based approximation and operates on the full data.
Case-study configuration: Figure 1 depicts candidate attack samples as red hexagons connecting the k−1 closest clusters in single-linkage clustering.The candidates correspond to the bridge links used by the poisoning strategy.
Case-study configuration: The case study uses MIST level 1, q-gram length 1, and single-linkage clustering without prototype-based approximation.The authors note that enabling prototype approximation would introduce a complete-linkage preprocessing step requiring a revised attack derivation.

6. EXPERIMENTAL EVALUATION

The evaluation tests poisoning attacks against Malheur using two malware datasets, controlled calibration and evaluation splits, and clustering-quality metrics. Carefully selected bridge-based attacks substantially damage clustering, while random injection has little effect and attack effectiveness varies by dataset.

Datasets and setup: The evaluation uses Malheur data and a 2013 Recent Malware dataset, with each dataset split into calibration set T and evaluation set S.T calibrates the clustering cutoff distance, while S evaluates clustering on unseen malware under increasing poisoning percentages.
Metrics: The evaluation measures objective-function change, cluster count, and F-measure to quantify poisoning effects on clustering.F-measure is the harmonic mean of precision and recall; cluster count indicates whether poisoning bridges clusters.
Attack construction: Malheur’s binary, unit-ℓ2-normalized embedding constrains poisoning samples, so attacks use realistic malware and feature addition rather than arbitrary feature changes.Candidate bridge points must respect the embedding constraints, and bridge construction differs from midpoint averaging because of the representation.
Results: Random injection does not significantly worsen clustering because random points become singleton clusters, leaving the remaining clustering largely unaffected.Random (Best) performs slightly better by testing k − 1 candidate points per iteration instead of one.
Results: Maximizing the objective function reduces cluster count and achieves performance similar to F-measure (Best), despite not using domain, algorithm, or feature knowledge.The proposed objective function is presented as potentially applicable beyond Malheur.
Results: On the Malheur dataset, Bridge (Best) and F-measure (Best) reduce 40 clusters to 5 with 2% injected samples and merge them into one cluster at 5%.Bridge (Soft) and Bridge (Hard) require slightly more samples but are significantly less expensive computationally than the Best strategies.
Results: On the Recent Malware dataset, bridge attacks cannot merge all clusters because candidate bridge points become too distant, limiting their effectiveness.The passage attributes this behavior partly to the dataset’s smaller feature set, while Bridge (Best) still reaches an objective-function value of 250.

7. CONCLUSIONS AND FUTURE WORK

The study shows that a small fraction of poisoning samples can significantly compromise Malheur’s malware-family recovery, raising broader security concerns for clustering-based malware analysis. The authors identify limits of the current evaluation and call for more robust clustering algorithms and countermeasures.

A small fraction of poisoning samples can largely destroy malware-family recovery in a dataset of real malware.
The attacks adapt previously proposed poisoning methods to Malheur’s feature representation and application-specific constraints when creating real poisoning malware samples.
Creating artificial behavioral features may be more or less difficult depending on the underlying sandbox environment.
The exploited vulnerability resides in the clustering algorithms and can therefore hardly be fixed by changing the feature representation.
Future work includes limited-knowledge attacks, attacks against more clustering algorithms, and countermeasures against adversarial threats and well-crafted attacks.
Poisoning is one attack type among others, including attempts to make malware behavior mimic legitimate samples without substantially changing clustering output.