Pablo Mesejo
email: pmesejo@ce.unipr.it

Andrea Valsecchi
email: andrea.valsecchi@softcomputing.es

Linda Marrakchi-Kacem

Stefano Cagnoni
email: cagnoni@ce.unipr.it

Sergio Damas
email: sergio.damas@softcomputing.es

Biomedical Image Segmentation using Geometric Deformable Models and Metaheuristics

Keywords: Image Segmentation, Deformable Models, Deformable Registration, Genetic Algorithms, Scatter Search

This paper describes a hybrid level set approach for medical image segmentation. This new geometric deformable model combines region-and edge-based information with the prior shape knowledge introduced using deformable registration. Our proposal consists of two phases: training and test. The former implies the learning of the level set parameters by means of a Genetic Algorithm, while the latter is the proper segmentation, where another metaheuristic, in this case Scatter Search, derives the shape prior. In an experimental comparison, this approach has shown a better performance than a number of state-of-the-art methods when segmenting anatomical structures from different biomedical image modalities.

Introduction

Image segmentation is commonly defined as the partitioning of an image into non-overlapping regions that are homogeneous with respect to some visual feature, such as color or texture [START_REF] Pham | Current Methods in Medical Image Segmentation[END_REF]. In many medical imaging applications, segmentation algorithms play a crucial role by automatically identifying anatomical structures and other regions of interest. Such algorithms are nowadays in the core of multiple tasks, like quantification and measurement of tissue volumes, localization of pathologies or computerintegrated surgery. It is important to highlight that manual segmentation is not only tedious and time consuming but, sometimes, also inaccurate, hence the importance of developing automatic and accurate segmentation methods.

In particular, medical imaging segmentation is usually challenging due to poor image contrast, noise, diffuse organ/tissue boundaries, and artifacts. These problems can cause considerable difficulties when applying traditional segmentation techniques, such as edge detection or thresholding. Consequently, an intelligent way of proceeding is to incorporate as much prior knowledge as possible about the particular object and image modality to segment. To address these difficulties, deformable models have been extensively studied and widely used in medical image segmentation with interesting results [START_REF] He | A comparative study of deformable contour methods on medical image segmentation[END_REF][START_REF] Heimann | Statistical shape models for 3D medical image segmentation: a review[END_REF].

A single source of prior knowledge is usually not enough to satisfactorily tackle medical image segmentation problems. Therefore, the development of hybrid approaches combining different sources of information has been a major focus in the field of image segmentation [START_REF] Malik | Contour and Texture Analysis for Image Segmentation[END_REF][START_REF] Zhang | Medical Image Segmentation Using New Hybrid Level-Set Method[END_REF][START_REF] Chupin | Automatic segmentation of the hippocampus and the amygdala driven by hybrid constraints: Method and validation[END_REF]. In this work, the search/learning abilities of metaheuristics and the capability of geometric deformable models to handle topological changes are combined. Three sources of information (a region term, a shape prior, and an edge term) are used to accurately segment the organs of interest in different medical image modalities: microscopy, Xray computed tomography (CT), and magnetic resonance imaging (MRI). In our proposal, metaheuristics [START_REF] Gendreau | Handbook of Metaheuristics[END_REF] have capital importance in two stages. First, during the training process of the new model, the tuning of the parameters is carried out by a Genetic Algorithm [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]. Second, in the proper segmentation stage, the shape prior is obtained by a deformable registration process guided by Scatter Search [START_REF] Laguna | Scatter search: methodology and implementations in C[END_REF].

Every image modality has its own peculiarities, thus the training phase allows our model to learn the most suitable parameters for a specific modality/anatomical district using few images as paradigmatic examples. In turn, the segmentation phase uses only one manually segmented reference image to generate the prior shape knowledge that will guide, together with the region-and edge-based terms, the evolution of the moving contour.

To assess the quality of the new approach, we developed an experimental comparison including seven state-ofthe-art segmentation methods. The study was carried out on four different datasets, for a total of 22 microscopy, 11 MR, and 5 CT images.

This paper is structured as follows: in section 2 we provide the theoretical foundations necessary to understand our work. In section 3, a general overview of the method is presented, providing details about the different terms used in our deformable model. Finally, section 4 presents the results and the statistical analysis of the experimental comparison, followed, in section 5, by some final remarks and a discussion about possible future developments.

Theoretical Background

In this section, an overview of the main techniques applied in our approach (geometric deformable models, image registration and metaheuristics) and previous related work are presented.

Deformable Models

The term "deformable models" (DMs) was first used in the late eighties [START_REF] Terzopoulos | Deformable Models[END_REF] with reference to curves or surfaces, defined within the image domain, that are deformed under the influence of "internal" forces, related with the curve features, and "external" forces, related with the features of the image regions surrounding the curve. Internal forces enforce regularity constraints and keep the model smooth during deformation, while external forces are defined to attract the model toward features of the object of interest.

DMs are segmentation techniques that use prior information about the shape of the object to be located or segmented. They start with some initial boundary shape represented in the form of a curve, and iteratively modify it by applying various shrink/expansion operations according to some energy function. DMs can either be regionbased or edge-based approaches, depending on the feature they rely on to segment the object of interest. Regionbased methods usually proceed by partitioning the image into connected regions by grouping neighboring pixels with similar features. Edge-based methods, instead, are focused on contour detection, relying on discontinuities in image values between distinct regions.

There are basically two types of DM depending on the kind of shape representation used: parametric/explicit and geometric/implicit.

• Parametric Deformable Models. This type of DM represents curves and surfaces explicitly in their parametric forms during deformation, allowing direct interaction with the model and leading to a compact representation for fast real-time implementation. As examples of parametric DMs we could cite "snakes" or Active Contour Models (ACMs) [START_REF] Kass | Snakes: Active contour models[END_REF], Active Shape Models (ASMs) [START_REF] Cootes | Active shape models-their training and application[END_REF], Active Appearance Models [START_REF] Cootes | Active Appearance Models[END_REF][START_REF] Cootes | Comparing Active Shape Models with Active Appearance Models[END_REF], and Topological Active Nets (TANs) [START_REF] Bro-Nielsen | Active nets and cubes[END_REF].

• Geometric Deformable Models. Geometric DMs are based on curve evolution theory [START_REF] Kimia | Shapes, Shocks, and Deformations I: The Components of Two-Dimensional Shape and the Reaction-Diffusion Space[END_REF][START_REF] Kimmel | Finding Shortest Paths on Surfaces Using Level Sets Propagation[END_REF][START_REF] Sapiro | Affine Invariant Scale-Space[END_REF] and the Level Set method [START_REF] Osher | Fronts propagating with curvaturedependent speed: algorithms based on Hamilton-Jacobi formulations[END_REF][START_REF] Sethian | Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry[END_REF]: curves and surfaces are adapted using only geometric measures, resulting in deformations that are independent of the parameterization but, as in parametric DMs, also rely on image data to delineate object boundaries. Since the adaptation is independent of parameterization, the evolving curves and surfaces can be represented implicitly as a level set of a higher-dimensional function and topological changes can be handled automatically.

Among geometric models, the Level Set (LS) method [START_REF] Osher | Fronts propagating with curvaturedependent speed: algorithms based on Hamilton-Jacobi formulations[END_REF] relies on an evolving closed surface defined by a moving interface, the front, which expands into the image. The interface Γ(t) can be characterized as a Lipschitz continuous function:

   φ(t, x) > 0 for x inside Γ(t) φ(t, x) < 0 for x outside Γ(t) φ(t, x) = 0 for x on Γ(t)
The front or evolving boundary, denoted by Γ, is represented by the zero level Γ(t) = {x | φ(t, x) = 0} of a LS function φ(t, x). The dynamics of φ can be described by the following general form:

∂φ ∂t + F |∇φ| = 0
known as the LS equation, where F is called the speed function and ∇ is the spatial gradient operator. F can depend on position, time, the geometry of the interface (e.g., its normal or its mean curvature), or the different image features.

In any case, the definition of the LS function φ is essential. One common choice is the signed distance function d(x), which gives the distance of a point to the surface and the sign: generally d > 0 if the point x is outside and d < 0 if it is inside the surface (assuming it is a closed surface). This definition is especially interesting to avoid numerical instabilities and inaccuracies during computations. But even with this definition, φ will not remain a signed distance function all the time and a reinitialization procedure to keep the LS intact will be needed [START_REF] Osher | Level Set Methods and Dynamic Implicit Surfaces[END_REF].

Metaheuristics

The classic gradient search techniques perform efficiently when the problem under consideration satisfies tight constraints. But when the search space is discontinuous, noisy, high-dimensional and multimodal, then metaheuristics [START_REF] Gendreau | Handbook of Metaheuristics[END_REF] have been found to consistently outperform traditional methods. Among the stochastic approaches to continuous optimization, Evolutionary Algorithms (EAs) and Swarm Intelligence (SI) algorithms, as well as other metaheuristics [START_REF] Luke | Essentials of Metaheuristics[END_REF], offer a number of attractive features: no requirement for a differentiable or continuous objective function, robust and reliable performance, global search capability, virtually no need of specific information about the problem to solve, easy implementation, and implicit parallelism.

Genetic Algorithms

Genetic Algorithms (GAs) [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF] are stochastic, parallel search algorithms based on the principles of natural selection. GAs were designed to efficiently search large, non-linear, poorly-understood search spaces where expert knowledge is scarce or difficult to encode and where traditional optimization techniques fail. They are flexible, robust, and try to exhibit the adaptiveness of biological systems.

These algorithms encode a potential solution to a specific problem into a chromosome-like data structure and apply recombination operators to preserve critical information. The main features of a GA are the encoding of individuals as strings of symbols, the individuals selection policy, and the use of both the mutation and recombination operators. The basic outline of a GA is shown in Algorithm 1.

Algorithm 1 Genetic Algorithm Pseudocode

