Patrick Bas

François Cayre

Natural Watermarking: a secure spread spectrum technique for WOA

This paper presents a spread spectrum (SS) watermarking technique that is secure against carriers estimation in a Watermark Only Attack framework. After reviewing the sufficient conditions to design secure algorithms for watermarking and steganography, we present a setup based on Blind Source Separation (BSS) theory to assess the lack of security of classical SS techniques such as classical SS or ISS. We motivate a new SS watermarking algorithm called Natural Watermarking (NW) where the estimation of the secret carriers is impossible and which achieves perfect secrecy thanks to unchanged Gaussian distributions of the secret carriers. The theoretical evaluation of the NW security is carried out and the case of multi-bit embedding is addressed. Finally, a robust extension of NW is presented and the properties of NW and Robust-NW are both practically verified.

Introduction

Robustness, capacity and imperceptibility have always been considered, since the very beginning of watermarking, as the main three constraints to respect in order to build a valuable watermarking scheme. Recently the watermarking community has thrown light on the problem of security which appears also to be a fundamental constraint to respect in order to guaranty the usability of a watermarking technology. Several authors [START_REF] Cayre | Watermarking security part I: Theory[END_REF][2] [START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF] showed that some information about the secret key may leak from several observations of watermarked pieces of content. Using this information, it may be possible to estimate the secret key, and then to destroy the security of the considered scheme by removing, copying or altering the embedded messages. Several studies address also the security of practical watermarking techniques for digital images [START_REF] Bas | Security of dm quantization watermarking scheme: a practical study for digital images[END_REF] [START_REF] Cayre | Watermarking security part II: Practice[END_REF].

In this paper, we tackle the problem of security for the well-known class of spread spectrum (SS) watermarking schemes. In this case, the secret key which practically is the seed of a random generator, corresponds to the set of secret carriers that is used to convey the information. It is important to note that an attacker does not need the seed used to initialiaze the random number generator: the secret carriers are good enough to attack the watermark. We propose a watermarking scheme that is secure (e.g. it does not offer information leakage of the secret key) for the class of Watermark Only Attacks (WOA). This class of attacks, proposed by [START_REF] Cayre | Watermarking security part I: Theory[END_REF], considers an attack that is based on the observation of watermarked contents, watermarked with the same key but conveying different messages. We named the proposed scheme natural spread spectrum watermarking because embedding is achieved without altering the natural distribution of each secret carrier before and after embedding. As shown in the paper, this characteristic enables to achieve perfect secrecy. Moreover, when embedding several bits, we show that if each carrier is embedded in the contents with an amplitude following a Gaussian distribution, it is impossible to individually estimate the carriers.

The rest of the paper is divided into five sections. First, the security of classical SS techniques for WOA are analysed as a Blind Source Separation (BSS) problem: in section 2 we show that the characterisation of the distributions of each carrier for the observed contents enables to estimate the different carriers. Section 3 presents the constraints, principles and characteristics of Natural Watermarking (NW). The embedding, decoding and distortion related to NW are presented and the link with the Scalar Costa's Scheme, another scheme preserving perfect secrecy, is outlined. An extension of NW to increase the robustness is presented in section 4, the implications in term of security are also mentioned. Section 5 presents a comparison between the estimations of the secret carriers for different SS watermarking schemes including NW. We show that for NW it is impossible to estimate the carriers. For Robust-NW only the estimation of the watermark subspace is possible. Finally section 6 concludes this paper and presents open research lines for future works.

2 Assessing the security of spread-spectrum techniques using BSS techniques

Notations

Vectors are denoted in bold face (v) and coefficients of vectors with parenthesis (v(i) is the coefficient number i in vector v). Matrices are denoted in capital bold face and are generally composed of several realizations of vectors of the same name, column-wise: the columns of V are several realizations v 1 . . . v N of a "template" vector v.

Let us denote x the host vector of N v coefficients into which we want to hide a binary message vector m of N c bits. The resulting watermarked vector is denoted y. To this aim, we use u i orthogonal carriers, 1 ≤ i ≤ N c . The decoded message is denoted m. It is to be estimated from y ′ , a potentially degraded version of y. Let us further denote z v,ui the correlation between a vector v and a carrier u i :

z v,ui =< v|u i >= 1 N v Nv k=1 v(k)u i (k) (1)

Information theoretical constraints for perfect secrecy

Perfect secrecy has different meanings according to the domain of application. For steganography, perfect secrecy means the impossibility to distinguish between an original content (x) and a stego content (y). Cachin studied the necessary conditions to obtain a secure steganographic scheme and claims that a scheme is secure if the Kullback-Leibler divergence D KL between the distributions P x and P y of x and y is null. The quantity D KL is defined by:

D KL (P x ||P y ) = i P x (i) log P x (i) P y (i) (2)
which means that perfect secrecy may be achieved if and only if the distributions of x and y are identical. A practical implementation of a steganographic scheme satisfying the perfect secrecy constraint has been proposed in [START_REF] Sallee | Model-based steganography[END_REF]. For robust watermarking, the problem does not concern a possible distinction between the original and the watermarked content: it is not important to know wether a content is watermarked or not, but is it important not to disclose the secret carriers based on observations of pieces of watermarked contents. The concept of information leakage in the context of robust watermarking has been proposed in [START_REF] Cayre | Watermarking security part I: Theory[END_REF] and developed in [START_REF] Comesaña | Fundamentals of data hiding security and their application to spread-spectrum analysis[END_REF] [START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF]. The notion of information leakage stems from the definition of the mutual information between N o watermarked contents Y and the secret carriers U (where the u i are the columns of U and the N o observed y are the columns of Y):

I(U, Y) = H(Y) -H(Y|U) = H(U) -H(U|Y) (3)
then a watermarking scheme is secure if the mutual information between U and Y is null: in this case there is no information leakage.

Spread spectrum carriers estimation

As mentioned previously, a SS watermarking scheme is secure if it is impossible to estimate the secret carriers using observed signals. On the contrary, if a given technique enables to estimate the secret carriers u i based only on the observations of y, then the security of the watermarking scheme is greatly reduced. Such a tool can be provided using BSS theory. The goal of BSS is to decompose the observations as a mixture of signals having special statistical properties.

For example, a Principal Component Analysis decomposes observations into orthogonal components according to their variances, and an Independent Component Analysis decomposes the observations into independent signals. Making connections between BSS and SS watermarking is straightforward. A noteworthy property of the class of spread spectrum watermarking schemes is the fact that the embedding part of a SS scheme can be formulated exactly as a blind source separation problem:

Y = X + US m . (4)
In this equation, the matrix U is an N v × N c matrix called the mixing matrix (in a BSS framework) and which represents in our case the different carriers u i column-wise. The matrix S m denotes the different sources that have to be extracted and represents the modulation signal for each carrier that is a function of the embedded message m. The matrix X represents the host signals (columnwise) and shall be considered as noise in a BSS framework. The goal of BSS is to estimate the matrices U (the secret carriers) and S m according to the observation matrix Y.

In the case of WOA, this decomposition is possible thanks to the fact that each message is embedded independently from another one. It is consequently possible to use Independent Component Analysis techniques to break the security of many spread spectrum watermarking schemes.

The principle of ICA techniques is to find directions in the observed data space whose projections give singular distributions [START_REF] Hyvärinen | Independent Component Analysis[END_REF]. Based on the fact that the sum of independent variables tends to a Gaussian law, independent components are defined as the most "non-gaussian" components. Moreover, if the watermark components have a different variance than the host data, principal component analysis can be used to perform a reduction of dimension that makes the search of independent components easier.

We now focus on the estimation process of the secret carriers for two popular SS schemes (classical SS and ISS). The ability to estimate their secret carriers is presented.

Classical Spread Spectrum watermarking: In the case of classical SS, the embedding is given for each vector by:

y = x + Nc i=1 b(i)u i (5)
where b ∈ {-1; +1} Nc is the BPSK modulation of the embedded message m.

Improved Spread Spectrum watermarking (ISS): ISS was proposed in [START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF], it can be considered an informed-embedding variation of classical SS. The embedding is given in this case by:

y = x + Nc i=1 (αb(i) -λ z x,ui ||u i || )u i (6)
where α and λ are respectively calculated to respect the targeted distortion and to achieve the most little error probability after addition of white Gaussian noise. Eq. 5 and Eq. 6 can be easily transposed in the multidimensional case to obtain a formulation similar to Eq. 4: the matrix U still contains the carriers and the matrix S m contains the modulation signals for each carrier.

To assess the security of a SS-based technique, we have decided to adopt the following methodology which is generally used in BSS benchmarks:

1. We generate N o observations of watermarked contents and generate the matrix of observations Y. 2. We whiten the observed signals using principal component analysis. To reduce the searching time, a reduction of dimension is therefore performed. If we consider that the host signal is generated from an i.i.d. process, the subspace containing the watermark generated by N c carriers will be included into a N c -dimensional space of different variance [START_REF] Doërr | Danger of low-dimensional watermarking subspaces[END_REF]. We consequently select the subspace generated by eigenvectors presenting singular (lower or higher) eigenvalues. 3. We run the FastICA algorithm [START_REF] Hyvärinen | Fast and robust fixed-point algorithms for independent component analysis[END_REF] on this subspace to estimate the independent components and the independent basis vectors (e.g. the secret carriers). 4. We compute the normalized correlation c between each original and estimated carriers. A value of c close to 1 means that the estimation of the component is accurate. An estimation close to 0 means that the estimation is erroneous. If N c = 2, we evaluate the estimation accuracy by plotting a 2D constellation of points of coordinates (c 1 ; c 2 ). A successful estimation will then provide a point close to one of the four cardinal points (0, 1), (0, -1), (1, 0), (-1, 0)3 .

- We have depicted the empirical joint distributions of two carriers in the observed watermarked signals (see Fig. 2) and applied our estimation setup for N c = 2 secret carriers (see Fig. 3). In both cases the host vectors are Gaussian i.i.d. signals of law N (0, 1) and two carriers where used during the embedding. The Watermark to Content Ratio (WCR) was fixed in both case to -21dB. For each SS scheme, the joint distribution of the carriers in the observed content is the sum of four bi-dimensional Gaussian distributions. Note that the variance of each distribution is less important for ISS embedding than for SS because of the embedding optimization performed by ISS. Note also that the global variance of the distribution for SS is more important than for ISS. For each distribution, the directions of the two carriers (horizontal and vertical axis) are easily identifiable by the ICA algorithm.

