Tomáš Pevný
email: pevnak@gmail.com

Patrick Bas
email: patrick.bas@gipsa-lab.inpg.fr

Jessica Fridrich
email: fridrich@binghamton.edu

Steganalysis by Subtractive Pixel Adjacency Matrix

Keywords: Steganalysis, LSB matching, ±1 embedding Categories and Subject Descriptors D.2.11 [Software Engineering]: Software Architecturesinformation hiding Security, Algorithms

This paper presents a novel method for detection of steganographic methods that embed in the spatial domain by adding a low-amplitude independent stego signal, an example of which is LSB matching. First, arguments are provided for modeling differences between adjacent pixels using first-order and second-order Markov chains. Subsets of sample transition probability matrices are then used as features for a steganalyzer implemented by support vector machines. The accuracy of the presented steganalyzer is evaluated on LSB matching and four different databases. The steganalyzer achieves superior accuracy with respect to prior art and provides stable results across various cover sources. Since the feature set based on second-order Markov chain is highdimensional, we address the issue of curse of dimensionality using a feature selection algorithm and show that the curse did not occur in our experiments.

INTRODUCTION

A large number of practical steganographic algorithms perform embedding by applying a mutually independent embedding operation to all or selected elements of the cover [START_REF] Fridrich | Digital image steganography using stochastic modulation[END_REF]. The effect of embedding is equivalent to adding to the cover an independent noise-like signal called stego noise. The weakest method that falls under this paradigm is the Least Significant Bit (LSB) embedding in which LSBs of individual cover elements are replaced with message bits. In this case, the stego noise depends on cover elements and the embedding operation is LSB flipping, which is asymmetrical. It is exactly this asymmetry that makes LSB embedding easily detectable [START_REF] Ker | A general framework for structural analysis of LSB replacement[END_REF][START_REF] Ker | A fusion of maximal likelihood and structural steganalysis[END_REF][START_REF] Ker | Revisiting weighted stego-image steganalysis[END_REF]. A trivial modification of LSB embedding is LSB matching (also called ±1 embedding), which randomly increases or decreases pixel values by one to match the LSBs with the communicated message bits. Although both steganographic schemes are very similar in that the cover elements are changed by at most one and the message is read from LSBs, LSB matching is much harder to detect. Moreover, while the accuracy of LSB steganalyzers is only moderately sensitive to the cover source, most current detectors of LSB matching exhibit performance that can significantly vary over different cover sources [START_REF] Ker | Feature reduction and payload location with WAM steganalysis[END_REF][START_REF] Cancelli | A comparative study of ±1 steganalyzers[END_REF].

One of the first detectors for embedding by noise adding used the center of gravity of the histogram characteristic function [START_REF] Harmsen | Steganalysis of additive noise modelable information hiding[END_REF][START_REF] Ker | Steganalysis of LSB matching in grayscale images[END_REF][START_REF] Li | Detecting LSB matching by applying calibration technique for difference image[END_REF]. A quantitative steganalyzer of LSB matching based on maximum likelihood estimation of the change rate was described in [START_REF] Soukal | Maximum likelihood estimation of secret message length embedded using ±k steganography in spatial domain[END_REF]. Alternative methods employing machine learning classifiers used features extracted as moments of noise residuals in the wavelet domain [START_REF] Holotyak | Blind statistical steganalysis of additive steganography using wavelet higher order statistics[END_REF][START_REF] Goljan | New blind steganalysis and its implications[END_REF] and from statistics of Amplitudes of Local Extrema in the graylevel histogram [START_REF] Cancelli | Detection of ±1 steganography based on the amplitude of histogram local extrema[END_REF] (further called ALE detector). A recently published experimental comparison of these detectors [START_REF] Ker | Feature reduction and payload location with WAM steganalysis[END_REF][START_REF] Cancelli | A comparative study of ±1 steganalyzers[END_REF] shows that the Wavelet Absolute Moments (WAM) steganalyzer [START_REF] Goljan | New blind steganalysis and its implications[END_REF] is the most accurate and versatile and offers good overall performance on diverse images.

The heuristic behind embedding by noise adding is based on the fact that during image acquisition many noise sources are superimposed on the acquired image, such as the shot noise, readout noise, amplifier noise, etc. In the literature on digital imaging sensors, these combined noise sources are usually modeled as an iid signal largely independent of the content. While this is true for the raw sensor output, subsequent in-camera processing, such as color interpolation, denoising, color correction, and filtering, creates complex dependences in the noise component of neighboring pixels. These dependences are violated by steganographic embedding because the stego noise is an iid sequence independent of the cover image. This opens the door to possible attacks. Indeed, most steganalysis methods in one way or another try to use these dependences to detect the presence of the stego noise.

The steganalysis method described in this paper exploits the fact that embedding by noise adding alters dependences between pixels. By modeling the differences between adja-cent pixels in natural images, we identify deviations from this model and postulate that such deviations are due to steganographic embedding. The steganalyzer is constructed as follows. A filter suppressing the image content and exposing the stego noise is applied. Dependences between neighboring pixels of the filtered image (noise residuals) are modeled as a higher-order Markov chain. The sample transition probability matrix is then used as a vector feature for a feature-based steganalyzer implemented using machine learning algorithms. Based on experiments, the steganalyzer is significantly more accurate than prior art.

The idea to model dependences between neighboring pixels by Markov chain appeared for the first time in [START_REF] Sullivan | Steganalysis of spread spectrum data hiding exploiting cover memory[END_REF]. It was then further improved to model pixel differences instead of pixel values in [START_REF] Zo | Steganalysis based on Markov model of thresholded prediction-error image[END_REF]. In our paper, we show that there is a great performance benefit in using higher-order models without running into the curse of dimensionality.

This paper is organized as follows. Section 2 explains the filter used to suppress the image content and expose the stego noise. Then, the features used for steganalysis are introduced as the sample transition probability matrix of a higher-order Markov model of the filtered image. The subsequent Section 3 experimentally compares several steganalyzers differing by the order of the Markov model, its parameters, and the implementation of the support vector machine (SVM) classifier. This section also compares the results with prior art. In Section 4, we use a simple feature selection method to show that our results were not affected by the curse of dimensionality. The paper is concluded in Section 5.

SUBTRACTIVE PIXEL ADJACENCY MA-TRIX

Rationale

In principle, higher-order dependences between pixels in natural images can be modeled by histograms of pairs, triples, or larger groups of neighboring pixels. However, these histograms possess several unfavorable aspects that make them difficult to be used directly as features for steganalysis:

1. The number of bins in the histograms grows exponentially with the number of pixels. The curse of dimensionality may be encountered even for the histogram of pixel pairs in an 8-bit grayscale image (256 2 = 65536 bins).

2. The estimates of some bins may be noisy because they have a very low probability of occurrence, such as completely black and completely white pixels next to each other.

3. It is rather difficult to find a statistical model for pixel groups because their statistics are influenced by the image content. By working with the noise component of images, which contains the most energy of the stego noise signal, we increase the SNR and, at the same time, obtain a tighter model.

The second point indicates that a good model should capture those characteristics of images that can be robustly estimated. The third point indicates that some pre-processing or calibration should be applied to increase the SNR, such as working with a noise residual as in WAM [START_REF] Goljan | New blind steganalysis and its implications[END_REF]. Figure 1: Distribution of two horizontally adjacent pixels (Ii,j, Ii,j+1) in 8-bit grayscale images estimated from ≈ 10000 images from the BOWS2 database (see Section 3 for more details about the database). The degree of gray at (x, y) is the probability P (Ii,j = x ∧ Ii,j+1 = y).

Representing a grayscale m × n image with a matrix {Ii,j|Ii,j ∈ N, i ∈ {1, . . . , m}, j ∈ {1, . . . , n}} , N = {0, 1, 2, . . .},