Generate a random population of chromosomes while stopping criterion is not met do Decode each chromosome into an individual Evaluate each individual's fitness Generate a new population, partly by cloning (copying), partly by recombining, partly by mutating the chromosomes of some selected (usually among the best ones) individuals end while

Scatter Search

Scatter Search (SS) [START_REF] Laguna | Scatter search: methodology and implementations in C[END_REF] is based on a systematic combination between solutions (instead of randomized, as is usual in EAs) taken from a subset of the population, named the "reference set", that is usually significantly smaller than a typical EA population. SS is composed of five structural "blocks" or methods:

Image Registration

Image registration (IR) refers to the process of geometrically aligning multiple images having a shared content [START_REF] Zitová | Image registration methods: a survey[END_REF]. The alignment is represented by a spatial transformation that overlaps the common part of the images. One image, the scene, is transformed to match the geometry of the other image, called the model.

Three main components characterize an IR method: the transformation model, the similarity metric and the optimization process. The transformation model determines what kind of transformations can be used to align the images. Transformation models vary greatly in complexity, ranging from simple combinations of translation and rotation up to elastic transformations that can represent local deformations and warpings.

The similarity metric is the component that measures the quality of an alignment. In medical applications, the most common approach, called intensity-based, compares the joint distribution of intensity values between the scene and the model once a transformation has been applied. The degree of matching can be computed from the intensity distributions using measures such as the mean square error, the correlation coefficient or the mutual information [START_REF] Pluim | Mutualinformation-based registration of medical images: a survey[END_REF].

The optimization procedure is the component responsible for finding an appropriate transformation to carry out the registration. A transformation is specified by a series of parameters (e.g. a translation vector and a rotation angle), which turns the registration into a continuous optimization problem. Classic numerical optimization algorithms such as gradient descent, Newton's method, Powell's method and discrete optimization [START_REF] Maes | Comparative evaluation of multiresolution optimization strategies for image registration by maximization of mutual information[END_REF][START_REF] Klein | Evaluation of Optimization Methods for Nonrigid Medical Image Registration Using Mutual Information and B-Splines[END_REF] are among the most common choices for the optimization component, as well as approaches based on EAs and other metaheuristics [START_REF] Damas | Medical Image Registration Using Evolutionary Computation: An Experimental Survey[END_REF].

In this study, image registration is used as a preliminary step in a segmentation process. We assume to have an atlas available (i.e., a typical or average image of the anatomical region to be segmented), in which the target region has been already labeled. The atlas-based segmentation process [START_REF] Cabezas | A review of atlas-based segmentation for magnetic resonance brain images[END_REF] begins by registering the atlas to the input image. Then, the region of the target image that overlaps the labeled region in the atlas is the result of the segmentation process. See Figure 1 for an example of this procedure.

Atlas

Input image Registered image Result The quality of atlas-based segmentation depends closely on the accuracy of the registration step, although the anatomical variability in the target region can limit the effectiveness of the method.

Image Segmentation using Deformable Models and Metaheuristics

It is fundamental to understand that the combination of internal and external forces in a DM determines a target function to minimize, whose minimum is theoretically located at the boundary of the object to segment. This target function can be very complex (noisy, highly-multimodal) and the classic algorithms fail at minimizing it [START_REF] Mesejo | Automatic Hippocampus Localization in Histological Images using Differential Evolution-Based Deformable Models[END_REF]. Hence, the global search capabilities of metaheuristics can be very beneficial to optimize this function. Furthermore, the automatic learning of DM parameters is also possible with these intelligent techniques [START_REF] Heydarian | Optimizing the Level Set Algorithm for Detecting Object Edges in MR and CT Images[END_REF]. In fact, this automatic parameter configuration is even desirable since it is known that manual parameter tuning is time consuming and may introduce a bias in comparing an algorithm with a reference, due to better knowledge of the algorithm under consideration with respect to the reference, or to possible different time spent tuning each of them.

In the literature several examples can be found which hybridize parametric DMs and metaheuristics. In [START_REF] Ballerini | Genetic Snakes for Medical Images Segmentation[END_REF] and [START_REF] Chen | A self-learning segmentation framework-the Taguchi approach[END_REF], snakes are combined with an optimization procedure based on GAs. In [START_REF] Mcintosh | Medial-based Deformable Models in Non-convex Shape-spaces for Medical Image Segmentation using Genetic Algorithms[END_REF] a GA evolves a population of medialbased shapes extracted from a training set, using prior shape knowledge to produce feasible deformations while also controlling the scale and localization of these deformations. In [START_REF] Hsu | Automatic segmentation of liver PET images[END_REF] an ACM is applied to the automatic segmentation of PET images of liver; a GA is used to find optimal parameters values for the edge detection step. Also, in [START_REF] Mesejo | Automatic Hippocampus Localization in Histological Images using Differential Evolution-Based Deformable Models[END_REF], different metaheuristics are compared (Particle Swarm Optimization, SS, GA, Simulated Annealing, Differential Evolution) to optimize an ASM and localize the hippocampus in microscopy images. With respect to standard and extended TANs, in [START_REF] Ibáñez | Genetic approaches for topological active nets optimization[END_REF], [START_REF] Novo | Topological Active Models optimization with Differential Evolution[END_REF] and [START_REF] Bova | Image Segmentation Using Extended Topological Active Nets Optimized by Scatter Search[END_REF], the minimization of TANs energy to segment CT images is carried out by means of GA and memetic algorithms, Differential Evolution and SS, respectively.

In relation to geometric DMs, much fewer proposals of hybridization have been presented. In [START_REF] Ghosh | A Genetic Algorithm-Based Level Set Curve Evolution for Prostate Segmentation on Pelvic CT and MRI Images[END_REF] a GA is used to perform LS curve evolution using texture and shape information to automatically segment the prostate in CT and MRI pelvic images. In [START_REF] Heydarian | Optimizing the Level Set Algorithm for Detecting Object Edges in MR and CT Images[END_REF], a GA is used to find an optimal set of parameters that characterize the LS method in CT and MRI segmentation. In [START_REF] Feltell | 3D level set image segmentation refined by intelligent agent swarm[END_REF], the initial segmentation based on the LS method is refined using swarms of intelligent agents. Finally, in [START_REF] Mesejo | An experimental study on the automatic segmentation of in situ hybridization-derived images[END_REF], a comparative study on the segmentation of histological images is carried out where different geometric approaches are initialized using metaheuristics and parametric DMs.

HybridLS method

In this section, we present a novel segmentation approach based on the LS method, called HybridLS, that combines edge, region and prior shape knowledge of the target object to guide the LS evolution. Moreover, we take advantage of the beneficial characteristics of metaheuristics to automatically learn the inherent parameters of a specific type of object using training data (a set of already segmented images). In its first stage, using an atlas of the target object, HybridLS performs atlas-based segmentation of the image under consideration, as in section 2.3. This requires In the bottom row, the input image is overlapped with the current contour, which is colored according the force. Green means the force is close to zero, while blue and red colors mark inward and outward forces, respectively. In this example, the region term (d) is correctly moving the contour towards the lungs boundaries, as they define two very homogeneous areas. The prior term (e) is just pulling towards the prior segmentation (b). Finally, the edge term (f) is moving the level set towards the closest edges, regardless whether these belongs to the lungs boundaries or not.

Atlas-based segmentation

the availability of a single image of a similar target object, along with its segmentation. The initial registration-based step provides a prior segmentation that will allow the LS to start its evolution near the area to be segmented. This benefits both the speed and the accuracy of the segmentation since, with a default initialization over the whole image, features located far from the target area are more likely to negatively influence the evolution of the LS. The LS moves under the influence of three force terms, each providing information about a different characteristic of the current contour. There are a region, an edge and a prior term. The region term minimizes the inhomogeneity of the intensity values inside and outside the surface enclosed by the evolving contour, while the edge term attracts the curve towards natural boundaries and other edges of the image. Finally, the prior term moves the LS towards the prior segmentation obtained by the registration, incorporating the information gathered at the first stage of the method in the later segmentation process. Note that this is rather different than just using the prior as initial contour for the LS. Indeed, the prior term, rather than its initial location, influences the evolution of the contour, and can balance the other forces when they are small or inconsistent, leading to a more "conservative" segmentation with respect to using the initial contour.

Figure 3 provides an overview of HybridLS, while Figure 2 shows a visual example of the effect of three force terms in segmenting a lung CT. The total force acting on the LS is a linear combination of the force terms

F tot = w r F r (C) + w e F e (C) + w p F p (C, P ) ( 1
)
where C is the current contour and P is the prior segmentation. Along with the specific parameters for each term, the use of weights provides flexibility to our approach, allowing it to be adapted to the features and particularities of the objects to be segmented. In HybridLS, a GA is in charge of tuning the weights and the parameters of each term based on training data.

In what follows, we describe the components of Hy-bridLS, starting with the computation of the registrationbased prior. Then, we define the three force terms and show how to compute them. Finally, we provide details about the GA and the parameter learning phase.

Registration-based prior

The registration algorithm we used is a recent contribution [START_REF] Valsecchi | Intensity-based Image Registration using Scatter Search[END_REF] called SS + . The optimization procedure, the core of the registration process, is based on the Scatter Search metaheuristic (section 2.2), which has been successfully used in a number of works in image registration [START_REF] Cordón | Scatter Search for the Point-Matching Problem in 3D Image Registration[END_REF]. In its original study on brain MRI, SS + provided superior results compared to other established techniques. Moreover, SS + delivered the best performance in a preliminary study on the registration of histological images.

In this work, the applications of SS + are extended to histological and CT images. The registration is performed in two steps, beginning with affine registration. Being a composition of translation, rotation, scaling and shearing operations, an affine transform can remove large misalignments between the images. Then, a deformable B-Splinebased registration takes care of adjusting the overlap locally, to match the finer details.

