# Graph Neural Network-based Android Malware Classification with Jumping
Knowledge

Wai Weng Lo1, Siamak Layeghy2, Mohanad Sarhan3, Marcus Gallagher4, and
Marius Portmann5  School of Information Technology and Electrical Engineering
The University of Queensland, Brisbane, Australia  Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper presents a new Android malware detection method based on Graph
Neural Networks (GNNs) with Jumping-Knowledge (JK). Android function call
graphs (FCGs) consist of a set of program functions and their inter-procedural
calls. Thus, this paper proposes a GNN-based method for Android malware
detection by capturing meaningful intra-procedural call path patterns. In
addition, a Jumping-Knowledge technique is applied to minimize the effect of
the over-smoothing problem, which is common in GNNs. The proposed method has
been extensively evaluated using two benchmark datasets. The results
demonstrate the superiority of our approach compared to state-of-the-art
approaches in terms of key classification metrics, which demonstrates the
potential of GNNs in Android malware detection and classification.

###### Index Terms:

Graph Neural Networks, Android Malware, Machine Learning

##  I Introduction

Android is the most used widely mobile operating system with 73.0% [1] of the
smartphone market share in November 2021. Due to its open-source nature,
Android provides flexibility for mobile software developers to create custom
Android Application Packages (APKs). However, this has been an effective
method for cybercriminals to create malicious applications to access user
sensitive information such as credit cards and contact information. In
contrast to other closed source platforms such as Apple iOS, hackers can
inspect the application’s source code to develop exploits [2]. Moreover, users
can install untrusted third-party applications on Android devices, allowing
hackers to distribute the malware efficiently. Therefore, mobile anti-malware
solutions are critical for the detection and prevention of mobile malware.

This paper has been accepted for publication in IEEE Conference on Dependable
and Secure Computing, Edinburgh, UK, June 2022. This is an author’s copy, The
respective copyrights are with IEEE.

Traditional anti-malware solutions are mainly based on signature-based
detection techniques [3], which rely on the analysis and comparison of malware
attack signatures to a list of pre-identified signatures. However, this method
of traditional detection methods cannot effectively detect unknown malware
variants, such as zero-day malware. In contrast, Machine Learning (ML)-based
[3] anti-malware approaches can detect unknown malware variants, using both
static and dynamic features such as API calls, permissions [4][5]. In recent
years, anti-malware vendors have tried to apply new ML models and techniques,
particularly deep learning-based approaches, to develop new anti-malware
solutions.

Graph Neural Networks (GNNs) [6] represent one of the most recent and fastest
growing areas in Machine Learning. Their power to capture topological patterns
of graph-based data can be applied in many real-world applications, such as
social media networks, biology, telecommunications, etc. Android Function Call
Graphs (FCGs) consist of a set of program functions and their inter-procedural
calls, which can be extracted from Android Application Package (APK) files and
represented as a graph. The corresponding graph structures can be utilised for
Android malware detection based on graph representation learning. As an
illustration, Figure 1 shows the example of the FCG of SMS malware.

The main problem of ML algorithms [5][7][8][9] is that they require domain
knowledge from experts to extract different types of features which is very
complex and time-consuming. Moreover, those ML methods have not considered the
chain reaction between different function calls, which should be considered.
Therefore, the main motivation of this paper is to perform automatic Android
malware detection and classification by using GNNs based on FCGs without the
use of any handcrafted features.

GNNs are susceptible to the oversmoothing problem[10] and their performance
can degrade significantly with an increase in the number of neural network
layers. To address this problem, we applied the Jumping Knowledge (JK)
technique, which combines intermediate representations and jumping to the last
layers. Our results indicate that the proposed method can outperform the
state-of-the-art approaches in terms of key classification metrics, which
demonstrates the potential of GNNs in Android malware classification, and
provides motivation for further research.

In summary, the key contributions of this paper are:

  * •

The design of an Android malware detection and classification system using a
GNN model with JK technique to capture the topological information embedded in
Function Call Graphs. A key benefit of the approach is that it does not
require handcrafted feature extractions from domain experts.

  * •

The comprehensive evaluation of the proposed framework using two benchmark
datasets demonstrates the superiority via comparison state-of-the-art
approaches.

Figure 1: Example of SMS malware’s FCG

##  II RELATED WORKS

###  II-A Shallow Learning-based Android Malware Classification

Daniel et al. [5] proposed an explainable ML approach to classify Android
malware based on linear Support Vector Machines (SVMs). This approach requires
several features from the APKs, including permissions and sensitive APIs to
identify malware. The extracted feature sets are projected into a joint vector
space for the linear SVM to detect the malware and explain the results. In
[11], a Bayesian classifier was applied to detect Android malware by using 58
defined code-based attributes. The set of 1,000 non-malicious apps and 1,000
malicious apps from 49 different families were used to evaluate the
classifier. In [12], opcode-sequence n-gram features were used for Android
malware classification. The n-gram features were used to train a classifier to
distinguish between benign and malicious APKs. However, this approach is not
robust to bytecode-level obfuscation as the opcode sequences can be directly
altered.

