Jean-François Lalande
email: jean-francois.lalande@inria.fr

Android Malware Analysis: from technical difficulties to scientific challenges

Keywords:

Ten years ago, Google released the first version of its new operating system: Android. With an open market for third party applications, attackers started to develop malicious applications. Researchers started new works too. Inspired by previous techniques for Windows or GNU/Linux malware, a lot of papers introduced new ways of detecting, classifying, defeating Android malware. In this paper, we propose to explore the technical difficulties of experimenting with Android malware. These difficulties are encountered by researchers, each time they want to publish a solid experiment validating their approach. How to choose malware samples? How to process a large amount of malware? What happens if the experiment needs to execute dynamically a sample? The end of the paper presents the upcoming scientific challenges of the community interested in malware analysis.

Introduction

Research about Android malware mainly addresses three types of problem: deciding if an application is a malware or not (detection), classifying a malware sample among families (classification) and explaining precisely what a sample is doing (characterization). These three types of contribution require a dataset of malware for performing experiments that support the proposed contribution. Nevertheless, performing reliable experiments is not as simple as expected. In addition with the difficulties to reproduce previous experiments, many technical difficulties can have an impact on the results.

This paper summarizes the encountered difficulties when experimenting with Android malware. In particular, we focus on the choice of the malware dataset, that can have a large influence on the outperformed results. Finally, we discuss the upcoming challenges when contributing to the field of malware analysis.

Designing malware analysis experiments

Datasets

The choice of the dataset is of primary importance to discuss with accuracy the obtained results. As Android is quickly evolving, malware samples are quickly outdated and some of them cannot be installed on recent versions of the operating system. Thus, fundamental papers that have a lot of citations like Copper-Droid [START_REF] Tam | CopperDroid: Automatic Reconstruction of Android Malware Behaviors[END_REF], IntelliDroid [START_REF] Wong | IntelliDroid: A Targeted Input Generator for the Dynamic Analysis of Android Malware[END_REF], TaintDroid [START_REF] Enck | TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones[END_REF], to name a few, suffer from outdated datasets or incompatibility problems. For example CopperDroid runs on several Android versions, which is fine, but uses three outdated datasets: Contagio mobile1 , the Genome Project [START_REF] Zhou | Dissecting Android Malware: Characterization and Evolution[END_REF] and samples provided by McAfee. Contagio mobile is a blog which contains few samples, posted by contributors. The Genome Project has now closed its service and the database cannot be accessed anymore. Finally, the samples obtained from a collaboration with McAfee is of course interesting but cannot be reproduced in other papers.

The size of the dataset makes experiments difficult to compare. For example, a recent paper about malicious libraries [START_REF] Chen | Following Devil's Footprints: Cross-Platform Analysis of Potentially Harmful Libraries on Android and iOS[END_REF] provides results based on 1.3 millions of applications, whereas the experiments of TriggerScope for dealing with logic bombs evaluate the approach on 14 malware among 9,313 applications. Experiments are difficult to compare when there is so much difference between the processed number of applications. Additionally, most of the time, authors have to reimplement previous contributions, such as TriggerScope that reimplemented Kirin [START_REF] Enck | On Lightweight Mobile Phone Application Certification Categories and Subject Descriptors[END_REF], DroidAPIMiner [START_REF] Aafer | DroidAPIMiner: Mining API-Level Features for Robust Malware Detection in Android[END_REF], and FlowDroid [START_REF] Arzt | FlowDroid: Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps[END_REF], which is obviously a lot of efforts.

New datasets recenlty appeared that try to address these problems. Andro-Zoo [START_REF] Allix | AndroZoo: collecting millions of Android apps for the research community[END_REF] is a large dataset of million of applications that is helpful for a having a large diversity of benign and malware applications. In particular, they provide pairs of applications that show that a lot malware applications are repackaged version of benign applications. The AMD dataset [START_REF] Wei | Deep ground truth analysis of current android malware[END_REF] is another contributions that provides 24,650 malware samples. Some contextual information (classes, actions,. . . ) are provided that have been computed for a part by automatic tools and for the other part by a manual analysis. We believe that these two contributions for building reliable and documented datasets are an important step towards reproducible security experiments, but some questions remain, for example the lifespan of a dataset, used for training purpose [START_REF]1st International Workshop on Advances in Mobile App Analysis, A-Mobile@ASE 2018[END_REF].

Designing an experiment

