Ahmed Drissi

El Maliani

Mohammed El Hassouni

Nour-Eddine - Eddine Lasmar

Yannick Berthoumieu

Driss Aboutajdine

Mohammed El Hassouni

Color Texture Classification Using Rao Distance between Multivariate Copula Based Models

Keywords: Color texture classification, Gaussian Copula, Rao distance

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Texture classification is an important and challenging task in image analysis. Efficient texture classification is essentially based on a pertinent feature extraction and similarity measurement steps, especially when choosing the K-Nearest Neighbor approach. The feature extraction step consists of figuring out a set of attributes that best describe the texture, and best discriminate this latter from different textures. Many works, stressed that treating the texture in the wavelet domain allows accurate characterization, by modeling histograms of the wavelet subbands with appropriate models. In this context, the Generalized Gaussian Density (GGD) proposed by Do and Vetterli [START_REF] Do | Wavelet-based texture retrieval using generalized Gaussian density and Kullback-Leibler distance[END_REF] showed a good ability in modeling the heavely tailed and pickly pronounced behavior of the histograms. In the case of color textures, and more specifically when they are represented in the RGB color space, a big correlation exists between the color bands, thus considering univariate models leads to a considerable loss of information in the characterization. For this, joint models were proposed to describe the dependence across color bands. Verdoolaeg et al. [START_REF] Verdoolaeg | Multiscale colour texture retrieval using the geodesic distance between multivariate Generalized Gaussian models[END_REF], proposed a multivariate Generalized Gaussian distribution (MGGD) for multiscale color texture retrieval, modeling dependence across color components. A t-Student Copula based multivariate Weibull distribution was proposed by Kwitt et al. [START_REF] Kwitt | A joint model of complex wavelet coefficients for texture retrieval[END_REF], describing dependence between complex wavelet coefficient magnitudes also in the context of color texture retrieval. The second step of a KNN based classification process, is the similarity measurement, which consists of measuring distance between textures according to the extracted features. In their pioneering work, Do and Vetterli [START_REF] Do | Wavelet-based texture retrieval using generalized Gaussian density and Kullback-Leibler distance[END_REF] showed that the Kullback-Leibler (KL) divergence is suitable for comparing textures reposing on the estimated model parameters. Recently KL divergence has been used to measure similarity between Copula based distributions, in the context of texture retrieval [START_REF] Kwitt | A joint model of complex wavelet coefficients for texture retrieval[END_REF]. A Monte-carlo approach was adopted to deal with the lack of a closed form of the KL divergence between Copula based models. However, the KL divergence cannot be considered as a metric on the space of probability distributions, since it is not symmetric and does not obey the triangle inequality. To remedy to this problem, a Riemannian metric namely the Rao or Geodesic distance can be used instead of the commonly used Kullback-Leibler divergence. The Rao distance was first proposed by Rao [START_REF] Rao | Information and the accuracy attainable in the estimation of statistical parameters,textquotedblright in Bull[END_REF] exploiting that the Fisher information for a set of probability density functions (pdfs) is a Riemannian metric on the corresponding manifold. Thus, the Rao distance is achieved reposing on the Fisher information metric and by resolving the corresponding geodesic equations. Rao distance was already used in different fields, such as segmentation and classification [START_REF] Pastore | Segmentation of brain magnetic resonance images through morphological operators and geodesic distance[END_REF] [START_REF] Yong | Modified kernel functions by geodesic distance[END_REF]. Closed forms of the Fisher-Rao metric were proposed for Extreme Value probability distributions namely the Gumbel, Cauchy-Fréchet, and Weibull [START_REF] Oller | Information Metric for Extreme Value and Logistic Probability Distributions[END_REF]. In [START_REF] Verdoolaeg | Multiscale colour texture retrieval using the geodesic distance between multivariate Generalized Gaussian models[END_REF], the Rao distance was used as a similarity measure between zero-mean multivariate generalized Gaussian distributions (MGGD). A closed form of the Rao metric was computed in the case of a fixed shape parameter, while geodesic equations were solved numerically when assuming different shape parameters. In this work, we propose a Rao metric as a similarity measure on the manifold of Gaussian Copula based multivariate probability distributions. This assumes that we know Rao distance for the marginal distributions, before computing the metric for the joint model. To test effectiveness of the Rao distance based similarity measure, we show results in comparison with the KL divergence based similarity measure in term of classification rates. This paper is organized as follows. In the next section, we give a review of Copula theory and construct the multivariate models reposing on the Copula approach. In section 3, we derive the general form of the Rao distance on the manifold of Gaussian Copula based probability distributions. In section 4, we present results of texture classification using the Rao distance and the Kullback-Leibler divergence, before concluding in section 5. Manifold

Review of the Copula theory

We draw on the Copula theory to incorporate the information of dependency between color components in the RGB color space. Copulas are an elegant tool for merging a set of marginal pdfs into a multivariate pdf with a particular dependence structure. A Copula is a multivariate cumulative distribution function defined on the d-dimensional unite cube [0, 1] d [START_REF] Nelsen | An Introduction to Copulas[END_REF], with uniform one dimensional marginals. Given a d-dimensional vector x = [x 1 , ..., x d ] on the unit cube [0, 1], with a cumulative distribution function F and marginal cumulative distribution functions (cdf) F 1 , ..., F d . The multivariate cdf is:

F (x 1 , ..., x d ) = P (X 1 ≤ x 1 , ..., X d ≤ x d ) (1)
Sklar theorem [START_REF] Sklar | Fonctions de répartition à n dimensions et leurs marges[END_REF] shows that there exists a d-dimensional Copula C such that:

F (x 1 , ..., x d ) = C(F 1 (x 1 ), ..., F d (x d )) (2)
Further, if C is continuous and differentiable, the Copula density is given by:

c(u 1 , ..., u d ) = ∂ d C(u 1 , ..., u d ) ∂u 1 ...∂u d (3)
The joint pdf is uniquely deduced from the margins and the Copula density as follows:

f (x 1 , ..., x d ) = c(F 1 (x 1 ), ..., F d (x d )) d i=1 f i (x i ) (4)
where f i , i = 1, ..., d, represent the marginal densities. It appears that the Gaussian Copula is suitable to model linear dependence, which is the most popular in texture modeling. Gaussian Copula density is defined by:

c(u, Σ) = 1 |Σ| 1/2 exp[- 1 2 ϑ T (Σ -1 -I)ϑ] (5)
with

ϑ i = φ -1 (F i (u i ))
, and φ represents the standard normal cumulative distribution function. Σ denotes the correlation matrix, and I denotes the ddimensional matrix identity. From this we can derive the joint model as:

f (x, θ) = 1 |Σ| 1/2 exp[- 1 2 ϑ T (Σ -1 -I)ϑ] d i=1 f i (x i ) (6)
where θ = (η, Σ) denotes the hyperparameters of the joint model, where η = (η (1) , η (2) , ..., η (k) ) represents a set of the marginal parameters and Σ denotes the covariance matrix of the Gaussian vector ϑ.

For estimating parameters of the Gaussian Copula based model we use the IFM (Inference From Margins) method [START_REF] Joe | Multivariate Models and Dependence Concepts[END_REF]. In a first time, this consists of estimating the parameters of the marginals using the Maximum Likelihood (ML) procedure. ML estimators ηi are deduced as:

ηk = argmax η k n i=1 log(f k (x ik , η k )) (7)
Secondly, the log-likelihood function for the joint distribution is maximized using the margins estimators η=(η (1) , ..., η(k) ):

Σ = argmax Σ n i=1 log c(F 1 (x 1i ; η1 ), ..., F d (x di ; ηd ); Σ) (8)

Multivariate Weibull Distribution

From ( 6), the pdf of multivariate Weibull (Mwbl) distribution is defined as:

f M wbl (x, θ) = 1 |Σ| 1/2 exp[- 1 2 ϑ T (Σ -1 -I)ϑ] × ( τ λ ) d d i=1 x τ i exp - d i=1 ( x i λ ) τ (9)
with θ = (τ, λ, Σ), τ represents the shape parameter, λ represents the scale parameter, and Σ denotes the covariance matrix.

Multivariate Gamma Distribution

The joint pdf of multivariate Gamma (Mgam) distribution is defined as:

f M gam (x, θ) = 1 |Σ| 1/2 exp[- 1 2 ϑ T (Σ -1 -I)ϑ] × ( β -α Γ (α) ) d d i=1 x α-1 i exp - d i=1 ( x i β ) (10)
with θ = (α, β, Σ), α represents the shape parameter, β represents the scale parameter, and Σ denotes the covariance matrix.

Multivariate Laplacian Distribution

The pdf of multivariate Laplacian (Mlap) Distribution is defined as:

f M lap (x, θ) = 1 |Σ| 1/2 exp[- 1 2 ϑ T (Σ -1 -I)ϑ] × 1 b d exp - d i=1 (x i -a) b (11)
with θ = (a, b, Σ), a represents the location parameter, b represents the scale parameter, and Σ denotes the covariance matrix.

Rao Geodesic Distance On The Manifold Of Gaussian Copula Based Distributions

Let us consider M θ as the statistical manifold of Gaussian Copula based probability distributions, and f (x; θ) a pdf from this manifold, where θ a vector of parameters of f . Rao distance is a Riemannian metric defined by the fisher information matrix as:

ds 2 = d i,j=1
g ij (θ)dθ i dθ j [START_REF] Van De Wouwer | Statistical Texture Characterization From Discrete Wavelet Representations[END_REF] where g ij represents the Fisher matrix elements:

g ij (θ) = E ∂ ∂θ i log f (X; θ) ∂ ∂θ j log f (X; θ) (13) = -E ∂ 2 ∂θ i θ j log f (X; θ) (14)
Hence, given two probability distributions f (x; θ 1 ) and f (x; θ 2 ) on M θ , we can compute the Rao geodesic distance as:

L = θ2 θ1 ds = 1 0 i,j g ij θi θj dt (15)
In M θ , probability distributions are defined as:

f (x, θ) = c Φ (u 1 , ..., u d ; Σ) d i=1 f i (x i ; η i ) (16) So, g ij (θ) = -E ∂ 2 ∂θ i θ j log c Φ (u 1 , ..., u d ; Σ) d i=1 f i (x i ; η i ) (17) = -E ∂ 2 ∂θ i θ j log c Φ (u 1 , ..., u d ; Σ) + log d i=1 f i (x i ; η i ) ( 18
)
The vector (u 1 , ..., u d ), is constructed by transforming the vector (x 1 , ..., x d ) empirically with known parameters η i via u i = F (x i ; ηi ) , thus we consider these observations without assumptions on the parametric form of the marginal distributions: (u 1 , ..., u d ) = (F (x i , η1 ), ..., F (x i , η1 )). This approach has been already considered for estimating the parameters of the copula without estimating the marginals parameters as an alternative of the IFM method, and was named as CML (Canonical Maximum Likelihood) [START_REF] Durrleman | Which copula is the right one[END_REF]. When this is supposed, we have:

