Clustering based opcode graph generation for malware variant detection

Malware is often used as a means to gain an initial compromise of victim hosts commonly through activities such as social engineering and phishing schemes. Once targets are infected, a variety of malicious activities are furthered performed by the malwares. These activities include lateral movement to infect more targets in the same network, exfiltration or destruction of valuable data and the disruption of critical systems. The detection of malwares is therefore a must for protecting critical systems and hence is a widely researched topic. There is a large variety of research works and methodologies on the detection of malwares which have been introduced by various surveys [24, 16, 21, 39]. However, it has become increasingly challenging for these methods to have ideal detection performances due to the rapidly evolving malwares and growing pool of different malware families [11]. In the SonicWall’s 2021 Cyber Threat Report [12], their solutions found a total of 589,313 new malware variants in 2020. Overall, 74% more never-before-seen malware variants were identified in 2020 than in 2019.

Malware authors apply various types of techniques on the creation of malware variants in order to evade detection from the variety of defense mechanisms. Such obfuscation techniques include encryption, polymorphism and metamorphism which have been introduced in research works such as in [40]. In particular, metamorphism provides the capability to alter the internal structure of each malware, whilst being able to maintain the same functional outputs [28, 35, 15]. Thus it is possible to produce an infinite pool of malwares within the same family. These malwares achieve the same purpose but are not identical. Common signature-based solutions therefore become ineffective as each of these malwares have different signatures. This also makes it challenging for other types of methods such as dynamic and behaviour analysis to effectively detect these continuously morphing malwares that have evasive mechanisms during runtime.

Static analysis, which involves analyzing the file properties and structure, may also be relied upon to detect obfuscated malware. In this paper, our proposed methodology focuses on the analysis of one such static property, which is opcodes. Opcodes are machine instruction codes that define the operations that needs to be performed when the file is executed. Hence, it is a representation of a file’s structure and operations and is useful for malware detection.

In this work, we extract opcodes from malware samples, build opcode graphs using bigrams and perform graph similarity comparison for malware classification and family attribution. However differing from the above previous works and graph-based methods in particular, we integrate the use of clustering algorithms on the graphs belonging to samples within the same families. The purpose of this idea is to first detect potential clusters of sub-family samples as a preliminary step, as malwares belonging to the same family may be generated from different versions of the family codebase. Hence there may be some considerable differences in the structure of the malwares generated by different code versions within the same family. It is then meaningful to detect these different groups to be able to boost detection accuracy. Opcode bigrams belonging to clustered samples are used to build a single opcode graph which represents its signature. Each malware family is thus represented by a set of opcode graph signatures, with each signature belonging to a different sub-family or version. For an incoming unknown sample, its opgraph is extracted and compared against each signature to find the closest matching family for classification.

In summary, these are the contributions of our paper:

1. 1.

   An opcode-based approach for malware detection and attribution is proposed. The method builds opcode graph signatures for each malware family, which can be used for similarity comparison against samples and classify them to one of the malware families.

2. 2.

   Clustering algorithms are explored to perform the detection of clusters on samples belonging to the same malware family. The existence of different clusters of samples that have considerable difference in characteristics and therefore potentially belong to separate sub-families is demonstrated as a result.

3. 3.

   The proposed methodology is evaluated on a dataset comprising of 2300 malware samples belonging to six different malware families and 580 benign file samples. Both binary classification experiments for general malware detection and multi-class classification experiments for family attribution are performed.

In the following section, we discuss the related works. In Section III, we present our methodology in detail and describe its various steps. Experiments and performance evaluation of the proposed method are presented in section IV. Finally, future improvements and conclusions are discussed in section V

Vast research has been carried out in the areas of malware analysis due to the rampant growth of the issue and the critical need for defense mechanisms against malwares. Many research surveys have been published to provide the community with a comprehensive breakdown of features and techniques explored. [37, 39] are some recent surveys. Malware analysis can be broadly categorised into two categories, static analysis and dynamic analysis. In static analysis, extraction of features based on the content of the files without executing them is performed. Such features include file strings, byte sequences, opcodes, static API calls and control flow graphs. There are also features unique to different types of applications such as android. In [41], n-gram analysis techniques were applied on XML and DEX files found within the application’s Android Package Kit (APK). On the other hand, dynamic analysis involve observing the behavior of malwares during execution in a simulated environment. This approach allows more information related to the malwares’ interactions, such as its dynamic API calls, network activity, access and modifications to the file systems and registries to be collected.