In [8], the authors extracted 11 types of static features from each app and
employed an ensemble classifier which consists of Support Vector Machine
(SVM), K-Nearest Neighbor (KNN), Naive Bayes (NB), Classification and
Regression Tree (CART) and Random Forest (RF) classifiers to distinguish
malicious from benign APKs.

Li et al. [7] proposed SIGPID, which is based on permission usage to detect
Android malware. They mined the permission data using 3-levels of pruning
techniques to identify the most 22 significant permissions as features. A
Support Vector Machine (SVM) approach was used to detect malicious apps. Xu et
al. [13] extract Inter Component Communication (ICC) patterns from the source
code to recognize malware that utilizes inter-component communication to
launch stealthy attacks.

###  II-B Deep Learning-based Android Malware Classification

McLaughlin et al. [14] applied convolution neural networks (CNNs) on the raw
opcode sequences for detecting Android malware. The opcode sequences were
extracted from disassembled apps. Then, the extracted opcode sequences were
encoded as one-hot vectors and fed to an opcode embedding layer for training
the CNNs. [15][16][17] convert malware samples as grayscale images then fed
them to the CNNs for malware detection and classification.

In [18], Android permission sequences were extracted into features through
word embedding using an LSTM model. The word embedding was fed into a fully
connected layer with a Sigmoid activation function for malware detection. In
[4], the API features were mapped to the hand-refined graph matrix as input
for the CNN classifier. The API feature selection was based on API occurrence
frequency between benign and malware. The results demonstrated that the top 20
API calls can achieve a high F1 score of 94.3% in Android malware detection.
Bai et al. [9] applied a Fast Correlation-Based Filter (FCBF) on the n-grams
of opcodes in order to reduce feature dimensionality and perform malware
detection.

###  II-C Android Malware Detection based on Graph Representation Learning

In [19], the authors generated OpCode graphs from the execution files and used
the Power Iteration method to embed the graph into a low dimensional feature
space, to serve as input for ML algorithms such as k-nearest neighbour (KNN)
and support vector machine (SVM) to perform malware classification. A similar
approach was used by Hashem et al. [20] who applied graph embedding techniques
for Android malware classification. The API call graphs were transformed into
a lower dimensional space using graph embedding techniques such as HOPE [21]
and SDNE [22]. The extracted graph embedding was then fed to an 1D CNN [23]
for Android malware detection. However, these proposed methods are shallow
encoders that cannot incorporate and leverage node features of the graphs. In
[24], DroidSIFT was proposed for Android malware classification based on the
weighted contextual API dependency graph and the classifier achieved 93%
accuracy on the Genome dataset [25].

In [26], GDroid was proposed for Android malware detection by utilizing word
embedding and GNN techniques. The skip-gram model extracted the features for
graph nodes based on API sequences. The extracted node features were mapped to
the heterogeneous graph to form APP to API relationships to train the GNNs to
detect malicious app nodes. However, the proposed method is transductive,
which cannot generalize zero-day malware and unknown applications, as we
cannot expect every API call to exist in the skip-gram model training phase.
The entire model needs to be retrained if a new API call, which is not part of
the training set, is encountered. Scott et al. [27] proposed MalNet, a large
scale Android malware FCG dataset, and they applied state-of-the-art graph
representation learning approaches such as GIN [28] for Android malware
classification. Among all the methods, Feather and GIN achieved the highest
classification performance.

In contrast, the proposed framework presented in this paper uses an inductive
learning approach, which does not suffer from this limitation.

##  III BACKGROUND

###  III-A Android FCG

Overall, the APKs can be presented by the combination of its methods.
Formally, an FCG is a directed graph $G=(N,E)$, where $N$ is a set of nodes
representing Android API function, and $E$ represents the set of inter-
procedural calls. FCGs can be very useful for Android malware classification.
For example, when an app requires to send an SMS message, it has to perform a
series of API calls on the Android platform. An FGC consists of all possible
execution paths called during its runtime. For example, the app consists of
the steal function, which calls a list of functions to gather sensitive
information such as phone contacts, SMS, the browser’s bookmark, etc. Then,
the sensitive information can be written into an XML file and sent back to the
attacker by using sendData functions.

###  III-B Graph Neural Networks

Convolutional Neural Networks (CNNs) have been very successfully applied to
the image classification problem. However, CNNs cannot be applied to non-
Euclidean data structures. Therefore, GNNs can be thought of as a
generalization of Convolutional Neural Networks to non-Euclidean data
structures [29]. GNNs have recently received a lot of attention due to their
high interpretability via visualization of the graph embeddings [30].

GNNs aim to generate node embeddings [31] which transform the graph nodes to a
low-dimensional embedding space. All node embeddings can be passed through the
readout function (i.e. via taking the mean of all node embeddings) to form the
whole graph embeddings [31], which encode the whole graph into low-dimensional
space for graph classification.

The FCG consists of structural information by modelling a set of functions and
inter-procedural calls. The objects are represented by graph nodes and their
relationships by graph edges. As a result, we can use GNNs for Android malware
classification. In this paper, we evaluated three variants of GNNs for malware
detection and classification, which are described below.

####  III-B1  Graph Convolutional Networks

