1 Introduction
1.1 Contributions
-
We present an architecture for learning flipped data which reflects our main focus in the malware detection system.
-
We propose a label flipping poisoning technique to attack the Android malware detection based on deep learning: where an algorithm is proposed for crafting efficient prototypes so that the attacker can deceive the classification algorithm. In this technique, we use silhouette clustering to find an appropriate sample to flip its label.
-
We introduce a DL-based semi-supervised approach against label flipping attacks in the malware detection system called LSD, which uses label propagation and label spreading algorithms along with CNNs to predict the correct value of labels for the training set.
-
We implement a countermeasure method based on clustering algorithms as a defense mechanism. It is a DL-based semi-supervised approach against label flipping attacks in the malware detection system that improves the detection accuracy of the compromised classifier. In this approach, we use four clustering metrics and validation data to relabeled poisoned labels.
-
We conduct our experiments on two scenarios on three real Android datasets using three feature types compared to the cutting-edge method and deeply analyze the trade-offs that emerge. The source code of the paper is available in GitHub [31].
1.2 Organization of the paper
Notations | Description |
---|---|
AML | Adversarial machine learning |
SSL | Semi-supervised learning |
LSD | Label-based semi-supervised defense |
CSD | Clustering-based semi-supervised defense |
KSSD | KNN-based semi-supervised defense |
GAN | Generative adversarial network |
CNN | Convolutional neural network |
LP | Label propagation |
LS | Label spreading |
RI | Rand index |
MI | Mutual information |
FMI | Fowlkes–Mallows index |
2 Related work
2.1 Defense algorithms against poisoning attacks
2.2 Semi-supervised learning defense algorithms
3 System model and proposed architecture
3.1 Problem definition
3.2 Proposed architecture
4 Proposed attack and defensive solutions
4.1 Classification algorithm
4.2 Attack strategy: Silhouette Clustering-based Label Flipping Attack (SCLFA)
4.3 Defensive strategies
4.3.1 LSD defense
-
Label propagation (LP) LP is a type of semi-supervised ML algorithm that can give a label to the unlabeled sample data. First, LP gives labels a small dataset of samples and makes classifications. In other work, LP aims to propose the labels to the unlabeled data points. That is, LP helps to find the community structure in real complex networks [2]. LP compared to the other practical methods in the literature has much lower processing time and could support a priori information needed about the network structure, and it does not require any knowledge of data point and samples before propagation. However, LP could produce several solutions for each set of data points.
-
Label spreading (LS) LS algorithm is a type of propagation method that can apply the normalized graph Laplacian and soft clamping in an affinity matrix to influence on the labels. It also can diminish the regularization properties of a loss function and make it robust against the noise [18]. LS algorithm repeats on the modified version of a graph of data points and can normalize the edge weights by computing the normalized graph Laplacian matrix.
4.3.2 CSD defense
-
Rand index (RI) Rand measure/index is a statistical index to calculate the similarity between two data clusterings [27]. It is a value between zero and one such that zero indicates that two sets of clustered data do not have any pair point and one indicates that the data clustering is the same. Also, RI can be used to adjust a group for elements that we called them adjusted Rand index. In other words, RI is a metric of the accuracy of two sets of data points, which represents the frequency of occurrence of total pairs. Formally speaking, RI presents the probability of how can we randomly select two pairs \(X_1\) and \(X_2\) in two partitions of the same big set.
-
Mutual information (MI) MI, or information gain, is a measure to realize the amount of information and dependency between two separate variables by observing them [23]. It is a type of entropy of a random variable that can understand the joint distribution of a pair data point which calculates by the product of the marginal distribution of those pair samples. Since the data we are dealing with are fallen in the group of discrete data with discrete distribution, we can calculate the \({\mathcal{I}}\) MI of two jointly discrete random variables \(X_1\) and \(X_2\) as follows:where \(p_{(X_1,X_2)}\) is a joint probability mass function for the two samples of \(X_1\) and \(X_2\) , and \(p_{X_1}\) is a marginal probability of sample \(X_1\) and \(p_{X_2}\) is a marginal probability of sample \(X_2\).$$\begin{aligned} {\mathcal{I}}(X_1,X2)&= \sum _{x_1\in X_1}\sum _{x_2\in X_2} p_{(X_1,X_2)}(x_1,x_2)\log _2\\ &\quad\left( \frac{p_{(X_1,X_2)}(x_1,x_2)}{p_{X_1}(x_1)p_{X_2}(x_2)}\right) \end{aligned}$$(4)
-
Homogeneity metric (HM) This metric uses for validating the data points which are members of a single class. HM is independent of being changed the score value of data point when a permutation of the class or labels is applied [14]. We can define HM values as \({\mathcal{HM}}\) as follows:where \({\mathcal{HM}}\) can be between 0 and 1. Note that low values of \({\mathcal{HM}}\) explain a low homogeneity or vice versa. If we have a sample data Y, we define \(Y_{PR}\), \(Y_{T}\) are the predicted and the corrected values for that sample; hence, \(H(Y_{T})\) is the HM value for that sample when it is correctly placed and predicted to be placed in one single class, respectively. Besides, the \(\frac{H(Y_{T}|Y_{PR})}{H(Y_{T})}\) indicates that the predicted sample is not placed correctly in a single class. We aim to approach this fraction smaller and reach it to zero \(({\mathcal{HM}}\rightarrow 1)\). We can achieve this goal when we reduce the knowledge of \(Y_{PR}\) and diminish the uncertainty of \(Y_{T}\) that results in the fraction above become smaller, and we have HM around 1.$$\begin{aligned} {\mathcal{HM}}=1-\frac{H(Y_{T}|Y_{PR})}{H(Y_{T})} \end{aligned}$$(5)
-
Fowlkes–Mallows index (FMI) Fowlkes–Mallows Index (FMI) metric is a popular metric to understand the similarity between two generated clusters, whether hierarchical or benchmark classification clusters [12]. The higher similarity between two clusters (created cluster and the benchmark one) indicates higher FMI values. FMI is an accurate metric used to evaluate the unrelated data and also is reliable even with added noises to the data results.
4.4 Computational complexity
-
Time complexity of SCLFA attack Focusing on SCLFA, the computation of all possible configurations in lines 1–2 of Algorithm 1 creates a model based on the K-means method and predicts the correct n training samples, resulting in \({\mathcal{O}} (n ^ 2\times k)\). Since, in this method, \(k = 2\), the time complexity is in the order of \({\mathcal{O}} (n ^ 2)\). In line 3 of this algorithm, silhouette values are computed for n training data samples, which has a complexity of \({\mathcal{O}} (n ^ 2)\). Lines 4–8 of the algorithm include a for loop that performs the correction of the m validating labels and has a complexity of \({\mathcal{O}} (m)\). Overall, the computational complexity of Algorithm 1 is in the order of \({\mathcal{O}} (n ^ 2) + {\mathcal{O}} (n ^ 2) +{\mathcal{O}}(m)\)=\({\mathcal{O}}(n ^ 2)\), \(\forall \ n \gg m\).
-
Time complexity of LSD defense Focusing on LSD, the computation of Algorithm 2 directly relates to the LS method, which has a complexity of \({\mathcal{O}} (n)\). Similarly, in lines 6–8, the model is based on the LP algorithm, which has a complexity of \({\mathcal{O}} (n)\). Then, lines 9 and 10 present CNN model creating, according to [13], which has a computational complexity of all convolutional layers. CNN computational complexity is \({\mathcal{O}} (\Sigma {^d}_{i=1} {n_{(l-1)}}\times s^2_l \times m^2_l)\), where l is the index of a convolutional layer; d is the depth (number of convolutional layers); \(n_l\) is the width or the number of filters in the \(l_{th}\) layer–\(n_{(l1)}\) is the number of input channels of the l-th layer; \(s_l\) is the spatial size (length) of the filter; and \(m_l\) is the spatial size of the output feature of CNN which has a time complexity in the order of \({\mathcal{O}} (n ^ 3)\). Then, we perform voting between results that has a complexity of \({\mathcal{O}} (1)\) (line 11). Overall, the computational complexity of LSD defense algorithm is \({\mathcal{O}}(n)+{\mathcal{O}}(n)+{\mathcal{O}} (n ^ 3)+{\mathcal{O}} (1)\)=\({\mathcal{O}}(n ^ 3)\).
-
Time complexity of CSD defense Focusing on CSD, the computation of Algorithm 3 relies on CNN model construction based on validation data (lines 1–2). Then, we predict the label for training data samples based on this generated ML model. Therefore, the computational complexity of this part is in the order of \({\mathcal{O}} (n ^ 3)\). Focusing on the RI, MI, HM and FMI clustering metric calculations, they have a complexity of \({\mathcal{O}}(n)\) (lines 4–7). Then, we calculate the values of these parameters for m samples. Hence, the complexity of this loop of the CSD algorithm is in the order of \({\mathcal{O}} (n\times m)\) (lines 8–16). As a result, the overall computational complexity of CSD defense method is \({\mathcal{O}}(n \times m)+{\mathcal{O}}(n ^ 3) +{\mathcal{O}}(n )\)=\({\mathcal{O}}(n^3)\),\(\forall \ n\gg m\).
5 Experimental evaluation
5.1 Simulation setup
5.1.1 Test metrics
-
Accuracy Accuracy metric is defined in:where \(\Omega\) is true positive; \(\chi\) is true negative; \(\Lambda\) is false positive; and \(\nu\) is false negative metrics.$$\begin{aligned} {\hbox{Acc}}=\frac{\Omega +\chi }{\Omega +\chi +\Lambda +\nu } \end{aligned}$$(6)
-
Precision Precision is the fraction of relevant samples between the retrieved samples which is shown in$$\begin{aligned} {\hbox{Precision}}=\frac{\Omega }{\Omega +\Lambda } \end{aligned}$$(7)
-
Recall The recall is expressed in$$\begin{aligned} {\hbox{Recall}}=\frac{\Omega }{\Omega +\nu } \end{aligned}$$(8)
-
F1-score This metric defines as a harmonic mean of precision and recall which is defined as$$\begin{aligned} {\hbox{F1-Score}}&=\frac{1}{\frac{1}{\rm{Recall}}+\frac{1}{\rm{Precision}}} \\ &= 2*\frac{\hbox{Precision}*\hbox{Recall}}{\hbox{Precision}+\hbox{Recall}} \end{aligned}$$(9)
-
False-positive rate (FPR) This metric represents a ratio between the number of negative events incorrectly classified as positive (false positives) and the total number of actual negative events. This metric is described in Eq. (10):$$\begin{aligned} \hbox{FPR}=\frac{\Lambda }{\Lambda +\chi } \end{aligned}$$(10)
-
Area under curve (AUC) AUC measures the trade-off between misclassification rate and FPR. This metric can be calculated as (11):$$\begin{aligned} \hbox{AUC}=\frac{1}{2}\left( \frac{\Omega }{\Omega +\Lambda }+\frac{\chi }{\chi +\Lambda }\right) \end{aligned}$$(11)
-
False negative rate (FNR) This metric is a method for determining the case that the condition does not hold, while in fact it does. In this work, we also called it miss rate. This metrics can be calculated as (12):$$\begin{aligned} \hbox{FNR}=\frac{\nu }{\nu +\Omega } \end{aligned}$$(12)
5.1.2 Datasets
-
Drebin dataset This dataset is an Android example collection that we can apply directly. The Drebin dataset includes 118,505 applications/samples from various Android sources [1].
-
Contagio dataset It consists of 11,960 mobile malware samples and 16,800 benign samples [8].
-
Genome dataset This dataset is an Android example which is supported by the National Science Foundation (NSF) project of the United States. From August 2010 to October 2011, the authors collected about 1200 samples of Android malware from different categories as a genome dataset [16].
5.1.3 Features
-
Permission Permission is a essential profile of an Android application (apk) file that includes information about the application. The Android operating system processes these permission files before installation.
-
API API feature monitors various calls to APIs on an Android OS, such as sending SMS or accessing a user’s location.
-
Intent Intent feature applies to represent the communication between different components which is known as a medium.
5.1.4 Parameter setting
5.1.5 Comparison of defense algorithms
5.2 Experimental results
5.2.1 Comparing methods based on precision, recall, F1-score
5.2.2 Comparing methods based on FPR and accuracy
5.2.3 Comparing methods based on FNR and AUC
Other ML metrics | Datasets | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Ratio (%) | Drebin | Contagio | Genome | ||||||||||
Algorithms | File type | WoFS | WFS | WoFS | WFS | WoFS | WFS | ||||||
FNR | AUC | FNR | AUC | FNR | AUC | FNR | FNR | FNR | AUC | FNR | AUC | ||
Attack | |||||||||||||
SCLFA | Permission | 10.71 | 82.64 | 11.71 | 60.56 | 6.67 | 59.06 | 23.79 | 60.76 | 5.95 | 96.21 | 3.46 | 68.80 |
API | 16.59 | 83.22 | 12.43 | 80.78 | 29.70 | 94.35 | 25.75 | 92.91 | 32.29 | 74.40 | 25.86 | 70.24 | |
Intents | 49.21 | 62.97 | 7.94 | 42.28 | 45.83 | 95.87 | 3.21 | 43.55 | 45.22 | 94.26 | 0.31 | 48.32 | |
Defenses | |||||||||||||
LSD | Permission | 2.17 | 93.90 | 2.33 | 70.77 | 1.65 | 80.32 | 0.81 | 61.64 | 1.29 | 93.89 | 2.05 | 68.65 |
API | 6.62 | 90.77 | 5.65 | 88.44 | 6.59 | 95.34 | 11.13 | 94.03 | 7.40 | 96.59 | 12.15 | 55.23 | |
Intents | 10.20 | 91.97 | 0.43 | 43.70 | 6.28 | 89.42 | 0.75 | 50.07 | 7.27 | 91.82 | 0.53 | 50.41 | |
CSD | Permission | 1.44 | 95.08 | 3.22 | 73.98 | 0.94 | 93.18 | 0.84 | 91.36 | 1.33 | 97.06 | 1.58 | 69.07 |
API | 2.53 | 98.40 | 2.04 | 98.28 | 1.47 | 95.05 | 0.42 | 91.39 | 0.84 | 98.42 | 0.65 | 96.83 | |
Intents | 2 | 93.74 | 0.54 | 45.60 | 1.75 | 93.18 | 0.55 | 50.31 | 1.10 | 94.12 | 0.40 | 51.43 | |
GANX [30] | Permission | 48.95 | 47.00 | 11.06 | 70.93 | 47.91 | 0.54 | 25.28 | 61.19 | 33.62 | 55.49 | 3.51 | 69.14 |
API | 11.11 | 87.37 | 12.46 | 78.92 | 16.96 | 93.80 | 20.78 | 95.58 | 27.26 | 59.77 | 24.78 | 70.76 | |
Intents | 87.35 | 8.96 | 6.99 | 43.50 | 33.46 | 57.75 | 2.10 | 71.60 | 26.36 | 60.84 | 0.57 | 83.29 | |
KSSD [26] | Permission | 4.95 | 91.17 | 11.58 | 70.59 | 3.53 | 61.88 | 25.19 | 90.94 | 5.60 | 90.91 | 3.72 | 68.57 |
API | 10.78 | 86.27 | 12.46 | 78.92 | 19.81 | 94.45 | 23.27 | 94.25 | 19.91 | 72.48 | 24.73 | 71 | |
Intents | 39.10 | 70.93 | 6.91 | 42.39 | 35.11 | 89.02 | 2.35 | 44.58 | 41.79 | 90.04 | 0.30 | 50.51 |
5.2.4 Computational complexity comparisons
Computational complexity | Datasets | ||||||
---|---|---|---|---|---|---|---|
Time (s) | Drebin | Contagio | Genome | ||||
Algorithms | File type | WoFS | WFS | WoFS | WFS | WoFS | WFS |
Attack | |||||||
SCLFA | Permission | 140.09 | 4.04 | 87.66 | 3.56 | 130.10 | 3.11 |
API | 7.14 | 4.71 | 4.84 | 3.88 | 4.21 | 3.74 | |
Intents | 150.99 | 3.83 | 209.89 | 2.87 | 106.07 | 2.92 | |
Defenses | |||||||
LSD | Permission | 385.79 | 101.16 | 417.62 | 107.81 | 348.62 | 106.02 |
API | 123.91 | 114.64 | 117.35 | 112.75 | 109.87 | 105.38 | |
Intents | 963.97 | 105.17 | 747.98 | 96.81 | 501.85 | 108.10 | |
CSD | Permission | 148.15 | 11.50 | 118.77 | 9.51 | 123.45 | 9.16 |
API | 21.76 | 15.77 | 17.22 | 13.27 | 14.56 | 12.77 | |
Intents | 281.83 | 11.26 | 235.24 | 9.21 | 198.63 | 11.42 | |
KSSD [26] | Permission | 95.90 | 5.20 | 83.91 | 4.15 | 90.83 | 5.16 |
API | 9.95 | 7.59 | 8.53 | 6.46 | 8.41 | 6.42 | |
Intents | 210.99 | 5.17 | 206.77 | 4.12 | 146.55 | 5.12 | |
GAN [30] | Permission | 425.13 | 211.64 | 471.33 | 194.55 | 394.65 | 176.38 |
API | 94.23 | 67.45 | 86.56 | 64.75 | 75.34 | 57.14 | |
Intents | 515.41 | 276.54 | 495.32 | 209.21 | 436.97 | 196.45 |