In this paper we focus on the static analysis feature of opcodes for malware family attribution and detection of metamorphic malware. Santos et al. [33] represented each malware sample as a vector containing the frequencies of fixed length opcode sequences. Similarity comparison is performed against variants belonging to a set of different malware families and attribute the sample to the closest family. Rad and Masrom [14] extracted opcode frequencies as histograms and applies histogram dissimilarity metrics to detect similarities to metamorphic families and hence classify them. Toderici and Stamp [36] proposed to combine chi-squared statistical test with HMM method. Each program is represented by a spectrum of opcode frequencies and chi-squared test is performed to determine whether it matches the expected spectrum of frequencies from a malware family. This method is effective at metamorphic virus detection but performs poorly when techniques such as copying benign codes into malware are used. Shangmugam et al. [34] applied the use of a simple substitution cipher technique as a measure of similarity between the opcode distribution matrix of each metamorphic family to that of an unknown sample. Fazlali et al. [20] extracted an opcode feature set such as normalized frequency count of opcodes and appearance of high frequency opcodes. The feature set is used to train models of six different decision tree based machine learning algorithms such as Random forest to classify samples into metamorphic families or as benign. Sahay and Sharma [32] investigated and found that malwares generated from the same metamorphic virus kit are similar in size. Thus they applied K-Means clustering on their size values to detect clusters of metamorphic malwares from a dataset. Opcode frequency based features are then extracted from each cluster and used to train common classifiers for detection. Okane et al. [29] explored the use of runtime opcodes during the execution of the program for obfuscated malware such as encrypted malware. Support vector machine (SVM) was applied on density histogram of runtime opcodes as features.

Recently, works have applied deep learning on opcode-based features. Darem et al. [17] uses the popular method of converting features into images. Opcode n-gram features were converted into malware binary code and finally into gray-scale images before feeding into a Convolutional Neural Network (CNN) model. Their final model is an ensemble of CNN and XGBoost, combining both deep learning and traditional machine learning. [27] is another image based deep learning work that combines opcode features from both ASM and Bytes file of the malwares.

Graph-based techniques have also been applied on opcodes for malware analysis. Many of such works extract weighted directed graph of opcode digrams for each malware sample. One aspect of such works involve the use of sub-graph matching techniques. Khalilian et al. [26] constructs the opcode graph of samples and applies graph mining techniques to detect frequently occurring subgraphs across samples of the same malware family. These subgraphs represent micro-signatures of each family and are used as features to train classifiers for detection. [18] is a closely similar work but uses control flow graphs (CFG) instead of opcodes for frequent sub-graph mining. Gulmez et al. [22] performs further engineering of the sub-graphs of opcodes into histograms containing the degree of each graph node to produce final features as input to the machine learning models. Alam et al. [13] proposes two different techniques, with one using CFG and the other using opcodes. One key novelty of their work involves representing both CFG and opcodes as higher level patterns. This CFG is termed as Annotated CFG (ACFG) and they apply sub-graph isomorphism technique for malware pattern matching. Their second technique performs analysis of pattern distributions by applying sliding windows on the higher level opcode representations.