∂ ∂η c Φ (u; Σ) = 0 (19) so then, g ηΣ (θ) = g Ση (θ) = 0. Thus g ΣΣ (θ) = -E ∂ 2 ∂Σ∂Σ log c Φ (u; Σ) (20)
and

g µν (θ) = -E ∂ 2 ∂µ∂ν log d i=1 f i (x i ; η i ) (21)
with µ, ν ∈ {η (1) , ..., η (k) }

g µν (θ) = -E ∂ 2 ∂µ∂ν d i=1 log f i (x i ; η i ) (22) = -E d i=1 ∂ 2 ∂µ∂ν log f i (x i ; η i ) (23) = d i=1 -E ∂ 2 ∂µ∂ν log f i (x i ; η i ) (24)
Thus, from ( 12):

ds 2 = g ΣΣ dΣdΣ + d i=1 µ,ν g µν μ νdt (25) = ds 2 Gauss + d i=1 ds 2 M argins (26)
Thus, the Rao distance between two probability density functions f (x; θ 1 ) and f (x; θ 2 ) on M θ is defined from equation (15) as follows:

L(f (x; θ 1 )||f (x; θ 2 )) = L Gauss (f (x; Σ 1 )||f (x; Σ 2 )) + d i=1 L M argins (f (x; η 1 )||f (x; η 2 )) (27)
and then, the Rao distance between two Mwbl pdfs is:

L(f M wbl (x; θ 1 )||f M wbl (x; θ 1 )) = [ 1 2 d i=1 (ln r i ) 2 ] 1/2 + [log(τ 2 /τ 1 ) -s(λ 2 -λ 1 ) 2 /λ 2 1 λ 2 2 ] 2 + q 2 (λ 2 -λ 1 ) 2 /λ 2 1 λ 2 2 [log(τ 2 /τ 1 ) -s(λ 2 -λ 1 ) 2 /λ 2 1 λ 2 2 ] 2 + q 2 (λ 2 + λ 1 ) 2 /λ 2 1 λ 2 2 1/2 (28)
where r i , i = 1, ..., d represents the eigenvalues of Σ -1 1 Σ 2 , s = 1 -γ and q = π √ 6 . The Rao distance between two Mlap pdfs is:

L(f M lap (x; θ 1 )||f M lap (x; θ 1 )) = [ 1 2 d i=1 (ln r i ) 2 ] 1/2 + 1 2 log {a 1 -(K + R)}/{a 1 -(K -R)} {a 2 -(K + R)}/{a 2 -(K -R)} (29) with, K = 1 2 b 2 2 -b 2 1 a 2 2 -a 2 1 + a 1 + a 2 , and R 2 = b 2 1 +b 2 2 2 + (a2-a1) 2 4 + (b 2 2 -b 2 1 ) 2
4(a2-a1) 2 . Sometimes, the geodesic equations of the marginal probability distribution are difficult to solve as the case of the Gamma distribution. In such cases, we proceed by numerical approximations for the geodesic equations [START_REF] Reverter | Computing the Rao distance for Gamma distributions[END_REF].

Experiments are conducted on the MIT vision texture database (Vistex) [START_REF]MIT vision and modeling group[END_REF]. We consider 30 texture classes as used in [START_REF] Van De Wouwer | Statistical Texture Characterization From Discrete Wavelet Representations[END_REF]. Each 512 × 512 texture image is splitted into sixteen subimages of size 128 × 128 resulting on a database of 480 samples. Then color bands of each subimage are decomposed via the Dual Tree Complex Wavelet Transform (DTCWT). DTCWT presents advantages over the classic DWT (Discret Wavelet Transform), in terms of translation invariance and directional selectivity, since DTCWT provides complex subbands in six orientations at each decomposition level. Every color band (R, G and B) is then decomposed via DTCWT resulting on six subbands r i , g i , b i , i ∈ {1, ..., 6} for each color component (considering only subbands of the second decomposition level). Thus, the dataset to be modeled is constructed by arranging the absolute values of the subbands coefficients in an n × 18 matrix, where n is the number of subband coefficients. As said in the introduction we choose the K-Nearest Neighbor approach for the classification purpose. In the KNN approach, an instance is classified reposing on a similarity measure, and is accorded the label of the majority of its K-Nearest Neighbors. We begin the classification process by dividing our dataset into training and testing sets. From each class of textures, we choose, randomly, Q samples to construct the training set. The rest of the samples are then considered as the testing set. This experiment is repeated 100 times before returning the average classification rate. In our experiments, we vary Q from 2 to 8 in order to test performances for different numbers of training samples. Table 1 shows the average classification rates for two submanifolds of M θ namely Mwbl and Mgam with Rao distance as a similarity measure in comparison with the MGGD model [START_REF] Verdoolaeg | Multiscale colour texture retrieval using the geodesic distance between multivariate Generalized Gaussian models[END_REF], also with the same similarity measure, and then with the approach proposed in [START_REF] Kwitt | A joint model of complex wavelet coefficients for texture retrieval[END_REF], which uses the Monte-carlo based KL divergence with Multivariate Weibull distribution. We observe that for Mwbl and Mgam higher classification rates are achieved for Q = 8, with 95.96% for Mwbl and 95.33% for Mgam, which is better than the rates achieved when using MGGD (94.56% for Q = 8). This is due the flexibility of the Gaussian Copula based models in describing the information of dependence. Also, it can be seen that, in comparison with the KL divergence based approach, results with the Rao distance are slightly better. These little improvements in term of classification rates are valuable, since one can replace the use of the Kullback-Leibler divergence by the Rao distance, and then benefits the advantages of this latter over the KL divergence, as being a distance in the right sense of the word, respecting properties of symmetry and triangularity. Another advantage of the Rao distance, is that for multivariate distributions, and especially those based on copulas, the KL divergence is numerically computed using the Monte carlo method, known as being computationally expensive.

Conclusions

In this work, we have proposed to use the Rao distance as a similarity measure between Gaussian Copula based multivariate distributions. We derived a closed form for the Rao distance of these joint distributions when the Rao distance of the marginal distributions is known. Results in term of classification show the Rao distance can replace the use of the Kullback-Leibler divergence since rates are improved, and then benefit the advantages of the Rao distance.

Table 1 .

 1 Average classification rate for different number of training set.

	Q	2	3	4	5	6	7	8
	Mwbl	86.75 86.90 91.72 92.14 94.25 95 95.96
	Mgam	84.83 85.74 91.76 91.93 92.70 93.62 95.33
	Mwbl+KL [3] 85 86.14 90.65 91.33 93.75 94.81 95.45
	MGGD [2] 84.54 84.98 88.42 90.14 92.49 92.95 94.56

This work was supported by franco-moroccan CNRS-CNRST project STIC 05/10


Davide Canali
email: canali@eurecom.fr

Andrea Lanzi
email: lanzi@eurecom.fr

Davide Balzarotti
email: balzarotti@eurecom.fr

Christopher Kruegel

Mihai Christodorescu

Engin Kirda

A Quantitative Study of Accuracy in System Call-Based Malware Detection

Keywords: H.3.4 [Systems and Software]: Performance evaluation (efficiency and effectiveness), C.4 [Performance of Systems]: Measurement techniques, K.6.5 [Security and Protection]: Invasive software (e.g., viruses, worms, Trojan horses) Security, Experimentation, Measurement Security, evaluation, malware, behavior

Over the last decade, there has been a significant increase in the number and sophistication of malware-related attacks and infections. Many detection techniques have been proposed to mitigate the malware threat. A running theme among existing detection techniques is the similar promises of high detection rates, in spite of the wildly different models (or specification classes) of malicious activity used. In addition, the lack of a common testing methodology and the limited datasets used in the experiments make difficult to compare these models in order to determine which ones yield the best detection accuracy.

In this paper, we present a systematic approach to measure how the choice of behavioral models influences the quality of a malware detector. We tackle this problem by executing a large number of testing experiments, in which we explored the parameter space of over 200 different models, corresponding to more than 220 million of signatures. Our results suggest that commonly held beliefs about simple models are incorrect in how they relate changes in complexity to changes in detection accuracy. This implies that accuracy is non-linear across the model space, and that analytical reasoning is insufficient for finding an optimal model, and has to be supplemented by testing and empirical measurements.

INTRODUCTION

When studying the published results of existing research on behavior-based detectors [5, 6, 8-10, 14, 20, 23], one can make three interesting observations. First, despite their differences, all proposed malware detectors seem to work quite well. The detection rate is typically very high, with very few (or even zero) false positives. The second observation is that, even though each solution is based on a different behavioral model (i.e., type of program abstraction), a clear motivation of why a particular model was chosen is often missing. Finally, the data sets which were used for the experimental evaluations of these systems were often limited to very few benign and malicious samples, calling into question whether the excellent detection results reported would still hold with more extensive and systematic experiments.

The motivation behind these research approaches to behavior-based detection were the increasing limitations exhibited by anti-malware techniques. Recent high-profile incidents such as Operation Aurora [START_REF] Kurtz | Operation "Aurora" hit Google, others[END_REF] and Stuxnet [START_REF] Falliere | Stuxnet introduces the first known rootkit for industrial control systems[END_REF] are instructive examples of the ongoing shift towards stealth and evasion in the malware industry. Anti-malware techniques often rely on byte signatures (i.e., strings or regular expressions of bytes in the malware binary file), which are easily evaded by simple code changes (e.g., run-time packing, obfuscation), as previous work has demonstrated [START_REF] Christodorescu | Testing malware detectors[END_REF][START_REF] Moser | Limits of Static Analysis for Malware Detection[END_REF]. Behavior-based methods rely instead on higher-level, more abstract representations of malicious code, usually using system calls instead of instruction bytes, with the often-stated explanation that system calls capture intrinsic characteristics of the malicious behavior and thus are harder to evade.

Unfortunately, simply transitioning a specification of malicious behavior from using bytes or instructions to using system calls does not guarantee more accurate and more resilient detection. The structure of this specification is important, in terms of how the system calls are organized (i.e., as a sequence of calls, as an unordered set, as a dependence graph), how many system calls are part of the specification, how much of the specification has to match for detection to succeed, etc. The existing work provides data points for different models to consider, but there is no clear understanding of which specification models are most suitable for detection given that malware writers continuously adapt their work to be stealthy and to evade detection. Finally, all these approaches have been tested on very limited datasets including only a handful of benign applications run by the authors on a single machine in a controlled environment.

