Ramtine Tofighi-Shirazi
email: ramtine.tofighishirazi@thalesgroup.com

Irina Măriuca Asăvoae

Philippe Elbaz-Vincent
email: philippe.elbaz-vincent@univ-grenoble-alpes.fr

Fine-Grained Static Detection of Obfuscation Transforms Using Ensemble-Learning and Semantic Reasoning

Keywords: machine learning, ensemble learning, deobfuscation, obfuscation, reverse engineering, symbolic execution

The ability to efficiently detect the software protections used is at a prime to facilitate the selection and application of adequate deobfuscation techniques. We present a novel approach that combines semantic reasoning techniques with ensemble learning classification for the purpose of providing a static detection framework for obfuscation transformations. By contrast to existing work, we provide a methodology that can detect multiple layers of obfuscation, without depending on knowledge of the underlying functionality of the training-set used. We also extend our work to detect constructions of obfuscation transformations, thus providing a fine-grained methodology. To that end, we provide several studies for the best practices of the use of machine learning techniques for a scalable and efficient model. According to our experimental results and evaluations on obfuscators such as Tigress and OLLVM, our models have up to 91% accuracy on state-of-the-art obfuscation transformations. Our overall accuracies for their constructions are up to 100%.

INTRODUCTION

Code obfuscation is a widely used software protection technique to mitigate the risks of reverse-engineering. It aims at protecting intellectual property by hiding the logic and data of a code. The use of code obfuscation transformations depends on the sensitivity of the application. Its applications are mainly digital right management, software licensing code or white-box cryptography, among others. Malicious codes also use extensively code obfuscation to hide their intent, evade detection and hinder analyses.

In order to properly evaluate obfuscation transformations, or to efficiently analyze malwares, many deobfuscation techniques have emerged. Their goal is to remove the protection layers applied on the code. The deobfuscation process can be seen as different strategies such as reverting, simplifying, or gathering information about the obfuscated code. In this paper we mainly focus on information gathering, particularly the static detection of obfuscation transformations. We also study an extension to the transformations constructions, namely the different methods employed for a specific obfuscation transformation to be achieved (e.g. dispatch-methods for control-flow flattening or code virtualization). This approach is previously known as metadata recovery attacks [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF].

State-of-the-art deobfuscation techniques are often specific to obfuscation transformations. For example, the work of Udupa et al. [START_REF] Sharath | Deobfuscation: Reverse engineering obfuscated code[END_REF] targets control-flow transformations, whereas others [START_REF] Bardin | Backward-bounded DSE: targeting infeasibility questions on obfuscated codes[END_REF][START_REF] Ming | LOOP: logic-oriented opaque predicate detection in obfuscated binary code[END_REF][START_REF] Dalla Preda | Opaque predicates detection by abstract interpretation[END_REF][START_REF] Tofighi-Shirazi | DoSE: Deobfuscation based on Semantic Equivalence[END_REF] aim at removing opaque predicates. Generic deobfuscation techniques, however, make no assumption about the applied protections [START_REF] Salwan | Symbolic deobfuscation: From virtualized code back to the original[END_REF][START_REF] Yadegari | A generic approach to automatic deobfuscation of executable code[END_REF]. These techniques are based on dynamic symbolic execution and may lack in code coverage and scalability.

Though obfuscation transformations are semantic-preserving, they may introduce side effects to the code [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF]. Each transformations has its own construction methodology, thus specific patterns. Recent works try to tackle the detection of software protections using machine learning or deep learning techniques. Ugarte-Pedrero et al. [START_REF] Ugarte-Pedrero | Semi-supervised learning for packed executable detection[END_REF] propose a semi-supervised learning approach in order to classify packed and unpacked binaries. Sun et al. [START_REF] Sun | Pattern recognition techniques for the classification of malware packers[END_REF], and more recently Biondi et al. [START_REF] Biondi | Effective, efficient, and robust packing detection and classification[END_REF], aim at detecting and identifying packers using machine learning techniques. Tofighi-Shirazi et al. [START_REF] Tofighi-Shirazi | Defeating Opaque Predicates Statically through Machine Learning and Binary Analysis[END_REF] propose a deobfuscation methodology for invariant opaque predicates based on machine learning techniques.

From the variety of obfuscation techniques, as well as deobfuscation methodologies, the ability to efficiently detect the software protections used is at a prime. To that end, the recent work of Salem et al. [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF] focuses on the detection of obfuscation transformations. Their goal is to facilitate the selection and application of adequate deobfuscation techniques. To the best of our knowledge, their work is the first to tackle code obfuscation detection using machine learning. However, their methodology is also prone to some limitations as explained next.

Current limitations. Existing detection technique for code obfuscation [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF] based on machine learning techniques comes with the following limitations:

(1) Code dependency: machine learning and syntax-reasoning used for the detection of obfuscation transformations can lead to code dependency. Namely, the trained model becomes dependent to the analyzed code used in the training set, thus lowering its accuracy. (2) Multi-class problem: the methodology used relies on multiclass problems for classification. Namely, they consider that one binary cannot be obfuscated with more than one obfuscation transformation. However, transformations can be combined, thus the necessity to be able to detect the several applied layers. (3) Granularity: the detection technique has a high-level of granularity. They may detect an obfuscation transformation, but they do not focus on their constructions. The latter is of importance in order to decide which analysis to apply on obfuscated code. Many transformations constructions are made to prevent existing deobfuscation techniques. Motivation. When applying obfuscation transformations for software protections, stealth is sometimes not desired. Many applications aim for dissuasion in order to prevent reverse-engineering. In any case, the goal of our methodology is to provide a static and automated framework to help reverse-engineers. By detecting obfuscation transformations, and more specifically their constructions, an analyst will gain an important amount of time. The selection of the deobfuscation process to apply requires such knowledge beforehand. A motivating example is illustrated in Figure 1. It represents the obfuscated control-flow graph of a quick-sort function. Based on the previously introduced problems, our goal is to answer the following questions:

• Complexity: can we detect all applied layers of obfuscation transformation? • Granularity: can we detect the constructions of applied obfuscation transformations? • Efficiency: can we create accurate and generic enough models for unknown data? As previously discussed in [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF], metadata recovery attacks are usually manual tasks, therefore a potential bottleneck in the reverse engineering process. Our methodology, which could be plugged-in a disassembler framework, provides all applied transformation and construction and allows reverse-engineers to setup automated deobfuscation strategies. As an example, several opaque predicates constructions prevent SMT-solver based deobfuscation techniques [START_REF] Xu | Manufacturing resilient bi-opaque predicates against symbolic execution[END_REF]. Other recent works prevent the application of dynamic symbolic execution techniques [START_REF] Banescu | Predicting the resilience of obfuscated code against symbolic execution attacks via machine learning[END_REF][START_REF] Ollivier | How to kill symbolic deobfuscation for free; or unleashing the potential of path-oriented protections[END_REF]. Thus, knowing which transformations and constructions analysts are facing may prevent using unadapted techniques for the deobfuscation process.

Contributions. In order to face the above limitations and answer our motivating questions, we bring the following contributions:

(1) A novel methodology that combines semantic reasoning with ensemble learning techniques applied for a multi-label and multi-output ensemble model. We believe that semantic reasoning will prevent our model from code dependency limitations, and provides us with the ability to detect several combined layers of obfuscation transformations.

(2) An extension of our methodology for a fine-grained detection. Based on our main approach, a second classification model is used for the detection of the transformations constructions, based on a multi-class classification model (i.e. one unique label per instances). (3) Several studies and experiments that justify the constructions of our methodology. We compare different machine learning approaches and techniques in order to build efficient and scalable models. We also evaluate our methodology against state-of-the-art obfuscators such as Tigress [START_REF] Collberg | The Tigress C Diversifier/Obfuscator[END_REF] and Obfuscator-LLVM [START_REF] Junod | Obfuscator-LLVM -software protection for the masses[END_REF] (i.e. OLLVM). Our paper is organized as follows. Section 2 presents the background information about code obfuscation and targeted transformations. We also introduce related work, as well as notions of supervised machine learning. Section 3 describes our methodology which combines semantic reasoning with ensemble learning. Section 4 contains our studies and experiments towards an efficient implementation of our methodology. Section 5 illustrates our evaluations on state-of-the-art and publicly available obfuscators. Section 6 briefly discuss the application of our methodology to setup deobfuscation strategies. Then, we discuss our design limitations in Section 7, as well as our perspectives in Section 8. Finally, Section 9 presents our conclusions.

Limitations. While our results illustrate the interest of the methodology, evaluating the exact gain of the different components of the approach and experimental comparison to related contributions are left as future work.

BACKGROUND

We briefly present code obfuscation and some of the employed transformations. Then we introduce several notions related to supervised machine learning and metadata recovery attacks introduced in [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF].

Code obfuscation

Collberg et al. [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF] define code obfuscation as follows: Let P T -→ P ′ be a transformation T of a source program P into a target program P ′ . We call P T -→ P ′ an obfuscating transformation if P and P ′ have the same observable behavior, P ′ is harder to analyze than P, and P ′ is no more than polynomially slower than P. Consequently, the following conditions must be fulfilled for an obfuscating transformation : if P fails to terminate, or terminates with an error condition, then P ′ may or may not terminate; otherwise, P ′ must terminate and produce the same output as P.

Obfuscation transformations

An obfuscation transformation T can be classified into different categories such as data obfuscation, static code obfuscation, and dynamic code obfuscation. Early techniques are given by Collberg et al. [START_REF] Collberg | Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection[END_REF][START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF]. A classification of all these obfuscations, as well as known deobfuscation methods has been provided by S. Schrittwieser et al. [START_REF] Schrittwieser | Protecting software through obfuscation: Can it keep pace with progress in code analysis?[END_REF]. The following paragraphs present a nonexhaustive list of obfuscation transformations.

Encodings.

Static data within binaries, such as strings or constant values, contain useful information for an analyst. Encoding, as an obfuscation transformation T , converts data to a different representation. To this end, special encoding functions are employed to mitigate the need of storing the static data in clear text within the binary. During execution, the inverse function is used to decode the obfuscated data. To prevent pattern-matching attacks, the obfuscated representation must be parameterized in order to have a family of representations. In other words, each representation renders different-looking obfuscated variables. However, they are all based on the same obfuscating algorithm.