To compute a prior, one of the training images plays the role of the atlas. In cases where the target object has a large anatomical variability, a single atlas cannot express the whole distribution of possible shapes the object can assume, leading to poor registration results. This can be improved by using multiple atlases and selecting the most similar atlas for the registration to the target.

In HybridLS, the prior is obtained considering multiple images to be used as atlas. To select the actual atlas, all candidate images are registered to the target image using affine registration. Then, the candidate atlas having the highest similarity metric value is selected for the further B-Spline registration step.

Force terms

Region term

Our region term is borrowed from the classic "Active Contours Without Edges" (CV) [START_REF] Chan | Active Contours without Edges[END_REF] method by Chan and Vese. This algorithm was designed to detect objects whose boundaries are not necessarily defined by gray level gradients; indeed, it ignores edges completely, converting CV in a region-based method. The idea is to separate the image into two regions having homogeneous intensity values. More formally, the process minimizes the energy functional shown in Equation 2. The functional is used to evolve a LS representing the contour C, using the conventional variational calculus approach.

E(C) = µ • Length(C) + ν • Area(C) + λ 1 C |I(x, y) -I C | 2 dx dy+ + λ 2 Ω\C |I(x, y) -I Ω\C | 2 dx dy (2)
In the equation, I is the intensity value of the image to be segmented and I is its average value. Along with the length of C and its area, there are a third and fourth term representing the variance of the intensity level (i.e., the homogeneity) inside and outside C. Each term has a weight that determines its influence on the total energy, so that, for instance, the smaller µ, the more the length of the curve can increase without penalizing the minimization.

In HybridLS, we are interested in a pure region-based term without area or length restrictions, therefore we just use the two homogeneity terms. Therefore, in terms of force acting on the LS, we get

F r (x, y, C) = λ 1 |I(x, y) -I C | 2 (x, y) ∈ C λ 2 |I(x, y) -I Ω\C | 2 (x, y) ∈ C (3)
Figure 4: Vector field kernel used to compute the VFC term.

Edge term

The edge term incorporates the information about the boundaries in the image. Basically, the edge term pulls each point of the contour towards the closest edge. Our edge term is based on Vector Field Convolution (VFC) [START_REF] Li | Active contour external force using vector field convolution for image segmentation[END_REF]. Compared to other edge-based forces such as Gradient Vector Flow [START_REF] Xu | Gradient Vector Flow: A New External Force for Snakes[END_REF], VFC has a lower computational cost and shows better robustness to noise and initialization. In addition, it showed good performance as external force for DMs [START_REF] Bova | Image Segmentation Using Extended Topological Active Nets Optimized by Scatter Search[END_REF][START_REF] Li | Active contour external force using vector field convolution for image segmentation[END_REF].

The VFC is static, in the sense that it does not depend on the current LS but only on the target image, therefore the field is calculated only once. The computation of the force occurs in two independent steps. First, an edge map of the target image is obtained applying Gaussian smoothing followed by the Sobel edge detector [START_REF] Gonzalez | Digital Image Processing[END_REF]. Then, the edge map is convolved with a vector field kernel K in which each vector points to the origin, as in Figure 4. The magnitude of the vectors decreases with the distance d, in such a way that distant edges produce a lower force than close edges (the actual value is 1/d γ+1 ). For a point c of contour C, the edge term is simply the normal component of the VFC with respect to C.

Prior term

The aim of the prior term is to move the LS towards the prior segmentation. Also, we want the module of every force vector to be proportional to the overlap between the current evolving curve and the prior segmentation. The idea about how to compute the actual force comes from the region term. If one considers the prior segmentation as a binary image, having an intensity value inside the object and another one outside, this image has two regions that are perfectly homogeneous. This is exactly the kind of result our region-based term was designed to deliver. Therefore, to compute the prior term we simply calculate the region term on the prior image, rather than on the target image.

F p (x, y, C) = |P (x, y) -P C | 2 (x, y) ∈ C |P (x, y) -P Ω\C | 2 (x, y) ∈ C (4)
In this case, λ 1 and λ 2 have been set to 1, since the images used to calculate the prior term force are binary, thus presenting a perfectly homogeneous foreground and background, and it is not necessary to weight one region more heavily.

Implementation

In HybridLS, the contour C evolves according to

dC dt = F tot • N
were F tot is the weighted sum of the three force terms (Equation 1) and N is the normal direction of C. We used the Shi and Karl's Fast-Two-Cycle (FTC) algorithm [START_REF] Shi | A Real-Time Algorithm for the Approximation of Level-Set-Based Curve Evolution[END_REF], a fast LS implementation without the need of solving partial differential equations (PDE). It is a narrow band technique that restricts the calculations of the LS to a much smaller region than the whole grid, and significantly speed up the curve evolution process. This method also separates the evolution process into two different cycles: one cycle for the data dependent term and a second cycle for the smoothness regularization.

Parameter learning using metaheuristics

HybridLS has the ability to learn optimal parameter settings for every specific dataset. Provided a training set of already segmented images of the same class, the parameters are learned using a classic machine learning approach: configurations of parameters are tested on the training data, and the results are compared with the ground truth to assess their quality. In the most basic approach, all combinations of parameters need to be tested, but this exhaustive search is very time consuming, if not even impossible when a large number of parameters are involved. Fortunately, we can overcome this problem by using metaheuristics, since a properly designed metaheuristic has the ability of learning optimal parameter values faster than an exhaustive search.

In this work, we developed a GA to learn the weights of the force terms (w r , w e , w p ) and their corresponding parameters (λ 1 , λ 2 for the region term and γ for the edge term). A solution of the problem, or an individual in GA terms, is a string of real values encoding the parameters values. The quality of a solution s (its fitness) is defined as the average quality of the segmentations obtained using the parameters values in s. In this case, we measured the average Dice coefficient obtained segmenting the images in the training set.

The GA begins by creating a set of random solutions (a population) of fixed size. Then, individuals are selected and variation operators are applied to create a new generation of solutions. The current population is then entirely replaced by new one, except for the best individual that is never discarded (elitism). The individuals are selected using a tournament: k individuals are drawn at random, and the best individual of the group (the winner of the tournament) is selected. The variation operators, responsible for combining and altering solutions, are blend crossover (BLX-α) [START_REF] Eshelman | Real-coded genetic algorithms and interval-schemata[END_REF] and random mutation [START_REF] Bäck | Handbook of Evolutionary Computation[END_REF]. The random mutation operator picks randomly one of the individual parameters and replace it with a random value in the parameter's range, both times using uniform probability. Blend crossover operator is more complex: given two individuals x and y, called "parents", for each position i of the parents' coding, the algorithm computes the value d = |x i -y i | and then randomly generates two values a, b in the interval [min(x i , y i ) -αd, max(x i , y i ) + αd] with uniform probability. The values a and b are assigned to the i-th positions of the two offspring, and α is a positive value controlling the width of the ranges in which the new parameters' values are drawn.

It is important to notice that, when testing combinations of parameter values, not all segmentation steps need all parameters. For instance, the VFC of an image depends only on γ. Having this in mind, and in order to speed up the learning process, we saved in a cache all the information that are shared between different configurations. This is especially important for the prior, which is the most computationally demanding step in the segmentation process by far. The prior do not use any of the parameters in the learning process, therefore only one per image is needed but, since the registration algorithm is non-deterministic, we represented its variability by creating a pool of 30 priors for each image. The priors used in tuning the segmentation parameters were drawn at random from the pool. This approach led to an impressive speedup of the training process. Once the priors and the VFC of each training image has been computed, a single parameter configuration could be tested in less than a second.

Experimental Setup

One of the main aims of this research is to develop a method that, combining the advantages of geometric DMs, metaheuristics and prior shape knowledge, can achieve remarkable results with different medical image modalities and anatomical structures of interest. To accomplish this purpose, three image modalities with completely different characteristics and various structures have been tested. In this section, these datasets will be described, as well as the anatomical structures to be segmented. Then, we will present the different methods included in the comparison, and devote two separate sections to the atlas registration and the tuning of the parameters (given their critical importance in our pipeline). Finally the final results of segmentation will be presented and analyzed.

Datasets

Three kinds of biomedical image modalities were used to verify the global performance of the different methods over different datasets. We focused our interest on microscopy histological images derived using In Situ Hybridization, X-Ray computed tomography, and magnetic resonance imaging.

• In Situ Hybridization-derived images (ISH). 26 microscopy histological images were downloaded from the Allen Brain Atlas (ABA) [START_REF]Allen Reference Atlases[END_REF]. The anatomical structure to segment was the hippocampus, and the ground truth was created manually by an expert in molecular biology: every image was manually segmented 5 times and, for each group of 5 manual segmentations, the consensus image was calculated and used as ground truth. The typical resolution of ABA images is about 15,000 × 7,000 pixels, and the ROIs about 2,500 × 2,000 pixels.

• Magnetic Resonance Imaging (MRI). A set of 17

T 1 -weighted brain MRI were retrieved from a NMR database with their associated manual segmentations [START_REF] Poupon | A database dedicated to anatomo-functional study of human brain connectivity[END_REF]. The deep brain structures to segment were caudate, putamen, globus pallidus, and thalamus. All MR images used in training and test have a resolution of 256 × 256 pixels.

• X-Ray Computed Tomography (CT). A set of 10 CT images were used in the experiments [START_REF] Bova | Image Segmentation Using Extended Topological Active Nets Optimized by Scatter Search[END_REF]. Four of them correspond to a human knee and the other six to human lungs. The gray value of all pixels have been inverted so the bone and the lungs are the darker objects in the image. Knee images have an average size of 410 × 435 pixels, while Lung images have 510 × 350 pixels.

All four datasets, considering lungs and knee as different image sets, were divided in training and test data. The training images were used by HybridLS for the learning of the parameters, while the test images were the ones used in the final experiments to check the performance of the methods.