To overcome this limitation, our goal in this paper is to develop a methodology to systematically test and compare the effectiveness of different models to capture program behavior. We argue that, in order to obtain a better understanding of how the choice of the behavioral model and its parameters influences the quality of malware detection, the detection capabilities of different behavior models have to be tested on a realistic and large-scale data sets. In addition, in order to provide a better understanding of why a particular model works better than others and under which circumstances, our methodology organizes the space of behavioral models along three dimensions: the granularity of atomic program operations, the ways in which these operations relate to each other, and the number of operations included in a specification.

As program operations constitute the basic building blocks of models, we refer to them as behavior atoms. In this work, we focus on using system calls, with and without parameters and with various levels of abstraction, as the atomic operations that models can use to characterize program behavior.

The second dimension captures the ways in which behavioral atoms can be structured and combined together. In particular, we are interested in the ordering constraints that models can formulate on top of these atoms, and the possible structures that these constraints yield. Together these dimensions allow us to explore empirically the design space of specifications over system calls, from unordered sets, to simple sequences, and to general finite state automata.

Given the universe of all possible behavior models that can be expressed based on our atoms and structures, we explore this space by running over 200 different testing experiments against several large and diverse datasets of malicious and benign programs. The datasets consist of program execution traces observed both in a synthetic environment (based on Anubis [1]) and on real-world machines with actual users and under normal operating conditions. By using this mix, we ensure that the representations we consider are not biased towards particular runtime environments, or particular usage patterns. Our datasets consist of a total of 1.5 billion system-calls invoked by over 363,000 unique process executions. This exploration process leads us to observe the existence of limit points beyond which accuracy cannot possibly improve and the non-linearity of accuracy with model parameters. It is clear that only an exhaustive (and experimentally-supported) approach can provide sufficient information to allow us to reason about models in comparison. Thus, the impossibility of generalizing results in a closed form for finite-state models is one of the main contributions of the paper.

We summarize our contributions as follows:

• We present a systematic testing technique to evaluate the quality of behavioral-based detection models. In our experiments, we explore the space of behavioral models by generating over 200 different detection models and over 220 million of specifications, and test each one against large, real-world datasets. • We provide empirical evidence that accuracy varies nonlinearly with any parameters of the specification model space. Our paper shows how, by attempting to general-ize results in a closed form, it is easy to fall into common pitfalls. Therefore, any proposed model has to be driven by a comprehensive experimental validation. • We provide empirical evidence that the training set (i.e., the benign and malicious samples used to construct a specification) has a large influence on the resulting accuracy. This means that any analytically developed detection scheme has to be supplemented with experimental support from large data sets. Finally, we hope that the methodology and the results presented in this paper will provide a benchmark for future malware detector proposals and research efforts.

OVERVIEW

Consider the following scenario: A malware analyst is given the task of deriving a representation from the malware "catch," which nowadays can run at over 55,000 new samples per day [START_REF]McAfee threats report: Fourth quarter 2010[END_REF]. The analyst has to construct an optimal representation from the malware and benign datasets on hand, and then he has to translate the result into the format that is understood by the detection engine (possibly creating multiple signatures in that format). The challenge is to find an optimal representation for the large set of malware samples.

If the resulting representation is to be used in a bytesignature antivirus engine, then the easiest path to get there is to derive the byte signature that best covers the given malware set. Unfortunately, this simple approach can result in a suboptimal outcome because it tries to capture the common behavior in a fairly rigid representation. Suboptimal in our case means that the newly derived byte signature will suffer from false positives or false negatives (and likely from both). Therefore, as attackers started using obfuscation strategies, detectors were forced to move toward more complex representations. The first evolution consisted in using regular expressions over byte sequences [START_REF] Ször | The Art of Computer Virus Research and Defense[END_REF], approach that quickly became obsolete as byte patterns have little predictive power (i.e., they can accurately capture only previously seen malware) and are not resistant to evasion and obfuscation techniques. Other static models, such as byte ngrams [START_REF] Li | Fileprints: Identifying file types by n-gram analysis[END_REF], system dependencies of the program binary [START_REF] Schultz | Data mining methods for detection of new malicious executables[END_REF], and syntactic sequences of library calls [START_REF] Mukkamala | Static analyzer for vicious executables (SAVE)[END_REF][START_REF] Xu | Polymorphic malicious executable scanner by API sequence analysis[END_REF] have also been proposed, but they had limited success.

Researchers have also tried to describe malware in terms of violations to an information-flow policy. Because it is not feasible for performance reasons to track system-wide information flows accurately, the focus shifted on better and better approximations of the information flow. For example, Bruschi et al. [START_REF] Bruschi | Detecting self-mutating malware using control-flow graph matching[END_REF] and Kruegel et al. [START_REF] Kruegel | Polymorphic Worm Detection Using Structural Information of Executables[END_REF] have shown that some classes of obfuscations could be rendered innocuous by modeling programs according to their instruction-level control flow. At the same time, Christodorescu et al. [START_REF] Christodorescu | Semantics-aware malware detection[END_REF] and Kinder et al. [START_REF] Kinder | Detecting malicious code by model checking[END_REF] built obfuscation-resilient detectors based on instruction-level information flow. However, extracting and or collecting instruction-level information is either very hard (from a static point of view) or very inefficient (from a dynamic perspective).

To avoid the previously mentioned limitations and achieve a precise and harder to evade malware characterization, recent research has focused on detection techniques that model the runtime behavior of malware samples [START_REF] Christodorescu | Mining specifications of malicious behavior[END_REF][START_REF] Kirda | Behavior-based spyware detection[END_REF][START_REF] Kolbitsch | Effective and efficient malware detection at the end host[END_REF][START_REF] Martignoni | A layered architecture for detecting malicious behavior[END_REF][START_REF] Stinson | Characterizing bots' remote control behavior[END_REF]. To better illustrate the challenge of extracting a behavioral signature we can use the simple example of Figure 1. On the NtOpenKey (" SYSTEM \ Cu ... 70 B }" , 131097) Nt Quer yVal ueKe y (1640 , " EnableDHCP " , 2) Nt Quer yVal ueKe y (1640 , " DhcpServer " , 2) Nt Quer yVal ueKe y (1640 , " DhcpServer " , 2) NtClose (1640) NtCreateFile ("\\ Device \ ... 70 B }" , 3 , 0) NtClose (1640) (a) Short system-call trace. s1: NtOpenKey s2: NtOpenKey("SYSTEM\Cu ... 70B}", 131097) s3: NtOpenKey, NtQueryValueKey s4: { NtOpenKey, NtQueryValueKey } s5: [ NtOpenKey("SYSTEM\Cu ... 70B", 131097), . . . , NtQueryValueKey(1640, "EnableDHCP", 2) ] (b) Five behavioral specifications derived from (a). left side, there is a brief system-call trace from a program execution, similar to what an analyst would see if he were to run the malware samples in a honeypot. On the right side, we list five possible behavioral representations that match this system-call trace. Each of these behavioral representations is a candidate for use in a malware detector. The first representation, s1, matches all programs whose execution traces include an invocation of NtOpenKey, irrespective of its arguments, while s2 will match only if the invocation has the specified arguments. Behavioral representations s3 and s4 match programs that invoke NtOpenKey and NtQueryValueKey in sequential order and any order, respectively. The fifth representation, s5, matches all programs that invoke NtOpenKey with the specified arguments, followed by any number of arbitrary system calls, followed by an invocation of NtQueryValueKey with the specified arguments. Each of the behavioral representations in Figure 1(b) differs in its expressive power. For example, s1 is less specific than s2 because it does not impose any constraints on program arguments, so a detector using s1 will likely have higher detection rate and higher false positive rate than one using s2. Thus, in a practical scenario, the analyst is faced with the problem of finding the optimal behavioral representation from an extremely large set of closely related, yet slightly different candidates. The automation of this kind of exploratory task of searching for and comparing candidates is exactly what we focus on in this paper.

Table 1 summarizes how the problem was solved by some of the most relevant previous publications in the area of behavioral malware detection. Some of the proposed approaches are specific to detect particular classes of malware, e.g., spyware [START_REF] Kirda | Behavior-based spyware detection[END_REF] or botnets [START_REF] Stinson | Characterizing bots' remote control behavior[END_REF], while others have a broader scope that can cover different domains. The table contains several columns, reporting information about the data source used to build the models and the structure of the model themselves. For instance, Christodorescu et al. [START_REF] Christodorescu | Mining specifications of malicious behavior[END_REF] use automatically constructed models based on direct acyclic graphs of system calls, while Kirda et al. [START_REF] Kirda | Behavior-based spyware detection[END_REF] manually selected a subset of potentially dangerous API calls.

The last two columns of table 1 report the size of the malware and the benign datasets used to test the detection and false positive rates. Unfortunately, these sets are very small and often collected on a single machine in a controlled environment. For instance, MiniMal was tested on six benign applications run for a maximum of 2 minutes each. Finally, the efficiency column describes if the proposed solution is more suitable for runtime detection or for offline malware analysis. We marked a technique as "Detection" if the authors present experiments to support a possible end-user installation of their solution, without taking into account the real performance overhead (that, unfortunately, was often too high to be used in a real environment). In fact, in many cases the authors presented solutions based on complex models (such as graphs enriched with program slices, or multi-layered graphs) that are hard to apply in realtime.

Even though all these approaches seem to provide acceptable results, a motivation of why such complex models are required is still missing. Are simpler behavioral models inadequate or insufficient to detect malware? Which ones are their intrinsic limitations?

To answer these questions, in this paper, we present a bottom-up testing methodology to evaluate behavioral-based representations.

ATOMS, SIGNATURES, AND MODELS

We describe a detection specification as a model that combines a number of signatures, where each signature is formed from atoms that represent basic program operations in a particular temporal and state relation to each other. Conceptually, signatures correspond to low-level program behaviors (e.g., reading a system-configuration file), while models correspond to high-level program behaviors (e.g., exfiltration of sensitive configuration data) that arise from the coupling of low-level operations.

A signature captures a program behavior in terms of the relevant program operations together with the relationships between them. Signatures are the basic blocks used in the malware detection process, where the core operation is the matching of a program against a signature.

According to our approach, we define a signature based on the following three elements:

• A signature atom is the fundamental behavioral element that appears in a program trace. For example, program instructions, library calls, system calls, and system calls together with their parameters are all possible signature atoms. • A signature structure describes how the atoms must be ordered, and in what trace contexts they may appear for a match to occur. An example of a structure is a set, where atoms from the set can be matched in any order, and within any context in an execution trace. • A signature cardinality defines how many atoms are included in the structure. We write A to represent the set of all atoms. A program matches a signature if the program matches the signature atoms according to the structure of the signature.

