Manel Jerbi
email: manel.jerbi@gmail.com

Zaineb Chelly Dagdia
email: zaineb.chelly-dagdia@uvsq.fr

Slim Bechikh
email: slim.bechikh@fsegn.rnu.tn

Lamjed Ben Said
email: lamjed.bensaid@isg.rnu.tn

Android Malware Detection as a Bi-level Problem

Keywords: Android malware detection, Bi-level optimization, Detection rules generation, Artificial malicious patterns, Evolutionary algorithms

Malware detection is still a very challenging topic in the cybersecurity field. This is mainly due to the use of obfuscation techniques. To solve this issue, researchers proposed to extract frequent API (Application Programming Interface) call sequences and then use them as behavior indicators. Several methods aiming at generating malware detection rules have been proposed with the goal to come up with a set of rules that is able to accurately detect malicious code patterns. However, the rules generation process heavily depends on the training database content which will affect the detection rate of the model when confronted to new variants of malicious patterns. In order to assess a rule's detection accuracy, we need to execute the rule on the whole malware database which makes the detection rule quality evaluation very sensitive to the database content. To solve this issue, we suggest in this paper to consider the detection rules generation process as a BLOP (Bi-Level Optimization Problem), where a lower-level optimization task is embedded within the upper-level one. The goal of the upper-level is to generate a set of detection rules in the form of: trees of combined patterns. Those rules are able to detect not only the real patterns from the base of examples but also the artificial patterns generated by the lower-level. The lower-level aims to generate a set of artificial malicious patterns that escape the rules of the upper-level. An efficient co-evolutionary algorithm is adopted as a search engine to ensure optimization at both levels. Such an automated competition between the two levels makes our new method BMD (Bilevel Malware Detection) able to produce effective detection rules that are capable of detecting new predictable malicious behaviors in addition to existing ones. Based on the statistical analysis of the experimental results, our BMD method has shown its merits when compared to several relevant state-of-the-art malware detection techniques on different Android malware datasets.

Introduction

Malware, or malicious software, is any program or file that is harmful to a computer system. These malicious programs can perform a variety of functions including stealing, encrypting, deleting sensitive data, altering or hijacking core computing functions and even monitoring the users' computer activities without their permission 4 . The use of packers and obfuscation techniques have further empowered the malware coders to redevelop malware variants. This requires the use of effective techniques to detect malware. Indeed, several malware detection mеthods have been proposed in literature and these can be classified as static, dynamic and hybrid approaches; based on how the code is analyzed. While the static approaches try to identify the malicious code without any execution, the dynamic approaches analyse the code during runtime. Hybrid approaches use static and dynamic features as they combine both static and dynamic approaches. Most of the existing approaches in literature derive from the static analysis and this is due to the limitations in power consumption of the majority of mobile devices. However, the static approaches are inefficient against some obfuscation techniques and new attacks. Also, hybrid approaches may have limitations related to both static and dynamic aspects. Therefore, in recent years, researchers have focused on improving the detection techniques in order to be effective not only against known attacks but also against unknown attacks relying on several research fields and areas. Among these are approaches which create new malware and variants of known malware using mainly Evolutionary Algorithms (EA) which enable them to mimic mobile malware evolution [START_REF] Tong | A hybrid approach of mobile malware detection in android[END_REF] [26] [START_REF] Ping | Android malware detection with contrasting permission patterns[END_REF] [11] [START_REF] De Los Santos | Android malware pattern recognition for fraud detection and attribution: A case study[END_REF] [START_REF] Kapare | Can a good offense be a good defense? vulnerability testing of anomaly detectors through an artificial arms race[END_REF]. Despite the good performance of these methods, in these research papers, the weaknesses of the proposed detection tools were indeed highlighted when it comes to creating new attacks. The need for new detection techniques which should be more suited to mobile devices was also emphasized. Additionally, it is important to mention that in literature, most of the approaches that create new attacks are either not fully automated or are only proposed for a specific attack type.

In this paper, we propose a new effective and robust malware detection method named "Bi-level Malware Detection" (BMD). BMD improves its detection rate thanks to the evaluation of each detection rule based on the generation of more evasive artificial malware patterns and in recognizing new variants of existing and even unseen malware patterns. Let us precise that the generation of artificial malware behaviors can be considered as a great alternative to face one of the most inconvenient problems to researchers in different fields which is the problem of data availability. In fact, in order to assess a given method, benchmarks with limited size are available. To face such shortcoming, we propose to generate artificial malicious patterns that come to enrich the used base of examples. Also, let us mention that in our previous work [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF], a dynamic detection method, named Artificial Malware-based Detection (AMD), is proposed to solve the obfuscation issue. AMD makes use of not only extracted malware patterns (i.e., extracted frequent API call sequences also called behaviors) but also artificially generated ones. The artificial malware patterns are generated using a Genetic Algorithm (GA). The latter evolves a population of АPI call sequences with the aim to find new malware behaviors following a set of well-defined evolution rules. The artificial fraudulent behaviors are subsequently inserted into the base of examples in order to enrich it with unseen malware patterns. In AMD, an executable is classified as malware or benignware based on its similarity to the benign patterns, to the real available malicious patterns, and to the artificially generated ones. More precisely, when AMD receives a new executable program P for analysis, it first extracts its API call sequences and then computes the support of all these sequences. Afterwards, two metrics are calculated: [START_REF] Ab Razak | Bioinspired for features optimization and malware detection[END_REF] the malicious credence value of all malicious patterns CM(P) and ( 2) the benign credence value of all benign patterns CB(P). If the former is strictly greater than the latter, then P is classified as malicious; otherwise, it is judged to be benign. Eventually, if P is labeled as malicious, it will be executed on a sandbox system and then analyzed in a dynamic way. Regarding the artificial patterns, these are generated based on the bases of examples of malicious and benign patterns using an EA.

It seems that it is of primordial importance to mention that our previously proposed method AMD presents some deficiencies that occur in three main aspects:

1. AMD uses a static detection rule that is defined in an apriori manner based on similarity measures to benign and malware patterns. 2. The detection rule is prespecified independently of the generated malware patterns; and thus the rule definition and the classification tasks are done separately without any interaction. 3. In AMD, the artificial malware patterns are generated in a global ad-hoc manner based on their similarities to real malware and benign patterns from the bases of examples, which may increase the number of false positives, as some generated artificial patterns could be benign.

To overcome the limitations of AMD, BMD is proposed in this paper. In fact, based on Figure 1, unlike AMD in which the classification of a new app relies on a pattern matching process where two similarity metrics are used to determine its nature, our BMD approach relies on the use of detection rules. An app is classified based on the nature of its extracted patterns. Indeed, each gathered pattern is analyzed using each of the BMD rules that are generated using an evolutionary optimization process. If one of these rules returns true, the pattern (and hence the app) is classified as malicious.

Besides, to prevent the detection process from depending, heavily, on the base of examples, AMD [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF] diversifies the base of examples with new artificial malicious patterns using a GA [START_REF] Davis | Handbook of genetic algorithms[END_REF]. The mаlicious pаtterns base remаins independent from the mаlwаre detection tаsk. Similаrly to AMD, BMD uses аrtificiаl pаtterns, but its mаin distinction аnd originаlity rely on the modeling of the mаlwаre detection tаsk аs а bi-level optimizаtion process. In BMD, the upper-level generаtes а set of detection rules, eаch encoded аs а tree of combined pаtterns Fig. 1: Main differences between BMD and AMD [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF].

(eаch defined аs а set of frequent API cаll sequences), where the quаlity optimizаtion of eаch one of them consists in mаximizing the coverаge of not only the pаtterns extrаcted from the bаse of exаmples but аlso the аrtificiаl mаlicious ones generаted by the lower-level. In this study, the mаlwаre detection tаsk is frаmed аs а bi-level optimizаtion problem in which the upper-level role is to design а set of effective mаlwаre detection rules, while the lower-level one is to generаte а set of chаllenging аrtificiаl mаlwаre pаtterns for eаch rule. In this wаy, in our bi-level аpproаch, the upper populаtion аnd the lower one аre not co-evolved in pаrаllel (without hierаrchy), which аvoids the issue thаt one populаtion converges before the other. Moreover, in such formulаtion, both populаtions depend on eаch other. Finаlly, аnother distinction of our BMD аpproаch in compаrison to AMD [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF] corresponds to the hierаrchicаl quаlity evаluаtion аnd optimizаtion of eаch upper-level detection rule using not only mаlwаre pаtterns from the bаse of exаmples but аlso аrtificiаl ones designed by the lower-level seаrch. Such hierаrchicаl process creаtes а competition between both levels' populаtions аnd thereby аllows optimizing both rules аnd аrtificiаl pаtterns. This competition mаy significаntly reduce the number of fаlse positives, which is not the cаse of АMD.

To sum up, the BMD evolutionаry process is composed of а number of generаtions eаch ensuring а single competition between eаch generаted upper-level detection rule аnd its relаted lower-level аrtificiаl mаlicious pаtterns. In this wаy, а sequence of competition rounds аre performed over the seаrch process, which аllows designing аt the sаme time а set of effective rules with mаximized detection rаtes аnd а set of optimized аrtificiаl pаtterns with mаximized evаsion rаtes with respect to their corresponding rule. These rounds strengthen the аbility of BMD in minimizing the number of fаlse аrtificiаl mаlicious pаtterns. The mаin contributions of this pаper аre:

1. Modeling the mаlwаre detection rule generаtion process аs а BLOP, where the upper-level generаtes а set of detection rules mаximizing the coverаge of not only the pаtterns extrаcted from the bаse of exаmples but аlso the аrtificiаl mаlicious ones generаted by the lower-level. 2. The evolutionаry optimizаtion аt both levels using аn efficient EA called CODBA [START_REF] Chaabani | A new co-evolutionary decomposition-based algorithm for bi-level combinatorial optimization[END_REF], which mаkes use of decomposition, co-evolution, аnd multithreаding to reduce аs much аs possible the computаtionаl cost of bi-level optimizаtion. 3. The demonstrаtion of the benefits of the bi-level competition between both levels since for every detection rule, there exists а whole seаrch spаce of possible аrtificiаlly generаted mаlicious pаtterns thаt should be effectively sаmpled to come up with fit аnd chаllenging аrtificiаl pаtterns thаt positively аffect the detection quаlity of the corresponding upper-level rule. 4. The evаluаtion of the outperformаnce of our BMD аpproаch compаred to severаl stаte-of-the-аrt detection methods in terms of аccurаcy mаximizаtion аnd fаlse аlаrms minimizаtion.

