A Channel Model for a Watermark Attack

Jan. 1999, pp. 159-170.

A Channel Model for a Watermark Attack Jonathan K. Su, Frank Hartung, and Bernd Girod Telecommunications Institute I University of Erlangen-Nuremberg Cauerstrasse 7, D-91058 Erlangen, Germany

ABSTRACT

Digital watermarking of multimedia (e.g., audio, images, video, etc.) can be viewed as a communications problem

in which the watermark must be transmitted and received through a \watermark channel." The watermark channel includes distortions resulting from attacks and may include interference from the original digital data. Most current techniques for embedding digital watermarks in multimedia (e.g., audio, images, video, etc.) are based on spread spectrum (SS), although the connection is not always explicit. Current analyses of the watermarking channel are typically limited to the additive white Gaussian noise (AWGN) channel. However, new channel distortions not considered in classical SS are now possible. This paper describes several such manipulations and focuses on signal re-indexing (i.e., re-ordering of samples). The re-indexing channel is shown to behave like a linear lter on average, and the optimal detector, which has linear complexity, is derived. The channel is studied further for the case of spatial direct-sequence SS watermarks. For the conventional detector, it can yield a probability of bit error (PE ) of 0.5, the worst possible case. A linear pre lter or the optimal (maximum-likelihood) can be used for resynchronization and reduction of PE . Both methods are analyzed and compared with experimental results. These results include both synthetic data and standard test images and video. Keywords: Digital watermarking, watermark attacks, spread-spectrum communications

1. INTRODUCTION

