MG-DVD: A Real-time Framework for Malware Variant Detection Based on Dynamic Heterogeneous Graph Learning

1 Introduction

Malware has become one of the largest catastrophes endangering information systems, which consistently permeates and attacks information systems to steal sensitive information, take control of the target system, and collect ransom [Gandotra et al., 2014]. Purifying the network environment and keeping information systems away from malware attacks has become a serious challenge faced by security communities and researchers [Ye et al., 2019].

During the last decade, a large volume of malware detection approaches has been proposed. The existing malware detection methods can be roughly divided into two types: signature-based [Kang et al., 2016; Gaviria de la Puerta and Sanz, 2017; Raff et al., 2018; Zhang et al., 2019; Singh and Singh, 2020] and behavior-based [Pascanu et al., 2015; Sun et al., 2016; Bartos et al., 2016; Zhang et al., 2018; Wang et al., 2019b]. Particularly, signature-based methods rely on feature engineering to manually extract malware fingerprints from known samples, which hardly identify new malware variants [Ye et al., 2019]. Behavior-based detection methods focus on investigating the independent API sequence rather than considering their interactive call relationships, inevitably resulting in high false positives and expensive time cost [Zhang et al., 2020].

∗Corresponding Author

†Corresponding Author

Indeed, most malware will perform variants over time to evade detection, and their malicious behaviors are triggered in a very short time [Wang et al., 2019b]. As shown in Figure 1, the malicious behaviors of "kdevtmpfsi" are submitted between 54s and 86s. However, the existing detection approaches cannot meet the dynamic detection requirements and misjudge malicious behaviors as benign. In summary, the existing malware detection approaches expose three major challenges. First, they [Wang et al., 2019b; Chen et al., 2018; Wu et al., 2019] are inefficient to indiscriminately retrain the entire graph whenever a new node or event is injected, resulting in their incapacity of detecting malware variants in real time. Second, static random walk strategy [Wang et al., 2019b; Fu et al., 2017; Fan et al., 2018] often generates a large search space since long-term walks for all nodes, causing an expensive and unacceptable time cost. Third, featurebased [Kang et al., 2016; Gaviria de la Puerta and Sanz, 2017; Raff et al., 2018; Zhang et al., 2019; Pascanu et al., 2015; Sun et al., 2016; Bartos et al., 2016; Zhang et al., 2018] and metapath-based [Wang et al., 2019b] detection approaches are incapable of characterizing high-order and expressive representations of malware variants.

To tackle these challenges, we present a novel MetaGraphguided Dynamic Variant Detection (MG-DVD) framework based on dynamic heterogeneous graph learning, which models execution events stream of the target variant into a series of dynamic heterogeneous graphs and identifies the variant in a real-time and interpretable way. The contributions of this paper are summarized as follows:

• We propose a dynamic detection framework, namely MG-DVD, consisting of two encoders involving DWIUE and CHGAE. MG-DVD utilizes the overlapping information of adjacent sliding windows to dynamically generate graph embedding, which provides malware warnings in real time to keep information systems frommalicious intrusions.
• MG-DVD implements an efficient dynamic walk strategy, which concentrates on the newly injected nodes in the heterogeneous graph at the target sliding window and learns their node representations by exploring the emerging meta-graphs between them. As a result, MG-DVD is able to effectively alleviate the pressure of search space and time overhead.
• MG-DVD presents remarkable interpretability by introducing the meaningful meta-graphs depicting interactive
• relationships between malware and corresponding variants, which can effectively learn the evolutionary patterns of variants from different malware families.
• We conduct extensive experiments on large-scale realworld samples. Experimental results verify that our proposed MG-DVD outperforms the state-of-the-art approaches in detecting new malware variants.

2 Preliminary

In this section, we recap important definitions used in our work, such as DHGS, network schema, and meta-graph.

Definition 1. A dynamic heterogeneous graphs sequence (DHGS) over the execution events stream of malware variant is a graph set G={G1, G2,. . . , GT}, each Gt = (Vt, Et) with an entity type mapping φ: Vt → A and a relation type mapping ψ: Et → R, where Vt and Et denote the entity set and the relation set of Gt, respectively, and A and R denote the entity type and relation type, respectively. Among them, |A| > 1, |R| > 1. The network schema [Sun and Han, 2012] of DHGS, denoted as TG = (A, R), is a graph with nodes as entity type from A and edges as relation type from R.