GCN is the most representative GNN to compute node embeddings by aggregating
neighbour nodes’ features. We consider graph $G=(N,E,A)$, where $N$ represents
the set of nodes and $E$ the set of edges. $|N|$ is the number of nodes in the
graph, and $|E|$ is the number of edges. The adjacency matrix $A$ is an
$N\times N$ sparse matrix with $(i,j)$. Each node has a k-dimensional feature
vector, and $X\in\mathbb{R}^{N\times K}$ represent the feature matrix for all
$N$ nodes. An L-layer GCN [32] consists of $L$ graph convolution layers, and
each of them constructs embeddings for each node by mixing the embeddings of
the node’s neighbours in the graph from the previous layer.

$Z^{l+1}=\sigma\left(X^{l}W_{0}^{l}+\tilde{A}X^{l}W_{1}^{l}\right)$ (1)

where $X^{(l)}\in\mathbb{R}^{N\times K_{l}}$ is the embedding at the $l$-th
layer for all the N nodes and $X^{(0)}=X$. $W^{(l)}$ is the weight matrix that
will be learnt for the downstream tasks. The $\sigma$ is an activation
function that is usually set to be the element-wise ReLU. Let there be $L$
layers of graph convolutions, the output $Z(L)$ is the matrix consists of all
node embeddings after $L$ layer transformations.

####  III-B2 GraphSAGE

The Graph SAmple and aggreGatE (GraphSAGE) algorithm was developed by Hamilton
et al. [33]. In GraphSAGE, unlike GCNs, a fixed size sub-set of node
neighbours are (uniformly randomly) sampled. This allows limiting the space
and time complexity of the algorithm, irrespective of the graph structure and
batch size. Similar to the convolution operation in CNNs, information relating
to a node’s local neighbourhood is collected and used to compute the node
embedding.

At each iteration, the node’s neighbourhood is initially sampled, and the
information from the sampled nodes is aggregated into a single vector. At the
$k$-th layer, the aggregated information $\mathbf{h}_{N(v)}^{k}$ at a node
$v$, based of the sampled neighborhood $N(v)$, can be expressed as follows:

$\mathbf{h}_{\mathcal{N}(v)}^{k}=\text{ AGG
}_{k}\left(\left\\{\mathbf{h}_{u}^{k-1},\forall{u}\in\mathcal{N}(v)\right\\}\right)\
$ (2)

Here, $\mathbf{h}_{u}^{k-1}$ represents the embedding of node $u$ in the
previous layer. These embeddings of all nodes $u$ in the neighbourhood of $v$
are aggregated into the embedding of node $v$ at layer $k$. The aggregators
$AGG$ can be implemented as a mean, pooling or LSTM aggregator function.

The aggregated embeddings of the sampled neighbourhood $\mathbf{h}_{N(v)}^{k}$
are then concatenated with the node’s embedding from the previous layer
$\mathbf{h}_{v}^{k-1}$. After applying the model’s trainable parameters
($\mathbf{W}^{k}$, the trainable weight matrix) and passing the result through
a non-linear activation function $\sigma$ (e.g. ReLU), the layer $k$ node $v$
embedding is calculated, as shown in Equation 3.

$\small\mathbf{h}_{v}^{k}=\sigma\left(\mathbf{W}^{k}\cdot\operatorname{CONCAT}\left(\mathbf{h}_{v}^{k-1},\mathbf{h}_{\mathcal{N}(v)}^{k}\right)\right)$
(3)

The final representation (embedding) of node $v$ is expressed as
$\mathbf{z}_{v}$, which is essentially the embedding of the node at the final
layer $K$, as shown in Equation 4. For the purpose of node classification,
$\mathbf{z}_{v}$ can be passed through a sigmoid neuron or softmax layer.

$\mathbf{z}_{v}=\mathbf{h}_{v}^{K},\ \ \ \ \ \forall v\in\mathcal{V}$ (4)

####  III-B3 Graph Isomorphism Network

Graph Isomorphism Network (GIN) was proposed by Xu et al. [28]. The main
difference between GIN and other GNNs is the message aggregation function part
which is shown below:

$h_{v}^{(k)}=\mathrm{MLP}^{(k)}\left(\left(1+\epsilon^{(k)}\right)\cdot
h_{v}^{(k-1)}+\sum_{u\in\mathcal{N}(v)}h_{u}^{(k-1)}\right)$ (5)

Message passing of traditional GNNs is less powerful than the Weisfeiler-
Lehman (1-WL) [34] algorithm. As the aggregation functions of the GNNs can be
the same as the hash function of the 1-WL algorithm. Thus, update functions
are not necessarily injective. Therefore, GIN [28] was proposed to make the
aggregation function to be injective, as shown in Equation 5, where
$\varepsilon^{(k)}$ is a scalar parameter and MLP stands for a multi-layer
perceptron.

Figure 2: Proposed Framework

##  IV Proposed Framework

Figure 2 shows a high-level overview of our proposed framework for Android
malware classification and analysis. First, the Android malware function
graphs are extracted from the Android APK’s DEX file and fed into different
GNN models for supervised FCG classification training. After the training
process, the GNN models can perform malware detection, type and family
classification based on FCGs. These three steps are explained in the following
subsections.

