基于布谷鳥算法的可逆數(shù)據(jù)庫水印方案

宋 巖 沈泉江 楊洪山

1(國網(wǎng)上海市電力公司電力科學(xué)研究院 上海 200433)2(星環(huán)信息科技(上海)有限公司 上海 200233)

0 引 言

隨著大數(shù)據(jù)等IT技術(shù)的快速發(fā)展，越來越多的個人及企業(yè)將重要數(shù)據(jù)上傳到云端進(jìn)行存儲、傳輸和發(fā)布。不過2016年Facebook發(fā)生的數(shù)據(jù)泄露事件表明，存放在云端的數(shù)據(jù)并沒有用戶所認(rèn)為的安全。在這種關(guān)系型數(shù)據(jù)模式下，授權(quán)用戶可以通過應(yīng)用程序?qū)?shù)據(jù)進(jìn)行訪問和進(jìn)一步使用，但這也面臨一些安全威脅：授權(quán)用戶可以隨意對數(shù)據(jù)庫信息進(jìn)行復(fù)制或修改，甚至可以為牟利將數(shù)據(jù)非法泄露給未授權(quán)用戶。可以看出，防止數(shù)據(jù)的非法共享是數(shù)據(jù)庫安全應(yīng)用面臨的一大關(guān)鍵問題。因此數(shù)據(jù)庫水印技術(shù)被提出。

近期，數(shù)據(jù)庫加密和水印技術(shù)可以對數(shù)據(jù)庫加密并將數(shù)字水印嵌入加密的數(shù)據(jù)庫中，這使驗(yàn)證數(shù)據(jù)的來源與保護(hù)數(shù)據(jù)庫的安全并免受篡改成為可能。數(shù)字水印技術(shù)在提出時主要是針對多媒體數(shù)據(jù)[1-3]；而與一般多媒體數(shù)據(jù)相比，數(shù)據(jù)庫具有低冗余度和低敏感性的特點(diǎn)，這使得在對數(shù)據(jù)庫嵌入水印時，需要考慮減小因嵌入水印造成的失真以及如何保證水印魯棒性的問題。

2000年，Khanna S等率先利用數(shù)據(jù)庫水印解決數(shù)據(jù)庫安全問題的思路。2002年文獻(xiàn)[4]提出了首個用于關(guān)系數(shù)據(jù)庫的數(shù)字水印方案。根據(jù)使用目的分類，數(shù)字水印可以分為魯棒性數(shù)字水印和脆弱性數(shù)字水印。脆弱性水印是指對數(shù)據(jù)庫進(jìn)行的微小改動會破壞水印，這類水印主要用于保證數(shù)據(jù)未被攻擊者篡改；而魯棒性水印則保證在大幅度修改數(shù)據(jù)庫信息時，依然可以通過水印提取方法從數(shù)據(jù)庫中提取出原始水印，這類水印通常被用于證明數(shù)據(jù)來源及版權(quán)。

目前，傳統(tǒng)數(shù)據(jù)庫水印方法大多會隨機(jī)選擇嵌入水印的位置，這種方式雖操作直接且簡便，但插入的水印可能會造成原始屬性值的失真(超出原本值的范圍)。將尋找嵌入水印的位置轉(zhuǎn)化為一項(xiàng)優(yōu)化求解問題，尋找插入水印的最佳位置成為一項(xiàng)廣泛研究的問題，但大多數(shù)方法仍無法避免數(shù)據(jù)失真與計(jì)算速度較慢的問題。

差分水印拓展技術(shù)是一種將水印嵌入到數(shù)據(jù)差值中的方法，相比于其他嵌入水印的方法，這種技術(shù)最大的優(yōu)點(diǎn)在于，在水印被提取出后仍可以無失真地恢復(fù)出原始數(shù)據(jù)庫；即只要數(shù)據(jù)庫傳送到合法用戶，用戶在使用時無須考慮失真對于使用數(shù)據(jù)所造成的影響。但如果對數(shù)據(jù)不加選擇地使用差分拓展技術(shù)，會使得插入水印后的值與原始值相差過大甚至超過本屬性值所允許的范圍。例如，電網(wǎng)頻率通常保持在50 Hz±0.2 Hz，但如果對這一數(shù)值嵌入水印，可能會使得頻率遠(yuǎn)超合法的波動范圍，變?yōu)?0 Hz甚至70 Hz，攻擊者可以很容易判別出這一位置的數(shù)據(jù)插入了水印，進(jìn)而摧毀或查看水印信息，甚至可以將水印替換成其他內(nèi)容，通過這種方式嵌入的水印顯然是不安全的。因此，在嵌入水印時應(yīng)當(dāng)選擇合適的位置嵌入水印，使得嵌入水印后的值與原始值相差較小(失真較小)；除減小失真外，也需要考慮水印的容量。差分拓展每次只能嵌入一個比特位的數(shù)值(0或1)，這就需要盡可能多地尋找可以嵌入水印的位置，但同時還需考慮數(shù)據(jù)實(shí)時傳輸?shù)囊螅瑴p少尋找嵌入水印位置所花費(fèi)的時間。因此，需要能高效尋找適合嵌入水印位置的算法。