To characterize high-order semantic information and capture the more discriminative malicious patterns of various malware types, we investigate the real-world meta-graphs for dynamic malware variants detection, defined as below:

Definition 2. A meta-graph [Zhao et al., 2017] M is a directed acyclic graph with a single source node ns (i.e., with in-degree 0) and a single target node nt (i.e., with out-degree 0), defined on a DHGS G with schema TG = (A, R), then a meta-graph can be defined as M=(VM, EM, AM, RM, ns, nt), where VM ∈ V, EM ∈ E are constrained by AM ∈ A and RM ∈ R, respectively.

Particularly, Figure 2(a) demonstrates the schema of MGDVD, which consists of 8 types of entities and 10 types of relations. With the schema, we first enumerate all meta-graphs of MG-DVD, which start and end with processes (i.e., P1 and P2). Then the frequency of each meta-graph is measured on large-scale samples, and the final meta-graphs are obtained, as shown in Figure 2(b), which hold high-frequency and rich semantics depicting the evolutionary patterns between malware and their variants.

3 Framework

Figure 3 shows the framework of MG-DVD, which consists of three major components, detailed below.

3.1 Dynamic Heterogeneous Graphs Constructing

MG-DVD models the execution events stream of the malware variant into a DHGS={G1, G2, . . . , GT} with different sliding windows [Wang et al., 2019a]. As shown in Figure 3, Gt can be updated from Gt-1 as the new execution events are joined, and expired events are removed, and then the heterogeneous graph Gt at Wt is obtained, represented as adjacency matrix At. MG-DVD utilizes overlapping information at adjacent sliding windows (e.g., Gt-1 and Gt) to receive richer variant evolution behaviors rather than reconstructing the entire graph under each sliding window, which offers better efficiency. Experimentally, the detection performance depends on the sliding window size (i.e., W) and sliding step (i.e., p), and it is proved that MG-DVD could reach the desired performance when W is set to 60s and p=1/2W.

3.2 Dynamic Graph Learning

Unlike the static frameworks [Chen et al., 2018; Hamilton et al., 2017; Wu et al., 2019], MG-DVD aims to implement a dynamic malware variants detection based on the overlapping information of heterogeneous graphs under adjacent sliding windows. To this end, MG-DVD proposes Dynamic Walk Incremental Updating Encoder (DWIUE) and Combined Hierarchical Graph Attention Encoder (CHGAE), which can discriminatively update or retrain the graph embedding at each target sliding window based on the threshold ∆Vt/Vt. Particularly, given Gt and ∆Vt at sliding window Wt, the graph embedding of Gt can be generated under the two paradigms. On the one hand, if ∆Vt/Vt≤ γ, MG-DVD utilizes DWIUE to straightly assemble the representation matrix based on the strongly correlated hGt-1 and dynamic neighbors; on the other hand, MG-DVD presents CHGAE to partially learn the graph embedding by discriminatively aggregating newly joined neighbors. Our presented dynamic walk strategy only traverses the changed nodes rather than all nodes in the target graph, which markedly alleviates the search space and time cost compared with the static random walk [Fu et al., 2017; Fan et al., 2018]. Definitely, the set of changed nodes on the target graph is denoted as a dynamic node set ∆Vt, which is formalized as below:

where vx and vy are nodes in Vt, ex,y is the relation between them. Et-1\ Et denotes the difference set of Et-1 and Et.

Dynamic Walk Incremental Updating Encoder

As mentioned above, DWIUE focuses on dynamically updating graph embedding when ∆Vt/Vt≤ γ, which involves three major steps: (A) Construct dynamic walk neighbor set; (B) Incrementally fuse representation matrix; and (C) Aggregate graph embedding.

(A) Construct dynamic walk neighbor set Nitv : Given the heterogeneous graph Gt and the meta-graphs M={M1, M2,. . . , M|M|}, the path-relevant neighbor set Nitv of the target process v can be obtained with the guidance of each Mi.

(B) Incrementally fuse representation matrix hitv : As shown in Figure 4(b), a representation matrix of the target process v can be established by fusing hGt-1 at Wt-1 and its new neighbors' feature vectors at Wt, which leverages both the embedding of itself and the information of its new neighbors in Nitv . Innovatively, DWIUE selects the intersection between Nitv and ∆Vt as the meaningful dynamic neighbors, and the representation matrix hitv ∈ Rd×d is expressed as:

