Source-linked AI summary
Malware Classification based on Call Graph Clustering
Joris Kinable, Orestis Kostakis
TL;DR
The paper addresses the need to classify massive and evolving malware collections despite pattern-evasion techniques. It represents samples as call graphs, approximates graph-edit-distance comparisons, and clusters the resulting similarities. Experiments against analyst-labeled families show that call-graph clustering can detect malware families, while exact graph matching remains computationally hard.
Problem
Tens of thousands of daily samples and constantly modified malware make automated detection and family classification necessary.
Method
The paper extracts call graphs, computes pairwise similarities using graph matching that approximately minimizes graph edit distance, and applies k-medoids and DBSCAN clustering.
Results
Call-graph clustering can accurately detect malware families in experiments evaluated against manual analyst classifications.
Takeaways & Limitations
Recognizing structural similarities among malware variants can support generic signatures instead of separate detection patterns for every sample.
Abstract
from arXiv · showhide
Each day, anti-virus companies receive tens of thousands samples of potentially harmful executables. Many of the malicious samples are variations of previously encountered malware, created by their authors to evade pattern-based detection. Dealing with these large amounts of data requires robust, automatic detection approaches. This paper studies malware classification based on call graph clustering. By representing malware samples as call graphs, it is possible to abstract certain variations away, and enable the detection of structural similarities between samples. The ability to cluster similar samples together will make more generic detection techniques possible, thereby targeting the commonalities of the samples within a cluster. To compare call graphs mutually, we compute pairwise graph similarity scores via graph matchings which approximately minimize the graph edit distance. Next, to facilitate the discovery of similar malware samples, we employ several clustering algorithms, including k-medoids and DBSCAN. Clustering experiments are conducted on a collection of real malware samples, and the results are evaluated against manual classifications provided by human malware analysts. Experiments show that it is indeed possible to accurately detect malware families via call graph clustering. We anticipate that in the future, call graphs can be used to analyse the emergence of new malware families, and ultimately to automate implementation of generic detection schemes.
1 Introduction
Malware analysis must handle very large sample volumes and constantly modified code. The paper motivates high-level abstractions that expose commonalities across related samples despite such changes.
- Daily submissions of tens of thousands of potentially harmful executables require autonomous detection, identification, and categorization systems.
- Packing, encryption, and new malware versions hinder automated detection based on executable code patterns.
- Recognizing commonalities among malware-family members could support proactive detection of known samples and future modified releases.
- Call-graph comparison can reveal differences between executable versions or code theft and may focus analyst effort on variant differences.
2 Introduction to Call Graphs
The paper represents executables as directed call graphs whose vertices are functions and whose edges are function calls. Static disassembly extracts these structures, distinguishing local functions from external system and library calls.
- A call graph represents an executable as a directed graph of function vertices connected by directed edges denoting calls.
- Vertices represent either local functions implemented by the program designer or external system and library calls.
- In the example call graph, names beginning with ’sub’ denote local functions, while other names denote external functions.
- Static analysis unpacks or decrypts code, identifies functions, assigns symbolic names, and adds edges for extracted function calls.
3 Graph Matching
The paper compares malware call graphs through graph matching and graph edit distance, then converts these comparisons into similarity scores for clustering. Because exact optimization is computationally expensive, it uses approximation methods.
- Graph Matching: Graph matching compares call graphs by finding mappings that optimize a cost function measuring mapping quality.
- Graph Matching: The comparison techniques considered include graph isomorphism, maximum common subgraphs, and minimum graph edit distances.
- Graph Edit Distance: Graph edit distance is the minimum-cost sequence of vertex insertion/deletion, edge insertion/deletion, and vertex relabeling operations transforming one graph into another.
- Graph Edit Distance: Exact minimum GED and GED-minimizing graph matching are computationally hard, so the paper relies on approximation algorithms.
- Graph Similarity: Similarity is defined on [0,1], with 0 for identical graphs and 1 for graphs with no similarities, and it is symmetric.
- Graph Similarity: The method pads unequal graphs with dummy vertices, counts vertex, edge, and relabel costs, and uses simulated annealing to approximate a GED-minimizing mapping.
4 Clustering
The clustering stage groups malware call graphs using similarity scores, adapting k-means ideas to graph-valued data through medoids and examining alternative initialization and clustering procedures.
- Clustering is used to identify malware families with strong structural similarities and support generic signatures covering shared characteristics.
- Clustering Algorithms: The paper evaluates k-medoids and DBSCAN on call-graph samples, with the algorithm receiving a cluster count and a set of call graphs.
- k-medoids Clustering: Unlike k-means, k-medoids selects an actual call graph with the highest within-cluster similarity as each cluster center.
- k-medoids Clustering: k-medoids minimizes similarity-based within-cluster objectives using approximate optimization because exact solutions are NP-hard.
3 repeat
The study evaluates k-medoids and DBSCAN clustering of malware call graphs against 24 analyst-defined families, finding that DBSCAN separates most families more effectively than k-means-based clustering.
- 3 repeat: K-medoids convergence follows from the monotonic decrease of its objective function over a finite set of possible clusterings.The method can nevertheless produce poor results when initialization is weak, motivating k-means++-style initialization.
- 4.1.1 Clustering performance analysis: The evaluation uses 194 malware call graphs manually classified by F-Secure analysts into 24 families.The samples contain 234 nodes and 488 edges on average.
- 4.1.1 Clustering performance analysis: k-means++ produces tighter, more coherent clusters than randomly initialized k-medoids, while trained initialization performs best in the reported comparison.The trained method initializes medoids using one member from each predetermined family.
- 4.2 Determining the number of clusters: Neither Sum of Error nor the silhouette coefficient yields a clear koptimal matching the 24 manual partitions under k-means-based clustering.The experiments also found that some samples were difficult to assign automatically.
- 4.3 DBSCAN clustering: DBSCAN performs best at Minpts = 3 and Rad = 0.3, and each cluster correctly identifies a family except three clusters.Most samples from larger families are clustered rather than labeled noise, whereas small families are often discarded as noise.
5 Conclusion
The paper studies automated malware-family classification by comparing call graphs and clustering structurally similar samples. On 194 samples manually categorized into 24 families, DBSCAN successfully identified malware families, while k-means was ineffective for this task.
- Graph edit distance provided a viable metric for expressing similarities between malware call graphs.
- Clustering experiments used various k-medoids algorithms and DBSCAN on call graphs from malware samples.
- 194 unique malware samples were manually categorized into 24 malware families by F-Secure Corporation for classification verification.
- Metrics for selecting the desired number of k-medoids clusters were inconclusive, making k-means ineffective for discovering malware families.
- DBSCAN produced much better results and successfully identified malware families.