本文基于布谷鳥搜索算法和差分拓展技術(shù)提出一種新的嵌入可逆水印的方案：首先通過哈希算法將數(shù)據(jù)依據(jù)元組的主鍵和屬性的名稱重新排序；然后通過布谷鳥算法尋找最適合插入水印的位置；最后，通過差分拓展技術(shù)在尋找到的最佳位置上打入水印。

基于此，本文的數(shù)據(jù)庫水印方案可有效抵抗針對數(shù)據(jù)屬性或數(shù)據(jù)元組的排序攻擊，并且在位置尋優(yōu)過程中具有較快的收斂速度。為了驗(yàn)證本文方案的效率，在一個森林覆蓋類型數(shù)據(jù)集對這一方法進(jìn)行了實(shí)驗(yàn)，并比較不同規(guī)模的數(shù)據(jù)庫嵌入水印時，花費(fèi)時間和造成數(shù)據(jù)失真的變化。

1 相關(guān)研究

Khanna S等率先提出利用數(shù)據(jù)庫水印完成安全控制的思路并開啟本領(lǐng)域研究。在此基礎(chǔ)上，文獻(xiàn)[4]提出了首個可用于關(guān)系數(shù)據(jù)的數(shù)字水印方案。

在此之后，研究者們針對關(guān)系數(shù)據(jù)無序、數(shù)據(jù)冗余小等特點(diǎn)，提出了一系列適合關(guān)系數(shù)據(jù)的數(shù)字水印方案，主要分為針對水印嵌入技術(shù)的研究、針對水印嵌入算法的研究，以及針對嵌入水印信息的研究。

針對水印嵌入算法的研究主要包括：Kiernan等[5]提出了針對關(guān)系數(shù)據(jù)庫，通過MAC碼來選擇待嵌入水印元組和屬性位置，通過LSB技術(shù)嵌入水印的方法。Sion等[6]在此基礎(chǔ)上提出了一種按照標(biāo)準(zhǔn)化值的最高位排序元組，然后在MAC能夠整除m的元組中，通過修改接近標(biāo)準(zhǔn)偏差邊界的元組值來嵌入水印的方法。Shehab等[7]基于基因算法，首次將嵌入數(shù)字水印位置轉(zhuǎn)化為優(yōu)化問題，他們的方案減小了嵌入水印后造成的數(shù)據(jù)失真。Iftikhar等[8]基于信息概念提出了新的選擇水印嵌入位置依據(jù)的方案。Imamoglu等[9]使用螢火蟲算法在關(guān)系數(shù)據(jù)中選擇嵌入水印的最佳位置,基于差分拓展技術(shù)實(shí)現(xiàn)水印嵌入和數(shù)據(jù)恢復(fù)。

針對水印嵌入算法的研究包括：Zhang等[10]首次提出了基于屬性差值構(gòu)建直方圖的可逆數(shù)據(jù)庫水印方案。同年,針對關(guān)系數(shù)據(jù)庫，張勇等[11]提出了基于異或運(yùn)算的可逆水印方案，但該方法并未給出水印檢測算法；Gupta等[12]提出基于差分?jǐn)U展的可逆水印方案，該方法將數(shù)字水印嵌入到不同屬性的插值中完成水印的嵌入和提取；Farfoura等針對關(guān)系數(shù)據(jù)庫提出的BRM方案可插入能夠盲檢測的可逆水印；Chang等[13]提出的BRRW技術(shù)基于直方圖變換實(shí)現(xiàn)了針對關(guān)系數(shù)據(jù)庫插入可逆水印。

針對水印信息的研究包括：Zhang等[14]將圖像轉(zhuǎn)化為二進(jìn)制流作為水印插入到數(shù)值屬性，該方案基于差分拓展技術(shù)實(shí)現(xiàn)水印的可逆提取。文獻(xiàn)[15]將音頻信號混合成水印信息后嵌入到關(guān)系數(shù)據(jù)庫中，完成了水印的嵌入和提取。