In ISH, 22 images were used for testing and 4 as a training set. As atlas for the registration, the actual references in the ABA were employed to obtain the shape prior. With respect to MRI, 3 images were used as training set, another 3 were used as atlas, and the remaining 11 as test set. Finally, in relation to CT, one image of every organ was used as training and atlas for the registration, leaving 3 lung and 2 knee images for testing the system.

Methods included in the comparison

In our comparisons we have included both deterministic and non-deterministic methods, as well as classic and very recent proposals. The stress has been focused on DMs, and their hybridization with metaheuristics, but other kinds of approaches have also been taken into account.

• Active Shape Models (and Iterative Otsu Thresholding Method) refined using Random Forests (ASM + RF) [START_REF] Mesejo | Automatic Hippocampus Localization in Histological Images using Differential Evolution-Based Deformable Models[END_REF][START_REF] Mesejo | Automatic Segmentation of Hippocampus in Histological Images of Mouse Brains using Deformable Models and Random Forest[END_REF]. This method, published in 2012, uses a medial-based shape representation in polar coordinates, with the objective of creating simple models that can be managed in an easy and fast manner. Such a parametric model is moved and deformed by a metaheuristic (Differential Evolution (DE) [START_REF] Das | Differential Evolution: A Survey of the State-of-the-Art[END_REF]) according to an intensity-based similarity function between the model and the object itself. After that, Otsu's thresholding method [START_REF] Otsu | A Threshold Selection Method from Gray-Level Histograms[END_REF] is iteratively applied on every region identified by the located control points. Finally, Random Forests [START_REF] Breiman | Random Forests[END_REF] is applied to expand the segmented area to the regions that were not properly localized. This segmentation algorithm has shown very good performance in histological images, but needs a training set of shapes to manually create the parametric template and its possible deformations, as well as a training set of textural patterns for the expansion phase. Due to these restrictions it was only applied to ISH images.

• Soft Thresholding (ST) [START_REF] Aja-Fernandez | Soft thresholding for medical image segmentation[END_REF]. This deterministic method, presented in 2010, is based on relating each pixel in the image to the different regions via a membership function, rather than through hard decisions, and such a membership function is derived from the image histogram. In a first stage, the normalized histogram of the image is calculated and a sum of weighted known distributions is fit to it. Each probability distribution represents the probability for a pixel with a certain value to belong to the corresponding region. This segmentation technique is totally automatic, and the spatial operations performed make the thresholding more robust to noise and artifacts. Having been successfully applied to CT, MRI and ultrasound, it seemed interesting to apply it also to microscopy histological images and compare its performance with other state-of-the-art methods.

• Atlas-based deformable segmentation (DS) [START_REF] Valsecchi | Intensity-based Image Registration using Scatter Search[END_REF]. This method refers to the atlas-based segmentation procedure used in HybridLS to compute the prior (section 3.1). This is actually a stand-alone segmentation method, therefore it is included in the experimental study as a representative of registrationbased segmentation algorithms. Moreover, comparing DS's and HybridLS's results will assess the influence of the prior term on the performance of the second method. During the whole study, the setup and the atlas selection mechanism of DS (section 3.1) are always the same whether the method is used stand-alone or embedded in another segmentation technique.

• Geodesic Active Contours (GAC) [START_REF] Caselles | Geodesic Active Contours[END_REF]. This technique, introduced in 1997, connects classical 'snakes' based on energy minimization and geometric active contours based on the theory of curve evolution. It is based on active contours that evolve in time according to intrinsic geometric measures of the image: the evolving contours naturally split and merge, allowing the simultaneous detection of several objects and both interior and exterior boundaries.

The Partial Differential Equation of the GAC is the following:

u t = α • div(g∇u/|∇u|)|∇u| + β • g|∇u| (5)
where g is a positive and strictly decreasing function, ∇ is the gradient operator computed on image I, div is the divergence operator (that measures the magnitude of a vector field's source or sink at a given point), and α and β are the contour (internal force) and expansion (external force) weights, respectively. This method is equivalent to the minimization of the length of curve C according to a Riemannian metric, and such a metric depends here on the local gradient of the image I.

In this paper, two implementations of GAC have been tested. The first one uses as initial contour the whole image, while the second one, called DSGAC, employs the segmentation obtained using DS to create the initial contour of the geometric DM.

• Chan&Vese Level Set Model (CV) [START_REF] Chan | Active Contours without Edges[END_REF]. This implicit DM was also included in the comparison to check its performance in comparison with the other approaches (see section 3.2.1). Also in this case, like in GAC, two implementations have been tested. The first one uses the whole image as initial contour, and the second one employs the segmentation result obtained by DS as the LS initial contour.

Parameter settings

As HybridLS has an automatic parameter learning phase, it would be unfair to compare it against other methods without some kind of parameter tuning. A manual tuning is time consuming and error-prone, while using the GA to tune all methods could introduce a bias, as the behavior of the GA could vary with each method. In general, we want the competitors to deliver their best performance, regardless of their parameter sensitivity or their ability to be tuned. Therefore, we decided to tune the competitors with an exhaustive search using the test data, rather then the training one. This means the results reported for all methods but HybridLS are actually the best average results they can obtain on these datasets. This gives them a clear advantage over HybridLS, as for the latter the parameters are learned using the training data only.

For CV, GAC, DSGAC and DSCV, all the possible combinations of the values in Table 1 were tested. Also, a pre-processing and a post-processing stages were included to improve the results obtained. The post-processing stage makes a refinement of the results removing the connected components smaller than a certain amount of pixels, while the pre-processing is a median filter to remove salt-andpepper-like noise present in some of the images. Moreover, for DSGAC and DSCV, 10 different initial masks were created using DS and the best one was used in the tuning. The number of iterations for GAC and CV was set to 500 to ensure the process reached convergence. In a few cases, on the ISH dataset, CV failed to converge within the limit due to poor parameters values. This occurred only while producing very low quality, degenerate segmentations, therefore the early stopping did not affect the tuning process.

After tuning these methods, the minimum allowed size in pixels of connected components was set to 75, 200 and 25000 for MRI, CT and ISH, respectively. For ASM+RF, the parameters used (Table 3) were those suggested in the bibliography for the ISH dataset, which has been deeply tested by the authors.

For HybridLS, the parameters settings were learned by the GA using the training data. The size of the population was set to 50 individuals, and the evolution lasted 50 generations. The probability of crossover and mutation was set to 0.7 and 0.1, respectively, and the size of the tournament was 3. The range of λ 1 , λ 2 was restricted to {1, 2, 5} to match the settings used with the other methods.

The final parameters configurations are reported in Table 2. It is interesting to remark how the GA detected a different level of importance for each term across the datasets. For instance, in MRI the edge term is not used (w e = 0) since our machine learning system determines that, for a good segmentation, the region term and prior shape knowledge are enough. When segmenting CT lungs the only term used is the region-based one. In this case, λ 1 and λ 2 were set to 5 and 2, respectively. This means that our final segmentation will have a more uniform foreground region (since the energy contributed by the "variance" in the foreground region has a larger weight), at the expense of allowing more variation in the background.

Experimental results

To evaluate the performance of the segmentation methods, we employed three standard segmentation metrics: the Dice coefficient (DSC), the Jaccard similarity index (JI) and the Hausdorff distance (HD). Both the Dice coefficient and the Jaccard index measure set agreement: a value of 0 indicates no overlap with the ground truth, and a value of 1 indicates perfect agreement. In turn, the Hausdorff distance measures the mutual proximity of two images, calculated as the maximum distance from a point in the ground truth to the closest point in the segmentation.

It is important to remark that ASM+RF, DS, DSCV, DSGAC and HybridLS are non-deterministic, since stochastic methods, like Differential Evolution or Scatter Search, are embedded in these algorithms. It is essential to execute such algorithms several times to estimate and compare their performances. In this case, 20 repetitions per image were run and the mean, median and standard deviation values were calculated over the whole set of results (see Table 5). For instance, in ISH the mean Dice value of DS is 0.876, and represents the average of 440 experiments performed (20 repetitions per image and 22 images).

We also performed a statistical analysis of the results. When comparing two methods, we used Wilcoxon ranksum test [START_REF]Historical Notes on the Wilcoxon Unpaired Two-Sample Test[END_REF], a non-parametric statistical test that checks whether one of two independent samples tends to have larger values than the other. When multiple comparisons were performed, Holm correction [START_REF] Holm | A Simple Sequentially Rejective Multiple Test Procedure[END_REF] was applied to the pvalues to control the family-wise error rate. Note that, in the Lungs and Knee datasets, the number of images is not large enough to allow the comparison of the deterministic methods (ST, CV and GAC), therefore they have been excluded from the test.

In Table 4, some concise information about the running time of each algorithm is provided with an illustrative purpose. The fastest method is ST with MRI, taking only 1 second per image, while the slowest are the different applications of DS to ISH, employing up to 10 minutes to process an image. Nevertheless, several factors affect the accuracy of a comparison in terms of execution time. First, some of the methods have been developed in MATLAB and others in C++. Moreover, the size of the images differs from one image modality to another, as well as some of the pre-and post-processing stages we used. Finally, the nature of the algorithms is completely different, making them hardly comparable.

Analysis

The experimental results are reported in Table 5. Visual examples of two segmentations obtained by the methods on each dataset are provided in Figure 6. For simplicity, our discussion focuses on the results in terms of mean DSC, but note that this choice does not really affect the outcome of the comparison, as there is an almost perfect agreement with the other validation measures we considered.

The performance of the segmentation methods varies greatly across the four datasets. The easiest problem to be solved has been the segmentation of Lungs in CT images, with all methods but GAC and DS scoring higher than 0.95. The most complex task has shown to be the segmentation of deep anatomical structures in brain MRI, where four of the compared methods have obtained an average DSC of 0.2 or less).

The per-dataset results are shown in Figure 5 using boxplots and in Table 6 through the average rankings. Obviously, the performance of every method depends on the nature of the image to be segmented. For instance, techniques based on grey intensity level (such as CV and ST) yielded worse results in image modalities with less contrast and small differences in terms of pixel intensity like MRI.

