Combineren van statische Android malware detectietechnieken David De Lille
Promotor: prof. dr. ir. Bjorn De Sutter Begeleiders: dr. Bart Coppens, ir. Daan Raman Masterproef ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2013-2014
Combineren van statische Android malware detectietechnieken David De Lille
Promotor: prof. dr. ir. Bjorn De Sutter Begeleiders: dr. Bart Coppens, ir. Daan Raman Masterproef ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2013-2014
VOORWOORD
i
Voorwoord Allereerst wil ik mijn promotor, professor Bjorn De Sutter, en mijn begeleider, Daan Raman, bedanken voor de tijd en energie die zij besteed hebben om deze thesis in goede banen te leiden. Hun motivatie, advies en feedback waren essentieel om dit werk tot een goed einde te brengen. Vervolgens wens ik mijn vrienden Lionel Pigou, Gilles Jacobs en Steven De Ridder te bedanken voor het nalezen van dit document. Al hun suggesties, verbeteringen en opmerkingen waren zeer waardevol. Ten slotte mag ik in dit dankwoord mijn ouders niet vergeten. Zij zijn mij altijd blijven steunen en ik ben immens dankbaar voor het feit dat ze mij de mogelijkheid hebben geboden om te studeren. Ook voor het proe ezen van deze tekst wil ik mijn waardering uiten.
David De Lille, augustus 2014
TOELATING TOT BRUIKLEEN
iii
Toelating tot bruikleen
De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.
David De Lille, augustus 2014
Combineren van statische Android malware detectietechnieken door David De Lille Masterproef ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: computerwetenschappen
Academiejaar 20132014 Promotor: Prof. Dr. Ir. Bjorn De Sutter Begeleiders: Dr. Bart Coppens, Ir. Daan Raman Faculteit Ingenieurswetenschappen Universiteit Gent Vakgroep Elektronica en Informatiesystemen Voorzitter: Prof. Dr. Ir. Jan Van Campenhout
Samenvatting Er bestaan reeds technieken om Android malware op een statische manier te detecteren, maar nog geen manier om deze technieken te combineren. In dit werk wordt onderzocht hoe men automatisch beslissingsbomen kan opstellen die de bestaande detectietechnieken op een e ciënte en eectieve manier hanteren om te beslissen of een onbekende Android applicatie malware bevat.
Trefwoorden malwaredetectie, statische analyse, Android, beslissingsbomen
Combining static Android malware detection techniques David De Lille Supervisor(s): Bjorn De Sutter, Bart Coppens, Daan Raman (NVISO) Abstract— In recent years, malware has become a serious problem for mobile devices, such as smartphones and tablets. Detecting malicious applications is therefore an import topic of research. As such, there already exist a number of techniques that can differentiate malware and goodware apps. However, there has not yet been any research into how these existing techniques can be combined to increase the overall accuracy while also keeping the costs of execution low. The goal of this article is to study how decision trees, that can leverage existing techniques for static malware detection on the Android platform, can be constructed automatically. Keywords— malware detection, static analysis, Android, decision trees
I. I NTRODUCTION Malware is short for “malicious software”; this term is used for any program that executes actions that are undesirable for the owner of the system. Any software that isn’t malware is known as goodware. Examples of undesirable actions are the theft of personal information (e.g. passwords), the interception of financial information (e.g. credit card numbers), the sending of spam messages, and the launching of a Distributed Denial of Service attack. In addition to this, malware for mobile devices can also steal money directly by using the SIM card to send messages to premium numbers. Mobile devices have become an increasingly interesting target for malware in recent years. This is due to the large number of such devices (1.7 billion smartphones and 100 million tablets in 2013[1] ) and the fact that smartphones contain a SIM card that can be used to transfer money directly by sending premium text messages. The Android operating system is by far the most targeted platform, with 97% of new malware in 2013 being designed for Android devices[2] . For this reason, this research has been limited to malware designed for Android. While a number of malware detection techniques for Android already exist, there is not yet a way to combine these methods. The goal for such a system is to increase the accuracy while also limiting the total execution time. In this work, only static techniques be used. These are techniques that will only use information that can be gathered statically; in other words, by only inspecting the file that installs the application. The alternative is called a dynamic technique, where the behaviour of the application is examined by running the application in a sandbox. The reason for this limitation is that static analysis is generally faster than dynamic analysis. The way the techniques will be combined, is by constructing decision trees in which the nodes represent techniques and the leaves correspond to either “goodware” or “malware”. The advantage of this, compared to other combination methods, is that a decision tree only has to be generated once, and also that not all individual techniques have to be used.
II. D ECISION TREES
Decision trees are predictive models that can be used for classification. The entity that is being classified is called a sample. In this case, the samples represent Android applications. A sample has certain attributes that contain the data that will be used by the model to determine the class of the sample. The goal of this article is to study decision trees that can classify samples based on the output of existing malware detection techniques. A decision tree is a directed graph without cycles, in which the leaves represent classes and the internal nodes correspond to attributes. Every edge starts in an internal node and is associated with one or more possible values of the attribute associated with that node. To predict the class of a new sample, the tree has to be traversed from the root node to a leaf, by choosing the right edges. There are several algorithms for constructing decision trees, but they follow the same general procedure. The idea is to start with a collection of samples for which the class is known, called the training set. For this data set, an attribute is chosen using some metric. Then all the samples are redistributed into subsets based on the value of this attribute. The same algorithm is then applied recursively on these subsets. The algorithm stops when all the samples belong to the same class, or when all the samples have identical values for all attributes. These final data sets are assigned the class label that occurs the most often among the samples. For each data set, a new node is added to the decision tree. An internal node is given the name of the chosen attribute for that node. A leaf node carries the name of the predicted class for that data set. When a set is split into subsets, the child nodes are connected to the parent node. Each of these edges carries the values of the attribute that are specific to that subset. The difference between the different algorithms that were tested, is the way an attribute is chosen for a certain data set. The most popular decision tree algorithm is ID3[3] and selects the attribute that contributes the most information about the class when it is examined; it does this by calculating the information gain for each attribute, which is based on the concept of entropy. At every step, the attribute with the highest information gain is
chosen. Frequency of class y in data set T : p(y) =
|(T |y)| |T |
Entropy of data set T : H(T ) = − ∑ p(y) · log2 (p(y)) y∈Y
[
Subset after choosing attribute A : T =
s
s∈S
Information Gain: IG(A, T ) = H(T ) − ∑ H(s) · s∈S
|s| |T |
The metrics for the other algorithms also include a cost for using an attribute. This is meant to model the execution cost of a detection technique. This creates a trade-off between having a high information gain and a low cost. This is a list of the metrics that each of the tested algorithms use to determine which attribute to choose for a data set: ID3[3] : in f ormation gain EG2[4] : (2(in f ormation gain) − 1)/(attribute cost + 1)ω
CS-ID3[5] : (in f ormation gain)2 /attribute cost IDX[6] : in f ormation gain/attribute cost
CSGain[7] : (Nattribute /N) · in f ormation gain − ω · attribute cost The parameter ω, used for EG2 and CSGain, can be adjusted by the user to indicate the relative importance of information gain and cost. N is the amount of samples in the entire training set and Nattribute is the amount of samples in the current data set. Finally, to avoid that a decision tree tries to mimic the training set too closely, two extra conditions are imposed before a data set is split: first of all, the number of samples in the data set has to be high enough, and secondly, a dataset can not be split if the information gain of the chosen attribute is too small. III. S AMPLES The data set consists of 1858 goodware applications and 1590 malware applications. The goodware samples were collected from the top 60 apps in each of the 34 categories of the Google Play store (the official Android app store) using a service called APK Downloader[8] . Two sources were used to gather the mobile malware apps: the Android Malware Genome Project[9] and Contagio Mobile[10] . It is important for testing purposes that each sample is given the correct label; this is called establishing a ground truth. This is not a problem for the malware samples, because these applications are confirmed to contain malicious code by malware analysts. It is possible, however, for the goodware applications to contain malware, but this is unlikely for two reasons: because these applications were in the top-60 of a certain category, meaning that they have been downloaded and tested by a lot of people , and because the Google Play store makes use of the Google Bouncer service that scans all applications for malware. IV. T ECHNIQUES In order to evaluate a classifier, the data set has to be divided into a training set and a test set; this is done using 10-fold cross
validation. First, the data set is randomly split into 10 subsets. Then 10 tests are conducted, each time with a different subset as test set and the 9 other subsets as training set. In these tests, a predictive model is created based on the training set, which is then used to predict the class of the samples in the test set. Afterwards the predicted class is compared to the given class to see how well the classifier performed. Now follows a description of each of the 10 individual detection techniques that were used in this work. A. Adagio The first step of this technique[11] is to construct the Function Call Graph (FCG) of the application. Every node in this graph represents a function and gets assigned a hash value that describes the properties of the functions that are connected to it. Then the number of times each hash value is present in the graph is counted. These values are transformed into a vector that characterizes the application. The vectors of the training set are used to create a predictive model called a Support Vector Machine. This model is then used to classify the vectors of the test set. B. API 1-NN In this technique, based on work by Aafer et al.[12] , the API calls are extracted from the application. Each API call is then hashed and the remainder of this hash value, divided by a given integer N, is taken. A bit vector of siez N is constructed that indicates which remainders did or did not occur. After calculating the vector for all the samples, the nearest-neighbour algorithm is used to predict the class of the test samples. C. AppRiskPred This term is used to describe three very similar techniques (BNB, PNB, and HMNB) that were described in an article by Peng et al.[13] . Each of the three approaches constructs a Naive Bayesian model based on the permissions1 and the category of the samples in the training set. These models don’t assign class labels (goodware or malware), like the previous techniques; they assign a risk score that indicates how dangerous an app might be, compared to other apps. These risk scores were converted to the desired binary class output using a threshold. The optimal threshold was determined by first calculating the risk scores of the training samples and finding the threshold that best classified these samples. D. Contains APK This newly developed technique works by verifying if the application contains an application within itself. The reason for this is that there are certain malware apps that don’t appear to be dangerous at all, but they do have an application package file (APK) inside them. It is the inner APK that contains the malicious code. 1 Every Android application has to request certain permissions in order to make use of protected resources such as the internet connection or the GPS. These permissions have to be declared by the app and are shown to the user before the installation is started.
E. Droidlegacy Introduced by Deshotels et al.[14] , this technique was designed
to detect repackaged malware. This is a type of malware that is created by taking a goodware app and adding malicious code to it. When two applications contain very similar malicious code, they are said to belong to the same malware family. This technique groups the classes of an app into modules that are characterized by their API calls. By comparing training samples of the same malware family, the recurring malicious module can be identified and this will act as a signature for the malware family. Then, every test sample is compared to every signature and a value between 0 and 1 indicates how well the sample fits the signature. The score is then converted to a class prediction using a threshold, similar to the AppRiskPred techniques.
Technique Adagio API 1-NN BNB PNB HMNB Contains APK Droidlegacy Kirin No Permissions Permissions DT
Cost (in s) 18,15 10,53 25,30 25,57 28,20 0,97 63,03 0,60 16,87 16,87
Acc 94,52% 95,48% 77,29% 77,12% 78,42% 64,62% 83,29% 64,32% 47,23% 94,55%
PPV 91,57% 93,93% 74,59% 73,80% 76,77% 95,12% 92,25% 73,34% 46,60% 93,98%
NPV 97,33% 96,86% 79,75% 80,28% 79,82% 60,50% 78,51% 61,73% 81,97% 95,04%
TABLE I R ESULTS INDIVIDUAL TECHNIQUES
F. Kirin This is one of the oldest techniques[15] that can be used for detecting Android malware. The goal of the approach was to inform a user when certain dangerous combinations of permissions are requested by an application. The technique has seven combinations of permissions that are not allowed. If one of these seven rules is triggered, the sample is considered to be malicious. G. Permissions DT This technique, invented for this article, constructs a decision tree to classify the samples. The attributes are the permissions and four boolean values that show if certain types of suspicious behaviour (encryption, dynamic loading, reflection, and native code2 ) take place. This decision tree is used to predict the class of each sample from the test set. H. No Permissions This final technique, also developed for this article, only examines if the sample happens to have no permissions at all. As soon as there are one or more permissions, the predicted class will be malware. The goal of this technique is to quickly be able to say that a sample probably does not contain malware; after all, an application with no permissions is limited in what it can abuse. V. R ESULTS Table I contains the test results for the individual detection techniques. The accuracy shows how many samples were correctly classified. The positive predictive value (PPV), also called the precision, expresses if a positive prediction is likely to be correct or not. The negative predictive value (NPV) represents the credibility of a negative prediction. The accuracy and cost are also represented visually in Figure 1. The techniques API 1-NN, Permissions DT and Adagio offer the best accuracy and have a decent cost. Droidlegacy performs well, but has a very high cost. The tree techniques that are part of AppRiskPred (BNB, PNB, and HMNB) have a below average 2 Regular code for Android applications is called dex-code and is executed in the Dalvik Virtual Machine. Native code is code,written in C or C++, that runs directly on the processor for performance reasons.
Fig. 1. Results individual techniques
result; both in accuracy and cost. Kirin has a bad accuracy but a really small cost. At first glance, Contains APK seems to have a low accuracy, but what is important about this technique is its high PPV, which means that when this technique gives a positive result, the sample is very likely to contain malware. Finally, No Permissions has decent NPV, making it better than average at detecting goodware, but bad at everything else. The results for the decision tree algorithms were obtained for a lot of different combinations of parameters. For each of the those combinations, several tests using 10-fold cross validation were performed. Each of those tests was characterized by an accuracy and an average cost. When one result had a better accuracy and a lower average cost than a second result, then this second result is considered inferior and omitted. This creates what is called a Pareto efficient frontier. A comparison of the five frontiers for each of the decision tree algorithms can be found in Figure 2. Because API 1-NN has an accuracy of more than 95% for only a cost of 10 seconds, there is no point in considering decision trees that have an accuracy lower than that. The algorithm that produced the best results is EG2, followed closely by IDX and CSGain. The two other algorithms, ID3 and CS-ID3, always produced decision trees that have higher costs for an equal or lower accuracy. The best result was generated using the EG2 algorithm and achieves an accuracy of 97,36%, for an average cost of 55,09 seconds. A decision tree, built using the same algorithm and parameters, can be seen in Figure 3.
Fig. 2. Results decision tree algorithms
Fig. 3. Decision tree with the highest accuracy
VI. C ONCLUSION Based on these results we can conclude that it is indeed possible to achieve a higher accuracy by combining individual detection techniques in a decision tree. Of all the decision tree algorithms, the EG2 algorithm boasts the lowest cost for given accuracy more times than any other algorithm. However, IDX and CSGain are not far behind. For every result by the algorithms ID3 and CS-ID3, there is a result by one the three other algorithms that has the same or higher accuracy and a lower cost, making them the worst choices for making cost sensitive decision trees. R EFERENCES [1] Cisco, Visual Networking Index: Forecast and Methodology, 2013-2018, White Paper, June 2014. [2] Victor Chebyshev, Roman Unuchek, SecureList Mobile Malware Evolution: 2013, Kaspersky Security Bulletin, Feb 2014. [3] J. Ross Quinlan, Induction of Decision Trees, Machine learning, vol. 1, nr. 1, pp. 81-106, 1986. [4] Marlon Nez, The use of background knowledge in decision tree induction, Machine learning, vol. 6, nr. 3, pp. 231-250, 1991. [5] Ming Tan, Cost-sensitive learning of classification knowledge and its applications in robotics, Machine Learning, vol. 13, nr. 1, pp.7-33, 1993. [6] Steven W. Norton, Generating Better Decision Trees., Proceedings of the 11th International Joint Conference on Artificial Intelligence, vol. 1, pp. 800-805. 1989.
[7] Jason V. Davis, Jungwoo Ha, Christopher J. Rossbach, Hany E. Ramadan, and Emmett Witchel, Cost-sensitive decision tree learning for forensic classification., Machine Learning: ECML 2006, pp. 622-629. Springer Berlin Heidelberg, 2006. [8] APK Downloader, http://apps.evozi.com/apk-downloader/. [9] Yajin Zhou, Xuxian Jiang, Dissecting Android Malware: Characterization and Evolution, Proceedings of the 33rd IEEE Symposium on Security and Privacy (Oakland 2012), San Francisco, CA, May 2012. [10] Contagio Mobile, http://contagiominidump.blogspot.com. [11] Hugo Gascon, Fabian Yamaguchi, Daniel Arp, Konrad Rieck, Structural detection of android malware using embedded call graphs., In Proceedings of the 2013 ACM workshop on Artificial intelligence and security, pp. 4554. ACM, 2013. [12] Yousra Aafer, Wenliang Du, Heng Yin, DroidAPIMiner: Mining API-level features for robust malware detection in android., In Security and Privacy in Communication Networks, pp. 86-103. Springer International Publishing, 2013. [13] Hao Peng, Chris Gates, Bhaskar Sarma, Ninghui Li, Yuan Qi, Rahul Potharaju, Cristina Nita-Rotaru, Ian Molloy, Using probabilistic generative models for ranking risks of android apps., In Proceedings of the 2012 ACM conference on Computer and communications security, pp. 241-252. ACM, 2012. [14] Luke Deshotels, Vivek Notani, Arun Lakhotia, DroidLegacy: Automated Familial Classification of Android Malware., In Proceedings of ACM SIGPLAN on Program Protection and Reverse Engineering Workshop 2014, p. 3. ACM, 2014. [15] William Enck, Machigar Ongtang, Patrick McDaniel, On lightweight mobile phone application certification., In Proceedings of the 16th ACM conference on Computer and communications security, pp. 235-245. ACM, 2009.
INHOUDSOPGAVE
ix
Inhoudsopgave Voorwoord
i
Toelating tot bruikleen
iii
Overzicht
iv
Extended abstract
v
Inhoudsopgave
ix
Tabel van afkortingen en symbolen
xiii
1 Inleiding
1
1.1
Probleemstelling
1.2
Doelstelling
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Structuur
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2 Achtergrondinformatie 2.1
2.2
2.3
Android
5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.1.1
Software stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.1.2
Applicaties
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.1.3
Beveiligingsmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.1.4
Dex-code en native code
. . . . . . . . . . . . . . . . . . . . . . . .
8
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.1
De nitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.2
Soorten malware
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.3
Botnet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.4
Repackaged malware
. . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.5
Malwarefamilies . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.6
Soorten malwareanalyse
. . . . . . . . . . . . . . . . . . . . . . . .
11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Mobiele malware
Supervised Learning 2.3.1
Algemeen
INHOUDSOPGAVE
x
2.4
2.3.2
Ground Truth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3.3
K-fold cross validation
. . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3.4
Voorbeeld dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.3.5
Beslissingsbomen
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.3.6
K-nearest-neighbours . . . . . . . . . . . . . . . . . . . . . . . . . .
24
Uitgebreide doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3 Literatuuranalyse 3.1
3.2
29
Statische technieken
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.1.1
A Static Assurance Analysis of Android Applications
. . . . . . . .
29
3.1.2
Adagio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.1.3
AppRiskPred
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.1.4
Droidlegacy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
3.1.5
Kirin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.1.6
DroidAPIMiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
Dynamische technieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.2.1
Andromaly
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.2.2
Crowdroid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4 Werkwijze
39
4.1
Verzamelen van technieken . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.2
Standaardisering van de output
4.3
Samples
. . . . . . . . . . . . . . . . . . . . . . . .
39
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.3.1
Goodware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.3.2
Malware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.3.3
Eliminatie van samples . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.3.4
Malwarefamilies . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.3.5
Categorie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.3.6
Goodware recenter dan malware . . . . . . . . . . . . . . . . . . . .
42
4.4
Technieken uitvoeren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.5
Beslissingsbomen genereren
43
4.6
Andere Supervised-Learningalgoritmen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Gebruikte detectietechnieken 5.1
5.2
46
47
Beperkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.1.1
Niet-statische technieken . . . . . . . . . . . . . . . . . . . . . . . .
47
5.1.2
Technieken met voorkennis . . . . . . . . . . . . . . . . . . . . . . .
47
5.1.3
Technieken op Android toestellen
. . . . . . . . . . . . . . . . . . .
48
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Adagio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
Speci eke technieken 5.2.1
INHOUDSOPGAVE
xi
5.2.2
Permissions_DT
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
5.2.3
AppRiskPred
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5.2.4
Droidlegacy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5.2.5
Kirin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
5.2.6
API_1-NN
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
5.2.7
No_Permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5.2.8
Contains_APK . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
6 Evaluatie 6.1
55
Individuele detectietechnieken . . . . . . . . . . . . . . . . . . . . . . . . .
55
6.1.1
Adagio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.1.2
Permissions_DT
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.1.3
AppRiskPred
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.1.4
Droidlegacy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.1.5
Kirin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.1.6
API_1-NN
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.1.7
No_Permissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.1.8
Contains_APK . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
6.1.9
Besluit individuele detectietechnieken . . . . . . . . . . . . . . . . .
61
6.2
Resultaten beslissingsbomen . . . . . . . . . . . . . . . . . . . . . . . . . .
65
6.3
Resultaten andere Supervised-Learningmethoden
67
. . . . . . . . . . . . . .
7 Besluit
73
7.1
Conclusie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
7.2
Praktisch gebruik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
7.3
Mogelijke uitbreidingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
TABEL VAN AFKORTINGEN EN SYMBOLEN
Tabel van afkortingen en symbolen APK
Application Package File
K-NN
K-Nearest-Neighbours
DT
Decision Tree
PVW
Positief Voorspellende Waarde
NVW
Negatief Voorspellende Waarde
Spec
Speci citeit
Sens
Sensitiviteit
ω
parameter gebruikt door de kostgevoelige beslissingsboomalgoritmen EG2 en CSGain om relatieve voorkeur voor nauwkeurigheid of kost uit te drukken
xiii
INLEIDING
1
Hoofdstuk 1 Inleiding 1.1 Probleemstelling Mobiele toestellen vormen een interessant doelwit voor malware, omdat er veel zulke toestellen bestaan (momenteel 1,7 miljard smartphones en 100 miljoen tablets [1]).
Niet
alleen het feit dat malware de klassieke activiteiten van een desktop kan misbruiken, maar ook de toegang tot een simkaart, is een belangrijk aspect. Dankzij de simkaart kan geld rechtstreeks worden gestolen door middel van betalende gesprekken of sms'en. Het probleem dat hier zal onderzocht worden, is het detecteren van mobiele malware. Hiermee wordt bedoeld dat een verzameling applicaties zo goed mogelijk geclassi ceerd moet worden als malware of goodware. In dit eindwerk zal enkel malware op Android worden onderzocht, omdat dit het meest populaire besturingssysteem voor mobiele toestellen is (marktaandeel van 80% [2]) en waarvoor dus ook de meeste malware wordt ontworpen (in 2013 is 97% van de nieuwe mobiele malware voor Android toestellen ontwikkeld [3]). Manuele controle door malwareanalisten geeft in de meeste gevallen het beste resultaat wanneer het aankomt op het aantonen van de aanwezigheid van malware, maar er worden te veel applicaties ontwikkeld om ze alle manueel te onderzoeken en de kost van het analyseren is zeer hoog.
We willen dus een schaalbare manier vinden om automatisch verdachte
applicaties op te sporen. Er bestaan reeds technieken die automatisch Android malware kunnen detecteren, maar op één enkele techniek vertrouwen is meestal geen goede optie.
Een eerste probleem is
1.2 Doelstelling
2
dat een techniek nooit alles kan controleren, dus zelfs indien de nauwkeurigheid van de techniek goed is, bestaan er misschien bepaalde soorten malware die er niet door worden gedetecteerd.
Bovendien is het voor malwareontwikkelaars in dat geval voldoende om
slechts één techniek te omzeilen om ongedetecteerd te blijven.
1.2 Doelstelling Het doel van deze thesis is het onderzoeken van algoritmen die bestaande detectietechnieken van Android malware op een eectieve en e ciënte manier combineren.
Het gebruikte
algoritme moet een model produceren waarmee de klasse van een onbekende applicatie (malware of goodware) kan worden voorspeld en waarbij rekening wordt gehouden met zowel de nauwkeurigheid van detectie als de totale uitvoeringstijd.
In dit werk werd ervoor gekozen om te focussen op beslissingsbomen waarvan de knopen bestaande detectietechnieken voorstellen.
Elke applicatie die deze boom doorloopt zal
in elke interne knoop de bijhorende techniek moeten uitvoeren; de tak die daaruit moet gevolgd worden, wordt bepaald door het resultaat van de uitgevoerde techniek. Er is gekozen voor beslissingsbomen, omdat het niet e ciënt is om alle mogelijke technieken uit te voeren op elk app, zoals nodig is bij andere combinatiemethoden; dit zou te duur zijn in termen van uitvoeringstijd. Welke technieken worden gekozen en de volgorde waarin ze worden uitgevoerd, hangt af van de resultaten van de vorige technieken. Deze manier van werken kan het best worden voorgesteld door een beslissingsboom. Ook is het handig dat het model op voorhand opgesteld wordt, zodat het eigenlijke classi ceren snel kan gebeuren. Ten slotte bestaan er algoritmen om beslissingsbomen op te stellen die ook rekening houden met de kost van de attributen.
Er kan dus onderzocht worden of deze algoritmen een
positieve invloed hebben op de e ciëntie van het resulterende model.
Omdat malware voortdurend verandert en omdat er ook nieuwe technieken worden ontwikkeld, is het niet genoeg om eenmalig zo'n beslissingsboom op te stellen.
Men moet
in staat zijn automatisch een beslissingsboom op te stellen op basis van een verzameling technieken en een gelabelde dataset van Androidapplicaties. Indien een nieuwe techniek wordt geïmplementeerd of indien men de dataset aanpast, kan men het algoritme opnieuw uitvoeren en krijgt men een nieuw model dat rekening houdt met deze nieuwe technieken en/of apps.
1.3 Structuur
3
Het voordeel van deze aanpak is enerzijds dat het voor lange tijd relevant zal blijven. De individuele technieken kunnen misschien wel hun nut verliezen, maar deze kunnen dan vervangen worden door andere technieken. Anderzijds is het ook mogelijk om zeer gespecialiseerde technieken, die enkel bedoeld zijn om zeer speci eke soorten malware te detecteren, te combineren met meer algemene methoden. Elke techniek kan dan beperkt worden tot één basisidee, en het gebruikte algoritme zal zelf bepalen waar in de beslissingsboom deze technieken het best gebruikt kunnen worden. Er zijn echter ook nadelen, namelijk dat het succes van de beslissingsboom afhankelijk is van de kwaliteit van de gebruikte detectietechnieken.
Ook wordt de beslissingsboom
opgesteld met enkel de gemiddelde nauwkeurigheid in gedachten, waardoor met bepaalde randgevallen mogelijk geen rekening gehouden wordt. In Sectie 2.4 (Uitgebreide doelstelling) worden nog een aantal doelen besproken, die niet kunnen worden vermeld zonder de achtergrondinformatie.
1.3 Structuur In hoofdstuk 2 wordt de achtergrond geschetst die nodig is om dit werk correct te kunnen begrijpen. Eerst wordt het Android besturingssysteem besproken, gevolgd door uitleg over malware op dit soort toestellen. Vervolgens wordt uitleg gegeven over de technieken uit de arti ciële intelligentie die zijn gebruikt. Aan het einde van het hoofdstuk worden bepaalde doelen, waarvoor bepaalde achtergrondinformatie nodig is, beter toegelicht. Een overzicht van het bestaande werk op het gebied van detectie van mobiele malware kan gevonden worden in Hoofdstuk 3. Hierbij wordt een onderscheid gemaakt tussen statische en dynamische technieken. Het vierde hoofdstuk bevat een chronologisch overzicht van de werkwijze die is toegepast bij het uitvoeren van het onderzoek. Er wordt ook dieper ingegaan op de manier waarop de Android applicaties zijn verzameld. In hoofdstuk 5 wordt eerst uitgelegd waarom bepaalde soorten technieken niet beschouwd zijn. Daarna volgt een bespreking van de speci eke detectietechnieken, waarvan gebruik is gemaakt, en hun implementatie. Hoofdstuk 6 bevat de testresultaten. Eerst worden de individuele detectietechnieken onderling vergeleken. Dan worden de prestaties van de verschillende beslissingsboomalgoritmen
4
1.3 Structuur
geëvalueerd. Ten slotte worden een aantal andere Supervised-Learningtechnieken toegepast op dezelfde data om de resultaten van de beslissingsbomen mee te kunnen vergelijken. Het laatste hoofdstuk bestaat uit de algemene conclusie, gevolgd door de opmerkingen die nodig zijn om het systeem in een realistische context te gebruiken, en ten slotte een aantal mogelijkheden om dit onderzoek uit te breiden.
ACHTERGRONDINFORMATIE
5
Hoofdstuk 2 Achtergrondinformatie 2.1 Android Android is een open-source besturingssysteem, gebaseerd op de Linux kernel, ontworpen voor mobiele toestellen met touchscreens zoals smartphones en tablets.
Android is mo-
menteel het meest populaire besturingssysteem met een marktaandeel van 80% [2]. Het werd initieel ontwikkeld door Android Inc., dat later overgenomen werd door Google.
De meest recente versie is Android 4.4 met KitKat als codenaam.
De eerste versie van
Android (1.0) werd uitgebracht in september 2008 en KitKat (4.4) werd uitgebracht in oktober 2013.
In de eerste jaren van de ontwikkeling kwam er om de 3 maanden een
nieuwe versie uit; dit is nu teruggezakt tot een nieuwe versie elke 6 maanden.
2.1.1 Software stack Android maakt gebruik van een kernel gebaseerd op de Linux kernel. Bovenop deze kernel bevinden zich C-bibliotheken en de Android runtime. Deze runtime bevat de Dalvik Virtual Machine waarin dex-code, waaruit de meeste applicaties bestaan, gesandboxt worden uitgevoerd.
Dex staat voor Dalvik Executable.
1
kan
Sinds versie 4.4 is ook een
nieuwe runtime toegevoegd, de ART (Android RunTime), die op termijn de Dalvik VM moet vervangen.
De ART is op het moment van schrijven nog altijd optioneel en het
onderzoek in dit eindwerk maakt geen gebruik van deze runtime. Android biedt ook een
1 Een
sandbox is een beveiligingsmechanisme dat gebruikt wordt om de uitvoering van een applicatie af te zonderen van de rest van het systeem.
2.1 Android
6
groot aantal bibliotheken aan in het Application Framework, die gebruikt kunnen worden door de applicaties. Een overzicht van deze software stack is te zien in Figuur 2.1.
2.1.2 Applicaties Alle gebruikerssoftware komt voor onder de vorm van applicaties, ook wel apps genoemd. Deze apps kunnen soms tegen betaling worden gedownload van de Google Play Store, de Amazon Appstore of een andere appstore. In tegenstelling tot Apple iPhones en iPads, is de o ciële appstore niet de enige mogelijke bron van applicaties.
Dit is één van de
redenen waarom er meer malware is voor Android dan voor iOS.
Android applicaties worden opgeslagen in een speciaal bestandsformaat: het APK-formaat. Deze afkorting staat voor application package le. Een APK-bestand is een ZIP-bestand met een vaste structuur van mappen en bestanden, gelijkaardig aan een JAR-bestand voor Java applicaties. Dit bestand bevat alles wat een Android toestel nodig heeft om de app te installeren en uit te voeren. Aangezien een app volledig bepaald wordt door het bijhorende APK-bestand, is het voldoende om enkel dit bestand te onderzoeken op malware.
De
analyse kan dus op een server gebeuren, waardoor de energie- en prestatiebeperkingen van een smartphone worden vermeden.
Bij het uitvoeren van applicaties kan het platform
een invloed hebben op de werking, maar in dit werk worden enkel technieken beschouwd waarbij enkel het bestand zelf gebruikt wordt om te bepalen of een app mogelijk malware bevat; dit aspect is hier dus niet belangrijk.
2.1.3 Beveiligingsmodel Om de veiligheid van het systeem te verhogen, worden alle applicaties uitgevoerd in een sandbox, waardoor ze geen toegang hebben tot de rest van het systeem. Om toch bepaalde features te kunnen gebruiken, moet de applicatie zogenaamde permissies aanvragen. Bij het installeren van de app wordt een waarschuwing getoond met de lijst van alle aangevraagde permissies.
Zo zijn er permissies die de app bijvoorbeeld toegang geven tot de
camera of de GPS, het mogelijk maken om sms te versturen of gebruik te maken van de internetverbinding.
Deze permissies worden opgeslagen in het Android Manifest; dit is
een XML-bestand dat in elke APK aanwezig is en algemene informatie over de applicatie bevat.
2.1 Android
7
Figuur 2.1: Overzicht van de software stack op Android [4]
2.2 Mobiele malware
8
Er zijn ook malwareapplicaties die proberen om beveiligingszwakheden in Android te misbruiken om te ontsnappen uit hun sandbox; dit noemt men privilege escalation. Davi et al. beschrijft de problemen met het Android beveiligingssysteem die dit soort aanvallen mogelijk maken en illustreert het begrip met een proof-of-concept [5]. Het permissiesysteem op Android is echter niet zeer succesvol, omdat zo goed als elke app meerdere permissies nodig heeft om te functioneren, waardoor er een overvloed aan waarschuwingen optreedt, die ertoe leidt dat de gebruiker deze accepteert zonder ze te lezen [6].
2.1.4 Dex-code en native code De meeste applicaties worden geschreven in Java en worden daarna omgezet in Dalvik bytecode (dex-code). Het is ook mogelijk om delen van een app te schrijven in C of C++, om bijvoorbeeld bestaande bibliotheken aan te spreken of indien CPU-intensieve functies nodig zijn. Deze code wordt niet in de Dalvik Virtual Machine uitgevoerd en wordt 'native code' genoemd. Het is uiteraard ook aanwezig in het APK-bestand, maar op een andere plaats dan de dex-code. Dit soort code wordt echter niet vaak gebruikt; volgens een studie uit 2012 maakt slechts 4,25% van alle Android apps gebruik van native code [7].
2.2 Mobiele malware 2.2.1 De nitie Het woord malware komt van malicious software, wat zich letterlijk laat vertalen naar kwaadaardige software. Deze term wordt gebruikt voor alle software die acties uitvoert die ongewenst zijn voor de eigenaar van het systeem. Alle software die geen malware is, wordt goodware genoemd.
Mobiele malware is de naam voor alle malware die speciaal
ontworpen is voor mobiele toestellen. Voorbeelden van ongewenste acties op traditionele systemen zoals desktops zijn onder andere het stelen van persoonlijke gegevens en wachtwoorden, het onderscheppen van bankgegevens en kredietkaartnummers, het versturen van spam of het uitvoeren van DistributedDenial-of-Service-aanvallen. Deze acties zijn ook van toepassing op mobiele toestellen, met nog een aantal andere zoals bijvoorbeeld het versturen van betalende sms'en, het a uisteren van gesprekken of het opvragen van de GPS-locatie van het toestel.
2.2 Mobiele malware
9
2.2.2 Soorten malware Nu volgt een niet-exhaustieve lijst van soorten mobiele malware:
sms trojan: malware die betalende sms'en verstuurt
banking trojan: malware die bankgegevens onderschept
adware: malware die ongewenste advertenties vertoont
spambot: malware die automatisch ongewenste mails of sms'en verstuurt
spyware / keylogger: malware die persoonlijke gegevens verzamelt
ransomware: malware die het toestel blokkeert om losgeld te eisen
backdoors: malware die het mogelijk maakt om de controle van het toestel over te nemen
2.2.3 Botnet Backdoors in mobiele malware worden meestal gebruikt om een botnet op te stellen. Een botnet is een netwerk van malware met als doel bepaalde taken uit te voeren. Dit geeft de ontwikkelaar van de malware in feite controle over een netwerk van duizenden tot miljoenen toestellen, om illegale activiteiten uit te voeren. Sinds kort worden deze botnets
2
zelfs gebruikt om cryptocurrencies zoals Bitcoins te minen .
De werking van een botnet dat spam verstuurt is weergegeven in Figuur 2.2. Eerst wordt malware verspreid die toestellen infecteert (in de afbeelding zijn dit desktops, maar het concept is analoog voor mobiele toestellen). De maker van de malware heeft nu controle over het netwerk van bots. Men kan dan het botnet `huren' tegen betaling om taken uit te voeren zoals het versturen van ongewenste mails.
2 Door
berekeningen uit te voeren die Bitcointransacties verwerken (dit noemt men minen), worden nieuwe bitcoins gecreëerd, die worden vrijgegeven aan de personen die deze berekeningen uitvoeren. Men kan ook een premie toekennen bij het maken van een transactie om de verwerking sneller te laten verlopen; deze premie is een extra drijfveer voor Bitcoinminers om rekenkracht en elektriciteit te investeren.
10
2.2 Mobiele malware
Figuur 2.2: Illustratie van de werking van een botnet [8]
2.2 Mobiele malware
11
2.2.4 Repackaged malware Repackaged malware is een type malware dat niet onderscheiden wordt op basis van zijn acties, maar op het feit dat het is opgesteld uit een bestaande applicatie, waaraan malwarecode is toegevoegd.
Aangezien het eindresultaat eruit ziet als een originele app en ook
dezelfde functionaliteit vertoont, is het gemakkelijker de gebruiker te misleiden en detectie te vermijden.
2.2.5 Malwarefamilies Net zoals voor andere software, ontwikkelen makers van malware geregeld nieuwe versies van hun creaties met grofweg dezelfde functionaliteit. Hierdoor bestaan er veel malwareapplicaties die slechts in beperkte mate van elkaar verschillen. Het gevolg is dat malware kan worden ingedeeld in malwarefamilies. Alle apps in eenzelfde familie noemt men varianten van deze familie.
2.2.6 Soorten malwareanalyse Om malware te detecteren bestaan er verschillende soorten analyses. Ten eerste is er de manuele analyse. Hierbij zal een persoon de werking van de applicatie onderzoeken, mogelijks met de hulp van automatische analyses. Dit soort analyse geeft de beste resultaten, omdat de persoon kan redeneren over de code. Het nadeel is dat dit zeer duur is en dat er te veel malware bestaat om allemaal manueel te onderzoeken. Naast manuele analyse bestaat er ook automatische analyse.
Hiervan bestaan er drie
soorten: statische, dynamische en hybride. Bij statische analyse wordt enkel gekeken naar het bestand zonder het uit te voeren; enkel de code en resources kunnen geïnspecteerd worden om kwaadaardige activiteiten te ontdekken. Dynamische analyse is net omgekeerd: het bestand zal meestal in een sandbox worden uitgevoerd om verdacht gedrag te bestuderen, zonder naar de code of de rest van het bestand te kijken.
Hybride analyse
combineert beide methoden om de voordelen van beide optimaal te benutten. Noch statische, noch dynamische analyse is in staat om op zichzelf alle malware te detecteren. Statische analyse zou kunnen ontweken worden door gebruik te maken van encryptie van de kwaadaardige code of door tijdens de uitvoering code te downloaden van een server, zodat het niet aanwezig is in het bestand. Er kan wel statisch worden gedetecteerd dat er
2.3 Supervised Learning
12 encryptie of dynamisch inladen plaatsvindt.
Bij dynamische analyse ligt het grote probleem vooral in de uitvoerpaden van het programma.
Door de kwaadaardige code bijvoorbeeld enkel uit te voeren indien een be-
paalde datum bereikt is, kan de malware niet dynamisch gedetecteerd worden voor deze datum. Een andere mogelijkheid zou zijn om te controleren op welk platform de applicatie wordt uitgevoerd en enkel de kwaadaardige acties uit te voeren indien het om een gewone smartphone gaat. Ten slotte is er een praktische limiet op de tijd dat elke applicatie kan worden uitgevoerd in de sandbox. Door de kwaadaardige acties uit te stellen tot bijvoorbeeld een kwartier na het opstarten, kan detectie veelal worden ontweken. Algemeen kan wel gesteld worden dat statische analyse sneller is dan dynamische analyse, mede omdat hierbij het volledige systeem niet moet geëmuleerd worden. Ook brengt het uitvoeren van malware zekere gevaren met zich mee, zelfs in een sandbox.
Daarom is
statische analyse altijd minstens even veilig als dynamische analyse.
2.3 Supervised Learning Aangezien het doel van deze thesis is om bestaande technieken te combineren tot een beslissingsboom, wordt in deze sectie een overzicht gegeven van het onderzoeksdomein waaruit dit concept komt.
2.3.1 Algemeen 3
Supervised Learning is een onderdeel van Machinaal Leren , dat als doel heeft de waarde van een onbekende variabele te voorspellen. Dit gebeurt door het opstellen van een predictief model op basis van een verzameling voorbeeldgevallen waarvan de waarde van de gezochte variabele gegeven is; deze verzameling wordt de trainingset genoemd.
Formele beschrijving We gaan uit van een n-dimensionale ruimte
Y.
Hierin zoeken we een functie f, zodat
3 Dit
X1 × · · · × Xn
f : X1 × · · · × Xn → Y
en een 1-dimensionale ruimte
is een onderzoeksdomein van kunstmatige intelligentie dat systemen bestudeert die in staat zijn te leren uit data en ervaringen.
2.3 Supervised Learning
13
X1 × · · · × Xn noemen we een sample en noteren we als x = (x1 , . . . , xn ). van de vector xi noemen we attributen. Een element van Y wordt een label
Een element van De elementen
genoemd en is de variabele die men wenst te voorspellen.
Een sample bestaat dus uit
een vector van attributen en wordt geassocieerd met een label.
De trainingset
T
is een
verzameling van m samples, met gekende labels:
T = {(x(1) , f (x(1) )), . . . , (x(m) , f (x(m) ))} Het opstellen van een predictief model komt overeen met het zoeken naar een functie f, gebaseerd op de trainingdata
Wanneer Indien
Y
Y
T.
een continue verzameling is (bijvoorbeeld
R),
dan spreken we van regressie.
een discrete verzameling is, wordt er van classi catie gesproken. In het geval van
classi catie van Android applicaties, zijn er meestal maar twee mogelijke labels (of klassen): goodware en malware. Regressie kan echter ook nuttig zijn voor malwaredetectie, omdat het kan gebruikt worden om de mate van zekerheid van een voorspelling weer te geven. In plaats van een waarde 0 (voor goodware) of 1 (voor malware) toe te kennen als label, kan een continue waarde tussen 0 en 1 een meer genuanceerde voorstelling geven van de overtuiging dat de sample malware bevat.
Unsupervised Learning Naast Supervised Learning, bestaat er ook Unsupervised Learning. Hierbij hebben de samples geen label en is er ook maar één verzameling samples. De bedoeling is om patronen te herkennen in de gegeven data. Dit kan onder andere gebruikt worden voor clustering en
4
dimensiereductie . Unsupervised learning is slechts in beperkte mate nuttig voor malwaredetectie. Een mogelijk gebruik is een techniek waarbij eerst een grote verzameling applicaties geclusterd wordt om zeer gelijkaardige apps te herkennen; Juxtapp is hier een voorbeeld van [9]. Voor elke cluster kan dan worden nagegaan of sommige applicaties in de cluster mogelijk repackaged malware bevatten.
4 Bij
het uitvoeren van dimensiereductie wordt het aantal willekeurige variabelen verlaagd om de data minder sparse te maken.
2.3 Supervised Learning
14
2.3.2 Ground Truth Wanneer Supervised Learning wordt toegepast, is het zeer belangrijk dat de trainingset correct gelabeld is.
In het geval dat er een aantal malwaresamples als goodware gela-
beld zijn, wordt het model verkeerd opgesteld en kan dit ervoor zorgen dat gelijkaardige malwaresamples onterecht geclassi ceerd worden als goodware. Dit komt overeen met het gezegde 'garbage in, garbage out'. De data waarvan men ervan uitgaat dat alle labels juist zijn, wordt de 'ground truth' genoemd.
2.3.3 K-fold cross validation K-fold cross validation is een manier om een dataset op te splitsen in trainingset en testset. Het is immers niet wetenschappelijk verantwoord om de nauwkeurigheid van een model te testen met samples waarmee het model werd opgesteld; de trainingset en de testset moeten disjunct zijn.
Deze methode werkt door een verzameling samples willekeurig in delen op te splitsen en hiermee
k
testen uit te voeren.
k
(gegeven geheel getal)
Elk van de
k
deelverzamelingen
wordt één keer gebruikt als testset en alle andere keren als deel van de trainingset. Indien
k
gelijk is aan 5, zullen er dus 5 testen zijn, waarbij telkens 1/5 van de samples als
testset en de overige 4/5 als trainingset worden gebruikt. Dit garandeert dat elk sample één keer getest wordt en dat hetzelfde sample nooit tegelijk in training- en testset zit.
Populaire waarden voor
k zijn 2, 10 en n (met n het aantal samples in de volledige dataset).
Deze laatste keuze wordt
leave-one-out cross validation
genoemd, omdat voor elk sample
de hele dataset, behalve het geteste sample, gebruikt wordt als trainingset. Hoe hoger de waarde van grote waarde voor
k,
hoe groter de trainingset en dus hoe beter het model. Een
k leidt echter ook tot een hogere uitvoeringstijd, omdat er meer modellen
moeten opgesteld worden en omdat de trainingsets meer elementen bevatten. Er moet dus een afweging gemaakt worden tussen uitvoeringstijd en betere testresultaten.
Voor dit
werk is altijd 10-fold cross validation gebruikt, omdat dit veruit het meest gebruikt wordt in de academische literatuur en dit dus de beste keuze is om de gevonden resultaten te kunnen vergelijken met ander onderzoek.
2.3 Supervised Learning
15
Speci eke technieken Er bestaan verschillende soorten Supervised-Learningtechnieken die gebruikt kunnen worden, zoals bijvoorbeeld beslissingsbomen, k-nearest-neighbours, neurale netwerken, lineaire regressie en support vector machines. De eerste twee hiervan zijn van groot belang voor dit werk en worden lager in detail uitgelegd. Deze twee secties zijn gebaseerd op de syllabus van het vak Informatiebeheer [10].
2.3.4 Voorbeeld dataset Om de concepten van deze twee speci eke technieken te illustreren wordt voor beide een kort voorbeeld uitgewerkt. Deze waarden zullen opnieuw gebruikt worden in de voorbeelden voor zowel beslissingsbomen als k-nearest-neighbour.
De trainingset (Tabel 2.1) is
de verzameling samples waarvan de labels gegeven zijn. Tabel 2.2 bevat de verzameling ongelabelde samples. In dit geval stellen de samples Androidapplicaties voor en bevatten de attributen informatie die statisch kan worden verzameld uit de APK-bestanden. Het uitvoeren van een Supervised-Learningtechniek zal aan elk ongelabelde sample het label 'goodware' of 'malware' toekennen.
2.3.5 Beslissingsbomen Een beslissingsboom is een boomstructuur waarmee classi catie kan worden uitgevoerd met behulp van Supervised Learning.
De werking ervan lijkt zeer sterk op die van een
owchart, maar dan zonder cycli. Elke interne knoop (niet-bladknoop) komt overeen met een attribuut. Om het label van een sample te voorspellen, begint men in de startknoop en komt men, door telkens de juiste takken te volgen, in een bladknoop terecht. Deze bladknoop geeft dan aan wat de voorspelling is.
Om te weten welke tak moet genomen worden in een bepaalde knoop,
bekijkt men welk attribuut bij deze knoop hoort en welke waarde het sample voor dit attribuut heeft.
Elk tak bevat één of meerdere waarden voor het attribuut, maar deze
verzamelingen zijn disjunct, dus hoeft men enkel de tak te kiezen die bij de gevonden waarde hoort.
Het opstellen van een beslissingsboom gebeurt aan de hand van enkel de trainingset. Er
2.3 Supervised Learning
16
Attributen packages
native code
stuurt sms
encryptie
Label
Sample1
3
ja
ja
ja
Malware
Sample2
2
nee
nee
ja
Goodware
Sample3
1
nee
ja
nee
Goodware
Sample4
2
nee
ja
ja
Malware
Sample5
2
ja
nee
nee
Malware
Sample6
1
ja
nee
ja
Sample7
2
nee
nee
nee
Malware
Sample8
3
ja
nee
nee
Malware
Sample9
2
ja
ja
ja
Malware
Sample10
3
nee
nee
nee
Goodware
Goodware
Tabel 2.1: Voorbeeld trainingset
Attributen packages
native code
stuurt sms
encryptie
Sample11
2
ja
nee
ja
?
Sample12
1
nee
ja
nee
?
Sample13
3
nee
ja
ja
?
Tabel 2.2: Voorbeeld ongelabelde samples
Label
2.3 Supervised Learning
17
bestaan verschillende manieren om beslissingsbomen op te stellen, met het ID3-algoritme [11] als meest bekende.
ID3 In dit algoritme wordt de trainingset recursief in deelverzamelingen opgedeeld totdat alle samples in zo'n deelverzameling hetzelfde label hebben.
Om een dataset op te splitsen,
wordt een attribuut gekozen en worden de samples zo ingedeeld dat elke deelverzameling overeenkomt met een verzameling mogelijke waarden van het gekozen attribuut. Wanneer alle samples in een dataset hetzelfde label hebben, zal de dataset niet meer verder worden opgesplitst. Bij het splitsen van een dataset, wordt gekozen voor het attribuut met de hoogste
mation gain.
infor-
Deze waarde geeft aan hoeveel informatie over het label men te weten komt
door de waarde van een attribuut te kennen. In het beste geval is de information gain gelijk aan de entropie van de trainingset en is het label volledig bepaald door het attribuut; in het slechtste geval is deze waarde 0 en leert de waarde van het attribuut ons niets nieuw over de waarde van het label. Frequentie van label
y
Entropie in trainingset
|(T |y)| |T | X T : H(T ) = − p(y) · log2 (p(y))
in
T : p(y) =
y∈Y
Deelverzameling na splitsen op attribuut
A:T =
[
s
s∈S Information Gain:
IG(A, T ) = H(T ) −
X s∈S
H(s) ·
|s| |T |
Elke dataset komt overeen met een knoop in de beslissingsboom, beginnend met de volledige trainingset die voorgesteld wordt door de startknoop.
Wanneer een attribuut met de
hoogste information gain gekozen wordt om de dataset te splitsen, schrijft men de naam van dit attribuut in de knoop. Daarna worden alle nieuwe deelverzamelingen voorgesteld door kindknopen van de huidige knoop. Elke tak die de ouderknoop met een kindknoop verbindt, wordt benoemd met de overeenkomstige waarde van het attribuut.
Op deze
deelverzamelingen wordt dan recursief hetzelfde algoritme toegepast. Wanneer de samples in een kindknoop alle hetzelfde label hebben, wordt deze knoop een bladknoop en krijgt het de naam van het label.
2.3 Supervised Learning
18
In het speciale geval waarbij de trainingset twee of meer samples bevat met identieke attributen maar met verschillende labels, zal er op een bepaald moment een dataset zijn die enkel nog deze samples bevat. Deze dataset kan niet gesplitst worden (alle attributen zijn identiek) en toch zijn er verschillende labels. In dit geval wordt deze dataset ook een bladknoop en wordt meerderheidsstemming toegepast om het bijhorende label te bepalen.
Voorbeeld Als voorbeeld zal nu een beslissingsboom worden opgesteld voor de trainingset uit sectie 2.3.4 (Voorbeeld dataset), gebruikmakend van het ID3-algoritme.
Stap 1:
volledige trainingset
H(T ) = −4/10 · log2 (4/10) − 6/10 · log2 (6/10) = 0, 971 Uit Tabel 2.3 is duidelijk dat het attribuut `packages' de hoogste information gain heeft. Dit was enigszins te verwachten, omdat dit attribuut drie mogelijk waarden heeft, in tegenstelling tot de andere attributen die er elk twee hebben. De samples van de dataset worden dus gesplitst in drie deelverzamelingen, naargelang het aantal packages in de applicatie. De startknoop van de beslissingsboom krijgt de naam packages en heeft drie kindknopen. Ook is op te merken dat het attribuut encryptie information gain nul heeft. Dit is omdat er in de initiële dataset 40% goodwaresamples zijn en dit ook het geval is voor de 2 deelverzameling die men verkrijgt wanneer men de dataset opsplitst op basis van dit attribuut. Attribuut Information Gain
packages
native code
stuurt sms
encryptie
0,3346
0,1245
0,2202
0
Tabel 2.3: Information Gain voor de attributen in Stap 1
Stap 2:
`packages' == 1 (Sample3 en Sample6)
Aangezien alle samples in deze dataset hetzelfde label (Goodware) hebben, wordt deze knoop een bladknoop met naam Goodware.
Stap 3:
`packages' == 2 (zie Tabel 2.4)
H(T ) = −1/5 · log2 (1/5) − 4/5 · log2 (4/5) = 0, 722
2.3 Supervised Learning
19 Attributen
packages
native code
stuurt sms
encryptie
Label
Sample2
2
nee
nee
ja
Goodware
Sample4
2
nee
ja
ja
Malware
Sample5
2
ja
nee
nee
Malware
Sample7
2
nee
nee
nee
Malware
Sample9
2
ja
ja
ja
Malware
Tabel 2.4: Deelverzameling stap 3, voorbeeld beslissingsboom
Attribuut Information Gain
packages
native code
stuurt sms
encryptie
0
0,055
0,181
0,055
Tabel 2.5: Information Gain voor de attributen in Stap 3
In dit geval heeft het attribuut `stuurt sms' de hoogste information gain, zoals te zien is in Tabel 2.5.
Stap 4:
`packages' == 3 (zie Tabel 2.6)
H(T ) = −1/3 · log2 (1/3) − 2/3 · log2 (2/3) = 0, 918
Tabel 2.7 bevat de information gain van de attributen voor deze stap. We zien aan het feit dat de information gain van `native code' gelijk is aan de entropie, dat dit attribuut alle overblijvende onzekerheid over het label wegneemt. Na deze knoop komen er dus twee bladknopen.
Attributen packages
native code
stuurt sms
encryptie
Label
Sample1
3
ja
ja
ja
Malware
Sample8
3
ja
nee
nee
Malware
Sample10
3
nee
nee
nee
Goodware
Tabel 2.6: Deelverzameling stap 4, voorbeeld beslissingsboom
2.3 Supervised Learning
20 Attribuut Information Gain
packages
native code
stuurt sms
encryptie
0
0,918
0,251
0,251
Tabel 2.7: Information Gain voor de attributen in Stap 4
Stap 5:
`packages' == 2 en `stuurt sms' == ja (Sample2 en Sample4)
In deze dataset hebben beide samples dezelfde waarden voor alle attributen; er kan dus niet verder worden gesplitst. De samples hebben wel een verschillend label (ondanks dezelfde attributen te hebben), wat wijst op een probleem met de trainingset.
Normaal gezien
wordt in dit geval meerderheidsstemming toegepast om een waarde toe te kennen aan deze bladknoop, maar aangezien beide labels elk één keer voorkomen, kan de waarde hier gekozen worden. Omdat een
false positive
(goodwaresample dat onterecht als malware wordt
gelabeld) minder negatieve gevolgen heeft dan een
false positive
(malwaresample dat on-
terecht als goodware wordt gelabeld), wordt ervoor gekozen om voor deze deelverzameling een `Malware'-bladknoop aan te maken.
Stap 6:
`packages' == 2 en `stuurt sms' == nee (Sample5, Sample7 en Sample9)
Alle samples in deze deelverzameling zijn malwaresamples, dus krijgt de bijhorende bladknoop het label `Malware'.
Stap 7:
`packages' == 3 en `native'` == ja (Sample1 en Sample8)
Ook deze verzameling bevat enkel malwaresamples, en er wordt dus een 'Malware'-bladknoop aan de beslissingsboom toegevoegd.
Stap 8:
`packages' == 3 en `native' == ja (Sample10)
Ten slotte bestaat deze laatste dataset uit één enkel goodwaresample, dus krijgt de bijhorende bladknoop het label `Goodware'.
De resulterende beslissingsboom is te zien in Figuur 2.3. Nu de beslissingsboom opgebouwd is, kunnen voorspellingen gemaakt worden voor de drie ongelabelde samples uit sectie 2.3.4 (Voorbeeld dataset). De toegekende labels worden weergegeven in Tabel 2.8.
C4.5 Het C4.5-algoritme [12] is de opvolger van het ID3-algoritme, dat een aantal van de tekortkomingen probeert aan te pakken. Een eerste probleem is dat ID3 voorkeur geeft aan
2.3 Supervised Learning
21
Figuur 2.3: Voorbeeld ID3-beslissingsboom
Attributen packages
native code
stuurt sms
encryptie
Label
Sample11
2
ja
nee
ja
Sample12
1
nee
ja
nee
Goodware
Sample13
3
nee
ja
ja
Goodware
Malware
Tabel 2.8: Voorspellingen beslissingsboom voorbeeld
2.3 Supervised Learning
22
attributen met veel verschillende waarden, omdat deze attributen logischerwijze een hogere information gain hebben. Dit wordt opgelost door bij elke opsplitsing de verzameling waarden voor een attribuut in te delen in twee groepen. Er vertrekken dus twee takken uit elke interne knoop. Deze aanpassing maakt het ook mogelijk om continue waarden toe te laten voor de attributen, waar vroeger enkel nominale waarden toegelaten werden. Dit heeft wel als gevolg dat er meerdere keren op hetzelfde attribuut kan worden gesplitst. Een tweede probleem dat wordt aangepakt, is dat er daarom
pruning
over tting 5
kan optreden. C4.5 past
toe, dat bepaalde subgrafen van de boom vereenvoudigt tot een blad-
knoop. Dit zorgt er (meestal) voor dat de beslissingsboom de training data minder goed classi ceert met de hoop dat de test data een betere voorspelling krijgt.
In het boven-
staande voorbeeld zou pruning er bijvoorbeeld voor zorgen dat de subgraaf van `packages == 2' samengevoegd wordt tot één bladknoop.
Ten slotte kan het C4.5-algoritme ook
omgaan met ontbrekende waarden, waar dit bij ID3 niet mogelijk is. Zoals lager uitgelegd wordt in Sectie 4.2 (Standaardisering van de output), wordt ervoor gezorgd dat alle detectietechnieken een binaire output hebben. Wanneer op basis van deze data een beslissingsboom wordt opgesteld, hebben alle attributen dus maar 2 mogelijke waarden. Het gevolg is dat het uitvoeren van ID3 op deze data geen nadelen ondervindt van de tekortkomingen die normaal gezien gepaard gaan met dit algoritme (behalve de over tting). In feite geeft ID3, uitgevoerd op een dataset van binaire waarden, hetzelfde resultaat als het uitvoeren van C4.5 (zonder het prunen van de boom). In dit werk wordt ervoor gekozen het gewone ID3-algoritme te implementeren, met twee andere uitbreidingen om over tting te voorkomen. Zo wordt er vooraleer een dataset wordt gesplitst, nagegaan of het aantal samples wel groot genoeg is en of de information gain van het gekozen attribuut wel hoog genoeg is. Deze aanpassingen zijn afkomstig uit de ID3-implementatie in het programma RapidMiner 6.
Kostgevoelige beslissingsbomen Er bestaan ook uitbreidingen op het ID3-algoritme die rekening houden met een mogelijke kost voor het gebruiken van een bepaalde attribuut; dit noemen we kostgevoelige beslissingsbomen.
Lomax et al.[13] geeft een overzicht van verschillende algoritmen om zulke
beslissingsbomen op te stellen. De redenering achter deze uitbreiding is eenvoudig te begrijpen in een medische context: om een diagnose te stellen kan een dokter verschillende
5 Over tting
treedt op bij Supervised-Learningmodellen wanneer men de training data of ruis te dicht probeert te benaderen. Het gevolg is dat het model de onderliggende eigenschap minder goed beschrijft.
2.3 Supervised Learning
23
testen laten uitvoeren, maar veel van deze testen zijn duur en geven een verschillende mate van zekerheid over een mogelijke diagnose. Het is dus nodig om een evenwicht te vinden tussen hoeveel inzicht een bepaalde test geeft in de ziekte van de patiënt en de kost die gepaard gaat met deze test.
Hieronder is een lijst weergegeven van vier algoritmen om
een kostgevoelige beslissingsboom op te stellen. Het enige verschil tussen het ID3 en deze gekozen algoritmen is de metriek waarmee attributen worden gekozen om op te splitsen. ID3 [11]: EG2 [14]: CS-ID3 [15]: IDX [16]: CSGain [17]:
De veranderlijke
ω
inf ormation gain (2(inf ormation
gain)
− 1)/(attribute cost + 1)ω
(inf ormation gain)2 /attribute cost inf ormation gain/attribute cost
(Nattribute /N ) · inf ormation gain − ω · attribute cost
die in een aantal van de formules voorkomt is een parameter, gekozen
door de gebruiker, die moet weergeven in hoeverre voorkeur wordt gegeven aan nauwkeurigheid of aan kost.
Nattribute
is de grootte van de huidige dataset, en
N
is de grootte van
de originele dataset. Men zou zich initieel kunnen afvragen waarom deze
ω
niet in alle formules voorkomt om
problemen met eenheden te voorkomen. Hoe kan immers information gain vergeleken worden met een kost (bijvoorbeeld in
¤)?
Er moet toch een soort verhouding gevonden worden
die de kost omzet naar eenheid van informatie. Dit is geen probleem, omdat in bijna alle formules information gain gedeeld wordt door de kost, waardoor deze verhouding wegvalt. Als men het maximum zoekt van een aantal getallen, mag men deze getallen delen door een constante (groter dan nul) zonder dat dit de optimale keuze beïnvloedt:
a b c max({a, b, c}) max , , = k k k k
(indien k > 0)
De formule van CSGain is de enige waarbij dit niet het geval is, en hier wordt
ω
gebruikt
als verhouding tussen de eenheid van information gain en de eenheid van kost. Dit betekent wel dat het kiezen van een goede waarde voor
ω
hier afhangt van de gekozen eenheid voor
de kost.
Voor- en nadelen Het voordeel van beslissingsbomen is dat de berekeningen om het model op te stellen vooraf gebeuren en dat de voorspelling dus snel uit te voeren is.
Ook is het concept
2.3 Supervised Learning
24
van beslissingsbomen zeer intuïtief en eenvoudig om over te redeneren. Beslissingsbomen hebben wel het nadeel dat het opstellen ervan veel berekeningen vergt.
2.3.6 K-nearest-neighbours K-nearest-neighbours (afgekort k-NN) is een algoritme dat kan gebruikt worden om Supervised Learning toe te passen.
De hoofdgedachte achter deze techniek is dat samples
die op elkaar lijken ook gelijkaardige labels hebben. Dit is een voorbeeld van Case-Based
6
Reasoning , een methodologie uit de arti ciële intelligentie waarbij men problemen oplost door zich te baseren op oplossingen van bekende gevallen (cases). Deze techniek werkt door eerst de
k
samples uit de trainingset
op het ongelabeld sample lijken. Het aantal deze
k
k
T
te zoeken die het meest
is een gegeven geheel getal. Op basis van
samples wordt dan het voorspelde label bepaald.
De eerste stap is de selectiestap, waarin de k gelabelde samples worden gezocht die het meest op het ongelabelde sample gelijken. Hierbij wordt een afstandsmetriek
d
gebruikt
die kwanti ceert in welke mate twee verschillende samples op elkaar lijken:
d : (X1 × · · · × Xn )2 → R Net zoals voor alle afstandsmetrieken, gelden voor
d
de volgende eigenschappen:
d(x, x) = 0 d(x, y) = d(y, x)
(symmetrie)
d(x, y) + d(y, z) ≥ d(x, z)
(driehoeksongelijkheid)
De keuze van metriek is belangrijk, want als de gevonden afstand tussen de gevallen niet overeen komt met hoe sterk de gevallen echt op elkaar lijken, dan zal de voorspelling minder goed zijn. Een eerste mogelijke metriek is de Manhattanafstand, ook wel de genoemd:
d(x, y) =
X i
|xi − yi |
Een andere metriek is de Euclidische afstand, ook wel de
d(x, y) = 6 Meer
s
L2 -afstand
X ((xi − yi )2 ) i
informatie te vinden in het artikel door Watson, 1999 [18].
genoemd:
L1 -afstand
2.3 Supervised Learning
25
De selectiestap is afgelopen nadat de afstand tussen het ongelabelde sample en elk trainingsample berekend werd met de gekozen metriek. Hierna volgt de predictiestap, waarin de labels van de gevonden trainingsamples worden gecombineerd tot het voorspelde label. Dit gebeurt aan de hand van een aggregatiefunctie
a:
a:Yk →Y Men kan hierbij meerderheidsstemming toepassen, waarbij het label dat het vaakst voorkomt, gekozen wordt als voorspelling. Dit kan proceduraal gedaan worden door aan elk mogelijk label een gewicht 0 toe te kennen. Dan wordt voor elk van de
k
dichtste samples
de waarde 1 opgeteld bij het gewicht van het bijhorende label. Het label met het hoogste gewicht wordt dan gekozen als voorspelling.
b(xj , yi ) =
w(yi ) =
1
0
k−1 X
als sample
xj
label
yi
heeft
anders
b(xj , yi )
j=0
Hierbij wordt echter geen rekening gehouden met de afstanden tot het ongelabelde sample. Dit probleem kan worden opgelost door, in plaatst van de constante 1, een waarde die omgekeerd evenredig is met de afstand tot het ongelabelde sample, bij het gewicht kunnen optellen. Het uiteindelijke gewicht van elk mogelijk label is dan bijvoorbeeld de som van het omgekeerde van de afstanden van alle samples die overeenkomen met dat mogelijke label:
w(yi ) =
k−1 X b(xj , yi ) j=0
d(x, xj )
(x:
het ongelabelde sample)
In het speciale geval dat er trainingsamples zijn met onderlinge afstand 0, klopt deze formule niet meer, maar dan wordt meerderheidsstemming toegepast op enkel deze samples. De laatste belangrijke beslissing is de keuze van de gehele parameter samples uit de trainingset worden gekozen.
k , die bepaalt hoeveel
Een te lage waarde is gevoelig voor ruis en
een te hoge waarde geeft voorkeur aan bepaalde labels die vaker voorkomen dan andere. Indien
k
= 1, wordt de techniek simpelweg nearest-neighbour genoemd (afkorting 1-NN),
en is de aggregatiefunctie gewoon de identieke functie, omdat er maar één trainingsample is per ongelabeld sample.
2.4 Uitgebreide doelstelling
26
Voorbeeld Als voorbeeld wordt deze techniek nu toegepast op de samples uit sectie 2.3.4 (Voorbeeld dataset). Voor de parameters
k wordt de waarde 1 gekozen.
Indien er een aggregatiefunctie
nodig is, zal gebruik gemaakt worden van meerderheidsstemming. Voor de afstandsmetriek wordt gebruik gemaakt van de Manhattanafstand.
Men zou deze afstandsmetriek nog
kunnen aanpassen om ervoor te zorgen dat elk attribuut even zwaar doorweegt, maar dat is in dit geval weinig verschil uitmaken.
Tabel 2.9 bevat de afstand tussen elk trainingsample en elk ongelabeld sample.
Voor
Sample11 zijn er vier trainingsamples met afstand 1 (twee met label Goodware en twee met label Malware), dus wordt het voorspeld label hier Malware, omdat het verkeerd labelen van een malwaresample ergere gevolgen heeft dan een goodwaresample verkeerd te labelen. Aangezien de attributen van Sample12 identiek zijn aan die van Sample3, krijgt dit sample hetzelfde label toegewezen. Sample13 krijgt het label Malware omdat de twee samples met de kortste afstand beide malwaresamples zijn.
Voor- en nadelen Het voordeel van k-NN is dat het algoritme relatief eenvoudig is, maar toch exibel blijft door de keuzes van
k,
de afstandsmetriek en de aggregatiefunctie. Het nadeel is dat het
model minder schaalbaar is dan beslissingsbomen, omdat geen van de berekeningen op voorhand kunnen gebeuren. Indien het aantal samples in de trainingset verdubbeld wordt, moeten er ook dubbel zoveel afstanden berekend worden.
2.4 Uitgebreide doelstelling Nu de nodige achtergrondkennis is verworven, kunnen twee extra doelen worden vermeld.
Beslissingsbomen zijn niet de enige Supervised-Learningmethoden die op deze manier kunnen worden gebruikt om detectietechnieken te combineren. Zo goed als alle SupervisedLearningalgoritmen zijn een mogelijke keuze. De meeste van deze algoritmen maken bij het indelen van de samples gebruik van alle attributen, wat overeen komt met het uitvoeren van alle tests op alle samples. De totale kost om één sample te classi ceren is dan gelijk aan de som van de kosten van alle detectietechnieken. Bij beslissingsbomen is het wel mogelijk
2.4 Uitgebreide doelstelling
27 Sample11
Sample12
Sample13
Label
Sample1
2
4
Malware
Sample2
1
1
3
2
Goodware
Sample3
4
0
3
Goodware
Sample4
2
2
1
Malware
3
4
Malware
3
4
Goodware
Sample6
1 1
Sample7
2
2
3
Malware
Sample8
2
4
3
Malware
Sample9
1
3
2
Malware
Sample10
3
3
2
Goodware
Malware
Goodware
Malware
Sample5
Voorspeld:
Tabel 2.9: Voorspellingen k-nearest-neighbours voorbeeld
om een voorspelling te maken met slechts een deel van de attributen. Deze andere classi ers zijn dus enkel nuttig indien de kost onbelangrijk is, of indien ze een nauwkeurigheid behalen die beter is dan die van de beslissingsbomen. Na het uitvoeren van de testen, zullen de resultaten van de beslissingsbomen onderling worden vergeleken om te kijken of bepaalde algoritmen beter geschikt zijn voor deze taak dan andere. Ook zullen de resultaten geëvalueerd worden ten opzichte van de individuele technieken en andere Supervised-Learningtechnieken. Omdat alle verzamelde bestaande detectietechnieken zeer algemeen zijn, zullen ten slotte ook twee eenvoudige detectietechnieken (Contains_APK en No_Permissions) geïmplementeerd worden om te testen of technieken met een zeer speci eke functie een nuttig bijdrage kunnen leveren aan het gecombineerd systeem.
28
2.4 Uitgebreide doelstelling
LITERATUURANALYSE
29
Hoofdstuk 3 Literatuuranalyse In dit hoofdstuk volgt een overzicht van bestaande werk over het detecteren van Android malware. Zoals reeds aangegeven in Sectie 2.2.6 (Soorten analyse), kunnen malwaredetectietechnieken worden ingedeeld in statische en dynamische technieken.
3.1 Statische technieken 3.1.1 A Static Assurance Analysis of Android Applications Deze techniek door Elish et al. onderzoekt het verband tussen gebruikersacties en kritische systeemfuncties [19].
Er wordt vertrokken van de veronderstelling dat bij goodware op-
roepen naar kritische systeemfuncties kunnen worden teruggekoppeld naar een actie door de gebruiker, en dat bij malware kritische functies worden opgeroepen zonder bijhorende gebruikersacties.
Eerst wordt bepaald door de onderzoekers welke API calls als gevaarlijk worden beschouwd. Ook wordt een lijst opgesteld van alles wat wordt beschouwd als input door de gebruiker. Daarna wordt, aan de hand van de dataverloopgraaf, onderzocht welke kritische systeemoproepen het gevolg zijn van gebruikersacties en welke niet. Het percentage van alle kritische oproepen waarvoor een bijhorende actie is gevonden, wordt de 'assurance score' genoemd. Uit het onderzoek blijkt dat malware beduidend lagere assurance scores hebben dan nietkwaadaardige applicaties. Deze assurance score kan met behulp van een drempelwaarde worden omgezet naar een binaire beslissing. Na het bepalen van de waarde van de assurance score, wordt deze waarde vergeleken met de drempelwaarde. Indien de waarde groter is dan de drempelwaarde, wordt
3.1 Statische technieken
30
het sample als goodware beschouwd. In het andere geval zal het als malware bestempeld worden. In het artikel wordt 80% aangegeven als goede keuze voor de drempelwaarde. Deze techniek werd uitgevoerd op 482 malwareapplicaties. Hiervan haalden 313 applicaties een assurance score van 0%. De meeste andere malwaresample hadden een assurance score lager dan 50%. Er waren slechts 7 samples met een assurance score hoger dan 80%. Van de 708 goodwareapplicaties waarvan assurance scores werden berekend, haalde het merendeel (648 applicaties) een assurance score van 100%. Geen enkel goodwaresample haalde een assurance score van minder dan dan 70%.
3.1.2 Adagio Gascon et al. bespreken een techniek waarbij wordt Supervised Learning toegepast op de function call graphs van de applicaties [20]. Eerst wordt een gerichte graaf opgesteld waarin de knopen functies voorstellen en de pijlen aangeven welke functies elkaar oproepen.
Daarna krijgt elke knoop een omgevingshash-
waarde toegewezen die de informatie over de eigenschappen van de functies in de directe omgeving (de buren) van de knoop bevat.
Vervolgens wordt geteld hoe vaak elke hash-
waarde voorkomt; deze aantallen worden op geslagen in variabelen keer dat de
i
de
hashwaarde voorkomt).
dimensionale vector
x
Op basis van deze waarden wordt dan een
vector. De
i
N
M −α
α
gelijk aan
M −α
groep n
mogelijke hashwaarden, worden M binaire waarden toegevoegd aan de
groep van
M
waarden bestaat uit
αi
keer 1, gevolgd door
M − αi
α1 gelijk is aan 3 en M gelijk aan 5, dan zijn de eerst 5 1, 1, 1, 0, 0. De dimensie van de vector, P , is gelijk aan N · M .
Indien bijvoorbeeld
x
P-
z }|n { z }| n { z }|1 { z }| 1 { x = ( 1, . . . , 1, 0, . . . , 0 , . . . , 1, . . . , 1, 0, . . . , 0 ) | {z } | {z } groep 1
de
is het aantal
opgesteld, die de applicatie voorstelt:
α
Voor elk van de
αi (αi
keer 0.
waarden van
Zodra voor alle applicaties zo'n vector is opgesteld, kan hierop Supervised Learning toegepast worden. In dit geval worden een lineaire Support Vector Machine (SVM) gebruikt. Deze techniek gaat zoeken naar het
(P − 1)-dimensionale hypervlak dat de P -dimensionale
punten uit de trainingset zo goed mogelijk lineair separeert. Dit betekent dat het hypervlak wordt gekozen dat zich het verst mogelijk van het dichtste punt bevindt en toch alle trainingsamples correct classi ceert; het hypervlak met de grootste marge. Deze lineaire separatie vormt dan het model waarmee de testsamples een label toegewezen krijgen.
3.1 Statische technieken
31
Deze techniek is geëvalueerd met een dataset van 135792 goodwaresamples en 12158 malwaresamples, verzameld van de Google Play store en een aantal andere populaire app stores. Om te bepalen of een applicatie malware bevat of niet, is gebruikt gemaakt van een reeks commerciële malwarescanners.
Een nauwkeurigheid van 89% wordt gerapporteerd
met een false positive rate van 10%.
3.1.3 AppRiskPred Dit is een verzamelnaam voor een aantal Naïve-Bayesmodellen, beschreven door Peng et al., die voor elk testsample een relatieve risk score kunnen voorspellen, op basis van de permissies en de categorie van applicaties in de trainingset [21]. Deze risk score heeft als doel de gebruiker beter te informeren over de risico's van een app in vergelijking met andere apps. In het paper worden 4 modellen voorgesteld die varianten zijn van Naïve-Bayesclassi ers. Deze technieken werken als volgt, in volgorde van toenemende complexiteit: BNB (Basic Naive Bayes) traint een eenvoudig Naive-Bayesmodel op enkel de permissies, PNB (Naive Bayes with Informative Priors) houdt daarnaast ook rekening dat sommige permissies gevaarlijker zijn dan andere, MNBC (Mixture Naive Bayes with Categories) veronderstelt dat apps toebehoren aan meerdere jnkorrelige klassen en houdt ook rekening met de categorie van de app (elke categorie heeft een andere verdeling voor de jnkorrelige klassen), en in HMNB (Hierarchical Mixture of Naive Bayes) zijn de verdelingen van de jnkorrelige klassen gelijkaardig voor alle categorieën. Voor het HMNB-model is de categorie van de apps in de trainingset nodig voor het opstellen van het model.
Aangezien de categorie van de malware apps niet bekend is, moet de
categorie van de deze samples in de trainingset voorspeld worden.
Eenmaal het model
getraind is, worden de risk scores voor de testset voorspeld. De resultaten voor deze techniek worden weergegeven aan de hand van een ROC-curve. Dit is een gra ek waarbij de horizontale as de false positives aangeeft en de verticale as de true posities weergeeft. Door een parameter te laten variëren kunnen verschillende resultaten in dit vlak worden bepaald. Een optimale techniek bereikt voor een bepaalde parameter een true positive rate van 100% en een false positive rate van 0%. Door het resultaat niet als nauwkeurigheid weer te geven, zijn de resultaten echter niet gemakkelijk vergelijkbaar met andere methoden die dit wel doen. Er wordt ook gemeld dat HMNB het best presteert, maar dat het verschil tussen de 4 modellen klein is.
3.1 Statische technieken
32
3.1.4 Droidlegacy Droidlegacy werd gepresenteerd door Deshotels et al.[22]. Het is ontwikkeld met als doel om nieuwe varianten van bekende malwarefamilies te detecteren; met andere woorden om repackaged malware te herkennen. Als output geeft deze techniek de malwarefamilie waar het sample het meest waarschijnlijk toe behoort en een getal tussen 0 en 1 dat aangeeft hoe goed het sample op deze familie lijkt.
Voor elke malwarefamilie worden handtekeningen opgesteld, die bestaan uit API-
calls van de klassen van de app die malware bevatten. Om een ongelabeld sample te testen wordt gekeken of de applicatie aan deze handtekening voldoet.
Om te beginnen worden de handtekeningen van de malwarefamilies in de trainingset opgesteld. Op dit moment worden de goodwaresamples in de trainingset dus nog niet gebruikt. In de eerste stap van het algoritme worden de klassen van de malwareapplicaties in de trainingset gepartitioneerd in modules, zodat de klassen binnen eenzelfde module een sterke samenhang hebben en de klassen van verschillende modules een zwakke samenhang hebben. Dit wordt gedaan aan de hand van een Class Dependence Graph. Elke van deze modules wordt gekarakteriseerd door zijn API-calls. Deze stap is geïllustreerd in Figuur 3.1.
Daarna volgt stap 2 van het algoritme, waarin de modules van alle trainingsapplicaties binnen eenzelfde malwarefamilie worden vergeleken om de module te identi ceren die de malware bevat. De API-calls uit deze module vormen dan de handtekening van de malwarefamilie. De gelijkaardigheid tussen modules wordt gekwanti ceerd aan de hand van de
1
Jaccard Similarity . Figuur 3.2 bevat een gra sche weergave van stap 2.
Eenmaal de handtekeningen van de malwarefamilies zijn opgesteld, kan de best passende familie van een ongelabelde sample worden voorspeld; dit is stap 3 van het algoritme. Hierbij worden eerst de modules van de app opgesteld, zoals tijdens stap 1.
Voor al
deze modules wordt de Jaccard Similarity met alle handtekeningen berekend en geordend. De handtekening van de malwarefamilie die de hoogste score krijgt, bepaalt tot welke familie het ongelabelde sample het meest waarschijnlijk behoort. De geassocieerde Jaccard
1 De
Jaccard Similarity is een getal, tussen 0 en 1, die de overeenkomst tussen eindige verzamelingen aangeeft. De formule voor die aangeeft hoe sterk verzameling A en B op elkaar lijken: J(A, B) =
|A ∩ B| . |A ∪ B|
3.1 Statische technieken
33
Figuur 3.1: Droidlegacy - Stap 1: klassen partitioneren in modules [22]
Similarity geeft aan hoe goed de handtekening bij het sample past. Stap 3 wordt afgebeeld in Figuur 3.3.
3.1.5 Kirin Dit is één van de oudste statische detectietechnieken voor Android malware. In een artikel door Enck et al. wordt security requirements engineering toegepast op het Android platform om een aantal security rules op te stellen [23]. Manueel worden vereisten voor bepaald ongewenst gedrag opgesteld (bijvoorbeeld het afluisteren van gesprekken), die dan worden vertaald naar een combinatie van permissies. Eén van de combinaties bevat ook een Intent. Dit is een abstracte beschrijving van actie die kan worden uitgevoerd op een Android systeem. In dit geval gaat het over de Call-intent, die het maken van een telefoongesprek voorstelt. Indien aan één van deze regels is voldaan, wordt de app beschouwd als riskant. Deze 7 regels zijn dus verboden combinatie van permissies:
The application can run/stop other applications in debug mode: SET_DEBUG_APP
The application can detect phone call activity, record the conversation, and send to the Internet: READ_PHONE_STATE, RECORD_AUDIO, INTERNET, and RECEIVE_BOOT_COMPLETED
34
3.1 Statische technieken
Figuur 3.2: Droidlegacy - Stap 2: opstellen handtekening van een malwarefamilie [22]
3.1 Statische technieken
Figuur 3.3: Droidlegacy - Stap 3: Analyse van een ongelabeld sample [22]
35
3.1 Statische technieken
36
The application can track your location using GPS and leak it to the Internet: ACCESS_FINE_LOCATION, INTERNET, and RECEIVE_BOOT_COMPLETED
The application can track your location using Cell-ID or WiFi and leak it to the Internet: ACCESS_COARSE_LOCATION, INTERNET, and RECEIVE_BOOT_COMPLETED
The application can replace shortcut with malicious shortcut: INSTALL_SHORTCUT and UNINSTALL_SHORTCUT
The application can silently take over make call functionality: SET_PREFERRED_APPLICATIONS and CALL-intent
The application can send SMS and delete send history: SEND_SMS and WRITE_SMS
3.1.6 DroidAPIMiner In het werk door Aafer et al. wordt een methode beschreven om Android applicaties te classi ceren op basis van API-calls [24]. Er zijn verschillende classi catiealgoritmen getest (ID3, C4.5, K-NN en SVM), waarvan K-NN het beste resultaat gaf.
Voor elke applicatie worden de API-calls verzameld die niet worden opgeroepen door een extern package (zoals een reclamepackage). Daarna worden enkel de calls overgehouden die ofwel signi cant vaker voorkomen in de malwaresamples dan in de goodwaresamples, ofwel vaak voorkomen in zowel de goodware- als de malwareset, maar die opgeroepen worden met gevaarlijke parameters (wat bepaald wordt aan de hand van data owanalyse).
Dit
geeft een lijst van kritische API-calls en API-calls met gevaarlijke parameters. Deze APIcalls zijn de features die een applicatie karakteriseren, waarmee dan meerdere SupervisedLearningmodellen worden opgesteld.
De dataset, waarop de testen zijn uitgevoerd, bestaat uit 3987 malwaresamples en ongeveer 16000 goodwaresamples. Om de modellen te vereenvoudigen werd de lijst van 491 kritische API-calls beperkt tot die calls die minstens 6% vaker voorkwamen in de malware (wat neerkomt op 169 calls).
In de eerste test werden de 4 modellen uitgevoerd op de top-n
meest gebruikte API-calls (met n gelijk aan 10, 40, 80, 120 en 169).
Hieruit blijkt dat
K-NN voor n gelijk aan 169 het beste resultaat geeft (nauwkeurigheid van net minder dan 99%). Bij de tweede test wordt ook rekening gehouden met de API-calls die gebruik
3.2 Dynamische technieken
37
maken van gevaarlijke parameters. Ook hier worden enkel een aantal meest gebruikte calls beschouwd (top-20, top-40 en top-60). Het K-NN-algoritme, toegepast op de combinatie van de 169 meest gebruikte kritische calls en de 20 meeste gebruikte calls met gevaarlijke parameters, leidt tot de hoogste nauwkeurigheid (99%). In alle testen is gebruik gemaakt van 3-fold cross validation.
3.2 Dynamische technieken 3.2.1 Andromaly Andromaly, ontworpen door Shabtai et al., is een framework met als doel om het gedrag van malware op smartphones te herkennen aan de hand van Machinaal Leren [25]. Een speciale applicatie voert anomaliedetectie uit op verschillende features en gebeurtenissen, zodat een sample kan geclassi ceerd worden als goodware of malware.
Eerst wordt metrieken over de toestand van een mobiel toestel (bijvoorbeeld het CPUgebruik, het aantal verzonden packets, het aantal opgestarte processen, etc.) verzameld. Deze data wordt dan doorgegeven aan verschillende detectie-eenheden, die elke een eigen functie hebben.
Deze detectie-eenheden kunnen regelgebaseerd, kennisgebaseerd or
Machine-Learningtechnieken zijn, en produceren een beoordeling van het risico van de waarnemingen. Elke individuele beoordeling krijgt een gewicht toegewezen. Op basis van deze gewichten worden de beoordelingen dan gecombineerd tot een algemene evaluatie die wordt weergegeven in een melding. Ten slotte kan het systeem, in het geval van detectie van abnormaal gedrag, een aantal mogelijke acties voorstellen aan de gebruiker (bijvoorbeeld het desinstaleren van een app of het uitschakelen van een proces).
Om de werking van deze methode te testen, werden 4 malwareapplicaties ontwikkeld door de onderzoekers (omdat er op het moment dat dit is onderzoek is uitgevoerd nog geen Android malwaresamples bekend waren) die Denial-of-service-aanvallen uitvoeren of persoonlijke gegevens stelen. Om deze reden zijn de resultaten moeilijk te vergelijken met die uit ander onderzoek.
Uit de experimenten bleek dat Naive Bayes en logistieke regressie
betere testresultaten behaalden dan de andere geteste classi ers.
3.2 Dynamische technieken
38
3.2.2 Crowdroid Burguera et al. stellen een techniek voor die informatie verzamelt van een grote hoeveelheid gebruikers en dit analyseert op een centrale server om repackaged malware te detecteren [26].
Deze aanpak is gebaseerd op crowdsourcing: hoe weer data verzameld wordt over
applicaties, hoe beter het systeem malware kan detecteren. Een speciale app, Crowdroid genaamd, kan worden gedownload door eindgebruikers. Deze applicaties controleert voortdurend de systeemoproepen naar de Linux kernel and stuurt deze door naar de centrale server voor verwerking. Voor elke interactie tussen de gebruiker en de applicatie wordt een vector opgesteld van deze system calls. Deze vectoren karakteriseren dus het gedrag van de geassocieerde applicatie. Daarna wordt een partitioneel clusteringalgoritme toegepast op elke dataset. Hierdoor is het mogelijk om te detecteren wanneer het om repackaged malware gaat, omdat het gedrag sterk verschillend van apps met dezelfde naam en identi er. Het systeem was in staat 100% van de malware, speciaal ontworpen voor dit artikel, te detecteren.
Daarnaast zijn ook twee echte malwaresamples getest, en hierbij werd een
100% nauwkeurigheid vastgesteld voor de eerste applicatie en 85% voor de tweede.
WERKWIJZE
39
Hoofdstuk 4 Werkwijze 4.1 Verzamelen van technieken De eerste stap was het zoeken naar bestaande statische detectietechnieken voor Android malware in de academische literatuur.
De auteurs van de relevante papers werden ge-
contacteerd met het verzoek of er van de implementatie van hun techniek mocht gebruik gemaakt worden in dit werk. De implementaties die werden verkregen zijn dan waar nodig aangepast of opnieuw geïmplementeerd in Python om ervoor te zorgen dat alle tests eenzelfde soort input konden accepteren en dezelfde soort output genereerden. Hierbij is gebruikt gemaakt van de twee tools, geïmplementeerd in Python, die functies aanbieden om reverse engineering toe te passen op APK-bestanden: Androguard [27] en Apktool [28].
Er zijn ook een aantal nieuwe technieken bedacht en geïmplementeerd. Het doel van twee hiervan was om over eenvoudige technieken te beschikken die enkel geschikt zijn om ofwel een zeer speci ek soort malware te detecteren, ofwel om op een snelle manier te herkennen dat bepaalde samples waarschijnlijk geen malware bevatten.
Meer informatie over de speci eke technieken kan gevonden worden in sectie 5.2 (Speci eke technieken).
4.2 Standaardisering van de output Er werd voor gezorgd dat alle technieken een binair resultaat geven: 0 voor goodware en 1 voor malware. Dit voorkomt dat bepaalde technieken voorkeur krijgen bij het opstellen van
40
4.3 Samples
de beslissingsboom, omdat ze een grotere verzameling outputwaarden hebben. De meeste technieken hadden al een binaire output. De twee technieken die dat niet deden, hadden als output een relatieve score die de betrouwbaarheid van een app aangaf ten opzichte van de trainingset, of een voorspelling van de meest waarschijnlijke malwarefamilie waartoe het sample behoorde, met een bijhorende waarde tussen 0 en 1 om aan te geven hoe goed deze voorspelling was.
Om een numerieke voorspelling om te zetten naar een binaire output, wordt deze voorspelling vergeleken met een gegeven drempelwaarde. Indien de voorspelling kleiner is dan de drempelwaarde, is de output 0; in het andere geval is de output 1. Om een geschikte drempelwaarde voor het opgestelde model te vinden, werden eerst de voorspellingen berekend voor alle samples uit de trainingset, omdat van deze samples het binaire label gekend is. Vervolgens wordt de drempelwaarde gezocht die voor het grootste aantal trainingssamples de correcte output oplevert. Deze optimale drempelwaarde werd dan gebruikt om de voorspellingen van de samples uit de testset (de ongelabelde samples) om te zetten naar binaire waarden.
4.3 Samples Het verzamelen van de Android applicaties was de tweede stap. Zoals uitgelegd in sectie 2.3.2 (Ground thruth), is een ground truth nodig om de testen op een wetenschappelijk verantwoorde manier uit te voeren. Dit betekent dat elk sample correct gelabeld moet zijn als malware of goodware. Verkeerd gelabelde samples in de trainingset kunnen voor fouten in het model zorgen, en in de testset geven ze een incorrect beeld van de nauwkeurigheid van de techniek.
4.3.1 Goodware De goodwaresamples werden gedownload van de o ciële Android app-store, de Google Play store. Hiervoor werd eerst een lijst opgesteld van alle applicaties in de top-60 in elk van de 34 categorieën met behulp van een webscraper. De reden waarom er voor 60 apps per categorie gekozen werd, is omdat de Google Play website dit aantal weergeeft bij het aanvragen van de meest gedownloade applicaties in een categorie en dat dit een voldoende groot getal leek in verhouding met het aantal verzamelde malwaresamples.
4.3 Samples
41
De Google Play store laat enkel toe de APK's van de applicaties downloaden naar een Android toestel, dus werd er gebruik gemaakt van een service die deze APK's toch kon downloaden naar een desktop. Er werd contact opgenomen met de ontwikkelaar van APK Downloader om toegang te krijgen tot hun API, waardoor een script snel en op basis van enkel de packagenaam de APK's kon downloaden [29].
Omdat er overlap is tussen de verschillende categoriën, diende er te worden gecontroleerd dat elke applicatie maar één keer in de lijst voorkwam.
Er werden in het totaal 1877
applicaties gedownload, waarvan wordt uitgegaan dat ze geen malware bevatten.
Een
eerste verantwoording hiervoor is dat de Google Play store dynamische analyse uitvoert op alle nieuwe applicaties om malware te detecteren en te verwijderen (deze service wordt Google Bouncer genoemd). Het feit dat deze applicaties voorkwamen in de top-60 van een categorie, en dat er dus veel mensen deze apps getest hebben, verkleint ook de kans dat er zich malware in deze apps bevindt.
Tijdens het uitvoeren van de detectietechnieken zijn er nog een aantal goodwaresamples verwijderd vanwege problemen met de tools voor analyse van Androidapplicaties, en omdat sommige apps adware bevatten, die mogelijk konden gezien worden als malware. Uiteindelijk bleven er 1858 goodwaresamples over in de nale dataset.
4.3.2 Malware De verzameling malwaresamples is afkomstig uit 2 bronnen.
De eerste hiervan is het
Android Malware Genome Project, een verzameling van meer dan 1200 samples verzameld tussen augustus 2010 en oktober 2011 en geordend per malwarefamilie [30].
De tweede bron is Contagio Mobile; dit is een blog waar mobiele-malwaresamples kunnen worden uitgewisseld voor academische doeleinden [31]. Deze verzameling bevatte malware voor meerdere platformen, dus werden enkel de Android-malwareapps behouden. Aangezien beide bronnen samples bevatten die onderzocht werden door professionele malwareanalysten, is de kans verwaarloosbaar klein dat er zich in deze verzameling goodwaresamples bevinden.
Bij het testen van de 1623 malwaresamples, doken er soms problemen op net als voor de goodwaresamples, en bleven er na eliminatie van de probleemgevallen 1590 malwaresamples over.
4.3 Samples
42
4.3.3 Eliminatie van samples Sommige van de problemen met de analysetool Androguard werden veroorzaakt door padding-errors in bepaalde samples, omdat het bestand niet volledig voldoet aan het verwachte formaat.
Dit is omwille van een probleem met de analysetool, en niet omwille
van de technieken die van deze tool gebruik maken. De probleemsamples werden uit de dataset verwijderd om ervoor te zorgen dat de testresultaten uniform zijn. In de praktijk is het beter om bij dit soort problemen een positief resultaat te geven, omdat makers van malware anders fouten in de analysetools kunnen misbruiken om detectie te omzeilen [32].
4.3.4 Malwarefamilies Van de samples, afkomstig van Contagio, werd niet aangegeven tot welke malwarefamilie ze behoren. Voor één van de detectietechnieken (Droidlegacy) is kennis over deze indeling
1
wel noodzakelijk, dus werd voor deze samples met behulp van VirusTotal
opgezocht van
welke malwarefamilie ze deel uitmaken.
4.3.5 Categorie Er was een gelijkaardig probleem met een andere techniek (AppRiskPred), die de categorie van een applicatie nodig heeft. Om dit probleem op te lossen, werd een webscraper geschreven, die de categorie van een goodwareapp opzoekt op de Google Play store en opslaat. Dit was niet mogelijk voor de malwareapps, dus werd de categorie van deze apps voorspeld door de techniek zelf, zoals beschreven staat in sectie 3.1.3 (Speci eke technieken).
4.3.6 Goodware recenter dan malware Ten slotte is er nog een mogelijk probleem met het feit dat het merendeel van de goodwaresamples recenter zijn dan de malwaresamples. Dit kan belangrijk zijn, omdat de permissies en de API van Android na verloop van tijd aangepast worden. Tijdens het uitvoeren van de testen werd gekeken of dit mogelijk een eect had op de geproduceerde modellen (door
1 VirusTotal
is een website die een online malwarescanner aanbiedt. Na het uploaden van het verdachte bestand worden een aantal (54 op het moment van schrijven) andere online malwarescanners aangesproken om het sample te onderzoeken. De resultaten van de verschillende scanners worden daarna verzameld in een overzicht.
4.4 Technieken uitvoeren
43
bijvoorbeeld te kijken of een beslissingsboom van permissies te veel vertrouwde op nieuwe permissies voor classi catie), maar een dergelijke invloed werd niet vastgesteld.
4.4 Technieken uitvoeren Eenmaal de training- en testsets zijn opgesteld met 10-fold cross validation, kunnen de technieken worden uitgevoerd.
Indien een techniek Supervised Learning toepast, wordt
eerst een predictief model opgesteld op basis van de trainingset, en daarna wordt voor elk sample van de testset de voorspelling berekend met het model. Voor de andere technieken, waarvoor geen trainingset nodig is, worden de voorspellingen enkel op basis van het testsample gemaakt. Achteraf werden de technieken nog eens uitgevoerd op een kleinere verzameling samples (50 goodwaresamples en 50 malwaresamples, op willekeurige wijze geselecteerd) om de gemiddelde uitvoeringstijd van de technieken te meten. Hierbij werd enkel rekening gehouden met de tijd die nodig is om een sample te classi ceren, daar er vanuit gegaan wordt dat, in een commercieel systeem, de predictieve modellen slechts één keer worden opgesteld voor de trainingset en dan opgeslagen worden in het geheugen.
Nadat alle testen uitgevoerd waren, werden alle testresultaten verzameld in één bestand. Deze data werd omgezet naar een tabel van binaire waarden waarin de rijen overeenkomen met samples en de kolommen technieken voorstellen.
Deze tabel bevat ook een kolom
waarin aangegeven staat of het sample goodware of malware is, en een rij, waarin de gemiddelde uitvoeringstijd van de technieken wordt bijgehouden. Uit dit bestand kan dan voor elk sample een vector van testresultaten en een label gehaald worden.
Het is deze
data waarmee de beslissingsbomen zijn opgesteld.
4.5 Beslissingsbomen genereren Om te beginnen zijn de vijf beslissingsboomalgoritmen uit sectie 2.3.5 (Kost-gevoelige beslissingsbomen) geïmplementeerd. Hierbij werden bovendien twee uitbreidingen ingevoerd om de grootte van de beslissingsboom te beïnvloeden. Deze aanpassingen zijn geïnspireerd door de ID3-implementatie in het programma RapidMiner 6. De eerste uitbreiding zorgt ervoor dat de information gain die overeenkomt met het splitsen van de dataset op een bepaald attribuut minstens even groot is als een gegeven waarde. De andere uitbreiding
4.5 Beslissingsbomen genereren
44
legt op dat een dataset niet gesplitst kan worden indien het aantal samples te klein is. Dit levert twee parameters op die een invloed hebben op de uiteindelijke beslissingsboom. Ten slotte is er de parameter
ω
uit de formules voor de kostgevoelige algoritmen EG2 en
CSGain.
Er is bij de implementatie van de beslissingsboomalgoritmen gekozen voor de programmeertaal Java, omdat objectoriëntatie zich goed leent voor de modellering van beslissingsbomen. Het klassendiagram wordt afgebeeld in Figuur 4.1.
ID3 is het eerste beslissingsboomalgoritme dat onderzocht werd. Een interval van mogelijke waarden werd door trial-and-error opgesteld voor de twee relevante parameters (ω wordt niet gebruikt bij ID3). Voor alle mogelijke combinaties van deze waarden werden een aantal beslissingsbomen opgesteld en geëvalueerd met 10-fold cross validation.
Elke
beslissingsboom wordt gekarakteriseerd door een nauwkeurigheid en een kost, en er wordt ook altijd bijgehouden met welk algoritme en welke parameters de beslissingsboom werd opgesteld. De lijst van beslissingsbomen werd dan omgezet naar een lijst van (nauwkeurigheid, kost)-paren. Omdat de detectietechniek API_1-NN (zie sectie 5.2.6) een nauwkeurigheid van 95% behaalt met een kost van ongeveer 10 seconden, werden alle beslissingsbomen met een nauwkeurigheid onder de 95% uitgesloten. De gemiddelde kost van alle beslissingsbomen (met een degelijke nauwkeurigheid) ligt namelijk aanzienlijk hoger dan 10. Vervolgens werd de resulterende lijst van paren overlopen om alle overbodig paren weg te laten. Een (nauwkeurigheid, kost)-paar is overbodig indien er een ander paar bestaat met een hogere (of gelijke) nauwkeurigheid en een lagere kost. Door na te gaan welke parameters aanleiding gaven tot de overblijvende beslissingsbomen, werden de intervallen voor de parameters iteratief aangepast tot er geen verbetering meer mogelijk was. Voor deze intervallen werd het algoritme nog een laatste keer uitgevoerd, maar nu met een groter aantal beslissingsbomen voor elke combinatie van parameters. De reden waarom er meerdere beslissingsbomen moeten worden gemaakt voor dezelfde combinatie parameters, is dat cross validation de dataset willekeurig opsplitst en dus de trainingset niet steeds dezelfde is. Alle beste paren uit alle iteraties werden bijgehouden en uit de verzameling van deze paren werden opnieuw alle overbodige paren verwijderd.
Enkel de paren (en bijhorende para-
meters) die de beste ID3-beslissingsbomen voorstellen, blijven nu over. Deze combinaties vormen een Paretogrens. Dit betekent dat voor het gegeven algoritme niet mogelijk is een beslissingsboom te construeren die een punt van de Paretogrens overbodig maakt.
4.5 Beslissingsbomen genereren
45
Figuur 4.1: Klassendiagram voor de implementatie van de beslissingsboomalgoritmen
4.6 Andere Supervised-Learningalgoritmen
46
Deze procedure werd herhaald voor de vier overige algoritmes. Bij EG2 en CSGain werd uiteraard ook een interval voor de
ω -parameter
voorzien. De resultaten van de vijf algo-
ritmen werden dan met elkaar vergeleken.
4.6 Andere Supervised-Learningalgoritmen Ten slotte werden ook nog een aantal andere Supervised-Learningalgoritmen toegepast op de data van testresultaten, om de resultaten van de beslissingsbomen mee te vergelijken. Dit werd gedaan met behulp van het programma RapidMiner 6, dat een aantal van deze algoritmen in verschillende categorieën aanbiedt.
Uit elke categorie werd één algoritme
gekozen om uit te voeren op de dataset. Met dit programma is het niet mogelijk om een kost te associëren met een attribuut, waardoor de technieken altijd gebruik maken van alle attributen van een sample. Dit zou in de praktijk betekenen dat alle detectietechnieken op alle samples uitgevoerd moeten worden, waardoor de kost om één sample te classi ceren gelijk is aan de som van de kosten van alle technieken. Ook hier werden de resultaten van de verschillende testen met elkaar vergeleken.
GEBRUIKTE DETECTIETECHNIEKEN
47
Hoofdstuk 5 Gebruikte detectietechnieken 5.1 Beperkingen In deze sectie wordt besproken welke soorten technieken worden uitgesloten en de redenen waarom deze beperkingen worden opgelegd.
5.1.1 Niet-statische technieken Zoals reeds in de titel van dit werk aangegeven, zijn enkel statische detectietechnieken gebruikt. Dit betekent dat de bestanden van de Androidapplicaties enkel doorzocht worden, zonder ze uit te voeren. Technieken die dynamische of hybride analyse uitvoeren, zijn niet beschouwd. Deze beperking was op voorhand opgelegd door NVISO (het bedrijf dat het onderzoek heeft begeleid), omdat statische technieken over het algemeen sneller zijn dan dynamische technieken (waarbij een applicatie worden uitgevoerd om het gedrag van het sample te bestuderen).
5.1.2 Technieken met voorkennis Ook worden alle technieken uitgesloten die voorkennis over speci eke malware nodig hebben om ze te detecteren.
Dit omvat alle technieken die reeds gekende malwaresamples
proberen te herkennen met behulp van handtekeningen. De reden voor deze beperking is dat deze technieken vertrouwen op een database van handtekeningen, die inspanningsintensief en nancieel duur zijn om op te stellen en te onderhouden. Vervolgens is er ook een probleem met het testen van deze technieken op
5.2 Speci eke technieken
48
een wetenschappelijk verantwoorde manier. De detectie van een malwaresample met zo'n techniek hangt af van het feit of de overeenkomstige handtekening in de database zit of niet, en niet van de techniek zelf. Indien er k-fold cross validation wordt toegepast, zal dit soort technieken dus geen enkele sample herkennen. Het herkennen van malwaresamples die op voorhand bekend moeten zijn, kan veel gemakkelijker gebeuren aan de hand van een service zoals VirusTotal, die hun database gratis ter beschikking stellen. Wat wel toegestaan is, zijn technieken die varianten van bestaande malwarefamilies detecteren, omdat deze bestanden kunnen ontdekken die nog nooit geïdenti ceerd zijn. Droidlegacy (zie Sectie 3.1.4) is zo'n techniek.
5.1.3 Technieken op Android toestellen Vanwege de prestatie- en energiebeperkingen van een smartphone, worden alle technieken op een desktop/server uitgevoerd, en dus niet op een Android toestel. Hoewel beveiligingsapplicaties op Android wel degelijk nuttig kunnen zijn voor het tegenhouden van malware waarvan de handtekening al bekend is, is grootschalige detectie van `nieuwe' malware beter geschikt voor servers.
5.2 Speci eke technieken Nu volgt een overzicht van de 10 detectietechnieken die geïmplementeerd en getest zijn voor dit eindwerk. Deze sectie bevat de implementatiedetails en de mate waarin de bestaande technieken verschillen van hun beschrijving in de academische literatuur. Zoals uitgelegd in sectie 2.3.3 (K-fold cross validation), is bij alle technieken 10-fold cross validation gebruikt voor het testen. In de gevallen waarin een techniek geen trainingset nodig heeft, wordt de trainingset gewoon genegeerd.
Om de testen op een uniforme manier te kunnen uitvoeren, werd ervoor gekozen om voor alle technieken Pythonscripts te gebruiken.
De testapplicaties werden in 4 mappen bij-
gehouden, naargelang ze in de training- of de testset zaten, en of het om malware- of goodwaresamples ging. Na elke `fold' werden de applicaties herverdeeld over deze mappen.
Aangezien er gebruik is gemaakt van 10-fold cross validation, is elke techniek 10 keer uitgevoerd bij het verzamelen van de testresultaten. Omdat het niet e ciënt is om 10 keer
5.2 Speci eke technieken
49
dezelfde informatie (bijvoorbeeld de permissies) te extraheren uit de APK-bestanden, is dit voor elke techniek slechts één keer gebeurd, waarna deze informatie opgeslagen is in een bestand. Tijdens het uitvoeren van de technieken zijn deze bestanden dan ingelezen en gebruikt voor het maken van de voorspellingen.
5.2.1 Adagio De werking van deze techniek wordt uitgelegd in Sectie 3.1.2. De verkregen implementatie was al geschreven in Python, dus waren maar weinig aanpassingen nodig. Om te vermijden dat het opstellen van de vectoren meerdere keren moest gebeuren, werden deze waarden éénmaal berekend en opgeslagen in een bestand.
Tijdens het uitvoeren van de testen
werden deze getallen dan uitgelezen en gebruikt voor de voorspelling. Er is ook een optimalisatie uitgevoerd om de voorspelling sneller te laten verlopen. Dit is gebeurd door het formaat, waarin de vectoren werden opgeslagen, aan te passen.
5.2.2 Permissions_DT Dit is de eerste zelfontwikkelde techniek die is geïmplementeerd. Hierbij wordt een beslissingsboom opstelt op basis van permissies en vier andere eigenschappen van applicaties. Deze techniek werkt als volgt: de nodige data over de applicaties wordt verzameld, deze informatie wordt omgezet naar bitvectoren, de beslissingsboom wordt gegenereerd en de klassen van de ongelabelde samples worden voorspeld.
De eerste stap is het verzamelen van de data. In dit geval gaat het om de permissies van de applicatie en vier Boolese waarden die aangeven of mogelijk verdacht gedrag aanwezig is. Het mogelijk verdacht gedrag omvat: het bezitten van native code, het gebruiken van encryptie, het dynamisch inladen van klassen en het gebruik van re ectie. Deze data wordt dan omgezet naar een bitvector van dimensie 149, omdat er op het moment van schrijven 145 permissies bestaan en er rekening wordt gehouden met 4 soorten verdacht gedrag. De bitvectoren voor elke applicatie zijn opgeslagen in een bestand om het herhaaldelijk extraheren van dezelfde informatie te vermijden. Op basis van de vectoren van de trainingset wordt dan de beslissingsboom opgesteld; meer informatie over beslissingsbomen kan gevonden worden in sectie 2.3.5 (Beslissingsbomen). Ten slotte worden de labels van de samples uit de testset voorspeld aan de hand van de opgestelde beslissingsboom.
5.2 Speci eke technieken
50
5.2.3 AppRiskPred De implementatie van deze techniek (beschreven in Sectie 3.1.3), voorzien door de auteurs, is geschreven in C++. Hierbij was aangegeven dat er problemen waren met het MNBCmodel, dat daarom niet is gebruikt.
De enige informatie die deze techniek nodig heeft, zijn de permissies en categorie van de applicaties.
Aangezien de permissies al waren geëxtraheerd bij het voorbereiden van de
techniek Permissions_DT, konden de juiste permissies uit de opgeslagen bitvectoren voor die techniek worden ingeladen. Met een apart script werd al deze informatie voor de trainingset en testset dan samengevoegd tot afzonderlijk dat- les.
Hierna werden de verkregen binaries uitgevoerd met de
dat- les als programma-argumenten, met behulp van het subprocess-package dat aanwezig is in Python.
De output van dit Pythonscript is een lijst met risk scores. Gegeven een drempelwaarde, kunnen deze risk scores worden omgezet naar een binaire output door alle samples, waarvan de risk score groter is dan de drempelwaarde, output 1 te geven en alle andere samples output 0 te geven. Aangezien de echte labels van de samples uit de trainingset gekend zijn, kan voor elke mogelijke drempelwaarde gekeken worden hoeveel samples correct worden geclassi ceerd. Nadat de best mogelijke drempelwaarde is gekozen, worden de risk scores van de testset met hetzelfde model voorspeld. Hierna wordt met optimale drempelwaarde de voorspelde klasse van de ongelabelde samples bepaald.
5.2.4 Droidlegacy Sectie 3.1.4 bevat meer informatie over hoe deze techniek in zijn werk gaat. De verkregen implementatie was verspreid over een hele reeks Python- en Bashscripts. De functionaliteit uit deze scripts is samengevoegd tot twee Pythonbestanden. In het eerste bestand worden de modules voor elke applicatie opgesteld en opgeslagen. Het tweede bestand bevat het deel van de code dat deze modules uitlaadt, op basis hiervan de handtekeningen voor de malwarefamilies opstelt en voor elk test sample bepaalt welke handtekening het best overeenkomt met dit sample.
Net zoals bij AppRiskPred moet de output worden omgezet naar binair label met behulp van een drempelwaarde. Ook hier worden eerst alle scores berekend voor de samples in de
5.2 Speci eke technieken
51
trainingset (niet enkel malware dit keer). Daarna wordt de drempelwaarde gezocht die de meeste samples correct labelt. Deze optimale drempelwaarde wordt dan gebruikt om te bepalen welk labels aan de testsamples worden toegewezen. Deze techniek gaf tijdens het testen veel false positives (incorrect samples als malware beschouwen). De reden hiervoor was dat sommige handtekeningen te algemeen waren en niet overeenkomen met één speci eke malwarefamilie. Dit kan mogelijk het gevolg zijn van enkele malwaresamples die onterecht aan een bepaalde malwarefamilie zijn toegewezen. Dit probleem werd opgelost door manueel op te zoeken welke handtekeningen te algemeen waren en deze uit te sluiten. Deze aanpak is niet helemaal wetenschappelijk verantwoord, omdat de techniek wordt aangepast tot het resultaat goed is, maar het was desondanks de beste oplossing.
5.2.5 Kirin Zoals uitgelegd in Sectie 3.1.5, heeft deze techniek geen trainingset nodig om een voorspelling te maken. In dit geval zijn alle voorspellingen vooraf gebeurd en opgeslagen. De implementatie voor deze techniek is vrij beschikbaar, maar is ontwikkeld om uitgevoerd te worden op een Android toestel. De 7 regels, die deze techniek controleert, zijn dus geherimplementeert in Python. Indien aan één van deze regels is voldaan, wordt het sample beschouwd als malware.
5.2.6 API_1-NN Deze techniek voert Machinaal Leren uit op de API-calls van de applicatie en is gebaseerd op DroidAPIMiner [24]. Hiervan is echter geen originele implementatie verkregen en zijn er een paar aanpassingen doorgevoerd bij de herimplementatie. Zoals bij alle Supervised-Learningtechnieken moet eerst elke applicatie worden voorgesteld door een vector. Deze vector moet in dit geval aangeven welke API-calls worden opgeroepen door de applicatie. Om te beginnen wordt daarom de dex-code uitgepakt, gedisassembleerd en doorzocht naar strings die Landroid en -> bevatten. Landroid/net/Uri;-> parse(Ljava/lang/String;)Landroid/net/Uri; is een voorbeeld van zo'n API-call. De lijst van alle API-calls moet worden omgezet naar een vector, maar dit kan niet rechtstreeks gebeuren zoals voor de permissies in de techniek Permissions_DT. De API-calls
5.2 Speci eke technieken
52
kunnen immers niet worden geënumereerd. De oplossing die hiervoor bedacht is, is om de strings te hashen om een numerieke waarde te bekomen. Het aantal mogelijke hashwaarden is echter te groot, dus worden de rest van de hashwaarde berekend bij deling door een parameter
N.
In een bitvector van grootte
N
wordt bijgehouden welke waarden als rest worden
bekomen tijdens het verwerken van de volledige lijst van API-calls. Deze bitvector wordt dan opgeslagen in een bestand, zodat elke vector maar één keer moet worden opgesteld.
x = (b0 , . . . , bN −1 ) 1 , ∃ s ∈ API-calls: hash(s) mod N = i bi = 0 , anders
Nadat voor elke applicatie de bijhorende vector is opgesteld, kan het voorspellen van de klassen van de samples uit de testset plaatsvinden. Dit wordt gedaan aan de hand van het 1-NN-algoritme met de Euclidische afstand als metriek. Een uitgebreide uitleg kan worden teruggevonden in sectie 2.3.6 (k-nearest-neighbours), maar in het kort komt het er op neer dat voor elke testsample het trainingsample wordt gezocht dat er het dichtste bij ligt in de
N -dimensionale
ruimte. Het testsample krijgt dan dezelfde klasse als het trainingsample
toegewezen. De parameter
N , die bepaalt hoe groot de vector van elke applicatie is, moet experimenteel
bepaald worden. Wanneer men verschillende waarden voor N uitprobeert, kan men zien dat de nauwkeurigheid van de techniek (zo goed als) gelijk blijft voor grote waarden voor
N.
Zodra
N
te klein wordt, zal de nauwkeurigheid van de techniek blijven afnemen. Dit
komt door het feit dat voor een kleine
N , bepaalde API-calls worden afgebeeld op dezelfde
index van de bitvector, wat nadelig gevolgen heeft voor de nauwkeurigheid van de techniek. Door trial-and-error werd bepaald dat 1500, in dit geval, een goede waarde is voor
N.
5.2.7 No_Permissions No_Permissions is een nieuwe techniek die als doel heeft om tegen een lage kost voor bepaalde samples te kunnen besluiten dat ze waarschijnlijk geen malware bevatten.
De
redenering achter deze aanpak is dat een applicatie zonder permissies niet genoeg rechten heeft om kwaadaardige acties uit te voeren. Bij het toepassen van deze methode wordt geen model getraind, zoals bij de meeste andere technieken. Voor elk ongelabeld sample wordt gewoon gekeken of de applicatie permissies
5.2 Speci eke technieken
53
bevat of niet. Wanneer dit niet het geval is, krijgt het sample de voorspelling goodware; in het andere geval is de voorspelde klasse malware. Het is te verwachten dat deze techniek een grote hoeveelheid false positives veroorzaakt. Dit heeft als gevolg dat enkel een goodware-voorspelling nuttige informatie oplevert. Omdat voor deze techniek geen trainingset nodig is, zijn alle resultaten op voorhand berekend en opgeslagen. Bij het toepassen van de 10-fold cross validation zijn dan eenvoudigweg de juiste resultaten uit een bestand gehaald. Tijdens het testen van deze techniek bleek dat de testresultaten tegenvielen.
Namelijk,
er waren een redelijk aantal malwaresamples die toch de voorspelling goodware kregen. Na nader onderzoek bleek dat veel van deze incorrect-geclassi ceerde samples zelf een APK-bestand bevatten. Op basis van deze observatie is de techniek Contain_APK dan bedacht.
5.2.8 Contains_APK Dit is een zeer eenvoudige techniek die is bedacht tijdens het testen van de No_Permissionstechniek. Het doel van deze techniek is net het omgekeerde van de vorige: om op een snelle manier te kunnen beslissen dat een sample bijna zeker malware is. Deze techniek maakt niet gebruik van Supervised Learning en heeft dus geen trainingset nodig om correct te werken. Het APK-bestand wordt uitgepakt en doorzocht naar ZIPbestanden, aan de hand van
magic numbers.
Een magic number is een sequentie van
bytes (meestal aan het begin van een bestand) waaraan het type bestand kan worden herkend. Van deze gevonden ZIP- les wordt dan gekeken of deze misschien APK-bestanden zijn, door eerst te kijken naar de extensie en dan te kijken naar de aanwezigheid van een Android Manifest in het ZIP-bestand.
Indien een APK wordt gevonden in een sample,
krijgt dit sample de voorspelling malware; anders krijgt het de voorspelling goodware. Deze resultaten zijn opnieuw op voorhand bepaald. Deze techniek is uiteraard niet nuttig om alleen te gebruiken (enkel een zeer speci ek type malware wordt gedetecteerd), maar kan mogelijk goede resultaten behalen in samenwerking met andere technieken.
54
5.2 Speci eke technieken
EVALUATIE
55
Hoofdstuk 6 Evaluatie 6.1 Individuele detectietechnieken Om te beginnen zal een overzicht gegeven worden van de individuele detectietechnieken. Omdat de gemiddelde nauwkeurigheid van de technieken alleen niet voldoende is om bepaalde nuances weer te geven, zal voor elke techniek een tabel gegeven worden met het aantal malware- en goodwaresamples dat correct en incorrect wordt geclassi ceerd. Er zijn hier dus 4 mogelijkheden: malwaresamples die een malware-voorspelling krijgen (een true positive), malwaresamples die een goodware-voorspelling krijgen (een false positive), goodwaresamples die een malware-voorspelling krijgen (een false negative) en goodwaresamples die een goodware-voorspelling krijgen (true negative).
Een false positive wordt ook wel
een Type-I fout genoemd en een false negative staat bekend als een Type-II fout. Deze 4 waarden worden voorgesteld in een foutmatrix (zie Tabel 6.1) [33]. Op basis van deze matrix kunnen 5 getallen worden berekend die bepaalde eigenschappen van de resultaten weergeven. De nauwkeurigheid (Engels: accuracy) moet in één getal voorstellen hoe goed de techniek een willekeurig sample kan classi ceren, en wordt berekend door het aantal correct
Malware
Goodware
Voorspelling Malware
true positive (TP)
false positive (FP)
PVW
Voorspelling Goodware
false negative (FN)
true negative (TN)
NVW
Sensitiviteit (Sens)
Speci citeit (Spec)
Nauwk.
Tabel 6.1: Foutmatrix
6.1 Individuele detectietechnieken
56
geclassi ceerde samples te delen door het totale aantal samples:
nauwkeurigheid =
TP + TN TP + FP + FN + TN
Er zijn technieken die niet bedoeld zijn om een goede algemene nauwkeurigheid te hebben, maar wel om snel een hoeveelheid malware te detecteren. Zo'n techniek zou bijvoorbeeld weinig samples hebben die een malware-voorspelling krijgen, maar van deze samples zijn de meeste ook eectief malware. Contains_APK is een voorbeeld van een dergelijke techniek. Het getal dat aangeeft hoe zeker men mag zijn van een positieve voorspelling wordt de positieve voorspellende waarde (Engels: positive predictive value / precision) genoemd.
PV W =
TP TP + FP
Analoog bestaat er ook een getal die aangeeft of een negatieve voorspelling waarschijnlijk correct is of niet; de negatieve voorspellende waarde (Engels: negative predictive value).
NV W =
TN TN + FN
Ten slotte kunnen uit de resultaten ook de sensitiviteit (Engels: sensitivity / recall) en de speci citeit (Engels: speci city) worden berekend. Deze waarden stellen, respectievelijk, voor welk percentage van de malwaresamples correct worden gedetecteerd, en welk percentage van de goodwaresamples correct worden gedetecteerd.
Sens =
TP TP + FN
Spec =
TN TN + FP
Merk op dat een techniek die altijd de voorspelling malware toekent aan alle samples geen extra informatie bijbrengt, maar toch een nauwkeurigheid heeft die gelijk zal zijn aan het aantal malwaresamples gedeeld door het totaal aantal samples. Indien er evenveel malwaresamples als goodwaresamples aanwezig zijn in de dataset, heeft deze constante toewijzing een nauwkeurigheid van 50%. In zo'n dataset, hebben de beste technieken een nauwkeurigheid die zo ver mogelijk van 50% ligt. Zo is een techniek met een nauwkeurigheid van 100% even goed als een techniek met een nauwkeurigheid van 0%.
Een techniek die altijd het verkeerde label toewijst is
6.1 Individuele detectietechnieken
57
nuttig, omdat men het tegengestelde van het voorspelde label altijd correct is. Ook voor de positieve en negatieve voorspellende waarde geldt dat de waarden zo ver mogelijk van 50% moeten liggen. Per techniek wordt ook de gemiddelde uitvoeringstijd in seconden bijgehouden. Dit is de gemiddelde tijd nodig om één sample voor te bereiden en te testen met de gegeven techniek; hier wordt de tijd om het model op te stellen niet bijgerekend.
6.1.1 Adagio Deze techniek heeft een goede nauwkeurigheid en een zeer lage kost, en is dus een geschikte techniek voor algemene classi catie. We kunnen ook zien dat de techniek lichtjes beter is in het herkennen van goodware dan in het herkennen van malware, omdat de negatieve voorspellende waarde (97,33%) groter is dan positieve voorspellende waarde (91,57%). Procentueel gezien worden malwaresamples beter geclassi ceerd dan goodwaresamples. De resultaten zijn te zien in Tabel 6.2.
(kost: 18,15 s)
Malware
Goodware
Voorspelling Malware
1543
142
0,9157
Voorspelling Goodware
47
1716
0,9733
0,9704
0,9236
0,9452
Tabel 6.2: Resultaten Adagio
6.1.2 Permissions_DT De nauwkeurigheid van deze techniek is zeer hoog en de kost valt goed mee. Deze techniek is zeer gebalanceerd; alle berekende waarden liggen dichter bij elkaar (rond de 94%) dan bij de andere technieken. Deze waarden staan aangegeven in Tabel 6.3.
(kost: 16,87 s)
Malware
Goodware
Voorspelling Malware
1498
96
0,9398
Voorspelling Goodware
92
1762
0,9504
0,9421
0,9483
0,9455
Tabel 6.3: Resultaten Permissions_DT
6.1 Individuele detectietechnieken
58
6.1.3 AppRiskPred AppRiskPred is de verzamelnaam voor drie zeer gelijkaardige technieken: BNB, PNB en HMNB. (kost: 25,30 s)
Malware
Goodware
Voorspelling Malware
1224
417
0,7459
Voorspelling Goodware
366
1441
0,7975
0,7698
0,7756
0,779
Tabel 6.4: Resultaten BNB
(kost: 25,30 s)
Malware
Goodware
Voorspelling Malware
1242
441
0,7380
Voorspelling Goodware
348
1417
0,8028
0,7811
0,7626
0,7714
Tabel 6.5: Resultaten PNB
(kost: 28,20 s)
Malware
Goodware
Voorspelling Malware
1213
367
0,7677
Voorspelling Goodware
377
1491
0,7982
0,7629
0,8025
0,7842
Tabel 6.6: Resultaten HMNB
Tabellen 6.4, 6.5 en 6.6 bevatten de testresultaten voor deze drie technieken. De nauwkeurigheden liggen rond de 78%. De kost is ongeveer gelijk voor de 3 varianten. Bij elk van technieken is een goodwarevoorspelling een klein beetje geloofwaardiger dan een malwarevoorspelling. BNB en PNB zijn ongeveer even goed in het classi ceren van beide soorten samples; HMNB is lichtjes beter wanneer toegepast op goodwaresamples.
6.1 Individuele detectietechnieken
59
6.1.4 Droidlegacy Het opmerkelijke aan deze techniek is de hoge kost.
Dit illustreert waarom een com-
mercieel systeem niet enkel rekening mag houden met de nauwkeurigheid en dat er een afweging moet gebeuren tussen nauwkeurigheid en kost. Zoals te zien is in Tabel 6.7 is de nauwkeurigheid bij één van de betere (83,29%). Aangezien bij het testen van de techniek manueel bepaalde slechte handtekening van malwarefamilies zijn verwijderd, is het aantal false positives (goodwaresamples die voorspelling malware krijgen) arti cieel verlaagd. Dit zorgt voor een positive voorspellende waarde (92,25%) die veel hoger is dan de negatieve voorspellende waarde. Ook is deze techniek duidelijk beter in het classi ceren van goodwaresamples (94,99% correct) dan malwaresamples.
(kost: 63,03 s)
Malware
Goodware
Voorspelling Malware
1107
93
0,9225
Voorspelling Goodware
483
1765
0,7852
0,6962
0,9499
0,8329
Tabel 6.7: Resultaten Droidlegacy
6.1.5 Kirin Deze techniek presteert redelijk slecht in vergelijking met de andere technieken. De nauwkeurigheid is slecht (64,32%) en ook de positieve voorspellende waarde (73,34%) en de negatieve voorspellende waarde (61,73%) zijn laag.
Goodwaresamples worden wel vaak
correct geclassi ceerd (88,97%), maar dit is niet bepaald nuttig voor een techniek in een gecombineerd systeem. Aan de andere kant is de kost wel de laagste van alle technieken. De details van de resultaten staan in Tabel 6.8.
(kost: 0,60 s)
Malware
Goodware
Voorspelling Malware
564
205
0,7334
Voorspelling Goodware
1025
1653
0,6173
0,3549
0,8897
0,6432
Tabel 6.8: Resultaten Kirin
6.1 Individuele detectietechnieken
60
6.1.6 API_1-NN Zoals te zien is in Tabel 6.9 is dit de techniek met de hoogste nauwkeurigheid (95,48%). Ook is de kost één van de laagste van alle technieken.
Er is weinig verschil tussen de
betrouwbaarheid van een positieve en een negatieve voorspelling. Ook worden malware en goodware applicaties ongeveer even goed geclassi ceerd.
(kost: 10,53 s)
Malware
Goodware
Voorspelling Malware
1533
99
0,9393
Voorspelling Goodware
57
1759
0,9686
0,9642
0,9467
0,9548
Tabel 6.9: Resultaten API_1-NN
6.1.7 No_Permissions Het doel van deze techniek is om op een snelle manier voor bepaalde applicaties te kunnen bepalen dat ze waarschijnlijk goodware zijn. Als gevolg hiervan is de negatieve voorspellende waarde (81,97%) het belangrijkst.
De nauwkeurigheid is maar 47,23% (zie Tabel
6.10), maar dit is gedeeltelijk het resultaat van het feit dat er meer goodwaresamples dan malwaresamples zijn en dat de meeste samples voorspelling malware krijgen. De positieve voorspellende waarde bedraagt 46,60% en men kan dus enkel nuttige informatie halen uit een voorspelling wanneer die voorspelling goodware is. De kost voor deze techniek is redelijk hoog voor een techniek die enkel dient om goodware te herkennen. We zien dat er toch 11 malwaresamples zijn zonder permissies, ten opzichte van 50 goodwaresamples, wat nog redelijk veel is. Tijdens het testen is onderzocht hoe deze 11 samples kwaadaardige code kunnen uitvoeren zonder enige permissies, en toen is gebleken dat de meeste van deze samples zelf een kwaadaardig APK-bestand bevatten. waarom de Contains_APK techniek is ontwikkeld.
(kost: 16,87 s)
Malware
Goodware
Voorspelling Malware
1578
1808
0,4660
Voorspelling Goodware
11
50
0,8197
0,9931
0,0269
0,8911
Tabel 6.10: Resultaten No_Permissions
Dit is de reden
6.1 Individuele detectietechnieken
61
6.1.8 Contains_APK De bedoeling van deze laatste techniek is niet om een hoge nauwkeurigheid te behalen, maar om zeer speci ek type malware te vinden. De resultaten voor deze techniek staan aangegeven in Tabel 6.11.
De nauwkeurigheid is zeer laag (64,62%), maar de positieve
voorspellende waarde is de beste van alle geteste technieken (95,12%). Dit betekent dat, indien een sample geclassi ceerd wordt als malware, er een zeer grote kans is dat dit sample inderdaad malware bevat.
De negatieve voorspellende waarde is slecht en het heeft dus
niet veel zin om een beslissing te nemen over een sample indien het voorspelling goodware krijgt.
Bijna alle goodwaresamples worden echter correct geclassi ceerd (98,92%), maar
malwaresamples worden dan weer zeer vaak een verkeerd label toegewezen. De kost is zeer laag, zoals kan worden verwacht voor zo'n techniek. Ten slotte moet ook worden opgemerkt dat er niet veel samples zijn die voorspelling malware krijgen (slechts 410 van de 3448), omdat dit ook een invloed heeft op het nut van deze techniek.
(kost: 0,97 s)
Malware
Goodware
Voorspelling Malware
390
20
0,9512
Voorspelling Goodware
1200
1838
0,6050
0,2453
0,9892
0,6462
Tabel 6.11: Resultaten Contains_APK
6.1.9 Besluit individuele detectietechnieken Een overzicht van de prestaties van de verschillende technieken en hun kost kan worden teruggevonden in Tabel 6.12. Deze resultaten zijn ook gra sch weergegeven in Figuur 6.1, die de nauwkeurigheid ten opzichte van de kost uiteenzet.
Om de beste technieken te vinden, zoeken we naar technieken die een hoge nauwkeurigheid hebben en een lage kost. Informeel kunnen we stellen dat we technieken zoeken die dicht bij de rechterbenedenhoek liggen.
We merken uit deze gra ek op dat, voor deze dataset, API_1NN de beste individuele detectietechniek is: de algemene nauwkeurigheid is de hoogste van alle technieken en de kost is relatief laag. De negatieve voorspellende waarde is zelfs de hoogste van alle technieken. Indien er een systeem moet gebouwd worden met een zeer lage kost, is deze techniek alleen
6.1 Individuele detectietechnieken
62
Techniek
Kost (in s)
Nauwk.
PVW
NVW
Sens
Spec
Adagio
18,15
94,52%
91,57%
97,33%
97,04%
92,36%
API_1-NN
10,53
95,48%
93,93%
96,86%
96,42%
94,67%
BNB
25,30
77,29%
74,59%
79,75%
76,95%
77,56%
PNB
25,57
77,12%
73,80%
80,28%
78,11%
76,26%
HMNB
28,20
78,42%
76,77%
79,82%
76,26%
80,25%
0,97
64,62%
95,12%
60,50%
24,53%
0,9892%
63,03
83,29%
92,25%
78,51%
96,92%
94,99%
0,60
64,32%
73,34%
61,73%
35,49%
88,97%
No_Permissions
16,87
47,23%
46,60%
81,97%
99,31%
2,69%
Permissions_DT
16,87
94,55%
93,98%
95,04%
94,21%
0,9483%
Contains_APK Droidlegacy Kirin
Tabel 6.12: Overzicht resultaten technieken
Figuur 6.1: Nauwkeurigheid en kost van de technieken
6.1 Individuele detectietechnieken
63
gebruiken een goede keuze op korte termijn (omdat veranderingen in malware deze techniek misschien minder kunnen eectief maken). Kort daarop volgen de technieken Adagio en Permissions_DT, die nog steeds een nauwkeurigheid hebben van meer dan 90% en een kost van minder dan 20 seconden. De 3 technieken van AppRiskPred (BNB, PNB en HMNB) zijn in deze meeste gevallen beter dan Droidlegacy. Hoewel deze technieken een lagere nauwkeurigheid hebben, maakt de veel lagere kost dit goed. Kirin en Contains_APK hebben gelijkaardige waarden voor nauwkeurigheid en kost, maar toch zal Contains_APK nuttiger zijn in de context van gecombineerde technieken.
De
positieve precisie van Contain_APK is immers zeer hoog en kan in combinatie met andere technieken leiden tot een hoge gemiddelde nauwkeurigheid. De techniek No_Permissions lijkt op de gra ek veruit de slechtste techniek, maar dat komt omdat enkel de gemiddelde nauwkeurigheid wordt beschouwd. Net zoals Contains_APK, komt deze techniek pas tot zijn recht in combinatie met andere technieken.
In Figuur 6.2 worden de testresultaten gra sch weergegeven.
Elke rij stelt een Android
sample voor en bestaat uit 500 pixels. De linkerdeel guur bevat de malwaresample en de rechterdeel ggur bevat de goodwaresamples. Er zijn 10 kolommen, elk 50 pixels wijd, die overeenkomen met de individuele detectietechnieken. Elk element van 50 pixels is wit of zwart, afhankelijk van het resultaat van de techniek die overeenkomt met de kolom op het sample in die rij (zwart indien de voorspelde klasse malware is). De samples en kolommen zijn geordend om zo veel mogelijk positieve testresultaten dicht bij de linkerbovenhoek te plaatsen. De betekenis van de kolommen is, in volgorde: No_Permissions, Adagio, API_1NN, Permissions_DT, PNB, BNB, HMNB, Droidlegacy, Kirin, Contains_APK. Uit deze guur is onder andere te zien hoe complementair bepaalde technieken zijn. Zo is bijvoorbeeld te zien in de malware-deel guur (en in mindere mate ook in de goodwaredeel guur) dat Droidlegacy en PNB/BNB/HMNB voor bepaalde samples net omgekeerde labels voorspellen. Er is ook te zien dat alle malwaresamples, die door de techniek No_Permissions (eerste kolom) als goodware beschouwd, wel worden gedetecteerd door Contains_APK (laatste kolom). Het aantal samples dat hieraan voldoet is echter wel een klein deel van de volledige dataset. Ten slotte is het mogelijk om, bij nader onderzoek, te concluderen dat een beslissingsboom, opgemaakt uit deze technieken, de samples van deze dataset onmogelijk allemaal goed kan classi ceren. Er zijn namelijk samples die dezelfde resultaten hebben voor alle technieken, maar toch een verschillend label hebben.
6.1 Individuele detectietechnieken
64
(a) Malwaresamples
(b) Goodwaresamples
Figuur 6.2: Gra sche weergave testresultaten
6.2 Resultaten beslissingsbomen
65
6.2 Resultaten beslissingsbomen Net zoals voor de individuele technieken, zijn zowel de nauwkeurigheid als de kost belangrijk voor een beslissingsboom.
Vanwege het feit dat er een techniek is met een nauwkeurig-
heid van 95% en een kost van ongeveer 10 seconden, zijn alle beslissingsbomen met een nauwkeurigheid van minder dan 95% weggelaten.
Zoals beschreven in Sectie 4.5 (Beslissingsbomen genereren) zijn voor elk van de vijf beslissingsboomalgoritmen een aantal parameters in meerdere iteraties gebruteforced om meerdere beslissingsbomen voor dat algoritme te genereren. Elke beslissingsboom is gekarakteriseerd door een nauwkeurigheid en een kost. Zoals eerder al vermeld, zal de Paretogrens worden opgesteld door de beslissingsbomen weg te laten waarvoor er andere beslissingsbomen bestaan met een hogere nauwkeurigheid en een lagere kost. Deze curves bestaan uit een geordende lijst van beslissingsbomen waarvoor nauwkeurigheid en kost toenemen, en worden weergegeven in Figuur 6.3. Het opstellen van de beslissingsbomen gebeurt extreem snel; tijdens het testen zijn meerdere miljoenen beslissingsbomen getest over een periode van slechts een paar dagen. De tijd die nodig is om een nieuwe beslissingsboom op te stellen is dus verwaarloosbaar in vergelijking met het uitvoeren van de individuele detectietechnieken.
Aan deze guur is te zien dat het inderdaad mogelijk is om individuele technieken te combineren om de nauwkeurigheid te verhogen (hier is maximaal een nauwkeurigheid van 97,36% behaald) en dat de kost al bij al nog meevalt (som van de kosten van alle technieken is 209 seconden en de gemiddelde kost van de beste beslissingsbomen ligt meestal lager dan 40 seconden). Onder de verschillende beslissingsboomalgoritmen lijkt EG2 de beste te zijn, kort gevolgd door IDX en CSGain.
De curven van deze drie algoritmen komen elk op
bepaalde plaatsen onder al de andere door, wat betekent dat ze daar het beste resultaat geven. De algoritmen ID3 en CS-ID3 zijn voor geen enkele nauwkeurigheid de beste keuze.
Ze
behalen wel ongeveer dezelfde maximale nauwkeurigheid, maar voor een gegeven nauwkeurigheid hebben ze een hogere gemiddelde kost dan de drie andere algoritmen. Bij het interpreteren van deze resultaten hoort ook enige voorzichtigheid omdat, door het willekeurige aspect van cross validation, de trainingset niet constant is, wat een invloed heeft op het uiteindelijke resultaat en de prestatie. Dit probleem werd hier aangepakt door, voor elke combinatie van algoritme en parameters, vele keren cross validation toe te passen en enkel de beste resultaten te behouden. Omdat de resultaten van de beslissingsboomal-
6.2 Resultaten beslissingsbomen
66
Figuur 6.3: Prestaties van de vijf beslissingsboomalgoritmen
goritmen enkel onderling worden vergeleken, is dit geen probleem. Nu zullen een aantal van de best presterende beslissingsbomen worden besproken.
Het
eerste punt dat zal worden onderzocht, werd opgesteld door het algoritme CSGain, en behaalt een nauwkeurigheid van 96,96% voor een gemiddelde kost van 28,43 seconden. De parameters zijn: minimum 350 samples nodig voor opsplitsing, minimum 0,15 information gain en
ω
gelijk aan 0,5.
Dit resultaat komt echter niet overeen met één beslissingsboom, vanwege de 10-fold cross validation.
Tijdens het testen zijn de beslissingsbomen niet opgeslagen omdat dit neer
zou komen op het opslaan van 10 beslissingsbomen per testresultaat.
Daarom was het
nodig om achteraf opnieuw een beslissingsboom te genereren met dezelfde parameters. De beslissingsboom die werd opgesteld met dezelfde parameters als het beschouwde punt, is te zien in Figuur 6.4. Merk op dat in het rechtse deel van de beslissingsboom een subgraaf aanwezig is met 2 bladknopen die allebei het label `Goodware` dragen.
Deze subgraaf
(van 3 knopen) zou dus vereenvoudigd kunnen worden tot één enkele bladknoop met het label Goodware, waardoor de kost van de interne knoop wegvalt.
Dit gebeurt hier niet
omdat het algoritme volledig top-down is. Een mogelijke uitbreiding van het algoritme zou dus zijn om pruning toe te passen op de beslissingsboom.
Dit heeft geen invloed op de
6.3 Resultaten andere Supervised-Learningmethoden
67
nauwkeurigheid, maar verlaagt wel de gemiddelde kost.
Het tweede resultaat heeft een nauwkeurigheid van 97,19% en een gemiddelde kost van 40,84 seconden per sample. Hiervoor werd het IDX algoritme gebruikt zonder minimum aantal elementen voor opsplitsing en een minimum information gain van 0,225. Aangezien
ω
niet gebruikt wordt voor het IDX-algoritme is deze parameter hier niet van belang.
Figuur 6.5 geeft de bijhorende beslissingsboom weer.
Als laatste wordt het resultaat bestudeerd dat de hoogste nauwkeurigheid heeft en gegenereerd is met het EG2-algoritme met de parameters 10 (minimum aantal samples), 0,025 (minimum information gain) en 1 (ω ). Dit resultaat heeft een gemiddelde kost van 55,09 seconden en behaalt een nauwkeurigheid van 97,36%. De beslissingsboom, die met deze parameters is opgesteld, is te zien in Figuur 6.6.
Uit deze 3 beslissingsbomen kunnen we een aantal conclusies trekken. Ten eerste zien we dat de beslissingsbomen complexer worden naarmate de kost en de nauwkeurigheid stijgt. We kunnen ook zien dat het algoritme dat beslissingsbomen opmaakt nog kan verbeterd worden door pruning toe te passen.
Er zijn namelijk subgrafen met meerdere knopen
waarin alle bladknopen dezelfde waarde hebben, en dus kunnen worden vervangen door één enkele bladknoop. Hierdoor blijft de nauwkeurigheid gelijk, maar zal de gemiddelde kost dalen.
Ten slotte is het duidelijk uit de drie beslissingsbomen dat de technieken
die speci ek zijn ontworpen om een bepaald type malware te detecteren tegen een lage kost, zeker nuttig kunnen zijn in een gecombineerd systeem.
Zowel Contains_APK als
No_Permissions komen in elk van de onderzochte beslissingsbomen voor, ondanks het feit dat ze individueel zeer slechte resultaten behalen.
6.3 Resultaten andere Supervised-Learningmethoden Om de testresultaten van de beslissingsbomen in context te plaatsen, zijn ook een aantal andere Supervised-Learningalgoritmen uitgeprobeerd op de testresultaten van de technieken, met behulp van RapidMiner 6. Deze methoden zijn niet ontworpen om rekening te houden met mogelijke kosten van attributen, dus maken deze classi ers meestal van alle attributen gebruik. De gemiddelde kost om een label te voorspellen is dus gelijk aan de som van de kosten van alle technieken (ongeveer 209 seconden). De resultaten van deze testen staan aangegeven in Tabel 6.13.
68
6.3 Resultaten andere Supervised-Learningmethoden
Figuur 6.4: Beslissingsboom - CSGain (350; 0,15; 0,5)
6.3 Resultaten andere Supervised-Learningmethoden
Figuur 6.5: Beslissingsboom - IDX (1; 0,225; - )
69
70
6.3 Resultaten andere Supervised-Learningmethoden
Figuur 6.6: Beslissingsboom - EG2 (10; 0,025; 1)
6.3 Resultaten andere Supervised-Learningmethoden
71
Methode
Nauwkeurigheid
ID3
97,04%
1-NN
92,98%
2-NN
93,13%
3-NN
97,07%
4-NN
97,22%
5-NN
97,07%
Naive Bayes
97,39%
Neuraal netwerk
97,10%
Support Vector Machine
96,37%
Lineair Discriminant Analysis
97,01%
Tabel 6.13: Resultaten andere Supervised-Learningmethoden
Als eerste resultaat is het ingebouwde ID3-algoritme van RapidMiner toegepast op de data. We zien dat de nauwkeurigheid ongeveer overeenkomt met de resultaten van de eigen implementatie. Er is echter geen eenvoudige manier om de gemiddelde kost van de gegenereerde beslissingsboom te bepalen, dus dit kan niet worden vergeleken. Het k-nearest-neighboursalgoritme is ook aanwezig in RapidMiner. Hiervoor zijn verschillende waarden van
k
geprobeerd;
k
gelijk aan 4 levert de hoogste prestatie.
Verder zijn nog vier classi catiemethoden uitgevoerd, die allemaal een gelijkaardige nauwkeurigheid hebben. Dit toont aan dat Supervised-Learningalgoritmen voor deze dataset en verzameling technieken een maximale nauwkeurigheid kunnen behalen van ongeveer 97,3%. We kunnen aan deze cijfers zien dat de beslissingsbomen (max.
97,36%) ongeveer even
goed scoren als de andere Supervised-Learningmethoden (97,39% voor Naive Bayes), maar voor een veel lagere kost. Bovendien is het toepassen van een beslissingsboommodel heel goedkoop in vergelijking met bijvoorbeeld k-nearest-neighbours, waarbij geen van de berekeningen op voorhand kunnen gebeuren.
Beslissingsbomen zijn dus nauwkeurig, kost-
e ciënt en schaalbaar ten opzichte van andere Supervised-Learningalgoritmen wanneer het aankomt op het combineren van detectietechnieken.
72
6.3 Resultaten andere Supervised-Learningmethoden
BESLUIT
73
Hoofdstuk 7 Besluit 7.1 Conclusie Het doel van deze masterproef was te onderzoeken of bestaande statische detectietechnieken voor Android malware gecombineerd konden worden op een e ciënte en eectieve manier. De resultaten geven aan dat het inderdaad mogelijk is om een systeem te ontwerpen dat een hogere nauwkeurigheid heeft dan de individuele technieken. De winst is echter niet heel hoog (de beste techniek had een nauwkeurigheid van 95,48% en de beste beslissingsboom had nauwkeurigheid 97,36%), maar de gemiddelde kost was wel vervijfvoudigd. De reden hiervoor is dat de beste techniek de lat zeer hoog legt en het dus niet eenvoudig is om de prestatie nog te verbeteren, en ook omdat er misschien niet voldoende individuele technieken beschikbaar zijn. Of deze afweging de moeite waard is, hangt af van de situatie. Het grote voordeel van dit soort beslissingsbomen is dat ze volledig automatisch kunnen worden opgesteld. Het enige wat deze algoritmen nodig hebben om een beslissingsboom op te stellen, is een dataset die de verdeling van malware `in het wild' nabootst en een verzameling detectietechnieken. Er moet ook benadrukt worden dat deze aanpak niet beperkt is tot statische technieken op Android. Deze manier van combineren is ook toepasbaar op dynamische en hybride technieken, en ook op andere platformen (zoals Windows). Van alle bestaande technieken presteert API_1-NN veruit het beste voor deze dataset. Niet alleen heeft deze techniek de hoogste nauwkeurigheid van alle technieken; de kost is bovendien ook bij één van de laagste. EG2 is de beste van al de beslissingsboomalgoritmen die getest werden. Kort daarop volgen IDX en CSGain. ID3 en CS-ID3 zijn slechter dan de andere. Al deze algoritmen bereiken wel ongeveer dezelfde nauwkeurigheid, maar het verschil ligt in de kost die daarmee
7.2 Praktisch gebruik
74
gepaard gaat. Voor elke beslissingsboom van ID3, bestaat er een beslissingsboom van één van de drie beste algoritmen die minstens dezelfde nauwkeurigheid haalt, maar voor een lagere kost. De testresultaten van de andere Supervised-Learningmethoden tonen aan dat de nauwkeurigheid telkens rond de 97% ligt (net zoals voor de beste beslissingsbomen), maar voor een veel hogere kost. Deze methoden houden immers geen rekening met de kost van de technieken en maken vaak gebruik van alle technieken, waardoor de kost gelijk is aan de som van de kost van alle technieken. We kunnen dus besluiten dat, van de onderzochte methoden, beslissingsbomen de beste manier zijn om technieken te combineren, indien de uitvoeringskost van belang is.
7.2 Praktisch gebruik Waarvoor kan dit onderzoek nu gebruikt worden? Aangezien hier rekening wordt gehouden met de kosten van classi ceren, zijn de conclusies het best toepasbaar op systemen waar de uitvoeringskosten laag moeten worden gehouden. Een goed voorbeeld hiervan is een app store die zeer grote hoeveelheden apps moet scannen op korte tijd. Dit werk kan echter ook nuttig zijn, zelfs wanneer de uitvoeringskost niet cruciaal is; zoals bijvoorbeeld bij een online malware scanner.
Naarmate dat het aantal individuele
detectietechnieken stijgt, wordt het steeds belangrijker om ervoor te zorgen dat niet alle technieken moeten worden uitgevoerd. Mits enige aanpassingen in het algoritme, zou dit ook kunnen gebruikt worden voor een triagesysteem, dat applicaties automatisch scant om later dan dynamische of manuele analyse op uit te voeren. Het grootste probleem voor dit soort systeem, is het feit dat de output binair is en in zijn huidige vorm niet aangeeft hoe zeker deze voorspelling is.
Nog een belangrijk aspect voor het toepassen van de aanpak, is het samenstellen en bijwerken van de trainingset. In een realistische omgeving is het essentieel dat de verdeling van de applicaties in de trainingset overeenkomt met de verdeling van de applicaties die gescand zullen worden. Naargelang nieuwe soorten malware worden ontwikkeld en aan populariteit winnen of verliezen, moet de trainingset worden aangepast om deze veranderingen te weerspiegelen.
Tijdens het testen is gebleken dat de technieken die additionele informatie nodig hebben, zoals de malwarefamilie van een malwaresample, slechte resultaten kunnen opleveren indien
7.3 Mogelijke uitbreidingen
75
deze informatie niet correct is. Ook gaat er een kost gepaard met het verzamelen van deze informatie (in
¤
of in werkuren).
Om deze redenen is het voor de meeste commerciële
doeleinden waarschijnlijk beter om dit soort technieken niet te gebruiken. In Sectie 5.1 (Beperkingen) werd uitgelegd waarom technieken, die informatie over speci eke malware nodig hebben om ze te detecteren, uitgesloten worden in dit werk. In een commercieel systeem is er echter geen reden om deze technieken niet te gebruiken. Door voor alle apps eerst te controleren of er ooit al malware in is ontdekt, door gebruik te maken
1
van een service zoals VirusTotal , kan een groot deel van de malware op een eenvoudige manier worden herkend.
7.3 Mogelijke uitbreidingen De grootste uitbreiding voor dit werk zou zijn om de discrete klassen goodware en malware te vervangen door een spectrum van waarden tussen deze twee extremen.
Dit zou dus
niet meer vallen onder classi catie, maar onder regressie (zie Sectie 2.3). Beslissingsbomen waarbij de voorspelde waarde geen discrete klasse is, worden regressiebomen genoemd. Een bijkomend probleem echter is dat de vijf geteste beslissingsboomalgoritmen niet geschikt zijn voor continue attributen, dus men zal hier waarschijnlijk uitbreidingen moet toepassen zoals die in C4.5 (zie sectie 2.3.5). Een andere mogelijkheid zou zijn om andere manieren te beschouwen voor het opstellen van de beslissingsbomen.
ID3 en de andere besproken algoritmen hebben allemaal een
greedy aanpak, wat betekent dat ze in elke iteratie de beste keuze op dat moment maken, zonder rekening te houden met de volgende iteraties. Een eerste suggestie zou dus kunnen zijn om een andere aanpak te bedenken om beslissingsbomen op te stellen, die niet greedy is. Het C4.5-algoritme maakt gebruik van pruning (het samennemen van bepaalde subbomen tot een bladknoop) om over tting tegen te gaan. Deze uitbreiding kan, zoals uitgelegd in Sectie 6.2, de gemiddelde kost verlagen, zonder de nauwkeurigheid te beïnvloeden. Er bestaan ook speciale kostgevoelige beslissingsboomalgoritmen die extra kosten opleggen aan het verkeerd classi ceren van samples.
1 VirusTotal
Indien de situatie daarom vraagt, kan het
is een website die een online malwarescanner aanbiedt. Na het uploaden van het verdachte bestand worden een aantal (54 op het moment van schrijven) andere online malwarescanners aangesproken om het sample te onderzoeken. De resultaten van de verschillende scanners worden daarna verzameld in een overzicht.
76
7.3 Mogelijke uitbreidingen
gebruik deze algoritmen worden overwogen. Ten slotte wordt er momenteel nog geen rekening gehouden met het feit dat verschillende technieken dezelfde informatie (bijvoorbeeld permissies) gebruiken. Men betaalt dus voor elk van deze technieken opnieuw de kost om de informatie te verzamelen, ook al is deze informatie in een vorige techniek al eens opgezocht. Misschien kan een complexer algoritme de kosten van de technieken aanpassen na het uitvoeren van een techniek. Een laatste soort uitbreiding kan zich richten op het verruimen van de focus. Het combineren van detectietechnieken met behulp van beslissingsbomen kan worden uitgeprobeerd op andere platformen dan Android. Er kunnen ook nieuwe technieken worden geïmplementeerd. Het toelaten van dynamische en hybride technieken is ten slotte nog een manier om het onderzoek verder te zetten.
BIBLIOGRAFIE
77
Bibliogra e [1] Cisco. Cisco visual networking index: Forecast and methodology, 20132018.
White
Paper, pages 140, June 2014. [2] Abi research q1 2014 smartphone os results: Android dominates high growth developing markets, May 2014.
[3] F-Secure. Threat report h2 2013.
Threat Report, pages 140, 2013.
[4] Patrick Brady. Anatomy and physiology of an android, May 2008.
[5] Lucas Davi, Alexandra Dmitrienko, Ahmad-Reza Sadeghi, and Marcel Winandy. Privilege escalation attacks on android. In Mike Burmester, Gene Tsudik, Spyros Magliveras, and Ivana Ili¢, editors,
Information Security,
volume 6531 of
Lecture Notes in
Computer Science, pages 346360. Springer Berlin Heidelberg, 2011. [6] Adrienne Porter Felt, Elizabeth Ha, Serge Egelman, Ariel Haney, Erika Chin, and David Wagner. Android permissions: User attention, comprehension, and behavior. In
Proceedings of the Eighth Symposium on Usable Privacy and Security, SOUPS '12,
pages 3:13:14, New York, NY, USA, 2012. ACM.
[7] Yajin Zhou, Zhi Wang, Wu Zhou, and Xuxian Jiang. Hey, you, get o of my market: Detecting malicious apps in o cial and alternative android markets. In
NDSS, 2012.
[8] Tom-b, Jan 2010.
[9] Steve Hanna, Ling Huang, Edward Wu, Saung Li, Charles Chen, and Dawn Song. Juxtapp:
A scalable system for detecting code reuse among android applications.
Detection of Intrusions and Malware, and Vulnerability Assessment, volume 7591 of Lecture Notes in Computer Science, pages 6281. Springer Berlin Heidelberg, 2013. In Ulrich Flegel, Evangelos Markatos, and William Robertson, editors,
BIBLIOGRAFIE
78 [10] Guy De Tré and Antoon Bronselaer.
Information management.
Ghent, Oct 2013.
Syllabus, Second Edition.
[11] J.R. Quinlan. Induction of decision trees.
[12] J. Ross Quinlan.
Machine Learning, 1(1):81106, 1986.
C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers
Inc., San Francisco, CA, USA, 1993.
[13] Susan Lomax and Sunil Vadera. algorithms.
A survey of cost-sensitive decision tree induction
ACM Comput. Surv., 45(2):16:116:35, March 2013.
[14] Marlon Núñez. The use of background knowledge in decision tree induction.
Machine
Learning, 6(3):231250, 1991. [15] Ming Tan. Cost-sensitive learning of classi cation knowledge and its applications in robotics.
Machine Learning, 13(1):733, 1993.
Proceedings of the 11th International Joint Conference on Arti cial Intelligence - Volume 1, IJCAI'89, pages
[16] Steven W. Norton. Generating better decision trees. In
800805, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc.
[17] JasonV. Davis, Jungwoo Ha, ChristopherJ. Rossbach, HanyE. Ramadan, and Emmett Witchel.
Cost-sensitive decision tree learning for forensic classi cation.
In Johan-
Machine Learning: Lecture Notes in Computer Science, pages 622629.
nes Fürnkranz, Tobias Scheer, and Myra Spiliopoulou, editors,
ECML 2006,
volume 4212 of
Springer Berlin Heidelberg, 2006.
[18] I. Watson. Case-based reasoning is a methodology not a technology.
Knowledge-Based
Systems, 12(56):303 308, 1999. [19] Karim O Elish, Danfeng Daphne Yao, Barbara G Ryder, and Xuxian Jiang. A static assurance analysis of android applications.
Virginia Polytechnic Institute and State
University, Tech. Rep, 2013. [20] Hugo Gascon, Fabian Yamaguchi, Daniel Arp, and Konrad Rieck. Structural detection of android malware using embedded call graphs.
Workshop on Arti cial Intelligence and Security, NY, USA, 2013. ACM.
In
Proceedings of the 2013 ACM
AISec '13, pages 4554, New York,
BIBLIOGRAFIE
79
[21] Hao Peng, Chris Gates, Bhaskar Sarma, Ninghui Li, Yuan Qi, Rahul Potharaju, Cristina Nita-Rotaru, and Ian Molloy. Using probabilistic generative models for ranking
Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS '12, pages 241252, New York, NY, USA, 2012. ACM. risks of android apps. In
[22] Luke Deshotels, Vivek Notani, and Arun Lakhotia. Droidlegacy: Automated familial
Proceedings of ACM SIGPLAN on Program Protection and Reverse Engineering Workshop 2014, PPREW'14, pages 3:13:12, New
classi cation of android malware.
In
York, NY, USA, 2014. ACM.
[23] William Enck, Machigar Ongtang, and Patrick McDaniel.
On lightweight mobile
Proceedings of the 16th ACM Conference on Computer and Communications Security, CCS '09, pages 235245, New York, NY, USA,
phone application certi cation. In
2009. ACM.
[24] Yousra Aafer, Wenliang Du, and Heng Yin. Droidapiminer: Mining api-level features for robust malware detection in android. In Tanveer Zia, Albert Zomaya, Vijay
Security and Privacy in Communication Networks, volume 127 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pages 86103. Springer International Varadharajan, and Morley Mao, editors,
Publishing, 2013.
[25] Asaf Shabtai, Uri Kanonov, Yuval Elovici, Chanan Glezer, and Yael Weiss. romaly: a behavioral malware detection framework for android devices.
and-
Journal of
Intelligent Information Systems, 38(1):161190, 2012. [26] Iker Burguera, Urko Zurutuza, and Simin Nadjm-Tehrani. Crowdroid: Behavior-based
Proceedings of the 1st ACM Workshop on Security and Privacy in Smartphones and Mobile Devices, SPSM '11, pages 1526, malware detection system for android. In
New York, NY, USA, 2011. ACM.
[27] Anthony Desnos, Axelle Apvrille, Yanick Fratantonio, and Craig Smith. Androguard (https://code.google.com/p/androguard/).
[28] Apktool (https://code.google.com/p/android-apktool/).
[29] Apk downloader (http://apps.evozi.com/apk-downloader/).
BIBLIOGRAFIE
80 [30] Yajin Zhou and Xuxian Jiang. evolution. In
Dissecting android malware:
Characterization and
Security and Privacy (SP), 2012 IEEE Symposium on,
pages 95109,
San Fransico, CA, May 2012. [31] Contagio mobile (http://contagiominidump.blogspot.com). [32] Wei Yan. Hey androguard, i will crash you or your python buddy!
Blog, March 2013. [33] Howard Hamilton. Confusion matrix.
Zscaler Threat Lab
LST VAN FIGUREN
81
L¼st van guren 2.1
Overzicht van de software stack op Android [4] . . . . . . . . . . . . . . . .
2.2
Illustratie van de werking van een botnet [8]
2.3
Voorbeeld ID3-beslissingsboom
7
. . . . . . . . . . . . . . . . .
10
. . . . . . . . . . . . . . . . . . . . . . . .
21
3.1
Droidlegacy - Stap 1: klassen partitioneren in modules [22] . . . . . . . . .
33
3.2
Droidlegacy - Stap 2: opstellen handtekening van een malwarefamilie [22] .
34
3.3
Droidlegacy - Stap 3: Analyse van een ongelabeld sample [22]
. . . . . . .
35
4.1
Klassendiagram voor de implementatie van de beslissingsboomalgoritmen .
45
6.1
Nauwkeurigheid en kost van de technieken
. . . . . . . . . . . . . . . . . .
62
6.2
Gra sche weergave testresultaten
. . . . . . . . . . . . . . . . . . . . . . .
64
6.3
Prestaties van de vijf beslissingsboomalgoritmen . . . . . . . . . . . . . . .
66
6.4
Beslissingsboom - CSGain (350; 0,15; 0,5)
. . . . . . . . . . . . . . . . . .
68
6.5
Beslissingsboom - IDX (1; 0,225; - ) . . . . . . . . . . . . . . . . . . . . . .
69
6.6
Beslissingsboom - EG2 (10; 0,025; 1)
70
. . . . . . . . . . . . . . . . . . . . .
82
LST VAN FIGUREN
LST VAN TABELLEN
83
L¼st van tabellen 2.1
Voorbeeld trainingset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2
Voorbeeld ongelabelde samples . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3
Information Gain voor de attributen in Stap 1 . . . . . . . . . . . . . . . .
18
2.4
Deelverzameling stap 3, voorbeeld beslissingsboom . . . . . . . . . . . . . .
19
2.5
Information Gain voor de attributen in Stap 3 . . . . . . . . . . . . . . . .
19
2.6
Deelverzameling stap 4, voorbeeld beslissingsboom . . . . . . . . . . . . . .
19
2.7
Information Gain voor de attributen in Stap 4 . . . . . . . . . . . . . . . .
20
2.8
Voorspellingen beslissingsboom voorbeeld . . . . . . . . . . . . . . . . . . .
21
2.9
Voorspellingen k-nearest-neighbours voorbeeld . . . . . . . . . . . . . . . .
27
6.1
Foutmatrix
55
6.2
Resultaten Adagio
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.3
Resultaten Permissions_DT . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.4
Resultaten BNB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.5
Resultaten PNB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.6
Resultaten HMNB
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.7
Resultaten Droidlegacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.8
Resultaten Kirin
59
6.9
Resultaten API_1-NN
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.10 Resultaten No_Permissions
60
. . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.11 Resultaten Contains_APK . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
6.12 Overzicht resultaten technieken
62
. . . . . . . . . . . . . . . . . . . . . . . .
6.13 Resultaten andere Supervised-Learningmethoden
. . . . . . . . . . . . . .
71