2 相關(guān)背景和知識

布谷鳥搜索算法是一種啟發(fā)式的算法，主要用于解決優(yōu)化問題尋找問題的最優(yōu)解；差分拓展水印嵌入技術(shù)是一種可逆的水印嵌入技術(shù)。

2.1 布谷鳥搜索算法

布谷鳥搜索算法是Yang等[16]觀察自然界中布谷鳥借巢產(chǎn)卵的行為提出的，在該算法中，布谷鳥會按照特定的飛行方式尋找適合產(chǎn)卵的鳥巢位置，在本文中即尋找適合嵌入水印的位置。其中，布谷鳥搜索算法在應(yīng)用時需滿足以下三個假設(shè)：

(1) 每只布谷鳥作為一個尋找全局最優(yōu)解的過程，一次只能選擇一個鳥巢作為一組解，即目標(biāo)位置點(diǎn)。

(2) 每次只有最好(目標(biāo)函數(shù)值最優(yōu))的鳥巢作為本次迭代的最優(yōu)解會被保留到下一代。

(3) 可以使用的鳥巢數(shù)量是開始就被確定的，一旦卵被發(fā)現(xiàn)(以0～1間的固定概率p)則重新尋找并建立新窩，即尋找新的目標(biāo)位置點(diǎn)。

因此，基于萊維飛行布谷鳥算法可以給出每次更新鳥巢位置和路徑的更新方式:

式中：?代表點(diǎn)乘運(yùn)算。

2.2 差分?jǐn)U展水印嵌入技術(shù)

差分拓展技術(shù)[17-18]是一種可以在提取出水印后無損恢復(fù)原始數(shù)據(jù)庫的可逆水印技術(shù)。在獲得某一元組的兩個屬性數(shù)值后，可以通過差分拓展技術(shù)修改它們的差值進(jìn)而嵌入水印。假設(shè)某一行需要嵌入水印的數(shù)據(jù)是A1、A2，它們的平均值和插值為：

當(dāng)接收方收到嵌入水印的數(shù)據(jù)后，可以通過如下步驟計(jì)算最終提取水印以及得到原始數(shù)據(jù)：

只要每次插入的水印信息b∈{0,1}便可以在取出水印后無失真地恢復(fù)出原始數(shù)據(jù)庫。

例如，假設(shè)在數(shù)據(jù)庫中需要嵌入的水印的兩個屬性值分別為A1=54、A2=21，需要插入的水印位為1，則嵌入水印的過程如下：

avg=?」=37

通過水印提取算法，可以提取出嵌入的水印并恢復(fù)出原始值，過程如下：

d=54-21=33

從上面的例子可以看出，差分拓展技術(shù)可以將水印以水印位(0或1的值)的形式嵌入到兩個數(shù)值中，但這種方法會改變原始數(shù)據(jù)的值并帶來一定的數(shù)據(jù)失真；通過這一方法，將嵌入水印后的數(shù)據(jù)庫傳輸?shù)娇尚诺牡谌胶螅ㄟ^嵌入水印的逆方法可以提取出水印并恢復(fù)出原始數(shù)據(jù)庫。

3 本文方案

本文提出一種新的可逆數(shù)據(jù)庫水印算法，該算法采用基于布谷鳥產(chǎn)卵的啟發(fā)式搜索算法尋找水印的最佳嵌入位置；之后采用差分拓展算法在原始數(shù)據(jù)庫中加入水印，該算法可以保證水印被提取出之后可以無損地恢復(fù)原數(shù)據(jù)庫。

首先，對于下文所使用的主要變量的符號及其描述進(jìn)行匯總和介紹，具體如表1所示。

表1 變量名及其含義

3.1 水印及數(shù)據(jù)庫預(yù)處理

對數(shù)據(jù)庫插入水印進(jìn)行預(yù)處理，保證算法對重新排列屬性/元組攻擊的魯棒性，預(yù)處理主要包括針對水印的預(yù)處理、針對元組的預(yù)處理，以及針對屬性的預(yù)處理三個部分。

(1) 數(shù)據(jù)水印的預(yù)處理。針對水印的預(yù)處理是因?yàn)椴罘滞卣辜夹g(shù)在嵌入水印時，每次只能嵌入1或0，首先對需要嵌入的水印進(jìn)行處理，將其轉(zhuǎn)化為二進(jìn)制的形式。