2.2.2 Instructions substitutions. Each program behavior can be implemented in multiple ways [START_REF] Warren | Hacker's Delight[END_REF]. In other words, instructions or sequences of instructions can be replaced with syntactically different, yet semantically equivalent code. As an example, complex instruction substitution include the replacement of call instructions with a combination of push and ret instructions [START_REF] Lakhotia | Context-sensitive analysis without calling-context[END_REF]. De Sutter et al [START_REF] Sutter | Instruction set limitation in support of software diversity[END_REF] replaced infrequently used opcodes with blocks of more frequently used instructions in their work. This transformation reduced the total number of different opcodes used in the code and normalizes their frequency. [START_REF] Collberg | Manufacturing cheap, resilient, and stealthy opaque constructs[END_REF] represents an obfuscated predicate with its outcome known at obfuscation time, but difficult to determine for a deobfuscator. Opaque predicates are used to make static reverse-engineering more complex. They introduce an analysis problem which is difficult to solve without running the program. There are two types of invariant opaque predicates and the two-ways opaque predicates. Collberg et al. defined these predicates by, respectively, P T , P F and P ? opaque predicates. Several works use two-ways opaque predicates constructs, either referred to as range-dividers [START_REF] Banescu | Code obfuscation against symbolic execution attacks[END_REF], or as correlated opaque predicates [START_REF] Ming | LOOP: logic-oriented opaque predicate detection in obfuscated binary code[END_REF][START_REF] Xu | Generalized dynamic opaque predicates: A new control flow obfuscation method[END_REF]. Moreover, regardless of their output, e.g. their type, there exists many different kinds of construction that produce the opaque predicates.

Opaque predicates. An opaque predicate

2.2.4

Control-flow flattening. This obfuscation transformation aims at obscuring links between basic-blocks by flattening the controlflow. Wang et al. [START_REF] Wang | Protection of software-based survivability mechanisms[END_REF] describe as chenxification this transformation, which puts the basic-blocks of a program into a large switchstatement. A dispatcher decides then where to jump next. Controlflow flattening using a central dispatcher is also described by Chow et al. [START_REF] Chow | An approach to the obfuscation of control-flow of sequential computer programs[END_REF]. A similar concept by Lynn and Debray [START_REF] Linn | Obfuscation of executable code to improve resistance to static disassembly[END_REF] uses what is called branch functions, which directs the control-flow to the actual target based on a call table. Further control-flow obfuscation constructions are described in [START_REF] Cappaert | A general model for hiding control flow[END_REF][START_REF] Coppens | Feedback-driven binary code diversification[END_REF][START_REF] Lazlo | Obfuscating c++ programs via control flow flattening[END_REF][START_REF] Popov | Binary obfuscation using signals[END_REF][START_REF] Schrittwieser | Code obfuscation against static and dynamic reverse engineering[END_REF].

Code virtualization.

Code virtualization describes the concept of converting a program functionality into byte-code for a custom virtual machine interpreter that is bundled with the program [START_REF] Ghosh | A secure and robust approach to software tamper resistance[END_REF][START_REF] Samuel | Subvirt: Implementing malware with virtual machines[END_REF]. This obfuscation transformation can also be combined with polymorphism by implementing custom virtual machine interpreters and payloads for each instance of the program [START_REF] Anckaert | Proteus: virtualization for diversified tamper-resistance[END_REF]. Other work [START_REF] Vrba | Program obfuscation by strong cryptography[END_REF] proposes the combination of fine-granular encryption and code virtualization to hide the virtual machine code from analysis. Collberg et al. [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF] describe a variant of this concept under the term table interpretation. A similar concept by Monden et al. [START_REF] Monden | A framework for obfuscated interpretation[END_REF] uses a finite state machine-based interpreter to dynamically map between instructions and their semantics. Thus, code virtualization proposes many constructions, as for previous transformations.

Dynamic code modification.

In this technique, similar functions are obfuscated by providing a general template in memory that is patched right before its execution [START_REF] Collberg | A taxonomy of obfuscating transformations[END_REF]. Static analysis techniques fail to analyze the program, as its functionality is available at runtime only. Other concepts of dynamic code modification [START_REF] Kanzaki | Exploiting self-modification mechanism for program protection[END_REF][START_REF] Madou | Software protection through dynamic code mutation[END_REF] implement the idea of correcting intentionally erroneous code at runtime, right before execution.

Our goal in this paper is to evaluate our methodology against the previously presented obfuscation transformations. Beforehand, the next section will recall some notions about supervised machine learning techniques for classification.

Supervised machine learning

Supervised machine learning [START_REF] Hastie | The elements of statistical learning: data mining, inference, and prediction[END_REF][START_REF] Kotsiantis | Supervised machine learning: A review of classification techniques[END_REF] provides a dedicated methodology to produce general hypotheses from external supplied instances via a given algorithm. From these hypotheses, predictions about future instances are possible. The aim of a supervised machine learning is to build a classification model which will be used to assign labels to unknown instances. In other words, let X be an input (i.e. instance) and Y the output (i.e. predicted label). A supervised machine learning algorithm will be used to learn the mapping function f such that Y = f (X ). The goal is to approximate f such that for any new instance X we can predict its label Y . In our case the inputs are represented by n-dimensional vectors of numerical features for which the extraction is described in the following paragraph. The traditional single-label classification associates an instance X with a unique label Y ′ from a previously known finite set of labels L. This approach is then considered a binary classification problem if |L| = 2, or a multi-class classification problem if |L| > 2. Other approaches exist, such as the multi-label classification. In this case, an instance X is associated with a set of labels S Y ′ ⊂ L. Moreover, if the model is based on a mapping function f that can return a set of multiple labels, we have a multi-output classification model. In our work, we use all these classification problems as described in Section 3.

Feature extraction.

Instances of a machine learning model are usually derived from what is called raw data, i.e. the data samples we want to classify or predict. These data samples cannot be directly given to a classification model and need to be processed beforehand. This processing step is called feature extraction [START_REF] Guyon | Feature Extraction: Foundations and Applications[END_REF] and consists in combining the raw data variables into numerical features. It allows to effectively reduce the amount of data that must be processed, while accurately describing the original dataset of raw data. In our case, raw data are text documents (e.g. disassembly code, symbolic execution state, etc.). Therefore, one practical use of feature extraction consists in extracting the words (i.e. the features) and classify them by frequency of use (i.e. weights). Different approaches exist for understanding what a word is and to compute its weight. In this paper we use the bag of words approach [START_REF] Christopher | Introduction to Information Retrieval[END_REF], which identifies terms with words using term frequency, in order to extract the features for our model. It is an efficient and simple approach which fits adequately our semantic reasoning approach.

Classification algorithms.

The choice of which specific learning algorithm to use is a critical step. Many classification algorithms exist [START_REF] James | Classification Algorithms[END_REF], each of them having different mapping functions. Classification is a common application of machine learning. As such, there are many metrics that can be used to measure and evaluate our models. In order to compute these metrics, k-Fold Cross-Validation [START_REF] Kohavi | A study of cross-validation and bootstrap for accuracy estimation and model selection[END_REF] is a frequently used technique. The definition of k-fold cross-validation consists in reserving a particular set of samples on which the model does not train. The limited set of samples allows to estimate how the model is expected to perform on data not used during the training phase. The parameter k refers to the number of groups that a given dataset of samples is split into, in order to calculate the mean of our models accuracy as well as the F1-score based on the value of k. While the accuracy of the model represents the ratio of correctly predicted labels to the total of labels, F1-score takes both false positives and negatives into account. In our experimentations and evaluations, the accuracies and F1-scores are calculated using k-fold cross-validation, with k = 10 for a better generalization of our model to unknown instances.

Another application of cross-validation, introduced in [53], consists in a functionality-based folding. In other words, the learning set and training set are divided based on the functionality of the samples from which the raw data are generated. The goal of such evaluation methodology is to measure if the model is dependent to the underlying code functionality, independently of the obfuscation transformation applied. The next paragraph introduce furthermore the work of Salem et al. [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF], known as metadata recovery attack.

Related work: Metadata recovery attack

Salem et al. [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF] introduce the use of machine learning techniques to evaluate the stealth of obfuscation transformations throughout their detection (known as metadata recovery attack). Their primary hypothesis is that machine learning techniques are capable of implementing these attacks by classifying obfuscated programs according to the transformations applied. Their experiments are based on two learning algorithms, namely Naive Bayes [START_REF] Friedman | Bayesian network classifiers[END_REF] and Decision trees [START_REF] Rokach | Data Mining With Decision Trees: Theory and Applications[END_REF]. Their raw data are based on static disassembly or dynamic instruction traces, either stripped or not. Thus, we refer to such raw data generation as syntax-reasoning. The evaluation of their models is made with two classification techniques. The first one is a traditional k-fold cross validation, with k = 10. The second one is more fine-tuned since it discriminates the training and test dataset on program functionality. In other words, the test dataset is excluded of any raw data that have been used in the training dataset, based on the functionality they implement. Such process is also repeated 10 times, to calculate the average accuracy for each fold. Their results are promising, showing up to 100% of accuracy for obfuscation transformations detection with decision trees, on dynamic traces. However, these results are obtained with the conventional cross-validation, whereas the second classification mode provides lower results (up to 61% of accuracy) with decision trees. This indicates that their model is dependent of the functionality implemented in their raw data. Moreover, their work is not implemented yet to cover several layers of obfuscation transformations, as it can be the case in most obfuscated programs. In our work, we also used both cross-validation approach to compare our results with their work. This gives an brief idea about the advantages of semantic reasoning over syntax-based approaches.

Our goal in this paper is to combine semantic reasoning and more advanced machine learning classification techniques in order to improve the accuracy. We want to have a static analysis tool, based on symbolic execution, in order to have a model that does not depend on the functionality of the program. The models are used to detect several layers of obfuscation transformations, thus having a multi-label and multi-output classification problem. Then, we extend our detection not only to the obfuscation transformations but also to their constructions. To this end, in the next section, we present our approach and methodology.

METHODOLOGY

