基于超混沌序列的數(shù)據(jù)庫零水印算法

歐陽苗

(廈門理工學(xué)院應(yīng)用數(shù)學(xué)學(xué)院，福建 廈門 361000)

0 引言

數(shù)字水印技術(shù)通過在不被察覺的條件下將版權(quán)等特定信息加密隱藏在要發(fā)布的數(shù)字媒體中，實(shí)現(xiàn)信息的隱秘傳送或版權(quán)保護(hù)。在外包數(shù)據(jù)庫服務(wù)模式中，由于數(shù)據(jù)庫服務(wù)器由第三方提供，物理文件可能輕易地遭到復(fù)制，故而需要對(duì)數(shù)據(jù)庫的版權(quán)進(jìn)行保護(hù)。S.Khanna等于2000年提出利用數(shù)字水印控制數(shù)據(jù)庫安全的方法[1]，開啟了數(shù)據(jù)庫水印技術(shù)的探索之門。兩年后，R.Agrawal等人在美國(guó)國(guó)家科學(xué)基金會(huì)技術(shù)資助下，提出在數(shù)據(jù)庫的數(shù)值屬性最低有效位嵌入水印的算法[2]，R.sion等提出了通過構(gòu)造項(xiàng)目集合嵌入有實(shí)際意義水印的方案[3]，也帶動(dòng)我國(guó)學(xué)者開始了相關(guān)研究[4-6]。

與一般多媒體數(shù)據(jù)庫對(duì)比，關(guān)系數(shù)據(jù)庫水印在以下幾方面有顯著差異，如表1所示。

表1 關(guān)系數(shù)據(jù)庫與多媒體數(shù)據(jù)庫的區(qū)別

首先，現(xiàn)有的數(shù)據(jù)庫水印方案的水印容量小，水印的魯棒性很難達(dá)到要求;為此，本文引入零水印數(shù)據(jù)庫。其次，現(xiàn)有水印方案未考慮如何篩選嵌入水印的數(shù)據(jù)項(xiàng);事實(shí)上，數(shù)據(jù)項(xiàng)篩選在隨機(jī)性、離散性、安全性上的不同會(huì)給后續(xù)各項(xiàng)流程帶來類似蝴蝶效應(yīng)的差異，本文將超混沌系統(tǒng)引入數(shù)據(jù)項(xiàng)篩選，旨在改良水印的魯棒性。再者，現(xiàn)有算法傾向選取MSB(Most Significant Bit)或LSB(Least Significant Bit)上的數(shù)據(jù)構(gòu)造水印，然而關(guān)系數(shù)據(jù)庫的屬性值域不相同的居多，不相同的數(shù)值型字段有效位數(shù)也不盡相同;因此，考慮到對(duì)不同的冗余空間，可以將重要比特位做更細(xì)致的分區(qū)，按需要從中選取數(shù)據(jù)來增強(qiáng)水印方案的魯棒性和安全性。

1 基于混沌變換的零水印構(gòu)造

1.1 基于混沌變換的數(shù)據(jù)項(xiàng)篩選

篩選前，先采用哈希函數(shù)SHA-1(Secure Hash Algorithm)為數(shù)據(jù)項(xiàng)進(jìn)行標(biāo)記:

利用屬性標(biāo)記密鑰key來計(jì)算每一條數(shù)值屬性的hash值，ωj∈[ω1，ω2]作為這條數(shù)值屬性的標(biāo)記值。r.p為屬性所在記錄的主鍵，zm為屬性名稱，Ai為數(shù)值屬性的值。

(1)生成混沌序列

混沌變換有確定性、遍歷性、偽隨機(jī)性、初值敏感性等特性，借助混沌序列篩選出的數(shù)據(jù)項(xiàng)不依賴于其他的元組，呈離散的分布狀態(tài)，增強(qiáng)了水印的魯棒性、安全性。這里用Logistic函數(shù)生成混沌序列，

0≤μ≤4稱為分支參數(shù)，Xi∈(0，1)。在3.5699457≤μ≤4時(shí)(2)式進(jìn)入混沌狀態(tài)，初值 X0，經(jīng)過 n次迭代，產(chǎn)生長(zhǎng)度為n的一維混沌序列{Xi|i=1，2，…，n}。

(2)線性變換

由線性函數(shù)

把混沌序列{Xi|i=1，2，…，n}約束到 ωi的取值范圍[ω1，ω2]內(nèi)，得到集合 ω':{ωi'|i=1，2，…，n}。

(3)判定標(biāo)記值是否存在