(2) 數(shù)據(jù)元組的預(yù)處理。對數(shù)據(jù)元組進(jìn)行重新排序，以此來防范攻擊者針對元組的增加、刪除與重組攻擊。主要方法是對輸入數(shù)據(jù)庫的元組r根據(jù)其主鍵PK分類到Ng個不同的子集，重新排序后x作為元組的索引：

x=H(key|H(key|r.PK))modNg

式中：|代表連接操作；key表示用戶指定的密鑰；H表示一個安全哈希算法(本文采用512比特的SHA-1哈希算法)；r代表輸入數(shù)據(jù)庫的元組,PK代表當(dāng)前元組的主鍵；mod代表取余操作；Ng代表子集總個數(shù)，本文以二進(jìn)制長度描述水印的長度。由此，輸入數(shù)據(jù)庫便被分成與數(shù)據(jù)庫水印長度相同數(shù)量的子集，每個組中將被嵌入水印的一位。例如，對于一個有100個元組的數(shù)據(jù)庫與長度為10的水印，數(shù)據(jù)庫將通過此方法為10個不同的組，每個組包含10個元組，后續(xù)對每個子集使用尋優(yōu)算法并在其中嵌入相應(yīng)的水印位的值。

(3) 數(shù)據(jù)屬性的預(yù)處理。為防范攻擊者針對屬性的刪除攻擊，需要對數(shù)據(jù)屬性進(jìn)行重新排序，其方式是根據(jù)屬性名稱的哈希值對數(shù)據(jù)庫的屬性計(jì)算后進(jìn)行重新排序，屬性名A.name在重新排序后作為插入水印時確定屬性位置的索引y：

y=H(key|H(key|A.name))

后文中使用的輸入數(shù)據(jù)庫與水印均經(jīng)過預(yù)處理，相關(guān)的x、y均為經(jīng)過預(yù)處理后的值。

3.2 改進(jìn)的布谷鳥搜索算法

該模塊使用布谷鳥搜索算法為所選子集DS中的元組選擇嵌入水印信息的最佳屬性對。從預(yù)處理模塊獲取子集作為輸入，并最終輸出所選擇的布谷鳥及其給出的最優(yōu)解即指定嵌入水印的位置(所選元組行的屬性索引)。

3.2.1創(chuàng)建初始種群

該算法使用P只布谷鳥創(chuàng)建初始種群，計(jì)算不同布谷鳥給出解決方案的目標(biāo)函數(shù)值后進(jìn)行排序，算法的主要輸入如下：

1) 待嵌入水印的關(guān)系數(shù)據(jù)庫DS∈(p,A1,A2,…,An),其中:p為DS各元組的主鍵;A1,A2,…,An為DS的n個屬性。DS由m個元組r1,r2,…,rm組成；每個元組都有且僅有一個各不相同的主鍵r.p和n個屬性列r.A1,r.A2,…,r.An。

2) 初始種群數(shù)量表示用于尋找最優(yōu)解的布谷鳥的數(shù)量，此數(shù)值越大，在尋優(yōu)過程中便更容易找到全局最優(yōu)解(或找到更好的局部最優(yōu)解)，但同時需要的算力也越大。

3) 待嵌入水印u=(u1,u2,…,uk)，ui∈{0,1},k≤m。

4) 對于插入水印造成失真的偏好wa與對于水印容量的偏好wc，代表了對于嵌入水印造成失真與水印容量的偏好選擇，wa+wc=1，wa越大則越偏好于選擇對數(shù)據(jù)庫造成失真小的方案，wc越大則代表了偏好于選擇水印容量較大的方案。

在經(jīng)過初始種群算法后的輸出主要如下：

1) 初始種群:F1,F2,…,FP為P只布谷鳥給出的解決方案的合集，其中每個解決方案為一個三維的向量，向量的前兩維代表對于不同元組為嵌入水印信息所選擇的兩個屬性的索引值，第三維代表次元組其嵌入水印后造成的數(shù)據(jù)失真：例如，F(xiàn)1={[2,7,11],[1,5,4]},[1,5,4]}代表對于第一個元組，選擇第2和第7個屬性嵌入水印，造成的失真為11，對于第二個元組，選擇第1和第5個屬性嵌入水印，造成的失真為4。

2) 最佳方案Fbest:記錄所有布谷鳥種，目標(biāo)函數(shù)(fitness值)最小解決方案的水印插入位置信息。

初始種群算法如算法1所示。

算法1初始種群算法

1. forp=1,p

2.mdfp=0,rowp=0

3. fori=1,i

4. [x[p][i],y[p][i]]=random chosed (x,y∈(0,n))

7.rowp=rowp+1