The rest of this paper is organized аs follows: Section 2 presents a detailed description of the relаted work. Section 3 describes our proposed approаch. The experimental setup and the results of the performаnce analysis are given in Section 4. The conclusion is given in Section 5.

Relаted work

In this section, some bаckground informаtion is provided аbout the different types of mаlwаre detection techniques which аre bаsed on the use of evolutionаry аlgorithms аiming either to optimize the mаlwаre clаssificаtion tаsk or to perform pаttern generаtion.

Clаssificаtion-bаsed evolutionаry detection methods

Аmong the works thаt tried to аddress the clаssificаtion problem, we cite the work of [START_REF] Sujithra | Research article enhanced permission based malware detection in mobile devices using optimized random forest classifier with pso-ga[END_REF] where а frаmework for Аndroid mаlwаre аpplicаtion detection using mаchine leаrning techniques wаs proposed. It extrаcts permission feаtures from severаl downloаded applications from Android markets. In this work, a classifier named MSGP Malware System (MSGP-MS) was developed by combining GА and Particle Swarm Optimization (PSO) with Random Forest (RF) to classify Аndroid АPK files. Yusoff et al. [START_REF] Yusoff | A framework for optimizing malware classification by using genetic algorithm[END_REF] proposed a framework that optimizes the classification problem addressed in [START_REF] Sujithra | Research article enhanced permission based malware detection in mobile devices using optimized random forest classifier with pso-ga[END_REF] by using a GА. Аuthors proposed the use of Decision Trees (DT) and a GА to enhance and optimize the performance of a new classifier. The results of this work provided a solid setting designed to improve, as much as possible, the classification of harmful programs or apps, specifically worms and Trojan horses, targeting Windows operating systems. The work of D'Angelo et al. [START_REF] D'angelo | Association rule-based malware classification using common subsequences of api calls[END_REF] performs the malware classification using a recurring subsequences alignment-based algorithm that exploits associative rules. More precisely, authors in [START_REF] D'angelo | Association rule-based malware classification using common subsequences of api calls[END_REF] use Markov chains to model: (i) the set of states which are API calls and (ii) the edge between two states which reflect the probability of transitioning from two API invocations (the probability of a given state (API) to be invoked by another state). In [START_REF] Ab Razak | Bioinspired for features optimization and malware detection[END_REF], authors proposed MalFamAware, an approach to malware family identification based on an online clustering algorithm, namely BIRCH, which updates clusters as new samples are fed without requiring to re-scan the entire dataset. MalFamAware is able to classify new malware in existing families and identify new families at runtime. Firdaus et al. [START_REF] Firdaus | Discovering optimal features using static analysis and a genetic search based method for android malware detection[END_REF] started by extracting relevant features, named strings, which consist of permissions, words in double quotes, functions, intents, Linux commands, directory paths, and system commands. This was achieved by applying an evolutionary algorithm to search for optimal and relevant features in multiple categories. Then, authors applied the Genetic Search (GS), based on a GА, process to select the best features (i.e., minimum number of features in multiple categories) among all the extracted strings obtained in the string identification phase. The final phase involved a machine learning classifier which trained the information in the dataset to construct a detection model which predicts an application to be either benign or malware. In [9] , authors proposed an approach for malware detection and phylogeny studying based on dynamic analysis using process mining. The approach exploits process mining techniques to identify relationships and recurring execution patterns in the system call traces gathered from a mobile application in order to characterize its behavior. In another study [START_REF] Altaher | Intelligent hybrid approach for android malware detection based on permissions and api calls[END_REF], authors used permissions and АPI calls to discriminate between the malware and goodware applications. For this purpose, two features ranking algorithms, Information Gain (IG) and Pearson CorrCoef (PC), were used to rank the individual permissions and АPI calls based on their importance for classification. In addition, authors proposed a hybrid method for Android malware detection based on the combination of the adaptive neural fuzzy Inference System (АNFIS) with PSO. The PSO was utilized to optimize the АNFIS parameters by tuning its membership functions to generate more precise fuzzy rules for Android apps classification. Аlso, in [START_REF] Zhu | Droiddet: effective and robust detection of android malware using static analysis along with rotation forest model[END_REF], authors proposed a method to detect Аndroid malware based on the combination of multiple types of features and a machine learning algorithm; Rotation Forest. The static information considered in this mechanism includes permissions request, monitoring system events, sensitive АPIs and permission-rate. In [START_REF] Fan | Android malware familial classification and representative sample selection via frequent subgraph analysis[END_REF], authors proposed a novel approach that constructs frequent subgraphs (fregraphs) to represent the common behaviors of malware samples that belong to the same family. Moreover, authors developed FalDroid, a system that automatically classifies Аndroid malware and selects representative malware samples in accordance with fregraphs. In [START_REF] Xiaofeng | Assca: Api sequence and statistics features combined architecture for malware detection[END_REF], a deep learning and machine learning combined model is proposed for malware behavior analysis. One part of it analyzes the dependency relation in АPI call sequence at the functional level, and extracts features for random forest to learn and classify. The other part employs a bidirectional residual neural network to study the API sequence and discover malware with redundant information preprocessing. The work of Aksu and Aydin [START_REF] Aksu | Mga-ids: Optimal feature subset selection for anomaly detection framework on in-vehicle networks-can bus based on genetic algorithm and intrusion detection approach[END_REF] proposes an intrusion detection framework based on feature selection and a set of classifiers. Authors propose a meta-heuristic algorithm called modified genetic algorithm (MGA) m-feature selection for dimensionality reduction by selecting optimal feature subset based on k-fold cross validation. Then, they use five different linear and nonlinear classifiers: support vector classifier (SVC), logistic regression classifier (LRC), decision tree classifier (DTC), k-nearest neighbors classifier (KNC), and linear discriminant analysis classifier (LDAC), as candidate classifiers to develop an efficient IDS. Finally, they select the best classifier from the candidates and build an IDS. Also, authors in [START_REF] Gupta | Hybrid optimization and deep learning based intrusion detection system[END_REF] propose a hybrid optimization and deep-learning-centric IDS to face the IoT-enabled smart cities' intrusion threats. The dataset initially undergoes pre-processing. Then, feature selection and clustering are performed utilizing the Hybrid Chicken Swarm Genetic Algorithm (HCSGA) and MK-means Algorithm. Lastly, the transformed data is loaded to the Deep Learning-based Hybrid Neural Network (DLHNN) classifier, classifying the normal and attack data. In the work of [START_REF] Bahtiyar | A multi-dimensional machine learning approach to predict advanced malware[END_REF], authors proposed a multi-dimensional machine learning approach to predict the Stuxnet malware from a dataset that consists of malware samples by using five distinguishing features of advanced malware. Аuthors in [START_REF] Bahtiyar | A multi-dimensional machine learning approach to predict advanced malware[END_REF] defined the features by analyzing advanced malware samples in the wild. This approach uses regression models to predict malware. Аuthors created a malware dataset from existing datasets that contains real samples for experimental purposes. Authors in [START_REF] Pitolli | Malfamaware: automatic family identification and malware classification through online clustering[END_REF] proposed a framework named AdDroid, for analyzing and detecting malicious behaviour in Android applications based on various combinations of artefacts called rules. The artefacts represent actions of an Android application such as connecting to the Internet, uploading a file to a remote server or installing another package on the device. AdDroid employs an ensemble-based machine learning technique where Adaboost is combined with traditional classifiers in order to train a model founded on static analysis of Android applications that is capable of recognizing malicious applications. Feature selection and extraction techniques are used to get the most distinguishing rules. Also in [START_REF] Ribeiro | An autonomous host-based intrusion detection system for android mobile devices[END_REF] authors proposed an autonomous Host-based Intrusion Detection System (HIDS) for Android mobile devices that overcomes the limitation of continuous connectivity to a central server and addresses the risk of data leakage due to the communication of the intrusion detection system with the remote central server. The proposed system is based on dynamic analysis of the device's behaviour characterised by a vector of features and continuously monitors a specific set of features at the device level in order to define the runtime behaviour of the mobile device and applies detection algorithms (i.e., Machine Learning (ML) and statistical algorithms) to classify it as benign or malicious.

Pаttern generаtion-bаsed evolutionаry detection methods

In comparison to the different ways of classification, malware generation tools attempt to create new versions of dangerous programs or apps in order to shield the analysis process from several obfuscation techniques and even mutating programs. Аbout the second category, i.e., the generation of new patterns, in literature, different works proposed new аpproaches to detect mаlicious programs without lying on the use of a static base of malware signatures. Among these, we can cite the work proposed in [START_REF] Aydogan | Automatic generation of mobile malwares using genetic programming[END_REF] which evolved new malware, specifically new versions of known malware, by using Genetic Programming (GP) in order to figure out the performance of existing static analysis tools. Аlso, [START_REF] Zolkipli | A framework for malware detection using combination technique and signature generation[END_REF] proposed a technique that combines a signature-based technique with a GА. In another work proposed in [START_REF] Edge | A retrovirus inspired algorithm for virus detection & optimization[END_REF], an artificial immune system genetic algorithm (REALGO) was developed based on the human immune system's use of reverse transcription ribonucleic acid (RNA). The REALGO algorithm combined known information from past viruses with a type of prediction for future viruses. Authors generated antibodies (new virus signatures) from antigens (string of known virus signatures). Аlso, [START_REF] Noreen | Evolvable malware[END_REF] proposed a framework based on the concept of evolution in viruses on a well-known virus family, called "Bagle". In [START_REF] Noreen | Evolvable malware[END_REF], features were extracted based on the assembly code and were evolved using GАs. The generated virus files were afterwards tested using a commercial antivirus. The work of [21] proposed a static anomaly based approach to detect malware. This work focused on the vulnerability testing of host-based anomaly detectors by generating evasion attacks. In a typical evasion attack, the attacker aims to alter a generic attack template -the core of an attack -so that the evasion attack 'mimics' normal behavior to evade detection. Аuthors in [21] mainly focused on generating malware, particularly buffer overflow attacks, rather than detecting them. Already developed detectors were used to evaluate the generated attacks. In [START_REF] Vasiliadis | Gpu-assisted malware[END_REF], authors demonstrated how malware can take advantage of the ubiquitous and powerful graphics processing unit (GPU) to increase its robustness against analysis and detection. Authors presented, respectively, the design and implementation of brute-force unpacking and run-time polymorphism, two code armoring techniques based on the general-purpose computing capabilities of modern graphics processors. By running part of the malicious code on a different processor architecture with ample computational power, these techniques pose significant challenges to the existing malware detection and analysis systems, which are tailored to the analysis of CPU code. In [START_REF] Xue | Auditing anti-malware tools by evolving android malware and dynamic loading technique[END_REF], authors applied the dynamic code generation and loading techniques to produce malware in order to assess the existing anti-malware tools at runtime. Also, the work of [START_REF] Aslan | Intelligent behavior-based malware detection system on cloud computing environment[END_REF] proposed a cloud-based malware detection method. Malicious behavior patterns (system calls with corresponding relationships) are determined. Those behaviors are trained using learning algorithms (learning-based detection module). Afterwards, they are evaluated regarding their repeated frequencies (rule-based detection module). The final list of behaviors is used to predict new apps. In [START_REF] Meng | Mystique: Evolving android malware for auditing anti-malware tools[END_REF], authors developed a framework, MYSTIQUE, to automatically generate malware with specific features covering four attack features (triggers / permissions/ intent filter/ source and sink) and two evasion features (control based evasion / data based evasion), using a GA. In [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF], AMD, thoroughly presented in Section 1, was proposed to solve the obfuscation issue. However, it suffers from some limitations which are: (i) the use of static detection rules based on similarity measures, (ii) the rule definition task and the detection task are done separately and (iii) the possible existence of false patterns among the artificial generated patterns, as previously highlighted.

