Make Evasion Harder: An Intelligent Android Malware Detection System

1 Introduction

Due to the mobility and ever expanding capabilities, smart phones have been widely used in people's daily life. Android, as an open source and customizable operating system for smart phones, is currently dominating the smart phone market by over 81% [IDC, 2017]. Due to its large market share and open source ecosystem of development, Android attracts not only the developers for producing legitimate Android applications (apps), but also attackers to disseminate malware (malicious software) that deliberately fulfills the harmful intent to the smart phone users. Many examples of Android malware have already been released in the market (e.g., Geinimi, DriodKungfu and Lotoor) which posed serious threats to the smart phone users, such as stealing user credentials and locking user's smart phone until the ransom is paid [Felt et al., 2011]. It's reported that one in every five Android apps were actually malware [Wood, 2015]. The increasing volume and sophistication of Android malware calls for new defensive techniques that are robust and capable of protecting users against novel threats [Burguera et al., 2011; Wu and Hung, 2014; Dimjasevic et al., 2016; Chen et al., 2017a; Ye et al., 2017b].

∗This paper is an abridged version of a paper titled "HinDroid: An Intelligent Android Malware Detection System Based on Structured Heterogeneous Information Network" that won the best paper award and the best student paper award in the applied data science track at the SIGKDD 2017 conference.

†Corresponding author.

To combat the Android malware's evasion tactics, in this paper, instead of using API calls only, we further analyze the relationships among them, e.g., whether the extracted API calls belong to the same code block, are with the same package name, or use the same invoke method, etc. Relations between APIs and apps and different types relations among apps themselves can introduce higher-level semantics and require more efforts for attackers to evade the detection. To represent the rich semantics of relationships, we first introduces a structured heterogeneous information network (HIN) [Sun and Han, 2012] representation to depict apps and APIs. Then we use meta-path [Sun et al., 2011] to incorporate higherlevel semantics to build up the semantic relatedness of apps. Since there can be multiple meta-paths to define different similarities and we want to incorporate all useful meta-paths and discard useless ones, we propose to use a multi-kernel learning algorithm [Vishwanathan et al., 2010] to automatically learn the weights of different similarities from data. We then develop an intelligent system HinDroid for automatic Android malware detection. Promising experimental results based on the real sample collection from Comodo Cloud Security Center demonstrate the effectiveness and efficiency of HinDroid, which has been incorporated into the scanning tool of Comodo Mobile Security product.

2 SystemArchitecture

The system architecture of HinDroid is shown in Figure 1, which consists of the following five major components.

• Unzipper and Decompiler: It first unzips each Android Application Package (APK) to get the dex file, and then generates the smali codes by decompiling the dex file. Dex [Hou et al., 2017] is a file format which contains compiled code written for Android and can be interpreted by the DalvikVM, but it is unreadable. We need to convert the dex file to a readable format. Smali is an assembler/disassembler for the dex format, which provides us readable

code in smali language. Smali code [Hou et al., 2017] is the intermediate but interpreted code between Java and DalvikVM. Listing 1 shows a segment of the converted smali code from a ransomware "Locker.apk" that will lock user's smart phone until the ransom is paid.

• Feature Extractor: As API calls can be used to represent the behaviors of an Android app, it automatically extracts the API calls from the decompiled smali codes generated from the previous component. Based on the extracted API calls, the relationships among them will be further analyzed, i.e., if the extracted API calls belong to the same smali code block, are with the same package name, or use the same invoke method. (See Section 3.1 for details).
• HIN Constructor: This component constructs the HIN based on the features extracted by the previous components. It first builds connections between the apps and the extracted API calls, and defines the types of relationships between these API calls. Then the adjacency matrices among different entity types are constructed, and further the commuting matrices of different meta-paths are enumerated and built. (See Section 3.2 for details.)
• Multi-kernel Learner: Given the commuting matrices from HIN, we build kernels for the Support Vector Machines (SVMs). Using standard multi-kernel learning, the weights of different meta-paths can be optimized. Given the meta-path weights, the different commuting matrices can be combined to formulate a more powerful kernel for Android malware detection. (See Section 3.3 for details.)
• Malware Detector: For each newly collected unknown Android app, it will be first parsed through the unzipper and decompiler to get the smali codes, then its API calls will be extracted from the smali codes, and the relationships among these API calls will be further analyzed. Based on these extracted features and using the constructed classification model, this app will be labeled as either benign or malicious.

3 ProposedMethod

3.1 Feature Extraction

As API calls are used by the Android apps to access operating system functionality and system resources [Tam et al., 2015], they can be used as representations of the behaviors of Android apps [Wu et al., 2012; Peiravian and Zhu, 2013; Yang et al., 2014]. After we unzip and decompile the collected Android apps, the API calls will be extracted from the decompiled smali codes. For example, in the smali code segment shown in Listing 1, the API calls of "Ljava/lang/Runtime; → getRuntime() Ljava/lang/Runtime" , "Ljava/lang/Runtime; → exec (Ljava/lang/String;) Ljava/lang/Process" and "Ljava/lang/Process; → getInputStream() Ljava/io/InputStream"will be extracted. After the extraction of the API calls, to describe the relation (i.e., R0) between app and API, we build the App-API matrix A whose element Aij = aij ∈ {0, 1} denotes if app i contains API j.