where u1 ̸= un ∈ (Nitv ∧∆Vt), and they are sorted by the node types (i.e., process, file, memory, registry, system, mutex, attribute, and network.) and the distance to node v.

(C) Aggregate graph embedding hGt : Actually, different meta-graphs show distinctive contributions in characterizing malware variants. Inspired by [Wang et al., 2019b], we implement a self-attention mechanism to learn the weight of each meta-graph for detecting malware variants. Concretely, the attention weight θi t of Mi is formalized as below.

where i ̸= j ∈ {1,. . . , |M|}, hitv and hjtv denote the node representations of the target process node v under meta-graph Mi and Mj, respectively. Wl and bl are the trainable weight and bias parameters. Naturally, the graph embedding of Gt with different meta-graphs can be aggregated as follows.

Combined Hierarchical Graph Attention Encoder

As shown in Figure 4(c), CHGAE is presented to handle the graph embedding of Gt when threshold ∆Vt/Vt> γ. Particularly, CHGAE also consists of three key steps: (A) Construct dynamic walk neighbor set; (B) Aggregate node embedding; (C) Aggregate graph embedding. Notably, steps (A) and (C) of CHGAE are similar to DWIUE. Here, we detail step (B), which can discriminatively aggregate newly joined and known nodes.

(B) Aggregate node embedding hiK tv : CHGAE calculates the significance of neighbor nodes for representing the target process node v, which specifically selects more important neighbor nodes to represent itself rather than uniformly aggregating its neighbor nodes in Nitv . Formally, the weight of the neighbor node can be defined as:

where Nitv .u[type] denotes the node set whose type is the same as instance u in Nitv , and n depicts u as the n-order neighbor of the target process node v.

Gt evolves from the DHGS = {G1,G2, . . . ,Gt-1}, which contains the previously known nodes before Wt and newly added nodes at Wt. Notably, the known nodes in Gt have been aggregated in Gt-1; thus, CHGAE only learns newly added nodes in Nitv at Wt. As shown in Figure 4(c), the former (K-1) layers of the proposed aggregator only tackle the new neighbors in Nitv , and the last layer aggregates all neighbors in Nitv , which greatly reduces the time cost of node embeddings. The former (K-1) layers can be defined as:

where k ∈ {1, 2,. . . , K-1} denotes the index of the layer, hik tv and hik tu are the feature vectors of target process node v and neighbor node u at the kth layer, respectively, and they can initialize by their state vectors. ϵk is a trainable trade-off parameter. Moreover, the Kth layer of the proposed aggregator is similar to the previous ones, which aggregates all neighbors in Nitv to represent the final node embedding.

3.3 Real-time Detection

In this section, we leverage the Pearson correlation coefficient [Feng et al., 2019] between the target variant and all samples to detect the target variant in real time. Intuitively, the real intentions (e.g., stealing sensitive information, etc.) of the new variant is similar to that of the original malware. Formally, the Pearson correlation coefficient is defined as:

where µhGt and µhGf are expectations of hGt and hGf , respectively. σhGt and σhGt are standard deviations of hGt and hGf , respectively.

MG-DVD outputs the type of the sample with the highest Pearson correlation coefficient exceeded the threshold τ as the detection result. Particularly, if ρ(hGt , hGf )≥ τ, MGDVD continues to slide forward until the two detection results are consistent. Inversely, if the Pearson correlation coefficients with all samples are less than τ, it is essential to slide forward and learn a richer embedding to continue detecting.

Finally, the objective function of dynamic malware variants detection is formulated as below.

where yp=1 if hGp1 and hGp2 are graph embeddings from the same malware; otherwise, label yp=-1. Here, we optimize l with Adam optimizer [Kingma and Ba, 2014].

Table 3: Performance on malware variants detection.

4 Experiments

4.1 Dataset

We collect a large number of real-world executable (PE) files from VirusTotal, 1 which contains the latest Windows malware and variants from Mar 2019 to Oct 2019. Afterwards, the execution events streams dataset of all PE files is captured using the KingKong system, namely ACT-KingKong. 2 More specifically, the sample distribution and basic statistics for our ACT-KingKong dataset are presented in Table 1 and Table 2, respectively. For all samples, we randomly divide the training set, validation set, and test set into 6:2:2.

4.2 Result Analysis