In this section we present our methodology composed of several steps, as illustrated in Figure 2. I. In order to create our models, we generate obfuscated as well as clean samples. This generation is done using publicly available obfuscators, specifically Tigress and OLLVM. II. We employ then semantic reasoning via symbolic execution 1 to extract our raw data, from the generated samples. This step is presented in Section 3.1. III. We create two different datasets for two different kinds of classifications. Using labeled raw data, we build our datasets for the detection of obfuscation transforms, including several combinations. Another dataset is made for the detection of specific constructions related to the transformations. These steps are introduced in Section 3.4. IV. The previous datasets are used to train our models. In order to select the most relevant approach and learning algorithms, several studies and experiments are provided in Section 4. V. The final step consists in their evaluation and their application on unknown instances, as presented in Section 5.

Semantic reasoning

Static symbolic execution is a binary analysis technique that captures the semantics (i.e. logic) of a program. An interpreter is used to trace the program, while assuming symbolic values for inputs rather than obtaining concrete values as a normal execution would. A symbolic state S is built and consists in a set of symbolic expressions S for each variables (i.e. registers, memory, flags, etc.). Several techniques exist for symbolic execution [START_REF] Baldoni | A survey of symbolic execution techniques[END_REF]. In order to avoid path explosions in static symbolic execution, we use an intra-procedural and bloc-centric approach, as summarized next.

3.1.1 Bloc-centric intra-procedural symbolic execution. We use semantic reasoning for the generation of our raw data. The symbolic representation helps to efficiently detect obfuscation transformations and constructions. Raw data refers to the representation of data samples, containing noisy features, which need to be processed in order to extract the informative characteristics to train the models. For the detection of obfuscation transformations, we choose to work on disassembled functions of binary code. On these functions, we apply static symbolic execution to retrieve their semantic representation. In our work we use disassembled functions to collect the symbolic expressions from the code, as illustrated in Algorithm 1. First, the semantic reasoning part of our methodology is given a disassembled function F as input. For the learning phase of our methodology, F needs to be labeled. In other words, we need to know which transformations are applied in order to properly train our model. However, in order to use our methodology as a static and automated detection framework, F does not require to be labeled once the models are trained. Based on F , we iterate over each basic Algorithm 1 semantic reasoning for raw-data generation return textFile 12: end procedure block B. We then collect the instructions of B, denoted by I B , with the function дetInstructions(). I B is translated into an intermediate language, denoted by IR B , using getIntermediateLanguage(). Finally, IR B is being used for the bloc-centric symbolic execution function symbolicExecution(). The latter will return the symbolic state S B , in order words, expressions of each modified variables in a static single assignment form, based on the intermediate representation IR B previously used. The generated semantics S B is then normalized using normalizeSemantics() function. Finally, the normalized semantics N S B is added to the dictionary L containing all normalized semantics for each processed basic block B. The content of L will be used to generate our raw data as text file. Our normalization step has the crucial role of making the model scale to unknown data. Next, Section 3.2 describes this step, along with the content of our raw data.

Semantic-based raw data

Intermediate representations often use concrete values within their generated expressions. This causes raw data to depend on addresses that are specific to some binaries and prevents our models to scale on unknown data. Some intermediate representations also use identifiers in order to express modified registers or memory areas.

1 ExprMem ( ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0

x f f f f f f f f f f f f f f d 0 , 6 4
) ) , s i z e = 6 4 ) = E x p r I d ( ' R D I _ i n i t ' , s i z e = 6 4 ) 2 E x p r I d ( ' a f ' , s i z e = 1 ) = E x p r S l i c e ( ExprOp ( ' ^' , ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0

x f f f f f f f f f f f f f f c 8 , 6 4 ) ) , ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0 x f f f f f f f f f f f f f f f 8 , 6 4 ) ) , E x p r I n t ( 0 x30 , 6 4
) ) , 4 , 5 ) 3 E x p r I d ( ' RBP ' , s i z e = 6 4 ) = ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0

x f f f f f f f f f f f f f f f 8 , 6 4 ) ) 4 ExprMem ( ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0 x f f f f f f f f f f f f f f c 8 , 6 4
) ) , s i z e = 3 2 ) = E x p r S l i c e ( E x p r I d ( ' R D X _ i n i t ' , s i z e = 6 4 ) , 0 , 3 2 ) 5 E x p r I d ( ' p f ' , s i z e = 1 ) = ExprOp ( ' p a r i t y ' , ExprOp ( '& ' , ExprMem ( E x p r I n t ( 0 x 6 0 6 0 7 8 , 6 4 ) , s i z e = 6 4 ) , E x p r I n t ( 0 x f f , 6 4 ) ) ) 6 E x p r I d ( ' RAX ' , s i z e = 6 4 ) = ExprMem ( E x p r I n t ( 0 x 6 0 6 0 7 8 , 6 4 ) , s i z e = 6 4 ) 7 E x p r I d ( ' I R D s t ' , s i z e = 6 4 ) = ExprCond ( ExprMem ( E x p r I n t ( 0 x 6 0 6 0 7 8 , 6 4 ) , s i z e = 6 4 ) , E x p r I n t ( 0 x40064 b , 6 4 ) , E x p r I n t ( 0 x 4 0 0 6 4 4 , 6 4 ) ) 8 E x p r I d ( ' z f ' , s i z e = 1 ) = ExprCond ( ExprMem ( E x p r I n t ( 0 x 6 0 6 0 7 8 , 6 4 ) , s i z e = 6 4 ) , E x p r I n t ( 0 x0 , 1 ) , E x p r I n t ( 0 x1 , 1 ) ) 9 ExprMem ( ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0

x f f f f f f f f f f f f f f f 8 , 6 4
) ) , s i z e = 6 4 ) = E x p r I d ( ' R B P _ i n i t ' , s i z e = 6 4 ) 10 E x p r I d ( ' o f ' , s i z e = 1 ) = E x p r I n t ( 0 x0 , 1 ) 11 E x p r I d ( ' n f ' , s i z e = 1 ) = E x p r S l i c e ( ExprMem ( E x p r I n t ( 0 x 6 0 6 0 7 8 , 6 4 ) , s i z e = 6 4 ) , 6 3 , 6 4 ) 12 E x p r I d ( ' c f ' , s i z e = 1 ) = E x p r I n t ( 0 x0 , 1 ) 13 E x p r I d ( ' RSP ' , s i z e = 6 4 ) = ExprOp ( ' + ' , E x p r I d ( ' R S P _ i n i t ' , s i z e = 6 4 ) , E x p r I n t ( 0

x f f f f f f f f f f f f f f c 8 , 6 4
) ) 14 E x p r I d ( ' RIP ' , s i z e = 6 4 ) = E x p r I n t ( 0 x 4 0 0 6 5 0 , 6 4 ) 15 E x p r I d ( ' I R D s t ' , s i z e = 6 4 ) = E x p r I n t ( 0 x 4 0 0 6 5 0 , 6 4 )

Listing 1: Symbolic state using Miasm2 intermediate language

This notation may further affect the scalability of our trained models. For the purpose of having a model that can scale to unknown data we use a normalization phase. The normalization consists in replacing all identifiers and concrete values by symbols, and non-alphanumerical characters by alphanumerical words. This is a necessary step for a complete features extraction phase that sometimes excludes non-alphanumerical characters when working on text-based raw data. In our methodology, we generate the raw data using the Miasm2 [START_REF] Desclaux | Miasm : Framework de reverse engineering[END_REF] intermediate language. This language is part of the symbolic execution engine that we use for the implementation of our methodology as IDA Pro plug-in. Additionally, the normalized Miasm2 intermediate language has also been successful for the application of machine learning techniques in order to deobfuscate opaque predicates [START_REF] Tofighi-Shirazi | Defeating Opaque Predicates Statically through Machine Learning and Binary Analysis[END_REF]. Listing 1 illustrates the symbolic state S of the first basic-block of the function quick-sort, which is illustrated in Figure 1. Note that the complete raw data will contain the symbolic states of each basic-blocks of the quick-sort function. We can see that Miasm2 intermediate language uses several keywords to express the semantics of the basic blocks. For example, ExprId is used for registers and ExprInt for concrete values. The registers and concretes values prevent our model from scaling to unknown data, thus potentially lowering our model accuracy. This underlines the necessity to normalize the intermediate language for an efficient semantic reasoning. Listing 16 illustrates the same basic-block symbolic state, but normalized. Listing 2: Symbolic state using our normalized Miasm2 intermediate language Additionally, the normalization step also reduces the size of the raw data. This helps enhancing the efficiency of learning and testing phase in terms of execution time. The next sections will present the different machine learning techniques used in our methodology. The purpose is to create automated and efficient models for the detection of obfuscation transformations, as well as their constructions.

Ensemble learning

In machine learning, ensemble methods [START_REF] Thomas | Ensemble methods in machine learning[END_REF] use multiple learning algorithms. They are mostly used to obtain better predictive performance than could be obtained from any of the constituent learning algorithms alone [START_REF] Maclin | Popular ensemble methods: An empirical study[END_REF][START_REF] Rokach | Ensemble-based classifiers[END_REF]. An ensemble, in this case, consists of a set of individually trained classifiers whose predictions are combined when processing novel instances. Different families of ensemble learning methods exists, e.g. Bagging [START_REF] Breiman | Bagging predictors[END_REF], Boosting [START_REF] Freund | Boosting a weak learning algorithm by majority[END_REF][START_REF] Freund | Experiments with a new boosting algorithm[END_REF] or Stacking [START_REF] Smyth | Linearly combining density estimators via stacking[END_REF]. Since every model has its strengths and weaknesses, ensemble models combine individual models to help cope with the weaknesses of each algorithms. In order to select the best possible predictions from our ensemble, we use a voting [START_REF] Su | Making an accurate classifier ensemble by voting on classifications from imputed learning sets[END_REF] algorithm. Hence, a model is selected to make the final prediction by a simple majority vote for accuracy. Our work aims to study the benefits of ensemble learning approach over individual models. Thus, we base our core methodology on voting classifiers. However, a more in-depth studies of other approaches could provide better insights into the reasons why/if ensemble models get consistenly better results for this task.

Multi-label and multi-class classifications

Multi-label classification methods are increasingly required by modern applications [START_REF] Boutell | Learning multi-label scene classification[END_REF][START_REF] Li | Detecting emotion in music[END_REF]. We use multi-label with multi-output classification, in order to return all the detected obfuscation layers, specially when combined. We also focus on multi-class classifications which play a key role in our methodoly due to the following facts:

(1) the detection of all the applied obfuscation transformations is a multi-label classification problem. For example, if our set of labels are the applied transformations, namely controlflow flattening and code virtualization, then one binary can have both protections. In such case, our methodology needs to return all predicted labels. We then refer to such model as a multi-output classification.

(2) the fine-grained detection of the constructions is a multi-class classification problem. For example, if we know that controlflow flattening is applied on a code, then its constructions can only be one unique label (e.g. switch-based, ifnest-based, indirect, call-based, etc.).

Multi-label classification methods differ from binary or multi-class approaches. Tsoumakas et al. [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF] group multi-label classification methods into two categories: problem transformation methods that transform the multi-label classification problem either into one or more single-label classification problems, and algorithm adaptation methods that extend specific learning algorithms in order to handle multi-label data directly. In our methodology we use classifier chains [START_REF] Read | Classifier chains for multi-label classification[END_REF], where each model is an ensemble of learning algorithm, as presented in Section 3.3. We also study the binary relevance methodology [START_REF] Godbole | Discriminative methods for multilabeled classification[END_REF] in Section 4. These two methodologies are briefly introduced in the following paragraphs.

Problem transformation methods. the binary relevance method

[72] is a problem transformation technique that transforms any multi-label problem into a binary problem for each label. Hence, it trains several classifiers, one for each class, i.e. one per obfuscation transformations. The union of all classes that are predicted is taken as the multi-label output. Binary relevance method is popular due to its easy implementation. However, the main drawback is that it ignores the possible correlations between labels. Classifier chains [START_REF] Read | Classifier chains for multi-label classification[END_REF] however, as opposed to binary relevance method, take into account the labels correlations. With this methodology we have for n labels also n binary classifiers f 0 , f 1 , ..., f n constructed. The construction is made as a chain where a classifier f i uses the predictions of all its previous classifiers f j with j < i. The chain order is randomly selected in our design.

Algorithm adaptation methods.

Algorithm adaptation extends single label classification to the multi-label context. It is usually done by changing the decision functions. Some learning algorithms support multi-label and multi-output classification (e.g. [START_REF] Zhang | Multilabel neural networks with applications to functional genomics and text categorization[END_REF][START_REF] Zhang | Ml-knn: A lazy learning approach to multilabel learning[END_REF]), whereas others can be extended.

During our experiments, these two classifications approaches, and multi-label problems will be studied in Section 4. Our objective is to provide the best suited algorithms and techniques for an efficient and accurate model.

EXPERIMENTS

In this section we present first the dataset used, common with previous related work [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF][START_REF] Tofighi-Shirazi | Defeating Opaque Predicates Statically through Machine Learning and Binary Analysis[END_REF]. Our preliminary studies towards an efficient implementation of a fine-grained detection framework are also introduced. All our experiments and evaluations are done on a Windows 7 laptop, using 16GB of RAM, and an Intel processor.

Datasets

Our experiments are made on several C code samples. We use the scikit-learn API [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] for the implementation of the models. The datasets contain various types of code, each of them having different functionalities in order to have models that do not fit to a specific type of program. The used samples are listed below:

• GNU core utilities (i.e. core-utils) binaries [START_REF]GNU Core Utilities[END_REF] for normal predicate samples; • Cryptographic binaries for obfuscated and non-obfuscated predicates [START_REF] Conte | crypto-algorithms[END_REF]; • Samples from [START_REF] Banescu | Code obfuscation against symbolic execution attacks[END_REF] containing basic algorithms (e.g. factorial, sorting, etc.), non-cryptographic hash functions, small programs generated by Tigress; • Samples involving the uses of structures and aliases [START_REF]The Algorithms[END_REF][START_REF] Howard | c-algorithms[END_REF].

Our choice is motivated by the samples low ratio of dependencies and their straightforward compilation. This makes their obfuscation possible using tools such as Tigress and OLLVM without errors during compilation. Furthermore, all datasets used for the studies and evaluations are balanced and contain between 1000 to 5000 samples. The obfuscation transformations applied are given in Appendix B and A. The next section will present our studies based on these datasets.

Preliminary studies

Our goal in this section is to provide some answers to the following questions related to our methodology:

• Study 1: when only one obfuscation transformation is applied, is a single model more effective than ensemble models for the detection? • Study 2: when several obfuscation transformations are applied, can the model from Study 1 be applied to the multilabel and multi-output classification problems? • Study 3: when several obfuscation transformations are applied, is a multi-label and multi-output model more efficient than one binary model for each transformation, i.e. classifier chains? • Study 4: for the fine-grained detection of obfuscation constructions, is a single model more efficient than ensemble models?

Our studies and evaluations present two different types of results based on two different evaluations approaches. One is the traditional k-folds cross-validation with scores in black colored font.

The other is made with the functionality-based cross-validation approach in red colored font, used in Salem et al. related work [START_REF] Salem | Metadata recovery from obfuscated programs using machine learning[END_REF]. Besides, we use as a traditional single-model random-forest algorithm throughout all our studies. As for the ensemble models, we combined extra-tree and random-forest learning algorithms. These algorithms were selected because they provided the best scores in terms of accuracy. For simplicity, a preliminary evaluation was made between several learning algorithms [START_REF] Sotiris | Supervised machine learning: A review of classification techniques[END_REF] (e.g. decision trees, k-nearest neighbors, support vector machines, neural network, naive Bayes, random forest, etc.). In order to select the best ensemble models, we combined between 2 to 6 single models, and selected the combination that provided the best scores.

Study 1:

In this study we experiment traditional models against ensemble learning for multi-class classification problems. Namely, each sample is assigned with a unique label. Thus our model returns only one label per sample. We experiment here if ensemble learning can be more efficient at detecting obfuscation transformation, when only one layer is applied. Therefore, we do not combine obfuscation transformations for this study. lustrates our results where we see that ensemble-learning provides a similar accuracy to random-forest, up to 97%, with traditional cross-validation. The illustrated F1-scores per labels, namely the obfuscation transforms, also points out that most of them are predicated similarly with both approaches. An exception is made for arithmetic encoding, i.e. EncA, and opaque predicates, i.e. AddO. With the functionality-based cross-validation approach however, the results differs more as observed in red font. Ensemble-learning technique provides 100% accuracy and F1-score for each classes, whereas random-forest achieves slightly lower results, with an average accuracy at 99%. Due to the semantic reasoning of our methodology, the results are better with this approach when having one layer of obfuscation. Yet, these results are not sufficient to select traditional mono-models over ensemble-learning, or the opposite way. Hence, the next study will experiment these two approaches for multi-label and multi-output classification.

Study 2:

In the following study, we combine all obfuscation transformations. The goal of our model is to correctly predict all the applied layers of obfuscation transformation. Thus, each sample can have one or more labels. We aim to compare the random-forest algorithm with the ensemble model based on random-forest and extra-trees for multi-label and multi-output classification. Our re- sults in Table 2 illustrate that traditional cross-validation provides a higher overall for ensemble learning classifier as opposed to random forest. Our ensemble of models scores 92% as opposed to 90% for random-forest, with F1-scores per labels above 91%. The functionality-based cross-validation provides lower results, with an overall accuracy at 83% and at 82% for respectively random forest and ensemble models. Still, our result indicates that both approaches can efficiently detect several layers of obfuscation transforms. However, we may improve our results using problem transformations methods such as classifier chains.

The next study will experiment this hypothesis.

Study 3:

As in the second study, we combine all obfuscation transformations but we use binary classification problem for multilabel and multi-output classification using classifier chains. Our with Tigress for our experiment. Tigress allows the user to select different kinds of constructions, such as switch-based, ifnest-based, linear-based, interpolation-based for example. This experiment is equivalent to Study 1 in the sense that it is a multi-class classification problem. Namely, each sample has a unique label and the selected model will return one unique label per instance.

Our results in Table 4 show that both random-forest and ensemble models provides the same F1-scores per labels. Their overall accuracies with standard cross-validation are also with 100% accuracy. With functionality-based cross-validation, ensemble models are slightly more efficient with a 100% accuracy as opposed to 99% for mono-model based on random-forest. This led us to select ensemble models in our methodology also for the classification of constructions, as it allows a fined-grained detection capability.

EVALUATIONS

In this section we evaluate our models with respect to the following classification problems:

(1) Multi-label and multi-output evaluation: can our model, based on a classifier chain of ensemble models, efficiently and accurately detect all obfuscation transformations when one or more layers are applied? (2) Multi-class evaluation: once the obfuscation transformation detected, can our ensemble model efficiently and accurately detect the construction of the latter? We use both cross-validation evaluation schemes as detailed in Section 2.3.2. Our evaluations are made with publicly available obfuscators, specifically Tigress and OLLVM, in order to combine obfuscation transformations from different tools.

Transformations detection

Our goal is to evaluate the stealth of obfuscation transformation, either applied as unique layer or combined. We use our multi-label and multi-output model based on ensemble-models and classifier chain to detect all the transformations applied. To measure the efficiency of our model, we used both traditional and functionalitybased cross-validation as explained in Section 2.3.2. A list of all combinations of the applied transformations used in our evaluations can be found in Appendices A and B. Additionally, command line options for Tigress and OLLVM are given in A.1 and B.1.

Obfuscation transformation

Classifier Chain OLLVM Ensemble model bcf 98% / 98% fla 92% / 95% sub 82% / 80% clean 94% / 93% Overall Accuracy 86% / 89% Cross-validation execution time 11s for 1000 samples Table 5: Evaluated accuracy and F1-scores per labels for the detection combined OLLVM transformations.