Although API calls can be used to represent the behaviors of an Android app, the relations among them can imply important information for malware detection [Ye et al., 2011]. For example, as the aforementioned ransomeware "Locker.apk", the API calls of "Ljava/io/FileOutputStream → write", "Ljava/io/IOException → printStackTrace", and "Ljava/lang /System → load" together in the method of "loadLibs" in the converted smali code indicate this ransomware intends to write malicious code into system kernel. Though it may be common to use them individually in benign apps, they three together in the same method of the converted smali code rarely appear in benign files. Thus, the relationship that these three API calls co-exist in the same method in the converted smali code is an important information for such ransomware detection. To describe such relationships, we define a code block as the code between a pair of ".method" and ".endmethod" in the smali file, which reflects the structural information among the API calls. To represent such kind of relationship R1, we generate the APICodeBlock matrix B where each element Bij = bij ∈ {0, 1}

denotes whether this pair of API calls belong to the same code block. Except for that whether the API calls co-exist in the same code block, we find that API calls which belong to the same package always show similar intent and indicate strong connections among them. For example, the API calls in the package of "Lorg/apache/http/HttpRequest" are related to Internet connection. To represent such kind of relationship R2, we generate the API-Package matrix P where each element Pij = pij ∈ {0, 1} denotes if a pair of API calls belong to the same package. In the smali code, there are five different methods to invoke an API call, which are invoke-static, invoke-virtual, invoke-direct, invoke-super, and invoke-interface. The same invoke method can show the common properties of the API calls (like the words have the same part of speech), which indicate implicit associations among them. To represent this kind of relationship R3, we generate the API-InvokeMethod matrix I where each element Iij = iij ∈ {0, 1} indicates whether a pair of API calls use the same invoke method.

The relationships among the extracted API calls (i.e., whether they belong to the same code block, are with the same package name, or use the same invoke method) create a higher-level representation than a simple list of API calls and require more efforts for attackers to evade the detection (e.g., it may result in execution collapse if the attackers add several non-associated API calls in the same code block).

3.2 HINConstruction

Given the analysis of rich relationship types of API calls for Andriod apps, it is important to model them in a proper way so that different relations can be better and easier handled. When we apply machine learning algorithms, it is also better to distinguish different types of relations. Here, we introduce how to use heterogeneous information network to represent the Andriod apps by using the features extracted above.

Definition 1 [Sun and Han, 2012] A heterogeneous information network (HIN) is a graph G = (V, E) with an entity type mapping φ: V → A and a relation type mapping ψ: E → R, where V denotes the entity set and E denotes the link set, A denotes the entity type set and R denotes the relation type set, and the number of entity types |A| > 1 or the number of relation types |R| > 1. The network schema for network G, denoted as TG = (A,R), is a graph with nodes as entity types from A and edges as relation types from R.

HIN not only provides the network structure of the data associations, but also provides a high-level abstraction of the categorical association. In our application for Android malware detection, we have two entity types (i.e., Android app and API call) and four relation types (i.e., R0-R3). The different types of entities and different relations of APIs motivate us to use a machine-readable representation to enrich the semantics of similarities among APIs. Meta-path [Sun et al., 2011] was used in the concept of HIN to formulate the semantics of higher-order relationships among entities. We follow this concept and extend it to our HinDroid framework.

Definition 2 [Sun et al., 2011] A meta-path P is a path defined on the graph of network schema TG = (A,R), and is denoted in the form of A1 R1 --→ A2 R2 --→ . . . RL --→ AL+1 , which defines a composite relation R = R1 · R2 · . . . · RL between types A1 and AL+1, where · denotes relation composition operator, and L is the length of P.

A typical meta-path P1 for apps is App contains -----→ API contains-1 -------→ App, which means that we want to connect two apps through the path containing the same API over the HIN; another example meta-path P2 is App contains -----→ API same code block ----------→ API contains-1 -------→ App, which denotes that we compute the similarity between two apps not only considering API calls inside, but also considering the type of API calls inside. To measure the similarity over apps using a particular meta-path, we use commuting matrix [Sun et al., 2011] to compute the counting-based similarity matrix for a metapath. Take P1 as an example, the commuting matrix of apps computed using P1 is AAT , while the one for P2 is ABAT .

3.3 Multi-Kernel Learning

Given a network schema with different types of entities and relations, we can enumerate a lot of meta-paths. However, not all of the meta-paths are useful for the particular Android malware detection problem. Here we propose to use a multikernel learning algorithm to automatically incorporate different similarities and determine the weight for each meta-path when classifying apps.