從集合ω'中取得ωi'，從數(shù)值屬性標(biāo)記值集合ω中取得的ωj，將ωi'與ωj依次判斷是否相等，相等則提取標(biāo)記值ωj，表明該數(shù)據(jù)項(xiàng)被選中;不相等，則取下一個(gè)i=i+1，進(jìn)行判斷。通常我們可以增大生成的混沌序列數(shù)據(jù)項(xiàng)，用來篩選出滿足待提取水印位數(shù)的數(shù)據(jù)項(xiàng)。

1.2 不同比特位數(shù)值的提取

現(xiàn)有數(shù)據(jù)庫零水印方案通過提取數(shù)值屬性值的最高有效位的最高比特位來構(gòu)造零水印[7]，這樣產(chǎn)生的水印魯棒性不高。畢竟數(shù)據(jù)特征權(quán)重長(zhǎng)度FWL越大，F(xiàn)SB(第一重要比特位)越能代表數(shù)據(jù)的特征，然而FWL越小，F(xiàn)SB和TSB(第二、三重要比特位)對(duì)于數(shù)據(jù)所代表的特征性越接近，因此可以用TSB代替FSB提取零水印，并不會(huì)降低水印質(zhì)量。

(1)數(shù)據(jù)分類

利用篩選出的數(shù)據(jù)項(xiàng)數(shù)值確定分類長(zhǎng)度L1，L2(L1＞L2)。L1為篩選出的數(shù)據(jù)項(xiàng)數(shù)值特征權(quán)重長(zhǎng)度均值:

L2為篩選出的數(shù)據(jù)項(xiàng)數(shù)值小于0的特征權(quán)重長(zhǎng)度均值(m為特征權(quán)重長(zhǎng)度小于0的數(shù)據(jù)項(xiàng)個(gè)數(shù)):

找出篩選出的數(shù)據(jù)項(xiàng)按ρ的長(zhǎng)度與L1，L2(L2＜L1)的大小關(guān)系，依表2所示確定提取水印的位置。

表2 篩選出的數(shù)據(jù)項(xiàng)類型及對(duì)應(yīng)提取水印位置

(2)提取初始水印

分別對(duì)不同類屬的數(shù)據(jù)進(jìn)行相應(yīng)比特位的提取，作為初始水印序列ω':{ωi'|i=1，2，…，n}。

1.3 混沌置亂

依照?qǐng)D1提取了初始序列信息后，引入二維超混沌變換系統(tǒng)，將其混沌置亂。

圖1 提取不同比特位處理流程

(1)混沌序列的生成

從實(shí)際需要出發(fā)，將二維偽隨機(jī)序列進(jìn)行降維，給定初值(x0，y0)生成一維超混沌偽隨機(jī)序列{Lp|p=1，2，…，n}。

(2)初始序列的置亂