5.1.1 OLLVM. Our first evaluation uses OLLVM. It implements transformations such as opaque predicates (i.e. bogus control flow, bcf ), instruction substitutions (i.e. sub) and control-flow flattening (i.e. fla). We built a dataset with several combinations of these transformations (c.f. Appendix B) in order to measure the efficiency of our model. Table 5 shows our results. Our model achieves an overall accuracy of 86% with traditional cross-validation and 89% with the functionality-based one. F1-scores for labels bcf, fla, and clean where no transformations are applied, are over 92% and up to 98% for bcf. However, the efficiency of our model to detect OLLVM instructions substitutions transformations, labeled as sub, achieves a low F1-score at 80%. Further evaluations indicate that sub is often considered clean by our model. Thus, when combined with other transformations, sub transformation is often undetected. results. F1-scores for heavy transformations such as Virt, Jit and Flat are high, averaging up to 100% for Jit as an example. Combined test samples between obfuscators such EncA-sub, AddO-bcf, and Flat-fla have high F1-scores, even when combined with other transformations. These heavy transformations introduce important side-effects to the code, allowing an efficient and accurate detection of our model. The ability to efficiently detect non-obfuscated samples is still low compared to the ability to detect all layers of obfuscation transformations. In that case, our model F1-scores are up to 83% and 80% depending on the cross-validation approach used. Still, our model is averaging an accuracy up to 88% and 86%. These overall accuracies illustrate our model efficiency regarding the detection of obfuscation transformations, even when combined, and between the two different obfuscators.

5.1.4 OLLVM vs. Tigress. Our final evaluation aims to compare the accuracies of our model depending on the learning dataset used. First, we use a learning dataset only based on OLLVM transforms. The model will be then evaluated against some similar obfuscation transformations generated by Tigress. Second, we do the opposite, namely train our model on Tigress samples to evaluate it on OLLVM raw data. The results are displayed in Table 8 Finally, when our model is trained on Tigress, the overall accuracy is up to 82% against all OLLVM transforms (c.f. Appendix B). This result indicates that our methodology provides some genericity.

Constructions detection

In this section we evaluate our model for the detection of specific obfuscation transformations constructions. We use our multi-class model, based on ensemble-models, to provide a fine-grained detection technique. As for previous evaluations, we use traditional and functionality-based cross-validation techniques. Yet, the overall accuracy of our model is at 95% and 93% depending on the evaluation approach used. This illustrates the efficiency of our methodology towards the detection of obfuscation transformations constructions.

LIMITATIONS

One threat to the validity of our results is that we only use datasets of relatively small C programs, except for the core-utils binaries used for non-obfuscated samples. Nevertheless, the samples used in our dataset involve all common programming language constructions and various functionalities (e.g. hash functions, sorts, cryptographic algorithms, etc.). However, our future work will include evaluation of our methodology on other obfuscators or programs, such as malwares. Our work shows that semantic reasoning combined with advanced machine learning present capabilities for a fine-grained detection of obfuscation transforms.

The capability of detecting unknown transformations or constructions represents another limitation of our methodology. If our model did not train on one specific transformation or constructions, it will not predict properly the unknown sample. This can lead to a loss of accuracy when unknown transformations are combined.

Dynamic transformations cause limitations to our model for the static detection of obfuscation transforms. Despite from the fact that we are able to accurately detect some of these transformations (i.e. Jit, Virt), when other obfuscation transformations are applied before them, our model is less efficient. Moreover, other transformations such as packing, or anti-symbolic execution techniques may lower the accuracy of our model. However, as pointed out in the next section, our methodology can scale to dynamically collected traces which allows to thwart some of these limitations.

PERSPECTIVES AND FUTURE WORK

First, more in-depth studies of aggregation approaches used in ensemble learning must be done in order to assess if ensemble learning are consistenly more efficient for that task compared to mono-models. The hard voting scheme used is a simple approach, but may not achieve the effective benefit of using the ensemble learning approach.

As seen in [START_REF] Tofighi-Shirazi | Defeating Opaque Predicates Statically through Machine Learning and Binary Analysis[END_REF], semantic reasoning and machine learning provides promising results for deobfuscation methodology. The evaluations shown in this paper illustrate that our model does not depend on the code functionality. A more accurate comparison must be made as future work.

To overcome the dynamic transformations limitations, we can adapt our methodology to dynamically collected instructions traces. With a given instructions trace, we reconstruct each basic-blocks and apply our semantic reasoning approach in order to generate raw data. This step can be done either for the learning or the evaluation phase. Our future work consists in extending the implementation of our current framework and evaluating other combinations of obfuscation transformations based on dynamic traces.

Another issue we need to consider is the application of n layers of the same obfuscation transformations. Presently, our evaluations is done by combining several transformations, but using one time each of them. Our future study should consider the extension of our evaluations to the use of one transformation several times.

We also plan on extending our datasets of C programs with more complex real-world software libraries in the interest of strengthening our experiments.

CONCLUSIONS

In this paper we presented the efficiency of semantic reasoning combined with advanced machine learning techniques. This combination is motivated by the construction of a fine-grained detection framework of obfuscation transformations and constructions. By extending our approach to multi-label and multi-output classification, we enhanced metadata recovery attacks to the detection of multiple layers of obfuscation transformations. We proposed a new approach that combines a bloc-centric symbolic execution with machine learning ensemble model and classifier chains. We used our models to evaluate the stealth of both obfuscation transformations and constructions. Our results are promising, with overall accuracies up to 91% for the transformations and 100% for the constructions, showing slight improvements with respect to current mono-models machine learning. The use of static symbolic execution allows us to be dependent on the underlying functionality of the code samples used for the learning phase. Our empirical studies illustrate that our choices conduct towards the implementation of an efficient and accurate evaluation framework against state of the art obfuscators. However, there is still place for improvements with a more in-depth study of learning algorithms used and their parameters. Our work slightly improves metadata-recovery attacks, and paves the way towards the efficient use of advanced machine learning combined with semantic reasoning.

Figure 1 :

 1 Figure 1: Control-flow graph of a quick-sort function obfuscated using several Tigress transformations.

Figure 2 :

 2 Figure 2: Design steps for fine-grained static detection of obfuscation transformations and constructions.

1 :

 1 procedure semantic reasoning(F : a disassembled function) 2: Initialize a dictionary L 3: for each basic block B in F do 4: I B ← getInstructions(B) 5: IR B ←getIntermediateLanguage(I B ) 6: S B ←symbolicExecution(IR B ) 7: N S B ←normalizeSemantics(S B ) 8: L[B] ← N S B 9: end for 10: textFile = generateRawData(L, F ) 11:

1

  ExprMem ( ExprOp ( op + , REG0 , v0 ) , s i z e = 6 4 ) = REG1 2 REG2 = E x p r S l i c e ( ExprOp ( op ^, ExprOp ( op + , REG0 , v1 ) , ExprOp ( op + , REG0 , v2 ) , v3 ) , 4 , 5 ) 3 REG3 = ExprOp ( op + , REG0 , v2 ) 4 ExprMem ( ExprOp ( op + , REG0 , v1 ) , s i z e = 3 2 ) = E x p r S l i c e ( REG4 , 0 , 3 2 ) 5 REG5 = ExprOp ( o p p a r i t y , ExprOp ( op & , ExprMem ( v4 , s i z e = 6 4 ) , v5 ) ) 6 REG6 = ExprMem ( v4 , s i z e = 6 4 ) 7 I R D s t = ExprCond ( ExprMem ( v4 , s i z e = 6 4 ) , v7 , v8 ) 8 REG8 = ExprCond ( ExprMem ( v4 , s i z e = 6 4 ) , v9 , v10 ) 9 ExprMem ( ExprOp ( op + , REG0 , v2 ) , s i z e = 6 4 ) = REG9 10 REG10 = v9 11 REG11 = E x p r S l i c e ( ExprMem ( v4 , s i z e = 6 4 ) , 6 3 , 6 4 ) 12 REG12 = v9 13 REG13 = ExprOp ( op + , REG0 , v1 ) 14 REG14 = v11 15 I R D s t = v11

Table 1

 1

	il-

Table 1 :

 1 Multi-class accuracy and F1-scores per labels for the detection of Tigress obfuscation transformations (1 layer).

Table 2 :

 2

Multi-label accuracy and F1-scores per labels for the detection of Tigress obfuscation transformations (several layers).

Table 3 :

 3 Classifier chain accuracy and F1-scores per labels for the detection of Tigress obfuscation transformations (several layers). For this final study, our goal is to evaluate the models for the fine-grained detection of an obfuscation transformation construction. We use in our dataset several Virtualized samples

	results with standard cross-validation does not different much from
	previous Study 2 as illustrated in Table 3. The functionality-based
	cross-validation provides improved overall accuracies and F1-scores
	per labels. Ensemble models used in classifier chains provide 90%
	of overall accuracy, compared to random-forest used in classifier
	chains that score 85% of overall accuracy. This study led us to
	select ensemble-learning techniques with classifier chains in our
	methodology since classifier chains allow us to create an efficient
	and accurate model for the detection of obfuscation transformations
	with one or more layers.
	4.2.4 Study 4: Code virtualization	Mono-model	Ensemble model
	Tigress constructions Random-forest Extra-tree & Random-forest
	linear-based	100% / 99%	100% / 100%
	switch-based	100% / 98%	100% / 100%
	if-nest-based	100% / 100%	100% / 100%
	Overall Accuracy	100% / 99%	100% / 100%

Table 4 :

 4 Accuracy and F1-scores per labels for the detection of Virtualized constructions.

  5.1.2 Tigress. Our second evaluation is made with the Tigress obfuscator. Tigress can generate state-of-the-art transformations such as dynamic-code generation (i.e. Jit), code-virtualization (i.e. Virt), control-flow flattening (i.e. Flat), opaque predicates (i.e. AddO) and several encoding (i.e. Arithmetics, Literals and Data, respectively EncA, EncL and EncD), among others. As illustrated inTable 6, our

	Obfuscation transformation	Classifier Chain
	Tigress	Ensemble model
	EncA	94% / 90%
	EncL	90% / 86%
	EncD	92% / 91%
	AddO	95% / 96%
	Flat	96% / 98%
	Virt	99% / 100%
	Jit	100% / 100%
	clean	91% / 89%
	Overall Accuracy	90% / 91%
	Cross-validation execution time 114s for 4000 samples