Additionally we see that the Cachin criterion which considers the distributions of original and watermarked contents is not fulfilled for this two schemes. Fig. 1 depicts the distribution of the two same carriers for original contents. This distribution is rather different than the distributions after SS watermarking. Fig. 3 depicts the normalized correlation between the original and estimated carriers for 100 trials considering every 1000 watermarked vectors. We can notice that the estimations are globally more accurate for SS than for ISS. In this case, this is mainly due to the fact that the variance of the embedding for ISS is lower than for SS and consequently the estimation of the subspace relative to the watermark is less accurate in the second case.

Natural Spread Spectrum Watermarking

In this section, we show how to build a SS-based watermarking scheme in such a way that the identification of the watermarking subspace spanned by the secret carriers is impossible.

Embedding and decoding

If we consider a carrier u i such that its coefficients follows a Gaussian model (u i ∼ N (0, σ 2 ui )), and host signals x ∼ N (0, σ 2 x ) then the random variable z x,ui follows a Gaussian law of parameters z x,ui ∼ N (0, σ 2 ui σ 2 x ). Note that this property is true because of the Central limit theorem as far as N v is important. Moreover, this property is still valid if x does not follow a Gaussian model. The goal of NW is to design the embedding in such a way that the distribution of z x,ui before and after embedding will remain identical. Moreover, as it is shown at the end of this section, the fact that each carrier follows a Gaussian distribution prevents the estimation of the different carriers and guarantees the security of the scheme.

The decoding rule remains the same than for usual SS schemes:

m(i) = 1 if z y ′ ,ui > 0 (7) m(i) = 0 if z y ′ ,ui < 0 (8)
The watermarked vector y is:

y = x + w (9)
where the watermark signal w is computed as follows:

w = - Nc i=1 1 + (-1) m(i) sign(z x,ui ) z x,ui u i 2 u i (10)
which means that the watermark w i associated to each carrier u i follows this simple embedding rule:

w i = 0 if m(i) = 1 ; z x,ui > 0 ( 11
)
or m(i) = -1 ; z x,ui < 0 ( 12)

w i = -2 z x,ui u i 2 u i if m(i) = 1 ; z x,ui < 0 (13) or m(i) = -1 ; z x,ui > 0 (14)
Eq. 10 states that x is symetrically modified iff sign(z x,ui ) = (-1) m(i) . This embedding rule is depicted on Fig. 4. Note that the embedding rule used for NW is quite similar to the rule used for ISS. In both cases, each carrier u i is modulated according to the correlation z x,ui . For ISS, z x,ui is used to increase the distance between the different codewords and increase the robustness. For NW, z x,ui is used to not modify the natural distribution of the carriers and consequently to increase the security.

zx,u 0 Pz x,u zx,u 0 zx,u 1 z w x,u 2 = zy,w 2 zx,u 2

Distortion

Distortion is usually expressed by means of the WCR (Watermark to Content Ratio), in dB. Under the assumption that, on average, one bit out of two calls for a symmetry, we are able to compute the MSE.

The pdf of the watermark (on each sample) is the following:

if x < 0 f (x) ∼ N (0, 4σ 2 x σ 2 u /N v ) (15) if x ≥ 0 f (x) = δ(x)/2 (16)
Then:

σ 2 W = 2σ 2 x σ 2 u N v (17)
and the Watermark-to-Content-Ratio is expressed as follows:

W CR = 10 log σ 2 W /σ 2 x = 10 log 2σ 2 u N v (18)
We shall stay with this last approximation, since Fig. 5 shows no difference between this theoretical approximation and the practical measurements. If targeting a classical W CR = -20dB, Eq. 18 leads to the trivial relation N v = 200N c if we set u ∼ N (0, 1) and x ∼ N (0, 1).

Theoretical evaluation of the security of Natural Watermarking

The goal of this section is to show that NW enables to have no information leakage in the case of a WOA setup. We first compute the mutual information for a scheme using only one carrier u (N c = 1: therefore the message m is a scalar binary value).

We consider the case z x,u > 0 but the equations are similar if z x,u < 0. The embedding formula can be expressed as:

If m = 1 then y = x (19) If m = 0 then y = x -2 uu ⊤ N v x. ( 20
)
By construction, y can also be modelled as an i.i.d. Gaussian process: y ∼ N (0, 1). Then:

H(y) = H(x) = N v 2 log(2πe). (21)
We recall that the mutual information between one observation y and a secret carrier u is given by:

I(y; u) = H(y) -H(y|u). (22)
Because the pdfs f y|u,m=1 (x) and f y|u,m=0 (x) are disjoint, and supposing that Pr[m = 1] = Pr[m = 0] = 1/2, the conditional H(y|u) is given by:

H(y|u) = 1 2 (H(y|u, m = 1) + H(y|u, m = 0)) + log(2). (23)
Using Eq.19, Eq.20 and the definition of differential entropy, it is easy to show that H(y|u, m = 1) = H(x)log 2 and

H(y|u, m = 0) = H(x -2uu ⊤ x/N v ) - log 2.
We obtain then the following expression of conditional entropy for NW:

H(y|u) = 1 2 H(x) + 1 2 H(x -2 uu ⊤ N v x) (24)
where

H(x -2 uu ⊤ N v x) = H((I -2 uu ⊤ N v )x) = H(x) + ln | det(I -2 uu ⊤ N v )|. (25)
Because ||u|| 2 = N v , the matrix I -2uu ⊤ /N v is an elementary reflection which corresponds to an orthogonal matrix:

(I -2 uu ⊤ N v )(I -2 uu ⊤ N v ) ⊤ = I -4 uu ⊤ N 2 v + 4 uu ⊤ uu ⊤ N 4 v = I since u ⊤ u/N 2 v =1. Consequently | det(I -2uu ⊤ /N v )| = 1
and we obtain:

H(y|u, m = -1) = H(x) (26)
and:

I(y; u) = H(y) -H(x) = H(x) -H(x) = 0. (27)
If we now consider N o observations, and because x 1 , ..., x No are independent random vectors, then due to Eq.19 and Eq.20, y 1 , ..., y No and y 1 |u, ..., y N0 |u are also independent vectors. Consequently we have the following properties:

H(y No |y No-1 , ..., y 1 ) = H(y) (28)
H(y 1 , .., y No ) = N o H(y) = N o H(x) (29)
H(y 1 , .., y No |u) = N o H(y|u) = N o H(x) (30)
and finally using Eq. 29 and Eq. 30:

I(Y; U) = N o H(X) -N o H(X) = 0 (31)
Note that having a mutual information between the secret key and the observed content being null has already been found for another watermarking scheme. In [START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF], authors show that for the Scalar Costa's Scheme [START_REF] Eggers | Scalar costa scheme for information embedding[END_REF] and an embedding parameter α = 1 2 , there is no information leakage too. Such a similar result is not surprising because in both cases, the distributions of x and y are the same.

Note also that natural watermarking also theoretically satisfies to the steganographic definition of security recalled in section 2.2. Because the distributions of x and y are the same, D KL (P x ||P y ) = 0.

Multi-bits embedding

When N c > 1 carriers are used, the security of the scheme can be seen as a problem of blind source separation: is it possible to separate a mixture of independent Gaussian variables with equal variance ?

ICA theory claims that it is impossible to perform such a separation because the joint distribution of such a mixture is rotationally symmetric [START_REF] Hyvärinen | Independent Component Analysis[END_REF]. Here, it is not possible for an BSS technique to find singular directions observing NWwatermarked vectors as it was possible with classical SS or ISS.

Toward robust natural watermarking

One solution to increase the robustness of the NW scheme is to increase the variance of the Gaussian distribution associated with each carrier. We can modify the embedding rule of NW (cf. Eq. 10) in such a way that the distribution of each carriers will still remain Gaussian, but will have a standard deviation proportional to a scale factor s. This modification enables to increase the average distance between codewords coding different symbols but also to increase the embedding distortion. The new modulation for Robust-NW is then given by:

w = - Nc i=1 1 + s(-1) m(i) sign(z x,ui ) z x,ui u i 2 u i (32)
and the distribution of the correlation z x,ui of one carrier u i now follows the model z x,ui ∼ N (0, s 2 σ 2 ui σ 2 x ). If s = 1, the embedding rule corresponds to NW, if s > 1, the robustness is increased and this leads to Robust-NW. The expression of the W CR becomes:

W CR = 10 log (s 2 + 1)σ 2 u N v (33)
Using Robust-NW leads also to another important consequence. Because distributions of carriers are now distinct from distributions of other components of watermarked contents, it is then possible to estimate the subspace related to the watermark using, for example, principal component analysis (PCA). But, if N c > 1, it is still not possible to estimate each carrier separately. Consequently the attacker can remove the watermark by zeroing all the projections on every carriers but still he has no access to the hidden message itself: he cannot copy it to another content or modify the embedded message because he does not know the values of z x,ui . Consequently the very security of the system is still preserved 4 .

As a remark, we have also to point out that, even if this implementation enables to obtain robustness on one hand, on the other hand the degradation of the host signal become rather significant. For example, if σ 2 n = σ 2 x = 1 (which is equivalent to a N DR = 1 for ISS) and N v = 512, for a same BER = 12% for both schemes, then the distortion is far more important for NW than for ISS (W CR = -15dB for NW and W CR = -21dB for ISS). For comparison, in the case of NW with W CR = -21dB, we have BER = 25%.

Results

The aim of this section is to assess the theoretical properties of NW and Robust-NW. We have used the estimation setup proposed in section 2.3 for classical SS and ISS considering the same parameters (N c = 2, N o = 1000). The distortion for NW remains the same (W CR = -21dB) but is different for Robust-NW (W CR = -14dB, s = 3). Normalized correlations between the two estimated and original carriers are depicted on Fig. 7 for 100 different trials. For NW (left plot), the estimation of the secret carriers is unsuccessful because every point is very close to the origin for each trial. The right plot, obtained for Robust-NW, illustrates the fact that in this case the watermark subspace is estimated (the distance between each point and the origin is close to 1), but that the estimation of the two carriers is not possible because each trial leads to a point which is randomly chosen on the unitary circle.

Conclusions and future works

This paper has presented a solution to obtain a secure spread spectrum watermarking scheme called Natural Spread Spectrum Watermarking for WOA. The security is guaranteed by two important properties:

-The distribution of each secret carrier is the same for the marked and original contents. From this property stems the fact that the mutual information between the secret carrier and the observed contents is null (condition of perfect secrecy for watermarking). Additionally, the embedding satisfies also the condition of secrecy for steganography. Note however that this first property is not true for Robust-NW (s > 1).

-The watermark subspace is equivalent to a mixture of Gaussian components having the same variance. BSS theory demonstrates that it is impossible to estimate each component (carrier) in this particular case.

We have also proposed a extension of NW to increase the robustness called Robust-NW which increases the variance of distributions of each carrier while preserving a multivariate Gaussian distribution. However, the compromises done to obtain a secure watermarking scheme have to balanced with the relative weak robustness of NW in comparison with SS or ISS. Our future works will concentrate on this point to discover if such a compromise is mandatory or if it is possible to obtain a more robust extension of NW. Anyway, Natural Watermarking should already be considered a secure alternative for fragile watermarking applications.