10.fitness(xp,yp)min(fitness)

11.Fbest=[xp,yp,fitness(xp,yp)]

12.F=[x,y,fitness]

變量row用于保存有關(guān)水印容量的信息。步驟9中每個布谷鳥計(jì)算第p個布谷鳥的fitnessp。fitness受兩個因素的影響：屬性的總失真和可以加水印容量。第一個因素是通過計(jì)算屬性mdfp來表示的;第二個因素主要由rowp衡量。這兩個因素的比重由wa和wc確定。步驟10中在生成初始種群中找到fitness最小的方案并記錄其信息為為Fbest。

布谷鳥算法的fitness函數(shù)旨在將嵌入水印之后的失真降到最小值，布谷鳥算法為每個元組選擇嵌入水印的最佳位置，保證在通過差分拓展技術(shù)嵌入水印后對數(shù)據(jù)庫造成的失真影響最小。適應(yīng)度函數(shù)旨在考慮兩個方面：插入水印引起所選屬性的失真和水印的容量。圖1給出了對于一個由9個屬性及2個元組組成的數(shù)據(jù)庫，使用布谷鳥算法基于4只布谷鳥的初始種群過程。

(a) 假設(shè)將要插入水印的數(shù)據(jù)庫

(b) 使用5只布谷鳥給定初始種群

(c) 計(jì)算初始種群解決方案中的屬性值插入水印后的值

(d) 每只布谷鳥解決方案的fitness圖1 初始種群例子

3.2.2確定最佳布谷鳥

在此步驟中，布谷鳥算法計(jì)算在前一階段創(chuàng)建的初始種群的基礎(chǔ)上，對除了給出最優(yōu)(即fitness最小)解決方案布谷鳥外，其他布谷鳥會通過萊維飛行更新獲取新的隨機(jī)位置并重復(fù)這一過程并保留較優(yōu)的過程，并在算法超過最大迭代次數(shù)或目標(biāo)函數(shù)值滿足閾值要求后，返回最優(yōu)的解決方案作為結(jié)果。該算法的輸入包括:

1) 原始關(guān)系數(shù)據(jù)庫DS。

2) 初始種群F。

3) 最佳方案Fbest。

4) 迭代次數(shù)epoch:算法迭代次數(shù)的上限，當(dāng)?shù)螖?shù)達(dá)到這一值后，返回本輪迭代的最優(yōu)方案，epoch值越大，fitness值則更優(yōu)，但相應(yīng)地也需要更多的算力與時間，如何合理地設(shè)置epoch是平衡算法時間與fitness的關(guān)鍵。

5) 結(jié)束閾值threshold：用于判斷是否已取得滿足問題要求的方案，當(dāng)最優(yōu)方案的fitness小于閾值時，便停止繼續(xù)迭代，返回滿足要求的水印嵌入方案。最終輸出為最佳解決方案Fbest。

種群更新算法如算法2所示。

算法2種群更新算法

1. fort=1,t

2. [newx, newy]=Cuckoo Search(x,y)

3. forp=1,p

4. fori=1,i

5. ifmdf(newx[p][i], newy[p][i])

6.x[p][i]=newx[p][i],y[p][i]=newy[p][i]

7.fitness[p]=fitness(x[p],y[p])

8. iffitness[p]

9.Fbest=[x[p],y[p],fitness(x[p],y[p])]

10. iffitness[p]

11. returnFbest

12. returnFbest

其中:步驟3中，對P只布谷鳥依次計(jì)算并通過Levy飛行更新其值；步驟4-步驟9對比Levy飛行后各位置值的并保留較優(yōu)值；步驟10-步驟11用于判斷當(dāng)前迭代的最優(yōu)fitness是否已滿足閾值要求。圖2以初始種群中的例子進(jìn)行說明。

(a) 假設(shè)將要插入水印的數(shù)據(jù)庫

(b) 對除了最優(yōu)的其他布谷鳥通過萊維飛行進(jìn)行更新

(c) 計(jì)算更新后的位置插入水印后的值

(d) 計(jì)算每只初始布谷鳥解決方案的fitness圖2 更新種群實(shí)例

3.3 水印嵌入

在水印嵌入階段所使用的差分拓展嵌入技術(shù)是一種可以在提取水印后恢復(fù)原始數(shù)據(jù)庫的方法，但其嵌入水印的效率較低(一次只能嵌入一位0或1)，不加選擇的嵌入水印會給原始數(shù)據(jù)庫帶來較大失真，在3.2節(jié)中使用布谷鳥搜索算法尋找適合的嵌入位置可以避免因嵌入水印造成過大的數(shù)據(jù)失真。