得到{Lp|p=1，2，…，n}后，將1.2中提取出來的初始序列通過混沌系列置亂處理。生成的混沌序列與初始的水印序列{ωi'|i=1，2，…，n}通過下標(biāo)對(duì)應(yīng)起來，將Lp排序(冒泡法)，即將混沌序列Lp按大小順序排列好，同時(shí)依照使ωi'的下標(biāo)排列順序與Lp下標(biāo)順序相同的規(guī)律調(diào)整ωi'。

1.4 零水印的生成

零水印的性能測(cè)度一般關(guān)注兩個(gè)指標(biāo):峰值信噪比和歸一化互相關(guān)系數(shù)[8]。為計(jì)算零水印的相似度，需要對(duì)其作轉(zhuǎn)換，通過映射:

提取的初始序列轉(zhuǎn)換成后續(xù)待用的零水印。

2 基于混沌變換的零水印檢測(cè)

當(dāng)版權(quán)糾紛發(fā)生時(shí)，我們需要檢測(cè)發(fā)生糾紛的數(shù)據(jù)庫。它包含從ZWMC[7](Zero-watermarking Manage Center)中獲取、重構(gòu)零水印，以及相關(guān)性計(jì)算;其中零水印的重構(gòu)算法優(yōu)劣直接關(guān)系到水印的構(gòu)造、嵌入、獲取之后能否被檢測(cè)出來，是研究重點(diǎn)。

2.1 零水印證書的獲取

零水印證書由ZWMC[7]通過數(shù)字簽名和加密技術(shù)頒發(fā)，記錄了版權(quán)所有者信息以及注冊(cè)的零水印信息，因此零水印檢測(cè)過程需要零水印證書作依據(jù)，文獻(xiàn)[9]詳細(xì)記載了獲得過程，這里從零水印重構(gòu)開始。

2.2 重構(gòu)零水印

水印的檢測(cè)會(huì)使得原始數(shù)據(jù)庫發(fā)生改變，甚至某些屬性值也遭到刪改。重構(gòu)過程可以采用提取初始水印之前的構(gòu)造過程，因此主要討論提取了初始水印之后的環(huán)節(jié)。

(1)提取初始水印

標(biāo)記待提取的數(shù)據(jù)項(xiàng)并保存在數(shù)組team中，標(biāo)記重構(gòu)過程中篩選的數(shù)據(jù)項(xiàng)并存在數(shù)組team’中，提取初始序列的過程如圖2所示，算法流程圖如圖3所示。

圖2 重構(gòu)時(shí)提取初始水印過程

圖3 重構(gòu)時(shí)提取初始水印處理流程

比較集合team’與集合team，若team’內(nèi)的標(biāo)記已經(jīng)存在于在team中，則取數(shù)值不同比特位來生成初始水印;若team’中的標(biāo)記不存在于team中，說明篩選的標(biāo)記沒在原數(shù)據(jù)項(xiàng)標(biāo)記集合中，為了便于計(jì)算最后零水印相似度，我們用“－1”代替提取的初始序列值。

(2)混沌置亂和相關(guān)轉(zhuǎn)換

接著利用構(gòu)造時(shí)的混沌系統(tǒng)與初值混沌置亂初始水印，進(jìn)行重排。由于重排過的水印序列會(huì)出現(xiàn)“－1”，“1”，“0”，而提取時(shí)初始序列只包含“1”，“0”，故將置亂后的序列再按下式轉(zhuǎn)化，以便利用相關(guān)性計(jì)算公式計(jì)算水印的相似度:

(7)與(6)中的轉(zhuǎn)換本質(zhì)相似，唯一區(qū)別在于“－1”到“0”的轉(zhuǎn)換。重構(gòu)水印提取的初始序列中包含“－1”，說明有一位的零水印沒有被檢測(cè)出來;對(duì)應(yīng)這位零水印的數(shù)值屬性可能遭到刪改，于是在檢測(cè)過程中用“0”表示。

2.3 相關(guān)性計(jì)算

相關(guān)性計(jì)算是判斷版權(quán)歸屬的重要方法，通常將從版權(quán)糾紛的數(shù)據(jù)庫中重構(gòu)出的零水印與從ZWMC中獲取的零水印比對(duì)給定的閾值，來確定版權(quán)歸屬。

其中W'和W″分別表示注冊(cè)的零水印和檢測(cè)時(shí)重構(gòu)的零水印。理論上，閾值的確定應(yīng)經(jīng)過盡可能多的實(shí)驗(yàn)來觀測(cè)，筆者做的實(shí)驗(yàn)數(shù)量上顯然不夠;考慮到原始數(shù)據(jù)庫提取出的水印為二值序列，它們將以0.5的概率完全匹配，可以粗略的預(yù)期計(jì)算得出的η也應(yīng)在0.5左右。若相關(guān)性檢測(cè)的結(jié)果大于0.5時(shí)，認(rèn)定含有指定水印。

3 實(shí)驗(yàn)結(jié)果與分析

最常見的三種數(shù)據(jù)庫水印攻擊為:子集增加攻擊、子集更改攻擊和子集刪除攻擊。以下實(shí)驗(yàn)分析針對(duì)這三種攻擊展開，不失一般性，選取閾值π=0.5，水印序列長(zhǎng)度N=100。

3.1 子集增加攻擊

我們?cè)?000條實(shí)驗(yàn)記錄數(shù)據(jù)的基礎(chǔ)上依次增大添加比例模擬攻擊，給出本文算法對(duì)比文獻(xiàn)[10]算法的子集增加攻擊值曲線圖，如圖4所示。

待構(gòu)造水印的數(shù)據(jù)項(xiàng)由二維超混沌序列篩選產(chǎn)生，因此有效的抵抗了元組重排，減弱通過加入元組對(duì)重構(gòu)水印的影響。從圖4中可以看出η在增加比例不超過80%時(shí)，都能檢測(cè)出水印信息。而文獻(xiàn)[10]的方法則不能有效的抵抗子集增加攻擊的影響。當(dāng)增加比例到達(dá)30%時(shí)，η為0.57，而且隨著增加比例的上升，η的衰減速度很快。實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)子集增加攻擊的抵抗性更好。

3.2 子集更改攻擊

顯然對(duì)數(shù)據(jù)庫數(shù)據(jù)更改比例越大，攻擊越顯著，但同時(shí)破壞程度也越大。現(xiàn)實(shí)情況中，過多的對(duì)數(shù)據(jù)施加更改攻擊將導(dǎo)致盜用者得到的數(shù)據(jù)庫價(jià)值大大降低，一般更改比例不高于整個(gè)數(shù)據(jù)比例的40%。

本組實(shí)驗(yàn)選取全部數(shù)據(jù)中按比例進(jìn)行隨機(jī)的抽取后，更改其屬性值;依次增大更改比例，以觀察隨著更改比例的加大，驗(yàn)證水印算法的抗攻擊能力變化并計(jì)算相應(yīng)的相似度。