From our point of view, designing an experiment for malware analysis always follows the same steps. After selecting a sample to be analyzed from the dataset, authors process this sample by applying static or dynamic analysis techniques. Depending on there goals (detection, classification, characterization), they compare the obtained performances with the results obtained by other tools. Even if this process is simple to understand, several question arise:

Is the sample really a malware? Picking up some sample from large unlabeled datasets or the play store gives a large variety of applications, representative of the reality. If this effort is continuous with time, authors are sure to capture new malware samples that appear on the play store before being removed. Then, samples should be analyzed to decide if they are malware or not, especially when evaluating a detection algorithm. For solving this issue, most of authors rely on VirusTotal to decide if a sample is malicious or not. We believe that it is not a good idea, because the analysis tools used by VirusTotal has no reason to decide accurately [START_REF] Lalande | Challenges for Reliable and Large Scale Evaluation of Android Malware Analysis[END_REF], especially for recent samples.

Where is the payload? The answer should be provided by the dataset. Most of papers use heuristics for answering this question, for example the approach of Aafer et al. [START_REF] Aafer | DroidAPIMiner: Mining API-Level Features for Robust Malware Detection in Android[END_REF] that study the API used by each part of the code. The idea behind this heuristic is that the malicious parts of the code use specific APIs and can be exposed. Identifying the payload is especially important when studying multiple repackaged applications where the payload is hidden in the code of benign applications. Nevertheless, five years after Aafer et al.'s publication, the mentioned evasion techniques, reflection, native code, encryption, dynamic loading are widely used by malware. Even benign applications now use packers that use these techniques to protect their code [6].

Is the static and dynamic analysis possible? Most approaches analyze statically the sample before eventually executing it in a sandbox or a real smartphone. Few papers mention that a static and dynamic analysis can crash. As an example, Yang et al. [START_REF] Yang | Malware detection in adversarial settings: Exploiting feature evolutions and confusions in android apps[END_REF] report in their paper that the executed sample crashes 76% of the time. The reasons behind these crashes remain unknown. It could be the setup of the experiment that is not reliable with the studied sample, for example a bad version of the operating systems, missing libraries such as the Google services, etc. For defeating the static analysis, malware can introduce some artifact for disturbing disassembly tools such as apktool [START_REF] Kiss | Kharon dataset: Android malware under a microscope[END_REF]. Consequently, in the last years, we proposed several tools for automatizing the static and dynamic analysis of Android malware [START_REF] Leslous | GPFinder: Tracking the Invisible in Android Malware[END_REF]2]. Our intention is to perform the classical steps of an analyzer: CFG extraction from a static analysis, payload identification using an heuristic similar to DroidAPIMiner, computation of execution paths, including the path that can use callbacks of the framework, and finally dynamic execution with an automatic exploration of the graphical interface. Additionally, we provide fallback methodologies when a difficulty is encountered. For example, if the Manifest file cannot be decoded, we provide a generated minimalistic one for our tools being able to run. Another example is the ability of GroddDroid to change a branching condition to force the execution flow towards a suspicious part of the code not analyzed yet.

Nevertheless, a lot of problems still exist when processing large amount of malware. The next section gives an overview of the remaining challenges.

Next upcoming challenges

As explained before, building reliable datasets remain a difficult challenge. Additionally, in some countries, sharing malicious codes is forbidden by the law. Some samples can also contain piggybacked code from copyrighted benign applications. These difficulties should be addressed by international consortiums that would provide a safe infrastructure for sharing resources. Such an effort could also help on the dataset labeling i.e. by determining the payload location, malware's actions, etc.

Experiments are also limited by the devices themselves. As it is hazardous to run a malware in an emulator, with anti analysis techniques, most of authors run their experiment on a real smartphone with an eventually modified operating system. In such conditions, running a clean execution of a malware, including a smartphone flashing step, requires several minutes. If several environments or parameters have to be tested the total running time becomes prohibitive.

Finally, these ten years of research efforts are intimately linked with Google's roadmap. In the near future, introducing a new operating system like Fuschia can lead to the restart of many results, at the price of few novelty. In the meantime, the ecosystems that Google try to promote has received few attention from the research community. For example, Android automotive, Wear OS has not being extensively studied and malware may exist on these platforms -if they don't already exist.

http://contagiominidump.blogspot.com

This work has received a French government support granted to the COMIN Labs excellence laboratory and managed by the National Research Agency in the "Investing for the Future" program under reference ANR-10-LABX-07-01.