####  IV-1 FCG Extraction

FCGs consist of rich function graph structures to perform Android malware
classification, which we aim to exploit in our approach. We convert the APK
files to FCGs using Androguard [35], which statically analyzes the APK’s DEX
file to generate FCGs. After the extraction process, the FCGs are used to
train the GNN models for Android malware categories classification.

The FCGs are featureless, i.e. they do not contain of any node or edge
features. In this paper, we perform graph node feature initialization based on
the following graph centralities inspired by [36]. The graph centralities are
standardized as the node features for function graph classification.

  1. 1.

PageRank: PageRank [37] was proposed in [37] and has been successfully applied
to ranking web-pages based on graph-based techniques. The key idea behind
PageRank is that highly linked pages are more influential than pages with few
backlinks, and pages linked by highly influential pages are more important
than pages linked by less important pages. Based on this idea, we adopt
PageRank to calculate the importance factor of each function in the FCGs. The
PageRank of a graph node $n_{i}$ is defined as fellow:

$PR\left(n_{i}\right)=\alpha\sum_{j\in
B\left(n_{i}\right)}\frac{PR\left(n_{j}\right)}{\left|F\left(n_{j}\right)\right|}+\frac{1-\alpha}{N}$
(6)

where $\alpha$ is the damping factor; $N$, the total number of function nodes;
$B\left(n_{i}\right)$, the set of function nodes that links to $n_{i}$; and
$\mid F\left(n_{j}\right)\mid$ is the number of forward links on node $n_{j}.$
In this paper, we apply dumping factor of 0.85 as it is a usually setting
[38].

  2. 2.

In/out degree: The in/out degree of each function nodes in FCGs.

  3. 3.

Node betweenness centrality: Node betweenness centrality [39] measures the
number of times a function node lies on the shortest path between other
function nodes. The betweenness centrality of a function node $v$ is defined
as fellow:

$c_{B}(v)=\sum_{s,t\in V}\frac{\sigma(s,t\mid v)}{\sigma(s,t)}$ (7)

where $V$ is the set of function nodes, $\sigma(s,t)$ is the number of
shortest $(s,t)$-paths, and $\sigma(s,t\mid v)$ is the number of those paths
passing through some function node $v$ other than $s,t$.

####  IV-2 Graph Neural Network Training

In this paper, we evaluate three powerful and effective GNNs in conjunction
with the JK technique [40] for Android malware detection and category
classification based on FCGs, as shown in Fig. 3. Similar to the convolutional
neural network, GNN models of increasing depth perform worse[10]. This is
mainly due to over-smoothing problem [10].

To mitigate the effects of over-smoothing, we applied the JK [40] technique by
using the concatenation layer. The key idea of JK is to select from all of
those intermediate node representations and jump to the last layer for
combining the intermediate node representations, to generate the final node
representation. In this paper, we applied Layer aggregation concatenation to
combine all intermediate node representations
$\left(h_{u}^{(1)},\ldots,h_{u}^{(k)}\right)$ for linear transformation to
compute the final node embeddings $h_{u}^{(final)}$.

The final node representation undergoes global-maximum pooling, which performs
element-wise max-pooling over the final node embeddings $h_{u}^{(final)}$ for
calculating the whole graph embeddings $r^{(i)}$ for function graph
classification. In the following, we describe the model architecture and
relevant hyperparameter settings.

Figure 3: Proposed Graph Neural JK Network Architecture

  1. 1.

GCN-JK: GCN is the most representative graph representation approach, which
obtains the node embedding by aggregating the neighbour nodes’ features. In
this paper, we tried a 6 GCN layer JK network with $\in\\{64,128\\}$ hidden
units to compute the node embedding, and applied max-pooling over the node
embeddings in a graph to compute the graph embedding. We found that a 6 layer
GCN JK network with 128 hidden units performs the best.

  2. 2.

GraphSAGE-JK: GraphSAGE is another recent and relevant GNN method. Unlike GCN,
which considers the entire set of neighbour nodes to obtain the node
embedding, GraphSAGE uses a fixed set of neighbour nodes to reduce memory
requirements. In this paper, we tried a 6 GraphSAGE max-pooling layer JK
network with $\in\\{64,128\\}$ hidden units to compute the node embedding, and
we applied max-pooling over the node embeddings in a graph to compute a whole
graph embedding. We found that a 6 layer GraphSAGE max-pooling JK network with
128 hidden units performs the best.

  3. 3.

GIN-JK: GIN is the most powerful GNN method. Traditional GNNs are less
effective than the 1-WL algorithm [34] due to their injective nature.
Therefore, GIN was proposed to make the aggregation function injective. In
this paper, we used a 6 layer GIN JK network with $\in\\{64,128\\}$ hidden
units and $\epsilon=0$ to compute the node embedding, and we applied max-
pooling over the node embeddings in a graph to compute a whole graph
embedding. We found that a 6 layer GIN JK network with 128 hidden units
performs best.