如圖5所示，攻擊比例高達(dá)40%時(shí)，η為0.55，依然可以檢測(cè)出零水印的存在，不難看出，本文算法對(duì)更改攻擊表現(xiàn)出較好的抗攻擊性。

圖4 子集增加攻擊

圖5 子集更改攻擊

3.3 子集刪除攻擊

子集刪除分三種情形處理:數(shù)據(jù)庫首刪除，數(shù)據(jù)庫尾刪除、隨機(jī)刪除，結(jié)果如圖6所示。

圖6 子集刪除三種攻擊

實(shí)驗(yàn)表明:從首部刪除比例達(dá)到45%時(shí)，從尾部刪除比例達(dá)到50%時(shí)，隨機(jī)刪除比例達(dá)到60%時(shí)，仍能檢測(cè)出水印的存在。

對(duì)關(guān)系數(shù)據(jù)進(jìn)行子集刪除攻擊實(shí)驗(yàn)時(shí)，水印信息隨著刪除比例的加大而減弱，但這三類攻擊下的水印檢測(cè)指數(shù)η的曲線比較接近，說明了嵌入水印的位置與數(shù)據(jù)前后順序關(guān)系不大。隨機(jī)刪除攻擊的抵抗效果好于首、尾大塊刪除的抵抗效果，因?yàn)闃?gòu)造水印時(shí)篩選過數(shù)據(jù)項(xiàng)，使得水印信息均勻分布開，因此隨機(jī)刪除時(shí)大比例丟失水印信息的概率減小了;相對(duì)而言，無論從首部還是尾部開始的大塊刪除則使水印數(shù)據(jù)丟失比例偏高。

綜上所述，本文算法的魯棒性能較好，即使數(shù)據(jù)刪除比例達(dá)到40%，水印相似度依然在55% ～63%之間。

4 結(jié)束語

本文設(shè)計(jì)了一種基于混沌變換的數(shù)據(jù)庫零水印模型:把混沌變換引入數(shù)據(jù)庫零水印構(gòu)造或檢測(cè)過程中，借助混沌序列篩選待構(gòu)造水印的數(shù)據(jù)項(xiàng)。在不同數(shù)據(jù)項(xiàng)冗余空間嵌入水印，通過分析數(shù)值型數(shù)據(jù)項(xiàng)有效位，依據(jù)特征權(quán)重均值對(duì)數(shù)據(jù)項(xiàng)進(jìn)行分類，提取不同比特位生成水印。實(shí)驗(yàn)結(jié)果表明本方案算法對(duì)添加攻擊、刪除攻擊、更改攻擊顯示出較強(qiáng)的抗攻擊性。

[1]Hakan Hacigumus，Bala Iyer，Shared Mehrotra.Providing Database as a Service[C].Proc of ICDE，2002.

[2]Sanjeev Khatma，F(xiàn)rancis Zane.Watermarking maps hiding information in structured data[C].SODA，2000:596-605.

[3]Sion R.Proving ownership over categorical data[C].Proceedings of IEEE International Conference on Data Engineering，2004:584-596.

[4]黃敏，張浩，黃加恒.一種基于數(shù)據(jù)庫的水印技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(10):153-156.

[5]姜傳勝，孫星明，易葉青，等.基于JADE算法的數(shù)據(jù)庫公開水印算法的研究[J].系統(tǒng)仿真學(xué)報(bào)，2006，18(7):1781-1784.

[6]彭沛夫，林亞平，張桂芳，等.基于有效位的數(shù)據(jù)庫的數(shù)字水印[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(11):166-168.

[7]蒙應(yīng)杰，吳超，蘇仕平，等.一種關(guān)系數(shù)據(jù)庫零水印方案的探討[C].中國(guó)第22屆數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集，2005.

[8]張桂芳，孫星明，肖湘蓉.基于中國(guó)剩余定理的數(shù)據(jù)庫水印技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(7):135-137.

[9]蒙應(yīng)杰，吳超，張文，等.數(shù)據(jù)庫零水印注冊(cè)方案的研究[J].計(jì)算機(jī)工程，2007，33(2):133-135.

[10]蒙應(yīng)杰，吳超.關(guān)系數(shù)據(jù)庫零水印的構(gòu)造算法[J].蘭州大學(xué)學(xué)報(bào):自然科學(xué)版，2007，43(6):51-55.

[11]李帥，王衛(wèi)星.基于超混沌迭代的雙重零水印算法[J].計(jì)算機(jī)工程，2008，34(17):158-161.

[12]王麗娜，司穎，季稱利.基于數(shù)字簽名的安全零水印方案[J].計(jì)算機(jī)科學(xué)學(xué)報(bào)，2010，37(7):55-56.