Digital multimedia documents (e.g., digital audio, images, video, etc.) can be stored, copied, and distributed easily, rapidly, and losslessly. They can also be altered with complete control over the modi cations. These properties are generally considered to be advantageous, but they also create diculty in protecting intellectual property rights (IPR). Owners of multimedia need to be able to protect them against illegal duplication, distribution, and other unauthorized usage. Digital watermarking has been proposed as a means to help protect IPR.1{3 We highlight the key ideas brie y below. In digital watermarking, a signal (the watermark) is embedded directly into a document. The watermark may convey information such as the document's owner, origin, intended destination, and time of distribution. A watermark should usually possess the three following properties. Imperceptibility : after embedding, the watermarked document should remain perceptually equivalent to the original; Robustness : given a watermarked document, an unauthorized party should not be able to destroy the watermark without also making the document useless. Security : Only authorized parties should be able to detect, recover, and possibly modify the watermark. Additional properties include fast embedding and/or recovery, the ability to embed multiple watermarks, and the ability to recover the watermark without reference to the original, unmarked document. The importance of the dierent properties depends upon the intended application area.

1.1. Abstract Communications Models

Digital watermarking can be viewed as a communications problem.3{5 A message (information to be embedded) is converted into a signal (the watermark), which is then sent through a channel to the receiver. The receiver must locate the watermark signal and attempt to recover the message from it. We refer to the channel as the watermarking channel to distinguish it from a conventional broadcast channel. Further author information: Send correspondence to J. K. Su. E-mail: [su,hartung,girod]@nt.e-technik.uni-erlangen.de

message (information to embed)

received message

Modulator/ Transmitter

Demodulator/ Receiver

watermark (signal to embed)

original document

+ +

marked document

received document = received signal (watermark and interference)

111111 000000 000000 111111 000000 111111 000000 111111 attacks 000000 111111 000000 111111 000000 111111 000000 111111

Watermark Channel

Figure 1. An abstract communications model for watermarking when the original document is not available during reception. The original document thus behaves like interference in the channel.

An attack is an operation, performed on the watermarked document, that may degrade a watermark and possibly make the watermark unreliably detectable. From a communications viewpoint, even coincidental manipulations| such as lossy compression or cropping|are attacks. Attacks are assumed to occur only in the channel. Attacks can be grouped into dierent categories depending upon how they attempt to defeat a watermarking system.6 \Simple" attacks do not directly target the watermark or watermarking algorithm; they are typically document manipulations that may impair a watermark as a side eect. Examples are lossy compression, linear ltering, and D/A and A/D conversion. \Ambiguity" attacks create confusion about the validity of watermark. For example, the attack may create a fake original document or fake watermark so that the true and fake information cannot be distinguished from one another.7,8 \Detection-disabling" attacks intend to render the watermark unreliably detectable by exploiting weaknesses in the detection mechanisms. An example is the StirMark attack,9 which defeats some image watermarking systems by applying geometric transformations to the marked image. Finally, \removal" attacks explicitly try to erase the watermark. Examples include linear or nonlinear estimators,10,11 which try to estimate and remove the watermark, and collusion attacks,1,12,13 which employ several dierently marked copies of the same original document. Note the dierence between a detection-disabling and a removing attack: a detection-disabling attack makes the watermark harder to detect, but it does not necessarily remove the watermark; a successful removal attack actually erases the watermark, so no amount of processing can recover the watermark from the attacked document. One important consideration in a watermarking system is whether or not the original document is available to the receiver. If not, then the original document behaves like interference and forms part of the channel. If so, the receiver should be able to remove interference from the original. These ideas are summarized in Figs. 1 and 2, depending upon the availability of the original at the receiver.

1.2. Watermarking Channels

It is clear from these abstract models that the performance of a watermarking system depends on the properties of the appropriate watermarking channel. The watermarking channel diers from a traditional, say, radio channel in a number of ways.

message (information to embed)

received message

Demodulator Modulator/ Transmitter

received signal (watermark and interference)

watermark (signal to embed)

original document

+ +

marked document

111111 000000 000000 111111 000000 111111 000000 111111 attacks 000000 111111 000000 111111 000000 111111 000000 111111

+

Receiver

received document

Watermark Channel

Figure 2. An abstract communications model for watermarking when the original document is available during reception. Any interference from the original can conceivably be eliminated at the receiver.

First, it is discrete and may be multidimensional. These dierences, however, do not greatly aect analysis. Second, it may have limited bandwidth, as in watermarking of small images that do not contain a large number of samples.4 Third, the watermarking channel is not necessarily a causal, time-domain transmission channel. This dierence means that a watermarked digital document can be subject to many new eects that are not usually part of a communications channel. Many channel eects, such as compression, can be modeled as linear ltering and/or additive noise. Any 2-D or 3-D ane transformation of a signal can be reversed with only a few reference points,14,1 so many geometric transformations of a watermarked document can be resisted. Some new possible channel eects are: collusion attacks; noncausal linear or nonlinear ltering; deletion, repetition, and insertion of samples; and re-indexing or re-ordering of samples. To the authors' knowledge, most previous studies4,5,15 of the watermarking channel have been restricted to the additive white Gaussian noise (AWGN) channel. This paper concentrates on the new eects caused by re-indexing. Section 2 rst reviews a popular method for watermarking based on spread-spectrum communications and discusses the AWGN channel. Section 3 then describes the re-indexing channel and analyzes its eects. Experiments with simulated data and natural images appear in Sec. 5, followed by conclusions in Sec. 6.

2. DIRECT-SEQUENCE SPREAD-SPECTRUM WATERMARKING

Most current watermarking schemes are forms of spread-spectrum communications, or simply spread spectrum (SS).16{18 A popular form of SS, known as direct-sequence spread spectrum (DSSS), is employed in several watermarking algorithms.1,19 We assume the reader is familiar with DSSS and present a brief review and introduce notation. Boldface indicates random quantities; regular fonts denote deterministic quantities or realizations of random quantities. For this example, we consider a single bit b 2 f,1; +1g of the message. At the transmitter, the bit is repeated N

times, where N is the chip rate. The spreading sequence is a noiselike signal c[n], which has the (ideal) properties NX ,1 n=0

c[n] = 0;

and

NX ,1 n=0

c[n]c[n + k] = N[k];

(1)

where [k] is the Dirac delta function. For security, the spreading sequence is assumed to be produced by a cryptographically secure pseudo-random number generator. We assume that the generator key is known only by authorized parties. p The modulated message forms the watermark w[n] = E=Nbc[n]. The watermark is embedded by adding w[n] to the original document d[n]. The marked document t[n] is thus t[n] = d[n] + w[n]. The receiver is assumed to be synchronized with the transmitter and in possession of the key. Given the received document r[n], the receiver uses a correlation detector or correlator to nd the received bit ^b. The receiver p P N , 1 regenerates c[n] and computes the correlation sum  = n=0 E=Nc[n]r[n]. Next,  is compared to a threshold T. If  > T, the detector assumes ^b = +1; otherwise, the detector returns ^b = ,1.

2.1. Standard Results for the Additive Noise Channel

A standard channel model is the additive noise channel, where r[n] = w[n]+ v[n], and v[n] is a wide-sense stationary (WSS) discrete-time random process (DTRP) that represents channel noise and possibly includes interference from the original document. In the SS literature, this model usually represents a basic jamming attack. Under the AWGN assumption, v[n] becomes a sequence of independent, identically distributed (IID) Gaussian random variables (RVs), each with mean zero and variance v2 =N. The signal-to-noise ratio (SNR) is thus E=v2 . However, it is well-known that the SS receiver enjoys a theoretical SNR advantage of GpE=v2 , where Gp denotes the processing gain and equals the chip rate N in this scenario. The processing gain is achieved by the correlation detector, which has moments E fg = Eb and var() = Ev2 =N, and hence the eective SNR is NE=v2 . The decision threshold is just T= 0,pand, under message bits are equiprobable, the probability  the assumption pthat
Rthe , 1 2 of bit error PE is PE = Q Gp E=v , where Q(x) = 1= 2 x e,y2 =2 dy.

2.2. Robustness and Synchronization

SS is resistant against attacks that are not correlated with the carrier c[n]. Linear ltering and additive noise are thus ineective attacks. Many simple attacks (Sec. 1.1) can be modeled as combinations of linear ltering and additive noise and are also ineective. If a reduced information rate can be tolerated, the chip rate N can be increased to provide a sucient margin of protection against such attacks. On the other hand, SS requires perfect synchronization between the transmitter and receiver.17 Because of the noiselike properties of c[n], the watermark w[n] has a at power spectrum, and therefore the receiver cannot simply look for a peak in the frequency domain as in many other communication schemes. Attacks can thus attempt to defeat SS watermarks by preventing the receiver from synchronizing. Most of these attacks fall into the category of detection-disabling attacks (Sec. 1.1). P ,1 pE=Nc[n]r0[n] has For example, if the receiver receives r0[n] = r[n , n] = w[n , n]+ v[n , n], then 0 = Nn=0 an expected value of zero, and PEP=N0:5. A more sophisticated receiver can use a sliding correlator to re-synchronize ,1 pE=Nc[n , n ]r0[n] for several values of n . For n 6= n , E f0 (n )g = 0; with c[n]. It computes 0 (n0) = n=0 0 0 0 0 however, E f0 (n )g = Eb. When the correlator nds a peak j0 (n0)j  E  0, it has regained synchronization. The eect of the deletion/repetition/insertion (DRI) channel can be modeled as subjecting the watermarked document to several blockwise random shifts. The principle of the sliding correlator can be extended to a multidimensional blockwise sliding correlator (MBSC) to p prevent such attacks.6 For example, the correlator can compute P N 2 0 the blockwise correlation  (n0 ; N1; N2 ) = n=N1 E=Nc[n , n0]r0[n], with 0  N1 < N2  N , 1. This correlator is multidimensional because several parameters (n0 , N1 , and N2 ) must be varied. Re-synchronization is performed by varying n0 , N1 , and N2 until the correlator collects enough re-synchronized blocks to complete the length-N spreading sequence c[n]. Once c[n] has been completed, the detector can determine the received bit ^b.

3. THE RE-INDEXING CHANNEL

The preceding section showed that, for DSSS, a MBSC should be able to detect watermarks sent through a DRI channel. However, if the DRI channel randomly shifts very small blocks (e.g., only a few samples), then the MBSC must also use small blocks. However, as N2 ! N1 +1, the MBSC has increasing diculty because it cannot separate peaks in j0 (n0 ; N1; N2 )j from noise. We now look at a special case of the DRI channel that operates on individual samples (the block size is 1); we call it the re-indexing channel. We transmit the signal t[n] = w[n] + d[n] through the re-indexing channel. The transmitted signal t[n] passes through the re-indexing channel, so that the received signal r[n] = t[n+ m[n]] + v0[n], where v0[n] is noise and m[n] is discussed shortly. Even if d[n] was available at the receiver and no other attacks occurred, subtracting d[n] away from t[n + m[n]] = w[n + m[n]] + d[n + m[n]] would introduce interference v0 [n] = d[n + m[n]] , d[n]. Since we are concerned with recovering w[n], we choose to express r[n] as r[n] = w[n + m[n]] + v[n]; (2) where m[n] is an integer-valued WSS DTRP, and v[n] is a zero-mean WSS DTRP that is independent of m[n]. The noise v[n] accounts for additional attacks and, as mentioned above, possible interference from the original document. We assume that m[n] is a sequence of IID discrete RVs with probability mass function (PMF) pm (m), where m is an integer and pm (m) = 0 for m < ,mb or m > mf . Hence, each sample r[n] is rst selected from one of the samples in w[n] within a neighborhood of size M = (mb + mf + 1) samples around index n. We call this neighborhood the M -neighborhood. Then the noise v[n] is added. We also assume that v[n] is white with underlying probability density function (PDF) fv (v). Observe that E fr[n]g = E fw[n + m[n]]g + E fv[n]g =

mf X

k=,mb

pm (k)w[n + k];

(3)

which means that, on average, re-indexing lter with impulse response g[n] = pm (,n). In the ,ej!
= Pbehaves ,e,j!like
Wa,elinear j!
, where capital letters denote Fourier transforms, and frequency-domain, we have E R m ,
P Pm ej! = mk=f,mb pm (k)e,j!k . This result is similar to the theory of motion-compensating prediction.20 Unfortunately, the output r[n] of the re-indexing channel is nonstationary, so we cannot use power spectral analysis. De ne the intermediate signal w0 [n] = w[n + m[n]]. Then the mean w0 [n] is w0 [n] = E fw0[n]g =

mf X

k=,mb

pm (k)w[n + k];

(4)

which depends upon the index n. Thus, w0 [n] is nonstationary, and r[n] = w0 [n] + v[n] is also nonstationary. The nonstationarity of w0[n] is a subtle point: Because the watermark w[n] is assumed to be deterministic, re-indexing w[n] to form w0 [n] results in w0 [n] being nonstationary. Alternatively, w[n] could be replaced by a DTRP w[n] whose elements are IID; in this case, the re-indexed DTRP w[n + m[n]] would bepstationary. However, for DSSS, we are concerned with synchronizing with a particular spreading sequence w[n] = E=Nc[n].

4. SPREAD-SPECTRUM WATERMARKING AND THE RE-INDEXING CHANNEL

We now consider the eect of the re-indexing channel on spatial DSSS watermarks. We examine three cases: direct correlation detection, pre ltering followed by detection, and optimal (maximum-likelihood (ML)) detection.

4.1. Direct Correlation Detection p For DSSS watermarking, w[n] = E=Nbc[n]. De nePthe intermediate DTRP c0 [n] = c[n + m[n]] so that r[n] = pE=Nb c0[n] + v[n]. The mean of c0 [n] is  0 [n] = mf p (k)c[n + k] and depends upon the index n. The c

k=,mb m

autocovariance function c0 c0 [k; `] = E f(c0 [k] , c0 [k]) (c0 [`] , c0 [`])g is given by

(

if k 6= `; 2 2 p (i)c [k + i] ,  [k]; if k = `: i=,mb m c0

c0 c0 [k; `] = 0; Pmf

(5)

P

Letting c20c0 [k] = mi=f,mb pm (i)c2 [k + i] , 2c0 [k], we write c0 c0 [k; `] = c20 c0 [k][k , `]. Suppose the DSSS receiver is given r[n] and computes the correlation statistic , =

NX ,1 p

NX ,1 p

n=0

n=0

E=Nc[n]r[n] =

E=Nc[n]

p



E=Nbc0[n] + v[n] :

(6)

Then  , the expected value of , is  = (Eb=N) = (Eb=N)

NX ,1

c[n]c0 [n] = (Eb=N)

n=0 mf X

k=,mb

pm (k)

= Ebpm (0):

To nd the variance of , we begin with  ,  =

NX ,1 p n=0

E=Nc[n]

= (Eb=N) It follows that var() = (E=N)2

NX ,1 k=0

c[k]

NX ,1 n=0

NX ,1 `=0

NX ,1 n=0

NX ,1 n=0

c[n]

mf X k=,mb

c[n]c[n + k] = (Eb=N)

p

pm (k)c[n + k] mf X k=,mb



E=Nbc0[n] + v[n] , (Eb=N)

p

c[n] (c0[n] , c0 [n]) + E=N

NX ,1 n=0

c[`]c0c0 [k; `] + Ev2=N = (E=N)2

pm (k)N[k]

NX ,1 n=0

(7)

c[n]c0 [n]

c[n]v[n]:

NX ,1 k=0

c2 [k]c20c0 [k] + Ev2 =N:

(8)

Let us suppose that the spreading sequence c[n] is a realization of a sequence of IID RVs c[n] with PDF fc (c). Let us assume that fc (c), pm (m), and fv (v) are all symmetric. Then we expect that  will have a PDF that is symmetric around  . Applying the Central Limit Theorem,21  is approximately Gaussian for large N. It then becomes possible to predict the false-miss probability  and false-hit probability . In particular, however, if pm (0) = 0, then (7) indicates that the receiver will have PE = 0:5.

4.2. Correlation Detection

Lowpass ltering before detection can counter some of the eects of the re-indexing channel. If the sample c[n] is present in r[n], it may appear with pre ltering at one or more samples in fr[n,mf ], r[n,mf +1], : : : , r[n+mb ]g. An FIR linear lter with impulse response h[n] and support from ,mf to mb will produce an output y[n] = h[n]  r[n], and y[n] will contain c[n]. Conceptually, the idea is that re-indexing may leave c[n] in the M-neighborhood of r[n], p so the lter acts like a net that collects the samples in the M-neighborhood together. Correlating y[n] with E=Nc[n] will then separate c[n] from interference introduced by the channel and lter. To analyze this detector, we have y[n] = h[n]  r[n]. We assume that r[n] = c[n] = 0 for n 62 [0; N , 1] and that h[n] has support from ,hb to hf , where hb  mb and hf > mf . The pre ltered correlation becomes =

NX ,1 n=0

p

p

p

y[n] E=Nc[n] = E=N

= E=N

hf NX ,1,j X j =,hb k=,j

NX ,1 n=0

p

(h[n]  r[n])c[n] = E=N

p

h[j]r[k]c[j + k] = E=N

hf NX ,1 X k=0 j =,hb

hf NX ,1 X n=0 j =,hb

h[j]r[n , j]c[n]

h[j]r[k]c[j + k];

(9)

where we exploited the assumption that r[n] = c[n] = 0, n 62 [0; N , 1]. The mean of the pre ltered correlation statistic is

p

 = E=N

hf NX ,1 X k=0 j =,hb hf NX ,1 X

= (Eb=N) = Eb

h[j]E

mf X

k=0 j =,hb

`=,mb

np

o

E=Nbc0 [k] + v[k] c[j + k] = (Eb=N)

h[j]c[j + k]

mf X `=,mb

pm (`)c[k + `] = (Eb=N)

hf NX ,1 X

mf X

k=0 j =,hb

`=,mb

pm (`)

h[j]c0 [k]c[j + k]

hf X

j =,hb

h[j]

NX ,1 k=0

c[j + k]c[k + `]

pm (`)h[`]:

(10)

A comparison of (7) and (10) shows that using a pre lter can partially compensate for re-indexing when pm (0) = 0. For the variance, we start with  ,  =

Then var() =

hf NX ,1 X k=0 j =,hb 2 NX ,1 ,

hf NX ,1 X k=0 j =,hb

h[j]c[j + k]

h

p

i

h[j]c[j + k] (Eb=N) (c0 [k] , c0 [k]) + E=N v[k] :

hf NX ,1 X k0 =0 j 0=,hb





h[j 0 ]c[j 0 + k0] (E=N)2c0 c0 [k; k0] + (E=N)(v2 =N)[k , k0 ]

3 hf hf X X
4 (E=N)2c20c0 [k] + Ev2=N 2 = h[j]c[j + k] h[j 0 ]c[j 0 + k]5 k=0 j =,hb j 0=,hb 2 0 12 3 h f NX ,1 , 64 (E=N)2c20c0 [k] + Ev2=N 2
@ X h[j]c[j + k]A 75 : =

(11)

j =,hb

k=0

Again, via the Central Limit Theorem,  may be treated as a Gaussian RV when N is large.

4.3. Optimal Detection

The two preceding sections considered the use of a correlation detector with or without pre ltering. However, we can also derive the ML detector for the re-indexing channel. We treat the transmitted bit as a discrete RV b with PMF pb (1) = 0:5. Denote the length-N segments of r[n], m[n], etc., and their realizations r[n],  m[n], etc., by ~ , and vectors ~r, m random vectors ~r, m ~ , respectively. For example, ~r = r[0] r[1]


r[N , 1] T . The notation ~c[~n + m ~ ] indicates the signal segment c[n + m[n]], n = 0, 1, : : : , N , 1. From basic detection theory,22 the ML detector computes the likelihood ratio  (~r), Pr (~r = ~rjb = +1) = Pr (r[n] = r[n]; n = 0; 1; : : : ; N , 1jb = +1) :  (~r) = Pr (12) (~r = ~rjb = ,1) Pr (r[n] = r[n]; n = 0; 1; : : : ; N , 1jb = ,1) Then the detector chooses ^b = ,1 if  (~r) < 1; otherwise, it chooses ^b = +1. For either value of b, we have Pr (~r = ~rjb = b) =

X

m ~ 2

~ =m Pr (~r = ~rjm ~ ; b = b) =

X p

m ~ 2

Pr



~ =m E=Nb~c[~n + m ~ ] + ~v = ~r Pr (m ~ ):

(13)

~ . Since m[n] and v[n] are both white, (13) becomes where is the set of all possible realizations of m Pr (~r = ~rjb = b) =

mf X

k0 =,mb



=



mf  X

p

pm (k0)pv r[0] , E=Nbc[k0]



mf X

kN,1 =,mb mf NY ,1 " X n=0 k=,mb



k1 =,mb

p



pm (k1 )pv r[1] , E=Nbc[1 + k1] 






p

pm (kN ,1 ) pv r[N , 1] , E=Nbc[N , 1 + kN ,1 ]



#

p

pm (k)pv r[n] , E=Nbc[n + k] :

(14)

The important result of (14) is that it can be evaluated with linear complexity in either M or N, with overall complexity O(MN). The complexity is thus the same (within a scale factor) as that for a pre lter with a support of M samples. Therefore, in the case of white noise, we can implement the optimal detector even for large N. It would be a simple matter to make pm (k) and fv (v) dependent upon the index n. As an example, for image watermarking, they could be signal-adaptive to re ect areas of the image that may permit a wider range for reindexing or greater noise masking. In at regions, the support of pm (m) could be increased and the variance v2 =N decreased. In textured regions, both the support of pm (m) and the variance v2 =N could be increased. Near edges, the support of pm (m) might have to be restricted to samples on one side on the edge, but v2 =N might be increased to allow for luminance masking. For simplicity, we do not make pm (m) or fv (v) dependent on n. Let us suppose that v[n] is WGN with mean zero and variance v2 =N for each n. Then

  N ,1 " mf 2 2# p ,
, N=2 Y X 2 Pr (~r = ~rjb = b) = 2v =N pm (k) exp ,N r[n] , E=Nbc[n + k] =2v ; n=0 k=,mb

and the likelihood ratio becomes

mf NY ,1 " X

(~r) =

n=0 k=,mb mf NY ,1 " X n=0 k=,mb

 

p

2

#

 

p

2

# :

pm (k) exp ,N r[n] , E=Nc[n + k] pm (k) exp ,N r[n] + E=Nc[n + k]

=2v2 =2v2

(15)

(16)

Unfortunately, (16) does not reduce further even if we use the log-likelihood function. There does not appear to be a convenient way to compute the false-miss and false-hit probabilities for the optimal detector except via simulation.

4.4. Multidimensional Case

The re-indexing channel model (2) and the above results can be extended to multidimensional signals in a straightforward manner. For 2-D signals, the channel operates as r[n1; n2] = w[n1 + m1 [n1; n2]; n2 + m2[n1 ; n2]]+ v[n1; n2]. Re-indexing is accomplished via the joint DTRPs m1[n1; n2] and m2[n1; n2], which are assumed to be a 2-D sequence of IID integer-valued RVs with joint PMF pm1 ;m2 (m1 ; m2) with support M. Let N denote the support of the 2-D spreading sequence c[n1; n2], and jNj the number of samples in N . For 2-D DSSS, direct extension of the analyses in Secs. 4.1 and 4.2 is possible. The direct correlation detector yields  = Ebpm1 ;m2 (0; 0);

and

var() = (E=N)2

X

(k1 ;k2 )2N

c2 [k1; k2]c20 c0 [k1; k2] + Ev2=jNj:

(17)

For a 2-D FIR pre lter with impulse response h[n1; n2] and support H, we nd  = Eb

X

(k1 ;k2)2M

pm1 ;m2 (k1 ; k2)h[k1; k2];

(18)

Table 1. Probability of bit error PE for various detection schemes for the re-indexing channel. \Pred." refers to

predicted results, assuming  is a Gaussian RV with appropriate mean and variance; \Sim." refers to simulation results (500 simulations for each case). \AWGN" is the AWGN-only channel (no re-indexing) for reference. For the direct detector, the predicted value of PE = 0:5 in all cases. \Direct" employed direct detection. Columns marked \Pre lter" contain predicted or simulated results for pre ltering followed by detection. \Optimal" provides simulated results for ML detection. Chip rate SNR Pred. PE Sim. PE Pred. PE Sim. PE Sim. PE N (dB) AWGN Direct Pre lter Pre lter Optimal 1000 ,25 0.037679 0.488 0.152538 0.158 0.092 " ,30 0.158655 0.506 0.275678 0.278 0.256 " ,35 0.286942 0.492 0.378836 0.394 0.370 5000 ,25 0.000035 0.522 0.010706 0.020 0. " ,30 0.012674 0.510 0.099408 0.112 0.080 " ,35 0.104298 0.534 0.231504 0.260 0.200 10000 ,25 9:36  10,9 0.578 0.000562 0. 0. " ,30 0.000783 0.504 0.034423 0.020 0.016 " ,35 0.037679 0.510 0.152272 0.158 0.088

and

2 0 123 X 6,
X h[j ; j ]c[j + k ; j + k ]A 7 : var() = 4 (E=jNj)2c20c0 [k1; k2] + Ev2=jNj2 @ 1 2 1 1 2 2 5 (k1 ;k2 )2N

(j1;j2 )2H

(19)

The ML detector for the 2-D case just requires the a posteriori probabilities Pr (~r = ~rjb = b). They are found in the same manner as in Sec. 4.3 and are given by

2 3   Y 4 X p Pr (~r = ~rjb = b) = pm ;m (k1; k2)pv r[n1; n2] , E=jNjbc[n1 + k1 ; n2 + k2 ] 5 : (n1;n2 )2N (k1 ;k2 )2M

1

2

(20)

The 2-D ML detector can thus be implemented with complexity O(jMjjNj).

5. EXPERIMENTAL RESULTS

We have conducted several experiments to study the eect of the re-indexing channel. The rst set of experiments employed synthetic data; later experiments were performed on spatial-domain DSSS image watermarks.

5.1. Results for Synthetic Data

In these experiments, the model (2) was simulated. The amplitude E was set to unity, and the AWGN variance v2 =N could be varied to achieve a desired SNR E=v2 . For imperceptibility of the watermark, the SNR should typically be low (below ,25 dB). For each selected chip rate and SNR, 500 simulations performed. All experiments used pm (1) = 0:5 and h[n] = 1=3, jnj  1. Results appear in Table 1. For reference, values of PE for the traditional AWGN-only channel (without re-indexing) are also included. Simulations for the direct detector after re-indexing all produced empirical values of PE near 0.5, as expected. Predicted values of PE for the case of pre ltering treated  as a Gaussian RV with mean and variance given by (10) and (11), respectively. It is evident that pre ltering can improve detection considerably, and experimental results match closely with the predicted values. We cannot predict PE for the optimal detector, but the empirical results show that it performs only slightly better than pre ltering. Finally, even if the receiver employs pre ltering or optimal detection, PE is at least 2 or 3 three times greater than PE for the AWGN-only channel. This result indicates that a spatial DSSS watermarking system may require much greater robustness than predicted by the AWGN-only channel.

Original

Watermarked Attacked Figure 3. Example of a re-indexing attack for a spatial DSSS image watermark.

5.2. Results for Real Images and Video

Direct application of re-indexing (2) to real images can produce visible artifacts that greatly reduce the quality of the attacked image. To preserve image quality, the attack was modi ed, but it still approximately conforms to (2). The attack operates on each pixel t[n1; n2] of the watermarked image separately. It examines the pixels in the 3  3 neighborhood of t[n1; n2]. Let T[n1; n2] denote the set of pixels in this neighborhood, and T 0 [n1; n2] denote T[n1; n2] minus the pixel at t[n1; n2]. If the local variance in T [n1; n2] is small, the area is considered \ at," and the new pixel r[n1; n2] is randomly selected from one of the eight pixels in T 0[n1 ; n2]. Otherwise, the attack uses simple template matching to identify an edge in the neighborhood T [n1; n2] and determines side of the edge where t[n1; n2] lies. Then it chooses r[n1; n2] from the pixels on that side of the edge. Following the re-indexing operation, white Gaussian noise is added to each pixel. This attack was applied to spatial DSSS image watermarks. Note that no error control coding (ECC) was employed because the goal is to test the channel's bit error rate. The detectors used did not have reference to the original image during watermark detection. To remove interference from the original image at the receiver, a simple 3  3 FIR highpass lter was applied before detection (including pre ltering, if any). An example is the 256  256 grayscale Lenna image. Fig. 3 shows enlarged segments from the original, watermarked, and attacked images. The watermark was embedded with amplitude E = 3 and chip rate N = 2000; hence, 32 bits could be embedded. The AWGN had variance v2 =N = 4. The gure demonstrates that the watermarked and original images are almost indistinguishable. The attacked image displays some artifacts, but it is not severely degraded. The image quality could be improved with a more sophisticated version of the same attack. In this example, the direct detector made 12 bit errors. A 3  3 averaging lter (all coecients equal to 1/9) was used as a pre lter before direct detection, but this method resulted in 19 bit errors. Finally, the optimal detector (with pm (m1 ; m2) = 1=9 for m1 , m2 2 f,1, 0, +1g) decoded all bits correctly. The chip rate in this example may be too low to provide adequate robustness against some attacks. However, because of the limited number of pixels in a single image, it is dicult to get an accurate idea of PE from singleimage experiments. (For example, increasing N to 10000 only allows 6 bits to be embedded. In this case, direct detection had 1 bit error, pre ltering produced 2 bit errors, and optimal detection made no errors.)

Table 2. Bit error counts for 40 frames of QCIF YUV Foreman sequence with spatial DSSS watermark and dierent detection schemes after re-indexing attack. Chip rate No. of bits Bit Errors N embedded Direct Pre lter Optimal 10,000 152 71 72 0 50,000 30 25 14 0 100,000 15 13 5 0

Hence, we also conducted experiments on 40 frames of the Foreman QCIF YUV test video sequence, which contains about 1:5  106 pixels (including U and V pixels). Table 2 lists the total bit errors for chip rates N = 10000, 50000, and 100000. The watermark coder used E = 3; the attack used a noise variance v2 =N = 4. Direct detection failed, and pre ltering did little to improve detection, but the optimal detector again suered no bit errors. Even at a chip rate of 100000, detection with pre ltering made 5 bit errors, while the optimal detector made no errors at a chip rate 10 times lower. The results with real images do not coincide exactly with the synthetic data. For example, pre ltering before detection did not always improve PE . Since real images tend to be highly correlated, the assumption in the analysis that v[n] is white, may not hold.

6. CONCLUSIONS

We have pointed out a communications interpretation of watermarking and described watermarking as transmission of a message through a discrete-index watermark channel. We have pointed out ways that the watermark channel diers from a traditional radio channel. Our investigation focused on the re-indexing channel, which re-orders signal samples. We have presented a simple model for the re-indexing channel. The re-indexing channel can cause a spatial DSSS system to lose synchronization, and even a multidimensional blockwise sliding correlator may not be able to re-synchronize. Hence, it is possible for the re-indexing channel to yield PE = 0:5. Pre ltering before correlation detection may be able to compensate for some channel losses, but we have also shown that the optimal (i.e., ML) detector for the re-indexing channel has linear complexity| the same as FIR pre ltering. This analysis extends directly to multiple dimensions. Experiments with synthetic data demonstrated that the re-indexing channel can lead to a PE two or three times greater than that for the conventional AWGN channel. They also con rmed that, while the optimal detector may outperform pre ltering, the reduction in PE is not always large. Next, experiments with actual images and video con rmed that the re-indexing channel can lead to large values of PE in practice. Pre ltering reduced PE somewhat at large chip rates. However, optimal detection correctly decoded all bits in all the simulations.

REFERENCES

1. I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon, \Secure spread spectrum watermarking for multimedia," IEEE Trans. Image Proc. 6(12), pp. 1673{1687, 1997. 2. M. D. Swanson, M. Kobayashi, and A. H. Tew k, \Multimedia data-embedding and watermarking techniques," Proc. IEEE 86, pp. 1064{1087, Jun. 1998. 3. J. K. Su, F. Hartung, and B. Girod, \Digital watermarking of text, image, and video documents," Computers & Graphics 22(6), 1998. 4. J. R. Smith and B. O. Comiskey, \Modulation and information hiding in images," in Proc. First Information Hiding Workshop, Springer-Verlag Lecture Notes in Comp. Sci. 1174, May 1996. 5. J. J. K. O Ruandaidh, W. J. Dowling, and F. M. Boland, \Watermarking digital images for copyright protection," IEE Proc. Vision and Image Sig. Proc. 143, pp. 250{256, 1996. 6. F. Hartung, J. K. Su, and B. Girod, \Spread spectrum watermarking: Malicious attacks and counterattacks," in Security and Watermarking of Multimedia Contents, Proc. SPIE 3657, Jan. 1999. 7. S. Craver, N. Memon, B.-L. Yeo, and M. M. Yeung, \On the invertibility of invisible watermarking techniques," Proc. IEEE ICIP-97 1, pp. 540{543, 1997.

8. W. Zeng and B. Liu, \On resolving rightful ownerships of digital images by invisible watermarks," Proc. IEEE ICIP-97 1, pp. 552{555, 1997. 9. F. Peticolas and M. G. Kuhn, \StirMark 2.3 watermark robustness testing software." available at URL http:// www.cl.cam.ac.uk/~fapp2/watermarking/image watermarking/stirmark/, Oct. 1998. 10. G. C. Langelaar, R. L. Lagendijk, and J. Biemond, \Removing spatial spread spectrum watermarks by nonlinear ltering," EUSIPCO 98 4, pp. 2281{2284, 1998. 11. J. K. Su and B. Girod, \On the imperceptibility and robustness of digital ngerprints." Submitted to IEEE ICMCS 99, 1999. 12. H. S. Stone, \Analysis of attacks of image watermarks with randomized coecients," tech. rep., NEC Research Inst., May 1996. 13. D. Boneh and J. Shaw, \Collusion-secure ngerprinting for digital data," in Advances in Cryptology { Proceedings CRYPTO '95, D. Coppersmith, ed., vol. 963, pp. 452{465, Lecture Notes in Computer Science, Springer, Aug. 1995. 14. O. Faugeras, Three Dimensional Computer Vision: A Geometric Viewpoint, MIT Press, 1993. 15. J. R. Hernandez, F. Perez-Gonzalez, and J. M. Rodrguez, \The impact of channel coding on the performance of spatial watermarking for copyright protection," Proc. IEEE ICASSP 98 0, pp. 0{0, 1998. 16. R. L. Pickholtz, D. L. Schilling, and L. B. Milstein, \Theory of spread spectrum communications | a tutorial," IEEE Trans. Comm. COM-30, pp. 855{884, May 1982. 17. R. C. Dixon, Spread Spectrum Systems, John Wiley & Sons, New York, 2 ed., 1984. 18. P. G. Flikkema, \Spread-spectrum techniques for wireless communications," IEEE Sig. Proc. Magazine 14, pp. 26{36, May 1997. 19. F. Hartung and B. Girod, \Watermarking of uncompressed and compressed video," Signal Processing 66, pp. 283{301, 1998. 20. B. Girod, \The eciency of motion-compensating prediction for hybrid coding of video sequences," IEEE Journal Sel. Areas Comm. SAC-5, pp. 1140{1154, Aug. 1987. 21. A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill, 3 ed., 1991. 22. J. C. Hancock and P. A. Wintz, Signal Detection Theory, McGraw-Hill Book Co., New York, 1966.