Cornelia Vacar

Jean-Franc ¸ois Giovannelli

Ana-Maria Roman

BAYESIAN TEXTURE MODEL SELECTION BY HARMONIC MEAN

Keywords: Texture, model choice, harmonic mean, Bayes, Metropolis-Hastings

The paper presents a model selection method for texture images, more specifically, it finds the most adequate model for the pixels' interaction. This approach relies on a Bayesian framework, that probabilizes all the quantities and determines the joint a posteriori law for the models and the parameters. In order to compute the a posteriori model probabilities, the model parameters are marginalized by means of sampling, performed independently for each model in a within-model sampling using a Metropolis-Hastings (M-H) algorithm. The resulting chains are used to compute the evidence of each model by an harmonic averaging of the likelihoods computed for the aforementioned sampled values. The work presented in the following represents a complex formalism based on state of the art methods for parameter estimation, model selection techniques and sampling algorithms, the novelty being the design of such an approach for a texture model selection problem. An image processing application of this kind raises serious difficulties regarding the large amount of data, the data correlation and the highly non-linear dependencies of the data with respect to the parameters. Despite these challenges, our method successfully solves the problem of texture model selection and parameter estimation.

INTRODUCTION

Model selection can prove to be an important tool in data analysis, signal processing and, as shown in the following, even in image processing. The goal is to select the model that best describes the data, concurrently with computing the parameters of that model. In our case, the data is the observed image, denoted by X, the models are M = k, with k = 1, .., K, and each model is driven by the parameters θ k . In such a setting, the Bayesian framework is conceptually well adapted and allows the development of a unified approach to solve the twofold problem.

The use of the Bayesian paradigm naturally leads to handling the joint law for the models, the parameters and the data, from which the a posteriori law for the models and the parameters can be deduced. The information contained by this law is extracted using numerical methods, sampling to be more exact and, regarding these methods, the literature is divided into two types of approaches: across-model simulation and within-model simulation.

The across-model approach consists in jointly sampling the model and the parameters corresponding to that model, thus allowing the algorithm to visit the models and jump from one to another concurrently with choosing adapted values for the parameters. This principle guides the state of the art algorithm of Reversible Jump Monte Carlo Markov Chain (RJMCMC), first introduced in [START_REF] Green | Reversible Jump Markov Chain Monte Carlo Computation and Bayesian Model Determination[END_REF] and then extensively studied and expanded in numerous papers, as shown in [START_REF] Green | Trans-dimensional Markov chain Monte Carlo[END_REF][START_REF] Green | Reversible Jump MCMC[END_REF]. One of the immediate applications of this algorithm to a Bayesian texture analysis problem, with an interesting perspective on texture modeling by Beta mixtures, is presented in [START_REF] Elguebaly | A Bayesian Approach for Texture Images Classification and Retrieval[END_REF].

The within-model simulation technique consists in computing the model probabilities by marginalizing out the parameters from the joint a posteriori law. This is done by sampling the parameters conditionally to each model, the values obtained being used to compute the "evidence", i.e., the probability of the data, given the model. The evidence for model M = k can be obtained using a harmonic mean of likelihood values computed for the parameter samples, drawn conditionally with respect to the data and under the assumption that M = k is the generating model. A detailed description of this principle can be found in [START_REF] Gelfand | Bayesian Model Choice: Asymptotics and Exact Calculations[END_REF][START_REF] Newton | Approximate Bayesian Inference with the Weighted Likelihood Bootstrap[END_REF] and more recently in [START_REF] Robert | Computational methods for Bayesian model choice[END_REF], where a survey of within-model simulation methods is presented.

An image processing application, more specifically texture analysis, will illustrate the model selection method. Our previous work [START_REF] Vacar | Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance[END_REF], devoted to efficient sampling algorithms for the same types of textures, is thus continued and enriched by a method that uses the parameter samples to select the generating model.

DATA MODEL

Most of the applications of the above methods attempt to determine the best model for the data probability distribution. In a significant part of the literature, the observations consist of i.i.d. data, so these methods do not deal with data correlations and assume the observations have a common distribution. Our goal was to assemble a method to solve a more complex task: selecting the model for the pixel correlation structure in a texture image.

The work focuses on textures modeled as zero-mean stationary Gaussian Random Fields (GRFs), as they are rather versatile in generating diverse patterns (see Fig. 1) and at the same time easy to manipulate and embed in a probabilistic framework. The model is completely described by its second order statistics and a distribution law:

f (x|R) = (2π) -N/2 det(R) -1/2 exp - 1 2 x t R -1 x (1)
where x collects the N pixels and R is the correlation matrix. In the frequency domain, by Whittle approximation, the previous expression becomes separable in terms of the Fourier coefficients:

f ( • x|λ) = (2π) -N/2 N n=1 λ 1/2 n exp - 1 2 N i=1 | • xn| 2 λn (2)
In fact, every element λn is the variance of the nth coefficient of the image's Fourier transform. Thus, as a physical interpretation, λ describes the image's Power Spectral Density (PSD). An important tool in the subsequent developments is the negative log-likelihood (NLL) of the data knowing the underlying model: This is where the notion of model intervenes, as the texture can be obtained by using any type of pixel interaction model, i.e., any form for the PSD. The dictionary of models chosen in the current work consists of parametric forms: Generalized Gaussian (M = 1), Student (M = 2), Chi-Square (M = 3), Ring (M = 4). Each model M = k is driven by the set of parameters θ k , Table 1 showing the dependencies λ k (θ k ). Some parameters are common to all the models, such as the scale factor γ, the central frequencies νx0, νy0, that give the positioning in the frequency space, and the widths σx, σy that determine the spread of the function. There are also some model specific parameters: the interior and exterior radii r1, r2 and the power p, which gives the models the possibility to have a wide range of shapes according to its values.

NLL = N 2 log 2π - 1 2 N n=1 log λn -| • x| 2 λn (3)

METHODOLOGY

Bayesian Setting

The model choice is a continuously active branch of statistics, that compares the models based on their structural properties and selects from a family of models the one that is best adapted to the available data, i.e., the observations and the a priori information.

The Bayesian approach is fundamentally probabilistic, i.e., a joint probability distribution is used to describe the relations between the unknowns and the data, and from this the a posteriori distribution is deduced, which extracts the useful information from the data.

In the current problem, we have a set of K = 4 models that will be tested for the data X. For the kth model, X has a law f (X|θ k , M = k), as seen in ( 3). The Bayesian approach pro-Table 1: Pixel correlation models for the textures

Model M = k Expression of λk(θk) Generalized 1 γ exp 1 2 |νx-νx0| p σ p x + |νy -νy0| p σ p y Gauss Student 1 γ 1 + (νx-νx0) 2 σ 2 x + (νy -νy0) 2 σ 2 y p Chi-Square 1 γ |νx -νx0| 1/2-p |νy -νy0| 1/2-p exp 1 2 |νx-νx0| σx + |νy -νy0| σy Ring    1 γ , if r 2 1 ≤ (νx-νx0) 2 σ 2 x + (νy -νy0) 2 σ 2 y ≤ r 2 2 10 5 , otherwise
ceeds by attributing an a priori distribution π(θ k |M = k) to the parameters of model k, consisting of uniform laws on the interval [-0.5, 0.5] for the central frequencies, as they represent the positions in the reduced frequency domain. For the widths we chose uniform a priori laws [0.01, 1], as beyond these values the laws are either too narrow and will correspond to uncorrelated fields, either too wide and then all pixels will be correlated to all the rest. For p, r1, r2 and γ uniform a priori laws were also used, in accordance with their physical significance. The a priori probabilities for each model were set to Pr(M = k) = 1/K, so that no model is favored with respect to another and the data decides on the model adequacy.

Intuitively, this complete specification can be regarded as a three stage model of hierarchic structure to generate the data X: firstly, the model k is chosen using Pr(M = k), secondly, the parameter vector θ k is obtained by using π(θ k |M = k) and, thirdly, the data is generated according to f (X|θ k , M = k) [START_REF] Chipman | The practical implementation of Bayesian model selection[END_REF].

Posterior Model Probabilities

The problem amounts to finding the most probable model, given the data, and for this the a posteriori probabilities of the models will be used. By applying Bayes' theorem, the probability of model k is:

Pr(M = k|X) = Pr(M = k)f (X|M = k) f (X) (4)
In ( 4) there are two quantities that have to be computed in order to select the most probable model:

1. the probability distribution of the data, f (X), 2. the evidence for each model, f X|M = k).