Table 6 :

 6 Evaluated accuracy and F1-scores per labels for the detection combined Tigress transformations. model accuracy is up to 90% with standard cross-validation. With functionality-based cross-validation, the overall accuracy is at 91%. F1-scores for heavy transformation such as Virt and Jit are up to 99% and 100%. The lowest F1-score is for i.e. EncL which is sometimes considered as a clean sample by our model. Regardless, our evaluation underlines the accuracy and efficiency our methodology against Tigress transformations.5.1.3 OLLVM and Tigress.For this evaluation we combine both OLLVM and Tigress datasets. We aim to see if our model is able to detect common obfuscation transformations. Table7shows our

	Obfuscation transformation	Classifier Chain
	Tigress and OLLVM	Ensemble model
	EncA and sub	93% / 90%
	EncL	88% / 88%
	EncD	90% / 88%
	AddO and bcf	95% / 95%
	Flat and fla	96% / 99%
	Virt	99% / 100%
	Jit	100% / 100%
	clean	83% / 80%
	Overall Accuracy	88% / 86%
	Cross-validation execution time 143s for 5000 samples

Table 7 :

 7 Evaluation accuracy and F1-scores per labels for the detection of both Tigress and OLLVM transformations.

  . As we

	Training dataset	Testing dataset	Overall accuracy
	OLLVM	Tigress (Flat)	100% / 100%
	OLLVM	Tigress (Flat, AddO)	68% / 61%
	Tigress	OLLVM (fla)	95% / 92%
	Tigress	OLLVM (all)	82% / 75%

Table 8 :

 8 Overall accuracies of our model using either OLLVM or Tigress learning dataset.can see, our model efficiently detects Tigress Flat transformation when training on 1000 samples of all OLLVM transforms, with 100% of accuracy. Results are lower when the training dataset is based on Tigress (4000 samples), against OLLVM fla transform, with an overall accuracy up to 95% with a standard cross-validation. Moreover, we can observe that our model cannot efficiently detect Tigress opaque predicates, i.e. AddO, when training only on OLLVM transforms. The results, in that case, indicate that our model efficiently detects the Flat transformation, but only few AddO ones.

Table 9 :

 9 Evaluation accuracy and F1-scores per class for the detection of control-flow flattening constructions.OLLVM but also novel bi-opaque methods[START_REF] Xu | Manufacturing resilient bi-opaque predicates against symbolic execution[END_REF]. Our results in Table 10 show that our model is accurately detecting opaque predicates constructions. F1-scores are up to 100% with standard crossvalidation. Bi-opaque constructions are however often un-detected when combined with other transformations.

	5.2.1 Control-flow flattening. As for code virtualization, control-
	flow flattening can also be constructed in several ways, as intro-
	duced in Section 2.2. Facing the same limitations as for code vir-
	tualization constructions, we evaluated two constructions namely
	switch-based from the Tigress obfuscator, and ifnest-based from
	OLLVM. The evaluation results are in Table 9. Our model averages
	high F1-scores and accuracy, the latter being at 98% with standard
	cross-validation evaluation.

5.2.2 Opaque predicates.

Many opaque predicates constructions exists, some of them having as purpose preventing the usage of existing deobfuscation techniques based on dynamic-symbolic execution. For the detection of their constructions, we used Tigress,

Table 10 :

 10 Evaluation accuracy and F1-scores per class for the detection of opaque predicates constructions.

In our work we consider semantic retrieval only. We are not interested in generating inputs for program exploration.

ACKNOWLEDGMENTS

We are much grateful to the referees comments and suggestions from the editorial board. This work is supported by the French National Research Agency in the framework of the Investissements d'Avenir program (ANR-15-IDEX-02).

A TIGRESS TRANSFORMATIONS

We list the combinations of obfuscation transformations used for our datasets, in their application order: AddOpaque (16 or 32 times); Ad-dOpaque, EncodeLiterals; EncodeLiterals; AddOpaque, EncodeArithmetics; EncodeArithmetics, AddOpaque; EncodeArithmetics; AddOpaque, Encode-Data; EncodeData, AddOpaque; EncodeData; AddOpaque, EncodeArithmetics, EncodeLiterals, EncodeData; EncodeData, EncodeArithmetics, En-codeLiterals, AddOpaque; AddOpaque, Flatten ; Flatten, AddOpaque; Flatten; Flatten, EncodeData, EncodeArithmetics, EncodeLiterals; Virtualize, Ad-dOpaque; Virtualize; Virtualize, EncodeData, EncodeArithmetics, EncodeLiterals; Virtualize, Flatten; Flatten, AddOpaque, EncodeData, EncodeArithmetics, EncodeLiterals; Virtualize, AddOpaque, EncodeData, EncodeArithmetics, EncodeLiterals; Virtualize, Flatten, AddOpaque, EncodeData, En-codeArithmetics, EncodeLiterals; Jit; Jit, AddOpaque; Jit, AddOpaque, En-codeData, EncodeArithmetics, EncodeLiterals.

A.1 Commands options

1 # AddOpaque o p t i o n s 2 t i g r e s s --Transform = I n i t E n t r o p y --Transform = I n i t O p a q u e --I n i t O p a q u e S t r u c t s = l i s t , a r r a y , env --

B OLLVM TRANSFORMATIONS

We list the combinations of obfuscation transformations used for our datasets, in their application order: bcf; bcf, sub; bcf, sub, fla; bcf, fla, sub; sub; sub, bcf; sub, bcf, fla ; fla ; fla, bcf ; fla, sub, bcf ; fla, bcf, sub.

B.1 Commands options


domain: spi phys math info

text:
Deqiang Han
email: deqhan@xjtu.edu.cn

Yi Yang

Jean Dezert
email: jean.dezert@onera.fr

On Decombination of Belief Function

Keywords: information fusion, decombination, belief functions, combination, divergence maximization

The evidence combination is a kind of decisionlevel information fusion in the theory of belief functions. Given two basic belief assignments (BBAs) originated from different sources, one can combine them using some combination rule, e.g., Dempster's rule to expect a better decision result. If one only has a combined BBA, how to determine the original two BBAs to combine? This can be considered as a defusion of information. This is useful, e.g., one can analyze the difference or dissimilarity between two different information sources based on the BBAs obtained using evidence decombination. Therefore, in this paper, we research on such a defusion in the theory of belief functions. We find that it is a well-posed problem if one original BBA and the combined BBA are both available, and it is an under-determined problem if both BBAs to combine are unknown. We propose an optimization-based approach for the evidence decombination according to the criteria of divergence maximization. Numerical examples are provided illustrate and verify our proposed decombination approach, which is expected to be used in applications such the difference analysis between information sources in information fusion systems when the original BBAs are discarded, and performance evaluation of combination rules.

I. INTRODUCTION

The theory of belief functions, which is also known as the Dempster-Shafer evidence theory [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], has been widely used in many information fusion based applications including the pattern classification [START_REF] Liu | Evidential classifier for imprecise data based on belief functions[END_REF], [START_REF] Yang | An angle-based neighborhood graph classifier with evidential reasoning[END_REF], multi criteria decision making (MCDM) [START_REF] Han | A fuzzy-cautious OWA approach with evidential reasoning[END_REF], fault diagnosis [START_REF] Xu | Interval-valued evidence updating with reliability and sensitivity analysis for fault diagnosis[END_REF] and image processing [START_REF] Zhang | A new adaptive switching median filter for impulse noise reduction with pre-detection based on evidential reasoning[END_REF].