Definition 1 (Signature Matching). A program P matches a signature s = A, Γ, α if an execution trace of the A model is defined by a set of signatures and an alert threshold. The alert threshold defines how many different signatures must be matched by a program before raising an alert. For example, it is possible to require 4 different sets of 7 system calls, or 15 sequences of 3 high-level actions. We note that models do not require that signatures are matched in any particular order, but just that a minimum number (given by the alert threshold) of signatures are matched.

We can now define what it means for a program to match a model. Intuitively, a program matches a model if it matches its signatures (or at least a minimum number of them).

Definition 2 (Model Matching).

A program P matches a model M = S, t , where S is a set of signatures S = {s1, . . . , sN } and t is the alert threshold, if the program P matches each signature in some set {sj 1 , . . . , sj t } ⊆ S, with 1 ≤ j1, . . . , jt ≤ N .

The definitions for signature and model are sufficiently generic to encompass the vast majority of behavioral representations that have been used or proposed for malware detection. For example, byte signatures are models using program instructions as atoms, with a total ordering relation, and a matching filter that always returns true. Malspecs (aka system-call dependency graphs) are models using system calls as atoms, with a partial ordering relation, and a matching filter that determines whether a depedency relation is preserved by a sequence of system calls. Thus, our model definition gives us the key dimensions along which to explore accuracy.

The number of all the potential models (i.e., the combination of all the possible parameters) that can be extracted from a program is extremely large. The alert threshold is bounded from above by the total number of possible signatures of a particular type. The cardinality of the signature is, in the limit, bounded by the maximum number of atoms in the samples. Finally, the number of signature structures does not even have a theoretical upper bound (given that both the order relation and the matching filter are arbitrary).

MODEL CONSTRUCTION

The fact that the space of all possible models is infinitely large prevents a complete testing exploration in any meaningful sense. We choose, therefore, to limit our exploration to a well-defined region containing the models of practical importance. In this section, we first discuss our choices to constrain the exploration, and then describe our methodology for exhaustively covering the resulting space and efficiently comparing the accuracy of models.

Restricting the Model Space

We define limits for each of the four parameters that characterize a model: atoms, structures, number of signatures, and alert thresholds.

Atoms

In our experiments we consider four types of atoms: system calls, system calls with arguments, actions, and actions with arguments. An action corresponds to a higher-level operation (e.g., reading a file, or loading a library) and it is obtained by grouping together a set of similar system calls (as illustrated in Table 2). For example, reading a file requires more than one low-level operations (at least one to open the file, and one or more to read the content). The action atoms have been defined by us, based on the traditional grouping of system calls by Microsoft into different classes [START_REF] Nebbett | Windows NT/2000 Native API Reference[END_REF].

Structures

We consider three possible structures to combine atoms together: n-grams, tuples, and bags.

An n-gram is a sequence of n atoms that appear in consecutive order in the program execution trace. In the terms of the Definition 1, an n-gram is given by the total order relation Γ = {(a1, a2), . . . , (ai, aj>i), . . . , (an-1, an)} and the matching filter α equal to false everywhere.

A bag of cardinality n (or n-bag) contains n atoms without any particular order relation. Matching between a program and a n-bag signature consists of checking whether each atom in the bag appears at least once in a program execution trace. Formally, a bag signature has an empty order relation, Γ = ∅, and an always-true matching filter α.

A tuple signature of cardinality n (n-tuple) combines the strict order relation of n-gram with the always-true matching filter of bag signatures. A tuple signature is matched by a program if its atoms appear in order, but at any distance from each other, in the program execution trace. We also consider more complex structures derived from combining the three basic structures with themselves in a recursive way. For example, it is possible to build models containing bags of n-grams, n-grams of tuples, or any other combination of the basic structures. We extend our definitions from signatures over atoms to signatures over signatures in the natural way. For example, a k-bag of n-grams is a signature with a bag structure and k n-grams as elements. Matching naturally extends in a similar way, where matching a signature requires the recursive matching of its component signatures. In the case of a bag of k n-grams, the matching requires matching each of the k n-grams in any order.

We observe that not all the structure combinations result in new signature types. For example, n-grams of n-grams, bags of bags, and tuples of tuples do not add complexity because they are equivalent to increasing the cardinality of the basic structure. Other combinations may instead generate models with a confused semantic. For example, an n-gram of bags would require to match in a strict order (without anything else in between) two groups of system calls that can appear in any order and at any distance between each other. In our experiments we excluded these ambiguous cases and we focused on the following non-trivial combinations: bags of n-grams, bags of tuples, tuples of bags, and tuples of ngrams.

These structures may look too simple and "behind the times" when compared with graph models recently introduced in literature (often adopting graph-based structures). However, this focus is deliberate, for two reasons. First, the basic models that we consider should be comprehensively assessed for their limitations before new research delves into increasingly more complex models. Second, combinations of our basic structures (n-grams, bags, and tuples) have the same expressive power as loop-free DFAs and NFAs (although we allow for whole-alphabet self-loops, i.e., Σ ⋆ ). Intuitively, for example, it is possible to enumerate all paths in a loop-free DFA by using a number of tuple signatures.

Signature Cardinality

We decided not to put an upper bound on the number of atoms that can be included in a signature. Instead, we performed an exhaustive exploration by first generating all models with 1 atoms, then all models with 2 atoms, etc. Since this upper bound is extremely high, we kept exploring this direction until the resulting models became too inaccurate to serve any purpose (see Section 5 for more details about the stopping criterion we adopted in our experiments).

Alert Thresholds

A model's alert threshold is naturally limited by the number of signatures in the model. In our experiments, we evaluate all values of the alert threshold, even though most of the useful results are obtained with thresholds below 1,000.

Rationale

One might wonder at this point whether we are restricting ourselves to a set of representations that are too simple to be useful in a malware detector. There is a long history of projects that used finite automata or richer models derived from finite automata to capture program behavior. We observe that models built on recursive combinations of structures can easily reach the same expressivity as finite automata. An additional reason for our focus on basic structures is that we want to restrict our analysis to behavior representations that can be enforced in real time on end users' machines. This excludes representations that need to collect detailed, "inner" information about a program's execution, including information about individual instructions that are executed and detailed data flows between system calls. Collecting such data (in particular, taint information) requires a special runtime for program execution, and it incurs a significant performance penalty. While data flow tracking mechanisms are invaluable for the fine-grained analysis of malware (in a controlled environment), they are typically impractical for malware detectors running on the user's machine. We argue that the mix of our basic structures and the way they can be combined together provides models with significant flexibility and expressiveness to capture program behaviors.

Exploration of the Model Space

Our testing approach is fundamentally experimental, in that we evaluate models against each other by comparing their associated detectors' accuracies against test sets of malware and benign programs. A detailed description of our experimental methodology appears in Section 5.

Number of Possible Signatures

For a program execution trace of length M , there are Mn + 1 possible sequences of length n. Since this number is usually not too high, we are able to construct them all without applying any approximations. The number of bags of cardinality n for an execution trace containing x unique atoms is given by x n . While the set of unique atoms is limited in the case of system calls and actions (since, for example, Microsoft Windows has no more than 350 system calls, depending on the version), the domain of atoms explodes in size for the types of atoms with arguments (i.e., system calls with arguments and actions with arguments).

For tuples, the problem is even bigger. From an execution trace containing x atoms, it is possible to extract x n ntuples.

As it is evident from these simple computations, even extracting all models based on simple structures is often impractical, as the number of signatures to be evaluated grows factorially in the size of the execution trace. Thus, we have to resort to some sort of pruning technique to reduce the number of signatures generated, and therefore the number of test to execute.

Experimentally Pruning the Signature Generation

If the number of atoms is high, generating all bags is computationally infeasible. In such cases, we apply the following pruning rule in order to use information gleaned from models considered up to now to reduce the number of models we consider in the future. A new signature is generated and considered for use in a model if and only if it covers some minimum number Mmin of malware samples that are not already covered by a minimum number Smin of existing signatures. In our experimental evaluation, we use Mmin = 5 and Smin = 20, 000. In other words, for our purpose, a new signature is generated only if it covers at least 5 samples that are not already covered by more than 20,000 existing signatures.

The meaning of these thresholds is as follows. The first threshold (Mmin ) is in place to prevent overfitting (i.e., the creation of signatures that only detect malware samples that are already covered by other signatures). Such signatures are not general enough and, therefore, will not contribute to the detection rate. The second threshold (Smin ) is used to prevent the generation of too many signatures for a single sample. This ensures that the generated signatures are sufficiently diverse to cover different subsets of the malware test set.

We found this simple pruning rule, controlled by only two parameters, to be sufficient in reducing the signature numbers to a manageable level. Because it requires that each new signature has enough "support" in the test set, we know that signatures that are not generated are guaranteed not be part of an optimal model.

MODEL EVALUATION

To evaluate the effectiveness of each model in distinguishing between malicious and benign behaviors, we performed a large number of experiments. In each test, we extracted the set of signatures according to the approach described below, and we then measured the number of false alarms and the number of detected malware samples. In particular, we grouped the false positives by application (i.e., a falsepositive rate of 1% means that 1 application out of 100 was erroneously flagged as malicious), instead of counting individual executions that were detected as malicious. Similarly, the detection rate is measured per sample so that a 1% detection rate indicates that 1 malware sample out of 100 was correctly detected by the signatures set.

Testing Methodology

We used four different datasets in our experiments. The first is a collection of execution traces of 6,000 malware sam-ples randomly extracted from Anubis [1]. This set, that we call malware, includes a mix of all the existing categories (botnets, worms, dropper, Trojan horses, ...), drawn from malware that is active in the wild. The second dataset contains 180 GB of execution traces collected from 10 different real-world machines, where we observed normal day-to-day operation of regular computer users. We label this set goodware. The third dataset (called anubis-good) contains the traces of 36 benign application executed under Anubis. Finally, we used a dataset of execution traces for 1,200 malware samples that have been collected on a different machine than the ones normally used for Anubis (we call this malware-test).

The purpose of having execution traces from different machines for both malware and benign programs is to eliminate any machine-specific artifacts (e.g., machine IDs, user IDs) that introduce noise in our results in the form of falsely discriminative atoms.