Figure 1 shows the distribution of two horizontally adjacent pixels (Ii,j, Ii,j+1) estimated from ≈ 10000 8-bit grayscale images from the BOWS2 database. The histogram can be accurately estimated only along the "ridge" that follows the minor diagonal. A closer inspection of Figure 1 reveals that the shape of this ridge (along the horizontal or vertical axis) is approximately constant across the grayscale values. This indicates that pixel-to-pixel dependences in natural images can be modeled by the shape of this ridge, which is, in turn, determined by the distribution of differences Ii,j+1 -Ii,j between neighboring pixels. By modeling local dependences in natural images using the differences Ii,j+1 -Ii,j, our model assumes that the differences Ii,j+1 -Ii,j are independent of Ii,j. In other words, for r = kl P (Ii,j+1 = k ∧ Ii,j = l) ≈ P (Ii,j+1 -Ii,j = r)P (Ii,j = l).

This "difference" model can be seen as a simplified version of the model of two neighboring pixels, since the co-occurence matrix of two adjacent pixels has 65536 bins, while the histogram of differences has only 511 bins. The differences suppress the image content because the difference array is essentially a high-pass-filtered version of the image (see below). By replacing the full neighborhood model by the simplified difference model, the information loss is likely to be small because the mutual information between the difference Ii,j+1-Ii,j and Ii,j estimated from ≈ 10800 grayscale images in the BOWS2 database is 7.615 • 10 -2 , 1 which means that the differences are almost independent of the pixel values.

Recently, the histogram characteristic function derived from the difference model was used to improve steganalysis of LSB matching [START_REF] Li | Detecting LSB matching by applying calibration technique for difference image[END_REF]. Based on our experiments, however, the first-order model is not complex enough to clearly distinguish between dependent and independent noise, which forced us to move to higher-order models. Instead, we model the differences between adjacent pixels as a Markov chain. Of course, it is impossible to use the full Markov model, because even the first-order Markov model would have 511 2 elements. By examining the histogram of differences ( Figure 2), we can see that the differences are concentrated around zero and quickly fall off. Consequently, it makes sense to accept as a model (and as features) only the differences in a small fixed range [-T, T ].

The SPAM features

We now explain the Subtractive Pixel Adjacency Model of covers (SPAM) that will be used to compute features for steganalysis. First, the transition probabilities along eight directions are computed. 2 The differences and the transition probability are always computed along the same direction. We explain further calculations only on the horizontal direction as the other directions are obtained in a similar manner. All direction-specific quantities will be denoted by a superscript {←, →, ↓, ↑, , , , } showing the direction of the calculation.

The calculation of features starts by computing the difference array D • . For a horizontal direction left-to-right

D → i,j = Ii,j -Ii,j+1, i ∈ {1, . . . , m}, j ∈ {1, . . . , n -1}.
1 Huang et al. [START_REF] Huang | Statistics of natural images and models[END_REF], estimated the mutual information between Ii,j -Ii,j+1and Ii,j + Ii,j+1 to 0.0255. 2 There are four axes: horizontal, vertical, major and minor diagonal, and two directions along each axis, which leads to eight directions in total.

Order T Dimension 1st 4 162 2nd 3 686

Table 1: Dimension of models used in our experiments. Column "order" shows the order of the Markov chain and T is the range of differences.

As introduced in Section 2.1, the first-order SPAM features, F 1st , model the difference arrays D by a first-order Markov process. For the horizontal direction, this leads to

M → u,v = P (D → i,j+1 = u|D → i,j = v),
where u, v ∈ {-T, . . . , T }.

The second-order SPAM features, F 2nd , model the difference arrays D by a second-order Markov process. Again, for the horizontal direction,

M → u,v,w = P (D → i,j+2 = u|D → i,j+1 = v, D → i,j = w),
where u, v, w ∈ {-T, . . . , T }.

To decrease the feature dimensionality, we make a plausible assumption that the statistics in natural images are symmetric with respect to mirroring and flipping (the effect of portrait / landscape orientation is negligible). Thus, we separately average the horizontal and vertical matrices and then the diagonal matrices to form the final feature sets, F 1st , F 2nd . With a slight abuse of notation, this can be formally written:

F • 1,...,k = 1 4 h M → • + M ← • + M ↓ • + M ↑ • i , F • k+1,...,2k = 1 4 h M • + M • + M • + M • i , (1)
where k = (2T + 1) 2 for the first-order features and k = (2T + 1) 3 for the second-order features. In experiments described in Section 3, we used T = 4 for the first-order features, obtaining thus 2k = 162 features, and T = 3 for the second-order features, leading to 2k = 686 features (c.f., Table 1).

To summarize, the SPAM features are formed by the averaged sample Markov transition probability matrices (1) in the range [-T, T ]. The dimensionality of the model is determined by the order of the Markov model and the range of differences T ).

The order of the Markov chain, together with the parameter T , controls the complexity of the model. The concrete choice depends on the application, computational resources, and the number of images available for the classifier training. Practical issues associated with these choices are discussed in Section 4.

The calculation of the difference array can be interpreted as high-pass filtering with the kernel [-1, +1], which is, in fact, the simplest edge detector. The filtering suppresses the image content and exposes the stego noise, which results in a higher SNR. The filtering can be also seen as a different form of calibration [START_REF] Fridrich | Feature-based steganalysis for JPEG images and its implications for future design of steganographic schemes[END_REF]. From this point of view, it would make sense to use more sophisticated filters with a better SNR. Interestingly, none of the filters we tested 3 provided consistently better performance. We believe that the superior accuracy of the simple filter [-1, +1] is because it does not distort the stego noise as more complex filters do.

EXPERIMENTAL RESULTS

To evaluate the performance of the proposed steganalyzers, we subjected them to tests on a well known archetype of embedding by noise adding -the LSB matching. We constructed and compared the steganalyzers that use the firstorder Markov features with differences in the range [-4, +4] (further called first-order SPAM features) and second-order Markov features with differences in the range [-3, +3] (further called second-order SPAM features). Moreover, we compared the accuracy of linear and non-linear classifiers to observe if the decision boundary between the cover and stego features is linear. Finally, we compared the SPAM steganalyzers with prior art, namely with detectors based on WAM [START_REF] Goljan | New blind steganalysis and its implications[END_REF] and ALE [START_REF] Cancelli | Detection of ±1 steganography based on the amplitude of histogram local extrema[END_REF] features.

Experimental methodology

Image databases

It is a well-known fact that the accuracy of steganalysis may vary significantly across different cover sources. In particular, images with a large noise component, such as scans of photographs, are much more challenging for steganalysis than images with a low noise component or filtered images (JPEG compressed). In order to assess the SPAM models and compare them with prior art under different conditions, we measured their accuracy on four different databases:

1. CAMERA contains ≈ 9200 images captured by 23 different digital cameras in the raw format and converted to grayscale.

2. BOWS2 contains ≈ 10800 grayscale images with fixed size 512 × 512 coming from rescaled and cropped natural images of various sizes. This database was used during the BOWS2 contest [START_REF] Bas | BOWS-2[END_REF].

3. NRCS consists of 1576 raw scans of film converted to grayscale [1].

4. JPEG85 contains 9200 images from CAMERA compressed by JPEG with quality factor 85.

5. JOINT contains images from all four databases above, ≈ 30800 images.

All classifiers were trained and tested on the same database of images. Even though the estimated errors are intradatabase errors, which can be considered artificial, we note here that the errors estimated on the JOINT database can be actually close to real world performance.

Prior to all experiments, all databases were divided into training and testing subsets with approximately the same number of images. In each database, two sets of stego images were created with payloads 0.5 bits per pixel (bpp) and 0.25 bpp. According to the recent evaluation of steganalytic methods for LSB matching [START_REF] Cancelli | A comparative study of ±1 steganalyzers[END_REF], these two embedding rates and discrete filters,