The other aspect of graph-based works consist of graph similarity analysis approaches which are closely related to our proposed methodology. Runwal et al. [31] first extracts the opcode graph of each malware sample. In order to determine the similarity between two graphs extracted from different samples, they proposed a formula to compute a score value from the graph matrices. They determined a threshold for the score value by performing a comparison of all samples in each metamorphic family and benign files. To classify new samples, comparison is performed on the opcode graph of the sample and any sample belonging to each metamorphic family or benign files and the sample is assigned to the class in which the score falls below the threshold. Kakisim et al. [25] proposes two graph similarity based techniques. Their first technique, coined as Co-opcode Graph Similarity based Metamorphic Malware Identification method (CGS-MMI), involves building a single opcode graph to represent each metamorphic family. A similarity comparison of opcode graphs of an unknown sample and that of each metamorphic family is done to determine the family with highest similarity for classification. Their similarity score is computed using a 2-D correlation coefficient formula which uses the mean of the weights of edges in the graphs. Their second proposed technique, Higher-Level Engine Signatures based Metamorphic Malware Identification method (HLES-MMI), aims to extract a higher level signature from the representative opcode graph of each metamorphic family. The idea is to only retain nodes and edges with the largest weights in each graph which indicates a specific pattern signature for each family. A metric is then used to determine the similarity among signatures for classification.

As our work also involves the use of clustering algorithms, following is a discussion on some clustering works. Zhang et al. [42] uses both static and dynamic features and applies clustering algorithms such as K-means and Hierarchical clustering. An ensemble method to combine both algorithms and improve robustness of results is proposed. Pitolli et al. [30] also use hybrid features but apply BIRCH clustering. Clustering is performed on the input dataset to group samples for the purpose of identifying the set of families that exist and attribute the samples to those families.

Hu et al. [23] propose a clustering-based work using opcode n-grams. Feature vectors containing occurrences of each opcode n-gram are used as input to calculate the Euclidean distance and hence determine program similarities. The authors argue that classic algorithms such as K-means and hierarchical clustering do not scale and propose the use of a prototype-based clustering method to cluster samples in their dataset of 20 malware families. Wang et al. [38] extracts opcode bigrams and uses information entropy on the bigram probabilities to select a smaller set of important bigrams as features. They propose a Fast Density-based Clustering which is an improvement over the standard density-based algorithm.

Differing from the above clustering works, our proposed methodology does not apply clustering on a dataset as a whole to identify the malware families or use clustering as the main means to classify new samples to their families. Instead we apply clustering separately on samples belonging to each malware family using a labelled dataset of samples with family categorisation. The purpose of this to attain a more fine-grained attribution capability by detecting potential sub-family groups that may have considerable differences even if they belong to the same family. In [23], it was reported that previous clustering approaches resulted in families being separated into several sub-family clusters, more specifically the detection of 50 clusters from a dataset of 20 families, due to highly diverse samples. This is an indication that our approach would be a meaningful research direction.

Our clustering approach is integrated to the graph similarity analysis techniques in [31, 25]. We follow these methods of similarity comparison as they have been shown to be effective in the detection of malware samples belonging to different metamorphic families. However, instead of applying the similarity comparison directly on samples, our approach applies such techniques as a means for similarity and distance calculations for input to the clustering algorithm to detect sub-family clusters within the same family.

Our proposed methodology can be organised as a three-stage process consisting of the following:

1. 1.

   Creation of family distance matrix via similarity comparison of opcode graphs

2. 2.

   Detection of sub-family groups via application of clustering algorithm

3. 3.

   Building of opcode graph signatures from clusters for detection and family attribution

An illustration of the above process is shown in Fig. 1.

In this paper, we presented an opcode-based methodology involving graph similarity comparison for malware detection and malware family attribution. We integrated a clustering algorithm into our approach to detect sub-family groups of malwares that potentially represent different versions of the malware family. Opcode graph signatures are extracted from each cluster which are used for similarity comparison to detect and attribute incoming samples. Experiments were performed on a dataset containing different malware families to evaluate the proposed methodology. The method achieved high recall and low false positives for binary classification. For multi-class classification, high attribution performance was obtained for some malware families. For certain families with relatively lower performance, investigations were performed to provide insights on the result.

There are several future work and enhancements that can be explored for the work. Further improvements or new methodologies can be proposed for the opcode graph based similarity comparison techniques that are used. Input parameters for the clustering algorithm resemble thresholds and are currently manually determined. It may be beneficial to look into how to better set these parameters, possibly through an automated approach. Another area is on scalability. The nature of signature comparison approaches is that the more signatures there are, the processing time required increases linearly. More signatures will be created from the addition of new malware samples and families and more comparisons have to performed. Hence we should also look into efficiency improvements.