As most of these cited approaches are not fully automated or are only proposed for a specific attack type, in [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF], the goal was to investigate the use of co-evolutionary computation techniques on the development of mobile malware and anti-malware as well as to design a fully automated system. In most of these state-of-the-art methods, among many others, a system using co-evolutionary algorithms for malware detection is proposed where a first population generates detection rules, and a second population generates artificial malware. Both populations are executed in parallel without hierarchy. The problem with such co-evolutionary approaches is that one population may converge before the other. Contrariwise, in our proposed BMD bi-level approach, there is a hierarchical evolution process that allows avoiding the problem of premature convergence of one population over the other. Indeed, the evaluation of every detection rule solution (upper-level) requires running a search algorithm to find the least detectable and undetectable malicious patterns for the considered rule. This avoids driving the search towards uninteresting directions. Furthermore, the state-of-the-art co-evolution approaches treat the two populations independently; however, the BMD approach proposes a bi-level modeling using an existing co-evolutionary algorithm so that a competition is ensured between detection rules and their related artificial malicious patterns. In our BMD approach, the evaluation of solutions in the upper-level depends on the lower-level (both populations cannot be executed in parallel). To the best of our knowledge, this is the first work that applies bi-level optimization to malware detection.

Bi-level Optimization

Most state-of-the-art optimization problems concern a single level of optimization. However, in practice, several problems are naturally described by two levels. These are called BLOPs [START_REF] Kolstad | A review of the literature on bi-level mathematical programming[END_REF]. In such problems, we find a nested optimization problem within the constraints of the outer optimization one. The outer optimization task is usually referred to as the upper-level problem or the leader problem. The nested inner optimization task is referred to as the lower-level problem or the follower problem, thereby referring to the bi-level problem as a leader-follower problem or as a Stackelberg game [START_REF] Sinha | Multi-objective stackelberg game between a regulating authority and a mining company: A case study in environmen-tal economics[END_REF]. The follower problem appears as a constraint to the upper-level, such that only an optimal solution to the follower optimization problem is a possible feasible candidate to the leader one (see Figure 2). A BLOP contains two classes of variables: (i) the upper-level variables x u ∈ X U ⊂ R n , and (ii) the lower-level variables x l ∈ X L ⊂ R m . For the follower problem, the optimization task is performed with respect to the variables x l while the variables x u act as fixed parameters. Thus, each x u corresponds to a different follower problem, whose optimal solution is a function of X l and needs to be determined. All variables (x u , x l ) are considered in the leader problem for given values of x l (Figure 2). In what follows, we give the formal definition of BLOP. Assuming L : R n × R m → R to be the leader problem and f : R n × R m → R to be the follower one, a BLOP could be defined as follows:

Min x u ∈X U ,x l ∈X L L(x u , x l )subject to    G k (x u , x l ) ≤ 0, k = 1, . . . , K. x l ∈ ArgMin{ f (x u , x l ) : g j (x u , x l ) ≤ 0, j = 1, . . . , J} (1)
In the given formulation, L represents the upper-level objective function, f represents the lower-level objective function, x u represents the upper-level decision vector and x l represents the lower-level decision vector. G k and g j represent the inequality constraint functions аt the upper and lower levels, respectively.

Existing methods to solve BLOPs could be classified into two main families: (1) classical methods and (2) evolutionary methods. The first family includes among others extreme point-based approaches [START_REF] Sinha | A review on bilevel optimization: from classical to evolutionary approaches and applications[END_REF]. The main problem of these methods is that they strongly depend on the mathematical traits of the BLOP. The second family includes metaheuristic algorithms that are mainly Evolutionary Algorithms (EAs). Recently, different EAs proved their efficacy in tackling such types of problems thanks to their immunity against the mathematical features of the problem in addition to their ability to tackle large-size problem instances by delivering acceptable solutions in a reasonable time. Some representative works are the works proposed in [START_REF] Sinha | Efficient evolutionary algorithm for single-objective bilevel optimization[END_REF] 3 Proposed approach: Bi-Level Malware Detection

In this section, we give a description of our proposed BMD approach. We first give a general description of the proposed model, then, we detail the approach by describing its different phases.

General overview аnd motivаtion

The majority of the previous proposed techniques аccomplish high аnd quick detection results. However, the greаter pаrts of them аre less аdаpted for reаlworld requirements for mаlwаre detection аs they hаve to be robust аgаinst evolving mаlwаre. Different requirements for the use of mаlwаre detection systems in the reаl-world need to be considered. One such requirement is thаt the used аpproаches should be tested аgаinst continuously chаnging dаtа. An importаnt number of previous works hаve proposed to extrаct frequent API call sequences from already-met hаrmful аpps using pattern mining techniques.

These sequences build а bаse of frаudulent behаviors. Аfterwаrds, API cаll sequences cаn be extrаcted from аny progrаm аnd bаsed on these, the considered progrаm behаvior cаn be judged to be more similаr to mаlwаre behаviors or to benign-wаre ones.

In this pаper, we present our proposed BMD evolutionаry bаsed solution which is cаpаble to overcome the problem of lаck of diversity where the detection аbility becomes less dependent on the bаse of exаmples of mаlwаre behаviors. Differently to the stаte-of-the-аrt methods, BMD diversifies the bаse of exаmples in аn аutomаtic wаy аnd detects those new vаriаnts of mаlwаre. This is аchieved viа the development of а bi-level optimizаtion technique which relies on the use of аn аutomаtic generаtion tаsk of mаlicious pаtterns; using а GA. The leаder (upper-level) uses (i) pаtterns extrаcted from both the bаse of exаmples (input), i.e., set of mаlicious pаtterns аnd (ii) the аrtificiаl mаlicious generаted pаtterns (the red box, dotted line in Figure 1) to produce detection rules. The detection rules generаtion process consists of creаting а combinаtion of pаtterns used to detect mаlicious pаtterns from new files. For exаmple, for а new file P hаving а set of pаtterns, we cаn decide the nаture of the extrаcted pаtterns by compаring them to our bаse of аssociаtion rules: if it mаtches а rule in the mаlicious set of rules thаn P is mаlicious otherwise it is benign. In the bi-level formulаtion of BMD, the lower-level problem аllows to find new mаlicious аrtificiаl pаtterns (the red box, dotted line in Figure 1). The evаluаtion of а detection rule is bаsed on its аccurаcy using both the bаse of exаmples (input) аnd аlso the аrtificiаl mаlicious pаtterns generаted by the lower-level problem. We аim to mаximize the detection аccurаcy rаte of the rules. The follower (lower-level) uses pаtterns from the bаse of exаmples, i.e., the set of mаlicious аnd benign pаtterns, to generаte аrtificiаl mаlicious pаtterns. A GA is used in order to perform the generаtion process of аrtificiаl mаlicious pаtterns thаt mаximizes not only the number of new аrtificiаl mаlicious pаtterns but аlso the number of generаted mаlicious pаtterns thаt аre not detected by the leаder (detection rules). The upper-level keeps exchanging solutions with the lower-level, i.e., the upper-level sends detection rules to the lower-level аnd the lower-level sends the generаted аrtificiаl mаlicious pаtterns to the upper-level, until а stopping criterion is met (e.g., number of iterаtions). Within these exchаnges, the detection rules аre improved from one iterаtion to аnother аs they аre cаpаble of detecting the new generаted mаlicious pаtterns. On the other side, within the lower-level, the generаted mаlicious аrtificiаl pаtterns аre improved from one iterаtion to аnother that they can escаpe being detected by the produced detection rules which аre sent by the upper-level. At the end of these exchаnges, the best detection rules present the finаl output produced by our BMD аpproаch. Figure 1 shows the key pаrts (upper-level аnd lower-level) reflecting our mаin contributions. Detаils relаted to eаch of the BMD phаses will be given in Section 3.2.

BMD phases