The information fusion in the theory of belief functions is implemented by evidence combination based on some combination rule, e.g., the well-known Demspter's rule. There have also emerged various alternative combination rules including Yager's rule [START_REF] Yager | On the dempster-shafer framework and new combination rules[END_REF], Dubois & Prade's rule [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF], Smets' rule [START_REF] Smets | The transferable belief model[END_REF], Murphy's rule [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF], Florea's rule [START_REF] Florea | Robust combination rules for evidence theory[END_REF], proportional conflict redistribution 5 (PCR5), and PCR6 [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion-Collected Works[END_REF], [13], etc.

The inverse process of the information fusion, which can also be called as information "defusion" or "decombination", is also meaningful in information processing and analysis. Like the blind source separation (BSS) [START_REF] Fantinato | A second-order statistics method for blind source separation in post-nonlinear mixtures[END_REF] component analysis [START_REF] Comon | Handbook of Blind Source Separation, Independent Component Analysis and Applications[END_REF], which aim to recover independent sources given only the observations that are unknown linear mixtures of the unobserved independent source signals, can be considered as a process of information decombination. One can analyze the original information sources and judge their relationship based on the results obtained using decombination. The community of belief functions theory seldom research on the information decombination problem, which means that given a combined BBA, how to determine the original BBAs for the combination. In Smets' work [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], the concept of decomposition of evidence was proposed, which focuses on decomposing any BBA (not always assumed to a combined BBA) into many simple support function of BBAs. He also proposed the inverse operation of evidence combination, which only focus on the following case: given a combined BBA and one BBA participating the combination, how to restore another BBA participating the combination. In this paper, we focus on the information decombination (separation) or evidence decombination in the theory of belief functions. For simplicity, here we only concern the evidence decombination for two information sources. We find that given the combined BBA together with one original BBA, it is well-posed, that is, the other BBA can be uniquely determined. However, it turns out to be an under-determined problem (with multiple solutions) if both BBAs participating the combination are unknown and the combined BBA is given. The optimization (maximization) based decombination method is proposed accordingly, where the objective function is the distance between the two original BBAs (unknown variables to determine). Examples and experiments are provided to illustrate and verify our proposed information decombination method for the belief function.

II. BASICS OF BELIEF FUNCTIONS THEORY

The basic concept in the theory of belief functions [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] is the frame of discernment (FOD), which is determined by what we want to know and what we know. Elements in an FOD are mutually exclusive and exhaustive. m : 2 Θ → [0, 1] is defined as a basic belief assignment (BBA, also called a mass function) defined on the FOD Θ satisfying

A⊆Θ m(A) = 1, m(∅) = 0 (1)
where 2 Θ denotes the powerset of Θ. if ∀m(A) > 0, then A is called a focal element of m(•). If a BBA only has singleton focal elements, then it is called a Bayesian BBA. Given a BBA m(•), its corresponding belief function (Bel) and plausibility function (P l) are respectively defined as

Bel(A) = B⊆A m(B) (2)
P l(A) = A∩B =∅ m(B) (3)
The belief Bel(A) represents the justified specific support for the focal element (or proposition) A, while the plausibility P l(A) represents the potential specific support for A. The length of the belief interval [Bel(A), P l(A)] represents the imprecision degree of A.

The evidence combination is the fusion of the BBAs originated from different sources. Two independent BBAs m 1 (•) and m 2 (•) can be combined using Dempster's rule of combination [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] defined by

m(A) =      0, A = ∅ A i ∩B j =A m1(Ai)m2(Bj ) 1- A i ∩B j =∅ m1(Ai)m2(Bj ) , A = ∅ (4)
Dempster's rule in general can be considered as a multiplicative and conjunctive fusion rule. Dempster's rule of combination has been criticized for its counter-intuitive behaviors [START_REF] Zadeh | A simple view of the Dempster-Shafer theory of evidence and its implication for the rule of combination[END_REF], [START_REF] Dezert | On the validity of Dempster's fusion rule and its interpretation as a generalization of Bayesian fusion rule[END_REF], especially in high conflict cases. Many alternative combination rules have been proposed accordingly. See [START_REF] Smarandache | Advances and Applications of DSmT for Information Fusion-Collected Works[END_REF], [START_REF] Han | Sequential weighted combination for unreliable evidence based on evidence variance[END_REF], [START_REF] Deng | Evidence combination from an evolutionary game theory perspective[END_REF] for details. Other researchers like Haenni [START_REF] Haenni | Shedding new light on Zadeh's criticism of Dempster's rule of combination[END_REF] think that the conflict results from a fault in the framing of problem.

Distance of evidence is for measuring the dissimilarity between BBAs. The most commonly used and strict distance of evidence is Jousselme's distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] defined as follows.

d J (m 1 , m 2 ) 0.5 • (m 1 -m 2 ) T Jac (m 1 -m 2 ) (5)
where the elements Jac(A, B) of Jaccard's weighting matrix Jac are defined as

Jac(A, B) = |A ∩ B|/|A ∪ B| (6)
Here A, B are focal elements of m 1 and m 2 , respectively. Jaccard's matrix has been proved to be positive-definite [START_REF] Bouchard | A proof for the positive definiteness of the Jaccard index matrix[END_REF], therefore, Jousselme's distance is a strict metric satisfying four requirements of the distance metric including the nonnegativity, non-degeneracy, symmetry, and triangular inequality.

III. EVIDENCE DECOMBINATION IN BELIEF FUNCTIONS THEORY

The evidence combination can be considered as a procedure of information fusion 1 as shown in Fig. 1. 1 or information compression because from two BBAs we get one. Given a BBA obtained after the combination, if one wants to know the possible original BBAs, then the evidence decombination is needed, which can be considered as a procedure of information decombination as shown in Fig. 2. In this paper, we focus on determining the original BBAs given a combined BBA. First, we analyze the relationship between the combined BBA and the original ones. For simplicity, we only suppose that there are two original BBAs in this paper.

A. Relation between Combined BBA and Original Ones according to Dempster's Rule

According to the Dempster's rule in Eq.( 4), one can obtain the following equations. Suppose that m 1 (•) and m 2 (•) are two BBAs defined on the FOD Θ = {θ 1 , ..., θ n }. For each BBA, there are at most 2 n -1 focal elements as shown below.

m1 m2       {θ1} {θ2} {θ1, θ2} . . . Θ             {θ1} {θ2} {θ1, θ2} . . . Θ       Define a matrix R (k) for each k = 1, ..., 2 n -1 where R (k) (i, j) = 1, if C k = A i ∩ B j 0, if C k = A i ∩ B j (7)
where A i is the focal element of m 1 (•), and where

B j is the focal element of m 2 (•). The combined BBA is m(•) = m 1 (•) ⊕ m 2 (•), and C k is the focal element of m(•). Note that i, j, k = 1, ..., 2 n -1.
According to Dempster's rule, the mass assignment of focal element C k in the combined BBA is

m(C k ) =      m 1 ({θ 1 }) m 1 ({θ 2 }) . . . m 1 (Θ)      T R (k)      m 2 ({θ 1 }) m 2 ({θ 2 }) . . . m 2 (Θ)      1 -K (8)
where k = 1, ..., 2 n -1 and

K = Ai∩Bj =∅ m 1 (A i )m 2 (B j )
denotes the conflict coefficient. For simplicity in the sequel, we denote the mass value vector as

m 1 =           m 1 ({θ 1 }) m 1 ({θ 2 }) m 1 ({θ 1 , θ 2 }) m 1 ({θ 3 }) m 1 ({θ 1 , θ 3 }) m 1 ({θ 2 , θ 3 }) m 1 (Θ)           T , m 2 =           m 2 ({θ 1 }) m 2 ({θ 2 }) m 2 ({θ 1 , θ 2 }) m 2 ({θ 3 }) m 2 ({θ 1 , θ 3 }) m 2 ({θ 2 , θ 3 }) m 2 (Θ)          
T Then, Eq. ( 8) can be rewritten as

m(C k ) = m T 1 R (k) m 2 1 -K 1)
Case I: In this case, the combined BBA m(•) is available, and both original BBAs are unknown. That is, m 1 (A i ) (i = 1, ..., 2 n -1) and m 2 (B j ) (j = 1, ..., 2 n -1) are unknown variables to determine, then the quantity of the unknown variable is 2 n -1 × 2 = 2 n+1 -2. For the BBA, there exists

2 n -1 i=1 m 1 (A i ) = 1 (9) 2 n -1 j=1 m 2 (B j ) = 1 (10)
Considering Eqs. ( 8)-( 10), we have 2 n -1 + 2 = 2 n + 1 simultaneous equations. As aforementioned, to determine all the mass values of m 1 (•) and m 2 (•), we have 2 n+1 -2 unknown variables. That is, the quantity of the unknown variables is larger than that of the equations. Therefore, this is an under-determined problem with multiple solutions in general.

2) Case II: In this case, the combined BBA m(•) and one original BBA (e.g., m 1 (•)) are available, while another original BBA (e.g., m 2 (•)) is unknown. To determine m 2 (•), we have 2 n -1 unknown variables. By considering Eqs. ( 8) and (10), we have 2 n simultaneous equations. That is, the quantity of the unknown variables is less than that of the equations. Therefore, this is an over-determined problem, and then m 2 (•) can be determined uniquely.

B. Optimization Based Evidence Decombination

As aforementioned, given a combined BBA, to determine the two original BBAs is an under-determined problem, for which, the optimization-based approach is feasible. Then, the key issue is to select an appropriate criterion to establish the objective function for the optimization.

In fact, the evidence decombination is like the blind source separation (BSS), where the divergence between different sources are used for the optimization based source separation, e.g, minimization of the mutual information (MMI) [START_REF] Babaie-Zadeh | A general approach for mutual information minimization and its application to blind source separation[END_REF], which represents the largest divergence. Therefore, in this paper, we use for reference the criterion in BSS to design the objective function in optimization based evidence decombination. Here we use the distance of evidence to describe the divergence between BBAs. Furthermore, we use the simultaneous equations including the Eqs ( 8)- [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF] together with inequalities (to assure a legal BBA2 with the mass value lies in [0,1]) as the constraints for the distance maximization to implement the evidence decombination as illustrated in Eq. [START_REF] Florea | Robust combination rules for evidence theory[END_REF].

max m1,m2 d J (m 1 , m 2 ) = 0.5 • (m 1 -m 2 ) T Jac (m 1 -m 2 ) s.t.                      m(C k ) = m1 T R (k) m2 1-K 2 n -1 i=1 m 1 (A i ) = 1 2 n -1 j=1 m 2 (B j ) = 1 0 ≤ m 1 (A i ) ≤ 1, ∀i = 1, ..., 2 n -1 0 ≤ m 2 (B j ) ≤ 1, ∀j = 1, ..., 2 n -1 (11
) By solving 3 the constrained maximization problem in Eq. ( 11), one can obtain a pair of BBAs that are farthest to each other, and that provide the combined BBA when fusioned with Demspter's rule.

IV. NUMERICAL EXAMPLES OF EVIDENCE DECOMBINATION BASED ON OPTIMIZATION

In this section we give different examples illustrating how BBAs decombination can be obtained based on optimization of evidence decombination.

A. Example 1

Suppose that the FOD is {θ 1 , θ 2 , θ 3 }. A BBA obtained after the combination of two unknown BBAs is

m({θ 1 }) = 0.1, m({θ 2 }) = 0.2, m({θ 1 , θ 2 }) = 0.1, m({θ 3 }) = 0.1, m({θ 1 , θ 3 }) = 0.1, m({θ 2 , θ 3 }) = 0.3, m(Θ) = 0.1.
The equality constraints for the maximization problem include

m({θ 1 }) = 0.1 =    m 1 ({θ 1 }) m 1 ({θ 2 }) m 1 ({θ 1 , θ 2 }) m 1 ({θ 3 }) m 1 ({θ 1 , θ 3 }) m 1 ({θ 2 , θ 3 }) m 1 (Θ)    T R (1)    m 2 ({θ 1 }) m 2 ({θ 2 }) m 2 ({θ 1 , θ 2 }) m 2 ({θ 3 }) m 2 ({θ 1 , θ 3 }) m 2 ({θ 2 , θ 3 }) m 2 (Θ)    1 -K where R (1) =    1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0   
It can be rewritten to a simpler form as

m({θ 1 }) = 0.1 = m 1 T R (1) m 2 1 -K For other focal elements, m({θ 2 }) = 0.2 = m 1 T R (2) m 2 1 -K where R (2) =    0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0    m({θ 1 , θ 2 }) = 0.1 = m 1 T R (3) m 2 1 -K where R (3) =    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0    m({θ 3 }) = 0.1 = m 1 T R (4) m 2 1 -K where R (4) =    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0    m({θ 1 , θ 3 }) = 0.1 = m 1 T R (5) m 2 1 -K where R (5) =    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0    m({θ 2 , θ 3 }) = 0.3 = m 1 T R (6) m 2 1 -K where R (6) =    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0    m(Θ) = 0.1 = m 1 T R (7) m 2 1 -K where R (7) =    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1   
and the two equations in Eqs.( 9) and Eqs. [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF]. The inequality constraints are