The malware dataset, anubis-good dataset, and traces for nine out of the 10 machines in the goodware dataset are used to build the models. The traces from the tenth machine in the goodware dataset and the malware-test dataset are instead used to evaluate the models. The choice of the nine machines used for model construction is done using 10-fold cross-validation approach. The evaluation results presented here are averages across the 10 tests. For any given structure and cardinality, extracting the best model works as follows: 1. We extract the models from the malware set. This phase may include pruning to limit the maximum number of signatures generated to a manageable level. 2. We remove from the models the ones that match the anubis-good dataset. This is required to be able to automatically "clean" our signatures of Anubis-specific items (e.g., the name of the sample file, usernames, etc.). 3. We create the signature by removing from the models extracted so far the ones that match on 9 out of 10 goodware machines. 4. We test the false positive of the signature set on the 10th machine, and the test detection rate on the malware-test dataset. The results are extracted for all possible values of the matching threshold. 5. We repeat Steps 3 and 4 for a total of 10 times, each time excluding a different goodware machine. At the end, we compute the accuracy by calculating the average of both the detection and the false-positive rate between the 10 experiments.

Experimental Setup

All the experiments were executed using two clusters: one with eight 4-core Xeon(R) machines with 16 GB of RAM each, and the second with eight 16-core AuthenticAMD machines with 45 GB of RAM.

Model Construction and Performance Evaluation

In our experiments, we automatically constructed and tested a total of 215 different detection models, containing a total of more than 220 million of signatures. For each of them, we performed 10 cross-validation experiments and we averaged the results. This required more that 2,100 different unique tests. In addition, we designed our matching algorithm to test in parallel for all possible values of the matching threshold. Each experiment required two distinct phases: one to extract the signatures, and one to evaluate the models to measure detection rate and false positives. Extracting the signatures to cover the training set of 6,000 malware samples required a substantial computational power. The time required for this task greatly depends on the complexity of the signatures, and on the number of distinct atoms. It ranged from 20 minutes for n-grams of system calls without parameters to almost 2 days for tuples of system calls with parameters.

Another important factor to take into consideration when evaluating a certain model is the time required by a malware detector to perform the matching. For this reason, we conducted a separate experiment to measure the matching speed on a standard desktop computer (Intel dual Core 2.66 GHz with 4 GB of RAM). We tested our prototype malware detector on execution traces covering twelve hours of user activity and recorded the time and amount of memory required by the detection process. Our results shows that the memory consumption may quickly become a problem when the number of signatures increases (reaching around 1GB for 5 millions signatures). Since the number of signatures is strictly related to the signature's cardinality, using signatures containing too many elements may become impractical in a real world deployment.

Experimental Strategy

For each experiment, we plotted a graph depicting the detection and false positive rates for all possible values of the matching threshold. For example, Figure 2(a) shows the results obtained with 4-grams of system calls with arguments. The graph shows that both false-positive and detection rates decrease when we increase the number of signatures that we require to match in any given sample. With a threshold of 1, the model can detect around 98% of unknown malware samples, but also misclassify almost 45% of the benign applications as malicious. In order to get a false positive rate close to zero, we would need to significantly increase the threshold, thus affecting also the detection rate that would drop down to a mere 35%. While this graph is useful in showing the overall effect of the threshold, it is difficult to tell which is the right value to chose in order to get the best trade-off between false positive and detection.

To answer this question, we also plotted the results of each experiment as a ROC curve, in which the X axis represents the false-positive rate, and the Y axis represents the detection rate. For example, Figure 2(b) shows the ROC curve obtained with the same model of 4-grams of system calls with arguments.

These two graph types are useful to summarize the effectiveness of a given model. However, our experiments generated hundreds of such graphs, and it is not obvious how they can be automatically compared in an objective way. For this reason, we decided to summarize each experiment using three indicators that represent different ways to choose the best configuration on the ROC curve. The first value (Vmax) corresponds to the configuration that maximizes the area under the curve. The second value (V1) is the one in which the model provides a 1% false-positive rate. Finally, the third value we considered (V90) corresponds to the configuration that provides a 90% detection rate.

By studying how these three indicators (emphasized by small circles in the ROC curve in Figure 2(b)) change, it is possible to quickly compare different models, or the effect of different parameters in a given model.

In the rest of the section, we discuss the results of our empirical evaluation with respect to these three indicators (Vmax , V90, and V1), and highlight several interesting discoveries along the way.

Global Comparison

The main objective of our experiments is to study the impact of different parameters on the effectiveness of a malicious behavior detector. Table 3 shows a summary of the best results across all the basic structures and atom types. The model providing the best results is the "2-bags of 2tuples of actions with arguments", closely followed by the "2-tuple of actions with arguments" and the "4-bags of actions with arguments". The first model was able to detect 99% of unknown malware samples with 0.4% false positives (and a variance of 0.00016), while the second achieved a 90% detection with zero false alarms. An interesting observation is that the three indicators (max ROC area, false positives at 90% detection rate, and detection at 1% false-positive rate) do not always provide consistent results. In other words, there are models that have a good V90, but do not perform equally well on the V1 scale, and vice versa. Therefore, the best model also depends on the user's choice of the optimization goal (e.g., detection rate, false-positive rate, or a combination of the two). On the other hand, variance values keep being consistent, and are in average 0.01 on the false positive rate at 90 and 95% detection rate and 0.00001 on the detection rate at 1% false positive rate. The highest variance value we encountered all over the experiments was of 0.033, on a model whose performances are not of high interest (20-grams).

Impact of Pruning Techniques

Before proceeding in the analysis of the different parameters, it is important to verify that the pruning techniques we adopt to generate the models of bags and tuples are not affecting the validity of the results.

As mentioned in Section 4, in order to contain the number of signatures to a reasonable volume, we discarded the signatures that were not detecting at least five malware samples (i.e., not general enough) not already covered by 20,000 other signatures (i.e., too redundant). As a consequence, the signature set extracted with this greedy approach depends on the order in which the samples in the training set are analyzed. Changing the order is equivalent to changing the starting point of the algorithm, and thus the greedy approach would converge to a different solution. To test the effect of the initial condition on our results, we chose a class of models (tuples of system calls with parameters, of various cardinality) and we repeated three times the signature extraction phase with three different orders of the training samples: normal, reversed, and random.

What we observed is that changing the initial conditions sensibly affects the total number of signatures that we extracted. However, the fluctuation in the quality indicators were quite small (e.g., ± 3% for Vmax) suggesting that the properties of the models were affected only marginally by the different pruning. Even more importantly for our results, the trends between different models were not affected at all. For example, the effect on the graphs when moving from a 4-tuple to a 10-tuple did not depend on the starting point of the pruning algorithm.

This gives us confidence that even though the absolute values we present may be slightly inaccurate due to the unavoidable pruning approach, the global trends and the messages we discuss in the rest of the section are valid independent of the approximate algorithm used to extract the signatures.

Impact of Model Threshold

One question we tried to answer with our experiments is whether there exists an optimal range of threshold values that improve the accuracy for all models. As we already described in Section 4, both the detection and the false positive rates monotonically decrease when the matching threshold is increased. The first thing we observed for the experiments is that the drop is faster for the models based on a semantically rich set of atoms (e.g., the syscalls with parameters) than on those that are based on simpler atom sets. Another important observation of our experiments is that the effect the threshold has on a model's accuracy depends on the structure of the model. Figure 3(a) shows three typical detection rate curves obtained for bags, sequences, and tuples of length 4. The graph shows that n-gram models are much more sensitive to the threshold than bag models. In fact, while the detection rate for all n-gram models quickly drops when increasing the threshold, for the bags the accuracy charts exhibit "plateaus" that decrease more slowly.

To summarize, the models that generate a large number of less constrained signatures, such as bags, are less sensitive to the threshold than the models that generate a small number of more specific signatures. Indeed, we found some models (e.g., bags of actions with arguments), for which increasing the threshold between 1 and 1,000 produces a drop of less than 2.5% on the detection rate.

Impact of Signature Cardinality