We would like also to propose a practical implementation of NW for real-life contents such as images or sounds. This will enable to evaluate specifically the perceptual distortion of the proposed system.

Fig. 1 .

 1 Fig. 1. Joint distributions of two carriers for original contents. No = 10000, Nv = 512, σ 2 x = 1.

Fig. 2 .

 2 Fig. 2. Joint distributions of two carriers for SS and ISS schemes. For both schemes No = 10000, W CR = -21dB and Nv = 512, σ 2 x = 1.

Fig. 3 .

 3 Fig. 3. Normalized correlations between the two estimated carriers and the real ones. For both schemes No = 1000, W CR = -21dB and Nv = 512.

Fig. 4 .

 4 Fig. 4. Natural watermarking for m = {1, 1, 1} (Nc = 3). Only the third bit calls for a model-based symmetry.

= 1 Nc = 3 Nc = 5 Fig. 5 .

 1355 Fig. 5. Comparison between theoretical and practical W CR.

  Fig 6 illustrates the joint distribution of two original carriers obtained after Natural Watermarking. The distribution cannot be used to find the direction of the carriers.

Fig. 6 .

 6 Fig. 6. Joint distributions of two carriers for NW. No = 10000, W CR = -21dB, Nv = 512, σ 2x = 1. The direction of the original carriers (horizontal and vertical axis) can not be estimated on a multivariate Gaussian distribution.

1Fig. 7 .

 7 Fig. 7. Normalized correlations between the two estimated carriers and the original ones. For both schemes: No = 1000 and Nv = 512.

We use Nc = 2 for illustration purposes, hiding more bits would require to use the Hungarian method[START_REF] Kuhn | The Hungarian method of solving the assignment problem[END_REF] to assign original and estimated carriers prior to the computation of the normalized correlation c.

One may argue that the whole private subspace is already an important information about the secret. We would like to emphasise however that Robust-NW is proved to deliver better security since it explicitly does not allow for estimation of the carriers.

Acknowledgements

The work described in this paper has been supported (in part) by the European Commission through the IST Programme under Contract IST-2002-507932 ECRYPT and the National French projects ACI-SI Fabriano and RIAM Estivale.


Patrick Bas
email: patrick.bas@hut.fi

Franc ¸ois Cayre

Achieving Subspace or Key Security for WOA using Natural or Circular Watermarking

Keywords: K.4.4 [Computers and society]: Electronic CommerceSecurity Security, Algorithms, Theory Watermarking, key-security, subspace-security, natural watermarking, circular watermarking, WOA

This paper presents two watermarking schemes that are secure when considering the Watermarked content Only Attack (WOA) framework. The definition of watermark security is first recalled and the distinction between key-security and subspace-security classes for Spread Spectrum (SS) watermarking schemes is presented afterwards. Blind source separation techniques are also recalled as a tool to assess the security of a SS watermarking scheme and prove that classical SS and Improved SS are not secure within the WOA framework. To further illustrate these security issues, we next build on a new watermarking scheme called Natural Watermarking (NW). We prove it to be subspace-secure under specific hypotheses. Natural watermarking does not change the Gaussian natural distributions of the projection of each carriers. Furthermore NW prevents estimations both of the watermark subspace (subspace-security) and the different carriers (key-security). We then extend the nice properties of NW to derive the more general family of Circular Watermarking schemes which are key-secure and may offer a better robustness to AWGN attack than NW. An implementation of CW based on ISS is next proposed and comparison of bit error rates for NW, CW, SS and ISS finally draws some conclusions on the robustness cost to achieve security.

INTRODUCTION

Beside robustness, imperceptibility and capacity, the somewhat new constraint of security shall be considered as one important requirement for watermarking schemes. The notions of security and robustness are close but still very different in essence. They can be better understood when considering the attacker point of view. We would like to emphasize on the accurate definitions proposed in [START_REF] Comesaña | Fundamentals of data hiding security and their application to spread-spectrum analysis[END_REF]:

• "attacks to robustness are those whose target is to increase the probability of error of the data-hiding channel."

• "attacks to security are those aimed at gaining knowledge about the secrets of the system (e.g. the embedding and/or the detection keys)."

This last definition is coherent with the definition proposed in [START_REF] Kalker | Considerations on watermarking security[END_REF]: "watermark security refers to the inability by unauthorised users to have access to the raw watermarking channel". It implies that it is not possible to either modify the embedded information or to copy it to another content if the watermarking scheme is secure. Performing an attack that estimates the secret key used for embedding and then copy the embedded message to another content using the estimated key is a threat on the security of a watermarking scheme. On the other hand, robustness is concerned by specific processes that prevent the detection of a watermark or alter randomly the embedded message. For example, noise addition or JPEG compression are processes that affect the robustness of a watermarking scheme: they may forbid the detection of the watermark or increase the bit error rate, possibly to a given level. Additionally, it is a common mistake to claim that a watermarking technique is secure because it relies on the use of a secret key during the message embedding process. When several contents are watermarked using the same secret key, it is important to guarantee that it does not exist a way to estimate this secret key. Exhaustive search is not the only solution to perform such an estimation. Several works [START_REF] Cayre | Watermarking security part I: Theory[END_REF][START_REF] Gwenaël | Danger of low-dimensional watermarking subspaces[END_REF][START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF][START_REF] Comesaña | Fundamentals of data hiding security and their application to spread-spectrum analysis[END_REF] recently showed how to disclose keys based on observations of watermarked contents. It gave rise to the notion of watermarking security levels: the number of observations required for improving the estimation of the secret by an order of magnitude. This paper deals with the two aspects presented above. Section 2 focusses on the security of Spread-Spectrum water-marking schemes and emphasizes on the difference between the notions of key-security and subspace-security. Section 3 and 4 present the principles of Natural Watermarking (NW) and Circular Watermarking (CW) that are respectively subspace-secure and key-secure. Implementations of NW and CW are also presented and the robustness of each scheme is compared with the robustness of classical SS and ISS.

SECURITY OF SPREAD SPECTRUM WATERMARKING SCHEMES

Notations

Vectors are denoted in bold face (v) and coefficients of vectors with parenthesis (v(i) is the coefficient number i in vector v). Matrices are denoted in capital bold face and are generally composed of several realizations of vectors of the same name, column-wise: the columns of V are several realizations v1 . . . vN of a "template" vector v.

Let us denote x the host vector of Nv coefficients into which we want to hide a binary message vector m of Nc bits. The resulting watermarked vector is denoted y. To this aim, we use ui orthogonal carriers, 1 ≤ i ≤ Nc. The decoded message is denoted m. It is to be estimated from y ′ , a potentially degraded version of y. Let us further denote zv,u i the correlation between a vector v and a carrier ui:

zv,u i =< v|ui >= 1 Nv Nv X k=1 v(k)ui(k) (1)
Moreover, we define the different matrices:

• Y is the matrix of observed watermarked signals. Its size is Nv No. Each column yi of Y represents one observed signal,

• X is the matrix of host signals. Its size is Nv No. Each column xi of X represents one host signal,

• U is the matrix of secret carriers. Its size is Nv Nc. Each column ui of U represents one secret carrier,

• S is the matrix of carriers modulation. Its size is Nc No. Each row si of S represents the modulation of the i th bit for each watermarked content.

Because all the schemes that are presented in this paper belong to the class of SS watermarking schemes, the decoding rule is given by:

m(i) = 1 if z y ′ ,u i > 0 (2) m(i) = 0 if z y ′ ,u i < 0 (3)

Security classes: subspace-secure, key-secure, insecure

In this paper, we shall emphasise on security classes: a watermarking scheme either belongs to the subspace-secure, the key-secure or the insecure class (by decreasing security order). Security is to be assessed within a framework (WOA, KMA or KOA [START_REF] Cayre | Watermarking security part I: Theory[END_REF]). If, within the given framework, the watermarking scheme belongs to the unsecure class, one may then compute its security level. WOA (Watermark Only Attack) is when the pirate has only access to watermarked contents, KMA (Known Message Attack) is when the pirate has access to watermarked contents and the corresponding hidden message, and finally KOA (Known Original Attack) is when the pirate has access to pairs of watermarked and corresponding original contents.

In the sequel, we assume that the attacker have access to a set of contents that have been watermarked using the same key but different messages. This framework has been called WOA (Watermarked content Only Attack) [START_REF] Cayre | Watermarking security part I: Theory[END_REF].

For SS schemes the secret key is defined by the set of carriers that are used to convey the secret message. Consequently, breaking the security of such schemes implies the estimation of the different carriers that are used to modulate each bit1 . Note that, because of the embedding equiprobability and unknown a-priori bit ordering, the estimation of the set of carrier may lead to the estimation of any matrices Uπ = π({±ui}) and Sπ = π({±si}) where π() is a permutation function. An important question naturally arise: whether a scheme can be considered secure if it is not possible to estimate a matrix Uπ, but if it is still possible to estimate the secret subspace which corresponds to the span of all vectors u i ? To answer this question we need to distinguish between several classes of security for Spread Spectrum watermarking schemes: subspace-security, key-security and insecurity as defined below:

• Definition of subspace-security:

A watermarking scheme is subspace-secure if it is impossible to estimate, from the observations Y, the secret subspace, of which one orthogonal basis is represented by the columns of the matrix B .

Corollary: A watermarking scheme is not subspace-secure if it is possible to decompose Y into:

Y = X + B Ŵ (4)
where the estimated matrices satisfy: limN o→+∞ X = X, limN o →+∞ B = B. The estimated matrix Ŵ represents the projections of the watermark signals on the basis associated to B. The true carriers ui therefore lie somewhere in span(ui) = span(bi).

• Definition of key-security: A watermarking scheme is key-secure if it is impossible to estimate the secret key, e.g. the set of carriers represented by a matrix Uπ, from the observations Y.

Corollary:

A watermarking scheme is not key-secure if it is possible to decompose Y into:

Y = X + Ûπ Ŝπ (5)
where the estimated matrices satisfy: limN o→+∞ X = X, limN o →+∞ Ûπ = Uπ, limN o →+∞ Ŝπ = Sπ.

• Definition of insecurity: A watermarking scheme is insecure if it is not keysecure.

Note that subspace-secure schemes are also key-secure. Subspace-security differs from key-security in the way that if only key-security is achieved, it can still be possible to estimate basis vectors that span the subspace in which are included the secret carriers. If a scheme satisfies subspacesecurity, it implies that the watermarking algorithm is totally secure: according to the definition of security, it is not possible to obtain information on the secret key. If an algorithm is key-secure but not subspace-secure, it means that it is possible to copy or erase the watermark, but that it is not possible to decode the embedded message or to modify targeted bits. Note that the identification of the watermark subspace can also be used to improve the efficiency of a specific attack affecting the robustness of the algorithm by focusing only on the most useful information. The definitions of key-security, subspace-security and insecurity classes are illustrated on Fig. 1.