Fortunately, f (X) is model independent and thus it can be numerically computed by factorizing it and imposing that the model probabilities add to 1:

f (X) = K k=1 f (X|M = k)Pr(M = k) (5)
The second quantity of interest, the evidence, is determined from the joint law, by marginalizing the parameters and amounts to calculating the integral:

f (X|M = k) = f (X|θ k , M = k)π(θ k |M = k)dθ k (6)
which is mathematically intractable due to the very complex dependencies with respect to the parameters [START_REF] Vacar | Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance[END_REF]. Thus, the integral must be computed numerically, as detailed in Section 3.3. Remark: In the final stage, the pairwise model comparison, say M = k and M = k ′ could be summarized by:

Pr(M = k|X) Pr(M = k ′ |X) A posteriori chances = f (X|M = k) f (X|M = k ′ ) Bayes Factors × Pr(M = k) Pr(M = k ′ )
A priori chances (7)

Harmonic Mean

As previously seen, the within-model analysis requires the computation of the evidences, f (X|M = k). If these could be calculated explicitly, the a posteriori model probability would result immediately. However, this is not possible and a numerical computation must be used, meaning that the usual difficulty of the Bayesian approach, i.e., computing integrals of the type (6), will be eliminated by using MCMC methods. Relation (6) can be seen as an expectation of the likelihood under the a priori law. In numerical terms, this can be computed by drawing samples from the a priori and averaging the likelihood computed for these samples. However, the laws f (X|θ k , M = k) for our texture images are very peaked, and the a prioris π(θ k |M = k) for the parameters are uniform, meaning that if we were to sample under the a priori there would be a high risk of drawing a considerable amount of samples from regions of very low probability, leading to a high rejection rate and a slow sampling process.

In order to avoid this, in a similar manner as with importance sampling, the integral is computed by introducing a more adequate sampling distribution and then compensating for this change. Thus, integral (6) can be rewritten as:

f (X|M = k) = Eg f (X|θ k , M = k) π(θ k |M = k) g(θ k ) ( 8
)
where g is an auxiliary function, not necessarily the sampling distribution. Its role is to make possible the sampling under a more adapted law that will allow a good exploration of the parameter space, but will also take into account the form of the likelihood. Such a law is the a posteriori and then (8) becomes:

f (X|M = k) = E θ k |X,M=k f (X|θ k , M = k) -1 -1 (9)
Practically, knowing that θ

(t)
k with t = 1, .., T are samples from the a posteriori law, the evidence can be numerically computed as:

f (X|M = k) = 1 T T t=1 f (X|θ (t) k , M = k) -1 -1 (10)
This is in fact the harmonic mean of the likelihood values computed for the samples θ

k . For this estimator, the g function is equivalent to the inverse of an importance function and thus the estimator performs better when g has lighter tails than π(θ k |X, M = k) [START_REF] Robert | Computational methods for Bayesian model choice[END_REF].

Even though f (X|M = k) converges to the true value f (X|M = k) when T → ∞, it does not generally satisfy the Gaussian central limit theorem. To be more exact, occasionally, a value of θ (t) k may occur that has low probability and thus has important effects on the final result [START_REF] Newton | Approximate Bayesian Inference with the Weighted Likelihood Bootstrap[END_REF]. These reservations were reinforced by [10], making the harmonic mean a rather avoided algorithm, since in some cases it may exhibit infinite variance. However, its computational efficiency and ease of implementation have lead to its use in a series of topic modeling papers such as [START_REF] Griffiths | Finding scientific topics[END_REF][START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF].

All these considerations are true for the general case, however, for the current application, the probability of drawing a sample of very low probability region is extremely small, as the sampling law (the a posteriori) is very peaked. Moreover, even if such a sample from a low probability region were to occur, in our case it would only do so during the burn-in period, as our sampler allows a thorough exploration of the law, but especially its high probability regions. This actually means that the general doubts regarding the infinite variance do not apply in our case due to the form of the posterior law, as long as we make sure the sampler has reached convergence before using the values in the computations.

Parameter Estimates

The samples drawn from the posterior distribution are not only used for computing the harmonic mean, and thus the evidence, but also to compute a parameter estimate. In this case, the A Posteriori Expectation estimator was chosen and it consists in calculating the expectation:

θ = E θ|X,M=k [θ] (11)
numerically computed by averaging the samples drawn from the a posteriori distribution.

Metropolis-Hastings Sampling

The evidences are the key ingredients for computing the model probabilities and they are obtained by a harmonic mean of likelihoods computed for a series of samples θ (t) , drawn from the a posteriori. At this point, the difficulty of sampling these laws must be pointed out, due to the complicated dependencies with respect to θ, as shown in [START_REF] Vacar | Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance[END_REF]. For this reason, direct sampling is infeasible and thus the M-H sampler will be used. Among the class of M-H samplers we chose the Fisher M-H, introduced in [START_REF] Vacar | Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance[END_REF] due to its very good speed performances when applied to texture parameter sampling. Although it adds an extra layer of complexity to an already multi-stage multi-algorithm combining approach, it exploits particularities of the problem and enhances the sampling speed.

The algorithm starts by initializing the parameter and at each iteration it makes a proposal, by a directional perturbation of the current parameter value. This proposal is either accepted, or rejected (the current value is repeated) according to an acceptance probability dictated by the proposal law and the a posteriori law.

ALGORITHM

The methodological and algorithmic ingredients previously presented are mainly state of the art, being complex tools in probability theory, random fields analysis and sampling. They are used to assemble the model selection method for texture images, a composite algorithm that inherits their capabilities, but also their complexity.

The implementation of the algorithm posed a series of numerical problems, mainly due to the exponential form of the likelihood law, amounting to quantities that overpass Matlab's representation capabilities and are set to zero or infinity. To be more exact, we would need to compute exponentials with arguments superior to 10 3 or inferior to -10 3 . For this reason NLLs are computed and handled in the sampling phase instead of the likelihoods themselves.

This solves only partially the problem, as when computing the harmonic means we need to use the exponential quantities. To overcome this standstill, a normalization was in order: we determined the minimum NLL for each chain and we normalized the chain by this value. However, the value by which we normalized had to be reintroduced in order to obtain correct results and this was done in the final phase of the a posteriori model probability computation. Remark: The values of the NLL for each parameter sample were already computed during the sampling stage. Consequently, the exponentials intervene only in the final stage, and they are factored, as shown by expression [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF]. This is done in order to replace computing the exponentials of the NLL chains minima with the exponentials of these differences, since the exponentials of the minima will be seen by Matlab as zero, yielding indeterminateness, while the exponentials of the differences will result in finite non trivial values. Moreover, even if the values of the differences are not finite, non trivial values, we will still have eliminated the indeterminateness: for instance if for a model l we have exp[mN LL(k) -mN LL(l)] = ∞, then P r M|X (l) = 1. Conversely, if for model k, exp[mN LL(k) -mN LL(l)] = 0, all the models l = k will have P r M|X (l) = 0 and P r M|X (k) = 1. This solution eliminates the numerical problems without introducing any approximation, only by conveniently handling the quantities.

Algorithm 1 Model Choice Algorithm % Initialize the a priori model probabilities P rM(k) = 1/K, k = 1...K; % For each model k generate T samples from π(θ k |X, M = k) for k = 1 → K do [Θ k , NLL k ] = MetropolisHastings(T ); mN LL(k) = min(NLL k ); normNLL k = NLL k -mN LL(k); Evid(k) = HarmonicMean(normNLL k ); end for for k = 1 → K do % Compute

EXPERIMENTAL RESULTS

This section is devoted to the performances in terms of speed and accuracy of our model selection method. The true model and the values of its parameters used to generate the data are known since we worked on synthetic images. Consequently, we can directly evaluate the accuracy of the model probabilities and parameter estimates.

The concerns regarding the behavior of the harmonic mean estimator, more specifically the fact that infinite variance situations may be encountered, have lead us to monitor the empirical variance all throughout the simulations and we report that with no exception, the variance is not only finite, but also tends to zero.

The implementation was done in Matlab, with T = 1000, resulting in a total run time of about 4 minutes on a 3GHz processor.

The algorithm performs very well, managing to correctly yield a strong probability for the model that generated the texture and very weak probabilities for the other models. An interesting fact, highlighting the strength of the method, is that it successfully distinguishes the models even if the observed textures are visually similar.