After the graph embedding computation, the graph embedding can be passed
through a dense layer with 128 units and a ReLU activation function, followed
by a softmax layer for malware detection and classification. In this paper, we
used the Adam optimizer with a learning rate of $\in\\{0.001,0.0001\\}$, which
provided the best results.

##  V Experimental Results

For evaluating the performance of the different GNN models, the standard
metrics listed in Table I are used, where $TP$, $TN$, $FP$ and $FN$ represent
the number of True Positives, True Negatives, False Positives and False
Negatives, respectively.

###  V-A Datasets

For the evaluation, we used two relevant publicly available Android malware
datasets, consisting of different types of malware categories/families.

TABLE I: Evaluation metrics utilised in this study. Metric | Definition
---|---
Recall (Detection Rate) | $\frac{TP}{TP+FN}$
Precision | $\frac{TP}{TP+FP}$
F1-Score | $2\times\frac{Recall\times Precision}{Recall+Precision}$
Accuracy | $\frac{TP+TN}{TP+FP+TN+FN}$

  1. 1.

Malnet-Tiny: Malnet-Tiny is an Android malware FCG dataset that was created by
Scott et al. [27] from Georgia Tech University and the Microsoft APT team. The
dataset consists of 4,500 malicious FCGs, belonging to four different malware
categories, and 500 benign FCGs. We follow the approach for training,
validation, and testing split (70/10/20), as specified by the authors.

  2. 2.

Drebin: Drebin [5] is an Android malware dataset that includes 5,560 APKs from
179 different malware families. The dataset was collected during the period of
August 2010 to October 2012. Since Drebin only consists of malware samples, we
also download 12,686 benign APK files from AndroZoo [41], a large-scale APK
repository, with samples collected from 2013 to 2019 for the malware detection
experiments. The dataset only consists of malware family labels rather than
category labels. Thus, we only perform malware family classification. We list
the top 24 malware families and perform malware family classification for
those top families. For these experiments, we randomly split the combined and
Drebin datasets into 70% for training and 30% for testing.

###  V-B Malnet-Tiny Classification Results

TABLE II: Malnet-Tiny Multiclass classification results.

Method | Accuracy | Precision | F1-Score | Recall
---|---|---|---|---
GCN-JK | 89.70% | 89.87% | 0.90 | 89.70%
GraphSAGE-JK | 94.40% | 94.53% | 0.94 | 94.40%
GIN-JK | 90.00% | 90.59% | 0.90 | 90.00%

TABLE III: Results of multiclass classification by GraphSAGE-JK on Malnet-Tiny dataset | GraphSAGE-JK
---|---
Class Name | Recall | F1-Score
Benign | 91.00% | 0.88
AdDisplay | 97.00% | 0.97
Adware | 95.00% | 0.95
Downloader | 99.50% | 0.99
Trojan | 89.50% | 0.93
Weighted Average | 94.40% | 0.94

As the Malnet-Tiny dataset only provides the multiclass splitting
configuration, we only perform multiclass experiments in this case. Tables II
and III show the corresponding multiclass results for Malnet-Tiny. In this
experiment, GraphSAGE-JK performed the best. It achieves a very high Weighted-
Recall and F1-Score across 5 application classes (4 malware types plus benign
class), with a Weighted-Recall and Weighted-F1 score of 0.94. The GraphSAGE-JK
model achieved the worst detection performance for the trojan malware class,
with 89.50% detection rate, and the best for the downloader class, with a
detection rate of 99.50%.

TABLE IV: Performance of Malnet-Tiny multiclass classification by JK-Networks compared with the baseline algorithms. Method | Accuracy
---|---
Feather [27] | 86.00%
LDP [27] | 86.00%
GIN [27] | 90.00%
GCN [27] | 81.00%
Slaq-LSD [27] | 76.00%
NoG [27] | 77.00%
Slaq-VNGE [27] | 53.00%
GCN-JK | 89.70%
GIN-JK | 90.00%
GraphSAGE-JK | 94.40%

Table IV shows the average multiclass accuracy of the considered JK-Networks
compared to the baseline results from the literature, provided in [27]. Since
the distribution across various application classes is balanced, we can use
the accuracy as a meaningful performance metric. We observe that GraphSAGE-JK
outperforms all baseline classifiers. Moreover, we observe that, compared with
the original deeper GCN performance [27], our JK-based GCN approach can
improve the original GCN performance from 81.00% to 89.70%.

###  V-C Drebin Classification Results

We are now considering the Drebin dataset. For the evaluation of the Drebin
experiments, we conducted both binary (malware/benign) and multiclass Android
malware classification.

####  V-C1 Binary Classification Results

TABLE V: Drebin Binary classification results.

Method | Accuracy | Macro Precision | Macro F1 | Macro Recall
---|---|---|---|---
GCN-JK | 97.82% | 97.06% | 0.97 | 97.81%
GraphSAGE-JK | 98.00% | 97.49% | 0.98 | 97.77%
GIN-JK | 97.39% | 96.86% | 0.97 | 96.96%

Tables V shows the corresponding malware detection results for the Drebin
dataset. Across all methods, GraphSAGE-JK again performs the best. It achieves
a high detection performance with a recall and F1 score of 97.77% and 0.98,
respectively.