" 0 +1 0 +1 -4 +1 0 +1 0 # , [+1, -2, +1], and [+1, +2, -6, +2, +1].
are already difficult to detect reliably. These two embedding rates were also used in [START_REF] Goljan | New blind steganalysis and its implications[END_REF].

The steganalyzers' performance is evaluated using the minimal average decision error under equal probability of cover and stego images

PErr = min 1 2 (PFp + PFn) , (2)
where PFp and PFn stand for the probability of false alarm or false positive (detecting cover as stego) and probability of missed detection (false negative). 4

Classifiers

In the experiments presented in this section, we used exclusively soft-margin SVMs [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF]. Soft-margin SVMs can balance complexity and accuracy of classifiers through a hyperparameter C penalizing the error on the training set. Higher values of C produce classifiers more accurate on the training set that are also more complex with a possibly worse generalization. 5 On the other hand, a smaller value of C leads to a simpler classifier with a worse accuracy on the training set.

Depending on the choice of the kernel, SVMs can have additional kernel parameters. In this paper, we used SVMs with a linear kernel, which is free of any parameters, and SVMs with a Gaussian kernel, k(x, y) = exp `-γxy 2

2

´, with width γ > 0 as the parameter. The parameter γ has a similar role as C. Higher values of γ make the classifier more pliable but likely prone to overfitting the data, while lower values of γ have the opposite effect.

Before training the SVM, the value of the penalization parameter C and the kernel parameters (in our case γ) need to be set. The values should be chosen to obtain a classifier with a good generalization. The standard approach is to estimate the error on unknown samples by cross-validation on the training set on a fixed grid of values, and then select the value corresponding to the lowest error (see [START_REF] Hsu | A Practical Guide to ± Support Vector Classification[END_REF] for details). In this paper, we used five-fold cross-validation with the multiplicative grid: C ∈ {0.001, 0.01, . . . , 10000}.

γ ∈ {2 i |i ∈ {-d -3, . . . , -d + 3},
where d is number of features in the subset.

Linear or non-linear?

This paragraph compares the accuracy of steganalyzers based on first-order and second-order SPAM features, and steganalyzers implemented by SVMs with Gaussian and linear kernels. The steganalyzers were always trained to detect 4 For SVMs, the minimization in ( 2) is carried over the set containing just one tuple (PFp, PFn) by varying the threshold because the training algorithm of SVMs outputs one fixed classifier for each pair (PFp, PFn) rather than a set of classifiers. In our implementation, the reported error is calculated according to 1 l P l i=1 I(yi, ŷi), where I(•, •) is the indicator function attaining 1 iff yi = ŷi, and 0 otherwise, yi is the true label of the i th sample and ŷi is the label returned by the SVM classifier. In case of an equal number of positive and negative samples, the error provided by our implementation equals to the error calculated according to (2). 5 The ability of classifiers to generalize is described by the error on samples unknown during the training phase of the classifier. Results, summarized in Table 3.2, show that steganalyzers implemented as Gaussian SVMs are always better than their linear counterparts. This shows that the decision boundaries between cover and stego features are nonlinear, which is especially true for databases with images of different size (Camera, JPEG85). Moreover, the steganalyzers built from the second-order SPAM model with differences in the range [-3, +3] are also always better than steganalyzers based on first-order SPAM model with differences in the range [-4, +4], which indicates that the degree of the model is more important than the range of the differences.

Comparison with prior art

Table 3 shows the classification error (2) of the steganalyzers using second-order SPAM (686 features), WAM [START_REF] Goljan | New blind steganalysis and its implications[END_REF] (81 features), and ALE [START_REF] Cancelli | Detection of ±1 steganography based on the amplitude of histogram local extrema[END_REF] (10 features) on all four databases and for two relative payloads. We have created a special steganalyzer for each combination of the database, features, and payload (total 4×3×2 = 24 steganalyzers). The steganalyzers were implemented by SVMs with a Gaussian kernel as described in Section 3.1.2.

Table 3 also clearly demonstrates that the accuracy of steganalysis greatly depends on the cover source. For images with a low level of noise, such as JPEG-compressed images, the steganalysis is very accurate (PErr = 0.8% on images with payload 0.25 bpp). On the other hand, on very noisy images, such as scanned photographs from the NRCS database, the accuracy is obviously worse. Here, we have to be cautious with the interpretation of the results, because the NRCS database contains only 1500 images, which makes the estimates of accuracy less reliable than on other, larger image sets.

In all cases, the steganalyzers that used second-order SPAM features perform the best, the WAM steganalyzers are second with about three times higher error, and ALE steganalyzers are the worst. Figure 3 compares the steganalyzers in selected cases using the receiver operating characteristic curve (ROC), created by varying the threshold of SVMs with the Gaussian kernel. The dominant performance of SPAM steganalyzers is quite apparent.

CURSE OF DIMENSIONALITY

Denoting the number of training samples as l and the number of features as d, the curse of dimensionality refers to overfitting the training data because of an insufficient number of training samples and a large dimensionality d (e.g., the ratio l d is too small). In theory, the number of training samples depends exponentially on the dimension of the training set, but the practical rule of thumb states that the number of training samples should be at least ten times the dimension of the training set.

One of the reasons for the popularity of SVMs is that they are considered resistant to the curse of dimensionality and to uninformative features. However, this is true only for SVMs with a linear kernel. SVMs with the Gaussian kernel (and other local kernels as well) can suffer from the curse of dimensionality and their accuracy can be decreased by uninformative features [START_REF] Bengio | The curse of dimensionality for local kernel machines[END_REF]. Because the dimensionality of the second-order SPAM feature set is 686, the feature set may be susceptible to all the above problems, especially for experiments on the NRCS database.

This section investigates whether the large dimensionality and uninformative features negatively influence the performance of the steganalyzers based on second-order SPAM features. We use a simple feature selection algorithm to select subsets of features of different size, and observe the discrepancy between the errors on the training and testing sets. If the curse of dimensionality occurs, the difference between both errors should grow with the dimension of the feature set.

Details of the experiment

The aim of feature selection is to select a subset of features so that the classifier's accuracy is better or equal to the classifier implemented using the full feature set. In theory, finding the optimal subset of features is an NP-complete problem [START_REF] Guyon | Feature Extraction, Foundations and Applications[END_REF], which frequently suffers from overfitting. In order to alleviate these issues, we used a very simple feature selection scheme operating in a linear space. First, we calculated the correlation coefficient between the i th feature xi and the number of embedding changes in the stego image y according to

6 corr(xi, y) = E[xiy] -E[xi]E[y] p E[x 2 i ] -E[xi] 2 • p E[y 2 ] -E[y] 2 (3)
Second, a subset of features of cardinality k was formed by selecting k features with the highest correlation coefficient. 7 The advantages of this approach to feature selection are a good estimation of the ranking criteria, since the features are evaluated separately, and a low computational complexity. The drawback is that the dependences between multiple features are not evaluated, which means that the selected subsets of features are almost certainly not optimal, i.e., there exists a different subset with the same or smaller number of features with a better classification accuracy. Despite this weakness, the proposed method seems to offer a good 1 n P n j=1 xi,jyj, where xi,j denotes the i th element of the j th feature vector. 7 This approach is essentially equal to feature selection using the Hilbert-Schmidt independence criteria with linear kernels [START_REF] Song | Supervised feature selection via dependence estimation[END_REF]. For each subset, we trained an SVM classifier with a Gaussian kernel as follows. The training parameters C, γ were selected by a grid-search with five-fold cross-validation on the training set as explained in Section 3.1.2. Then, the SVM classifier was trained on the whole training set and its accuracy was estimated on the testing set.

Experimental results

Figure 4 shows the errors on the training and testing sets on four different databases. We can see that even though the error on the training set is smaller than the error on the testing set, which is the expected behavior, the differences are fairly small and do not grow with the feature set dimensionality. This means that the curse of dimensionality did not occur.

The exceptional case is the experiment on the NRCS database, in particular the test on stego images with payload 0.25 bpp. Because the training set contained only ≈ 1400 examples (700 cover and 700 stego images), we actually expected the curse of dimensionality to occur and we included this case as a reference case. We can observe that the training error is rather erratic and the difference between training and testing errors increases with the dimension of the feature set. Surprisingly, the error on the testing set does not grow with the size of the feature set. This means that even though the size of the training is not sufficient, it is still better to use all features and rely on regularization of SVMs to prevent overtraining rather than to use a subset of features.

Discussion of feature selection

In agreement with the findings published in [START_REF] Ker | Feature reduction and payload location with WAM steganalysis[END_REF][START_REF] Miche | Reliable steganalysis using a minimum set of samples and features[END_REF], our results indicate that feature selection does not significantly improve steganalysis. The authors are not aware of a case when a steganalyzer built from a subset of features provided significantly better results than a classifier with a full feature set. This remains true even in extreme cases, such as our experiments on the NRCS database, where the number of training samples was fairly small.

From this point of view, it is a valid question whether feature selection provides any advantages to the steganalyst. The truth is that the knowledge of important features reveals weaknesses of steganographic algorithms, which can help design improved versions. At the same time, the knowledge of the most contributing features can drive the search for better feature sets. For example, for the SPAM features we might be interested if it is better to enlarge the scope of the Markov model by increasing its order or the range of differences, T . In this case, feature selection can give us a hint. Finally, feature selection can certainly be used to reduce the dimensionality of the feature set and consequently speed up the training of classifiers on large training sets. In experiments showed in Figure 4, we can see that using more than 200 features does not bring a significant improvement in accuracy. At the same time, one must be aware that the feature selection is database-dependent as only 114 out of 200 best features were shared between all four databases.

CONCLUSION

The majority of steganographic methods can be interpreted as adding independent realizations of stego noise to the cover digital-media object. This paper presents a novel approach to steganalysis of such embedding methods by utilizing the fact that the noise component of typical digital media exhibits short-range dependences while the stego noise is an independent random component typically not found in digital media. The local dependences between differences of neighboring pixels are modeled as a Markov chain, whose sample probability transition matrix is taken as a feature vector for steganalysis.

The accuracy of the steganalyzer was evaluated and compared with prior art on four different image databases. The proposed method exhibits an order of magnitude lower average detection error than prior art, consistently across all four cover sources.

Despite the fact that the SPAM feature set has a high dimension, by employing feature selection we demonstrated that curse of dimensionality did not occur in our experiments.

In our future work, we would like to use the SPAM features to detect other steganographic algorithms for spatial domain, namely LSB embedding, and to investigate the limits of steganography in the spatial domain to determine the maximal secure payload for current spatial-domain embedding methods. Another direction worth pursuing is to use the third-order Markov chain in combination with feature selection to further improve the accuracy of steganalysis. Finally, it would be interesting to see whether SPAM-like features can detect steganography in transform-domain formats, such as JPEG.

ACKNOWLEDGMENTS

Tomáš Pevný and Patrick Bas are supported by the National French projects Nebbiano ANR-06-SETIN-009, ANR-RIAM Estivale, and ANR-ARA TSAR. The work of Jessica Fridrich was supported by Air Force Office of Scientific Research under the research grant number FA9550-08-1-0084. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation there on. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied of AFOSR or the U.S. Government. We would also like to thank Mirek Goljan for providing the code for extraction of WAM features, and Gwenaël Doërr for providing the code for extracting ALE features.

0 2 • 10 - 6 6 • 10 - 6 1 • 10 - 5 4 • 10 - 5 1 • 10 - 4 3 • 10 - 4 9 • 10 - 4 2 • 10 - 3 6 • 10 - 3 1 • 10

 210610610510510410410410310310

Figure 2 :

 2 Figure 2: Histogram of differences of two adjacent pixels, Ii,j+1 -Ii,j, in the range [-20, 20] calculated over ≈ 10800 grayscale images from the BOWS2 database.

Table 2 :

 2 Minimal average decision error (2) of steganalyzers implemented using SVMs with Gaussian and linear kernels on images from the testing set. The lowest error for a given database and message length is in boldface. {10, 20, 30, . . . , 190, 200, 250, 300, . . . , 800, 850}.

			Gaussian kernel	Linear kernel
		bpp 1st SPAM 2nd SPAM	1st SPAM 2nd SPAM
	CAMERA 0.25	0.097	0.057	0.184	0.106
	BOWS2	0.25	0.098	0.053	0.122	0.063
	NRCS	0.25	0.216	0.178	0.290	0.231
	JPEG85	0.25	0.021	0.008	0.034	0.013
	CAMERA 0.5	0.045	0.030	0.088	0.050
	BOWS2	0.5	0.040	0.003	0.048	0.029
	NRCS	0.5	0.069	0.025	0.127	0.091
	JPEG85	0.5	0.007	0.075	0.011	0.004

We experimented with the adaptive Wiener filter with 3 × 3 neighborhood, the wavelet filter[START_REF] Mihcak | Low-complexity image denoising based on statistical modeling of wavelet coefficients[END_REF] used in WAM,

In Equation (3), E[•] stands for the empirical mean over the variable within the brackets. For example E[xiy] =


Frédéric Loiret
email: frederic.loiret@inria.fr

Juan Navas

Jean-Philippe Babau
email: jean-philippe.babau@univ-brest.fr

Olivier Lobry

Component-Based Real-Time Operating System for Embedded Applications

As embedded systems must constantly integrate new functionalities, their developement cycles must be based on high-level abstractions, making the software design more flexible. CBSE provides an approach to these new requirements. However, low-level services provided by operating systems are an integral part of embedded applications, furthermore deployed on resource-limited devices. Therefore, the expected benefits of CBSE must not impact on the constraints imposed by the targetted domain, such as memory footprint, energy consumption, and execution time. In this paper, we present the componentization of a legacy industry-established Real-Time Operating System, and how componentbased applications are built on top of it. We use the Think framework that allows to produce flexible systems while paying for flexibility only where desired. Performed experimentions show that the induced overhead is negligeable.

Introduction

Until recently, embedded systems were defined as resource constrained, dedicated and closed computing systems buried within an electro-mechanical structure they interact with. Much of the embedded systems are also real-time systems, i.e. systems in which temporal predictability is a key issue.

While limited resources constraint remains, paradigms like Everyware [13] boosted embedded systems development; growing demand in embedded devices market imposes new preoccupations such as Time to Market, industrial standards compliance, and adaptability to dynamic operation context. Consequently, embedded systems can no longer be closed and specific-task systems, since they must adapt themselves to the surrounding environment. System's design, development, deployment, and maintenance complexity has increased and traditional code-centric methodologies are no longer suitable, not only at application level, but also at operating system level since the latter is integral part of embedded applications.

Component-Based Software Engineering (CBSE) [START_REF] Szypersky | Component Software. Beyong Object-Oriented Programming[END_REF] addresses several aspects in today's embedded systems development. Systems are designed by assembling software and system components [START_REF] Kopetz | Compositional Design of RT Systems: A Conceptual Basis for Specification of Linking Interfaces[END_REF] and may evolve at execution time through dynamic reconfiguration [START_REF] Polakovic | Building Reconfigurable Component-Based OS with THINK[END_REF]. CBSE is particularly useful in handling the multiple variants of a same product line, as components can be treated as independent, arbitrary fine-grained entities to be deployed in heterogeneus devices. Several approaches, some of them inspired by CBSE paradigm, have been applied to obtain similar design and run-time benefits in the resources-constrained systems domain:

• Virtual machines and bytecode/script interpreters [START_REF] Levis | Maté: A Tiny Virtual Machine for Sensor Networks[END_REF][START_REF] Michiels | DAViM: a Dynamically Adaptable Virtual Machine for Sensor Networks[END_REF][START_REF] Xie | Tapper: a Lightweight Scripting Engine for Highly Constrained Wireless Sensor Nodes[END_REF] allow runtime flexibility in very resource-limited platforms such as sensor networks motes. However, peformance penalty increases as virtual machines are designed to be less application-specific, making this approach not scalable for more general realtime embedded systems product lines.

• Real-time embedded systems can be built by compiling component-based architecture descriptions [START_REF] Van Ommering | The Koala Component Model for Consumer Electronics Software[END_REF][START_REF] Levis | TinyOS: An Operating System for Sensor Networks[END_REF]. By this way, design-time CBSE benefits are preserved but the notion of component disappears at run-time, failing to take advantage of a global CBSE approach. Also, existing framework programming models make difficult the introduction of real-time specific concepts and prior developements.

• Component-based versions of executive parts can be integrated to realtime component-based applications that means to assemble OS-related services or to componentize existing RTOS source code. This approach globally preserves CBSE benefits, but may induce a significant overhead concerning critical metrics of embedded systems such as memory footprint, real-time responsiveness and execution time. However, recent studies [START_REF] Lobry | Controlling the Performance Overhead of Component-Based Systems[END_REF] show that it is possible to control and to limit the possible overheads caused by flexibility support.

The contribution of this paper follows this last approach. It presents how an existing real-time operating system, µC/OS-II, is componentized, as well as the considerations that shall be respected in this re-engineering task. We use the Think component framework [START_REF] Fassino | Think: A software framework for component-based operating system kernels[END_REF][START_REF] Anne | Think: View-Based Support of Non-Functional Properties in Embedded Systems[END_REF], an implementation of the Fractal component model [START_REF] Bruneton | The Fractal Component Model[END_REF] that fullfills the constraints of embedded-systems. This component model is used in a homogeneous way at both application and operating system levels. A Think component is an entity that is preserved during the whole system life cycle with minimal performance overhead.

The paper is organized as follows: Section 2 briefly describes µC/OS-II RTOS, Think framework and its underlying Fractal component model. Section 3 identifies challenges to be faced in a RTOS componentization task; Section 4 details the componentization scheme. Section 5 presents a use-case benchmark that demonstrates the benefits of our approach. Section 6 describes related work. Section 7 concludes the paper.

Background

This section presents the features of the µC/OS-II kernel and the Think component framework. We stress in Section 2.3 the reasons that led us to conduct our work grounded on these two projects.

2.1

The µC/OS-II RTOS µC/OS-II is a preemptive, real-time multitasking kernel for microprocessors and microcontrollers. It is implemented in ANSI C and certified by the FAA 4 for use in software intended to be deployed in avionics equipment. It has been massively used in many embedded and safety critical systems products worldwide.

The main services provided by µC as an RTOS are sketched out in Fig. 1, which gives the module structure of the kernel distribution. The main services are implemented within the Core, the Task and the Port modules. The latter implements the hardware-dependent services. µC/OS is implemented as a monolithic kernel, i.e. it is built from a number of functions that share common global variables and data types (such as task control block, event control block, etc).

It is a highly configurable kernel, whose configuration relies on more than 70 parameters. Since the kernel is provided in source form, configurability is done via conditional compilation at precompilation time, based on #define constants. µC allows to scale down, the main objective being to reduce the memory footprint of the final executable (up to several KBytes, depending on the processor). Hence, it is possible to avoid code generation of non required services, or to reduce the size of data structures used by the kernel. Several parameters allow developers to configure essential properties of the kernel, e.g. the tick frequency.

The execution time for most of these services is both constant and deterministic, which is a compulsory requirement for real-time systems in order to avoid unpredictable kernel jitter [START_REF] Angelov | A Jitter-Free Kernel for Hard Real-Time Systems[END_REF].

For a full description of the features, the design and the internals of µC/OS-II, we refer the interested reader to the book [2]5 .

The Think component framework

Think is an implementation of the Fractal component model that aims to take into account the specific constraints of embedded systems development. The Fractal specifications [START_REF] Bruneton | The Fractal Component Model[END_REF] define a hierarchical, reflective and general-purpose component model. A component definition exports functional interfaces (provided or required), configuration attributes, and may also provide non-functional interfaces implementing introspection and architectural reconfiguration services at run-time.

The Think framework allows developers to build embedded systems made out of Fractal components. A system architecture is described using an Architecture Description Language (ADL), interfaces are defined using an Interface Description Language (IDL). The code that implements the method of server interfaces is written in regular C (or wrapped assembler language) where ADL symbols are represented by convenient C symbols. The mapping between ADL symbols and C symbols can be specified using annotations in commentary section of the C files which facilitates the encapsulation of legacy code. An example of a Think component definition is given in Figure 2 The Think compiler maps architectural elements to C variables in implementation code, transforms existing functional code and produces meta-data and implementation of non-functional interfaces. The meta-data typically allow to retrieve an attribute, the descriptor of a bound-to server interface of the component context of a bound-to component. The resulting C code is then passed to traditional C compilers and linkers to generate the final binary file.

Since applying the component paradigm can easily impacts on performances, the Think compiler provides tools to produce, from a same architectural description, different binary images with different performance versus flexibilty tradeoffs. Architectural elements can be tagged with flexibility-oriented properties in an Aspect-Oriented-Programming manner. These properties will be interpreted by the compiler to generate an optimized binary image that only embeds flexibility where actually desired. For example:

-The address of the context of a single component is known at compile-time and need not be passed in calls; -A constant attribute is implemented as a compile-time constant and no metadata is generated; -A static binding does not generate meta-data and calls to the corresponding client interface are implemented as direct function calls; -The implementation code of the server interface can even be inlined in the caller; -no meta-data is generated for a server interface to which all bindings are static.

µC/OS-II and Think are good canditates

Regarding our experiment, µC/OS is a good candidate for the following reasons:

-It is a mature real-time operating system used in many industrial projects.

-A fundamental particularity of µC/OS resides in its determinist nature, which is a basic property to consider, and to preserve in a reengineering of its internal structure. -Its highly configurable capability is an interesting property that can help to compare with a component-based approach for which only the required services of the application are linked by composition within the final binary. -µC/OS was designed to be portable, and a special attention has been paid to clearely distinguish between the generic code and the hardware dependent code. This eases the separation of concerns applied to an implementation designed with the component paradigm.

Considering the Think framework and its underlying component model, we can highlight the following points:

-The component paradigm adopted by the Think framework provides a high degree of flexibility, which combined with the genericity and configurability of the Fractal component model, allows the construction of dedicated and fully configurable operating systems.

-Architecture-oriented optimizations make Think specially well suited for resource-limited embedded systems, as they allow to specify where flexibility capabilities should be added and which Fractal non-functional interfaces should be provided by components. -Several case studies have been conducted with Think to design minimal operating systems for various embedded platforms7 (ARM, PowerPC, AVR, Xscale, etc). These experiments demonstrate the robustness of the tools constituing the Think framework.

Challenges considering a µC componentization

Since a component is a basic first-class reuse entity, the separation of concerns is a key concept of CBSE. Improving this separation implies maximizing the decoupling between components in terms of encapsulated data and services. As a first challenge, considering that our experiment is based on an RTOS which was not initially designed as a component-based architecture, an important reengineering effort of the µC/OS's implementation should be considered. The component paradigm is based on abstractions which are well-suited to address flexibility requirements for complex systems. In our approach, we are interested in providing such a flexibility not only at application level but also at RTOS level. From a design point of view, we want to provide a framework to build both an application-dedicated executive part and also reusable parts of executive off-theshelf components. Since the component is a configurability unit for the developer, the granularity of components is a crucial point to consider according to these flexibility requirements. Furthermore, we have to provide the ability to choose and tune existing components. It should be possible within the design process to tailor the components according to various execution contexts. For example, to provide several implementations of a given component without changing its specifications, or to implement various parts of a complex communication protocol, etc. These aspects play a major role in the design and the developement of embedded systems. At the end, to mitigate the constraints of resource limited platforms, only the strictly required RTOS components should be embedded in the deployed system.

A third challenge appears when considering flexibility at runtime. Indeed, since the basic reconfiguration units are the components, their attributes and their assemblies are specified via bindings, and these concepts should thus be reified at runtime. Moreover, considering that our experiment tackles several very low-level RTOS services which will not be adapted at runtime, it is not compulsorily required to provide such reconfiguration capabilities for any components of the architecture. This requirement is a basic aspect to tackle considering the targetted application domain.

Last, but not least, the impact on execution time and memory footprint must be considered. An RTOS implementation designed following the compo-nent paradigm and the aforementionned flexibility requirements should not involve unbounded overheads in term of performance. Moreover, the component framework should not introduce indeterminism in the execution of the RTOS services.

µC/OS Componentization

Motivations for a µC/OS's reengineering

The modular structure of µC is a good starting point for our componentization process since the core functionalities of the OS are clearly identified. However, we considered several parameters in order to improve the separation of concerns in the resulting component-based infrastructure proposed in the next section.

First, we considered the basic aspects usually defined within a real-time kernel [START_REF] Buttazzo | Hard Real-Time Computing Systems[END_REF][START_REF] Stankovic | Real-Time Operating Systems[END_REF]. The two main aspects of an RTOS are the Task Management, for scheduling and the dispatching of tasks, and the Event Management, mainly for hardware events processing. Because these two aspects expose key features of an RTOS, we considered as a requirement the reification of them at architectural level. Moreover, since they are tangled over several µC modules, a reengineering of the kernel source code has been performed.

Legend: 0 0 to 0.3 0.3 to 0.4 0.4 to 0.8 0.8 to 1

• •• • • • Core Task Time Port Flag Mem Tmr IPC Core • • • • • • • • • • • Task • • • • • Time Flag • Mem Timer •• •• • IPC • • • Fig. 3.
Coupling between µC modules based on function dependencies.

Second, we have conducted several coupling analysis within the original µC/OS implementation. The Fig. 3 presents a coarse-grained coupling between µC modules8 based on the function dependencies. To compute the coupling metric between modules A and B, the number of function calls between them is divided by the total number of function call between A and the other modules 9 . This analysis highlights for example a tightly coupling between the Task and the Core modules. Indeed, the latter implements several functions related to Task Management. The Port module provides the functions to enable/disable hardware interrupts necessary for global variables protection. This explains the thightly coupling between all the modules to these functions. We have also conducted this coupling analysis with the global variables access, the data types definition and the configuration constants. This analysis helped us to propose the fine-grained component-based design of µC presented in the next section.

Description of the Componentization Process

The componentization process of the operating system has been conducted in the following steps:

1. Interface Definitions. The µC function definitions are specified with the Think IDL. For each type of service (e.g. timer management, task management, etc), a set of interfaces are defined according to their nature -creation or deletion of a resource, commonly or rarely used functions -and ordered within packages (e.g. see Fig. 2). Furthermore, we make a distinction between internal interfaces which are used only between µC modules, and public interfaces which provide all services visible at the application level following a set of system calls that may be invoked by application tasks.

Componentization.

As a first componentization level, we define an architecture structured as the original µC implementation: each module sketched in Fig. 1 is reified as a primitive component using the Think ADL. The architectural artifacts of these ADL descriptions are expressed within source code using annotations to inform the Think compiler of this mapping. These components are encapsulated into a top-level composite that exposes the public interfaces available for the application tasks.

From this componentization level, and following the reengeneering motivations exposed in Section 4.1, the architecture is refined. RTOS key-features scattered over the modules were reified as components, and resulting tighly-coupled functions are merged.

3. Global Variables Expressed at Architectural Level. Within our componentization process, each µC/OS' global variable is defined as private data of primitive component (i.e. "task-related variables" defined within the TaskManager Component). Getter/setter functions are specified according to the data type definition of each variable and mapped to internal interfaces. The access to these variables between components are then expressed at architectural level via basic bindings.

4. Resources Components. From our point of view, within a CBSE design process, the resources of the operating system used by the application (such as a semaphore, a mailbox or a timer) should be reified at the architectural level. Therefore, µC/OS resources are represented by primitive components, called resource wrappers. Application components access these resources using basic bindings. This approach allows the developer to configure these resources from their exported configuration attributes (e.g. the task priority, the initial value of a semaphore, etc). Examples of such resource wrappers are given in Fig. 6.

Attribute Definitions.

From the configuration parameters defined by µC/OS, we isolate two kinds of attributes. First, those which let the architect configure essential properties of the RTOS, such as the tick frequency, the priority assigned to the task managing the timer. Second, those which specify the thresholds for the use of ressources managed by the RTOS, e.g. the maximum number of tasks or semaphores supported by the kernel, the size of strings for event names, etc. Attribute signatures are thus defined (with naming conventions according to their kind) and attached to component definitions.

6. Component Library. Finally, we provide a library of ready-to-use RTOS, as a set of composite components, according to the services that they provide to the application (via their public interfaces).

An example of such a componentized RTOS is presented Fig. 4. It corresponds to the minimal operating system required by the application presented in the next section. The non-functional interface init (e.g. for the TaskManager Component) is invoqued by a Think-generated life-cycle-controller component that manages, among others, system initialization.

Evaluation

In this section, we evaluate our component-based design of µC/OS in comparison with its original implementation. As a qualitative evaluation in Section 5.2, we present how a classical multi-task application is designed using functional and resource components compared to a "pure C" implementation. We show how design time and runtime flexibility is addressed within our approach. Finally, we conduct benchmark tests in Section 5.3 to measure performance and memory footprint overheads introduced by the component-based design.

Motivation example

To better illustrate several aspects of the following evaluation, we introduce in Fig. 5 a typical real-time and embedded application scenario that will be revisited throughout the course of this section. This example is composed of Fig. 5. A real-time application example.

three tasks. The tasks Task1 and Task2 read and write a shared data which is protected by a binary semaphore (execution steps 1 -3 ). A task pending on the semaphore (via the acquire service) can not be blocked more than 4 time units (which corresponds to a timeout specified by the semaphore). Task2 is activated periodically by a timer, while Task1 is activated in response to an external interrupt event. At the end of its execution cycle, Task1 sends the content of the read data to the Task3 using a mailbox (execution step 4 ). This example illustrates the basic concepts used to design a real-time application.

Qualitative evaluation

Design space provided to the application developer. Within our approach, the application is designed as interconnected components. The high-level design space provided to the application developer is based on the same architectural concepts used at RTOS level. Indeed, we use the Think component model in a homogeneous way at these two abstraction levels (application and OS). As an illustration, the architecture of the application presented above is sketched out in Fig. 6. It shows a set of functional and resource components that require services provided by the operating system configuration in Fig. 4. Each application task given in Fig. 5 is represented by a composition between a Task resource component and a functional component which implements the task's entry point (via the runner interface). Resource components are instances of already existing components found in previously built components library; developers simply configure their attributes according to desired behavior (e.g. the priority for the tasks, the timeout for the semaphore, etc). The bindings between resource or functional components and the RTOS are generated automatically by our framework from interface signatures. Bottom line, we provide the application developer a higher-level design procedure, compared to commonly used plain C language mechanisms. Besides, the operating system resources used by the application are reified as basic components. First, this feature offers a clear view, at architectural level, of the resources used by the system, and it reifies via bindings how they are shared by the functional components. Second, it makes easier their configuration since each instance exports its configuration attributes at the architectural level, simply accessible by the developer.

Flexibility at Design Time. Within the original implementation of µC/OS-II , compilation options allow to configure essential properties of the RTOS and to scale down the final executive using precompilation directives. Within our approach, these configuration capabilities are managed at architectural level:

-The configuration of the RTOS' essential properties is addressed using components configuration attributes. These attributes are defined at architectural level, as for instance the OS TICKS PER SEC attribute defined for ATime-Component definition given in Fig. 2. Moreover, we implemented a simple tool which returns, from a given architecture description, the whole set of component attributes configurable by the developer. -The capability to scale down the final executive is addressed using the RTOS components stored in the library provided to the developer. For a given primitive component, several ADL definitions are stored in the library, differing by the number of interfaces -and thus the kind of services -they provide.

A set of RTOS composite component definitions are then built, exporting their public interfaces according to the interfaces provided by different combinations of subcomponents 10 .

Finally, the RTOS componentization does not restrict the configuration capabilities supported by the original µC/OS-II implementation. Moreover, we can emphasize a feature arising from our approach. Since the application components export the services that they require from the RTOS, it is possible to automatically retrieve from the component library the corresponding composite definition which fits strictly the needs of the application. This feature is wellsuited to address the constraints of resource-limited platforms, and represents a significant benefit of our approach compared to the manual configuration of original µC constants.

Flexibility at Runtime. As it has been presented in Section 2.2, the Think compiler generates meta-data that describes the Fractal component model architectural concepts at the C source-code level and consequently in final binary file. This meta-data provides the necessary infrastructure to enable flexibility from inside components. The standard Fractal API [START_REF] Bruneton | The Fractal Component Model[END_REF] that enables introspection and reconfiguration from outside components can be generated over these meta-data. Note however that Think only injects these control interfaces (and their respective implementations) only where it has been specifically specified, none being injected by default.

As run-time flexibility may not be necessary for all system components, the Think framework provides mechanisms to specify whether a single component or a subset of system components is not likely to evolve at execution time. Using flexibility-oriented properties the architect can instruct the Think compiler whether to generate the meta-data that make these components flexible. This feature allows to apply flexibility only where needed, and the way it is effectively needed, producing substantial reductions in memory footprint size and execution times, as it is presented in the following quantitative evaluation.

Quantitative Evaluation

As it has been described in Section 4.2, the componentization process led us to a reengineering of the µC's internal structure. Besides, we propose to reify the kernel resource instances as components, introducing a level of indirection between the functional and the operating system components. Finally, the tools provided by the Think framework allow to introduce several level of flexibility at runtime. In the following sections, we measure how this impacts the resulting executable in term of memory footprint and execution time. The evaluation is based on the RTOS and the application example presented respectively in Fig. 4 and Fig. 6. 10 The Think ADL supports inheritance relationships between architectural definitions which facilitates that procedure.

Memory Footprint. The Fig. 7 presents the memory footprints for a monolithic implementation used as a reference, compared to its component-based design 11 . We measure the overhead in code (i.e. .text section) and data, including initialized (i.e. .data section) and uninitialized (i.e. .bss section) data. We make this distinction as code is usually placed in ROM, whereas data are generally placed in RAM. For the component-based design, we propose three different configuration scenarios for the RTOS and the application presented in the preceding sections: the highly flexible, where components' meta-data allowing run-time flexibility are conserved at execution time, the not flexible scenario for which a completely static system is generated, and the partially flexible, for which only two functional components (Task3FunctionalCode and SharedData given in Fig. 2) are made flexible.

The systems generated in these scenarios do not include the non-functional Fractal interfaces that allow components to export Fractal's introspection and reconfiguration capabilities. This means that flexibility can only be exploited from inside components. In many cases, this basic flexibility level is enough to modify attributes or outgoing bindings according to internal component events.

Reference

Component-Based Design ( 4, and (2) for the complete system from Fig. 6.

From these results, we highlight the significative overhead implied by the highly flexible configuration (Fig. 7 (1)b and (2)b). This reflects the widespread use of interfaces and attributes within the component-based design that lead to the generation of the meta-data that enable flexibility, and confirms that optimization is an important issue. The not flexible configuration shows that such optimizations are feasible and they actually lead to an expected close to null overhead 12 (Fig. 7 (1)c). These results hence demonstrate the capability of the Think approach to benefit from CBSE at design time, without having to pay any overhead if no flexibility is required. The partially flexible configuration's overheads (Fig. 7 (2)d) show how runtime flexibility could be configured for only a dedicated subset of components at a reasonable cost.

The Fig. 8 shows the memory footprint overheads for the highly flexible and partially flexible scenarios when Fractal introspection and reconfiguration APIs implementations are injected into the systems. The highly flexible scenario (Fig. 8 (3)b and (4)b) shows the significative overheads resulting in both Code and Data sections. This is explained by the meta-data required to control the many bindings introduced by the encapsulation of the whole system into small components. Again, the partially flexible scenario (Fig. 8 (4)c) shows that this overhead can be considerably reduced if these control interfaces are only injected where actually desired, as permitted by the Think compiler.

for the RTOS level from Fig. 4, and (4) for the complete system from Fig. 6.

Measures at RunTime. Considering the performance, the Fig. 9 presents the comparison between the monolithic and the component-based design which has been conducted considering the execution path given in Fig. 5. It traverses more than ten components of the architecture, from the application level as well as the RTOS level (since semaphore and mailbox services provided by the RTOS are involved), and includes a context switch between Task1 and Task2 implemented by the hardware-dependent component. The testing environment consists of a Pentium 4 monoprocessor at 2.0 GHz. The scenario was simulated under a Linux 2.6 kernel (using a Linux port of µC) patched by Rt-Preempt. The latter converts the kernel into a fully preemptible one with high resolution clock support, allowing precise performance measures. The results show that even for the highly-flexible configuration, the impact on performance is small, and becomes negligible when considering the optimized configuration. The figure also shows that the maximal amount of memory which is dynamically allocated at runtime remains unchanged within our component-based design compared to the monolithic one.

Related Work

Several approaches have been proposed to satisfy actual needs of fast development cycles and dynamic adaptation to changing work contexts. In the very resource-constrained domain of wireless sensor networks, Virtual Machines (VM) or similar approaches such as Maté [START_REF] Levis | Maté: A Tiny Virtual Machine for Sensor Networks[END_REF], Tapper [START_REF] Xie | Tapper: a Lightweight Scripting Engine for Highly Constrained Wireless Sensor Nodes[END_REF] and DAViM [START_REF] Michiels | DAViM: a Dynamically Adaptable Virtual Machine for Sensor Networks[END_REF] provide support for run-time flexibility and low energy consumption at communication tasks. VM's implementations are strongly bound to the application hence hardly scalable to more general real-time embedded systems. DAViM provides support for more complex dynamic reconfiguration by adding or removing operation libraries and so modify a running VM.

Applying modularity benefits into OS executives development process, OS-Kit [START_REF] Ford | The Flux OSKit A Substrate for Kernel and Language Research[END_REF] and eCos [START_REF] Massa | Embedded Software Development with eCos[END_REF] provide a set of operating system components that can be used as building blocks to configure an operating system. Component definition and binding languages such as Knit [START_REF] Reid | Knit: Component composition for systems software[END_REF] can be used to assist the assemblage of components. While producing efficient applications, these frameworks do not support dynamic reconfiguration and flexibility control. OSKit is also more oriented to non-embedded hardware platforms.

Following a CBSE approach, TinyOS [START_REF] Levis | TinyOS: An Operating System for Sensor Networks[END_REF] and Koala [START_REF] Van Ommering | The Koala Component Model for Consumer Electronics Software[END_REF] define component models and allow to build a whole system, i.e. an application bound to a particular executive, compiling component architectures.

TinyOS is a component-based operating system and programming framework focused to motes in sensor networks domain. It reduces the penalty of finegrained components by imposing a component-programming language, nesC [START_REF] Gay | The nesC Language: A Holistic Approach to Networked Embedded Systems[END_REF], a dialect of C that facilitates functional code analysis and inlining. The use of this language introduces some significant limitations: besides making difficult the use of legacy code, a TinyOS application must be statically declared, as dynamic memory allocation is not supported. Dynamic reconfiguration at applicative and executive level is hence not supported, although.

Koala is a component-based development framework and a component model oriented to consumer electronic (CE) devices. The component paradigm is exploited at design time, bindings and other model abstractions are translated to traditional C programming language structures and compiled. Consequently Koala-based systems do not suffer from components-related performance overheads, but lack dynamic reconfiguration support.

Robocop project [START_REF]Robocop ITEA Project. Robocop: Robust Open component-based software architecture for configurable devices project[END_REF] enriched Koala component model offering, among others, component discovery and instantiation services and dynamic bindings features achieving CE devices requirements. Resources consumption is exhibited by IResource interfaces and is considered constant per operation [START_REF] Muskens | Prediction of Run-Time Resource Consumption in Multi-task Component-Based Software Systems[END_REF]. An evaluation mechanism to measure static memory consumption had been developed for Koala [START_REF] Fioukov | Evaluation of static properties for component-based architectures[END_REF].

Robocop and Koala propose a similar approach to Think and Qinna, a QoS framework for Think [START_REF] Tournier | Qinna, an Component-Based QoS Architecture[END_REF][START_REF] Gonnord | Quantity of Resource Properties Expression and Runtime Assurance for Embedded Systems[END_REF]. It has been tested in many industrial experiments and accepted as an ISO standard under the name of M3W. However, we have not found enough information about how the component model is compiled, neither comparison with legacy code performance.

CAmkES [START_REF] Kuz | CAmkES: A Component Model for Secure Microkernel-based Embedded Systems[END_REF] is a general embedded-systems oriented component model. Component-based applications run on top on a L4 micro-kernel [START_REF] Liedtke | On Micro-Kernel Construction[END_REF] and a set of basic operating-system services provided by Iguana [START_REF] Heiser | Secure Embedded Systems need microkernels[END_REF]. Produced glue code is agressivily optimized from compile-time available information. If flexibility at run-time is required, extension layers can be added to the application. This approach is flexible as it allows to minimize memory size overhead in a basic application and to add additional functionnalities if required. Nevertheless, the extension layers strongly rely on services provided by L4 micro-kernel and Iguana, creating a tight dependence between the component model, the component-based application and the operating system.

Hartex [START_REF] Berthing | Component-Based Design of Safe Real-Time Kernels for Embedded Systems[END_REF] is a component-based framework dedicated to real-time kernels. The RTOS is designed as a composite component encapsulating the kernel primitives which are structured as interconnected sub-components. From a library of basic kernel components implemented from scratch, the framework allows to derive kernel configurations depending on the functionalities needed by the application. However, as far as we know, Hartex is not based on an ADL, providing a higher-level representation of the component dependencies and kernel configurations. It is unclear how composition is managed by their compilation process and the framework do not support dynamic reconfiguration as well.

Conclusions

Component-based Software Engineering has emerged as a technology for the rapid assembly of flexible software systems, where the main benefits are reuse and separation of concerns. However, applying CBSE in the context of embedded systems implies to master the flexibility cost in term of performance, since they rely on low-level operating system services and are deployed on resource-limited devices.

This paper brings the following contributions to tackle these issues. First, we propose a componentization from an existing and mature Real-Time Operating System, µC/OS-II, based on the Think component framework. From the RTOS resources reified as components, we present how component-based applications are designed on top of it. At design time, within our component-based approach, we fully address the configuration capabilities proposed by the original µC implementation. Furthermore, we can highlight an improvement arising from our approach, which fulfill a constraint imposed by resource-limited platforms: from the application architecture which express its dependencies towards the RTOS services, we can retrieve automatically from the component library the operating system component which fits stricly the needs of that application.

Second, the Think component framework allows to introduce runtime flexibility, for RTOS components, as well as for application components, since we use its component model in a homogeneous way at these two abstraction levels. From a quantitative evaluation, and based on the Think features allowing to apply flexibility only when desired, we show that overheads involved by our component-based design in term of performance are reasonables, and negligeables when considering a completely static version of the executable.

Relevant future work concerns improving configurability features of the RTOS at design time. Firstly, we are investigating a predicate-based ADL support within the Think framework to provide a precompilation feature at architectural level. Secondly, the extensibility capabilities of our component-based design could be improved by exporting basic data type definitions used by the RTOS (such as task control block, event control block ) at architectural level.

Fig. 1 .

 1 Fig. 1. µC Modules.

Fig. 2 .

 2 Fig. 2. Definition of a primitive component: ADL (left part) and IDL (right part).

Fig. 4 .

 4 Fig. 4. Architecture's Example of a µC RTOS.

Fig. 6 .

 6 Fig. 6. A componentized example.

  6 .

		Non-functional interfaces					Configuration attributes
			CI	LCC		<<primitive>>
			uCOS.time.lib.ATimeComponent
		Provided	clock	1		2	irqSafe	Required
		Functional interfaces	delay		3	schedcore	Functional interfaces
	component uCOS.time.lib.ATimeComponent {		1 Interface clock
					public interface uCOS.time.api.ClockCommon
		// Public interfaces provided provides uCOS.time.api.ClockCommon as clock	INT32U OSTimeGet (void);
		provides uCOS.time.api.DelayCommon as delay	void OSTimeSet (INT32U ticks);
					2 Interface irqSafe
		// Internal interfaces required requires uCOS.task.api.SchedCoreInt			internal interface irq.api.IrqSafe
		as schedcore			void OS ENTER CRITICAL (void);
		requires irq.api.IrqSafe as irqsafe // Attributes definition attribute INT16U OS_TICKS_PER_SEC = 100		void OS EXIT CRITICAL (void); 3 Interface schedcore
					internal interface uCOS.task.api.SchedCoreInt
	}	content uCOS.time.lib.os_time			void OS Sched (void);

  Fig. 8. Memory footprint sizes (in Bytes) and overheads, with the Fractal APIs,

				Reference	Component-Based Design
				(a)	(b)	(c)
					highly flexible	partially flexible
					with Fractal APIs with Fractal APIs
	(3)	RTOS	Code Data	13508 14072	+32.2 % +16.8 %	--
	(4)	Complete Code System Data	14003 20252	+47.8 % +20.9 %	+4.1 % +1.1 %

Federal Aviation Administration.

In this paper, we refer to the version 2.86 of µC/OS.

By convention, the functional interfaces are graphically placed on the left and right sides of the component, the non-functional interfaces on the top side.

See http://think.objectweb.org/

The Mbox, Queue, Sem and Mutex modules are gathered under the IPC appellation (for Inter-Process Communication).

For example, the Core module makes 28 function calls to the Task module, and sums a total of 36 calls with all the modules. The result is a coupling metric of 0.77.

These experiments have been conducted using GCC with the -Os option that optimizes the binary image size.

[START_REF] Gonnord | Quantity of Resource Properties Expression and Runtime Assurance for Embedded Systems[END_REF] The light overhead observed in Code section (Fig.7(2)c) corresponds to the encapsulation of the resource components presented in Sec.5.2, overhead that may be eliminated in a near release of the Think compiler.

Acknowledgment

This work was supported by the french Minalogic Mind project.