In our experiments, for each signature type, we repeated the test with increasing cardinality values (in the set [1,[START_REF] Bayer | A view on current malware behaviors[END_REF][START_REF] Bruschi | Detecting self-mutating malware using control-flow graph matching[END_REF][START_REF] Christodorescu | Testing malware detectors[END_REF][START_REF] Falliere | Stuxnet introduces the first known rootkit for industrial control systems[END_REF][START_REF] Kolbitsch | Effective and efficient malware detection at the end host[END_REF][START_REF]McAfee threats report: Fourth quarter 2010[END_REF][START_REF] Stinson | Characterizing bots' remote control behavior[END_REF]30,40,50,60,75]), until we noticed that the detection rate was constantly dropping and the maximum area of the ROC curve decreased below 0.2.

Figure 3(b) shows how the cardinality affects the signature effectiveness in distinguishing benign from malicious behaviors. Because of space constraints, the chart reports only few models; however, a similar behavior was also observed for the other structures as well. For low values of cardinality, in the range of 2 to 10, adding more atoms to the model can improve the results. However, values greater than 10 do not seem to provide any further benefit. In this case, increasing the cardinality only had the effect of producing signatures that overfit the training malware dataset, thus reducing the detection rate.

The accuracy of certain models (like bags and tuples) drops fast when increasing the cardinality, while it decreases slowly for n-grams and models based on actions. Therefore, while bags and tuples reached our Vmax = 0.2 threshold at a size of 10 or 15, for n-grams we had to run experiments up to the 75-grams of actions. The fact that increasing the cardinality does not help to improve the accuracy is an interesting and positive result because extracting and matching signatures that contain a large number of elements is extremely time consuming.

The relation between the cardinality of models and the number of extracted signatures is less clear. For models based on n-grams, the signature number keeps growing linearly with the size of the models. However, the number of signatures that actually contribute to the detection (i.e., the ones that actually match at least one of the samples) shows an opposite negative trend (i.e., they slowly decrease). Again, this is the consequence of the fact that the signatures are overfitting the training set. Models based on bags generated a high number of signatures also for small cardinality. In this case, however, the number of matching signatures is also quite large, often an order of magnitude higher than for any other model. This is instead an example of signatures that are too general, and therefore, easier to match.

Finally, we tested nine cardinality combinations for each recursive model (inner cardinality = 2,3,4 and outer cardinality = 2,3,4). For example, we evaluated 3-bags of 4-grams or 2-tuples of 4-bags. Our considerations for simple models are still valid also for the recursive ones -the only difference being that all the curves dropped much faster. For example, the 3-tuples of n-bags starts with a Vmax of over 0.873 with n = 2, decreases to 0.199 with n = 3, and dropped to 0 for n = 4. This results from the fact that, structure aside, a 3-bag of 4-tuples contains 12 atoms and therefore is roughly equivalent (from a cardinality point of view) to a basic structure of that size.

Impact of Atoms and Signature Structure

The impact of the atom abstraction strictly depends on the structure used to combine the atoms together. In fact, this is the only dimension without a clear winner, with each combination having its own advantages and disadvantages.

For example, n-grams are the only structure that can produce some results also with models based on actions without arguments. However, our experiments show that models based on atoms without arguments contain signatures that are too generic. Therefore, also in the few cases in which they were able to reach the 90% detection level, the number of false alarms was, in the best scenario, already over 30%.

N -grams are also the best structure for low-level atoms (e.g, system calls), while bags and tuples provides the best results when combined with high-level atoms (e.g., actions). At a closer inspection, for models based on system calls, n-grams perform better than bags which in turn perform better than tuples. For models based on actions, the accuracy impact is reversed, with tuples performing better than bags, which perform better than n-grams.

Finally, the experiments on recursive structures confirmed the fact that tuples and bags tend to provide better results than sequences, especially when combined with actions with arguments. In fact, the "2-bags of 2-tuples of actions with arguments" was the best models among all our experiments (with respect to the max area of the ROC curve) achieving a Vmax = 0.99 and a V90 = 0.4%.

A Quick Look Inside the Models

In order to better understand why some models perform better than others, we took a closer look at some of the models we generated in our experiments. In particular, we extracted for each model the top 20 signatures contributing to the detection rate, and the top 20 signatures that were responsible for the false positives.

The first observation is that the signatures based on bags or tuples tend to be more homogeneous, picking only the combination of atoms that may appear less frequently in normal programs. On the other side, n-grams are forced to combine atoms that appear in a strict order, and therefore often contain more common calls about registry and file system operations. The advantage of tuples over bags is the fact that they can contain repetitions. For example, one of the top signatures of the 2-tuple of n-grams with arguments contains a repetition of the same NtReleaseMutant system call. The same call never appears in the top 20 for bags structures. In fact, the presence of only one of these calls was one of the main cause of false alarms.

Looking at the type of system calls included in the top signatures does not provide any useful insight. For example, NtQueryValueKey is an important item in the detection of models based on bags, but it is a main cause of false alarms for n-grams models. On the contrary, the picture is more clear when looking at models based on actions. In this family, one clear trend is the fact that the detection rate of good models is always dominated by the LoadLibrary atom. This high-level action summarizes many operations in the system-call world, and was therefore more difficult to express in models based on them. A second result is that the signatures responsible for false positives are very often based on actions related to registry operations.

To conclude, we also looked at the presence of particularly sensitive parameter values. For example, we checked ten registry keys associated to autostart locations, reported by Bayer et al. [START_REF] Bayer | A view on current malware behaviors[END_REF] as common in malicious samples. Most of the keys never appeared in the top-20 signature sets and few of them only appear as causes for false positives. However, there was one interesting exception, in that the registry key SOFTWARE/Microsoft/Active Setup/Installed Components/ was present in the top-20 signatures of 7 different n-grams models, but never appeared as a top cause of false alarms.

THE IMPORTANCE OF TESTING

Analyzing models beyond the ones built on signatures with simple structure requires a concerted effort to address the explosion in the number of candidate models. For example, if the number of tuple models over atoms is factorial in the size of the execution trace, then computing all models of bags of tuples is not feasible. Therefore, it may be tempting to follow some a priori rules, maybe based on intuitions about the models and their accuracies. Unfortunately, our experimental results indicate that, in general, no valid rules of this form exist, and that pruning rules should not be derived analytically without a solid experimental testing support.

Fallacy: Increasing the specificity of a component in a model improves the model's accuracy.

When the cardinality of a signature is increased to add more atoms to it, the signature becomes more specific and, therefore, less likely to match on both the goodware and the malware datasets. The result is that, intuitively, a model based on 3-grams should generate less false positives than a model based on 2-grams.

However, trying to extend the property of a signature to the property of the models based on that signature is a very common and dangerous pitfall. In fact, since altering the behavioral model alters the number of signatures that are generated, the overall results could often go against the common sense (e.g., making the signatures more specific can increase the number of matches of the entire model).

For example, we can consider the very simple scenario illustrated in Figure 4. The malware set contains only one sample that executes five atoms (a1...a5), and the goodware dataset contains only one process that executes seven atoms (again a1...a5 but in a different order). The bottom part of the figure shows some of the models that can be extracted from the two datasets (the signatures in each model are the ones that match the malware samples but never appear in the goodware one). The 3-grams model contains three signatures, the first of which, a1, a2, a3 , is not covered by any signature in the 2-grams model. Therefore, any program executing those three actions in a row would trigger a false alarm in that model, but not in the one with a lower cardinality (i.e., by increasing the cardinality we possibly increase the detection and false positive rates). Therefore, the actual effect of changing the cardinality of a model can only be measured experimentally, as we did earlier in this section.

Fallacy: Moving to a more selective model structure improves the model's accuracy.

Different structures are comparable in terms of their accuracy only when considering one signature at a time. For instance, sequences are more specific than tuples that, in turn, are more specific then bags. Hence, one may erroneously think that, keeping all the other parameters constant, moving from a sequence to a bag would improve the detection rate but also the false positives.

However, a quick look at the example in Figure 4 is enough to understand that this relationship between signatures does not hold at the model level. For example, the bag models are all empty, the 2-tuple contains only one signature, and the 2-grams contains two. The situation is not much better Malware: (a1, a2, a3, a4, a5) Goodware: (a3, a1, a2, a5, a4, a2, a3) 2-grams : a3, a4 , a4, a5 3-grams : a1, a2, a3 , a2, a3, a4 , a3, a4, a5 2-tuple : [a4, a5] 3-tuple : [a1, a3, a4], [a1, a3, a5], [a1, a4, a5], [a2, a3, a4], [a2, a3, a5], [a3, a4, a5] k-bags : ∅ This discussion illustrates that it is not possible to generalize results in a closed form. Therefore, an analysis of the model space has to be necessarily informed and driven by a comprehensive experimental evaluation. Otherwise, the use of intuitive yet wrong rules would erroneously eliminate certain models from consideration.

CONCLUSION

In this paper, we propose a systematic approach to measure how the choice of behavioral models influences the quality of a malware detector. We achieve our goal through a large set of testing experiments in which we explore the space of many possible behavioral models. Our findings confirm that the accuracy of certain models is very poor, independently of the values of their parameters. In general, the best models are the ones that rely on few, high-level atoms with their arguments. Finally, our experiments show how each parameter impacts the final result and how they should be chosen in order to maximize the accuracy and reduce the false alarms.

Figure 1 :

 1 Figure 1: A program execution trace and five examples of behavioral specifications that match it.

  (a) Detection and false-positive rates by alert threshold. (b) ROC curve.

Figure 2 :

 2 Figure 2: Accuracy for models of 4-grams of system calls with arguments.

Figure 3 :

 3 Figure 3: Matching thresholds and impact of cardinality for various models.

Figure 4 :

 4 Figure 4: Example of Behavioral Models

Table 1 :

 1 Summary of the main behavioral-based approaches Note that α and Γ together capture what we informally refer to as the structure of a signature.

	Approach	Data	Model Type	Model Extraction Efficiency	Malware Set	Benign Set
		Source
	Kirda et al. [9]	API Calls API Blacklist	Manual	Analysis	33	18
	MiniMal [6]	Syscalls	Graph	Automated	Detection	16	6
	BotSwat [20]	System &	Tainted Args in	Manual	Detection	6	8
		API Calls	Selected Calls
	Martignoni et al. [14]	Syscalls	Layered Graphs	Manual	Analysis	7	11
	Kolbitsch et al. [10]	Syscalls	Graph	Automated	Detection 563 (6 families)	5

program P contains each atom in the set A only in the order specified by Γ and separated only by atom strings specified by α, where:

• A ⊆ A is a set of atoms, • Γ ⊆ A × A is

an order relation between atoms, and • α : Γ × A + → {true, false} is a matching filter restricting what atom substrings the program execution trace can contain between two matched signature atoms (i.e., α (si, sj), x = true means that a match is allowed on a program trace containing the substring sixsj, for some string of atoms x).

Table 2 :

 2 The four types of atoms considered in this study.

	Atom Type	Examples
	system call	NtOpenFile, NtClose, . . .
	system call with arguments	NtOpenFile(104860, "C:\WINDOWS\system32\Msimtf.dll", 5, 96), NtClose(100)
	action	ReadFile, LoadLibrary, . . .
	action with arguments	ReadFile("C:\WINDOWS\REGISTRATION\R00000000000F.CLB"), Loadibrary("KNOWNDLLS\NTDSAPI.DLL")

Table 3 :

 3 Evaluation summary of different types of models.

	Model	Cardinality Range Vmax Best Cardinality	V90	V1
	n-grams of syscalls	2-40	0.615	10	31.7% 4.1%
	n-grams of syscalls with args	2-40	0.775	3	15.8% 43.3%
	n-grams of action	2-75	0.423	15	62.2% 0.4%
	n-grams of action with args	2-75	0.737	2	27.1% 45.9%
	bags of syscalls	1-10	0.127	3	-	12.8%
	bags of syscalls with args	1-20	0.736	1	26.4% 43.3%
	bags of actions	1-10	0.004	1	-	-
	bags of actions with args	1-15	0.970	4	0.4% 97.3%
	tuples of syscalls	2-10	-	-	-	-
	tuples of syscalls with args	2-10	0.616	2	-	28.0%
	tuples of actions	2-10	-	-	-	-
	tuples of actions with args	2-10	0.987	2	0.0% 99.2%
	bags of n-grams of syscalls	2-4/2-4	0.500	2/2	-	8.2%
	bags of n-grams of syscalls with args	2-4/2-4	0.648	2/4	-	30.2%
	bags of n-grams of action	2-4/2-4	0.111	3/4	-	-
	bags of n-grams of action with args	2-4/2-4	0.529	2/3	-	22.0%
	bags of tuples of syscalls	2-4/2-4	-	-	-	-
	bags of tuples of syscalls with args	2-4/2-4	0.497	2/2	-	33.8%
	bags of tuples of action	2-4/2-4	-	-	-	-
	bags of tuples of action with args	2-4/2-4	0.990	2/2	0.42%	-
	tuples of n-grams of syscalls	2-4/2-4	0.509	2/2	-	2.9%
	tuples of n-grams of syscalls with args	2-4/2-4	0.624	2/3	-	26.5%
	tuples of n-grams of action	2-4/2-4	0.142	3/4	-	0.1%
	tuples of n-grams of action with args	2-4/2-4	0.536	2/2	-	24.9%
	tuples of bags of syscalls	2-4/2-4	-	-	-	-
	tuples of bags of syscalls with arguments	2-4/2-4	0.480	2/2	-	32.4%
	tuples of bags of actions	2-4/2-4	-	-	-	-
	tuples of bags of actions with arguments	2-4/2-4	0.873	2/2	-	-

ACKNOWLEDGEMENTS

The research leading to these results was partially funded from the EU Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 257007, by the NSF grant CNS-1116777, and by the i-Code project.

We would like to thank Seeweb srl for lending us part of the machines in their cluster for conducting our experiments.


Adriana Aguilera González

Didier Theilliol

Manuel Adam Medina

Carlos Manuel

Astorga Zaragoza

Mickael Rodrigues

A Aguilera-González

M Adam-Medina

C M Astorga-Zaragoza

Sensor fault and unknown input estimation based on proportional integral observer applied to LPV descriptor systems

Keywords: Proportional-Integral Observer, Descriptor Systems, Linear Matrix Inequalities (LMIs), Fault Diagnosis and Isolation (FDI)

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Recent researches in Fault Detection and Diagnosis (FDD) design schemes, especially model-based FDD, are focused on systems modeled by coupled differential and algebraic equations (DAE's). Descriptor systems constitute an important class of systems of both theoretical and practical interest, which include, chemical and biological processes, interconnected large-scale systems, electrical circuits systems and robotic manipulators, among others. In this way, much research has aimed at generalizing existing theories, especially in the time domain, from normal systems to descriptor systems, which include controllability and observability [START_REF] Yip | Solvability, Controllability, and Observability of Continuous Descriptor Systems[END_REF]), feedback control [START_REF] Jiang | Memory State Feedback Control for Singular Systems with Multiple Internal Incommensurate Constant Point Delays[END_REF]), observer design [START_REF] Koenig | Observer Design for Unknown Input Nonlinear Descriptor Systems via Convex Optimization[END_REF]) and robust control [START_REF] Yang | Robust Passive Control of Singular Systems with Uncertainties[END_REF]).

Linear Parameter Varying (LPV) approach, can be used to convert a nonlinear system into a multiple model form. The transformation is realized without loss of information. LPV systems can be seen as nonlinear systems that are linearized along a trajectory determined by the parameter vector that it is assumed measurable [START_REF] Toth | A behavioral approach to LPV systems[END_REF]). Many physical systems exhibit parameter variations due to non-stationary or nonlinear behavior, or dependence on external variables. For such processes, the theory of LPV systems offers an attractive modeling framework. In this way, some authors have proposed to represent the systems using the LPV approach [START_REF] Cerone | Stabilization of a Riderless Bicycle [Applications of Control[END_REF]).

In LPV systems, the model parameters are assumed as functions of a time-varying signal, the called schedulingvariable (ε(θ)). Based on such representation some authors as [START_REF] Ichalal | Fault diagnosis for Takagi-Sugeno nonlinear systems[END_REF], have developed methods for state estimation and fault diagnosis in nonlinear systems described by Takagi-Sugeno multiple models. Or as in [START_REF] Hamdi | State estimation for polytopic LPV descriptor systems: application to fault diagnosis[END_REF], where a polytopic Unknown Input Observer for LPV descriptor systems is designed to estimate states of the system in presence of unknown inputs. In the work of [START_REF] Astorga | Sensor fault diagnosis for a class of LPV descriptor systems[END_REF], a strategy for detection and isolation sensor faults using a bank of residuals within a Generalized Observer Scheme (GOS) is presented. This strategy for fault estimation doesn't take into account the effects of disturbances and other uncertain factors.

Starting from LPV descriptor representation of the nonlinear systems, the present paper proposes sufficient conditions for the design of a Proportional-Integral Observer (PIO) that estimates the states of the system and the fault, even in the presence of unknown inputs. In contrast to [START_REF] Hamdi | Fault Detection and Isolation for Linear Parameter Varying Descriptor Systems via Proportional Integral Observer[END_REF], who only consider constant actuator faults and disturbances with slow variation, we consider here dynamic sensor faults in spite of unknown inputs which extends the range of possible scenarios in a real plant.

The model for sensor faults presented in this paper uses an increase in the system equations. This increase is an auxiliary state (or more in case of multiple faults) that represents the dynamic fault and in effect, converts the sensor fault as an actuator fault, which enables to estimate the fault as an new state. This paper presents a fault diagnosis scheme based on GOS for incipient or abrupt faults in descriptor systems, which is robust against unknown inputs because the disturbance distribution matrices are considered known, this fact allows its uncoupling. This observer is characterized by a integral term on the output error to estimate the unknown input. The stability and the convergence properties are ensured by using Linear Matrix Inequality (LMI's). The method used to model sensor faults, is based on the work of [START_REF] Park | On the representation of sensor faults in fault detection filters[END_REF], where the sensor faults are presented as pseudo-actuator faults.

LPV DESCRIPTOR SYSTEMS

Consider the following continuous-time nonlinear descriptor system:

E ẋ = F (x(t), u(t), d(t)) y(t) = Cx(t) (1)
where x(t) ∈ R n is the state vector, u(t) ∈ R m with (m < n) is the control input vector. y(t) ∈ R p and d(t) ∈ R l are the measurement output and the unknown bounded process disturbance vectors. E ∈ R q×n is a singular matrix with rankE ≤ n and F (•) is a smooth function. The linearization of the function F (•) by Taylor series around ε i operation points (x i , u i ) gives a set local linear descriptor models with the following descriptor linear system representation [START_REF] Hamdi | Robust H ∞ fault diagnosis for multi-model descriptor systems: a multi-objective approach[END_REF]):

E ẋ(t) = Ax(t) + Bu(t) + Rd(t) y(t) = Cx(t) (2)
where E, A ∈ R q×n , B ∈ R k×n , R ∈ R l×n and C ∈ R m×n are known constant matrices. With the following assumptions as in [START_REF] Darouach | Reduced-Order Observer Design for Descriptor Systems with Unknown Inputs[END_REF]:

Assumption 1: It is assumed that the triplet (E, A, C) is observable if: rank sE -A C = n ∀s ∈ C
where C is the set of complex numbers.

Assumption 2: It is assumed that the impulsive terms of the system are observable (the triplet (E, A, C) is Impulse-Observable) if:

rank E A 0 E 0 C = n + rank(E)
As is proposed in [START_REF] Hamdi | Robust H ∞ fault diagnosis for multi-model descriptor systems: a multi-objective approach[END_REF], (1) can be represented by the polytopic LPV descriptor structure as follows:

E ẋ(t) = Q i=1 ε i (θ(t)) [A i x(t) + B i u(t) + R i d(t) + ∆x i ] y(t) = Cx(t) (3)
where E, A i ∈ R q×n , B i ∈ R k×n , R i ∈ R l×n and C ∈ R m×n are known constant matrices. ∆x i represents the contribution of small signals due to the linearization of the system, i.e., is a vector that depends of the i th th operating point. This representation is defined as a multi-linear system where the matrices are set by known operation points.

LPV descriptor system is represented into a polytopic domain. The vertices of this polytope are called the submodels of this representation, i.e., the parameter θ(t) varies in a convex polytope of vertices θ i such that θ(t) ∈ Co{θ : θ 1 , θ 2 , ..., θ Q } with Q as the total number of local models. These submodels are combined by weighing functions to yield a global model. With respect to LPV systems, an additional assumption is cited:

Assumption 3: Let us consider that: i). θ(t) is bounded, and ii). θ(t) is on-line accessible and fault-free.