Subspace-secure watermarking.

Key-secure watermarking. Insecure watermarking.

Using BSS techniques for subspace and key estimation

In the case of spread spectrum watermarking, the secret key is equivalent to the set of secret sequences {u i }. Each secret sequence is added to the host signal (after a bit-wise modulation) to convey a message. Eventually, the secret key is only hidden by the host signal which suggests that denoising algorithms may be used to estimate the watermark. Techniques that are used to prove that an algorithm is not key-secure are usually very similar to techniques proving that a scheme is not subspace-secure. Key-security of SS schemes was addressed in [START_REF] Cayre | Watermarking security part II: Practice[END_REF] and subspace-security was addressed in [START_REF] Gwenaël | Danger of low-dimensional watermarking subspaces[END_REF]. A general methodology to estimate both key and subspace security is described below. Decomposition [START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF], that relates to key-security, and decomposition [START_REF] Gwenaël | Danger of low-dimensional watermarking subspaces[END_REF], that relates to subspace-security, can be performed using Blind Source Separation (BSS) techniques if we assume some statistical properties of the watermark signal. In the latter case, we will be able to estimate the true carriers, while in the former, we will only be able to disclose a basis of the secret subspace.

We first present techniques that can achieve decomposition [START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF]. Because si of S represents the modulation of the i th bit for each watermarked content, and because in the WOA setup each embedded bit is supposed to be independent from others, {si} i∈[1,...,Nc] can be considered as independent signals. In this case, Independent Component Analysis (ICA) techniques can be used to estimate both Ûπ and Ŝπ. The principle of ICA techniques is to find directions in the observed data space whose projections give singular distributions [START_REF] Hyvärinen | Independent Component Analysis[END_REF]. Based on the fact that the sum of independent variables tends to a Gaussian law, independent components are defined as the most "non-Gaussian" components. In the ICA setup, Ûπ is called the mixing matrix and Ŝπ the matrix of independent sources. X is considered as noise.

To assess the key-security of a SS-based technique, we have decided to adopt the following methodology which is generally used in BSS benchmarks:

1. We generate No observations of watermarked contents and generate the matrix of observations Y.

2. We whiten the observed signals using Principal Component Analysis. A reduction of dimension is therefore performed to reduce the searching time. If we consider that each host signal is generated from an i.i.d. process, the subspace containing the watermark generated by Nc carriers will be included into a Nc-dimensional space of different variance [START_REF] Gwenaël | Danger of low-dimensional watermarking subspaces[END_REF]. We consequently select the subspace generated by eigenvectors presenting singular (lower or higher) eigenvalues.

3. We run the FastICA algorithm [START_REF] Hyvärinen | Fast and robust fixed-point algorithms for independent component analysis[END_REF] on this subspace to estimate the independent components and the independent basis vectors (e.g. the secret carriers).

4. We compute the normalized correlation c between each original and estimated carriers. A value of c close to 1 means that the estimation of the component is accurate. An estimation close to 0 means that the estimation is erroneous. For Nc = 2, we may evaluate the estimation accuracy by plotting a 2D constellation of points of coordinates (c1, c2). A successful estimation will then provide a point close to one of the four cardinal points (0, 1), (0, -1), (1, 0), (-1, 0) 2 .

ICA techniques will not be efficient if {si} i∈[1,...,Nc] are dependent signals. In this case Principal Component Analysis can be used to estimate the watermark subspace. We can for example use the reduction of dimension of the initial observed space as presented in the second step to estimate the watermark subspace and one of its basis B.

Examples of insecure SS schemes

In this section we briefly describe two popular watermarking schemes (classical SS and improved SS) and test the proposed methodology to perform estimation of secret carriers. In the case of classical SS, the embedding is given for each vector by:

y = x + Nc X i=1 b(i)ui (6)
where b ∈ {-1; +1} Nc is the BPSK modulation of the embedded message m.

For ISS, proposed in [START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF], which can be considered as an informed-embedding variation of classical SS, the embedding is given by:

y = x + Nc X i=1 (αb(i) -λ zx,u i ||ui|| )ui (7)
where α and λ are respectively computed to minimise both the targeted average distortion and the error probability after addition of white Gaussian noise of a given variance. Eq. 6 and Eq. 7 can be easily transposed in the multidimensional case to obtain a formulation similar to Eq. 5: the matrix U still contains the carriers and the matrix Sm contains the modulation signals for each carrier.

We have applied the ICA-based carrier estimation method described in the previous section. Fig. 2 depicts the normalized correlation between the original and estimated carriers for 100 experiments considering each time 1000 watermarked vectors. We can notice that the estimations are globally more accurate for SS than for ISS. In this case, this is mainly due to the fact that the variance of the embedding for ISS is lower than for SS and consequently the estimation of the subspace relative to the watermark is less accurate in the second case. Both SS and ISS were experimented at the level of distorsion: the Watermark-to-Content Ratio (WCR) was set to -21dB.

NATURAL WATERMARKING

Natural Watermarking is a spread-spectrum watermarking scheme that is designed to ensure subspace-security against WOA attacks for 0-centered i.i.d symmetric distributions. 2 We use Nc = 2 for illustration purposes, dealing with more bits would require to use the Hungarian method [START_REF] Kuhn | The Hungarian method of solving the assignment problem[END_REF] to assign original and estimated carriers prior to the computation of the normalized correlation c. ISS embedding (N DR = 3dB, see [START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF] for definition of Document-to-Noise Ratio) We consider here i.i.d. Nv-dimensional Gaussian host signals [START_REF] Bas | Natural watermarking: a secure spread spectrum technique for woa[END_REF]. The principles that are the key concepts of NW are the following:

1. The fact that that the projection a each secret carrier on different host signals follows a Gaussian distribution (this is due to the Central Limit Theorem).

2. The proposed scheme is denoted "Natural" because the Nv-dimensional distributions of host and watermarked signals remain the same in the WOA context: embedding keeps the natural distribution of the host signal.

3. Point (1) (Gaussianity) prevents the estimation of each carrier and point (2) prevents the estimation of the watermark subspace.

Note that, in [START_REF] Bas | Natural watermarking: a secure spread spectrum technique for woa[END_REF], the theoretical assessment of the security class of NW is done and it is proved that there is no information leakage after embedding for NW: I(Y; U) = 0. NW can be seen as the Spread Spectrum equivalent of the Scalar Costa's Scheme [START_REF] Eggers | Scalar costa scheme for information embedding[END_REF] of a uniform host signal and a distortion parameter α = 0.5 [START_REF] Pérez-Freire | Information-theoretic analysis of security in side-informed data hiding[END_REF] because both schemes provide no information leakage about the secret key.

Embedding

For the sake of simplicity we consider Nc orthogonal carriers that are generated using a Gaussian generator following the law N (0, σ 2 u ) for each sample. Note that the distribution of each sample of the different carriers does not modify the properties of natural watermarking and that other distributions can be considered. The host signals are also generated according to a Gaussian law: each sample of each observation follows ∼ N (0, σ 2

x ). Consequenlty the random vector x follows a Nv-dimensional Gaussian law. The random variable zx,u i follows a Gaussian law of parameters zx,u i ∼ N (0,

σ 2 u i σ 2 x Nv
). This property is true because of the Central Limit Theorem as far as Nv is important. Moreover, this property is still valid if the various x are 0-centered and i.i.d.. The goal of NW is to design the embedding in such a way that the distribution of zy,u i will keep the same as the distribution of zx,u i .

The watermarked vector y is:

y = x + w (8)
where the watermark signal w is computed as follows:

w = - Nc X i=1 " 1 + (-1) m(i) sign(zx,u i ) " zx,u i ui 2 ui (9)
which means that the watermark wi associated to each carrier ui follows this simple embedding rule:

wi = 0 if m(i) = 1 ; zx,u i > 0 (10) or m(i) = 0 ; zx,u i < 0 (11) wi = -2 zx,u i ui 2 ui if m(i) = 1 ; zx,u i < 0 (12)
or m(i) = 0 ; zx,u i > 0 (13)

Eq. 9 states that x is symmetrically modified iff sign(zx,u i ) = (-1) m(i) . This embedding rule is depicted on Fig. 3. Note that the embedding rule used for NW is quite similar to the rule used for ISS. In both cases, each carrier ui is modulated according to the correlation zx,u i . For ISS, zx,u i is used to increase the distance between the different codewords and increase the robustness. For NW, zx,u i is used to not modify the natural distribution of the carriers and consequently to increase the security.

Advantages and drawbacks of NW

NW presents interesting properties:

• It is not possible to estimate the secret keys because the joint distribution of the carriers in the watermarked contents is circular. Fig. 4 presents the joint distribution of two carriers. As we can see, it is not possible to find the directions that are associated to each carrier.

• The host distribution is not modified after embedding and there is no information leakage. The ICA-based estimation attack described in Sec. 2.3 is not efficient to estimate the secret carriers. Fig. 5 presents the normalised correlation between the estimated carriers and the real ones after NW embedding for 100 experiments. The concentration of points close to the origin illustrates the fact that the estimation is not possible. Beside these theoretical advantages, NW also unfortunately leads to several drawbacks:

• The robustness of NW to Additive White Gaussian Noise (AWGN) addition attack is poor for low Watermark-to-Noise ratios (WNR). Fig. 6 depicts the bit error rate (BER) for ISS, NW and SS with respect to σ 2 N for W CR = -21dB and the same Nc and Nv. In this case, NW is the less robust scheme for σ 2 N > 0.06. For low noise addition however, NW is less sensitive to noise than SS. This is due to the fact that NW is built is such a way that the interference with the host signal is taken into account within the embedding function.

• The embedding for NW cannot guarantee that the power of the added carrier is in a given range. If the distortion is null for half of the bits; for the other half the distribution of the embedding strength for different watermarked contents follows a half-Gaussian distribution. Consequently, it is possible to have very important distortion due to the embedding on several contents (with very low probability however).

•

CIRCULAR WATERMARKING

Motivations

In this section, we present a new family of spread-spectrum watermarking schemes called Circular Watermarking (CW), of which NW is a special case. Looking back at NW with Nc = 2, it can be considered that the joint-distributions of the projection of the secret carriers considering watermaked contents are circular. The main characteristic of CW is that the joint-distributions of the secret carriers for CW keep the same property of circularity than the Gaussian joint-distributions for NW. Moreover the shape of the joint-distribution for CW has been designed to improve the robustness to AWGN addition and also to reduce the maximum possible distortion after embedding. Another property of CW is the fact that CW schemes are no longer subspace-secure even for i.i.d. Gaussian host signals.