HybridLS has obtained the best results in all biomedical image datasets. It achieved the best values for the mean DSC and JI metrics, and it was ranked as the best method in every image modality. The Wilcoxon test (Table 6) showed, with really high confidence, that the difference between HybridLS and the other methods is statistically significant in all but one case (DS on MRI). This behavior is also robust, as shown by the low standard deviation values. We can then conclude that our proposal is the best segmentation method in the comparison.

The DS method has been one of the best-performing algorithms, ranking second or third over three datasets. More in general, all methods using the registration-based initialization scored better than those using a standard one. This applies also to CV and GAC: in all but one case, both DSCV and DSGAC ranked better than their counterpart, with a statistically significant difference (Table 7).

Overall, DSGAC delivered an acceptable performance, ranking above average in three datasets out of four. This is remarkable, as the regular GAC ranked constantly in the last three positions, and it can be explained by the high sensitivity of GAC to its initialization.

DSCV ranked around average in all datasets, performing slightly worse, although more consistently, than DSGAC. The plain CV method achieved a bad performance, ranking last or second to last in three datasets. Only on the Lungs dataset, where the grey value is enough to segment the target quite accurately, CV delivered good results.

ST results showed a similar pattern to CV. It performed better than CV, but being ST based on the histogram it showed limited ability to cope with complex scenarios. On the other hand, ST is the fastest method on the group and it has virtually no parameters to be set.

ASM+RF obtained some of the best results with ISH images, being also one of the fastest techniques, but it is fair to underline its ad-hoc nature. It needs a training set of shapes to create the template and its possible deformations, and it also needs a training set of textural patterns for the expansion phase. Also, it is not able to manage topological changes in a natural way, as geometric DMs can do.

Finally, from the values of HD, it is interesting to notice how methods without shape deformation restrictions, like ST, CV and GAC, have a higher (worse) HD with respect to others introducing prior shape knowledge, like ASM+RF, DS and HybridLS.

Discussion and Future Research

It is crucial to highlight the main features of HybridLS:

• it is an accurate and also general segmentation method (it obtains very good results with all the medical image modalities tested, even overcoming well-consolidated techniques);

• its overall standard deviation is the lowest among the different methods compared, therefore we can affirm that the developed approach is consistent and stable in terms of performance;

• it does not need a training set of textures or shapes to segment the object of interest (it needs only one reference image to obtain the shape prior);

• it performs self-adaptation of its own parameters depending on the medical image modality to segment;

• and uses metaheuristics to generate the shape prior and to perform the previously mentioned learning of parameters.

Thanks to the automatic learning of the model parameters, our hybrid proposal is able to perform an effective segmentation with very different medical image modalities, adapting the importance of every term to each image modality and anatomical structure.

The main drawback of HybridLS is that it is not as fast as ST or even ASM+RF. This is obvious since it can be as fast as its components and, evidently, DS is a deformable registration process that can take several minutes in a general purpose computer. More sophisticated implementations, like GPGPU programming, can be tested to speed-up the computations. Finally, the introduction of a textural term could be taken into consideration if the benefits obtained with its use justify it.

Figure 1 :

 1 Figure 1: An example of atlas-based segmentation. The figure shows a slice of a 3D brain MRI and the corresponding deep brain structure segmentation obtained once the atlas is registered to the input image.

Figure 3 :

 3 Figure 3: The schematic view of the interaction among the components of HybridLS.

  (a) input image (b) atlas-based prior (c) vector field convolution (d) region term (e) prior term (f) edge term

Figure 2 :

 2 Figure2: A visualization of the different force terms. In the bottom row, the input image is overlapped with the current contour, which is colored according the force. Green means the force is close to zero, while blue and red colors mark inward and outward forces, respectively. In this example, the region term (d) is correctly moving the contour towards the lungs boundaries, as they define two very homogeneous areas. The prior term (e) is just pulling towards the prior segmentation (b). Finally, the edge term (f) is moving the level set towards the closest edges, regardless whether these belongs to the lungs boundaries or not.

Figure 6 :

 6 Figure 6: Some visual examples of the results obtained. Two images per image modality and structure to segment have been selected: the first two rows correspond to ISH, the next two rows to CT-Knee, and the last four to CT-Lungs and MRI. White represents true positives, red false negatives, and green false positives.

Figure 5 :

 5 Figure 5: Box-plot representing the DSC for all methods.

Table 1 :

 1 Combination of parameters tested for CV, GAC, DSCV and DSGAC.

	Parameter	Values
	α contour weight	{1, 2, 3}
	β expansion weight	{-1, -0.5}
	µ weightLengthTerm	{0.01, 0.1, 0.25, 0.5, 0.75}
	λ1	{ 1, 2, 5}
	λ2	{ 1, 2, 5}
	size median filter	{1, 3, 5, 10}
	minimum size allowed	{1, 50, 75, 100, 200, 5000, 25000}

Table 4 :

 4 Average execution time per method and kind of image. All values are in seconds, and were obtained running the experiments in an Intel Core i5-2410M @ 2.3GHz with 4.00 GB of RAM. Also the programming environment has been included between brackets.

		ASM+RF	ST	CV	GAC	DSCV	DSGAC	DS	HybridLS
		(MATLAB, C++)	(MATLAB)	(MATLAB)	(MATLAB, C++)	(MATLAB, C++)	(MATLAB, C++)	(C++)	(C++)
	ISH	35	39	87	32	582	493	471	545
	Lungs	-	1.7	36	15	384	342	326	331
	Knee	-	2.5	67	16	310	265	245	252
	MRI	-	1	11	1.5	429	407	404	405

Table 5 :

 5 Segmentation Results using 3 different metrics: Dice Similarity Coefficient (DSC), Jaccard Index (JI), and Hausdorff Distance (HD). Values are sorted in descending order using as criterion their average DSC value. The best results for every metric are shown in bold letters.

	Dataset	Method	Dice Coefficient mean median stdev	mean	Jaccard Index median	stdev	Hausdorff Distance mean median stdev
		HybridLS	0.888	0.918	0.079	0.806	0.849	0.109	103.614	70.109	100.115
		ASM+RF	0.885	0.896	0.040	0.797	0.812	0.061	114.906	94.736	52.785
		DS	0.876	0.907	0.078	0.787	0.829	0.108	101.437	75.166	79.779
	ISH	DSGAC ST	0.791 0.728	0.830 0.775	0.143 0.175	0.674 0.597	0.709 0.632	0.172 0.192	215.237 578.876	150.727 665.301	196.908 303.314
		DSCV	0.673	0.764	0.203	0.538	0.618	0.203	263.345	176.706	234.192
		GAC	0.670	0.722	0.181	0.528	0.564	0.192	693.257	707.560	265.589
		CV	0.589	0.723	0.257	0.460	0.567	0.242	839.800	844.773	331.804
		HybridLS	0.868	0.872	0.087	0.777	0.782	0.136	13.690	13.618	1.735
		DSGAC	0.810	0.811	0.142	0.705	0.705	0.204	84.611	84.611	4.040
		DS	0.687	0.685	0.227	0.569	0.563	0.271	45.015	45.308	25.303
	Knee	DSCV	0.528	0.527	0.079	0.363	0.361	0.073	69.642	76.261	16.468
		GAC	0.486	0.486	0.310	0.349	0.349	0.276	187.087	187.087	29.528
		ST	0.398	0.398	0.088	0.250	0.250	0.069	144.864	144.864	36.792
		CV	0.230	0.230	0.072	0.131	0.131	0.046	179.680	179.680	30.499
		HybridLS	0.996	0.997	0.001	0.992	0.994	0.003	2.949	3.606	1.415
		ST	0.979	0.990	0.023	0.960	0.981	0.044	51.550	60.208	42.882
		CV	0.973	0.992	0.034	0.949	0.983	0.063	52.903	60.208	38.592
	Lungs	DSCV	0.966	0.985	0.034	0.935	0.971	0.062	26.512	25.495	9.321
		DSGAC	0.950	0.952	0.027	0.906	0.908	0.049	37.828	29.155	27.197
		DS	0.896	0.897	0.062	0.818	0.814	0.102	39.378	51.478	18.023
		GAC	0.670	0.627	0.251	0.542	0.457	0.309	143.938	137.568	34.430
		HybridLS	0.758	0.780	0.048	0.612	0.639	0.062	7.819	6.708	2.874
		DS	0.752	0.783	0.056	0.606	0.643	0.071	10.838	10.000	3.192
		DSGAC	0.585	0.613	0.087	0.418	0.442	0.084	25.113	25.495	2.414
	MRI	DSCV	0.204	0.213	0.054	0.115	0.119	0.033	76.792	76.322	5.955
		CV	0.155	0.171	0.042	0.084	0.093	0.024	93.727	93.408	4.670
		ST	0.175	0.181	0.053	0.097	0.100	0.032	84.936	85.586	6.289
		GAC	0.124	0.139	0.035	0.066	0.074	0.020	90.856	90.139	5.459

Table 6 :

 6 Average rank achieved by every method per image modality and adjusted p-value of Wilcoxon test comparing each algorithm against HybridLS.

Acknowledgments

Pablo Mesejo and Andrea Valsecchi are funded by the European Commission (Marie Curie ITN MIBISOC, FP7 PEOPLE-ITN-2008, GA n. 238819). The authors want to thank Nicola Bova for his generous and helpful advice on the development of the level set implementation. NMR database is the property of "CEA/I2BM/NeuroSpin" and can be provided on demand to cyril.poupon@cea.fr. Data were acquired with PTK pulse sequences, reconstructed with PTK reconstructor package and postprocessed with Brainvisa/Connectomist software, freely available at http: //brainvisa.info.

Computerized Tomography -Knee 500 iterations 500 iterations 500 iterations 500 iterations

Computerized Tomography -Lungs 500 iterations 500 iterations 500 iterations 500 iterations