ε i (θ(t))
is the weighting function that defines the relative contribution of each local model to build the global model. This weighting function is constructed in such a manner that complies with follow property of the convex sum:

i=1 ε i (θ(t)) = 1, 0 ≤ ε i (θ(t)) ≤ 1 (4)
This polytopic structure makes it possible to represent any nonlinear behavior. The next section is dedicated to develop a method to detect and estimate the sensor fault in order to provide an efficient monitoring tool in the operator's decision.

REPRESENTATION OF THE SENSOR FAULTS

Let us consider the sensor fault f s (t) and the disturbances d(t) given by:

E ẋ(t) = Q i=1 ε i (θ(t)) [A i x(t) + B i u(t) + R i d(t) + ∆x i ] y(t) = Cx(t) + Jf s (t) (5)
where f s (t) ∈ R n f is a fault vector which represents the evolution of the fault and J represents the sensor fault distribution matrix. Let us consider f s (t) = β(t f )f (t) characterizes the time profile of a fault that occurs at some unknown time t f . More specifically, β(t f ) is a smooth function modeled by:

β(t -t f ) = 0, t < t f 1 -e -ς(t-t f ) , t ≥ t f (6)
where the scalar ς > 0 denotes the unknown fault evolution rate. Small values of characterize slowly developing faults, also known as incipient faults. For large values of ς, the time profile approaches a step function, which models abrupt faults. Based on [START_REF] Park | On the representation of sensor faults in fault detection filters[END_REF], the LPV descriptor system (5) can be represented such as:

Ē ẋ(t) = Q i=1 ε i (θ(t)) Āi x(t) + Bi ū(t) + Ri d(t) + ∆x i y(t) = C x(t) (7)
where x(t) ∈ R n+n f is the augmented state vector defined as x(t) = x(t) f s (t) , the control vector is defined as ū =

[ u ξ ] and the matrices are given by:

Ē = E 0 0 I n f C = [ C J ] Āi = A i 0 0 α n f
with a sensor input defined as: ξ = ḟsαf s , and

Bi = B i 0 0 I n f Ri = R i 0 ∆x i = ∆x i 0
where 0 is a zero matrix of appropriate dimension. The term α n f represents a diagonal matrix of appropriate dimension where α > 0 can be considered as an additional degree of freedom in the observer design. The fault can be modeled by a linear system of arbitrary order, but this fact depends of the characteristics of the fault.

It is a well-known result that the necessary and sufficient condition for detectability, is that the fault event vector is detectable, i.e., if and only if ( Āi , C) is observable [START_REF] Park | On the representation of sensor faults in fault detection filters[END_REF]). In addition, this requirement may be assumed in terms of the original system, i.e., if (A i , C) of the system (5) is observable.

PROPORTIONAL INTEGRAL OBSERVER (PIO)

The fault reconstruction is achieved considering a descriptor system represented by the polytopic LPV descriptor model ( 7), the equations of the PIO are [START_REF] Hamdi | Fault Detection and Isolation for Linear Parameter Varying Descriptor Systems via Proportional Integral Observer[END_REF]):

ż(t) = Q i=1 εi(θ(t)) Niz(t) + Gi ū(t) + Liy(t) + Hi d(t) + ∆zi x(t) = z(t) + My(t) ḋ(t) = Q i=1 εi(θ(t))Φi(y(t) -ŷ(t)) (8)
where x(t), z(t) ∈ R n+n f and d(t) ∈ R p are the estimate state vector, state observer vector and estimate unknown input respectively. N i , G i , L i , H i , ∆z i , M and Φ i are matrices for the PI observer. From (7) the estimation error is equal to:

ē(t) = x(t) -x(t) ē(t) = (I n+n f -M C)x(t) -z(t) (9)
where I n+n f represents the identity matrix of order n+n f , then on can define a real matrix U ∈ R (n+n f )×(n+n f ) calculated as:

U Ē = I n+n f -M C (10)
and, for [ Ē C] T as full rank column, is possible to calculate U and M , such that:

U M = Ē C + ( 11
)
where the superscript + represents the inverse generalized matrix, and the estimation error can be rewritten as:

ē(t) = U Ē x(t) -z(t) (12)
A restriction of the PIO is to suppose that the unknown inputs are bounded and their dynamic is slow, i.e., ḋ(t) ≃ 0. Then, for δ(t) = d(t) -d(t), the unknown input derive is defined as:

δ(t) = -ḋ(t) (13)
The estimation error dynamic is written as:

ė(t) = Q i=1 ε i (θ(t)) (U Āi -L i C -N i U Ē)x(t)+ (U Bi -G i )ū(t) + (U Ri -H i )d(t)+ (U ∆x i -∆z i ) + H i δ(t) + N i ē(t)] ( 14
)
where the following conditions can be defined:

U Āi = N i U Ē -L i C (15) G i = U Bi (16) H i = U Ri (17) ∆z i = U ∆x i (18)
From (3), ( 13) and ( 14), the estimation error and the unknown input dynamic is:

ė(t) = Q i=1 ε i (θ(t))(N i ē(t) + H i δ(t)) (19) δ(t) = Q i=1 ε i (θ(t))(-Φ i C)ē(t) (20)
and the following function can be established:

ė(t) δ(t) = Q i=1 ε i (θ(t)) N i H i -Φ i C 0 ē(t) δ(t) (21)
Then, the state estimation error (21) converges asymptotically to zero if the real part of the eigenvalues of

N i H i -Φ i C 0
< 0, i.e., are stables. From ( 10) and (15), the matrices N i , can be determined as follows:

N i = U Āi -(L i -N i M ) C (22)
and defining K i = L i -N i M , the matrices L i can be calculated. Then, (21) can be rewritten as:

ė(t) δ(t) = Q i=1 ε i (θ(t))( Ȃi -Ki C) ē(t) δ(t) (23)
where Ȃi = U Āi H i 0 0

, Ki = K i Φ i and C = [ C 0].
Then, the PI observer (8) for a LPV descriptor system with inputs unknown (3) exists and their estimation error converges asymptotically to zero, if and only if, the pairs ( Ȃi , C) are detectable ∀i = 1, 2, ..., Q. This observer is asymptotically stable if exists a positive definite symmetric matrix P and matrices W i = P Ki such that the following LMI holds:

( ȂT i P + P Ȃi -CT W T i -W i C) < 0, ∀i ∈ 1, 2, ..., Q. (24)
Observer gains can be calculated from Ki = P -1 W i . For ensuring the stability and convergence of the observation error, it is possible to define in the left part of the complex plane a bounded area S with a line of abscissa (-σ) where σ ∈ R + , and the LMI's defined in ( 24) must be replaced by the following inequalities:

( ȂT i P + P Ȃi -CT W T i -W i C) + 2σP < 0, ∀i ∈ 1, 2, ..., Q. ( 25
)
then, consequently x(t) will asymptotically converge to x(t) and d(t) to d(t).

ILLUSTRATIVE EXAMPLE

Consider a continuous-time LPV descriptor nonlinear system (1), described by:

ẋ1 (t) = -1.5x 2 1 (t) + 0.2x 3 (t)x 4 (t) + d(t) ẋ2 (t) = -u 1 (t)x 2 1 (t) -x 4 (t)x 2 3 (t) -2 (t) 0 = 0.5x 2 (t) -x 3 (t) + 0.2x 4 (t) 0 = -x 2 2 (t) + x 2 3 (t) -2x 4 (t) + u 2 (t) y(t) = 1 1 0 1 0 0 0 1 0 0 1 0 x(t) + v k , (26)
where u 1 (t) and u 2 (t) are constant signal of magnitude 10 and 7 respectively. v k ∈ R p is the measurement noise that is modeled as Gaussian white noise with variance center 0.01. For simulation purposes, an unknown input is modeled as a rectangular signal applied for 10 ≤ t ≤ 25.

LPV multi-model representation of the nonlinear dynamic system is given by the follow set of matrices: The weighting functions are calculated according to (4), ∀i = 1, . . . , Q with Q as the total number of local models considered, in this case Q = 3. The weighting functions ε i (θ(t)) characterize the dynamic behavior of the descriptor nonlinear system and its evolution depends of parameters that are functions of the state x 3 (t). These functions are defined as:

E = 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 , C = 1 1 0 1 0 0 0 1 0 0 1 0 , R i = R = 1 0 0 0 A 1 = -0.8775 0
ε i (t)(x 3 (t)) = µ i (x 3 (t)) 3 i=1 µ i (x 3 (t)) (27)
Assumption 4: The state x 3 (t) is defined as free of faults and always measurable.

The parameters trajectory is determined by the behavior of the system variables as:

µ 1 (x 3 (t)) = exp - 1 2 x 3 (t) + 5 2 2 µ 2 (x 3 (t)) = exp - 1 2 x 3 (t) 2 2 µ 3 (x 3 (t)) = exp - 1 2 x 3 (t) -5 2 2 (28)
5.1 Fault-free case.

For initial conditions, x 0 = [0.4 -0.004 0.755 3.785] T and x0 = [0 0 0 0] T , the nonlinear states and its estimated are depicted in the Fig. 1 in fault free case. In this figure the quick convergence of the observer to LPV descriptor nonlinear system can be seen.

Sensor-fault case.

A vector f s (t) ∈ R n f with n f = 1 and β(tt f ) = 1e ς(t-t f ) with ς = 0.01, is applied for y 2 in time 21 ≤ t ≤ t f and f s (t) = (2sin(5t -10)). To design the observer for the LPV descriptor system (5) the augmented system should be constructed as (7). Then, the matrices U and M can be calculated by ( 11) such that U Ē + M C = I n+n f . Using the Yalmip Toolbox [START_REF] Lofberg | A Toolbox for Modeling and Optimization in MATLAB[END_REF]) or the LMI Control Toolbox [START_REF] Gahinet | LMI Control Toolbox. LMI Control Toolbox User's Guide[END_REF]), it is possible to compute a solution satisfying the inequality (25), and to determine the observer matrices K i and Φ i respectively: In sensor fault case, the states and its estimated are depicted in the Fig. 2. In this figure only the state x 3 is well estimated, this is because it is the only measurement that is considered not affected by the fault. For simulation purposes, an unknown input is modeled as a rectangular signal applied for 10 ≤ t ≤ 25. The estimation of the unknown input is illustrated in the Fig. 3. From the procedure of augmented system, given in the Section 3, is possible to use the PIO for estimate the dynamic behavior of the sensor fault as an additional state. Fig. 4 shows the signal of the sensor fault and their estimation. For the purpose of fault isolation, a bank of observers is built as a generalized LPV descriptor observer scheme (based on GOS Frank (1994)). This scheme provides an estimator dedicated to a certain sensor is driven by all outputs except that of the respective sensor, i.e., where each one of the them is driven by all inputs and all outputs except the k th measurement variable. The measure y k is not used in the k observer due to the fact that y k is assumed corrupted. This scheme allows one to detect and isolate only a single fault in any of the sensors, however, with increased robustness with respect to unknown inputs.

K 1 =   1.
For the bank of observers, the following LPV descriptor system in considered:

E ẋ(t) = M i=1 ε i (θ(t)) (A i x(t) + B i u(t) + R i d(t) + ∆x i ) ζ k (t) = Cj x(t) + Jj f s (t) (29)
with Cj and Jj the matrix and sensor fault distribution vector respectively, without the k th row. The bank of observer generates an incidence matrix (Table 1) where a signal that is obtained from the residuals defining the effects associated with the fault.

Table 1. Incidence Matrix

Fault F 1 F 2 F 3 ||y -ŷ|| 1 1 1 ||ζ 1 -ζ1 || 0 1 1 ||ζ 2 -ζ2 || 1 0 1
The bank generates residuals different to zero, otherwise, only the observer which is insensitive to a sensor fault F k effects generates a unique residual with a media zero. The performance of the fault diagnosis system is illustrated for faults on the sensors y 1 and y 2 , the sensor y 3 is considered free of faults. Figs. 5-6, shows the results of the bank observers according to the incidence matrix, only the observer designed insensitive to a sensor fault provides a residual vector equal to zero means. Only a single sensor fault can be detected at a time.

This approach mainly considers the case of sensor fault. It is possible also to consider the actuator fault case, but it is important that into the LPV model of the system, the parameters considered to build the weighting functions cannot depend of the inputs of the system or any dependent variable of the inputs, i.e., the parameters should be free faults according to assumption A3. If this is the case, actuator faults can be estimated also using the same PI-Observer if they are modeled as unknown inputs of the system.

CONCLUSIONS

This paper has presented a sensor fault diagnosis method to detect and isolate sensor faults in LPV descriptor systems. This proposed method is easy to implement because only matrix manipulations were made to represent the system and its dynamics completely (states, unknown inputs and faults) into a LPV model. This allows the observer designed based on the LPV model, to provide reliable information on the status of the process. Through PIO approach, the error dynamics converges to zero, as well as the sensor faults f s (t) and the unknown inputs are estimated simultaneously. The diagnosis scheme is based on a PIO presented in [START_REF] Hamdi | Fault Detection and Isolation for Linear Parameter Varying Descriptor Systems via Proportional Integral Observer[END_REF], who only considered constant actuator faults, while we considered here dynamic sensor faults in spite of unknown inputs. Conditions to ensure the existence and the stability of the proposed scheme by using LMI formulation were established. The PIO was designed to estimate simultaneously the sensor fault and the unknown input and also, it was used to build a bank of observers to isolate adequately sensor faults. The effectiveness of this algorithm was evaluated via simulations using a numerical example.

Fig. 1 .

 1 Fig. 1. States of nonlinear system and their estimates.

Fig. 2 .

 2 Fig. 2. States of nonlinear system and their estimates.

Fig. 3 .

 3 Fig. 3. Unknown input estimated (disturbance).

Fig. 4 .

 4 Fig. 4. Sensor fault and corresponding estimated.

Fig. 5 .

 5 Fig. 5. Residual vector with a fault in the first sensor.

Fig. 6 .

 6 Fig. 6. Residual vector with a fault in the second sensor.

ACKNOWLEDGEMENTS

The first author thanks CONACYT, Mexico, for their financial support and CRAN, France, for the research support to develop this work.