The experimental setting is the following: we chose 20 sets of parameter values, θ, and using these sets we generated the 80 corresponding textures, by using every set θ for each model. We ran the algorithm 10 times for each texture and we counted the number of times the algorithm associates the highest probability to the true model. The results are synthesized in Table 2, where we can see that the method correctly identifies the true model in the large majority of cases, as shown by the strong probabilities on the diagonal. There are a series of misclassification situations, quantified by the other percentages, which occur mainly in situations where the shapes of the PSDs for those specific values of the parameters are very similar.

The parameter estimation for each model is very accurate, yielding values situated within the ±3% relative error interval with respect to the true parameter values, as also discussed in [START_REF] Vacar | Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance[END_REF].

In Fig. 2 we have shown an example of an original texture and its reconstruction using our model selection and parameter estimation method. We can observe their strong similarity as proof of the

CONCLUSION AND PERSPECTIVES

The paper presents the mathematical formulation and the performances of a model selection with joint parameter estimation method for texture images modeled as GRFs. This approach assembles state of the art algorithms, such as M-H, within-model simulation, harmonic means, in a fully Bayesian framework. The joint probability law synthesizes the information contained by the data and all prior information available on the models and the parameters.

This method uses a within-model sampling technique, the very nature of the tackled problem having lead us towards choosing this type of sampling rather than RJMCMC. The relatively small number of models and the fact that, based on our work in [START_REF] Vacar | Langevin and Hessian with Fisher approximation stochastic sampling for parameter estimation of structured covariance[END_REF], we were able to efficiently sample the model parameters reinforced our choice.

We foresee a number of future developments for this algorithm, among which we consider its integration in a more complex application for textured images segmentation with model selection and parameter estimation for each region. We also intend to widen the set of texture models beyond the class of GRFs, perspectives in this direction being non-Gaussian models such as: fractal models, Wold models, Markov Random Fields.

Fig. 1 :

 1 Fig. 1: Texture realizations using GRFs with structured PSDs [8].

  the a posteriori model probabilitiesP r M|X (k) = P rM(k) • Evid(k) K l=1 P rM(l) • Evid(l) • e mN LL(k)-mN LL(l)(12) end for

Fig. 2 :

 2 Fig. 2: Observed image and reconstructed texture successful model identification and accurate parameters estimation.

Table 2 :

 2 The probability (in %) of the method selecting a certain model, on the vertical, the true model used to generate the data and on the horizontal the model chosen by the method

	True model	GG	Estimated model St CS	Ro
	GG	96.3	1.8	1.6	0.3
	St	3.3	92.5	0.7	3.5
	CS	5.8	1.9	90.1	2.2
	Ro	1.8	6.1	0.8	91.3


Gabriele Svelto

Andrea Ornstein

Erven Rohou

A Stack-Based Internal Representation for GCC

Complex embedded systems have always been heterogeneous, and it is unlikely that this situation will change any time soon. Still, the huge non-recurring engineering cost of silicon products tends to make more parts of embedded systems programmable. Our research proposes to address this complexity through processor virtualization. We decided to rely on the CLI format, and we developed a GCC back-end for it. Even though we were able to generate reasonable code, we noticed that we were lacking some important optimizations that exploit the evaluation stack of the virtual machine. Since GCC internals do not provide any support for stack-based instruction set, we introduced our own. We review the limitations of our previous prototype, and we present the data structures of our internal representation, as well as its API. We also describe a number of optimizations that this representation enabled. To exemplify its convenience, we report the code size improvements we obtained with little effort.

Introduction

Complex embedded systems must provide a wide range of dedicated and demanding functionalities, such as communication, multimedia and user interface. Given their tight area and power constraints, no programmable homogeneous architectures can provide those functions. Rather, they typically consist of a host microcontroller running the system software, some heterogeneous processors, such as DSP or VLIW, and dedicated hardware.