In Situ Hybridization-derived images 500 iterations 500 iterations 500 iterations 500 iterations


A Abraham

R Andriatsimandefitra

A Brunelat

J.-F Lalande

V Viet

Triem Tong

GroddDroid: a Gorilla for Triggering Malicious Behaviors

Android malware authors use sophisticated techniques to hide the malicious intent of their applications. They use cryptography or obfuscation techniques to avoid detection during static analysis. They can also avoid detection during a dynamic analysis. Frequently, the malicious execution is postponed as long as the malware is not convinced that it is running in a real smartphone of a real user. However, we believe that dynamic analysis methods give good results when they really monitor the malware execution. In this article 1 , we propose a method to enhance the execution of the malicious code of unknown malware. We especially target malware that have triggering protections, for example branching conditions that wait for an event or expect a specific value for a variable before triggering malicious execution. In these cases, solely executing the malware is far from being sufficient. We propose to force the triggering of the malicious code by combining two contributions. First, we define an algorithm that automatically identifies potentially malicious code. Second, we propose an enhanced monkey called GroddDroid, that stimulates the GUI of an application and forces the execution of some branching conditions if needed. The forcing is used by GroddDroid to push the execution flow towards the previously identified malicious parts of the malware and execute it. The source code for our experiments with GroddDroid is released as free software 2 . We have verified on a malware dataset that we investigated manually that the malicious code is accurately executed by GroddDroid. Additionally, on a large dataset of 100 malware we precisely identify the nature of the suspicious code and we succeed to execute it at 28%.

Introduction

Between 1% [START_REF] Grace | RiskRanker: Scalable and Accurate Zero-day Android Malware Detection[END_REF] and 9% [START_REF] Cheetahmobile | [END_REF] of Android applications are identified as malware. CheetahMobile reports that most of them come from alternative markets where automatic checks and malware sanitization procedures are missing [START_REF] Cheetahmobile | [END_REF]. Most of the time, users are infecting their own smartphone with a repackaged version of a legitimate application containing malicious code. Identifying a potential malware by studying the required permissions becomes difficult, especially because developers have difficulties to use permissions accurately [START_REF] Stevens | Asking for (and about) Permissions Used by Android Apps[END_REF].

To prevent the distribution of malware, Google has developed a service called Bouncer that analyzes statically and dynamically applications submitted on Google Play. Static analysis has strong limitations since malware resorts to a lot of techniques to hide the malicious behavior within legitimate applications. They can obfuscate their code, use reflection or dynamic libraries. Additionally, a lot of interesting information are only available at runtime, for example the content and the recipient of a SMS, the content of a message received by a remote server, etc. Dynamic analysis can bring more information on malware behaviors. Research efforts have to be done on the setup of efficient dynamic analysis platforms as it is not reliable to deploy large scale analysis tools on user's devices.

Dynamic analysis faces several problems. Malware can load their code dynamically [START_REF] Poeplau | Execute this! analyzing unsafe and malicious dynamic code loading in android applications[END_REF], detect a virtual sandboxing of the application [START_REF] Vidas | Evading Android Runtime Analysis via Sandbox Detection[END_REF], use transformation attacks to escape signature based techniques [START_REF] Rastogi | Catch Me If You Can: Evaluating Android Anti-Malware Against Transformation Attacks[END_REF]. Thus, the effectiveness of dynamic analysis for building real time detection tools is an interesting and active debate. Dynamic analysis tools are only useful if the malware is executed during the analysis. If the environment is virtualized, if the network is not setup, or if some APIs are missing, some simple checks may lead a malware to prevent the run of its code. We think that this sub-problem should be addressed, and is a first important step for dynamic detection solutions.

In this article, we propose a methodology and a tool called GroddDroid to automatically trigger and execute sus-picious parts of the code of an application: our goal is to take as input an application, run it on a real smartphone and modify as few as possible the control flow of the application in order to force the execution of the suspicious part of the code. To achieve such a goal, we lead a two step approach. First, we identify the suspicious parts of the bytecode and compute a score (indicator of risk) for each function of the malware. Second, we introduce a new GUI stimulator, called GroddDroid, which runs the application by clicking on all possible detected buttons. Finally, we identify the remaining parts of the malware that has not been executed and we force the required control flow statements to push the flow to the unexecuted parts previously scored.

Our experimental results show that our GroddDroid executor has better code coverage than the Monkey [START_REF] Google | UI/Application Exerciser Monkey[END_REF] and A3E [START_REF] Azim | Targeted and Depth-first Exploration for Systematic Testing of Android Apps[END_REF]. Combined with the control flow forcing method, the triggering of malicious code increases and we measured this improvement on a dataset of malware for which we have manually identified the malicious parts. On a larger dataset we also show that GroddDroid succeeds in executing the suspicious parts previously detected.

This article is structured as follows. Section 2 describes the problem of executing malware and presents a literature review. Section 3 gives a comprehensive overview of our solution. Three sections describe the different features of GroddDroid: Section 4 explains how the malicious code is targeted, Section 5 describes how is automatized the interaction with the GUI of the applications and finally Section 6 details how GroddDroid can force branches during the execution in order to execute the previously detected suspicious code. Section 7 presents our experimental results based on two datasets, a small one and a large one, and finally Section 8 concludes the article.

State of the art

As the production of Android malware is increasing, writing malware is becoming a regular job: Allix et al. explain that, most of malicious codes are copy paste of online tutorials or variation of the same original malicious code [START_REF] Allix | A Forensic Analysis of Android Malware -How is Malware Written and How it Could Be Detected[END_REF]. Thus, families of malware can be rebuilt [START_REF] Faruki | Android Security: A Survey of Issues, Malware Penetration and Defenses[END_REF] and we can measure the improvements of the sophistication of each family [START_REF] Apvrille | The evolution of mobile malware[END_REF].

Two main approaches can be considered to inspect the behavior of malware: static approaches that analyze the available material of the malware as its bytecode, its resources, and dynamic approaches that run the malware and monitors its behavior. As reported in [START_REF] Neuner | Enter Sandbox: Android Sandbox Comparison[END_REF], different monitoring techniques can be used. Tainting techniques follows the information in the studied application [START_REF] Arzt | Flow-Droid: Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps[END_REF][START_REF] Enck | TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones[END_REF]. Virtual machine events crafting, system calls monitoring and method tracing can be implemented in the Dalvik virtual machine or at kernel level [START_REF] Blasing | An Android Application Sandbox system for suspicious software detection[END_REF].

Bläsing et al. propose an hybrid approach, with a first static step and a second one that is dynamic and run in an emulator [START_REF] Blasing | An Android Application Sandbox system for suspicious software detection[END_REF]. The first step statically analyzes the malware to extract relevant patterns such as JNI calls, binary executors, usage of reflection, etc. Then, the second step runs a dynamic analysis and monitors low levels system calls. Nevertheless, the two steps does not cooperate and the benefits of the static analysis is not reused for the dynamic step. We believe that dynamic approaches are promising approaches as long as they really observe the malicious behavior of a malware. However, malware authors are full of resources to evade dynamic approaches simply in delaying their malicious execution.

Well known analysis platforms like Andrubis [START_REF] Lindorfer | ANDRUBIS-1,000,000 Apps Later: A View on Current Android Malware Behaviors[END_REF] or SmartDroid [START_REF] Zheng | Smartdroid: An automatic system for revealing uibased trigger conditions in android applications[END_REF] do not address this problem. They trigger all possible activities and generates possible interesting events. But if the malicious code is protected, for instance waiting a special event, the malicious code will never been executed. Thus, running automatically an ordinary application is a difficult challenge. As the Monkey stimulator [START_REF] Google | UI/Application Exerciser Monkey[END_REF] gives insufficient results, researchers have also contributed to automate the interactions with the GUI. In [START_REF] Choudhary | Automated Test Input Generation for Android: Are We There Yet[END_REF], Choudhary et al. give an overview of the current input generators for Android. Random strategies can choose graphical elements or choose system events in order to stress the application. For example, DynoDroid [START_REF] Machiry | Dynodroid: an input generation system for Android apps[END_REF] repeats a loop "observeselect-execute" and implements different strategies for the selection phase. Model-based exploration strategies consider each activity as a state and each event is a possible transition. For example, AndroidRipper [START_REF] Amalfitano | Using GUI ripping for automated testing of Android applications[END_REF] discovers new states and generates the possible transitions dynamically during the execution.

Additionally, sophisticated techniques use combinations of methods to help the dynamic exploration, e.g. using the exploration strategy of A3E's tool of Azim et al. [START_REF] Azim | Targeted and Depth-first Exploration for Systematic Testing of Android Apps[END_REF]. Their tool calls the activities that can be triggered by Intents if they are detected in the manifest of the application. This is a simple combination of static analysis and dynamic execution that intends to increase the covering of code.

Finally, since malware developers frequently reuse the same benign application to embed different malicious codes, the authors proposes PuppetDroid which is a solution that reuses previous recorded interactions if the repackaged application's GUI looks similar [START_REF] Gianazza | PuppetDroid: A User-Centric UI Exerciser for Automatic Dynamic Analysis of Similar Android Applications[END_REF]. This example shows that the code coverage of the application is not the best way to study malware.

In this article, we do not care about covering the benign part of the code. Thus, we base our proposal on the idea that if we identify the parts of the code that are possibly malicious, and if a normal execution does not trigger this part of the code, then we should force the flow of execution in order to reach this part during subsequent executions. We show how a prior static analysis helps dynamic analysis in