0 ≤ m1({θ1}) ≤ 1 0 ≤ m1({θ2}) ≤ 1 0 ≤ m1({θ1, θ2}) ≤ 1 0 ≤ m1({θ3}) ≤ 1 0 ≤ m1({θ1, θ3}) ≤ 1 0 ≤ m1({θ2, θ3}) ≤ 1 0 ≤ m1(Θ) ≤ 1 and 0 ≤ m2({θ1}) ≤ 1 0 ≤ m2({θ2}) ≤ 1 0 ≤ m2({θ1, θ2}) ≤ 1 0 ≤ m2({θ3}) ≤ 1 0 ≤ m2({θ1, θ3}) ≤ 1 0 ≤ m2({θ2, θ3}) ≤ 1 0 ≤ m2(Θ) ≤ 1
According to the constrained maximization in Eq. ( 11), one can obtain two BBAs as follows:

B. Example 2

Suppose that there are two BBAs defined on the FOD Θ = {θ 1 , θ 2 , θ 3 }:

m 1 ({θ 1 }) = 0.6, m 1 ({θ 2 }) = 0.2, m 1 ({θ 2 , θ 3 }) = 0.1, m 1 (Θ) = 0.1. and m 2 ({θ 1 }) = 0.2, m 2 ({θ 2 }) = 0.6, m 2 ({θ 2 , θ 3 }) = 0.1, m 2 (Θ) = 0.1.
By calculating the Jousselme's distance in Eq. ( 5), one obtains that

d J (m 1 , m 2 ) = 0.4. With Dempster's rule of combination, one obtains that m(•) = m 1 (•) ⊕ m 2 (•) with m({θ 1 }) = 0.3846, m({θ 2 }) = 0.5385, m({θ 2 , θ 3 }) = 0.0577, m(Θ) = 0.0192.
According to the evidence decombination approach in Eq [START_REF] Florea | Robust combination rules for evidence theory[END_REF], one obtains that m a ({θ 1 }) = 0, m a ({θ 2 }) = 0.8750, m a ({θ 2 , θ 3 }) = 0.0851, m a (Θ) = 0.0400.

and m b ({θ 1 }) = 0.9399, m b ({θ 2 }) = 0, m b ({θ 2 , θ 3 }) = 0.0131, m b (Θ) = 0.0470.
It is easy to verify that the combination result

m a (•)⊕m b (•) = m(•), which is the same as m 1 (•) ⊕ m 2 (•).
By calculating the Jousselme's distance given by Eq. ( 5), one can verify that

d J (m a , m b ) = 0.9265 > d J (m 1 , m 2 ) = 0.4.

C. Example 3

A given combined BBA is the same as that in Example 2.

m({θ 1 }) = 0.3846, m({θ 2 }) = 0.5385, m({θ 2 , θ 3 }) = 0.0577, m(Θ) = 0.0192.
Moreover, suppose that we have additional information and we also know m 1 (•):

m 1 ({θ 1 }) = 0.6, m 1 ({θ 2 }) = 0.2, m 1 ({θ 2 , θ 3 }) = 0.1, m 1 (Θ) = 0.1.
Then, we try to use the BBA decombination to calculate the m2 (•) and to check whether it is the same as m 2 (•) in Example 2. Here is just the case II as aforementioned in Sect III.A. Therefore, m2 (•) should be unique. So, there should exist m 2 (•) = m2 (•). It is an over-determined problem, and we can still use the optimization to solve m2 (•) by modifying the optimization problem to

max m2 d J (m 1 , m2 ) = 0.5 • (m 1 -m2 ) T Jac (m 1 -m2 ) s.t.          m(C k ) = m1 T R (k) m2 1-K 2 n -1 j=1 m2 (B j ) = 1 0 ≤ m2 (B j ) ≤ 1, ∀j = 1, ..., 2 n -1 (12) where m2 =      m2 ({θ 1 }) m2 ({θ 2 }) . . . m2 (Θ)     
By solving Eq. ( 12), one obtains

m2 ({θ 1 }) = 0.2, m2 ({θ 2 }) = 0.6, m2 ({θ 2 , θ 3 }) = 0.1, m2 (Θ) = 0.1.
That is, given a combined BBA and one original BBA, another original one can be determined uniquely.

V. FURTHER ANALYSIS ON EVIDENCE DECOMBINATION

A. Divergence Minimization or Maximization?

In the evidence decombination shown in Eq. ( 11), distance maximization is adopted. This is inspired by the minimization of mutual information (i.e., the maximization of divergence) between sources in Blind Source Separation (BSS), which aims to bring out more independent components [START_REF] Babaie-Zadeh | A general approach for mutual information minimization and its application to blind source separation[END_REF]. One can also try to implement the evidence decombination based on the distance minimization. Based on our analysis, we find that if the distance minimization is used, the minimum distance will be zero and the BBAs of two sources are identical.

Suppose that m 1 (•) = m 2 (•) = m 0 (•), one can rewrite the constraints in Eq. [START_REF] Florea | Robust combination rules for evidence theory[END_REF] as

       m(C k ) = m0 T R (k) m0 1-K 2 n -1 i=1 m 0 (A i ) = 1 0 ≤ m 0 (B j ) ≤ 1, ∀j = 1, ..., 2 n -1 (13)
where

m 0 =      m 0 ({θ 1 }) m 0 ({θ 2 }) . . . m 0 (Θ)     
As we see in Eq. ( 13), there are 2 n -1 unknown variables (mass values for 2 n -1 focal elements in m 0 (•)) to determine. There are 2 n -1 + 1 = 2 n simultaneous equations in total. Therefore, if the solution exists, in general this is an overdetermined problem which has the unique solution.

Here we provide an example to verify this, where the combined BBA is still as chosen in Example 2, which is m({θ 1 }) = 0.3846, m({θ 2 }) = 0.5385, m({θ 2 , θ 3 }) = 0.0577, m(Θ) = 0.0192.

According to Eq. ( 11) and change the maximization to minimization, we obtain that m

1 (•) = m 2 (•) = m 0 (•), which is m 0 ({θ 1 }) = 0.3877, m 0 ({θ 2 }) = 0.3958, m 0 ({θ 2 , θ 3 }) = 0.1082, m 0 (Θ) = 0.1082. It is easy to verify that m 0 (•) ⊕ m 0 (•) = m(•).
We prefer the criterion of distance maximization, since it can bring out more distinct (likely to be more independent) evidences.

Note that since we select the maximization, to assure to find the unique global optimal, the objective should be upperconvex. However, the objective function, i.e., the distance of evidence cannot satisfy this. Therefore, in our work in this paper, intelligent optimization algorithms [START_REF] Kruse | Computational Intelligence: A Methodological Introduction[END_REF] (e.g., the particle swarm algorithm and genetic algorithm) are adopted for the maximization to achieve a better solution. Therefore, it cannot be used for analyzing or evaluating specific single sensor; however, the evidence decombination is expected to be used in applications like divergence evaluation between sensors, which is helpful for the sensor management. Given a BBA, if one can decombine it into two BBAs, then the maximum difference between corresponding information sources can be evaluated by calculating the distance between the two BBAs.

B. Possible Applications

Another possible application is the evaluation of different combination rules. Here, we only use the Dempster's rule to construct the evidence decombination. In fact, other alternative combination rules can also be used for finding evidence decombination, where the difference between most of existing rules of combinations available in the literature lies in the choice of matrix R (k) in Eq. [START_REF] Yager | On the dempster-shafer framework and new combination rules[END_REF]. Then, given a BBA, one can use different decombination methods corresponding to different combination rule to bring out different pairs of BBAs. One can calculate the distance between two BBAs in each pair to represent the aggregation capability of the corresponding combination rule. That is, an evidence decombination approach can bring out a more divergent BBA pair, then the decombination method's corresponding combination rule can aggregate (combine) a more divergent BBA pair to the same BBA compared with other rules. So we say that it has a better aggregation capability.

VI. CONCLUSIONS

In this paper, an evidence decombination approach is proposed, where the distance maximization criterion is adopted in the evidence decombination. Some numerical examples and related analysis are provided to illustrate our proposed method and the possible applications are forecasted.

In this paper, the distance of evidence used in the optimization is Jousselme's distance. In our future work, we will try other strict distance metric [START_REF] Jousselme | Distances in evidence theory: Comprehensive survey and generalizations[END_REF], [START_REF] Han | Belief interval-based distance measures in the theory of belief functions[END_REF] in the theory of belief functions for comparison. Currently, the objective function is the distance of evidence. In future work, we will try to use the difference between BBAs' uncertainty measure values [START_REF] Jousselme | Measuring ambiguity in the evidence theory[END_REF], [START_REF] Yang | A new distance-based total uncertainty measure in the theory of belief functions[END_REF]. Furthermore, we only consider two sources of evidence for the evidence decombination for simplicity. In our future work, we will try to design more sources (larger than two) for the evidence decombination. This paper is only a preliminary work on the evidence decombination, in future research work, we will try to apply the proposed method in various appropriate applications.

  and independent This work was supported by the National Natural Science Foundation (No. 61573275, No. 61671370), Postdoctoral Science Foundation of China (No. 2016M592790), Postdoctoral Science Research Foundation of Shaanxi Province (No. 2016BSHEDZZ46), and Fundamental Research Funds for the Central Universities (No. xjj2016066)

Fig. 1 .

 1 Fig. 1. Evidence combination -Information Fusion.

Fig. 2 .

 2 Fig. 2. Evidence decombination -Information Decombination or "Defusion".

  ma({θ1}) = 0, ma({θ2}) = 0, ma({θ1, θ2}) = 0.0323, ma({θ3}) = 0.1612, ma({θ1, θ3}) = 0.1612, ma({θ2, θ3}) = 0.4840, ma(Θ) = 0.1613. andm b ({θ1}) = 0.0834, ma({θ2}) = 0, m b ({θ1, θ2}) = 0.3666, m b ({θ3}) = 0, m b ({θ1, θ3}) = 0.0001, m b ({θ2, θ3}) = 0, m b (Θ) = 0.5499.It is easy to verify that the combination result m a (•) ⊕ m b (•) is the same as the given BBA m(•).

  Note that given a combined BBA m(•), m a (•) and m b (•) after the evidence decombination. However, we do not know the specific correspondence between {m a (•), m b (•)} and {m 1 (•), m 2 (•)}. That is, m a (•) could correspond to m 1 (•) or m 2 (•), and m b (•) could also correspond to m 1 (•) or m 2 (•).

to obtain admissible BBAs with values in [0,1] and their sum equals to one.

Here we use the global optimization toolbox in Matlab TM .