Suppose we have K meta-paths Pk, k = 1, . . . , K. We can compute the corresponding commuting matrices MPk , k = 1, . . . ,K, whereMPk is regarded as a kernel. If the commuting matrix is not a kernel (not positive semi-definite, PSD), we simply use the trick to remove the negative eigenvalues of the commuting matrix. Following [G¨onen and Alpaydin, 2011; Vishwanathan et al., 2010], we use the linear combination of kernels to form a new kernel:

where the weights βk ≥ 0 and satisfy ∑Kk=1 βk = 1. In our application, we then use the p-normmulti-kernel learning framework [Vishwanathan et al., 2010] to learn the weight of each meta-path [Hou et al., 2017].

4 Experimental Results and Analysis

In this section, we evaluate the performance of our developed system HinDroid which integrates the above proposed method for automatic Android malware detection, based on the real sample collection from Comodo Cloud Security Center, which contains 1,834 training Android apps (920 benign and 914 malicious) and 500 testing samples (198 benign and 302 malicious). We use accuracy (ACC) and F1 measure [Hou et al., 2017] for evaluations.

Based on the collected dataset, resting on the 200 extracted API calls and the three different kinds of relationships generated among them (R1-R3 described in Section 3.1), we construct 16 meta-paths (PID1-PID16 shown in Table 1) and compare their detection performances by using SVM. We then use all the meta-paths as the kernels and apply multikernel learning (described in Section 3.3) for Android malware detection (i.e., PID18); for comparison, we also evaluate the combined similarity [Wang et al., 2015] by using the Laplacian scores as the weights for the constructed metapaths to construct a new kernel (i.e., PID17) fed to the SVM. From the results shown in Table 1, it can be observed that (1) different meta-paths indeed show different detection performance, as they provide different similarities with different semantic meanings; (2) by combining different meta-paths using Laplacian scores, it can improve the performance; (3) the method using multi-kernel learning successfully outperforms the single meta-paths and the unsupervised meta-path selection algorithm, i.e., Laplacian score, which demonstrates that multi-kernel learning can successfully filter out the metapaths that do not perform well on the malware prediction problem while maintaining the "good" ones for final decision of malware detection.

To further evaluate the detection performance of HinDriod, (i.e., the system integrating multi-kernel learning based on all the constructed 16 meta-paths - PID18), we also compare HinDroid with other four typical classification methods [Hou et al., 2017] (i.e., Artificial Neural Network (ANN), Naive Bayes (NB), Decision Tree (DT), and SVM), based on the extracted API calls (denoted as f1) and feature engineering (denoted as f2, i.e., we simply put all HIN-related entities and relations as features for different algorithms to learn). From the results shown in Table 1, we can see that (1) feature engineering helps the performance of machine learning; however, (2) HinDroid further outperforms these alternative classification methods with feature engineering in Android malware detection. The reason behind this is that, in HinDroid we use more expressive representation for the data, and build the connection between the higher-level semantics of the data and the final results.

We also further evaluate the stability and scalability of HinDroid. Figure 2 shows the stability of HinDroid (i.e., using different values of the penalty parameter C ranging from 1 to 105 based on five-fold cross validations); while Figure 3 shows the scalability of HinDroid (i.e., training time with different sizes of the training data sets).

5 SystemDeployment and Operation

Due to its detection effectiveness and efficiency, our developed system HinDroid has already been incorporated into the scanning tool of Comodo's Mobile Security Product. HinDroid has been used to predict the daily sample collection from Comodo Cloud Security Center which contains over 15,000 unknown files per day. Note that Android malware techniques are constantly evolving and new malware samples are produced on a daily basis. To account for the temporal trends of Android malware writing, the training sets of our developed system are dynamically changing to include newly collected apps. Our system HinDroid has been deployed and tested based on the real daily sample collection for around half a year (about 2,700,000 Android apps in total that have either been trained or tested).

6 Conclusion

To combat the Android malware threats, our preliminary works [Hou et al., 2016a; 2016b; Chen et al., 2017a; 2017b;

Ye et al., 2017a] have attempted for automatic Andriod malware detection. To make the attackers evade the detection harder, in this paper, we present a novel Android malware detection framework HinDroid, which introduces a structured HIN representation of Android apps and employ multi-kernel learning to aggregate different similarities formulated by different meta-paths over HIN for classification. Due to its detectionn effectiveness and efficiency, our developed system HinDroid has been incorporated into the scanning tool of Comodo Mobile Security product.

Acknowledgments

The authors would also like to thank the anti-malware experts of Comodo Security Lab for the data collection as well as helpful discussions and supports. The work of S. Hou and Y. Ye is supported by the U.S. NSF Grant (CNS1618629), WV HEPC Grant (HEPC.dsr.18.5) and WVU Research and Scholarship Advancement Grant (844). The work of Y. Song is supported by China 973 Fundamental R&D Program (No.2014CB340304).