public static int syracuse(int) { int $i0, $i1; $i0 := @parameter0: int; label1: if $i0 != 1 goto label2; return $i0; label2: $i1 = $i0 if $i1 != 0 goto label3; $i0 = $i0 / 2; goto label1; label3: $i1 = $i0 * 3; $i0 = $i1 + 1; goto label1; } Listing 1: Jimple public static int syracuse(int n) { while (n != 1) { if (n n /= 2; else n = n * 3 + 1; } return n; }
Listing 2: Original Java code increasing its accuracy. The contribution of our article is precisely a static analysis that identifies the bytecode that seems dangerous followed by an automatic execution driven by the first analysis. In the next sections, after giving an overview of our solution, we depict all the components that achieve such a goal.

Overview

Figure 1 gives an overview of our proposal. Our approach can be divided into three different steps. First, we instrument the suspected application to observe the behavior of the application under analysis and get a reference execution. This instrumentation enables to learn which branches of the execution are taken during a run (see Control Flow Tracer on Figure 1). Thus, the GroddDroid runner executes the new APK on a smartphone in order to get the reference execution.

The second step consists in identifying the possible malicious code inside the malware using a static analysis of its bytecode (Malicious Code Targeting).

During the third step, GroddDroid uses the execution log of the reference execution to determine which control flow has to be forced to reach the parts of the code identified as malicious. A new APK is produced where the control flow is modified accordingly. The GroddDroid runner executes the new APK and new logs are generated. This step can be repeated for processing all the malicious parts of the identified code.

In the following, Section 4 describes the heuristic that identifies the potential malicious code, Section 5 explains how the reference execution is automated and Section 6 presents how the control flow is forced.

Automatic identification of malicious code

Android applications are packaged and distributed as APK files. These files are archives that do not contain the original Java code but only the pre-compiled Dalvik bytecode and the resources used by the application. In this article we propose a heuristic for targeting directly suspicious bytecode.

Handling application's bytecode

We extract the bytecode by using the Soot framework [START_REF] Arzt | Instrumenting Android and Java Applications as Easy as abc[END_REF] that is able to represent the Java bytecode as several intermediate representations. The main representation is based on the Jimple language, that has the same semantic as the Java language but with fewer instructions (only 15). This reduced set of instructions makes Jimple a practical language for static analysis and optimizations. Listing 1 (resp. 2) shows an example of the Jimple (resp. Java) representation of a method syracuse. The type is still available and control flow constructs are similar: the while loop is simplified with a conditional jump and a backward jump.

With this Jimple representation, Soot allows to programmatically manipulate the application code: each instruction is wrapped into an object that extends a Unit object. In the example of Listing 1, an instruction such as $i1 = $i0 % 2; is represented by an AssignStmt object (for assignment statement), a subclass of Unit, from which some values can be accessed, like the target of the assignment ($i1) and the RemExpr (for remainder expression) of the assigned operation. The control flow of a program can also be analyzed through the conditional and unconditional jump instructions IfStmt and GotoStmt.

In order to target suspicious code, we propose to search some particular types that are more frequently encountered in malware. For extracting those types, we use Soot's ability to give the types used in each instruction of the program.

Suspicious code targeting

Aafer et al. showed that some Java methods of the Android API are noticeably more frequently used in malware code than in benign applications code [START_REF] Aafer | DroidAPIMiner: Mining API-Level Features for Robust Malware Detection in Android[END_REF]. The difference can go from 20% to 50% of additional usage in the case of some sensible API calls such as getSubscriberId. In the following, we briefly summarize the API calls that are the most impacted by this difference and that will be the core of our scoring function (see [START_REF] Aafer | DroidAPIMiner: Mining API-Level Features for Robust Malware Detection in Android[END_REF] for full statistics). android.telephony.TelephonyManager: getSubscriberId and getDeviceId give a unique identifier of the phone. getLine1Number gives the phone number associated with the SIM card. android.app.Service: while services are perfectly common in benign applications, some overridden methods like onCreate frequently contain malicious code. android.context.pm.PackageManager: this component allows listing of installed applications and their installation. android.telephony.SmsManager: this class contains sendTextMessage, that allows to send send a SMS. java.lang.{Runtime,Process}: these standard components of Java allow the application to execute native programs (exec), monitor their output (getOutputStream) and their shutdown (waitFor).

We propose to compute a risk score for each method in the bytecode: we compute the sum of the score associated to each Unit of the method using the scoring constants of Table 1. This table defines a score value for each suspicious class following on the observations of Aafer et al. [START_REF] Aafer | DroidAPIMiner: Mining API-Level Features for Robust Malware Detection in Android[END_REF]. Our heuristic is that malicious code has a higher probability to be the code with the highest score. We give an example of scoring result in Table 2 for a sample of the SaveMe3 malware family. After inspecting manually the results, it appears that the heuristic successfully targets the malicious methods of this malware if we exclude the reflection class. Indeed, this class is used in many parts of application and the scoring was less accurate if reflection was considered, even with a low score.

Note that the score is high for two methods that have only two suspicious calls in it (TelephonyManager). On the contrary, the uploadFile method has 12 calls using HttpURLConnection. Of course, false positive targeting may happen, i.e. benign code targeted instead of the malicious code that is elsewhere in the application. Nevertheless, as shown in Section 7.1, our experimental results and manual checks show that the targeting works well.

Stimulating the graphical user interface

As discussed in the state of the art, many tools have covered the problem of stimulating the graphical interface in order to have a good coverage of an application. Unfortunately, most of the open source software that are cited in [START_REF] Choudhary | Automated Test Input Generation for Android: Are We There Yet[END_REF] are no longer supported. Thus, it becomes technically difficult to use the previous contributions in order to execute modern malware that use new versions of Android's APIs. For these reasons, we have chosen to recode a GUI runner, called the GroddDroid runner and to keep the Monkey [START_REF] Google | UI/Application Exerciser Monkey[END_REF] as a point of comparison.

Run by a monkey

The Monkey hits randomly the graphical interface and should be stopped arbitrarily because there is not guarantee that all possible activities have been visited.

The Monkey is often combined with the generation of events like SMS or phone calls and by starting all possible activities and services. Using such techniques [START_REF] Lindorfer | ANDRUBIS-1,000,000 Apps Later: A View on Current Android Malware Behaviors[END_REF] helps the Monkey but cannot achieve good results as we show at the end of the section.

Run by the Gorilla GroddDroid

The GroddDroid runner is based on uiautomator 4 which is a python wrapper to the Google API for testing purpose. GroddDroid pushes the malware on the smartphone and launches it main activity. For each displayed activity, GroddDroid collects the graphical elements that may trigger additional code. For now, we only collect Button objects as our first objective is to trigger the maximum number of activities. We could also manipulate forms, radio buttons, etc. If clicking on the button leads to a new activity, GroddDroid analyses it and repeat the same operation as before. Else, it triggers the next element of the activity or gets back to the previous activity. Of course, GroddDroid detects: dead-end activities where nothing new can be activated: GroddDroid generates the event "Go back button" to return to the previous activity; crashes: the application should be started again and GroddDroid should return to the activity where it crashed: the graphical element that triggered the crash is blacklisted; loops: the current activity has already been explored and GroddDroid should backtrack.

Code coverage comparison

Figure 2 studies the code coverage results of Grodd-Droid, compared to the Monkey [START_REF] Google | UI/Application Exerciser Monkey[END_REF] and A3E [START_REF] Azim | Targeted and Depth-first Exploration for Systematic Testing of Android Apps[END_REF]. For this experiment, we used a large dataset of 100 malware samples, as described later in Section 7.1. For each bar of the graph, we compute the number of applications that have the same coverage ratio. On the top graph, we consider that a method has been covered if the runners enters the method. On the bottom graph, we consider that a branch is covered if the execution flow executes the first instruction of the branch.

For the applications that have a low coverage (less than 15%), GroddDroid and Monkey have similar results. This can be explained by the fact that some malware samples crash just after being started: we observed 23 crashes for our dataset of 100 malware. A3E has surprisingly lower performances than the two others. We believe that, because A3E has been released several years ago, the tool cannot handle correctly more recent versions of Android applications. Thus, we want to emphasize that we believe that better results could be obtained with A3E if the source code was actualized. For coverages greater than 20%, Grodd-Droid is slightly better than Monkey.

Of course, GroddDroid cannot go above 80%: it is well known that executing 100% of the code is extremely difficult as it would require generating all possible inputs and to be sure that no dead code is present. We give more precise results in Section 7.

Forcing malicious code to execute

In this section, we present the ability of GroddDroid to force the conditional branches that have been identified as an execution path leading to the instructions targeted by the algorithm of Section 4. To identify how the control flow should be modified, we build our analysis on a reference execution. First, we compute an execution path from an execution point belonging to the reference execution and leading to the targeted suspicious code. Second, we modify the application bytecode in order to force this new path.

Control-Flow Tracer

We use Soot to instrument the application bytecode and add tracing information that allows us to know precisely which methods and conditional branches have been explored by the GroddDroid runner. We use the Log class of the Android API where the static method Log.i prints informations in a system log that is readable in real-time. The Control-Flow Tracer inserts calls to the Log.i method with unique identifiers, called tags, at the beginning of each method and conditional branch of the application. In the case of large applications, this means that we have to add thousands of these calls, but experiments have shown that it can be reliably done on every tested application. GroddDroid runner executes the application once these calls are inserted in the bytecode. This execution forms the reference execution. The printed tags are collected and stored in the Log Collector (cf. Figure 1). Thus, Grodd-Droid obtains the precise list of branches that have been executed and not executed.

In the following, we explain how we compute an execution path that reaches these parts of the bytecode. We suppose that we want to force a particular targeted method, e.g. the most scored., and we show how we modify the reference execution to force the execution of the targeted method.

Determining an execution path

Our algorithm that determines an execution path to a targeted method is based on the control flow graph of the application. We use control flow graphs (CFG) computed from the bytecode: in these graphs, nodes are instructions of a method and the directed edges between nodes represent the possible succession of instructions. It is relatively easy to compute the control flow graph of each method appearing in the bytecode. Unfortunately, the computation of the control flow graph of the whole application is trickier.

We take as input the CFG of all methods. These graphs have one entry point and possibly several output points. Any point of a CFG C 1 can be connected to an entry point of another CFG C 2 if there exists an inter-procedural flow from C 1 to C 2 , e.g. if a node of C 1 is an instruction that invokes the method whose CFG is C 2 . In addition to direct invocations, there are also method calls that indirectly connect two CFGs. These method calls are specific to Android and are related to the creation of application components such as activities and services. For example, to display a new activity, developers must not instantiate an activity object themselves, but rather call the startActivity method of the Android API, with an Intent object as argument. The system reacts to this API call by instantiating a new activity object and calling its method onCreate. As Grace et al. [START_REF] Grace | RiskRanker: Scalable and Accurate Zero-day Android Malware Detection[END_REF] reported, even though developers do not see explicitly the calls to onCreate, these system actions are well-defined in the documentation. We exploit this knowledge of the well-defined semantic of these API calls to determine the implicit flows for the Android-specific behavior. Thus, we created a control flow graph for the whole application (called ACFG) from the union of CFGs of methods. We give an example of reconstruction of an implicit flow in Figure 3. In an application com.app, the main activity starts a service. The call $r1.startService($r2) calls a method of $r1 which is a reference on this. Thus, we cannot see the direct link to the method onCreate() of MyService as it is called later by the system. The system also calls, when the service is created, the method onStartCommand where the service runs the functional code e.g. in this example, the malicious code that sends SMS. Thus, we analyze such special invocations and we create the two dotted lines in the ACFG graph to reflect these dependencies.

Once we have computed the ACFG, we can reconstruct the shortest execution path, from a targeted instruction, back to an entry point of the application, or to a method that was executed during the reference execution. This particular execution path becomes our targeted execution path.

Forcing branches

We propose here to modify the bytecode of the application to force the execution of our targeted execution path. To achieve the forcing, we first collect the tags of conditional jumps in the targeted execution path. Then, we replace each conditional jump that may divert the execution from the targeted execution with an unconditional jump to force the desired branches.

For example, Listing 3 shows a protection code that determines if the execution takes place on an emulator, and starts doing something suspicious otherwise. During a first execution on a emulator, only the branch 1 would be explored. Listing 4 shows the same sample as Jimple. To force the other branch of the conditional jump, we replace it with an unconditional jump, pointing to the first Unit of the branch 2, as shown by Listing 5. algorithm was able to point out the code identified as malicious by the manual analysis. Table 3 details these first results. This first analysis is promising: except one analysis that has crashed, and one analysis (MobiDash) that ranked first a legitimate method but found other methods with secondary scores containing malicious code, the highest ranked methods correspond to the malicious behavior of malware.

We have also evaluated the results provided by the targeting algorithm on a larger dataset. This second dataset has not been as much studied as the previous used dataset but it contains a higher diversity of malicious codes. This second dataset contains one hundred malware samples obtained from AndroTotal. We evaluate how many methods are scored by the targeting algorithm and computes the distribution of the score value on this larger dataset. Results are represented graphically, for each malware numbered from 1 to 100 on the x axis, in Figure 4. For each malware we draw a square when a method is scored by the heuristic. The higher the score is, the darker the associated color is. This second experiment shows that the heuristic has computed a score greater than 0 for 83 malware over 100. Moreover, a malware has, on average, 1410 methods and 12.34 methods with a score greater than 0. In other words, less than one percent of bytecode methods are considered as potentially malicious by our targeting algorithm. Furthermore, 35.82% of the methods that are scored have a score higher than 25 which is shown by the light gray squares on Figure 4. Only 15 malware present high scored methods (greater than 150). This second experiment allows us to conclude that our targeting algorithm identifies only few methods in the malware code which reduces the scope of further analysis.

Lastly Figure 6 depicts the genome of the second dataset, as seen by our heuristic. Many malware use telephony calls (IMEI, etc.) and also manipulate SMS. The use of the network is of course a common usage and cryptographic primitives are used in 27 cases.

Experimenting GroddDroid forcing

To conclude, we have forced the execution of the most scored method for each malware appearing on the two datasets. Our experiments have been done on a Nexus 5 smartphone under Android 4.4, connected to a Quad core PC with 4GB of RAM. Before executing each malware, we reinstall a fresh operating system in order to delete any modifications that the previous malware would have done. On the large dataset, we obtain a coverage of 16.31% of the methods (10.07% of all branches). When the highest scored method is not executed, GroddDroid runs a second run and forces the required branches. We obtain an extra +0.19% of covering for methods (+0.41% for branches). As expected, the increase is greater for branches as GroddDroid forces control flow conditions. These results are better than the coverages obtained with the Monkey (14.99% for methods, 9.35% for branches) or with A3E (1.46% for methods, 0.49% for branches). Figures 5 and7 show the method and branch covering ratio of GroddDroid (green) for the 100 malware, numbered on the x axis from 1 to 100. The extra bar on the top (in black) represents the additional coverage obtained by GroddDroid when it forces branches.

If we just consider the suspicious methods that have been identified by the heuristic of Section 4, then the cov-ering of these methods goes up to 24% without any forcing. If GroddDroid forces branches, the covering of the suspicious methods obtains an extra value of +4%. On the other hand, Monkey executes 20% of the targeted methods. Thus, in total, GroddDroid succeeds in executing 28% of the suspicious methods with an additional +8% compared to Monkey. Note that this additional performance result of +8% is reduced by the fact that 23 malware crash during the first seconds of execution. Naturally, for these ones, GroddDroid will never be able to reach the targeted method, similarly to Monkey or A3E. For a few malware samples, GroddDroid does not succeed in launching the application. This is because the malware has no main activity and is only triggered with a system event or should be started as a service. We need to add this feature for GroddDroid in future works, in order to launch the required services or intents.

Conclusion

We have presented GroddDroid, a framework dedicated to the discovery and the automatic execution of malicious codes driven by static analysis of the application bytecode. The originality of GroddDroid is its ability to force branches in order to reach the suspicious code despite of the malware developer's countermeasures that protect its triggering.

Figure 1 :

 1 Figure 1: Overview of the GroddDroid framework

Figure 2 :

 2 Figure 2: Number of malware with same code coverage

$Figure 3 :

 3 Figure 3: Example of ACFG reconstruction for an activity starting a service

Figure 4 :Figure 6 :

 46 Figure 4: Scoring of the detected suspicious methods for the large dataset Figure 5: Method coverage for the large dataset

Figure 7 :

 7 Figure6: Genome of the large dataset with the categories of Table1Figure7: Branch coverage for the large dataset

Table 1 :

 1 Proposed risk scores by class categories

	Category	Associated classes	Score
	SMS	android.telephony.SmsManager	50
	Telephony	android.telephony.TelephonyManager	20
	Binary	java.lang.Runtime	10
		java.lang.Process
		java.lang.System
	Dynamic	dalvik.system.BaseDexClassLoader	10
		dalvik.system.PathClassLoader
		dalvik.system.DexClassLoader
		dalvik.system.DexFile
	Reflection	java.lang.reflect.*	3
	Crypto	javax.crypto.*	3
		java.security.spec.*
	Network	java.net.Socket	3
		java.net.ServerSocket
		java.net.HttpURLConnection
		java.net.JarURLConnection

Table 2 :

 2 Scoring result of the SaveMe malware

	Method			Nb	Score
				Units
	com.savemebeta.GTSTSR: void CHECK()		2	100
	com.savemebeta.SCHKMS: void fetchContacts()	2	100
	com.savemebeta.Scan: int uploadFile(java.lang.String)	12	36
	com.savemebeta.Analyse:	void	onCre-	4	32
	ate(android.os.Bundle)
	com.savemebeta.CHECKUPD: void onCreate()		4	32
	com.savemebeta.CO: void onCreate()			2	16

Table 3 :

 3 Scoring results on the kharon dataset

	Malware	Highest	Successful	Most scored method
		ranked	Targeting
		method
	BadNews	80	ok	gathers user information
				(phone number, IMEI, ...)
	Cajino	200	ok	sends SMS with parameters
				from a C&C server
	DroidKungFu	50	ok	starts a binary containing the
				exploit udev
	MobiDash	147	wrong	gathers user information for
				legitimate use
	SaveMe	100	ok	sends SMS with parameters
				from a C&C server
	SimpleLocker	-	crash	-
	WipeLocker	150	ok	sends SMS

http://www.infosecurity-magazine.com/news/ socialpath-malware-backs-up-to-cc

https://github.com/xiaocong/uiautomator

http://contagiominidump.blogspot.fr/

Experimental results on a well studied set of malware samples showed that the targeting phase is accurate. For a dataset of 100 malware, GroddDroid succeeds in executing 16.31% of the methods on average. Using its ability to force branches, GroddDroid targets the suspicious methods and additionally succeeds in executing +0.19% of all methods. Thus, for the methods that are scored as the most suspicious, GroddDroid obtains an executing ratio of 28%.

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.

2 Sources available at http://kharon.gforge.inria.fr

Experiments

Experimenting the targeting algorithm

To evaluate the soundness of the targeting algorithm presented in section 4, we have used a small collection of seven malware namely the Kharon15 dataset. Every malware belonging to the dataset has been manually reversed in order to be able to locate and understand its malicious code. More precisely, malware in this dataset have been picked from the Genome Project [START_REF] Zhou | Dissecting Android Malware: Characterization and Evolution[END_REF] and Contagio mobile 5 and are samples of BadNews (2013), a remote administration tool [START_REF] Petsas | Rage Against the Virtual Machine: Hindering Dynamic Analysis of Android Malware Thanasis[END_REF]; Cajino (2015), a spyware; DroidKungFu (2011), a remote administration tool [START_REF] Zhou | Dissecting Android Malware: Characterization and Evolution[END_REF]; MobiDash (2014), an agressive adware; SaveMe (2015), a spyware; SimpleLocker (2014), a ransomware; WipeLocker (2014), a data eraser.

We have run the targeting algorithm presented in Section 4.1 on these malware and we wanted to know if our