In this section, we validate the effectiveness, efficiency, and interpretability of MG-DVD in detecting malware variants by comparing it with five strong baseline methods, where SVM+RBF [Gaviria de la Puerta and Sanz, 2017], MalConv [Raff et al., 2018] and CNN+BPNN [Zhang et al., 2019] belong to signature-based detection methods, RNN+LR [Pascanu et al., 2015] and MatchGNet [Wang et al., 2019b] belong to behavior-based detection methods. We implement or utilize the source codes shared by the authors and adopt the same parameters in their works.

Effectiveness Evaluation

As shown in Table 3 and Figure 5, our proposed MG-DVD outperforms all baseline methods in terms of all metrics. The improvement of MG-DVD can be attributed to the following traits. First, comparing with feature-based methods (e.g., SVM+RBF, MalConv, RNN+LR, and CNN+BPNN), MGDVD models the fine-grained execution events streams of malware variants into dynamic heterogeneous graphs sequences to effectively learn the evolutionary patterns between malware and their variants. Notably, our MG-DVD achieves a 9-21% improvement in terms of ACC against featurebased methods. Second, compared with MatchGNet, MGDVD implements a metagraph-guided dynamic graph learning method, which can learn more fine-grained representations of malware variants to accurately distinguish the new malware variants. Indeed, MG-DVD generates fewer false positives (i.e., 21) than MatchGNet (i.e., 46), indicating that MG-DVD can relieve alarm fatigue.

1 https://www.virustotal.com.

2 https://github.com/yidun1027/ACT-KingKong.

Efficiency Evaluation

Here we evaluate the efficiency of MG-DVD from two aspects. Firstly, we compare it with its two variants, namely MG-DVDstaticwalk and MG-DVDCHGAE. As shown in Table 4, MG-DVD is 2.18× and 3× faster than MG-DVDstaticwalk in terms of detection time and total time. Moreover, MG-DVD is significantly faster than MGDVDCHGAE since the encoder DWIUE in MG-DVD can skillfully reduce the time for node aggregation compared to the CHGAE. Secondly, we compare MG-DVD with the existing feature-based and metapath-based methods. As we presented in Table 4, feature-based detection methods, such as SVM+RBF, RNN+LR, MalConv, and CNN+BPNN, are faster than MG-DVD due to the fact that they do not consider the complex graph structure from various types of entity and relation. On the contrary, the static MatchGNet is slower than MG-DVD, which means that the metagraph-guided dynamic embedding encoders in our MG-DVD are beneficial to realtime malware variant detection.

Interpretability Evaluation

Figure 6 shows the frequency matrix of the top-k meta-graphs with the largest weights for different types of malware, which improves interpretability for malware variants detection, from which we can learn that: (i) several meta-graphs show crucial significance on detecting all types of malware variants, such as M1, M2, M7, and M8; (ii) several meta-graphs only focus on specific types, such as M13 and M14 are only involved in Virus, which depicts that the Virus is usually active in connecting to the network and infecting files.

• (c) W and p vs. detection time

(d) W and p vs. ACC

Figure 7: Parameter sensitivity.

4.3 Parameter Sensitivity

In this section, we conduct a large volume of experiments to analyze the sensitivity of different parameters in MG-DVD, including the number of layers (i.e., K), dimension of representation matrix (i.e., d), number of hidden neurons, embedding size, window size (i.e., W), and sliding step (i.e., p).

As shown in Figure 7(a), ACC stably increases with K increases from 1 to 3, when K= 4, the framework is more complex, yet has little improvement on the ACC. Moreover, the performance of our MG-DVD is outstanding in terms of accuracy and stability when the dimension of the representation matrix is set to 64. Similarly, as shown in Figure 7(b), our MG-DVD is the most stable and effective when the number of hidden neurons is set to 300 and embedding size = 60. As demonstrated in Figure 7(c), the detection time when p=1/2W is shorter than that of p=W, which can be attributed to adjacent sliding windows having more overlapping behaviors when p=1/2W, reducing the time cost of node retraining. Moreover, the larger W, the less detection time; however, when W is greater than the 60s, the detection time becomes longer because the number of sliding times is fixed when W reaches a certain value (i.e., 60s), but the more neighbors need to walk and aggregate in larger windows, causing more time cost. In addition, in Figure 7(d), we can observe that the improvement of ACC becomes slow after W=60s. Consequently, we set W=60s and p=1/2W in MG-DVD to hold the trade-off between detection accuracy and efficiency.