水印嵌入階段需要在原始數(shù)據(jù)庫中，按照在3.2節(jié)中獲得的最佳嵌入位置Fbest分組地嵌入水印。水印嵌入算法原理已經(jīng)在2.2節(jié)進(jìn)行了說明，本節(jié)主要以本問題的情況說明水印具體的嵌入過程：在3.2節(jié)中獲得的Fbest是一個m(原數(shù)據(jù)庫元組數(shù))行、2列的矩陣，其中第i行的2個數(shù)據(jù)表示原始數(shù)據(jù)庫第i個元組中用于嵌入水印屬性列的索引，兩個待嵌入水印的原始數(shù)據(jù)按序與需要被嵌入的一位水印(0或1)一同傳入水印嵌入算法，在嵌入水印后，按序分別替換用于嵌入水印的兩原始數(shù)據(jù)。算法的主要輸入如下：

1) 原始關(guān)系數(shù)據(jù)庫DS。

2) 最佳方案Fbest。

水印嵌入算法的輸出為已經(jīng)嵌入水印的數(shù)據(jù)庫，它會與加密密鑰key以及通過3.1節(jié)屬性名加密后的水印嵌入位置一起傳輸并最后用于提取水印以及恢復(fù)原始數(shù)據(jù)庫。水印嵌入算法如算法3所示。

算法3水印嵌入算法

1. fork=0,k

3. [i,j]=Fbest[k]

其中步驟2將原始數(shù)據(jù)庫進(jìn)行了拷貝，并在拷貝后的數(shù)據(jù)庫中通過改動數(shù)值的方式嵌入水印。

為方便理解，對于嵌入水印算法以及目標(biāo)函數(shù)和數(shù)據(jù)失真的計(jì)算舉例進(jìn)行說明：假設(shè)要在一個具有4個元組、9個屬性的數(shù)據(jù)庫中嵌入兩位水印u：(0，1)。通過3.1節(jié)的預(yù)處理，將4個元組分到了2個子集分別嵌入水印的兩位(第1、第3元組被分到子集1用于嵌入水印的第一位，第2、第4元組被分到子集2用于嵌入水印的第二位)。嵌入水印的過程如圖3所示。

(a) 原始數(shù)據(jù)庫、需要遷入的水印及在3.2節(jié)中選擇的嵌入水印的位置

(b) 嵌入水印后的數(shù)據(jù)庫

(c) 未嵌入水印數(shù)據(jù)庫各屬性的閾值

(d) 各元組能否嵌入水印及水印容量的計(jì)算

圖3 水印嵌入過程實(shí)例

4 實(shí) 驗(yàn)

本節(jié)對本文方案進(jìn)行實(shí)驗(yàn)仿真并對結(jié)果進(jìn)行詳細(xì)分析。實(shí)驗(yàn)環(huán)境為一臺配備Intel core i7-9750H處理器、16 GB DDR4內(nèi)存的計(jì)算機(jī)主機(jī)，操作系統(tǒng)為Windows 10，數(shù)據(jù)庫為Mysql。數(shù)據(jù)集為加利福尼亞大學(xué)的森林覆蓋類型(Forest CoverType dataset，F(xiàn)CT)數(shù)據(jù)集，其中數(shù)據(jù)集包含581 012個元組，由54個屬性組成。因?yàn)閿?shù)據(jù)庫第9個之后的屬性含有大量屬性值為0的元素，對此使用差分水印拓展技術(shù)會將兩個屬性值為0的屬性選作插入水印的最佳位置，從而導(dǎo)致算法有多個全局最優(yōu)解，這對于評估實(shí)驗(yàn)結(jié)果是十分不利的，因此，在實(shí)驗(yàn)過程中僅選取前9個屬性以及前20 000個元組進(jìn)行實(shí)驗(yàn)。本實(shí)驗(yàn)主要分為兩個部分，第一部分主要測試算法中種群數(shù)量、迭代次數(shù)、權(quán)重系數(shù)(wa和wc)對于目標(biāo)函數(shù)中數(shù)據(jù)失真和水印容量大小的影響，并對參數(shù)選擇進(jìn)行優(yōu)化；在第一部分的基礎(chǔ)上，第二部分主要測試算法中種群數(shù)量、迭代次數(shù)、原始數(shù)據(jù)庫元組數(shù)量對于目標(biāo)函數(shù)以及算法運(yùn)行時間的影響，并評價本算法的優(yōu)劣。