####  V-C2 Multiclass Classification Results

TABLE VI: Drebin Multiclass classification results.

Method | Accuracy | Precision | F1-Score | Recall
---|---|---|---|---
GCN-JK | 95.24% | 95.35% | 0.95 | 95.24%
GraphSAGE-JK | 96.88% | 97.01% | 0.97 | 96.88%
GIN-JK | 95.03% | 95.07% | 0.95 | 95.03%

(a)

(b)

(c)

Figure 4: UMAP visualizations of whole graph embeddings of all three models on
the Drebin dataset. (a) GCN-JK (b) GraphSAGE-JK (c) GIN-JK

(a)

(b)

(c)

Figure 5: UMAP visualizations of whole graph embeddings of all three models on the Malnet-tiny dataset. (a) GCN-JK (b) GraphSAGE-JK (c) GIN-JK  TABLE VII: Results of multiclass classification by GraphSAGE-JK on Drebin dataset | GraphSAGE-JK
---|---
Class Name | Recall | F1-Score
Adrd | 88.89% | 0.87
BaseBridge | 88.89% | 0.93
Boxer | 100.0% | 1.00
DroidDream | 95.83% | 0.96
DroidKungFu | 98.99% | 1.0
ExploitLinuxLotoor | 80.95% | 0.72
FakeDoc | 100.0% | 0.99
FakeInstaller | 98.20% | 0.98
FakeRun | 100.0% | 1.0
Gappusin | 100.00% | 0.97
Geinimi | 100.0% | 1.0
GinMaster | 88.24% | 0.90
Glodream | 84.21% | 0.84
Hamob | 100.0% | 1.0
Iconosys | 100.0% | 1.0
Imlog | 100.0% | 0.96
Jifake | 88.89% | 0.89
Kmin | 100.0% | 1.0
MobileTx | 100.0% | 1.0
Opfake | 99.46% | 0.98
Plankton | 99.46% | 0.99
SMSreg | 100.00% | 0.92
SendPay | 100.0% | 0.97
Yzhc | 100.0% | 0.96
Weighted Average | 96.88% | 0.97

Tables VI and VII show the corresponding multiclass results. Again, GraphSAGE-
JK performed the best. It achieved a Weighted-Recall and F1-Score across 24
malware families of 96.68% and 0.97, respectively. The classification
performance of the top 24 malware families is shown in Table VII—all samples
from the 24 largest malware families in the Drebin dataset.

Table VIII shows the average multiclass accuracy and detection rate of the
three considered GNN JK-Networks compared with the state-of-the-art. We
observe that GraphSAGE-JK outperforms most other approaches in terms of
accuracy.

TABLE VIII: Performance of Drebin malware detection by JK-Networks compared with the baseline algorithms. Method | Accuracy | Detection Rate
---|---|---
Drebin [5] | 93.90% | 94.00%
ICC [13] | 97.40% | 93.10%
FAMD [9] | 97.40% | 96.77%
GCN-JK | 97.82% | 97.81%
GIN-JK | 97.39% | 95.86%
GraphSAGE-JK | 98.00% | 97.20%

##  VI Learned Feature Representation

Finally, we provide a visualization of the graph embeddings of all three
models after a dense layer non-linear transformation by using the UMAP [42]
dimensionality reduction. Figure 4 shows the UMAP results of the Drebin
dataset. There is no significant difference in class separation among all
three models. The visualization results of the Malnet-Tiny dataset are shown
in Figure 5. It is clear that GCN-JK and GIN-JK (in Figure 5(a) and 5(c))
learn similar representations on Malnet-tiny. While these models perform well
in the detection classes adware and downloader, they are less effective in
distinguishing the other classes. Moreover, in terms of GraphSAGE-JK (in
Figure 5(b)), comparing between two other pairs of models, we can see that a
higher class separability can be achieved.

##  VII Limitations and Future work

The model architecture deployed in the GNN-JK model is limited to reasonably
complex 6-layer JK networks. Since the motivation of this paper is to
investigate the effectiveness of FCGs and GNNs for Android malware detection
and classification, the model we used was not optimized at all. In future
works, it would be interesting to explore other GNN architectures, such as
DeeperGCN [43], EdgePool [44].

Moreover, some existing detection approaches, e.g. [45], also try to use
network flow for Android malware detection. However, they only consider flow
data records independently and fail to detect sophisticated malware (i.e., the
botnet malwares try to launch DDoS attacks to the victims) as a more global
view of the network and traffic flow is required. As a result, it is worth
exploring the edge-based graph neural approaches such as E-GraphSAGE [46],
E-ResGAT [47] to perform Android malware detection based on malicious network
flows and combine with GNN-Based FCG’s approach for Android malware detection.

Furthermore, it is worth exploring explainable graph neural network
algorithms, such as SubgraphX [48], as it can help researchers analyze and
explain the working process of GNNs to detect malware by highlighting
suspicious function call paths for automatic malware forensics.

##  VIII Conclusion