Instruction set virtualization is a way to address this heterogeneity. The most widespread technologies are Java [START_REF] Lindholm | The Java Virtual Machine Specification[END_REF] and the Common Language Infrastructure (CLI). CLI is a rich virtualization environment for the execution of applications written in multiple languages (CLI is better known as the core of Microsoft's .NET technology). It is both an ECMA [START_REF]Common Language Infrastructure (CLI) Partitions I to IV[END_REF] and ISO [START_REF]2006 -Common Language Infrastructure (CLI), Partitions I to VI[END_REF] standard. Among other features, it includes an effective abstraction of instruction sets in the form of a processor-independent stack-based bytecode format.

In previous work [START_REF] Cornero | An experimental environment validating the suitability of CLI as an effective deployment format for embedded systems[END_REF][START_REF] Costa | Comparing the size of .NET applications with native code[END_REF], we have shown that CLI is an appropriate program representation for deployment of embedded applications, in terms of both code size and performance. Since most embedded applications are written in the C language, and we were unable to find any adequate C compiler for CLI, we originally developed a port of GCC. This work has been presented in [START_REF] Costa | CLI back-end in GCC[END_REF].

While this compiler produced reasonable code, we noticed that we were unable to take advantage of the evaluation stack, simply because GCC internals cannot represent it. The contribution of this paper is to present the lightweight stack-based intermediate representation (IR) that we added to GCC. We developed it to better manipulate CLI code, but it could be adjusted for any other representation that makes use of an evaluation stack. Our developments are publicly available in the usual GCC source code repository.

Section 2 explains in more details the limitations of our previous port of GCC and the motivations for our extension. Sections 3 and 4 respectively describe our new internal representation and the new optimization passes we wrote. We then evaluate its effectiveness in Section 5. Finally, we conclude in Section 6.

Motivation

The standard GCC compilation flow is the following: the front-end parses the input source code and turns it into an internal tree-based representation called GENERIC [START_REF] Merrill | GENERIC and GIMPLE: A new tree representation for entire functions[END_REF][START_REF] Richard | Stallman and the GCC Developer Community[END_REF]. This code is then lowered into the GIMPLE representation to be manipulated by the high-level optimizers. It is then turned back into GENERIC code before being translated into RTL, the register transfer language used by the back-end for low-level optimization.

RTL, unfortunately, is not a good starting point for emitting CLI bytecode: it is not type-rich, and it assumes that the underlying machine is register-based. The most important phases dealing with RTL are designed around this assumption. Previous attempts to coerce RTL into CLI code [START_REF] Singer | GCC .NET -a Feasibility Study[END_REF] reported fundamental problems caused by the mismatch between the abstraction levels.

The first version of our CLI back-end [START_REF] Costa | CLI back-end in GCC[END_REF] was based on the existing GCC infrastructure, with the exception that we bypassed the RTL passes. We processed the final GENERIC/GIMPLE code in order to emit CLI instructions one by one. Complex nodes were expanded into a sequence of simpler operations, then a single depth-first descent was made on the trees, directly printing CLI code into an assembly file. This technique worked but still it had some drawbacks.

-The simplification pass tried to twist GENERIC so that we could emit assembly directly from it. This was an awkward and fragile process because it relied on implicit assumptions between the simplifier and the emitter regarding how GENERIC nodes were handled. -The code quality depended heavily on the source trees. No context was available when recursively expanding one node at a time. Shallow trees (like those produced with optimizations off) produced CLI code that did not use the stack at all, forcing us to create many temporaries and bloating the code. Some GENERIC-to-GIMPLE simplifications also caused this behavior. -We missed the optimizations done on the RTL representation and we could not do CLI specific optimizations as our IR was not really CLI.

These problems prompted us to design a new simple and specific IR which improved code generation and made it more robust and simpler to extend. We refer to it simply as CLI instructions or CLI statements. For each funtion, the virtual machine executing the bytecode has a representation of local variables and arguments, and an evaluation stack which is used for storing partial results [START_REF]Common Language Infrastructure (CLI) Partitions I to IV[END_REF][START_REF]2006 -Common Language Infrastructure (CLI), Partitions I to VI[END_REF]. Almost all CLI instructions directly operate on the stack, popping their arguments from it and storing back their result. No operation can be done directly on local variables and arguments.

On top of this, the CLI bytecode has rich type information. Pointers retain the type of the object they point to, stack slots retain the type of the object which was stored in them, aggregate types know their fields, etc.

Representation of CLI instructions

We loosely modeled the CLI instructions against GIMPLE tuples.3 There are substantial differences, but most of the philosophy is retained. We kept an eye on the gimple-tuples branch during its development, because it has become the middle-end representation, and we wanted our design to be immediately familiar to GCC developers. Note that we only used a subset of the instruction repertoire defined by CLI [START_REF]Common Language Infrastructure (CLI) Partitions I to IV[END_REF][START_REF]2006 -Common Language Infrastructure (CLI), Partitions I to VI[END_REF]: we focused on unmanaged code, specifically on the C language, whereas many CLI instructions are designed for an objectoriented managed environment (exceptions, garbage collection, . . . )

A basic CLI instruction is made of a single small structure holding the instruction type, an extra type-dependent union field, plus a few extra fields for housekeeping (see Figure 1). The union field is either directly used by simple instructions or it points to another external structure holding more information for complex ones. Instructions working on local variables or arguments use this field for storing a tree representing the VAR_DECL or ARG_DECL involved; a load-or store-field instruction uses this field to point to a FIELD_DECL. This is somewhat similar to GIMPLE tuples statements. Complex CLI statements like function calls or switches use this field for holding a payload of additional information.

Our CLI instructions and their operands use GCC garbage collection facilities like other data structures in GCC front-and middle-end.

typedef s tr u ct { / * . . . * / } c i l s t m t i t e r a t o r ; s t a t i c i n l i n e c i l s t m t i t e r a t o r c s i s t a r t ( c i l s e q ) ; s t a t i c i n l i n e c i l s t m t i t e r a t o r c s i s t a r t b b ( b a s i c b l o c k ) ; s t a t i c i n l i n e c i l s t m t i t e r a t o r c s i l a s t ( c i l s e q ) ; s t a t i c i n l i n e c i l s t m t i t e r a t o r c s i l a s t b b ( b a s i c b l o c k ) ; s t a t i c i n l i n e b o o l c s i e n d p ( c i l s t m t i t e r a t o r ) ;

CLI container structures

CLI instructions are held into sequences of instructions. A sequence node is allocated for each CLI instruction so that the sequence can be easily manipulated. The functions provided for the CLI sequences have names and behavior very similar to their GIMPLE siblings. Sequences are cheap to allocate and manipulate, and they are cached to minimize allocation costs and memory footprint.

GCC provides hooks for additional representations. CLI sequences should be attached to basic blocks like trees or RTL sequences. However, at this time, our port is not integrated in the main development branch, and we did not want to pollute GCC global structures with target-specific data. We used an external hash-table to map CLI sequences to the basic blocks. This allows us to keep our representation almost completely isolated inside our target, and it facilitates the merging process from the main branch.

Generic control-flow information and helper functions can be used transparently so that CLI-specific optimization passes look very similar to GIMPLE passes. However, once the CLI code is generated, only minimal changes to the control flow graph are allowed, as described in Section 4.1.

CLI instructions manipulation

A rich set of helper function is provided for creating and manipulating CLI instructions. Building new CLI instructions is cheap. While it is possible to directly alter CLI instructions, the preferred method of altering significantly an instruction is to simply replace it. The internal structure of CLI instructions is shielded from the use by a set of accessors. Reuse of GENERIC/GIMPLE operands inside the instructions makes handling or building complex statements easy. Always faithful to the GIMPLE tuples philosophy we decided that manipulation of CLI sequences and instructions would be done through a set of iterators with very similar names and functionality (cf. Figure 2).

Stack representation

As mentioned before, the CLI bytecode uses a typed evaluation stack for storing partial results. Knowledge about its depth, what variables have been pushed on it, what are the types of its slots in a specific point of the instruction stream are important to implement CLI specific optimizations. s tr u ct c i l s t a c k d { / * . . . * / } ; typedef s tr u ct c i l s t a c k d * c i l s t a c k ; extern void c i l s t a c k a f t e r s t m t ( c i l s t a c k , c i l s t m t ) ; extern s i z e t c i l s t a c k d e p t h ( c o n s t c i l s t a c k ) ; extern c i l t y p e t c i l s t a c k t o p ( c o n s t c i l s t a c k ) ; Calculating the contents of the evaluation stack over a whole function is a fairly trivial task because of the very nature of CLI code. By design, a single pass over the basic blocks is sufficient for obtaining the full stack information (see § III, 1.7.5 of [START_REF]Common Language Infrastructure (CLI) Partitions I to IV[END_REF]).

However, an optimizer might want to significantly alter the code while it is working on it. Precalculating all the stack information might not be the best way of dealing with it. Moreover, calculating stack information requires valid CLI code, but the optimizer might want to temporarily leave part of the code in an invalid state, yet still have stack information for its next steps.

To solve these problems we decided to create a simple set of functions which allow an optimization pass to create stacks from basic blocks and propagate them to their successors without calculating directly the contents of the stack. The stack information is updated simply by submitting to it the statements which need to be simulated. This allows for very cheap stack analysis both in terms of computational and spatial resources. See Figure 3 for an excerpt of the stack manipulation functions.

At this point, the information we provide on the stack contents is still partial, even though it was more than enough to implement the optimizations we planned. A full data flow analysis (DFA) would provide accurate information, possibly integrating the stack facilities with GCC DFA infrastructure.

CLI types and interaction with the GCC type systems

The GCC type system is very complex because it is designed to model types coming from a plethora of input languages. This causes some problems when emitting those types in CLI form. The CLI type system is fairly rich and complete, however its constructs are not enough to entirely cover GCC types.

CLI offers a few basic type categories on which we mapped all other types. A fairly wide range of scalar types are offered, including 8-, 16-, 32-and 64-bits integer (signed and unsigned), pointer-sized integers (also known as "native" integers), single and double precision floating-point types, and typed pointers. Structured typesvalue type in CLI speak -can be loosely compared to C structs but with much more control and different semantics; we used them for modeling all kinds of non-scalar types.

Value types are composed of an arbitrary number of fields and the offsets of those fields can be specified explicitly. Regular structs are mapped directly on value types; unions are mapped by setting the offsets of the different fields so that they overlap. Complex numbers and vectors are also represented as value types.

Fixed-size arrays and C 0-terminated strings are mapped to value types as well because CLI does not offer an equivalent of a fixed size unmanaged array. We could not use CLI arrays because they are managed garbage-collected objects with range-checking. No pointer arithmetic is possible on them. C arrays of unknown size at compile time are mapped to pointers.

We also modeled C99 [START_REF]/IEC 9899:TC2 -Programming languages -C[END_REF] and GNU-C extended complex types as value types made of two fields of the appropriate basic type. GCC already lowers operations on complex types as operations on their single parts, CLI supports manipulation of value types within variables or on the stack directly, so the expansion of those accesses is extremely simple. This kind of implementation has the upside of preserving the semantics of complex types very clearly in the resulting code.

CLI assemblies (the "executable object" format used by CLI) also requires that every type must be named. We provide a mechanism for automatically generating names for nameless types including the types that we artificially create.

Functions also require some additional processing. C specifies function types (function pointers) but does use them only in the language. Once an object file has been created, functions are referenced only by their names as symbol in the executable object. CLI, on the other hand, requires that functions be completely specified: the name of a function is its complete signature (including the types of its arguments). This causes problems when supporting C89 with K&R style function declarations.

CLI-Specific Compilation Flow and Passes

As mentioned in Section 2, RTL and CLI do not match well. The compilation pipeline we are using thus skips all the RTL passes as well as the passes converting GIMPLE/GENERIC into RTL, and adds passes which convert GIMPLE/-GENERIC into our specialized stack-based IR, optimize it and finally emits CLI assembly code from it. The changes we made did not impact the usual compilation pipeline and the changes done into passes.c are enabled only if the CLI target is selected, leaving the other passes in place if a conventional target is used. As soon as a flexible pass manager is available, we will be able to reimplement these changes without touching passes.c. The rest of this section describes in detail the various passes of the CLI compilation flow.

Basic blocks reordering and control flow graph interaction

The evaluation stack plays an important role when it comes to control flow. Every basic block in a piece of CLI code can be thought as having a stack representation associated with it, holding the depth and types of the stack at the entry point. Every branch to the basic block must also have a stack with the same number of slots filled and compatible types for those slots. However, there is an additional constraint, the CLI code must be verifiable (i.e. checked for consistency) in a single linear pass (see § III, 1.7.5 of [START_REF]Common Language Infrastructure (CLI) Partitions I to IV[END_REF]). This forces basic blocks which are reached only by backward branches to have an initial empty stack.

These constraints make manipulating the control flow complex. Moving basic blocks or redirecting branches causes changes which propagate over the control flow graph and which would be very complex to deal with.

For the sake of simplicity, we introduced an initial pass which reorders basic blocks to minimize the number of jumps. We then "freeze" the CFG and avoid further changes which might change the order of the basic blocks (or the branch directions relative to them).

Switch expressions break up

The CLI switch instruction implements the multi-way control-flow statement present in many languages. However, it cannot be used directly for encoding any C switch statement. The set of "cases" of the CLI switch is a range of adjacent values starting at zero. For each value in that range, a branch destination is stored. Using this construct to implement sparse switches thus would waste a lot of space in filling the "empty" slots with branches to the default label. On top of this, the switch instruction cannot specify a range larger than 8192. Larger switches -even if dense -must be broken up into multiple switch instructions. We added a pass before GCC builds the CFG that analyzes the switch statements and breaks them into smaller switch and conditional expressions in order to work around those constraints.

GIMPLE/GENERIC to CLI expansion

We lower GIMPLE/GENERIC code to CLI code by descending the original trees and expanding one node at a time. Many GIMPLE statements can be expanded into a single CLI instruction making the code generation fairly straightforward with each node being expanded and implicitly leaving its result on the stack; however some statements require significantly more effort. Unordered floating-point comparisons, bit-field extractions and insertions, rotations and some boolean expressions are turned into fairly large CLI sequences. Before the new representation was available, those statements were rewritten in GIMPLE, generating a large number of temporaries; now we are able to store the temporaries on the stack fairly often.

We also deal with many built-in functions in this phase. Some of GCC's builtins are turned into CLI built-ins provided by the support library which ships with our back-end. Any JIT compiler aware of the semantics of those built-ins can directly take advantage of them. Other JITs will have to rely on the runtime library. Some built-ins which can be mapped efficiently to CLI instructions and are expanded in this phase. For example __builtin_memcpy is turned into a cpblk instruction. This phase was designed to improve on our previous work and generate better code. However, the quality of the resulting CLI code still depends on the input code. Deep GENERIC trees result in excellent and compact code making heavy use of the stack. Shallow trees and GIMPLE temporaries result in fat code and large metadata sections needed to encode CLI local variables. Instead of trying to fix up these inputs up front, we introduced some later optimizations passes to clean up these code sequences. This has the side benefit of allowing us to make this critical phase emit "naive" code, thus keeping it simple and robust.

Missing prototypes fix-up

This is not an optimization phase, but it is necessary for fixing up functions which do not have a prototype. When such a function is called, the types that it accepts are treated in the same way as the arguments of a variable argument function (i.e., char and short are promoted to int, etc.) However, the function's actual arguments can be of unpromoted types. The function signature in CLI uses the promoted types so that the linker can find it correctly and this pass creates artificial local variables with the correct argument types, converts the passed arguments and stores them in those variables. Those locals are then used instead of the arguments. The fix happens only if the promoted argument type is different from the actual type, other arguments are left alone.

Redundant temporaries removal and stack promotion

The middle-end tends to generate many temporaries. The normal compilation flow of GCC removes many of them during register allocation. In our case, however, there is no register allocation. This new phase scans the code and locally tries to identify temporary variables and to promote them to the stack.

Ideally, a full data flow analysis is needed to extend this phase across basic blocks. Yet, we implemented this phase as a sort of improved peephole optimizer, and we obtained very good results with very little effort. The pass works as follows:

-We scan for variables whose address has been taken and we tag them. They remain untouched. -We then look for stloc instructions (store to local variable). For each of them, the depth of the stack is recorded and a matching ldloc (load local variable) is looked for. If the stack has not been altered below the depth of the stloc between the two instructions and if the depth is the same at both instructions, the stloc is replaced by a dup stloc sequence and the corresponding ldloc is removed. If the value on the stack is an integer larger than the temporary variable type, a conversion is put before the dup in order to simulate the truncation caused by writing to the variable. -The code is scanned a second time and other simple copies which cannot be promoted on the stack are identified. This involves finding ldloc/stloc or ldarg/stloc pairs and replacing the load from the target variable with a load from the source variable if it has not been modified in between. This step can be seen as a very simple copy propagation mechanism and works across basic-blocks. -Finally, dead stores left by the previous steps are removed.

Consider the GIMPLE code of Figure 4. Figure 5 illustrates the transformations of this pass: (a) is the initial IR generated by the middle-end. In (b), the variables t1 and t2 are clearly redundant and they are promoted to the stack. In (c), the variable c is copied into t3. Finally, in (d), the dead stores are removed.

Note that this transformation is already profitable after step (b) because the dup instruction is encoded on one byte, while the ldloc needs two or four bytes (except for the special case of variables numbered 0 to 3, where one byte is enough and the transformation is neutral). GIMPLE conversion nodes (CONVERT_EXPR and such) are often expanded into actual conversions on the stack because we process one node at a time and we do not have enough visibility to decide when a conversion is redundant. We first remove the conversions which behave as no-ops simply looking at the types of the stack slots. Then, we also try to remove conversions made useless by the particular use of their result. For example, when storing a stack slot to a local variable or memory location, holding an integer smaller than 32-bits, an implicit truncation is done. If a conversion from a 32-bit integer to a 16-or 8-bit integer precedes a store to an 8-bit integral local variable it is removed.

Peephole optimizations

This pass is used for cleaning up simple instruction patterns generated by the previous passes and are fairly simple to deal with. Currently this phase mostly removes naive instruction sequences emitted when dealing with functions with a variable number of arguments. These instruction sequences usually involve putting the address of a local variable or argument on the stack and then writing or reading indirectly into the variable using this address. These patterns can be easily removed and replaced by regular loads and stores.

Branch condition replacement

In this pass, the conditional branches at the end of each basic block are analyzed and potentially changed in the aim of reducing the code size. If one of their edges goes to the next basic block, the pass checks if the instruction can be emitted in a single compare-and-branch instruction with the edge going to the basic-block becoming a fall-through. If this does not happen this pass will try to invert the branch condition and the outgoing edges to make the fall-through possible.

CLI assembly emission

The last pass emits the CLI code. It is fairly straightforward as the IR maps one-to-one with the CLI code. This phase, however, contains a few extra functionalities which are not usually required by an assembler emission phase. After all the functions have been emitted, this pass proceeds by emitting the type declarations, as well as the global variables, static variables (including functionstatic ones which cannot be declared inside a CLI function and thus must be "promoted" as plain global variables) and the string constants.

Examples and Experiments

This paper is not about quantitative achievements. Rather, it is about presenting the new IR we added to GCC, its design and its purpose. Still, as an illustration of its convenience, we quickly report the improvements that we have been able to achieve with a minimal effort. In the interest of space, we do not report in this paper the code of the optimizations themselves. However, all the above mentioned transformations are fully implemented and publicly available in the branch st/cli of the GCC Subversion repository.

The code transformations we implemented so far mostly target the code size. Performance is less impacted because a JIT will eventually transform the CLI to native code, replacing stack elements with machine registers. Classical optimizations applied by the just-in-time compiler will remove some of the inefficiencies of the bytecode 4 .

We used benchmarks from the MiBench [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] and MediaBench [START_REF] Lee | MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems[END_REF] suites, as well as a few proprietary multimedia benchmarks. All benchmarks were compiled at optimization levels -O2 and -Os with and without our new IR. Figure 6 shows that the modest effort made at implementing the above mentioned optimizations immediately pays off for most benchmarks. The small degradations actually are a bug fix: the previous implementation was too aggressive at removing conversions, and in some corner cases it generated incorrect code.

While the code size may be of relative importance to the general purpose computing, it does matter for embedded systems because the non volatile memory is a significant part of the total cost, and therefore it must be carefully sized. Anyhow, our proposed IR provides a means to manipulate a stack-based instruction set. As such it can also be used to implement optimizations targeted at performance.

Conclusion

In the course of our research, we are interested in applying virtualization technologies to ease the programming of embedded systems. In particular, we considered the CLI format. We have been developing an initial port of the GCC compiler for this purpose. While we were able to generate reasonable code, we noticed that we were unable to take advantage of the evaluation stack, simply because the GCC internals cannot represent it. This paper presents the new lightweight stack-based intermediate representation that we added to GCC for this purpose and made publicly available in the GCC source repository. We describe the data structures representing CLI instructions and the helper functions, as well as the stack representation. As an illustration, we also present a number of simple optimizations that we wrote using our new IR, and we report the code size improvements we achieved.

We strongly believe in the benefits that virtualization can bring to embedded systems. Being able to generate optimized CLI code from the C language is a mandatory step towards our goals. Our contribution clearly shows the need for exploiting the evaluation stack, and the benefits one can draw from our stackbased intermediate representation.

Fig. 1 .

 1 Fig. 1. Representation of a CLI Statement

Fig. 2 .

 2 Fig. 2. Iterators on CLI Statements

Fig. 3 .

 3 Fig. 3. Representation and Manipulation of the Stack

Fig. 4 .Fig. 5 .

 45 Fig. 4. Original GIMPLE Code

Note that the CLI bytecode is actually named CIL (Common Intermediate Language). This is the reason why we use the cil prefix in our naming convention. However, for the sake of simplicity we only use CLI in the text of this paper.

An interpreter would be faster because of the reduced number of instructions. The JIT compilation time can also benefit from these improvements.


Nadia Haddadou

Abderrezak Rachedi

DTM 2 : Adapting Job Market Signaling for Distributed Trust Management in Vehicular Ad Hoc Networks

In this paper, we address the issue of the presence of malicious and selfish nodes in Vehicular Ad Hoc Networks (VANETs). Malicious nodes spread false and forged messages, while selfish nodes only cooperate for their own interest. To deal with this, we propose DT M 2 , a Distributed Trust Model inspired by Spence's Job Market model from Economics. In our model, a sender node transmits a signal with its message. This signal represents a guarantee of the truthfulness of the message for the potential receivers. In order to use the signal, the sender node has to pay a cost, which depends on the value of the signal and its own behavior. Therefore, the worse the behavior of the sender node, the more expensive the signal cost. This model deters the sender nodes from acting as malicious nodes. Similarly, cooperation of the sender nodes is rewarded proportionally to the signal's value. We validated DT M 2 via extensive simulation in an urban scenario. We show that our approach is able to detect and evict gradually all malicious nodes in a network composed of 25%, and 50% of them. Moreover, our solution greatly decreases the ratio of corrupted and false data sent through a network to levels as low as 0%, and it increases the participation ratio of selfish nodes by 20%.

I. INTRODUCTION

Vehicular Ad Hoc Networks (VANETs) are collaborative networks having several particular properties, such as high mobility, predefined mobility scenarios, frequent topology changes, and few operational limitations (e.g. memory, processing, energy,...). They offer a wide variety of applications, ranging from driver and passenger comfort applications to road safety applications. In the latter, nodes broadcast their collected data, and relay other's messages in order to inform all participants about traffic conditions, and alerting them in case of accidents [START_REF] Camara | Propagation of public safety warning messages: a delay tolerant network approach[END_REF]. In this work, we are interested in this kind of applications when they are deployed in VANETs without any communication infrastructure, and requiring advanced dissemination algorithms, such as [START_REF] Haddadou | Modeling and performance evaluation of advanced diffusion with classified data in vehicular sensor networks[END_REF] and [START_REF] Wu | A broadcast path diversity mechanism for delay sensitive vanet safety applications[END_REF].

Certain safety applications, such as advanced driver assistance systems, are very important, and may cause unsafe situations on road traffic in case of misappropriation. Therefore, a node should never accept any safety information without guarantee on its truthfulness. Moreover, since safety applications are time sensitive, a node has to quickly make a decision about the validity of a received message. This task becomes even more challenging when the VANET infrastructure is scattered or non-existent, because it is impossible to validate any information beforehand.

In this work, we focus on two issues. First, we propose an effective solution that filters out the nodes that introduce false information or retransmit distorted information in a VANET. These nodes are called malicious nodes. In a VANET, some of the nodes can be strictly malicious, while others can alter their behavior from good to bad (e.g. sending false information) and vice-versa. Second, we tackle the problem of selfish nodes. Selfish nodes act to serve their own interests and use their resources only for their own needs. Thus, their cooperation rate is low. Unlike malicious nodes, these selfish nodes are rational, which means that they can cooperate if it is in their interest.

In a collaborative network such as a VANET, any node dissociation is difficult because of the significant number of nodes composing the network. On top of that, because of high mobility and extended deployment areas, asymmetric information regarding the behavior of each node is widely disseminated. Therefore, establishing direct connections between nodes becomes challenging, thus encouraging the emergence of malicious and selfish nodes. In order to deal with node scattering, we allocate each node a credit account, which can increase and/or decrease according to its behavior. This credit is useful to obtain advantages in the network, such as receiving other nodes' messages. Holding credits allows a node to take part in the network by sending or receiving messages. On the other hand, a node that runs out of credits is evicted from the network.

In order to manage the nodes' credit, we based our solution on an economics model called the Job-Market model [START_REF] Spence | Job market signaling[END_REF], belonging to the signaling models [START_REF] Sobel | Signaling games[END_REF]. These models intervene in the case of asymmetric information [START_REF] Spence | Signaling in retrospect and the informational structure of markets[END_REF], and thus can be used to have a global view of nodes' behavior in VANETs. In addition, the high mobility of vehicles and their large deployment area, cause sporadic connections in the network, and infrequent meeting intervals among nodes [START_REF] Baccelli | Information propagation speed in bidirectional vehicular delay tolerant networks[END_REF]. Moreover, since reputation models need stable connections to obtain actual reputation values, and may take a long time to eradicate one misbehaved node, a reputation model for VANET is not enough. The main concept behind signaling models is to exchange signals between nodes. The signal is a characteristic of the node's truthfulness. It has a cost corresponding to the actual behavior of the node. Thus, this cost is a guarantee of the node's truthfulness. If a sent message is considered as false and thus refused by the neighbors, the emitting node loses its signal cost and incurs an eviction from the network.

To summarize, the contributions of our work are:

• A distributed trust model for VANETs, inspired from the Job Market Signaling model.

• A prevention mechanism, in order to detect and evict malicious nodes from the network.

• An incentive mechanism, to increase the selfish nodes' cooperation. The remainder of this paper is organized as follows: In Section II we present the related works dealing with trust models in literature. In Section III we present our solution. Section IV presents our performance study and our simulations results. Finally, Section V concludes this paper and presents our future works.

II. RELATED WORK

There are many solutions proposed in literature dealing with trust models for mobile ad-hoc networks as presented in the survey [START_REF] Govindan | Trust computations and trust dynamics in mobile ad hoc networks: A survey[END_REF]. These solutions cope either with malicious nodes or selfish ones, but rarely with both of them at the same time.

To improve the cooperation in a network, existing solutions propose rewards in return of a node's participation, which is the general concept of incentive cost/reward models, as presented in [START_REF] Buttyán | Enforcing service availability in mobile adhoc wans[END_REF], [START_REF]Stimulating cooperation in self-organizing mobile ad hoc networks[END_REF] and [START_REF] Zhong | Sprite: A simple, cheat-proof, creditbased system for mobile ad-hoc networks[END_REF]. These solutions use nuggets or virtual money as method of payment to incite nodes to be more cooperative.

Buttyàn et al. propose two schemes to estimate a node's reward for a retransmission, the packet purse model and the packet trade model [START_REF] Buttyán | Enforcing service availability in mobile adhoc wans[END_REF]. The first scheme estimates rewards according to the number of intermediate nodes. However, because of the propagation speed of information in VANETs [START_REF] Zhang | On the information propagation process in multi-lane vehicular ad-hoc networks[END_REF] and the high mobility of vehicles, underestimation and overestimation of the reward occur, which leads the solution to be ineffective. In the second scheme, the destination node has to reward all intermediate nodes for their forwarding actions, which represents an expensive cost if there are many of them. Furthermore, both these schemes deal only with selfish nodes.

The second solution [START_REF]Stimulating cooperation in self-organizing mobile ad hoc networks[END_REF] proposes different levels of cooperation for network's nodes. These levels can make the participation turn into a quantitative one and not necessarily a constant one, thus leading to declines in the network's connectivity. The third solution is based on the presence of a Credit Clearance Service to verify the receipts of all the actions in the network, and then reward the participants [START_REF] Zhong | Sprite: A simple, cheat-proof, creditbased system for mobile ad-hoc networks[END_REF]. The use of this method can increase the network delays, and negatively impacts its performance.

Another kind of solutions based on the use of a reputation model for vehicles, is proposed by Minhas et al. [START_REF] Minhas | Towards expended trust management for agents in vehicular ad-hoc networks[END_REF]. The basic idea is to add a criterion about the category of the driver, setting apart, for instance, a law enforcement agent from a regular citizen. To validate a received message, a node asks its neighbors about its validity, and it takes it into consideration only if the received responses reach a majority consensus. The limitations of this solution concern performance due to the generated overhead, and the time that it can take to validate received data. Another solution uses fairness as criterion for cooperation by computing reputation values, so that nodes cooperate with each other in a reciprocal way [START_REF] Ashtiani | Achieving fair cooperation for multi-hop ad hoc networks[END_REF]. However, this solution involves huge costs caused by the monitoring as demonstrated in [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF].

Our solution, DT M 2 , is able to cope with the presence of both malicious and selfish nodes in a VANET without any infrastructure. The computation of signaling costs and reward values are not based on estimation, which leads our approach to handle more easily the high mobility of a VANET. DT M 2 creates an auto-selection among the nodes to evict malicious nodes and to increase the cooperation of selfish ones, without impacting the performance of the network.

III. DT M 2 : DISTRIBUTED TRUST MODEL INSPIRED FROM JOB-MARKET DT M 2
, is a solution inspired from the Job-Market model proposed by Spence [START_REF] Spence | Job market signaling[END_REF], which belongs to the signaling models [START_REF] Sobel | Signaling games[END_REF]. These models are used in asymmetric information cases, and bring solutions mainly in the form of equilibriums.

In the economics market of labor, asymmetric information concerns the employees and employers during a hiring. In this case, an employer has no way to ascertain the productive capacity of an employee before hiring him, while an employee is fully aware of it. Spence addresses this problem by transforming the communication between both parts into a signaling game. An employee uses his academic degrees as a signal to an employer, in order to distinguish himself from the other employees, thus influencing the employer to hire him. Spence's model differs from other signaling models because, unlike other models, a signal has no other purpose but to be used for the signaling function.

A signal has a cost. In Spence's model this cost has to be negatively correlated with the production capacity of a signaler. This allows an auto-selection of the members in a group. Each member uses the signal value, which maximizes its benefits; and because signaling costs are cheap for highly productive members, they use a great signal value. Moreover, the model prevents low-productive members from cheating by establishing expensive signaling costs for them, thus disabling them from imitating highly productive members.

A. Problem Formulation

Spence's model is adaptable to a VANET, since nodes in this kind of networks also suffer from asymmetric information regarding the behavior of each one of them. Because of long and infrequent meeting intervals, it is difficult to establish valid and truthful links between nodes only by using a reputation model. Also, this model increases cooperation among nodes, by offering them rewards positively correlated with their behavior. This represents a strong incentive to the selfish nodes. Regarding malicious nodes, they are detected and evicted when they run out of credit, which happens after a number of malicious actions. Our solution replaces the academic signal of Spence's model by a value signal, observable by all, and used when sending a message as a guarantee of its truthfulness. The signal cost depends on the remaining credit of each node. Upon their first connection to the network, each node receives the same amount of credit. This credit is used to pay the signaling cost when sending a message, and to decrypt received messages. It increases when a sent message is approved by a majority of recipient nodes.

B. DT M 2 Process

In order to secure this mechanism, we assume that each node has a Trusted Platform Module (TPM) [START_REF]Trusted computing group: Tpm main specification[END_REF]. A TPM is a secure hardware that is able to generate keys, and to encrypt messages. In this way, a node is able to encrypt its sensitive information. The TPM manages the credit count of nodes. It stores the credit in its shielded location, then it computes and deducts the signaling cost, in the case of sent messages; or deducts the price of a received message in case of it is validated by the receiver. It also increases the credit count when a sent message is accepted by the majority of its recipients. Finally, the TPM stores a fingerprint of the application it is responsible for (e.g. an advanced driver assistance system), which leads it to detect any changes to the application made by an attacker.

Fig. 1 illustrates the general functioning of DT M 2 . In this example, node A broadcasts a message that is received by node B. First, node A chooses a signaling value Y A . This value is attached to its message M sg A , and both of them are sent to its TPM. T P M A uses the credit count of node A, θ A , to compute the corresponding cost, C A , of its signal value Y A , and then subtracts it from the credit count. To ensure the integrity of the mechanism, the TPM signs the message, M A , which contains both the signal value Y A and the data to share, M sg A , using its private key, and then returns it to node A.

When node A broadcasts message M A , node B receives it and asks its TPM, T P M B , to decrypt the signal value for it in order to evaluate its coherence with the reputation value it holds on node A, R t B (A). If the reputation is coherent, then node B accepts the message and asks T P M B to decrypt the Fig. 2. Signaling cost values for different signal values and nodes' credit rest of the message, which contains the data. Then, its TPM subtracts the cost of receiving a message, C msg , fixed by the application; and delivers the decrypted data, while returning a signed acceptance message about the received information to node B, which will be sent to the source node. In case B refuses the message, a signed refusal message from T P M B is sent to the source node A.

In both acceptance and refusal cases, the reputation values of both nodes A and B are updated, for the sent message for A, and for the acceptance or refusal message for B, as described in [START_REF] Charikleia | Robust cooperative trust establishment for manets[END_REF]. Finally, if node A receives a majority of positive returns from its recipients, then T P M A increases its credit count by a reward, W A , proportional to its used signal value Y A .

In the following subsections, we detail the signaling cost and reward functions, and the incentive and preventive mechanisms of the trust model with respect to the net benefit of a node.

C. Computation of the Signaling Cost

In highly mobile environments, such as the one under consideration, the signal Y used by a source node acts as a guarantee about the validity of its messages and its honest behavior. An optimal signal value maximizes the net benefit of a node. This occurs when a signal corresponds to the real behavior of the node, which is unavailable to the network and unknown by its TPM. As the credit count value does not change with mobility, this information can be used as a hint on its behavior, since the more a node cooperates well, and the more recipients accept its messages, the more its credit increases thanks to rewards and vice-versa. This information is stored by the node's TPM. The signaling cost, C, is negatively correlated to the credit count, θ, but positively correlated to the signaling value according to the two conditions of the Job-Market model, as shown in [START_REF] Camara | Propagation of public safety warning messages: a delay tolerant network approach[END_REF]. The first condition is met when ∂C ∂Y > 0; and the second when ∂C ∂θ <0 and

∂ 2 C ∂Y ∂θ < 0. C(Y 1 , θ) > C(Y 2 , θ) F or Y 1 > Y 2 , C(Y, θ 1 ) < C(Y, θ 2 ) F or θ 1 > θ 2 , (1)
The signaling cost computation is presented in equation ( 2). It uses two positive real coefficients β and α, in order to

C(Y, θ) = β × Y θ α (2)
where β, α, θ >0 To demonstrate the negative and positive correlations required by the model, the derivatives of the cost function with respect to the signal value, the node's credit, and the second derivative, are given in [START_REF] Wu | A broadcast path diversity mechanism for delay sensitive vanet safety applications[END_REF].

     ∂C ∂Y = β θ α > 0 ∂C ∂θ = -α×β×Y θ α+1 < 0 ∂ 2 C ∂Y ∂θ = -α×β θ α+1 < 0 (3)
To avoid cheating or security problems when a node pays a signaling cost, the TPM calculates the cost and deducts it from the node's credit. It then encrypts the message containing both the data to share and the signal value by using its secret key, and returns it to the node.

D. Computation of the Reward Value

To motivate nodes to cooperate, DT M 2 proposes incentive rewards to truthful nodes for their sent messages. A reward value depends on the signal used by the source node. The secondary goal of this reward is to obtain an auto-selection of the nodes, which we name a separating equilibrium, by inciting them to maximize their benefit by not cheating on their used signal value. The advantage of an auto-selection is that it copes with frequent changes to the topology, as often found in VANETs.

In this model, a reward W is always greater than the cost paid by a node, provided that the node uses a signal corresponding to its credit. The two conditions given in (4), concern the reward on this model. The first condition concerns the rationality of a node. Each node chooses to use a signal Y to maximize its net benefit. This is found when the derivative of the wage is equal to the derivative of the cost with respect to the signal value. The second condition, sets the initial wage value, which has to be known beforehand by the nodes. Since the credit count of a node hints the real behavior of a node, the initial wage value depends on it to make it proportional to the real behavior of the node. The initial wage is set by dividing the credit of a node by a coefficient σ, such that the more σ is high, the more the application is strict regarding the final wage.

∂W ∂Y = ∂C ∂Y (Y, θ) W = θ σ ( 4
)
where σ>0

The resolution of this system, obtained by integrating Y 's value assuming that the minimum value of W and Y is equal to 0, gives us the final equation of the wage shown in [START_REF] Sobel | Signaling games[END_REF]:

∂W ∂Y = β θ α θ = W × σ ∂W ∂Y = β (W ×σ) α W α × ∂W ∂Y = β σ α ∞ 0 W α × ∂W ∂Y ∂Y = ∞ 0 β σ α ∂Y [W α+1 ] α+1 = β σ α × [Y ] W α+1 α+1 = β×Y σ α W = [ β×(α+1)×Y σ α ] 1 α+1 (5)
The reward value is added to the credit count of a source node by its TPM, providing that its sent message is validated by the most of the recipients. To verify this, each recipient notifies its own TPM about its decision regarding a received message, and an encrypted message about its decision of acceptance or not is sent to the source node. The message is encrypted to avoid case where a node accepts the received information but sends the refusal message to sabotage the source.

E. Optimum Signal Value

This model is designed in such a way that a node makes the maximum benefit when it uses the optimum signal value Y ⋆ regarding its credit. The optimum signal for each node is obtained from equation [START_REF] Sobel | Signaling games[END_REF], by replacing W by θ σ . The result is given in equation [START_REF] Spence | Signaling in retrospect and the informational structure of markets[END_REF].

Y ⋆ = θ α+1 σ × β × (α + 1) (6)
Failure to respect Y ⋆ causes a shortfall or a loss in credit, as illustrated in Fig. 3. This figure depicts two curves representing the signaling cost of two nodes, and another curve showing the received wage when the sent message is accepted. The first source node possesses 150 credits (i.e it has had a good behavior), and the second source node possesses only 40 (i.e it has had a bad behavior), given that the initial credit of the application θ initial is 100 credits. These curves show results for different signaling values ranging from 0 to 100, and are obtained by setting β = 3.5 • 10 4 , α=2.3, and σ=5 . We notice that the wage of the first node is more advantageous. But a shortfall is present for the two when they do not use the optimal signal values, which are Y ⋆ 1 and Y ⋆ 2 , respectively. The net benefit N B of the two nodes is observable in Fig. 3. It is at its maximum when the signaling value equals Y ⋆ . Its equation is given in ( 7) and the results using the same parameter values as before are illustrated in Fig. 4.

N B = W -C N B = [ β×(α+1)×Y σ α ] 1 α+1 -β×Y θ α (7)
Fig. 4 presents the curves of the net benefit for the two source nodes. We notice that the curve of the second node, which is less truthful than the first, decreases faster when it does not respect its optimum signal Y ⋆ . This clearly shows that because of bad behavior, nodes quickly exhaust their credit and are therefore evicted from the network.

F. Received Message Acceptance Process

A second way to encourage nodes to cooperate is to create the need for holding credits and earning them. For this reason, decrypting a received message is paid in this model. In the case where a node is selfish, its credit decreases slowly because of its inexistent or insufficient cooperation. To secure this part of the model, the cost of a received message, C msg , is fixed by the application, and subtracted from a recipient node's count by its TPM. This is only done in case of acceptance by the recipient. A validation decision is made with respect to the following two criteria:

• The reputation of the source node, held by the receiver.

• The used signal value by the source node. The used reputation, R t r (s), belongs to [0, 1], and is calculated at time t by the Receiver node r with respect to the source node, s. This reputation is local and is not shared in the network. Therefore, it is a firsthand reputation. If it is too bad, it represents an elimination criterion for the received message. This criterion is very important at the start of the application, when all the nodes have the same amount of credits and thus use the same signaling value. Its calculation can be done as described in [START_REF] Charikleia | Robust cooperative trust establishment for manets[END_REF]. After verifying the reputation criterion, a recipient node can base its acceptance on the signal used by the source. A minimum accepted signal is generally fixed to the value of the optimal signal value, Y ⋆ , for a node detaining only 20% of θ initial .

IV. PERFORMANCE EVALUATION

A. Simulation Setup

We evaluate the performance of our model by focusing on its ability to detect and evict malicious nodes, and to incite selfish nodes to cooperate more. In our scenario, a malicious node is a node that creates and sends false information, and that corrupts data before sending it during a retransmission. On the other hand, selfish nodes only participate out of selfinterest (i.e. when they do not have enough credit to decrypt received messages). To this end, we first measure the detection rate and average ratio of corrupted data respectively, in a network composed of 25% and 50% of malicious nodes. Then, the average data reception ratio is measured in a network composed of 25% and 50% of selfish nodes.

We conduct a set of simulations on N S2 [START_REF]The NS-2 website[END_REF] using VanetMobisim [START_REF] Fiore | Vehicular mobility simulation for vanets[END_REF] as vehicular mobility model in an urban scenario. We compare DT M 2 with a network not using any solution, and a network using a majority-based and experiencebased trust model presented in [START_REF] Minhas | Towards expended trust management for agents in vehicular ad-hoc networks[END_REF], which we refer to as MEB_Trust. The basic idea in MEB_Trust is that a node asks its neighbors, according to their categories, about the truthfulness of a received data, and considers it only if it reaches a majority consensus. This solution depends on the presence of trusted entities (e.g. police cars), which always respond correctly to nodes. For our simulation of this solution we include 3 police cars. The other simulation parameters are shown in Table I.

B. Result Analysis

The percentage of detected nodes for different compositions of malicious nodes in the network is illustrated in Fig. 5. A node is detected and evicted when it runs out of credits. The results show that the percentage of detection gradually increases, relatively quickly according to the number of malicious nodes in the network. Our solution is able to detect 50% of malicious nodes at around 800s, and it reaches 100% at around 3100s in a network composed of 25% of malicious nodes. Moreover, Fig. 6. Average received ratio of corrupted data with 25% and 50% of malicious nodes the false positive percentage does not exceed 8%, which means that a good behavior node is rarely mistakenly detected as being malicious.

Fig. 6 presents the average ratio of received corrupted data from malicious nodes, or retransmitted by good behavior nodes by mistake, in a network composed of 25% and 50% of malicious nodes. We note that when using DT M 2 , this ratio quickly decreases until reaching 0 after 2500s of simulated time for a network composed of 25%, and achieves a ratio of around 0.05 after 3600s of simulated time in a network composed of 50%. Moreover, while all malicious nodes have been evicted from the network when their credit is exhausted by using DT M 2 , it is not the when using MEB_Trust.

The effectiveness of our solution regarding its ability to incite selfish nodes to cooperate is visible on Fig. 7. The benefits of using our solution becomes evident, as the average data reception ratio in the presence of 25% of selfish nodes is the same that for the ideal case when no selfish nodes are present. This is because the need of obtaining credits is created among selfish nodes, since they need credits to decrypt their received messages. Moreover, when in the presence of 50% of selfish nodes, the average data reception ratio using DT M 2 is greater than the case where there is no deployed solution ratio in the presence of 25% of them.

V. CONCLUSION

In this paper, we proposed DT M 2 , a Distributed Trust Model for VANETs, adapted from Job Market Signaling, a well-known economics model used in case of asymmetric information. DT M 2 focuses on managing a tamper-proof credit count received by nodes at the start of the application. In order to detect and evict malicious nodes, it creates an auto-selection among the network's nodes and exhausts the credit for those nodes with bad behavior. Moreover, to improve the cooperation level of selfish nodes, it proposes inciting rewards. We showed via simulation the achievement of these two objectives in networks composed of 25%, and 50% of malicious or selfish nodes. In both of these cases, DT M 2 is able to gradually detect all malicious nodes and completely eliminate their negative effects on the network, while maintaining a low percentage of false positives. Furthermore, our approach is able to increase the cooperation of selfish nodes by 20% with respect to networks where no solution is deployed. As future work, we aim to improve our model to be used in different high mobility scenarios, and in combination with more sophisticated attacker models.

Fig. 1 .

 1 Fig. 1. Message exchange using DT M 2

Fig. 3 .

 3 Fig. 3. Cost and reward curves for different signal values

Fig. 4 .

 4 Fig. 4. Net benefit curves for different signal values

Fig. 5 .

 5 Fig. 5. Percentage of detected nodes: malicious and false positives

Fig. 7 .

 7 Fig. 7. Average ratio of received data with 0%, 25% and 50% of selfish node

TABLE I SIMULATION

 I PARAMETERS Number of nodes:100 Mac layers protocols: IEEE 802.11 Transmission range: 250 m Simulation time: 3600s Bandwidth: 11 Mbps Area size: 3 × 3 Km 2 Diffusion data algorithm: ADCD [2] Cmsg=C(Y ⋆ , θ initial )/5 Speed: 30-50 km/h β=3.5 • 10 4

		α=2.3
	σ=5	θ initial =100