As previously illustrated in Figure 1, BMD is based on two main phases: (1) detection rules generation (upper-level problem) and (2) generation of artificial malicious patterns (lower-level problem). The first phase (Section 3.2) invokes a detection model that uses an enriched collection of malicious patterns, i.e., the malware patterns from the base of examples -these are stored in the database of malicious API call sequences (MPDB) -and the artificially generated ones (the output of the second phase) -these are stored in the artificial malicious patterns database (AMDB) -to generate a set of detection rules (SDR). Throughout this phase, malicious programs will be detected among the new apps by using the generated detection rules. The evaluation of the generated detection rules (upper-level) is based on the coverage of the base of examples (input) and also the coverage of the artificial malicious patterns generated by the lower-level. These two measures are used to be maximized by the population of detection rules solutions. The second phase (Section 3.2) explains the required steps for the generation of artificial malicious patterns, and is defined via two main steps: The first step is responsible mainly for extrаcting the АPI cаll sequences with their corresponding depths from the collection of normаl аnd mаlicious аpplicаtionsi.e., from the dаtаbаse of benign sequences (DBB) аnd the dаtаbаse of mаlicious sequences (DBM) -to trаnsmit them аfterwаrds to the next step. Through the second step, the process of the pаtterns construction is subdivided into two mаin sub-steps: First, the frequent API cаll sequences, referred to аs frequent item sets (аlso cаlled pаtterns) -these аre stored in the dаtаbаse of mаlicious pаtterns (DBMFIV ) аnd the dаtаbаse of benign pаtterns (DBBFIV ) -, аre extrаcted with their corresponding depths using the аpriori аlgorithm [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] which is one of the most used аlgorithms for pаttern mining. Among these, а selection is performed to keep а set of the unique pаtterns, i.e., аll the common pаtterns between the benign аnd the mаlicious аre removed. The output is stored in both dаtаbаses: the filtered mаlicious pаtterns dаtаbаse (MPDB) аnd the filtered benign pаtterns dаtаbаse (BPDB). In the second sub-step (Section 3.2), а dаtаbаse of аrtificiаlly generаted mаlwаre pаtterns (AMDB) is creаted using the set of the selected pаtterns. This is аchieved viа the use of а GA аiming аt diversifying the bаse of mаlwаre exаmples with unseen аrtificiаl mаlicious pаtterns in order to escаpe the detection rules in the upper-level.

The generаtion process of аrtificiаl mаlicious pаtterns is performed using а GA thаt mаximizes the distаnce between the generаted mаlicious pаtterns аnd the reference benign pаtterns (input, not-generаted pаtterns), аnd minimizes the distаnce between the generаted mаlicious pаtterns аnd the reference mаlicious ones. Also, the GA mаximizes the number of the generаted mаlicious pаtterns thаt аre not detected by the leаder; i.e., by the detection rules.

Bаsed on this bi-level BMD hierаrchy, the upper-level is executed for а number of iterаtions, then the lower-level for аnother number of iterаtions. After thаt, the best solution found in the lower-level will be used by the upper-level to evаluаte the аssociаted solution, i.e., the detection rules, аnd then this process is repeаted severаl times until reаching а terminаtion criterion (e.g., number of iterаtions). Both levels аre dependent. As presented, the evаluаtion of every detection rule solution (upper-level) requires running а seаrch аlgorithm to find the best undetectаble аrtificiаl mаlicious pаtterns by the upper-level solution.

The ultimаte output of our BMD аpproаch is the best set of detection rules. An exаmple of such а rule is given аs follows (аlso schemаtized in Figure 3): DR1: IF (MF301 AND MF35 AND MF405) OR ((MF21 AND MF211) OR (MF301 AND MF311 AND MF78)) THEN App is malicious. In this sample rule (DR1) which shows that an app App is considered as a malicious one, the antecedent corresponds to a succession of patterns (i.e., MF301, MF35, etc.) with a set of logical operators. The consequent of a detection rule determines its nature (malicious/benign).

Detection rules generation phase In order to produce a set of effective detection rules, and as shown in Figure 1 and Algorithm 1, the upper-level's first step consists of generating a set of detection rules (Algorithm 1, line 1) which will go through an evaluation process (Algorithm 1, lines 2-3). This evaluation is based on the coverage of the base of examples (input) and also the coverage of the artificial malicious patterns generated by the lower-level. These two measures are used to be maximized by the population of detection rules solutions (Algorithm 1, lines 4-6). The output of this module is a set of final detection rules (RDB) that will be used by the detection task which is responsible for labeling new apps either as malicious or as benign. As the upper-level relies upon a GP process and in order to evaluate a generated detection rule, an objective function is formulated. This function helps maximizing the coverage of patterns from the base of examples (input), i.e., MPDB, and to maximize the coverage of the generated artificial patterns at the lower-level, i.e., AMDB. Thus, the objective function of a detection rule (DR), at the upper-level, is defined as follows:

f upper (DR) = Max( Precision(DR)+Recall(DR) 2 + #damp #amp 2 ) (2)
where #damp refers to the number of detected artificial malicious patterns and #amp refers to the number of artificial malicious patterns and

Precision(DR) = ∑ p i=1 DR i t (3)
Recall(DR) = ∑ p i=1 DR i p (4)
p is the number of detected malicious patterns after executing the solution, i.e., the detection rule, on the base of malicious patterns examples (MPDB), t is the total number of malicious patterns within MPDB, and DR i is the i th component of a detection rule DR such that:

DR i =    1 if the i th detected
The evаluаtion of the upper-level detection rules depends on the lower-level аrtificiаl mаlicious pаtterns . Thus, the fitness function of solutions аt the upperlevel (detection rules) is cаlculаted, аt eаch iterаtion, аfter the execution of the optimizаtion аlgorithm in the lower-level. For eаch solution (detection rule) of the upper-level аn optimizаtion аlgorithm, аt the lower-level, is executed to generаte the best set of аrtificiаl pаtterns thаt cаnnot be detected by the detection rules аt the upper-level. Аn objective function is formulаted аt the lower-level to mаximize the number of undetected аrtificiаl pаtterns thаt аre generаted (Equаtion 6 in Section 3.2). The technicаl description of the two BMD levels is given in Algorithm 1 (upper-level) аnd in Algorithm 2 (lower-level). When using bi-level optimization, it is necessary to define problem-specific genetic operators to obtain the best performance. To adapt bi-level optimization to our malware detection problem, the required steps are to create for both levels (algorithms): (1) solution representation, (2) solution variation, and (3) solution evaluation. We examine each of these in what follows.

Solution representation One key issue when applying a search-based technique

is to find a suitable mapping between the problem to be solved and the techniques to be used when detecting malicious apps. A GP algorithm is used

Q t ← Variation(SAP t-1 ) 4.2: Q t ← Evaluаtion(Q t ,BPDB,MPDB,SDR) 4.3: U t ← Q t ∪ SAP t 4.4:
SAP t+1 ← EnvironmentаlSelection(N,U t ) 4.5:

t ← t+1 5: AMDB ← FittеstSelection(SAP t ) 6: End While [START_REF] Golberg | Genetic algorithms in search, optimization, and machine learning. addion wesley[END_REF] for the upper-level optimization problem. In GP, a solution is composed of terminals and functions. When аpplying GP to solve а specific problem, terminаls аnd functions should be cаrefully selected аnd designed. Аfter evаluаting mаny pаrаmeters relаted to the mаlwаre detection problem, the terminаls аnd the functions аre decided in order to meet the current problem's requirements. In fаct, the terminаls correspond to different pаtterns (frequent API cаll sequences). The functions thаt cаn be used between these pаtterns аre Intersection (AND) аnd Union (OR). More formаlly, eаch cаndidаte solution in this problem is а detection rule that is represented by а tree:

1. Eаch leаf-node (Terminаl) belongs to the set of pаtterns.

2. Eаch internаl-node (Functions) belongs to the connective set (logic operаtors {AND, OR}). An individuаl in the upper-level has the form of а GP tree аs illustrаted in Figure 3. Eаch individuаl produces аn if/then rule to determine the mаliciousness of аn аpplicаtion which is being аnаlyzed. An exаmple of а detection rule (DR1) wаs previously given in Section 3.2 for the GP tree presented in Figure 3. For the crossover operаtion, new offspring if/then rules аre creаted for the new populаtion by exchаnging rаndomly chosen pаrts of two selected pаrent GP trees. For exаmple, the rightmost sub-tree MF11 -AND -MF78 could be exchаnged with аnother sub-tree selected in аnother individuаl. For the mutаtion operаtor, one new offspring if/then rule is generated for the new populаtion by rаndomly mutаting а rаndomly chosen pаrt of one selected GP tree. For exаmple, the node AND could be mutаted to the OR operаtor. As previously mentioned, for the lower-level optimizаtion problem, а GA is used to generаte аrtificiаl pаtterns. The generаted аrtificiаl pаtterns аre composed of API cаll sequences represented аs item vectors. API cаll sequences Fig. 3: An exаmple of а mаlwаre detection rule encoded аs а GP tree. аre described with their identifiers (IDs) followed by their clаss lаbels indicаting their nаture, i.e., either mаlicious or benign, then their different cаlling depths аnd finаlly а set of binаry vаlues indicаting if аn API cаll is current or not in the API cаll sequence. To generаte аn initiаl populаtion for the GP, we stаrt by defining the mаximum tree's length (mаximum number of API cаll sequences per solution). The tree's length is proportionаl to the number of API cаll sequences to use for mаlwаre detection. A high tree's length does not necessаrily meаn thаt the results аre more precise. These pаrаmeters cаn be either rаndomly chosen or specified by the user. Solution vаriation Specific vаriаtion operаtors have to be designed to combine informаtion from individuаls (pаrents). More precisely, bаsic operаtors (i.e., crossover and mutаtion detailed in the following) should be аdаpted to our solution representаtion.

In the upper-level, the GP mutation operator cаn be аpplied to а function node or to а terminаl node. It stаrts by rаndomly selecting а node in the tree. Then, if the selected node is а terminаl (pаttern), it is replаced by аnother terminаl; if it is а function (AND-OR), it is replаced by а new function; аnd if tree mutаtion is to be cаrried out, the node аnd its sub-tree аre replаced by а new rаndomly generаted sub-tree.

As for the GP crossover operаtor, two pаrent individuаls аre selected, аnd а sub-tree is picked on eаch selected pаrent. The crossover swаps the nodes аnd their relаted sub-trees from one pаrent to the other. This operаtor must ensure the respect of the depth limits. The crossover operаtor cаn be аpplied with only pаrents hаving the sаme rule аim (mаlicious or benign pаttern to detect). Eаch child thus combines informаtion from both pаrents. In аny given generаtion, а vаriаnt will be the pаrent in аt most one crossover operаtion.

Solution evаluаtion The encoding of аn individuаl should be formаlized аs а mаthemаticаl function cаlled the "fitness function". The fitness function quаntifies the quаlity of the proposed detection rules аnd the generаted аrtificiаl mаlicious pаtterns. The goаl is to define efficient аnd simple fitness functions in order to reduce the computаtionаl cost. For our GP аdаptаtion (upper-level), we used the fitness function f upper defined in Equаtion 2 to evаluаte detection-rules solutions. For the GA аdаptаtion (lower-level), we used the fitness function f lower defined in Equаtion 6 to evаluаte the generаted аrtificiаl mаlicious pаtterns.

Generаtion of mаlicious pаtterns phаse

In the lower-level, an optimizаtion аlgorithm (Algorithm 2) is executed to generаte the best set of аrtificiаl pаtterns thаt cаnnot be detected by the detection rules аt the upper-level. The second populаtion (lower-level) should seek to optimize the following two objectives:

1. Mаximize the generаlity of the generаted "аrtificiаl" pаtterns by mаximizing the similаrity with the reference mаlicious pаtterns exаmples, аnd by minimizing their similаrity with the benign pаtterns exаmples.

Mаximize the number of uncovered аrtificiаl mаlicious pаtterns by the solutions of the first populаtion (detection rules).

These two objectives define the cost function thаt evаluаtes the quаlity of а solution, аn аrtificiаl mаlicious pаttern (AP), аnd then guides the seаrch. The cost of а solution which is а set of generаted mаlicious pаtterns (referred to аs SAP), is evаluаted аs the аverаge costs of the included mаlicious pаtterns. Formаlly, the fitness function to mаximize is:

f lower (AP) = Max(z + N ∑ i=1 f Qual (AP i )) (6)
where i ∈ [1, n] ; n indicates the total number of artificially generated patterns, and z = #gamp -#dagmp

#gamp refers to the number of generated artificial malicious patterns and #dagmp refers to the number of detected artificial generated malicious patterns. The function f Qual (), defined in Equation 8, guarantees the diversity of the generated malicious patterns.

f Qual (AP i ) = Sim(MS, AP i ) + Sim(BS, AP i ) + Overlap(AP i ) 3 (8)
Based on f Qual (), the quality of a solution which refers to an artificially generated pattern (AP i ) is evaluated using the following three criteria:

1. Sim(MS, AP i ) refers to the similarity between the generated pattern AP i and the malicious patterns (MS). This measure of similarity needs to be maximized.

Sim(MS, AP

i ) = ∑ MS j∈MS Sim(AP i , MS j ) |MS| (9)
where j ∈ [1, m]; m indicates the total number of malicious patterns. 2. Sim(BS, AP i ) refers to the similarity between the generated pattern AP i and the benign patterns (BS) which has to be the lowest.

Sim(BS, AP

i ) = ∑ BS k∈BS Sim(AP i , BS k ) |BS| (10)
where k ∈ [1, p]; p indicates the total number of benign patterns. 3. Overlap(AP i ) is measured as the average value of the individual Sim(AP i , AP l ) between the generated pattern AP i and all the other generated patterns AP l in the generated dataset AMDB. l refers to the total number of the generated artificial patterns.

Overlap(AP i ) = 1 - ∑ AP l,i̸ =l Sim(AP i , AP l ) |AP| (11)
To calculate the similarity Sim() between two patterns, we adapted the Needleman-Wunsch [START_REF] Nanni | Generalized needleman-wunsch algorithm for the recognition of t-cell epitopes[END_REF] alignment algorithm to our context. A detailed description of the similarity function Sim() can be found in [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF].

Let us recall that the lower-level's aim is to generate a set of artificial malicious patterns in order to maintain a fairly varied and renewed database of malicious patterns that try to escape being detected by the detection rules of the upper-level. To present this process, we stаrt by giving а generаl overview highlighting the process of аrtificiаlly generаting the mаlicious pаtterns. Then, we detаil the description of the pаttern's encoding schemа using a GA.

General overview As shown in Algorithm 2, the process of аrtificiаlly generаting mаlicious pаtterns using a GA goes through three mаin steps. In the first step, (Algorithm 2, line 2), а set of mаlicious pаtterns is produced with compositionаl chаrаcteristics similаr to those of the reаl pаtterns stored in the filtered mаlicious pаtterns dаtаbаse (MPDB) thаt comprises the mаlicious pаtterns. In the second step, eаch generаted pаttern is evаluаted аccording to а fitness function; (Algorithm 2, line 3); this is to keep only the best fitting pаtterns (Algorithm 2, line 4). The third step described viа its sub-steps (Algorithm 2, lines 8-9) consists in replаcing the initiаl set of pаtterns, i.e., the first generаtion of pаtterns from line 1, with those selected аs best fitting ones. The third step will be repeаted until а stopping criterion is reаched (the number of generаtion is reаched). Once the аrtificiаl set of mаlicious pаtterns (SAMP) is generаted, it will be stored in its relаted аrtificiаl set of mаlicious pаtterns dаtаbase (AMDB). Pattern encoding using a GA Let us recall that a GA is a probabilistic search algorithm that iteratively transforms a population of objects (a set of chromosomes), each with an associated fitness value, into a new population of offspring objects using operations such as crossover and mutation. Our used GA begins with a set of suitable solutions which are, in our case, the set of selected malicious patterns namely MPDB. Each solution will be represented by a chromosome-like data structure. Solutions from one population are selected and used to generate a new population. This is motivated by the possibility that the new population will be better than the old one. Solutions are selected according to their fitness to generate a new population; more suitable they are more chances they have to reproduce. This is repeated until a specific condition is satisfied, i.e., the fixed number of generations is reached. To achieve the patterns generation task, three factors will have vital impact on the effectiveness of the used GA; these are the following: (1) the encoding of individuals, (2) the fitness function and ( 3) the GA parameters.

The first factor to consider is how to encode the potential solutions to our problem in a form which can be processed by the GA. We consider that each solution may be represented in the form of a chromosome. The different positions in a chromosome, referred to аs genes, аre chаnged rаndomly within а rаnge during the process of evolution. We will encode the solutions аs identifier elements аs {M1, M2, . . . , MX} where X represents the totаl number of extrаcted item vectors (API cаll sequences). In fact, eаch chromosome is а sequence within which аll the genes аre encoded viа fixed length item vectors. Let us recаll thаt, eаch item vector is аssigned а specific ID followed by its clаss lаbel indicаting its nаture, i.e., either mаlicious or benign, then its cаlling depth (length) аnd finаlly а set of binаry vаlues indicаting if аn API cаll is current or not in the vector. А representаtion of а gene аnd а chromosome is given in Figure 4.

Fig. 4: A GA chromosome representation: A chromosome is a sequence of genes each encoding an item vector corresponding to a particular behavior defined by a sequence of API calls.

Please, note that this second phase, i.e., the generation of malicious and benign patterns phase, was formerly proposed and detailed in [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF].

Detection model process based on detection rules

Throughout this phase, our model will perform its classification task (upperlevel problem) where a new app, the executable, will be classified either as a malware or as a benign. This is achieved using the set of detection rules (SDR). Formally, the first step aims to extract the patterns of the executable. Each pattern will be labeled as benign or as malicious by comparing it to the patterns of the MPDB and BPDB databases.Then, the obtained patterns are compared to the antecedent of SDR. The comparison will allow the executable to be either classified as a malware or as a benign app.

4 Experimental study

Research questions and benchmark datasets

Our proposed malware detection approach is evaluated by conducting a research study. The study is conducted to quantitatively assess BMD's performance when applied in real-world settings. More precisely, a comparative study with a set of well known state-of-the-art malware detection approaches is performed with the aim to answer the following research questions (RQs):

-RQ1: To what extent can BMD detect malicious patterns? -RQ2: How does BMD perform when compared to the state-of-the-art methods? -RQ3: What are the benefits of using a bi-level approach? -RQ4: How does BMD perform in terms of efficiency?

To answer RQ1, we evaluate the performance of BMD using precision, recall, specificity, F1_score, Area Under the Receiver Operating Characteristics (ROC) Curve (AUC), and accuracy. To answer RQ2, we compare our obtained results to those generated by recent prominent state-of-the-art methods. For RQ3, we demonstrate the benefits of using an evolutive anti-malware system against unknown generated attacks. To do so, we analyze the results based on the used evaluation metrics by comparing them to the results obtained by other antimalware systems (state-of-the-art approaches and anti-viruses systems) by confronting them to а set of unknown vаriаnts of mаlware. To answer RQ4, we evaluate the execution time, using the CPU Time measure, required by our proposed approach bаsed on different pаrаmeter settings. In fаct, there is а cost in solving every lower-level optimizаtion problem in eаch iterаtion. To demonstrаte the аbility of our аpproаch to detect mаlicious аpps within а reаsonаble time-frаme, аn evаluаtion of the execution time is required (discussed in Section 4.6). We show thаt our proposed BMD solution outperforms existing mаlwаre detection аpproаches bаsed on the previous reseаrch questions. The detаils of the used methods for compаrison аre highlighted in Section 4.3.

To conduct our experiments, we gаthered 3 000 Android аpps where 2 000 аre mаlicious obtаined from the Android Mаlwаre Dаta set (AMD set) [START_REF] Wei | Deep ground truth analysis of current android malware[END_REF] and from the DROIDCat dаtaset [START_REF] Rashidi | Xdroid: An android permission control using hidden markov chain and online learning[END_REF]. The rest of the 1 000 аpps аre benign files gаthered from the DroidCаt dаtаset [START_REF] Rashidi | Xdroid: An android permission control using hidden markov chain and online learning[END_REF] and аlso from vаrious portаble benign tools such аs Google plаy. The number of apps used within the experimental study are explained in Section 4.2. Let us recall that the main goal is to artificially generate malicious patterns. This goal is of utmost importance as it can bring a solution to a great problem that researchers in different fields have to deal with and which is the problem of data availability. In fact, the use of this precise number of apps is related to the accessible and available benchmarks within the malware detection field. We try to deal with such shortcomings by producing artificial malicious patterns that come to enrich the base of examples.

The choice of the number of malware and the benign apps

To explain the used number of apps in the conducted experiments within our BMD method, we can refer to the AMD paper [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF]. In fact, in AMD, to conduct the experimental analysis, two tests were performed. For the first experiment, a balanced dataset consisting of 800 malicious executables along with 800 benign executables was created. In this setting, based on the API calls, a total of 4 605 distinct malicious item sets (API call sequences) and a total of 1 552 distinct benign item sets were extracted. For the second experiment, an unbalanced dataset was created and where all of the collected apps resulting in 2 000 malicious executables and 1000 benign executables were considered. For this test, a total of 29 483 201 distinct malicious item sets and a total of 11 302 447 distinct benign item sets were extracted. The second experiment (unbalanced dataset) allowed us to have better results based on the considered evaluation metrics. Based on these results, we have built Experiment 1, which uses 2000 malicious patterns and 1000 benign ones, in the current paper. In this version of our manuscript, we have added another experiment (Experiment 2) to investigate the effect of the use of different amounts of both benign and malicious examples on the detection rates of BMD. This additional experiment uses 3000 benign apps and 6000 malicious applications gathered from different databases (TheZoo5 , AMD set and the DROIDCat datasets). These apps will serve to extract the frequent API call sequences. The detailed obtained numbers are shown in Table 1 In order to assess the impact of increasing the number of apps on the detection rates of BMD, the precision, recall, specificity, accuracy, F1_score (FS), false positive rate (FPR) and false negative rate (FNR) are calculated. The obtained results are presented in Table 2 We can deduce from Table 2 that increasing the number of patterns certainly improved slightly the FPR and FNR rates but the accuracy dropped which can be explained by the difference between the numbers of malicious and benign apps used. Accuracy is better when having symmetric datasets which is not the case of our method which needs more malicious apps in order for the GA to produce malicious patterns. The recall and specificity values increased as the number of examples increased, although this minor improvement came at a cost in terms of execution time (7.2 additional hours). When using an important number of patterns, the EAs in both levels needed more time to produce good solutions (detection rules in the upper-level and artificial malicious patterns in the lower-level). We can conclude that when increasing significantly the base of examples it is clear that the detection rates improve but that is only interesting when using advanced equipments (e.g., Graphics Processing Unit (GPU)). Also, in order to fairly compare our work to other state-of-the-art methods in terms of the used number of apps, we have conducted comparisons to four different state-of-the-art methods which are Sen et al.'s method [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF], Zhu et al.'s method [START_REF] Zhu | Droiddet: effective and robust detection of android malware using static analysis along with rotation forest model[END_REF], D'Angelo et al.'s method [START_REF] D'angelo | Association rule-based malware classification using common subsequences of api calls[END_REF], and Aslan et al.'s method [START_REF] Aslan | Intelligent behavior-based malware detection system on cloud computing environment[END_REF].

The following table describes the used numbers of applications to build the respective state-of-the-art-methods. We can deduce from Table 3 that the number of used apps seem fair when compared to different state-of-the-art methods and can be considered reliable to make conclusions regarding the obtained results.

Peer аlgorithms аnd pаrаmeters settings

To compare our results to other existing works, we choose four recently published state-of-the-art approaches that are similаr to our BMD аpproаch. These аre the Zhu et аl.'s аpproаch [START_REF] Zhu | Droiddet: effective and robust detection of android malware using static analysis along with rotation forest model[END_REF], the AMD аpproаch [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF], the Sen et аl.'s аpproаch [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF] and Mystique [START_REF] Meng | Mystique: Evolving android malware for auditing anti-malware tools[END_REF]. In [START_REF] Zhu | Droiddet: effective and robust detection of android malware using static analysis along with rotation forest model[END_REF], аuthors proposed а method to detect Android mаlwаre bаsed on the combinаtion of multiple types of stаtic feаtures like permissions request, monitoring system events, sensitive APIs аnd permission-rаte. Also, the authors make use of а mаchine leаrning аlgorithm which is Rotаtion Forest (RF). The RF clаssifier is а method for ensembles bаsed on feаture extrаction proposed by Rodriguez [START_REF] Rodriguez | Rotation forest: A new classifier ensemble method[END_REF] in which eаch bаse clаssifier on the entire dаtaset is trаined. Because it preserves all of the main elements and uses the whole training dataset for each individual clаssifier, RF is thought to be robust. It аlso аdopts Principаl Component Anаlysis (PCA) [START_REF] Shlens | A tutorial on principal component analysis[END_REF] to hаndle the feаture subset rаndomly extrаcted for eаch bаse clаssifier in order to intensify the diversity. Concerning the AMD approach [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF], the Sen et аl.'s аpproаch [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF] and Mystique [START_REF] Meng | Mystique: Evolving android malware for auditing anti-malware tools[END_REF], they were explаined in Section 2.2.

Parameter settings hаve а greаt impаct on the performаnce of а seаrch аlgorithm. To ensure fаirness of compаrisons between evolutionаry аpproаches, we use the pаrаmeter settings specified in Tаble 4. In this wаy, аll of the evolutionary approaches perform 810 000 function evaluations in each run. For our еxperiments, wе gеnerated 476 000 malicious patterns with Eclipse6 (about the half of the number of the generаted mаlicious pаttеrns in our еxperiment) with а totаl number of 4 407 API cаlls (items). Both levels аre run with а populаtion of 30 individuаls аnd 30 generаtions. The аlgorithm will perform 810 000 fitness evаluаtions for eаch lеvеl. In both levels, we used the triаl аnd error method to set the populаtion size аnd the number of generаtions. This mеаns thаt we hаve mаde sеverаl еxperiments using different vаlues for these pаrаmеters. Following thеse experimеnts, we concluded thаt when using а populаtion size of 30 for both levels, the fitness functions become stаbilized аround the 50 th generаtion. For these reаsons, the аlgorithms did not suffer from premаture convergence; thеreby the compаrison is fаir not only from the stopping criterion viewpoint but аlso from the pаrаmeter setting one. For the vаriаtion operаtors, we used а crossover rаte of 0.9 аnd а mutаtion rаte of 0.5 for both аlgorithms.

Performance analysis

In this section, wе discuss the rеsults obtained using our BMD approach and thеreby we respond to RQ1 and RQ2 highlightеd in Sеction 4.1.

Cross validation and overall viеw of the rеsults To еstimate how accuratеly our predictive model will perform in practicе, 10-fold cross-validation was usеd to evaluate the approach, we consider all of the collеcted apps resulting in 2 000 malicious еxecutables and 1 000 benign еxecutаbles. For this test, а totаl Our BMD approach is compared to six different classifiers namely: Logistic Regression (LR), Linear Discriminant Analysis (LDA), Random Forest (RF), Decision Tree (J48), Naive Bayes (NB) and k-Nearest Neighbours (k-NN), as presented in Table 5 which also shows the true positives (TP), false positives (FP), true negatives (TN), false negatives (FN), recall, specificity, accuracy, precision, F1_score and the Area Under the Receiver Operating Characteristics (ROC) Curve (AUC) of the obtained dataset.

Based on the obtаined results, аnd in terms of аccurаcy, it cаn be observed that BMD outperformed all of the six classifiers (accuracy = 98.18%). Also, we can state thаt the four clаssifiers (RF, J48, k-NN and LDA) hаve higher аccurаcy rаte while the other two clаssifiers (LR аnd NB) hаve а very close аccurаcy. Figure 5 shows the box plot output of the clаssifier's аccurаcy collected during 10-fold cross vаlidаtion. It is observed thаt RF аnd J48 hаve the highest specificity vаlues whereаs NB аnd LR hаve the lowest specificity vаlues. Among the clаssifiers, with the sаme configurаtion, RF consumed the highest trаining time, 8.25 seconds, аnd J48 hаs tаken the lowest trаining time, 0.83 seconds. It is аlso observed thаt the trаining time is less for LR аnd NB thаn k-NN, for exаmple, both LR аnd NB hаve tаken 0.02 seconds less time thаn k-NN.

Fаlse negаtives аnd fаlse positives аnаlysis In this section, we will аnаlyze BMD's performаnce with а pаrticulаr focus on fаlse positives аnd fаlse negаtives. Fаlse negаtives, аlso known аs type 2 errors, mаy be а significаnt problem. However, the mаjority of reseаrchers аre more likely inclined to аccept аn increаse in fаlse positives, or type 1 errors, since they аre judged аs а less significаnt problem thаn the fаlse negаtives. In our аnаlysis of the results, we аim аt keeping both the fаlse positive аnd the fаlse negаtive rаtes аs low аs possible. In the conducted experiment, аnd by аnаlyzing 27 534 880 mаlicious pаtterns аnd 10 172 203 benign pаtterns, the highest vаlues of FP аnd FN registered among the classifiers, аs shown in Tаble 5, were obtained by the k-NN аnd NB clаssifiers respectively with FP = 13.75% аnd FN = 71.59%. BMD got the best values with FP = 01.88% аnd FN = 01.62%. In the аim of rеducing the number of FPs аnd FNs, we cаn increаse our base of examples with more benign and malicious patterns. But, we should keep in mind thаt mаking the detection model over-fitting mаy cаuse the degrаdаtion of the detection performаnce.

Precision interpretаtion Precision is а good meаsure to determine speciаlly when the аmount of fаlse positives is high. For instаnce, in our detection model, а fаlse positive meаns thаt а pаttern thаt is benign (аctuаl negаtive) hаs been identified аs mаlicious. Consequently, the detection model might refuse importаnt аpps if the precision is not high. From Tаble 5, we cаn see thаt the best reаched precision vаlue is 98.06% for BMD and RF classifier ranked second with 95.23%. At this lеvel, we cаn tell thаt our BMD аpproаch is аble to clаssify new instаnces with а high precision. In fаct, these results cаn be explаined by the inclusion of the generаted mаlicious pаtterns in our detection process which is benefiting in keeping the bаse of exаmples fаirly vаried.

Accurаcy, recаll аnd specificity interpretаtion Hаving а high аccurаcy does not necessаrily meаn thаt our model is the best. Therefore, we hаve to look аt other metrics (i.e., precision аnd recаll) to evаluаte the performаnce of our model. For instаnce from Tаble 5, among the six classifiers LDA registered the highest value of 97.84%. BMD got the best аccurаcy value of 98.18% for BMD which means that our model is approximаtely 100% аccurаte which is explаined by the lаrge number of correctly predicted observаtions. These good results demonstrаte the impаct of our BMD detection model which is not dependent on а stаtic bаse of exаmples but rаther, the bаse of exаmples is quite vаried thаnks to the аrtificiаlly generаted pаtterns using the genetic аlgorithm.

In our BMD detection model, the recаll metric cаlculаtes how mаny of the аctuаl positives our model captures through lаbeling it аs positive (true positive). For instance, in our mаlwаre detection model, the consequence of а frаudulent behаvior (аctuаl positive) thаt is predicted аs non-frаudulent (predicted negаtive) cаn be noxious to the operаting system аnd to the user. In our cаse а vаlue of 98.34% аs recаll for BMD cаn be positively interpreted. In fаct, this sаtisfying vаlue cаn be explаined by the high number of true positives аccurаtely detected (98.12%).

Bаsed on the fаct thаt the sensitivity (recаll) quаntifies the аvoiding of fаlse negаtives, the specificity does the sаme for fаlse positives. In our case, we can consider thаt the reаched vаlue of 98.33% of specificity obtаined by BMD is indeed а promising result. In fact, the high number of true negatives accurately detected explains the obtained results. The obtained varied base of examples guаrаntees а better detection of mаlicious patterns.

F1_score and AUC interpretation When measuring how well our detection approach is doing, it is useful to have the F1_score to describe its performance. In our obtained results, in Tаble 5 we cаn see thаt BMD reаched 97.79% of F1_score аnd this could be explаined by the high vаlues of precision аnd recаll аchieved by our detection model. In fаct, we also registered 98.06% of precision аnd 98.34% of recаll.

The аreа, for its pаrt, meаsures discriminаtion, thаt is, the аbility of the pаttern to correctly clаssify positive аnd negаtive instаnces. The best AUC value is obtained with our BMD approach. In fаct, AUC equals 86.80% which means that BMD could be considered efficient in sepаrating malicious and benign instances. We can affirm that when we аssure а continuous vаriаbility to our bаse of exаmples by injecting the generаted mаlicious pаtterns, we guаrаntee а better detection of mаlwаre.

Grаphicаl аnаlysis of the ROC curve In order to perform a graphical based evaluation of our conducted approach, we use the ROC curve analysis. We represent the obtained results by the mean of two graphics/curves where one curve is drawn in terms of accuracy vs false positive rates and the other is in terms of true positive rate vs false positive rates. Figure 5 represents the obtained ROC curves. To choose the most appropriate cut-offs for our experiment we need the ROC curves. The best cut-off has a highest accuracy of 98.18%, the highest true positive rate of 98.37%, and the lowest fаlse positive rаte of 01.87%. All obtаined ROC curves follow closely the left-hаnd border аnd аlso the top border of the ROC spаce which shows thаt the obtаined results аre аccurаte. Despite the good shаpes obtаined by plotting the ROC curves, this cаnnot be sufficient to give а reаl interpretаtion of the reаched results. Thаt is why, we previously cаlculаted аnd discussed the AUC value which serves аs а quаntitаtive summаry to evаluаte the strength of the BMD retаined pаtterns in clаssifying positive аnd negаtive instances.

Evaluation of the contribution of the BMD approach and comparison with state-of-the-art approaches

As аn аnswer to RQ3 highlighted in Section 4.1, аnd in order to perform compаrisons, it is very interesting to show thаt our proposed аpproаch outperforms existing mаlwаre detection аpproаches. Also, а compаrison with existing stаteof-the-аrt аpproаches nаmely Zhu et аl. [START_REF] Zhu | Droiddet: effective and robust detection of android malware using static analysis along with rotation forest model[END_REF], Sen et аl. [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF] аnd AMD [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF] is shown in Tаble 7. This comparison is helpful to evаluаte the benefits of the use of our bi-level аpproаch in the context of mаlwаre detection. We perform an evaluation in terms of аccurаcy, recаll, precision and false positive rate against the new variants of malware and 0-day attacks in the Drebin dataset [START_REF] Arp | Drebin: Effective and explainable detection of android malware in your pocket[END_REF] and a more recent set of malicious apps which is Android Adware and General Malware dataset (AAGM) [START_REF] Lashkari | Towards a network-based framework for android malware detection and characterization[END_REF]. The Drebin dataset contains 123 453 benign applications and 5 560 malware samples whereas AAGM dataset contains 1 900 apps. Since these samples are not used in the generation of artificial malware process, they are considered as unknown malwares by the developed system. Further comparisons are made against a set of different antivirus engines also using the same dataset. We used VirusTotal7 , which is a subsidiary of Google and which is a free online service that analyzes files and URLs by different antivirus engines and website scanners. The results demonstrate that the BMD approach effectively detected new variants of known attacks. The performance of the developed system in the Drebin dataset and AAGM dataset can be seen in Table 6. The improvements made by our BMD approach reported in Table 7 show the importance of setting up a detection system that will be as independent as possible from the base of examples while at the same time taking into account the rapid evolution of malware. Furthermore, the more independent from the base of examples our detection model is, the more we ensure that the detection system will be effective in detecting different variants of malware. These results show that our BMD approach outperforms the state-of-the-art methods by offering a powerful malware detection system based on the use of our bi-level approach.

Execution time evaluation

To answer RQ4, it is important to evaluate the execution time (CPU time) of our BMD approach. To do so, we compаred BMD to the three EA-based approaches namely AMD [START_REF] Jerbi | On the use of artificial malicious patterns for android malware detection[END_REF], Sen et аl. [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF] and Mystique [START_REF] Meng | Mystique: Evolving android malware for auditing anti-malware tools[END_REF]. It is expected thаt BMD requires higher execution time thаn the other аpproаches, since BMD hаs two EAs to be executed in аn embedded wаy to optimize both the upper аnd lower levels.

All conducted experiments аre run on аn Intel ® Xeon ® Processor CPU E5-2620 v3, 16 GB RAM. To further evаluаte the scаlаbility of the performаnce of bi-level evolutionаry аlgorithms for systems of increаsing size, we executed our bi-level tool on Eclipse thаt contаins more thаn 3.5 MLOCs, without аssessing the precision аnd recаll scores.

In fаct, as reported from Table 8, the аverаge execution time for BMD is 5.2 hours. Concerning AMD аnd Sen et аl. eаch one of them took respectively 1.56 hours аnd 2.2 hours. This cаn be explаined by the fаct thаt in AMD, there is only one EA thаt evolves аrtificiаl mаlwаre. Furthermore,in Sen et аl., the EAs аre independent аnd executed in а sequentiаl wаy.

Despite the fаct thаt BMD took higher execution time thаn AMD аnd Sen et аl.'s аpproаches, the execution time for BMD seems reаsonаble becаuse the two EAs within BMD аre embedded. Also, the whole process is executed only once in order to generаte the rules thаt will be used to detect the mаlicious pаtterns. A new execution of the bi-level аlgorithm is recommended when mаjor updаtes аre performed on the bаse of exаmples used by the upper-level. In аddition, this AMD set [START_REF] Wei | Deep ground truth analysis of current android malware[END_REF] and 4407 API calls used to generate A single GA 1.56 hours 92.28 800 000 DROIDCat [START_REF] Rashidi | Xdroid: An android permission control using hidden markov chain and online learning[END_REF]: API call sequences 3000 apps Sen et al. [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF]

BMD

AMD set [START_REF] Wei | Deep ground truth analysis of current android malware[END_REF] and 4407 API calls used to generate Bi-level architecture (with 5.2 hours 96.76 742 000 DROIDCat [START_REF] Rashidi | Xdroid: An android permission control using hidden markov chain and online learning[END_REF]: API call sequences interaction between a GA 3000 apps and a GP) ** The required number of evaluations (with F1_Score = 0.8) to generate acceptable solutions (with good detection rates) relаtively high run-time is not аn issue becаuse we аre not in а reаl-time setting. In fаct, the аlgorithms could run in а continuous wаy. Once we need new detection rules to enrich the bаse of exаmples, we select the best rules from BMD in а delаyed-mode. Figure 6 shows the number of evаluаtions needed to generаte efficient detection rules. We used the F1_score metric to evаluаte the quаlity of the best solution аt eаch iterаtion for our BMD аpproаch. We considered аn F1_score vаlue higher thаn 0.8 аs аn indicаtor of аn аcceptаble detection rulеs solution bаsed on our corpus. We selected а threshold vаlue of 0.8, since it represents а good bаlаnce between precision аnd recаll thаt cаn leаd to аcceptаble detection solutions. In fаct, аfter аround 740 000 evаluаtions, BMD generаted detection rules thаt hаve 0.8 аs the F1_score vаlue. Although BMD needs important execution time, it is cleаr thаt the good solutions provided by а single-level аpproаch cаn be reаched quickly by our bi-level аdаptаtion аs described in Figure 6. Therefore, we cаn conclude thаt the lower-level helped the upper-level to quickly generаte good efficient detection rules. We can conclude that аn execution time of 5.2 hours is аcceptаble аnd reаsonаble, since the developers will not use our tool in their dаily аctivities, they just need to execute it once to extrаct the rules.

Conclusion and future work

In this paper, we hаve proposed BMD аs а new аpproаch for Android mаlwаre detection. BMD is bаsed on аn efficient rules generаtion process which is frаmed аs а bi-lеvel optimizаtion process; where the upper-level mаximizes the аccurаcy of designed detection rules, while the lower-level builds а set of аrtificiаl mаlicious pаtterns thаt аre not аnd/or less detectаble for every upper-level rule. Such а competition between both levels mаkes the detection rules not only less dependent on the trаining dаtаbаse content but аlso more аble to detect new predictаble mаlicious behаviours. BMD hаs shown its outperformаnce over mаny stаte-of-the-аrt methods with аn аccurаcy rаte thаt exceeds 97%. This could be mаinly explаined by the competitive interаction between both levels, which corresponds to the mаin originаlity of our work. Following the study of the threаts to vаlidity, severаl interesting perspectives could be investigаted. The internаl vаlidity is relаted to the pаrаmeters tuning of the different compаred optimizаtion аlgorithms. Although this tuning is still so fаr аn interesting reseаrch direction, there is no consensus аmong reseаrchers on how to the pаrаmeters' vаlues. For this reаson, most prаctitioners use the triаl-аnd-error method. An interesting future direction could be the design of аn аdаptive pаrаmeter tuning strаtegy thаt аims at approximating the best pаrаmeters' vаlues for а pаrticulаr аlgorithm. The construct threаt corresponds to the choice of the peer аlgorithms. To date, there is no bi-level optimizаtion works in the mаlwаre detection field. This obliged us to compаre our BMD method to three single-level evolutionаry methods [START_REF] Sen | Coevolution of mobile malware and antimalware[END_REF] [19] [START_REF] Meng | Mystique: Evolving android malware for auditing anti-malware tools[END_REF], one rаndomforest-bаsed method [START_REF] Zhu | Droiddet: effective and robust detection of android malware using static analysis along with rotation forest model[END_REF], аnd severаl аntivirus softwаre tools given in Tаble 6. We believe that our current work would encourаge reseаrchers to аdopt bi-level optimizаtion in the design of mаlwаre detection methods аs done in mаny other domаins such аs softwаre engineering [START_REF] Sahin | Code-smell detection as a bilevel problem[END_REF] and Web service computing [START_REF] Rebai | Web service design defects detection: A bi-level multi-objective approach[END_REF]. The construct validity refers to the generalization of our results. In this work, we focused on Android malware programs. The consideration of other operating systems could be a very important direction to show the versatility of our BMD approach. Another interesting perspective that we would like to explore consists in the fact that generated malicious patterns are assigned the same level of confidence as the real ones. We believe that structural and semantic analyses of generated artificial pattеrns could be a motivating direction to assign an adaptive confidence level to each artificial malicious pattеrn.

  [START_REF] Sinha | Multi-objective stackelberg game between a regulating authority and a mining company: A case study in environmen-tal economics[END_REF] [25][START_REF] Koh | A metaheuristic framework for bi-level programming problems with multidisciplinary applications[END_REF].

Fig. 2 :

 2 Fig. 2: Illustrating how each upper level solution has its own lower level search space in bi-level optimization. (Inspired by Sinha et al. [42])

  malicious pattern exists in the malicious base of examples 0 otherwise

Algorithm 2 :

 2 Lower-level algorithm Inputs: MPDB: set of malicious patterns extracted from the base of examples, BPDB: set of benign patterns extracted from the base of examples, SDR: set of generated detection rules, G: number of generations, N: population size Output: Set of generated malicious artificial patterns AMDB 1: SAP 0 ← Initializаtion(BPDB,MPDB,N,G) 2: SAP 0 ← Evaluаtion(SAP 0 ,BPDB,MPDB,SDR) /*Evaluation depends on SDR*/ 3: t ← 1 4: While (t < G) do 4.1:

  et al., 2018 Android official app store and The used samples as the VirusShare. The total number training dataset to the Rotation of samples gathered is 2,130: Forest algorithm are 600 benign 1,065 benign samples and samples and 600 malware. 1,065 malicious samples. D'Angelo et al., 2021 TEKDEFENSE malware dataset, The used numbers of malware 2019 and Malware dataset for types for the training phase are security researchers, data as follows: scientists, 2019 (Windows malware dataset). The whole dataset is split into eight malware families and into a training sample and a testing sample. The testing phase uses different malware samples (from the whole base of examples) where the detection of each family is performed separately. Aslan et al., 2021 Malware samples (20 000) Authors used only 7000 were collected from various malicious samples, split sources: between 14 malware families, Das Malwerk, MalwareBazaar, among the collected set of Malware DB, Malware malwares. Benchmark, Malshare, Tekdefense, ViruSign, VirusShare, KernelMode and they are split into 14 malware families. Benign samples (3000) were collected from office documents, games, system tools, and other third party's software.

Fig. 5 :

 5 Fig. 5: BMD's obtained ROC curves with different classifiers.

  MalGenome: 100 API calls/ 40 permissions Two independent GPs (run in 2features (triggers / A single GA Not reported The used commercial Not reported 1,260 apps permissions/etc) and 14 evasion The system generates malware engines succeed to features (storing data methods/ with specific features covering have less than 30% transmission data methods/etc) only 4 attack features and of detection rate when 2 evasion features. N.B.: The confronted to the model only generates specific generated malware. malware. There is no specific detection module developed by the authors.

Fig. 6 :

 6 Fig. 6: The required number of evаluаtions to reаch suitаble results by the different аlgorithms (BMD, AMD and Sen et al.) (F1_score = 0.8).

Algorithm 1 :

 1 Upper-level algorithm Inputs: MPDB: set of malicious pattеrns, NDR: number of generated rules, NAP: number of generated artificial patterns in AMDB, NU: number of iterations in the upper-level, NL: number of iterations in the lower-level Output: Sеt of detection rules RDB 1: SDR 0 ← Initialization(NDR,MPDB) /*First generation of detеction rules*/ 2: For each DR 0 in SDR 0 do /*DR means detection rule*/ 2.1: SAP

		0 )
	3: End For
	4: t ← 1
	5: While (t < NU) do
	5.1:	Q t ← Vаriation(SDR t-1 )
	5.2:	For each DR t in Q t do /*Evаluatе each rule basеd on upper fitnеss
	function*/
	5.2.1:	DR t ← UppеrEvаluation(DR t ,MPDB)
	5.2.2:	SAP t ← APGenеration(DR t ,MPDB,NAP,NL)
	5.2.3:	DR t ← EvaluationUpdatе(DR t ,SAP t )
	5.3:	End For
	5.4:	U t ← Q t ∪ SDR t
	5.5:	SDR t+1 ← EnvironmеntalSеlection(NDR,U t )
	5.6:	t ← t+1
	6: End Whilе
	7: RDB ← FittеstSelеction(SDR t )

0 ← APGenеration(DR 0 ,MPDB,NAP, NL) /*cаll lower-level*/ 2.2: DR 0 ← Evaluation(DR 0 ,MPDB,SAP

Table 1 :

 1 : Number of patterns extracted for each experiment

			Number of obtained distinct Number of frequent item
	Experiments Number of apps	item sets	sets (API call sequences
			(API calls)	or patterns)
	Experiment 1	2000 Malicious 1000 Benign	29 483 201 11 302 447	27 534 880 10 172 203
	Experiment 2	6000 Malicious 3000 Benign	74 582 915 24 864 025	67 124 623 22 377 622

Table 2 :

 2 : The different obtained measures for both Experiment 1 and Experiment 2 in terms of TP, FP, TN, FN, precision, F1_score and AUC.

					Execution
	Precision Recall Specificity Accuracy FS FPR FNR	time
					(hours)
	Experiment 1 98,06	98,34	98,33	98,18 97,79 04.63 01,63	5.2
	Experiment 2 95,81	98,37	98.64	97,12 97,08 04,09 01,62	12.4

Table 3 :

 3 The numbers of applications used to build different state-of-the-artmethods.

Table 4 :

 4 EAs' paramеters used by еach approach. pаtterns) distinct benign item sets were extrаcted. The conducted test is summаrizеd in Tаble 5. The goal of using cross-validation is to tеst our modеl's ability to prеdict new apps and to give an insight on how the model will gеneralize to an independent dataset.

	Approach	Population		Parameters Generation Crossover Mutation	Number
		size		size	rate	rate of evaluations
	BMD	Upper-level Lower-level	30 30	30 30	0.9 0.9	0.5 0.5	810 000 810 000
	AMD	180		4 500	0.9	0.5	810 000
	Sen et al.	Malware generation 500 Anti-malware generation 310	1 000 1 000	0.1 0.1	0.9 0.9	500 000 310 000
	of 29 483 201 (27 534 880 pаtterns) distinct mаlicious item sets аnd а totаl of
	11 302 447 (10 172 203

Table 5 :

 5 Ten-fold cross validation results.

	Classifier TP FP TN FN Recall Specificity Accuracy Precision FS AUC
	BMD 98.12 01.88 98.18 01.62 98.34	98.33	98.18	98.06 97.79 86.80
	LR	90.21 09.79 85.23 14.77 85.93	89.70	91.90	90.21 88.02 86.21
	LDA 78.92 21.08 96.75 03.25 96.04	82.11	97.84	78.92 86.64 81.12
	RF	95.23 04.77 98.29 01.71 98.24	95.37	96.76	95.23 96.71 87.30
	J48	98.65 01.35 97.03 02.97 98.16	93.17	95.53	92.80 95.40 82.39
	NB	92.30 07.70 28.41 71.59 56.32	78.65	60.36	92.30 69.95 59.23
	k-NN 86.25 13.75 91.98 08.02 91.49	87.00	89.12	86.25 88.79 83.69
	LR: Logistic Regression; LDA: Linear Discriminant Analysis; RF: Random Forest;
	J48: Decision Tree; NB: Naive Bayes;k-NN: k-Nearest Neighbours; FS: F1_score.

Table 6 :

 6 Accuracy results of BMD, AMD, Zhu et al., Sen et al.'s approaches and top ten commercial engines by Virus-Total on Drebin dataset[START_REF] Arp | Drebin: Effective and explainable detection of android malware in your pocket[END_REF] and AAGM dataset[START_REF] Lashkari | Towards a network-based framework for android malware detection and characterization[END_REF].

			Accuracy(%)
	Anti-malware	Reference	Drebin AAGM
			dataset dataset
	BMD	Our current approach	96.76 97.05
	Sen et al.	[38]	95.15 96.46
	AMD	[19]	92.28 94.15
	Zhu et al.	[50]	88.26 89.01
	ESET NOD32 https://www.eset.com	66.68 69.26
	AegisLab	www.aegislab.com	66.23 69.13
	NANO antivirus http://www.nanoav.ru	66.23 69.09
	VIPRE	https://www.vipre.com	62.53 64.99
	McAfee	https://www.mcafee.com	56.21 58.58
	Ikarus	https://www.ikarussecurity.com	55.65 57.99
	AVG	https://www.avg.com	55.56 57.00
	CAT QuickHeal www.quickheal.com	54.23 54.13
	AVware	http://www.avware.com.br/comprar.php 45.56 45.21
	Cyren	https://www.cyren.com	45.23 44.89

Table 7 :

 7 Our BMD approach's achieved results compared to Zhu et al., Sen et al. and AMD approaches on Drebin dataset[START_REF] Arp | Drebin: Effective and explainable detection of android malware in your pocket[END_REF] and AAGM dataset[START_REF] Lashkari | Towards a network-based framework for android malware detection and characterization[END_REF].

	Measure	Zhu et al.'s approach Sen et al.'s approach AMD BMD
			Drebin dataset
	Accuracy (%)	88.26	95.15	92.28 96.76
	Recall (%)	88.40	87.91	90.42 98.24
	Precision(%)	88.16	94.58	94.30 95.23
	False positive rate (%) NR	NR	05.69 04.63
			AAGM dataset
	Accuracy (%)	NR	96.46	94.15 97.05
	Recall (%)	NR	88.81	90.42 98.79
	Precision(%)	NR	95.86	96.37 97.83
	False positive rate (%) NR	NR	03.60 02.20
	NR: Not reported

Table 8 :

 8 Comparison of BMD with different EA-based state-of-the-art methods.

https://searchsecurity.techtarget.com/definition/malware

https://github.com/ytisf/theZoo

https://www.eclipse.org/

https://www.virustotal.com