4.4 Ablation Study

We perform a detailed ablation study comparing different variants of our MG-DVD, investigating the effects of different modules in the model. Table 5 summarizes our experiments. We first evaluate the two metagraph-guided dynamic embedding encoders by comparing MG-DVD with MatchGNet [Wang et al., 2019b], which indicates the importance of the meta-graph and two dynamic embedding encoders (i.e., DWIUE and CHGAE) to improve detection performance. We also study the effect of the dynamic walk strategy by comparing MG-DVD with MG-DVDstaticwalk that only adopted static random walk strategy. Table 5 shows that the dynamic walk strategy in MG-DVD outperforms the existing static random walk strategy since the dynamic walk strategy only traverses the newly added nodes rather than all nodes in the target graph. Additionally, we examine the discriminative effects of each metagraph-guided dynamic embedding encoder by experimenting with MG-DVDCHGAE and MG-DVDDWIUE, respectively. As can be seen from Table 5, the detection accuracy of MG-DVDCHGAE is a significant boost than that of MG-DVDDWIUE, which can be attributed to employing aggregators to aggregate high-order neighborhoods in CHGAE can more effectively capture semantic information than directly expanding the state vector of the target node in DWIUE.

5 RelatedWork

5.1 Signature-basedMalware Detection

There have been numerous studies concerning signaturebased malware detection [Gandotra et al., 2014; Kang et al., 2016; Gaviria de la Puerta and Sanz, 2017; Raff et al., 2018; Zhang et al., 2019; Singh and Singh, 2020]. Concretely, [Kang et al., 2016; Gaviria de la Puerta and Sanz, 2017; Raff et al., 2018] extracted the opcode or bytecode to detect malware, yet they rely on manually extracting features from known malware samples, which hardly identify new types of malware. Zhang et al. [Zhang et al., 2019] presented a hybrid model consisting of CNN and BPNN to extract more advanced malware features from raw opcodes and APIs. However, they are vulnerable to code obfuscation techniques, inevitably leading to a drop in malware variants detection performance.

5.2 Behavior-basedMalware Detection

Recently, extensive studies were implemented on detecting malware based on execution behaviors [Pascanu et al., 2015;

Sun et al., 2016; Bartos et al., 2016; Zhang et al., 2018; Wang et al., 2019b; Zhang et al., 2020]. Pascanu et al. [Pascanu et al., 2015] and Zhang et al. [Zhang et al., 2018] verified that the API sequences of malware are significantly different from that of the legitimate programs, which provides a new avenue for behavior-based malware detection. Nevertheless, these methods ignored the interactive relationships among various malware objects and cannot learn the evolutionary patterns between malware and their variants.

To address the limitations, Wang et al. [Wang et al., 2019b] proposed MatchGNet, and they characterized execution events of malware into a static heterogeneous graph and extracted metapath-based features to detect malware, which can effectively identify the unknown malware from a large number of benign samples. However, MatchGNet exposes two serious deficiencies. First, it focused on learning metapath-based malware features, which is unable to capture high-order and fine-grained malware variant patterns, resulting in a drop in malware variants detection performance and high false positive. Secondly, MatchGNet learned a long-term representation from the static heterogeneous graph, which cannot meet the dynamic detection requirements.

6 Conclusion

In this paper, we proposed MG-DVD, a dynamic malware variants detection framework. MG-DVD first utilized dynamic heterogeneous graphs sequence (DHGS) to model the execution events streams of malware variants and introduced meta-graphs to characterize the interactive relationships between malware objects. To realize real-time malware variants detection, MG-DVD then proposed two dynamic walk-based encoders, which leverages overlapping information between adjacent sliding windows to dynamically learn node embeddings. Finally, MG-DVD trained a Pearson-based model to automatically detect malware variants. Extensive experiments show that MG-DVD is effective and efficient in dynamically detecting new malware variants. In the future, we would expand the MG-DVD to a more high-level dynamic detection method by considering the temporal correlation between various behaviors.

Acknowledgements

This work was supported by the 2020 Industrial Internet Innovation and Development Project-the Key Project of Intelligent Connected Vehicle Safety Inspection Platform (Tender No. TC200H01S), the Opening Project of Shanghai Trusted Industrial Control Platform (TICPSH202003020-ZC), and the Beijing Advanced Innovation Center for Big Data and Brain Computing.