Min Incomparable

© Dimo Brockhoff
email: dimo.brockhoff@inria.fr

Deb Srinivasan

Manuel López-Ibáñez

[ López-Ibáñez

López

Dimo Brockhoff

[ Wagner

David Coello A Coello

Gary B Van Veldhuizen

Kluwer Lamont

Mastertitelformat Bearbeiten

Mastertitelformat bearbeiten A Brief Introduction to Multiobjective Optimization better worse incomparable

Keywords: rank objectives, define constraints, … rank objectives, define constraints, … Automated Benchmarking Weighted Hypervolume Indicator

single optimal solution, but some solutions ( ) are better than others ( ) max min incomparable

Mastertitelformat bearbeiten

Some problems are easier to solve in a multiobjective scenario example: TSP [START_REF] Knowles | [END_REF] Multiobjectivization by addition of new "helper objectives" [Jensen 2004] job-shop scheduling [Jensen 2004], frame structural design [Greiner et al. 2007], VRP [START_REF] Watanabe | [END_REF], ... by decomposition of the single objective TSP [Knowles et al. 2001], minimum spanning trees [START_REF] Neumann | [END_REF], protein structure prediction [Handl et al. 2008a], ... also backed up by theory e.g. [START_REF] Brockhoff | [END_REF], Handl et al. 2008b] related to constrained and multimodal single-objective optimization see also this recent overview: [START_REF] Segura | [END_REF]]

Multiobjectivization

Mastertitelformat bearbeiten

Often innovative design principles among solutions are found

Example: Cantilever beam topology optimization [START_REF] Bandaru | [END_REF] Innovization min min

Mastertitelformat bearbeiten

Often innovative design principles among solutions are found Innovization [START_REF][END_REF] = using machine learning techniques to find new and innovative design principles among solution sets = learning from/about a multi-objective optimization problem

Other examples:

SOM for supersonic wing design [Obayashi and Sasaki 2003] Biclustering for processor design and knapsack [START_REF] Ulrich | [END_REF] Successful case studies in engineering (noise barrier design, polymer extrusion, friction stir welding) But: can also result in cycles if reference point is not constant [Judt et al. 2011] expensive to compute exactly [START_REF] Bringmann | [END_REF] less and less practically important [START_REF] Guerreiro | [END_REF] Hypervolume-Based Selection

Mastertitelformat bearbeiten

Concept can be generalized to any quality indicator for example: R2-indicator [Brockhoff et al. 2012], [START_REF] Trautmann | [END_REF]],

[ Díaz-Manríquez et al. 2013] Generalizable also to contribution to larger sets HypE [START_REF] Bader | [END_REF]: Hypervolume sampling + contribution if more than 1 (random) solution deleted

Indicator-Based Selection

Optimal µ-Distribution:

A set of µ solutions that maximizes a certain unary indicator I among all sets of µ solutions is called optimal µ-distribution for I.

[ Auger et al. 2009a] The Optimization Goal in Indicator-Based EMO contain equally spaced points iff front is linear density of points with the slope of the front [START_REF] Friedrich | [END_REF]]:

optimal µ-distributions for the hypervolume correspond to ε-approximations of the front ! (probably) does not hold for > 2 objectives

Optimal µ-Distributions for the Hypervolume

Mastertitelformat bearbeiten

Open Questions: How do the optimal µ-distributions look like for >2 objectives? how to compute certain indicators quickly in practice? several recent improvements for the hypervolume indicator [Yildiz and Suri 2012], [Bringmann 2012], [Bringmann 2013] [Guerreiro and[START_REF] Guerreiro | [END_REF] how to do indicator-based subset selection quickly? also here several recent improvements [START_REF] Kuhn | [END_REF]], [START_REF] Bringmann | [END_REF]], [START_REF] Guerreiro | [END_REF] what is the best strategy for the subset selection?

Mastertitelformat bearbeiten

Attainment function approach applies statistical tests directly to the approximation set detailed information about how and where performance differences occur

Two Approaches for Empirical Studies

Quality indicator approach reduces each approximation set to a single quality value applies statistical tests to the quality values see e.g. [Zitzler et al. 2003]

Mastertitelformat bearbeiten