4.1 實(shí)驗(yàn)參數(shù)優(yōu)化

數(shù)據(jù)失真與水印容量是衡量數(shù)據(jù)庫水印算法優(yōu)劣的重要標(biāo)準(zhǔn)。因而在本節(jié)中主要研究迭代次數(shù)、種群數(shù)量、權(quán)重系數(shù)(wa和wc)對于數(shù)據(jù)庫失真與水印容量造成的影響。需要特別說明的是，在目標(biāo)函數(shù)中水印容量使用的是不能嵌入水印的元組數(shù)，為避免歧義，在后文中對于水印容量使用好和差進(jìn)行形容。

首先，為了驗(yàn)證算法對于目標(biāo)函數(shù)中數(shù)據(jù)失真度和水印容量的尋優(yōu)情況，設(shè)定數(shù)據(jù)庫元組數(shù)(rows)為5 000，研究不同權(quán)重系數(shù)情況(兩者之和恒為2)下，數(shù)據(jù)庫失真與水印容量隨迭代次數(shù)變化的情況，結(jié)果如圖4所示。

(a)

(b)圖4 水印容量與數(shù)據(jù)失真隨權(quán)重系數(shù)與迭代次數(shù)的變化情況

可以看出，隨著迭代次數(shù)的增大，數(shù)據(jù)失真與水印容量都逐漸收斂，在所測試的幾種情況中，當(dāng)?shù)螖?shù)超過800次之后，結(jié)果都已經(jīng)趨于穩(wěn)定。因此，在后續(xù)的實(shí)驗(yàn)中，設(shè)定最大迭代次數(shù)為1 000，并認(rèn)為此時的結(jié)果已經(jīng)收斂。同時，我們發(fā)現(xiàn)權(quán)重系數(shù)會影響最終收斂的結(jié)果，但圖4中曲線較為集中，難以觀察不同權(quán)重系數(shù)情況下，水印容量及數(shù)據(jù)失真收斂時的情況。因此，在圖4的基礎(chǔ)上，僅記錄最后一次迭代輸出的最終結(jié)果中數(shù)據(jù)失真及水印容量的大小，并記錄這一值隨權(quán)重系數(shù)的變化情況，且為在途中更直觀地反映有多少元組不能嵌入水印以及對于數(shù)據(jù)庫造成的總失真情況，在此實(shí)驗(yàn)中，使用的數(shù)據(jù)失真值為整個數(shù)據(jù)庫水印容量之和(未取平均值)，而水印容量為實(shí)際不能嵌入水印的元組數(shù)(未歸一化)，結(jié)果如圖5所示。

圖5 收斂時數(shù)據(jù)失真與水印容量隨權(quán)重系數(shù)的變化情況

可以看出，在實(shí)驗(yàn)的幾組數(shù)據(jù)中，wa=1可以使數(shù)據(jù)失真在實(shí)驗(yàn)最后獲得最低的數(shù)據(jù)失真，而對于水印容量，wa=1.90及wa=1.99都可以使水印容量達(dá)到最優(yōu)情況，但在wa>1后，水印容量的變化便已經(jīng)很小了，因此在后續(xù)的實(shí)驗(yàn)中，選擇wa=wc=1進(jìn)行實(shí)驗(yàn)。

其次，為了研究問題矩陣的維數(shù)對于問題結(jié)果造成的影響，設(shè)定wa=wc=1，最大迭代次數(shù)為1 000，種群數(shù)量為2，數(shù)據(jù)庫失真與水印容量隨問題矩陣變化的情況如圖6所示。

圖6 收斂時水印容量與數(shù)據(jù)失真隨問題矩陣維數(shù)的變化情況

可以看出，對于水印容量，幾乎很難找到使得收斂時水印容量最佳的數(shù)據(jù)庫維度。但可以發(fā)現(xiàn)，當(dāng)數(shù)據(jù)庫的維度過小時(在本實(shí)驗(yàn)中為1 000時)，數(shù)據(jù)庫水印容量相對較差，這主要是由于允許嵌入水印的范圍較小。對于數(shù)據(jù)失真，雖然在本實(shí)驗(yàn)結(jié)果中，當(dāng)水印容量為6 000時，數(shù)據(jù)失真較小。但多次實(shí)驗(yàn)發(fā)現(xiàn)這一結(jié)論與選擇的元組的值的具體情況有關(guān)。為了測試算法對于不同大小數(shù)據(jù)庫嵌入水印的情況，在后續(xù)的實(shí)驗(yàn)中分別選取5 000、10 000、15 000、20 000個元組嵌入水印。