This paper presents a novel approach for automatic malware detection and
analysis based on GNNs with JK. We first used the JK network to detect Android
malware with high detection rates effectively. Our experimental evaluation
based on two benchmark datasets shows that our approach performs exceptionally
well and overall outperforms the baseline ML-based/Graph-based Android malware
classifier. The evaluation results of our initial classifier demonstrate the
potential of a GNN-based approach for Android malware detection and
classification.

## References

  * [1] “Mobile Operating System Market Share Worldwide”  In _StatCounter Global Stats_ URL: https://gs.statcounter.com/os-market-share/mobile/worldwide
  * [2] Parvez Faruki et al.  “Android security: a survey of issues, malware penetration, and defenses”  In _IEEE communications surveys & tutorials_ 17.2 IEEE, 2014, pp. 998–1022
  * [3] Ekta Gandotra, Divya Bansal and Sanjeev Sofat  “Malware analysis and classification: A survey”  In _Journal of Information Security_ 2014 Scientific Research Publishing, 2014
  * [4] Na Huang et al.  “Deep android malware classification with api-based feature graph”  In _2019 18th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/13th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE)_ , 2019, pp. 296–303  IEEE
  * [5] Daniel Arp et al.  “Drebin: Effective and explainable detection of android malware in your pocket.”  In _Ndss_ 14, 2014, pp. 23–26
  * [6] Zonghan Wu et al.  “A comprehensive survey on graph neural networks”  In _IEEE transactions on neural networks and learning systems_ 32.1 IEEE, 2020, pp. 4–24
  * [7] Jin Li et al.  “Significant permission identification for machine-learning-based android malware detection”  In _IEEE Transactions on Industrial Informatics_ 14.7 IEEE, 2018, pp. 3216–3225
  * [8] Wei Wang et al.  “Detecting Android malicious apps and categorizing benign apps with ensemble of classifiers”  In _Future generation computer systems_ 78 Elsevier, 2018, pp. 987–994
  * [9] Hongpeng Bai, Nannan Xie, Xiaoqiang Di and Qing Ye  “Famd: A fast multifeature android malware detection framework, design, and implementation”  In _IEEE Access_ 8 IEEE, 2020, pp. 194729–194740
  * [10] Guohao Li, Matthias Muller, Ali Thabet and Bernard Ghanem  “Deepgcns: Can gcns go as deep as cnns?”  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 9267–9276
  * [11] Suleiman Y Yerima, Sakir Sezer, Gavin McWilliams and Igor Muttik  “A new android malware detection approach using bayesian classification”  In _2013 IEEE 27th international conference on advanced information networking and applications (AINA)_ , 2013, pp. 121–128  IEEE
  * [12] Quentin Jerome, Kevin Allix, Radu State and Thomas Engel  “Using opcode-sequences to detect malicious Android applications”  In _2014 IEEE international conference on communications (ICC)_ , 2014, pp. 914–919  IEEE
  * [13] Ke Xu, Yingjiu Li and Robert H Deng  “Iccdetector: Icc-based malware detection on android”  In _IEEE Transactions on Information Forensics and Security_ 11.6 IEEE, 2016, pp. 1252–1264
  * [14] Niall McLaughlin et al.  “Deep android malware detection”  In _Proceedings of the seventh ACM on conference on data and application security and privacy_ , 2017, pp. 301–308
  * [15] Riaz Ullah Khan, Xiaosong Zhang and Rajesh Kumar  “Analysis of ResNet and GoogleNet models for malware detection”  In _Journal of Computer Virology and Hacking Techniques_ 15.1 Springer, 2019, pp. 29–37
  * [16] Wai Weng Lo, Xu Yang and Yapeng Wang  “An Xception Convolutional Neural Network for Malware Classification with Transfer Learning”  In _2019 10th IFIP International Conference on New Technologies, Mobility and Security (NTMS)_ , 2019, pp. 1–5  DOI: 10.1109/NTMS.2019.8763852
  * [17] Ke He and Dong-Seong Kim  “Malware Detection with Malware Images using Deep Learning Techniques”  In _2019 18th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/13th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE)_ , 2019, pp. 95–102  DOI: 10.1109/TrustCom/BigDataSE.2019.00022
  * [18] R Vinayakumar, KP Soman and Prabaharan Poornachandran  “Deep android malware detection and classification”  In _2017 International conference on advances in computing, communications and informatics (ICACCI)_ , 2017, pp. 1677–1683  IEEE
  * [19] Hashem Hashemi, Amin Azmoodeh, Ali Hamzeh and Sattar Hashemi  “Graph embedding as a new approach for unknown malware detection”  In _Journal of Computer Virology and Hacking Techniques_ 13.3 Springer, 2017, pp. 153–166
  * [20] Abdurrahman Pektaş and Tankut Acarman  “Deep learning for effective Android malware detection using API call graph embeddings”  In _Soft Computing_ 24.2 Springer, 2020, pp. 1027–1043
  * [21] Mingdong Ou et al.  “Asymmetric transitivity preserving graph embedding”  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2016, pp. 1105–1114
  * [22] Daixin Wang, Peng Cui and Wenwu Zhu  “Structural deep network embedding”  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2016, pp. 1225–1234
  * [23] Xiang Zhang, Junbo Zhao and Yann LeCun  “Character-level convolutional networks for text classification”  In _Advances in neural information processing systems_ 28, 2015, pp. 649–657
  * [24] Mu Zhang, Yue Duan, Heng Yin and Zhiruo Zhao  “Semantics-aware android malware classification using weighted contextual api dependency graphs”  In _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_ , 2014, pp. 1105–1116
  * [25] Yajin Zhou and Xuxian Jiang  “Dissecting android malware: Characterization and evolution”  In _2012 IEEE symposium on security and privacy_ , 2012, pp. 95–109  IEEE
  * [26] Han Gao, Shaoyin Cheng and Weiming Zhang  “GDroid: Android malware detection and classification with graph convolutional network”  In _Computers & Security_ 106 Elsevier, 2021, pp. 102264
  * [27] Scott Freitas et al.  “A Large-Scale Database for Graph Representation Learning”  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks_ NeurIPS, 2021
  * [28] Keyulu Xu, Weihua Hu, Jure Leskovec and Stefanie Jegelka  “How powerful are graph neural networks?”  In _arXiv preprint arXiv:1810.00826_ , 2018
  * [29] M.. Bronstein et al.  “Geometric Deep Learning: Going beyond Euclidean data”  In _IEEE Signal Processing Magazine_ 34.4, 2017, pp. 18–42  DOI: 10.1109/MSP.2017.2693418
  * [30] Jie Zhou et al.  “Graph neural networks: A review of methods and applications”  In _AI Open_ 1, 2020, pp. 57–81  DOI: https://doi.org/10.1016/j.aiopen.2021.01.001
  * [31] H Cai, V W Zheng and K C Chang  “A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications”  In _IEEE Transactions on Knowledge and Data Engineering_ 30.9, 2018, pp. 1616–1637  DOI: 10.1109/TKDE.2018.2807452
  * [32] Thomas N Kipf and Max Welling  “Semi-supervised classification with graph convolutional networks”  In _arXiv preprint arXiv:1609.02907_ , 2016
  * [33] William L. Hamilton, Rex Ying and Jure Leskovec  “Inductive Representation Learning on Large Graphs”  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17  Long Beach, California, USA: Curran Associates Inc., 2017, pp. 1025–1035
  * [34] Nino Shervashidze et al.  “Weisfeiler-Lehman graph kernels.”  In _Journal of Machine Learning Research_ 12.9, 2011
  * [35] Anthony Desnos and G Gueguen  “Androguard-reverse engineering, malware and goodware analysis of android applications”  In _URL code. google. com/p/androguard_ 153, 2013
  * [36] Hejie Cui, Zijie Lu, Pan Li and Carl Yang  “On positional and structural node features for graph neural networks on non-attributed graphs”  In _arXiv preprint arXiv:2107.01495_ , 2021
  * [37] Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd  “The PageRank citation ranking: Bringing order to the web.”, 1999
  * [38] Andrea Esuli and Fabrizio Sebastiani  “Pageranking wordnet synsets: An application to opinion mining”  In _Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics_ , 2007, pp. 424–431
  * [39] Ulrik Brandes  “A faster algorithm for betweenness centrality”  In _Journal of mathematical sociology_ 25.2 Taylor & Francis, 2001, pp. 163–177
  * [40] Keyulu Xu et al.  “Representation learning on graphs with jumping knowledge networks”  In _International Conference on Machine Learning_ , 2018, pp. 5453–5462  PMLR
  * [41] Kevin Allix, Tegawendé F Bissyandé, Jacques Klein and Yves Le Traon  “Androzoo: Collecting millions of android apps for the research community”  In _2016 IEEE/ACM 13th Working Conference on Mining Software Repositories (MSR)_ , 2016, pp. 468–471  IEEE
  * [42] Leland McInnes, John Healy and James Melville  “Umap: Uniform manifold approximation and projection for dimension reduction”  In _arXiv preprint arXiv:1802.03426_ , 2018
  * [43] Guohao Li, Chenxin Xiong, Ali Thabet and Bernard Ghanem  “Deepergcn: All you need to train deeper gcns”  In _arXiv preprint arXiv:2006.07739_ , 2020
  * [44] Frederik Diehl  “Edge contraction pooling for graph neural networks”  In _arXiv preprint arXiv:1905.10990_ , 2019
  * [45] Laya Taheri, Andi Fitriah Abdul Kadir and Arash Habibi Lashkari  “Extensible android malware detection and family classification using network-flows and API-calls”  In _2019 International Carnahan Conference on Security Technology (ICCST)_ , 2019, pp. 1–8  IEEE
  * [46] Wai Weng Lo et al.  “E-GraphSAGE: A Graph Neural Network based Intrusion Detection System”  In _arXiv preprint arXiv:2103.16329_ , 2021
  * [47] Liyan Chang and Paula Branco  “Graph-based Solutions with Residuals for Intrusion Detection: the Modified E-GraphSAGE and E-ResGAT Algorithms”  In _arXiv preprint arXiv:2111.13597_ , 2021
  * [48] Hao Yuan et al.  “On Explainability of Graph Neural Networks via Subgraph Explorations”  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 12241–12252  URL: http://proceedings.mlr.press/v139/yuan21c.html