Note: success probability can be naturally replaced by the average runtime of an artificially restarted algorithm (aRT): code available at http://github.com/numbbo/coco/ see also [START_REF] Brockhoff | [END_REF] Plotting Instructor Biography: Dimo Brockhoff

  of a set and a decision for a solution EMO tutorial, GECCO'2018

[

  weighted sum approach Disadvantage: not all Paretooptimal solutions can be found if the front is not convex y = w 1 y 1 + … + w k y k (w 1 , w 2 , …, w k ) weighted Tchebycheff Several other scalarizing functions are known, see e.g.[START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF]]y = max | λ i (z i -y i ) | (λ 1 , λ 2 , …,λ k ) goes back to a proposal by David Goldberg in 1989. ... is based on pairwise comparisons of the individuals only. dominance rank: by how many individuals is an individual dominated? objectives percentage of non-dominated solutions within a random sample quickly approaches 100 % optimization is mainly guided by diversity criterion apply secondary criterion compliant with dominance relation Remark: Many-Objective Optimization Mastertitelformat bearbeiten Latest Approach (SMS-EMOA, MO-CMA-ES, HypE, …) use hypervolume indicator to guide the search: refines dominance Main idea Delete solutions with the smallest hypervolume contribution d(s) = I H (P)-I H (P / {s}) iteratively

  is to maximize a unary indicator… we have a single-objective problem on sets but what is the optimum? important: population size µ plays a role!

  see http://www.tik.ee.ethz.ch/sop/ download/supplementary/testproblems/ Mastertitelformat bearbeiten Hypervolume indicator refines dominance relation most results on optimal µ-distributions for hypervolumeOptimal µ-Distributions (example results)[Auger et al. 2009a]:

  multiobjective EAs were mainly compared visually: ZDT6 benchmark problem: IBEA, SPEA2, NSGA-II

  into a set problem define an objective function ("quality indicator") on sets use the resulting total (pre-)order (on the quality values)Question:Can any total (pre-)order be used or are there any requirements concerning the resulting preference relation? relation iffA B ∧ B A ⇒ A B ∧ B A (better ⇒ better) ⇒ fulfills requirementweakly refines a preference relation iffA B ∧ B A ⇒ A B (better ⇒ weakly better)⇒ does not fulfill requirement, but does not contradict ! sought are total refinements… [Zitzler et al. 2010] B) = how much needs A to be moved to weakly dominate B A B :⇔ I(A) ≥ I(B) A B :⇔ I(A,B) ≤ I(B,A) ,R) = how much needs A to be moved to weakly dominate R A B :⇔ I(A,R) ≤ I(B,R) diploma in computer science (Dipl.-Inform.) from University of Dortmund, Germany in 2005, Dimo Brockhoff received his PhD (Dr. sc. ETH) from ETH Zurich, Switzerland in 2009. Between June 2009 and October 2011 he held postdoctoral research positions---first at Inria Saclay Ile-de-France in Orsay and then at Ecole Polytechnique in Palaiseau, both in France. Since November 2011, Dimo has been a permanent researcher at Inria: from 2011 till 2016 with the Inria Lille -Nord Europe research center and since October 2016 with the Saclay -Ilede-France research center, co-located with CMAP, Ecole Polytechnique. His most recent research interests are focused on evolutionary multiobjective optimization (EMO) and other (single-objective) blackbox optimization techniques, in particular with respect to benchmarking, theoretical aspects, and expensive optimization.

EMO tutorial, GECCO'2018, Kyoto, Japan, July 2018 © Dimo Brockhoff

© Manuel López-Ibáñez[START_REF] López-Ibáñez | [END_REF]

Acknowledgements

57

Mastertitelformat bearbeiten

The Empirical Attainment Function "counts" how many solution sets attain or dominate a vector at time :

with ⊴ being the weak dominance relation between a solution set and an objective vector at time .

Note that is the empirical cumulative distribution function of the achieved objective function distribution at time T in the single-objective case ("fixed budget scenario"). Refine/modify dominance relation, e.g.: using goals, priorities, constraints [Fonseca and Fleming 1998a,b] using different types of dominance cones [START_REF] Branke | [END_REF] Use quality indicators, e.g.: based on reference points and directions [Deb andSundar 2006, Deb andKumar 2007] based on the hypervolume indicator [START_REF] Trautmann | R2-EMOA: Focused Multiobjective Search Using R2-Indicator-Based Selection[END_REF]Trautmann 2010] based on the R2 indicator [START_REF] Trautmann | [END_REF] Incorporation of Preferences During Search