The circular joint-distribution of the carriers after embedding offers a possibility to estimate the watermark subspace. However CW still offers key-security (the estimation of the secret carriers is not possible).

Definition of Circular Watermarking

The family of Circular Watermarking schemes is defined by the fact that the joint-distribution f (z1, . . . , zN c ) of the secret carriers u1, . . . , uN c is circular, which means that the distribution can be reduced to a distribution that depends only on one variable ρ:

f (z1, . . . , zN c ) = f (ρ) (14)
where ρ =

q z 2 1 + z 2 2 + . . . + z 2 Nc .
We can see that Natural Watermarking belongs to the family of Circular Watermarking schemes because the marginal densities of its carriers is Gaussian and then the joint-density can be written as:

f (z1, . . . , zN c ) = 1 (σ √ 2π) Nc exp " -(z 2 1 +...+z 2 Nc ) 2σ 2 « = 1 (σ √ 2π) Nc exp " -ρ 2 2σ 2 " (15)
It can be shown that NW is the only scheme that provides a circular joint distribution while keeping independent modulations between carriers [START_REF] Papoulis | Probability, Random Variables and Stochastic Processes[END_REF]. This means that, except for the case of NW, other CW schemes have to introduce dependency among modulation coefficients to achieve circularity.

A practical implementation based on ISS

We present here a possible solution to obtain one CW scheme which is based on Improved Spread Spectrum. The Nv-dimensional distribution of the projection of the carriers after ISS corresponds to sums of multivariate Gaussian distributions centred on cardinal points ( α, . . . , α). One solution to "circularise" this distribution after ISS is to randomly move each cardinal point on a specific region of a Nc-dimensional sphere.

To perform this, we construct a random vector d which is uniformly distributed on a Nc-dimensional sphere of unitary radius. One possible way to generate d is to first generate a Nc-dimensional Gaussian vector and to normalise it as proposed in [START_REF] Knuth | The Art of Computer Programming[END_REF]:

d = (d1, . . . , dN c ) = ( g1 ||g|| , . . . , gN c ||g|| ) ( 16
)
where gi ∼ N (0, 1). We construct

d + = (|d1|, . . . , |dN c |)
which is a unitary random vector that is uniformly distributed on the portion of the Nc-sphere presenting positive coordinates. The embedding formula to achieve a circular implementation of ISS watermarking is:

y = x + √ Ncα `b(1)d + 1 u1 + . . . + (b(Nc)d + Nc uN c -λ( zx,u 1 ||u 1 || u1 + . . . + zx,u Nc ||u Nc || uN c ) (17)
Note that by analogy with dither modulation watermarking [START_REF] Chen | Quantization index modulation : a class of provably good methods for digital watermarking and information embedding[END_REF], vector d + can be seen as a dither vector for the family of SS watermarking schemes : the modulation of each carrier ui with d + i hides the singularities of the initial distribution of the projections of the carriers as the dither vector in DM hides the location of the quantisation cells.

BER comparison

Fig. 7 depicts the joint-distributions for ISS and the circular extension of ISS for a 2-bit embedding scheme. As expected, the CW-ISS scheme produces a "ring-shaped" 2D circular distribution. Each codeword is associated with one quarter of the distribution and the shape of such a distribution enables to achieve a better robustness to AWGN than NW: it is due to the fact that there are statistically less codewords which are close to the decoding borders (X and Y axis) for CW-ISS than for NW (see Fig. 4).

Fig. 8 compares the robustness of the various proposed watermarking schemes to AWGN addition for the same hidden channel rate (same Nc and same Nv). Formulas for NW and CW-ISS are given in the appendices and those for SS and ISS are taken from [START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF]. For CW-ISS both practical and theoretical values are plotted. We can see in this figure that the improvement of CW-ISS over NW for Nc = 2 is significant. Moreover, if the performance CW-ISS is still far from the performance of ISS for low noise power, CW-ISS enables to have a key-secure watermarking scheme that equals or outperform classical SS. Also note that for the case of CW-ISS we used the same parameters α and λ than for ISS. No specific optimisation of these two parameters taking into account the specific shape of the distribution has been done. Fig. 9 illustrates the behaviour of the robustness for CW according to the number of carriers when the distortion per carrier remains constant. We can notice that our implementation of natural watermarking has a drawback: contrary to other SS watermarking schemes, the robustness of CW decreases with the number of used carriers. Practically the BER seems to converge toward a limit when the dimension goes toward infinity (BER=9.4% for Nc = 500) which is still smaller than the BER achieved using NW.

CONCLUSION AND PERSPECTIVES

We have presented in this paper a classification of security as well as different ways to achieve key or subspace security for SS-based watermarking schemes. Natural Watermarking enables to obtain subspace security if the host signal is considered i.i.d. Gaussian. One very interesting property of NW is the fact that after embedding, the secret carriers have circular distributions which prevent their estimations. To obtain more robust watermarking scheme we have proposed to extend the property of circularity to other SS embedding schemes. It is important to notice that in this case, CW schemes are generally only key-secure. Our future works will focus on finding optimal embedding strategy for the family of CW schemes with respect to distortion and robustness criteria. We would like also to define the conditions to achieve security for more sophisticated SS-based watermarking schemes which use informed coding [START_REF] Miller | Applying informed coding and embedding to design a robust, high capacity watermark[END_REF]. Finally, in this paper, we also wanted to outline what is the possible cost of watermarking security in terms of robustness.

APPENDIX A. BER FOR NW

Let the noise being Gaussian with law N (0, σ 2 N ) and corresponding pdf:

f (x) = 1 √ 2πσN exp " -x 2 2σ 2 N « (18)
If a 0 is coded, the correlation value z has a pdf of a half-Gaussian function:

g(x) = 2 √ 2πσW exp " -x 2 2σ 2 W « if x ≤ 0 (19) g(x) = 0 if x > 0 (20)
We have the following relations (that are not used in the equations for the sake of clarity):

σ 2 N = σ 2 u σ 2 n et σ 2 W = σ 2 u σ 2
x . The pdf of the watermarked signal which undergoes noise is:

(g * f )(t) = Z +∞ -∞ g(x)f (t -x)dx (21)
which can be expressed as:

(g * f )(t) = A Z 0 -∞ exp - " x - σ 2 W t σ 2 N +σ 2 W " 2 2 " σ W σ N √ σ 2 W +σ 2 N « 2 dx (22) with A = 2 exp -t 2 2σ 2 N + σ 2 W t 2 2σ 2 N (σ 2 N +σ 2 W ) ! 2πσ W σ N
after a variable substitution we can compute the integral part I(t) as:

I(t) = √ 2σW σN p σ 2 W + σ 2 N √ π 2 erfc σW t √ 2σN p σ 2 W + σ 2 N ! (23)
and finally :

Pe = Z +∞ 0 G σ 2 W +σ 2 N (t) erfc σW t √ 2σN p σ 2 W + σ 2 N ! dt (24)
with G σ 2

C. DISTORTION FOR CW (ISS BASED IMPLEMENTATION -2 CARRIERS)

The distortion for this implementation is the same than the distortion for classical ISS [START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF].

D. BER FOR CW (ISS BASED IMPLEMEN-TATION -2 CARRIERS)

Let's suppose Gaussian noise with a 2D corresponding pdf:

f (x, y) = 1 2πσ 2 Niss exp " -(x 2 + y 2 ) 2σ 2 Niss « (29)
with σ 2 Niss = σ 2 N /(Nvσ 2 u ). The marginal pdf f (y) is:

f (y) = 1 √ 2πσNiss exp " -y 2 2σ 2 Niss « (30)
After the Circular implementation of ISS we can assume that the pdf of the carriers for watermarked contents if the first coded bit corresponds to 0 is given by: g(x, y) = with αiss calculated from [START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF] and:

σ 2 iss = (1λiss) 2 σ 2 X /(Nvσ 2 U ). The marginal pdf g(y) is given by:

g(y) = Z +∞ -∞ g(x, y)dx (33)
and must be computed numerically.

The pdf of the watermarked signal which undergoes noise is:

(g * f )(t) = Z +∞ -∞ g(y)f (t -y)dy (34)
and the probability of error Pe is expressed as :

Pe = Z +∞ 0 (g * f )(t)dt (35)
Also note that these last two expressions have to be computed numerically.

Figure 1 :

 1 Figure 1: Representations of the possible observations for the three different classes of security.

Figure 2 :

 2 Figure 2: Normalised correlations between the two estimated carriers and ui ∼ N (0, 1) the real ones. For both schemes, No = 1000, W CR = -21dB and Nv = 512.

Figure 3 :

 3 Figure 3: Natural watermarking for embedding of one bit equal to 1 on three different contents. Only the third bit calls for a model-based symmetry.

Figure 4 : 1 .Figure 5 :

 415 Figure 4: Joint distributions of two carriers for NW. No = 10000, W CR = -21dB, Nv = 512, σ 2x = 1. The direction of the original carriers (horizontal and vertical axis) cannot be estimated on a multivariate Gaussian distribution.

Figure 6 :

 6 Figure 6: Comparison of BER for NW, classical SS ISS. Nv = 512, W CR = -21dB.

Figure 7 : 2 N = 1 ,

 721 Figure 7: Joint distributions of two carriers for ISS and Circular implementation of ISS. No = 10000, W CR = -21dB, σ 2 N = 1, Nv = 512, Nc = 2.

Figure 8 :

 8 Figure 8: Comparison of BER for NW, classical SS ISS and CW-ISS. Nv = 512, W CR = -21dB and Nc = 2.

Figure 9 :

 9 Figure 9: Evolution of BER according to the number of carriers for NW, classical SS, ISS and CW-ISS. Nv = 512, the distortion per carrier is constant (W CR = -24dB for Nc = 1).

W +σ 2 N

 2 The pdf of the watermark (on each sample) is the following:if x < 0 f (x) ∼ N (0, 4σ 2 x σ 2 u /Nv) (25) if x ≥ 0 f (x) = δ(x)/2 -to-Content-Ratio is expressed as follows:

  The major drawback of NW is the fact that subspacesecurity class can only be achieved if we assume that the host signal is i.i.d. with Gaussian distribution. If it is not the case, ICA techniques will enable to estimate a Nc-dimensional subspace with multivariate Gaussian distribution which represents the watermark subspace. Consequently, if the host signal is not i.i.d. with Ncdimensional Gaussian distributions, NW is only keysecure.

		1
		ISS
		NW
		SS
		0.1
	BER	0.01
		0.001
		0.001 0.0001	0.01	0.1	1
				VarN

Each carrier ui is supposed to be associated with the bit bi that is transmitted. In particular, informed coding strategies are not considered in this paper.

ACKNOWLEDGEMENTS

The work described in this paper has been supported (in part) by the European Commission through the IST Programme under Contract IST-2002-507932 ECRYPT and the National French projects ACI-SI Fabriano, RIAM Estivale and ARA TSAR.


Benoit Roue
email: benoit.roue@lis.inpg.fr

Patrick Bas
email: patrick.bas@lis.inpg.fr

Jean-Marc Chassery
email: marc.chassery@lis.inpg.fr

Improving LSB Steganalysis using marginal and joint probabilistic distributions

Keywords: H.2.0 [Software Arcitectures]: Security Steganography, Steganalysis, Texture Analysis, LSB

The goal of steganalysis is to search for the presence of hidden information in numerical contents. This paper is based on a previous LSB steganalysis scheme for digital images that estimates the size of the hidden message. The accuracy of this algorithm is first outlined, then the limits are presented in order to introduce some solutions based on texture processing: analysis of histograms and coocurrence matrices are presented and their uses, to improve steganalysis using segmentation, is proposed 1 .

INTRODUCTION

Since centuries, steganography has been used to share information between friends while keeping it secret to other people. In the first time techniques were simple, for example Romeo could have used invisible ink to write his love to Juliet... Steganographic techniques have to embed a message in such a way that it could not be found, neither with analytic techniques, nor visually (c.f. Figure 1). On this point steganography differs with watermarking which is more devoted to embed robust watermarks. Nowadays with the appearance of numerical contents, like digital images or sharewares, steganography is more and more used via internet. The hidden information may represent particular key points and may be used for strategic and politic purposes [START_REF] Fridrich | Detecting LSB Steganogeraphy in color and grayscale images[END_REF].

The goal of steganographic analysis, also called steganalysis, is in a first step to bring out drawbacks of steganographic schemes by proving that an hidden information is embedded in a content. The estimation of the size of the hidden information, which, for example, is proportional with the probability p that a pixel has been modified by LSB embedding, can also be performed in a second step. Such a schemes may be used by organisms of security to verify that internet sites does not keep suspect (e.g. hidden) information. Moreover steganalysis techniques can help a customer to protect his privacy by proving that a numerical product such that an Internet software is not a spyware and does not sent private information without the knowledge of the customer. A lot of steganographic techniques have been developed in the past years, they can be divided into two classes: ad hoc schemes (schemes that are devoted to a specific steganographic scheme) [START_REF] Fridrich | Reliable detection of LSB Steganogeraphy in color and grayscale images[END_REF] [START_REF] Dumitrescu | Detection of LSB steganography via sample pair analysis[END_REF] and schemes that are generic and that use classifiers to differenciate original and stego images [START_REF] Farid | Detecting hidden messages using higher-order statistical models[END_REF]. The last one work in two steps, you have first to extract the feature vectors (high pass components, prediction of error...) and then to train the classifier to separate steganalysed images from original images. The first category is much more efficient than the second and consequently we have focused our paper on Low Significant Bit ad hoc techniques.

LSB EMBEDDING IN THE SPATIAL DO-MAIN

The LSB insertion scheme (c.f. Figure 2) is obviously the simplest way to hide information in cover data, although a great amount of bits can be ranged without causing perceptible degradation of the cover object. Indeed, digital images are generally coded with eight bits by colour channel, so an insertion in the low significant bitplane is not visible. It is obvious that such a scheme is not interesting in water- marking, because the watermark would not be robust and could easily be removed, but , again, in steganography the robustness is not the main point.

In this paper we restrict the scope of our studies to LSB embedding in the spatial domain, but other LSB schemes exist in transformed domain (e.g. insertion in the DCT domain [START_REF] Upham | Jpeg-jsteg, modification of the independent jpeg group's jpeg software for 1-bit steganography in jfif output files[END_REF]).

DUMITRESCU'S SCHEME

The goal of this section is to explain the scheme introduced by Dumitrescu et al. in [START_REF] Dumitrescu | Detection of LSB steganography via sample pair analysis[END_REF] which can be seen as a mathematical formulation of the RS method, one of the first LSB steganalysis scheme presented by Fridrich [START_REF] Fridrich | Reliable detection of LSB Steganogeraphy in color and grayscale images[END_REF].

Definitions

This scheme is based on the statistical analysis of adjacent sample pairs of a numerical image. The authors define P as the multiset of values of sample pairs, P is partitioned in two submultisets Dn and Cm :

• Dn is defined such as the values of the sample pair are (u, u + n) or (u + n, u) with 0 ≤ n ≤ 2 b -1.

• Cm is defined such as the values of the sample pair after right shifting are (u , u + m) or (u + m, u ) with 0 ≤ m ≤ 2 b-1 -1.

In those two definitions, b is an integer equal to the number of bits which are used to code a sample (e.g. b = 8 in a 256 gray levels image). This leads to notice that the multisets Cm are invariant under the LSB embedding. Finally D2m+1 is fractioned into two sub-multisets X2m+1 and Y2m+1, defined such as :

X2m+1 = D2m+1 ∩ Cm+1 et Y2m+1 = D2m+1 ∩ Cm.
An other way to define X2m+1 and Y2m+1 is to say that the sample pair having the largest component which is odd is in Y2m+1 and the sample pair having the largest component which is even is in X2m+1 (cf. Figure 3). It is obvious that, in a natural image, there is no reason for a sample pair to have its largest value to be odd rather than even. This leads us to the main assumption of the method on which is based the steganalysis:

E{|Y2m+1|} = E{|X2m+1|}. 2 (1)
To summarize, Cm, which is closed under LSB embedding, is divided into four submultiset, which are: X2m-1, X2m, Y2m and Y2m+1.

The variation of the number of elements of those multisets considering the message insertion will lead us to estimate, as we will see in the next section, the length p of the embedded message thanks to equality (1).

Detection of LSB Steganography

As presented by Dumitrescu et al. in [START_REF] Dumitrescu | Detection of LSB steganography via sample pair analysis[END_REF] the effects of the LSB embedding on the multisets X2m-1, X2m, Y2m and Y2m+1 can be be totally described with a modification pattern π ∈ {00, 01, 11, 10}. Those modifications are listed in the table 1. Let ρ(π, P ) be the probability that the sample pair of P is modified with π and p be the length of the embedded message. Then, if the message is randomly inserted in the image, this leads to the following probabilities:

• ρ(00, P ) = (1 -p 2 ) 2 , • ρ(01, P ) = ρ(10, P ) = p 2 (1 -p 2 ), • ρ(11, P ) = ( p 2 ) 2 . π 00 01 11 10 X2m-1 X2m-1 Y2m Y2m+1 X2m X2m X2m Y2m+1 Y2m X2m-1 Y2m Y2m X2m-1 X2m Y2m+1 Y2m+1 Y2m+1 X2m X2m-1 Y2m
Table 1: Modifications of the several multisets under LSB embedding.

Finally, thanks to equality (1) the authors estimate the message's length with the following quadratic equation (( 2) and ( 3) ):

(|Cm|-|C m+1 |)p 2 4 - (|D 2m |-|D 2m+2 |+2|Y 2m+1 |-2|X 2m+1 |)p 2 +|Y2m+1| -|X2m+1| = 0, m ≥ 1 (2)
and

(2|C 0 |-|C 1 |)p 2 4 -(2|D 0 |-|D 2 |+2|Y 1 |-2|X 1 |)p 2 +|Y1| -|X1| = 0, m = 0. ( 3
)
Where p denotes the proportion of modified pixels under LSB embedding.

In order to improve the accuracy of the estimated message lenght Dumitrescu et al. propose to extend equations ( 2) and ( 3) with 0 ≤ m ≤ 30. So instead of equalities ( 2) and ( 3), we will estimate p thanks to equalities (3) and ( 4):

(

EVALUATION AND LIMITS OF THE AL-GORITHM

We have tested this method on a free database of 108 images from the kodak image database ( [START_REF]Kodak database[END_REF]).

Evaluation setup

The goal of this section is to describe how is implemented the algorithm in order to improve its performances.

The several steps of the used method are the following:

• The relative difference between X2m+1 and Y2m+1, in order to verify the assumption (1), is also computed with:

= 2 * ||X2m+1| -|Y2m+1|| |X2m+1| + |Y2m+1|
• The message is randomly generated with k keys. In the practical experiments we generally use k = 10.

• This message is scattered in eleven ratios of the cover image, in such a way that 0%, 10%, 20%, . . . , 100% of the low significant bitplane of the image is perturbed.

• Then the embedded message's length is estimated via the equations ( 2) and ( 3) on each ratio, m varies from 0 to 30.

• Finally, the MAE (Mean Absolute Error) is computed for each ratio of each key, by computing the difference between the real length and the estimated lenght of the message.

This method is used for each image from the database, as a final result we have got the mean of the MAEs, which is used to describe the general performance of the algorithm.

Results

From the tests we have noticed that the accuracy of the presented scheme is very good for almost 70% of the database (EAM≤ 3%). Indeed the results obtain on the whole set of images (Table 2) show that the algorithm have very high estimation errors (EAM above 10%) for only 2% of the images, and have very low estimation errors (EAM under 1%) for 13% of the images.

In the last case, images correspond to homogeneous images like the image "jellies" presented in the figure 4.

In the whole set of images the estimation errors are relatively low, indeed the EAM is of 2, 7% and the equality 1 is respected, on the set we have = 0, 023.

MAE number of images (%)

≤ 1% 13 ≤ 2% 42 ≤ 3% 69 ≤ 4% 85 ≥ 6% 4 ≥ 10% 2
Table 2: Results on the whole set of images.

Figure 4 represents selected images that provide both low and high estimation errors.

Even if the scheme yields to very accurate estimations of the message's length, it is interesting to point out the image's features that lead to important estimation errors. These characteristics have to be identified in order to:

-detect images that are likely to counter steganalysis schemes, e.g. images that may contain a high ratio of undetectable hidden information; -improve the original scheme by reducing the outlined drawbacks.

Limits and analysis

As we said in the past section, the studied scheme is really efficient on most of images, but in several cases the Mean Absolute Error becomes significant (refer to table 3). In this case, our analysis leads to the fact that important estimation errors are due to two different drawbacks:

-the non-equality of the cardinals, -a non-adapted distribution of the joint statistics of the image. Image

Non-equality of the cardinals

Because the presented scheme use an a priori hypothesis that E{|Y2m+1|} = E{|X2m+1}, this hypothesis has to be checked. However there exists natural images that do not respect this hypothesis: for example image having large uniform areas such as shadows or sky may contain isolated peaks in their histogram.

As we can see in the table 3, for the image "notredamewindow" the relative difference between X2m+1 and Y2m+1 is not insignificant. Indeed, there is a factor 10 between this value and mean of the relative differences (Table 3). The histogram of this image is depicted on Figure 5. On this histogram it is possible to notice the presence of a singular peak defined by an isolated double peak for pixel values equal to 9 and 10. Thus, such a configuration leads to an important increase of the value of |Y1| and consequently will break assumption [START_REF]Kodak database[END_REF]. Our analysis has outlined the fact that this drawback is the explanation if only about 10% of a wrong estimation of the message length, nevertheless a solution is proposed in section 5.1.

(a) (b)

Joint statistics of the image

For several images the studied scheme is not accurate even if assumption ( 1) is verified, in this case the problem must come from another reason, and more particularly, it comes from the empirical choice of the values of m. Indeed, let take the image "sandprints", in this image we can notice that X2m+1 Y2m+1, and nevertheless the Mean Absolute Error is far from being insignificant (table 3). In section 3.1 we have seen that Dumitrescu's scheme is based on joint statistics (statistics on adjacent sample pairs), so it is interesting to analyse the statistics of images that lead to high estimation errors in order to compare with those providing reliable estimations. Such an analysis is possible by using the coocurrence matrix which represents the joint statistics of the image. The coocurence matrix takes into account the probability for a sample to have a grey level, knowing its adjacent sample value, and is computed as following: In order to be coherent with the studied algorithm the pixels analysed are adjacent, in that case t is equal to (1,0). In order to observe the influence of the statistics of the images on results, we have computed the coocurrence matrices of the whole database. In the Figure 6 we give coocurrence matrices of the images presented in Figure 4.

M Ct(a, b) = Card{(s, s + t) ∈ I 2 \ V [s] = a, V [s + t] = b} (
We can notice two important points:

• For images presenting a low estimation error, the distribution of the maxima of joint probabilities are well located along the diagonal, it means that the way of summation on m is efficient. Indeed the samples take into account will be enough representative to have a good estimation of the message's length.

• For images that do not work the distribution of the maxima of joint probabilities are not located at all, therefore the summation is done on pixel pair which have not a difference of value enough represented. This leads us to take care of the distribution of the coocurrence matrix. Indeed it seems to be optimum to only take into account sample pairs that are largely represented in the coocurrence matrix because such pairs represent pixels which belong to textured areas of the image.

IMPROVEMENTS

The goal of this section is to proposed some improvements to the studied scheme, in order to compensate the related drawbacks.

Segmentation of the marginal probability distribution

As we have seen the difference of cardinals which break the assumption (1) leads to huge estimation errors.

If the cause of the non equality of the cardinals is that there is a double peak for pixel values equal to x and y in the histogram, we propose to not take care, during the steganalysis, of sample pair that have values (x, y). This will restore the equality between cardinals, and lead to a better estimation of the message's length.

Segmentation of the joint probability distribution

As we have seen in section 3.2 the values of m are empirically chosen from 0 to 30, but for some images it seems to not be adequate, so the goal of this section is to introduce an algorithm that take the statistics of the analysed image into account. The implementation of our algorithm is the following (also see Figure 7): • The way of embedding the message is the same that in section 4.1 (i.e. 11 ratios of the image are used for 10 different keys).

• For each embedded message we compute the coocurrence matrix of the cover image.

• Then this coocurrence matrix is threshold in order to keep only the largest values (we take 10 values of threshold).

• We only estimate the message's length on sample pairs that have their difference of values contain in the segmented matrix.

To summarize we only sum the sets' cardinals when m is enough represented in the coocurrence matrix.

Threshold of the matrix of coocurrence

The choice of the threshold of the coocurrence matrix is important in this method. Therefore we have computed the EAM for several thresholds, in order to understand the meaning of this value. For several thresholds the estimation of the message's length is not efficient at all. For example if we take a very low value, it is the same as to use all the coefficients of the matrix of coocurrence.

On an other side if we take a too much big value, we will compute the message's length on too few sample pairs of pixels. We have to find a compromise for the choice of the threshold.

The results shown in the graphic 8 describe the variation of the the MAE according to the threshold of the coocurrence matrix of the two images "duneprints" (on the left) and "sandprints" (on the right). We must notice that if we take a threshold too much big, the results are skewed because too few pairs of pixels are taken into account, therefore we have to be careful with choice of this threshold.

Experimental results

We have improved both algorithm from sections 5.1 and 5.2 on the images presenting a high MAE.

Segmentation of the marginal probability distribution

Here the image on which the scheme was tested is "notredamewindow". The results are really good, indeed the error estimation is divided by nearly 3 (Table 4).

MAE (%) Image

before algo after algo notredamewindow 12.01 4.23

Table 4: Estimation errors before and after the segmentation of the histogram.

Segmentation of the joint probability distribution

We have tested this scheme on the three images of the kodak database that have the worst results. For each image we have chosen the best threshold (i.e. the one which provides best estimations in Section 5.3), and the estimation errors lie in the The estimations of the embedding message's length are by this way, hugely improved, for this kind of images.

It is clear that an automatic choice of the the threshold would be a best improvement, and at the moment we work on an adaptive contrast function (based on the contrast function computed thanks to the coocurrence matrix and presented by Haralick in [START_REF] Haralick | Textural features for image classification[END_REF]) that could determine what should be the optimum threshold for a given image.

CONCLUSIONS AND PERSPECTIVES

The dumitrescu's scheme, that is very efficient on most of images, does not take the image texture into account, and by this way, is not always reliable. But thanks to texture image processing our perspectives are to compensate this drawback using the coocurence matrix to differentiate image which provide low or high MAE, and thanks to a contrast function decide which threshold is to take. An other track to follow is to transform from high frequency to low frequency the seventh Highest Significant Bitplanes of images that do not have good estimations.

Figure 1 :

 1 Figure 1: Steganography's problem.

Figure 2 :

 2 Figure 2: Message embedding in the Low Significant Bit of an image.

Figure 3 :

 3 Figure 3: Definitions of the several sets.

Figure 4 :

 4 Figure 4: Several tested images: jellies (a), crow (b), notredamewindow (c) and sandprints (d).

Figure 5 :

 5 Figure 5: Image notrewindow (a) and its histogram's region of interest (b).

  5) With M Ct(a, b) the element of the coocurrence matrix in (a, b), s a sample of the image, V [s] the value of the sample, I the image and t the distance between the two pixels.

Figure 6 :

 6 Figure 6: Coocurrence matrices of Tested Images: jellies (a), crow (b), notredamewindow (c) and sandprints (d).

Figure 7 :

 7 Figure 7: Algorithm used.

Figure 8 :

 8 Figure 8: MAE as a fonction of the treshold.

Table 3 :

 3 Examples of errors.

		MAE (%)
	jellies	0.54	0.017
	crow	0.87	0.004
	notredamewindow	12.01	0.22
	sandprints	15.18	0.046

Table 5 .

 5

		MAE (%)
	Image	before algo after algo
	notredamewindow	12.01	4.23
	sandprints	15.18	4.2
	duneprints	10.14	3.2

Table 5 :

 5 Estimation errors before and after the segmentation of the coocurrence matrix.

|.| denotes the number of elements of a set.


Yoan Miche

Benoit Roue

Amaury Lendasse

Patrick Bas

A Feature Selection Methodology for Steganalysis

This paper presents a methodology to select features before training a classifier based on Support Vector Machines (SVM). In this study 23 features presented in [1] are analysed. A feature ranking is performed using a fast classifier called K-Nearest-Neighbours combined with a forward selection. The result of the feature selection is afterward tested on SVM to select the optimal number of features. This method is tested with the Outguess steganographic software and 14 features are selected while keeping the same classification performances. Results confirm that the selected features are efficient for a wide variety of embedding rates. The same methodology is also applied for Steghide and F5 to see if feature selection is possible on these schemes.

Introduction

The goal of steganographic analysis, also called steganalysis, is to bring out drawbacks of steganographic schemes by proving that an hidden information is embedded in a content. A lot of steganographic techniques have been developed in the past years, they can be divided in two classes: ad hoc schemes (schemes that are devoted to a specific steganographic scheme) [START_REF] Fridrich | 6th Information Hiding Workshop[END_REF][START_REF] Dumitrescu | Detection of LSB steganography via sample pair analysis[END_REF][START_REF] Roue | Improving lsb steganalysis using marginal and joint probabilistic distributions[END_REF] and schemes that are generic and that use classifiers to differentiate original and stego images [START_REF] Lyu | Detecting hidden message using higher-order statistics and support vector machine[END_REF][START_REF] Pevny | Toward multi-class blind steganalyser for jpeg images[END_REF]. The last ones work in two steps, generic feature vectors (high pass components, prediction of error...) are extracted and then a classifier is trained to separate stego images from original images. Classifier based schemes have been more studied recently, and lead to efficient steganalysis. Thus we focus on this class in this paper.

Advantages of feature selection for steganalysis

Performing feature selection in the context of steganalysis offers several advantages.

it enables to have a more rational approach for classifier-based steganalysis:

feature selection prunes features that are meaningless for the classifier;

feature selection may also be used to improve the classification performance of a classifier (in [START_REF] Weston | Feature selection for SVMs[END_REF] it is shown that the addition of meaningless features decreases the performance of a SVM-based classifier); -another advantage of performing feature selection while training a classifier is that the selected features can help to point out the features that are sensitive to a given steganographic scheme and consequently to bring a highlight on its weaknesses. -The last advantage of performing feature selection is the reduction of complexity for both generating the features and training the classifier. If we select a set of N features from a set of M , the training time will be divided by M/N (this is due to the linear complexity of classifiers regarding the dimension).

The same complexity reduction can also be obtained for feature generation if we assume that the complexity to generate each feature is equivalent.

Fridrich's Features

The features used in this study were proposed by Fridrich et al [START_REF] Fridrich | 6th Information Hiding Workshop[END_REF]. All features are computed in the same way: a vector functional F is applied to the stego JPEG image J 1 and to the virtual clean JPEG image J 2 obtained by cropping J 1 with a translation of 4 × 4 pixels. The feature is finally computed taking the L1 of the difference of the two functionals :

f = ||F (J 1 ) -F (J 2 )|| L1 . (1)
The functionals used in this paper are described in the Table

Classifiers for steganalysis

This section presents two classifiers that differ in term of complexity and a method to estimate the mean and variance of the classification accuracy obtained by any classifier.

-K-Nearest Neighbours: the K-NN classifiers use an algorithm based on a majority vote: using a norm (usually Euclidean), the K nearest points from the one to classify are determined. The classification is then based on the class that belongs to the most numerous closest points, as shown on the figure (Fig 1). The choice of the K value is dependent on the data, and the best value is found using using a leave-one-out cross-validation procedure [START_REF] Efron | An Introduction to the Bootstrap[END_REF]. Note that if K-NN classifiers are usually less accurate than SVM classifiers, nevertheless, the computational time for training a K-NN is around 10 times smaller than for training a SVM.

-Support Vector Machines: SVM classification uses supervised learning systems to map in a non-linear way the features space into a higher dimensional feature space [START_REF] Zhang | An introduction to support vector machines and other kernel-based learning methods[END_REF]. A hyper-plane can then be found in this high-dimensional space, which is at the maximum distance from the nearest data points of the two classes so that points to be classified can benefit from this optimal separation.

-Bootstrapping for noise estimation: the bootstrap algorithm enables to have a confidence interval for the performances [START_REF] Efron | An Introduction to the Bootstrap[END_REF]. A random mix with repetitions of the test set is created, and then used with the SVM model computed before with a fixed train set. This process is repeated R times and thus gives by averaging a correct noise estimation when N is large enough.

? Class 1 Class 2

Fig. 1. Illustration of the K-NN algorithm. Here, K = 7: The Euclidean distance between the new point (?) and the 7 nearest neighbours is depicted by a line. In this case we have the majority for the light grey (4 nearest neighbours): the new point is said to be of class 2.

Feature selection methods

This section presents two different feature selection methods.

-Exhaustive search: in this case, we use a full scan of all possible features combinations and keep the one giving the best result. If you consider N features, the computational time to perform the exhaustive search equals the time to train/test one classifier multiplied by 2 N -1. Consequently this method can only be used with fast classification algorithms.

-The "forward" selection algorithm: The forward approach proposes a suboptimal but efficient way to incrementally select the best features [START_REF] Rossi | Mutual information for the selection of relevant variables in spectrometric nonlinear modelling[END_REF]. The following steps illustrate this algorithm : 1. try the α i,i∈ 1,N features one by one; 2. keep the feature α i1 with the best results; 3. try all couples with α i1 and one feature among the remaining N -1; 4. keep the couple (α i1 , α i2 ) giving the best results; 5. try all triplets with (α i1 , α i2 ) and one feature among the remaining N -2; 6. . . . iterate until none remains.

The result is an array containing the N the features ranked by minimum error. The computational time is equal to N × (N + 1)/2 multiplied by the time spent to train/test one classifier.

Applying feature selection to SVMs

Using the forward algorithm directly on SVM is too time-consuming. Consequently we propose to perform the feature selection for SVMs in three steps depicted on Figure 2.

1. Forward using K-NN: in this step, we use the explained forward algorithm with a K-NN classification method to rank features vectors. Since the K-NN is fast enough, it is possible to run this step in a reasonable time. 2. SVM and Bootstrapping: using the ranked features list found by the K-NN forward algorithm, we run 23 SVMs using the 23 different feature vectors, and a bootstrap on the test set, with approximately 5000 iterations. 3. Features selection: in the end, the curve from the bootstrap data shows that within the noise estimation, we can reduce the number of features, based on the fact that the addition of some features degrades the classification result. Within the noise range, the first L < N selected features present the best compromise for a same classification performance.

Experimental Results

The experiments have been performed using a set of 5075 images from 5 different digital cameras (all over 4 megapixels). A mix of these images has then been made, and half of them have been watermarked using Outguess 0.2 [START_REF] Provos | Defending against statistical steganalysis[END_REF], with and embedding rate of 10% of non zero quantised DCT coefficients. Each image has been scaled and cropped to 512×512, converted in grey levels and compressed using a JPEG quality factor of 80%. The extracted features from the 5075 images have then been divided in a training (1500 samples) and test set (3575 samples).

The SVM library used is the libSVMtl [START_REF] Ronneberger | Libsvmtl extensions to libsvm[END_REF].

Accuracy of KNN with feature selection

We present here (Fig 3) the classification accuracy of the forward algorithm using the K-NN method. In our case, the decision on whether to keep or leave out a feature has been made only on the results of the leave-one-out (i.e. using only the training set). As one can see from the curves, it finds the best set of features with only 6 of them (Leave-one-out classification rate around 0.705). Adding more features only results here in a degradation of the classification result. But tryouts using only those 6 features have proven that it is not the best solution for SVM. Consequently, we choose to use this step of the process only to obtain a ranking of the features.

Accuracy of SVM with feature selection

Since the 6 forward K-NN selected features are not enough, this process step uses all features, but according to the ranking order given by the forward K-NN. The SVM is thus used (RBF-type kernel), with the same training and test sets. As mentioned before, we use here a bootstrap technique to have a more robust result and an estimation of the noise. As it can be seen (cf Figure 4), the best accuracy is obtained using 14 features, achieving 72% of correct classification (10-fold cross-validation). In this case, the test error curve stays close to the 10fold one. For comparison purposes we have also plotted the performance of the K-NN on sets of 14 features taken randomly from the original ones. As illustrated on figure 3, it never achieves more than 68% in correct classification (training). This proves that the selected features using the forward technique are relevant enough.

Selected features

Table 2 presents the set of features that have been selected. For sake of simplicity the cardinal part for each feature has been skipped. Table 3 presents the final results from the explained method. It can be seen that the selected 14 features set is giving better results (within the noise estimation) than with all 23 features. Note that even-though the result is always superior using only 14 features, the noise is still to take into account (Fig 4). 3. The test error (in plain) and 10-fold cross-validation error (bracketed) for 14 and 23 features at different embedding rates.

N11 g -1 g -2 g -3 g 1 H g 4 g 0 h 21 g -4 N01 B2 h 13 h 12

Weaknesses of Outguess

Feature selection enables to link the nature of the selected features with Outguess v0.2, the steganographic software that has been used [START_REF] Provos | Defending against statistical steganalysis[END_REF] and then to outline its weaknesses. We recall that Outguess embeds information by modifying the least significant bits of the quantised DCT coefficients of a JPEG coded image. In order to prevent easy detection, the algorithm does not embed information into coefficients equal to 0 and 1. Outguess also preserves the global histogram of the DCT coefficients between the original and stego image by correcting statistical deviations.

The selected features presented in Table 2 present strong links with the way the embedding scheme performs:

-The feature N 11 is the first feature selected by the forward algorithm and describes the difference between co-occurrence values for coefficients equal to 1 or -1 on neighbouring blocks. This feature seems to react mainly to the flipping between coefficients -1 and -2 during the embedding. Note also that coefficients -2 and 2 are, after 0 and 1, the most probable DCT coefficients in a given image.

-The second and third selected features are g -1 and g -2 . They represent the dual histogram of coefficients respectively equal to -1 and -2 with respect to their coordinates. Once again, these features concern the same coefficients than previously but only on the first order (histogram).

-We can notice that nearly half of features related to the dual histogram have been selected. Due to symmetry one might think that features g -5 , g -4 , g -3 , g -2 carry respectively the same information than g 5 , g 4 , g 3 , g 2 , consequently it is not surprising that only one in each set has been chosen (with the exception of g -4 and g 4 ).

-Note that it can seem first curious that features g 0 and g 1 have been selected as meaningful features for the classifier because they are not modified by the embedding algorithm. However, these features can have been affected on the stego and cropped image: coefficients equal to 2 or 3 on the stego image can be reduced to 1 or 2 on the cropped image. Another reason can be that feature g 1 can be selected in association with feature g -1 because it has a different behaviour for watermarked images but a similar behaviour for original images.

Obtained results for other steganographic schemes

This feature selection method has also been tested for two other popular steganographic schemes called F5 and Steghide. Our test confirms that it is also possible to use K-NN-based feature selection on Steghide and to select 13 features which provide similar performances. The list of the 13 selected features is given on table 4 and the performances for different embedding rates is given on table 5. However, we have noticed that for the F5 algorithm performing feature selection is not efficient if the ratio of selected features is below 80%. Forward feature selection for F5 selects still 15 features and backward feature selection selects 22 features. The high number of selected features means that nearly each of the initial feature for F5 is significant for the detection process. Such a consideration is not surprising because F5 is the most undetectable of the three analysed steganographic schemes.

N00

g 2 h 22 H g 5 N01 g -2 g -1 h 13 g -5 g 1 g 5 V Table 4. List of the 13 selected features done by the forward algorithm using K-NN for Steghide. Features are ordered according to the forward algorithm. 5. The test error (in plain) and 10-fold cross-validation error (bracketed) for 13 and 23 features at different embedding rates for Steghide algorithm.

Conclusions and Future Works

This paper proposes a methodology to select meaningful features for a given steganographic scheme. Such a selection enables both to increase the knowledge on the weakness of a steganographic algorithm and to reduce its complexity while keeping the classification performances. Our future works will consist in combining input selection techniques with feature scaling in order to increase the performance of the classifiers.

Forward

Fig. 2 .

 2 Fig.2. Feature selection steps : features are first ranked by importance by the K-NN forward algorithm (1), SVMs give then improvement and an accuracy estimation thanks to a bootstrap[START_REF] Dumitrescu | Detection of LSB steganography via sample pair analysis[END_REF]. Features are in the end taken from the best SVM result (3).

Fig. 3 .

 3 Fig.3. The K-NN accuracy using the forward algorithm.

Fig. 4 .

 4 Fig.[START_REF] Lyu | Detecting hidden message using higher-order statistics and support vector machine[END_REF]. The SVM accuracy using the result of the K-NN forward. The vertical segments show the noise estimation obtained using the bootstrap technique. Crosses present the results of K-NN on 10 sets of 14 features randomly selected.

Table 1 .

 1 . ||,g 1 /||g 1 ||,g 2 /||g 2 ||,g 3 /||g 3 ||,g 4 /||g 4 ||,g 5 /||g 5 || List of the 23 used features.

	Functional/Feature name Functional F
	Global histogram	H/||H||
	Individual histogram for h 21 /||h 21 ||,h 12 /||h 12 ||,h 13 /||h 13 ||,
	5 DCT Modes	h 22 /||h 22 ||,h 31 /||h 31 ||
	Dual histogram for 11	g -5 /||g -5 ||,g -4 /||g -4 ||,g -3 /||g -3 ||,g -2 /||g -2 ||,g -1 /||g -1 ||,
	DCT values (-5, . . . , 5) g 0 /||g 0 Variation V
	L1 and L2 blockiness	B1, B2
	Co-occurrence	N00, N01, N11

Table 2 .

 2 List of the selected features done by the forward algorithm using K-NN. Feature are ordered according to the forward algorithm.

	Embedding rate	14 features	23 features
	10%	72.0% (71.9%)	71.9% (72.3%)
	25%	88.0% (92.9%)	87.2% (93.1%)
	50%	97.8% (99.3%)	97.0% (99.2%)
	75%	99.2% (99.7%)	98.0% (99.8%)
	Table