最后，為了研究種群數(shù)量對于實(shí)驗(yàn)結(jié)果造成的影響，設(shè)定數(shù)據(jù)庫元組數(shù)(rows)為5 000，最大迭代次數(shù)為1 000，研究數(shù)據(jù)庫失真與水印容量隨種群數(shù)量變化的情況，結(jié)果如圖7所示。

圖7 收斂時數(shù)據(jù)失真與水印容量隨種群數(shù)量的變化情況

可以看出，種群數(shù)量為35時，最終的數(shù)據(jù)失真最小；種群數(shù)量為15時，水印容量情況最優(yōu)。但種群數(shù)量通常會大幅度地影響算法的運(yùn)行時間，過大的種群數(shù)量通常會造成算法耗時過長，故在后續(xù)的實(shí)驗(yàn)中，只驗(yàn)證種群數(shù)量為2、5、10、50時的情況。

4.2 目標(biāo)函數(shù)及算法運(yùn)行時間

在4.1節(jié)基礎(chǔ)上，固定wa=wc=1、最大迭代次數(shù)為1 000，其他不能固定的參數(shù)會在每個實(shí)驗(yàn)中進(jìn)行說明。為更好地對本文方案的運(yùn)行時間和目標(biāo)函數(shù)(為找到降低數(shù)據(jù)失真和提高水印容量平衡的目標(biāo)函數(shù))進(jìn)行評測，本節(jié)主要關(guān)注種群數(shù)量、迭代次數(shù)及問題矩陣DS元組數(shù)量的變化對目標(biāo)函數(shù)(fitness)以及算法運(yùn)行時間造成的影響。

首先，保持種群數(shù)量為2，觀察不同輸入矩陣維數(shù)(rows)下目標(biāo)函數(shù)(fitness)隨epoch的變化情況，實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 迭代次數(shù)與問題矩陣維數(shù)對于目標(biāo)函數(shù)的影響

可以看出，隨著迭代次數(shù)的增大，fitness呈指數(shù)級下降，且不同種群數(shù)量的下降曲線幾乎一致，這就使得本文算法對于不同規(guī)模數(shù)據(jù)庫都有著較好的泛化性能。

其次，設(shè)定輸入矩陣維數(shù)(rows)為5 000，觀察不同種群數(shù)量(PopulationSize)下，目標(biāo)函數(shù)(fitness)隨迭代次數(shù)(epoch)的變化情況，實(shí)驗(yàn)結(jié)果如圖9所示。

圖9 迭代次數(shù)與初始種群數(shù)量對于目標(biāo)函數(shù)的影響

可以看出，隨著種群數(shù)量的增大，目標(biāo)函數(shù)的值下降速度變得更快；同時，對于測試的數(shù)據(jù)，目標(biāo)函數(shù)最終收斂的值隨種群數(shù)量的增大而減小，在實(shí)驗(yàn)中，當(dāng)種群數(shù)量大于10時，本文算法可以將目標(biāo)函數(shù)優(yōu)化到7左右。

最后，設(shè)定輸入矩陣維數(shù)(rows)為5 000，觀察不同種群數(shù)量情況下，尋找最優(yōu)位置花費(fèi)的時間(t)隨迭代次數(shù)變化的情況，實(shí)驗(yàn)結(jié)果如圖10所示。

圖10 初始種群數(shù)量與迭代次數(shù)對于程序運(yùn)行時間的影響

可以看出，實(shí)驗(yàn)所用時間(t)與迭代次數(shù)(epoch)幾乎呈正相關(guān)，且種群數(shù)量(PopulationSize)越大，其增長速度也越大，在實(shí)驗(yàn)中，對于種群數(shù)量小于10的情況，本文算法最終的運(yùn)行時間都保持在10 min以內(nèi)。

5 結(jié) 語

本文提出一種基于改進(jìn)布谷鳥算法和差分拓展技術(shù)的可逆數(shù)據(jù)庫水印方案。在接下來的工作中將會嘗試突破單純的差分拓展技術(shù)所受到的數(shù)據(jù)類型限制：實(shí)驗(yàn)中所使用的數(shù)據(jù)庫為整型數(shù)據(jù)庫，但在實(shí)際嵌入水印時，可能需要在非整型甚至文本型的數(shù)據(jù)庫中嵌入水印，差分拓展技術(shù)因其本身的算法要求，難以在非整型數(shù)據(jù)中嵌入水印，在文本型數(shù)據(jù)庫中也會面臨諸多挑戰(zhàn)。