基于動態差分擴展的強魯棒數據庫水印算法研究

汪天琦，張迎周，邸云龍，李鼎文，朱林林

基于動態差分擴展的強魯棒數據庫水印算法研究

汪天琦1,2,3，張迎周1,2,3，邸云龍1,2,3，李鼎文1,2,3，朱林林1,2,3

（1. 南京郵電大學計算機學院，江蘇 南京 210023；2. 南京郵電大學軟件學院，江蘇 南京 210023；3. 南京郵電大學網絡空間安全學院，江蘇 南京 210023）

科技行業的快速發展帶來信息量的暴增，各行各業都需要收集和應用大量的數據，海量數據在發揮價值的同時，給數據安全領域帶來了史無前例的挑戰。關系型數據庫作為數據的底層存儲載體之一，其存儲的數據規模大、數據內容豐富、數據隱私度高。數據庫的數據一旦泄露將會造成巨大的損失，保護數據庫的所有權，確認數據的歸屬刻不容緩。對于現有的數據庫水印技術來說，提高水印嵌入容量和減小數據失真之間存在固有矛盾問題，為了緩解此問題且進一步提高水印的魯棒性，提出了一種基于動態差分擴展的強魯棒數據庫水印算法。該算法選取QR碼作為水印，利用經過Haar小波變換的圖像低頻部分進行奇異值分解（SVD，singular value decomposition），提取部分特征值，用取余后的特征值作為待嵌入的水印序列，使得相同長度的水印序列包含更多信息，縮短了嵌入水印的長度。該算法結合自適應差分進化算法和最小差值算法選擇最佳嵌入屬性位，以緩解傳統差分擴展技術在嵌入水印時計算效率低、數據失真大、魯棒性差的問題，提高水印嵌入容量的同時減少了數據的失真。實驗結果表明，該算法保證高水印嵌入率的同時數據失真較低，能夠抵御多種攻擊，具有良好的魯棒性，追蹤溯源的能力強，且與現有的算法對比優勢明顯，在數據安全領域具有廣闊的應用前景。

數據庫水印；差分進化；差分擴展；SVD；Haar小波變換；QR碼

0 引言

科技行業的快速發展帶來的是信息量的暴增，各行各業都需要收集和應用大量的數據，累積的數據規模正以驚人的速度增長。海量數據蘊含的商業價值巨大，但其發揮價值的同時，也為數據安全領域帶來了史無前例的挑戰。數據庫作為最常用的底層存儲工具之一，其信息安全問題不容小覷。國內外學者大多是通過數據庫水印技術來保護數據庫的數據安全，解決信息泄露、源頭難以追蹤的困擾。在數據庫背后利益的驅使下，攻擊者在數據庫所有者不知情的情況下對其加以復制、分發和篡改。數據庫的數據一旦泄露將會造成巨大損失，保護數據庫的所有權，確認數據的歸屬刻不容緩。

數字水印技術[1]可以有效解決很多信息安全問題，作為一種安全有效的保護數字版權的技術手段，數字水印技術廣泛應用于多媒體領域[2-3]。但是，針對數據庫的數字水印研究相對較少。目前，數字水印技術主要關注其不可見性、魯棒性、安全性和嵌入容量等特性[4]。

可逆水印技術是數字水印技術的一個重要分支，Zhang等[5]提出了經典的可逆水印算法，該算法利用直方圖平移拓展出的冗余空間按照指定的運算公式來嵌入水印，經過逆運算即可恢復出原始數據和水印信息，但是該算法的魯棒性較差，在面對不法分子的惡意攻擊時提取出的水印信息不完整。針對Zhang等提出算法的不足，Hu等[6]引入了遺傳算法訓練出最佳的水印嵌入位置，結合分組密鑰和平移直方圖設計了一種基于遺傳算法的直方圖平移可逆水印技術。

對于數據庫水印來說，水印隱藏在關系數據庫中，數據值變化較大，嚴重破壞原始數據的質量，水印的魯棒性低，攻擊者很容易破壞水印信息。Gupta等[7]吸取了數字水印技術的經驗，提出了基于差分擴展的可逆數據庫盲水印，選取元組中的任意兩個屬性值，通過差分擴展計算將水印嵌入數值中，對兩個屬性值進行計算嵌入一位水印，導致數值改動大于水印的嵌入，影響了數據庫的可用性和魯棒性。差分擴展技術中增加了水印嵌入容量，但不可避免地增大了數據的失真，于是研究者想到利用優化算法改進差分擴展數據庫水印方法。Jawad等[8]利用遺傳算法改進了基于差分擴展的可逆數據庫盲水印，提出基于遺傳算法的差分擴展可逆數據庫水印，提高數據庫水印算法的魯棒性同時減少數據失真。但是，經過遺傳算法優化的水印嵌入率并不盡如人意。邱升紅[9]設計了一種基于差分擴展和人工蜂群算法的數據庫可逆水印方法，使用人工蜂群算法代替遺傳算法進行優化，增大了水印的嵌入容量并減少了數據的失真，進一步提高了水印算法的魯棒性。宋巖等[10]利用改進的布谷鳥算法啟發式地搜索水印嵌入屬性位，通過差分擴展嵌入水印，對于大規模的數據庫算法的水印嵌入率較高，對抗攻擊的能力較強。孔嘉琪等[11]基于模擬退火改進的粒子群算法尋找更好的水印嵌入位置，提出了基于屬性重要度的帶權損失函數，解決了現有方案在抗屬性維度攻擊時魯棒性較差的問題。由于數據庫存儲的是純數據，其數值的改變對原載體的影響遠大于多媒體水印，所以數據庫水印技術很難在水印容量和數據失真方面保持平衡。Shi等[12]試圖通過恢復原始數據和嵌入式水印信息來克服數據失真的問題。可逆水印技術能夠在提取水印的同時恢復數據，然而目前的可逆數據庫水印技術在嵌入水印后，數據質量和水印魯棒性方面存在缺陷，基于此，Ge等[13]對水印容量和數據失真做了研究和改進，在一定的數據失真范圍內提高了水印嵌入容量。現有的技術主要通過增加水印長度或提取水印特征壓縮數據兩種方法來達到提高水印嵌入容量的目的。陳青等[14]提出了一種新的基于旋轉穩定區域和兩級奇異值分解（SVD，singular value decomposition）的水印算法，保證水印的嵌入容量，且具有良好的不可見性和較高的魯棒性。關虎等[15]將大容量、高容錯的二維碼理論應用于變換域圖像水印算法，在保證水印不可見性和算法安全性的基礎上，顯著提高了水印容量和魯棒性。在學者不斷研究改進的過程中，數據庫水印的魯棒性和嵌入容量逐漸提高，數據的失真能夠控制在合理的范圍內。

1 本文算法

1.1 算法框架

大多數據庫水印技術是單純地嵌入一串數字序列或一副圖像，包含的信息量較少且容易被攻擊者破壞。當數據庫發生泄露被惡意攻擊時常常會導致水印被破壞，無法根據提取的信息鎖定攻擊者，因此水印的魯棒性和溯源度較差。為了解決這一問題，需要增加水印的嵌入容量，但是嵌入容量過多會造成數據嚴重失真，影響數據庫正常使用。針對數據庫冗余性小、水印嵌入容量和數據失真之間存在固有矛盾等問題，本文提出了一種基于自適應差分進化（ADE，adaptive differential evolution）和動態差分擴展（DDE，dynamic difference expansion）的強魯棒數據庫水印算法，以下簡稱ADE-DDEW。所提算法首先對經過Haar離散小波變換的圖像低頻部分進行SVD，提取非0特征值，然后對特征值進行取余，對取余后的特征值進行動態壓縮作為待嵌入的水印序列。結合自適應差分進化算法和最小差值算法選擇最佳的水印嵌入屬性位，最后通過動態地選取傳統的或改進的差分擴展技術進行水印的嵌入。算法的總體框架如圖1所示，主要包括水印預處理、水印嵌入和水印提取3個部分。

1.2 數據庫水印預處理

圖1 算法的總體框架

Figure 1 General framework of the algorithm

基于Haar小波變換的圖像壓縮算法的核心思想是通過計算平均值和差值得到細節系數（分為低頻和高頻），將圖像分解成若干個高頻圖像和一個低頻圖像，可以在不影響主要信息的情況下初步對原始圖像進行壓縮，達到減小圖像信息量的目的。Haar能夠完全無失真地還原出原始圖像，進而提高水印的可溯源性。本文采用Haar小波變換對QR碼圖像進行頻域分解，由于低頻部分包含圖像大多數的有用信息，并且低頻信號對于圖像壓縮、高斯噪聲等多種圖像處理操作有很強的抵御能力，所以本文提取分解后的低頻圖像作為處理完成的水印圖像。假設水印圖像的4個相鄰像素值是[]，基于Haar小波變換的QR碼頻域分解的具體步驟如下。

步驟1 將4個像素值兩兩分組，得到[]和[]。

SVD[16]主要應用在數據降維和數據壓縮領域，是很多機器學習算法的基石，其核心思想是將圖像矩陣分解出特征值和特征向量。矩陣的運算可以描述為線性空間中的變換，當一個矩陣進行運算時，本質上就是在矩陣空間下進行的一次線性變換（拉伸或者旋轉），線性變化無法直觀地通過圖像來展示，但是經過奇異值分解得到的部分特征向量代表了該矩陣的主要變化方向。在這些方向上進行變換，就可以模擬矩陣的運算。基于上述性質，SVD可以做到無失真的壓縮，不對圖像造成損壞的同時通過逆運算還原出原始圖像。

目前，圖像作為水印嵌入數據庫的場景基本是需要分割圖像，然后將分割后的子圖像分別嵌入分組后的子數據表。這種傳統的方法不僅對圖像的尺寸有一定的要求，而且由于數據庫的分組不是無限的，所以嵌入的圖像也有一定的限制。為了將二維的圖片水印壓縮成一維的水印序列，使用SVD技術對頻域分解后提取出的低頻圖像進一步壓縮，提取部分特征值生成水印序列。SVD不要求圖像的尺寸并且有很強的數據降維能力，提高了水印信息的壓縮率，使得相同長度的水印序列中包含更多的數據信息。

假設QR碼圖像是一個×的矩陣，經過SVD可以變成如式(3)的形式。

圖2 水印SVD流程

Figure 2 Watermark singular value decomposition flow

1.3 算法設計

（1）數據庫分組

定義2 水印嵌入容量（WEC，watermark embedding capacity）：把嵌入水印的元組數和總元組數的比值定義為水印嵌入容量。

定義3 數據失真量（AoDD，amount of data distortion）：定義嵌入水印前后屬性值的改變率為數據失真量。即對于任意屬性列來說，是嵌入水印造成的整體數據差值和該屬性列極差之間的比值。

數據的變化量受原始數值的影響較大。具體來說，一位數的數據變化量只能在區間[0,9]，而兩位數則可以達到[0,99]，以此類推，可以得出原始數值越高，可能導致數據變化量越大，如果只是單純地累加數值變化量，對于有失真統計來說有失公平。本文數據失真量的計算方法如式(6)所示。

將上述WEC和AoDD兩個指標作為目標函數的主體得到最終的目標函數，如式(7)所示。

（2）最佳嵌入屬性位選取

本文利用自適應差分進化算法[15]進行水印最佳嵌入位置的選擇，在提高嵌入容量的同時數據失真也會比較大。因此，通常選擇每一個元組差值最小的兩個屬性進行嵌入，但是該算法難以抵御最小差值攻擊。于是，在嵌入水印之前增加一次屬性失真的判斷，將超過屬性失真范圍的屬性位置用最小差值計算的屬性位置來代替，具體步驟如下。

步驟2 根據式(9)～式(11)對初始基因種群進行變異處理得到變異后的基因個體數組。

步驟4 分別計算和的適應度函數，適應度函數越小，說明越符合收斂目標。

步驟5 根據步驟1重新隨機產生一個新的初始種群，分別計算和的適應度函數。

步驟6 重復執行步驟2到步驟5，直到獲得最優決策向量或者達到最大的進化迭代次數，計算得到的最優值即當前數據庫子組的最佳待嵌入水印屬性位，與元組主鍵一起構成水印嵌入位置表adet。

步驟7 提取每個參與水印運算的元組取余后屬性差值最小的兩個屬性，從而記錄最小差值的水印嵌入位置表mdt。對adet進行屬性失真判斷，如果元組嵌入水印后的值超過了有失真范圍，則將其水印嵌入位的下標記為?1，然后把下標為?1的位置用mdt的下標來代替，生成最終的嵌入水印的屬性位置表ademdt。

（3）水印嵌入算法

差分擴展技術[18]的核心思想是利用數值間的平均值和差值計算將水印嵌入數據載體中。基于這一特性，差分擴展的水印嵌入率很高，但同時如果數據之間的差值過大，剛經過計算后得到的新數據的改變量也很大，數據的失真降低了數據水印的可用性。因此本文對要嵌入水印的數據進行有條件的取余，盡量將數據之間的差值控制在一定范圍內，優化差分擴展特性導致的數據失真過大的弊端，增大水印的嵌入容量。

取余后屬性值間的均值avg和差值計算如式(14)所示。

傳統差分擴展技術和改進差分擴展技術對數值的改變量受到原始數據差值的影響，根據圖3可以看出，在原始數據差值小于10時，傳統的差分擴展的數據改變量普遍小于改進的差分擴展，而在原始數據差值大于10時，改進的差分擴展的數據改變量明顯小于傳統的差分擴展。因此，選取嵌入水印的屬性位置后，先判斷該位置上的屬性差值，如果<10，則選擇傳統的差分擴展算法，反之選擇改進的差分擴展算法。

圖3 傳統的差分擴展和改進的差分擴展算法應嵌入水印后的數據改變量對比

Figure 3 Comparison of the amount of data change between the traditional differential extension algorithm and the improved differential extension algorithm after embedding the watermark

基于自適應差分進化和動態差分擴展的水印嵌入算法如算法1所示。首先對數據庫進行聚類分為個子組；其次對所有子組使用自適應差分進化算法初步選擇出水印嵌入位，通過有失真分析結合最小差值算法確定最佳的水印嵌入位；最后判斷嵌入水印數值間的差值，根據差值的范圍動態選擇傳統的或改進的差分擴展算法，依次對子組進行水印的嵌入。特別地，每個子組冗余地嵌入同一水印比特位。

算法1 ADE-DDEW水印嵌入算法

輸入 數據庫DB，數據庫分組數，嵌入水印屬性列數，待嵌入水印序列，取余值Valmod

輸出 嵌有水印的數據庫DB，最終的嵌入水印位置表ade_mdt

1) ade_mdt=[][] //初始化最終的嵌入水印位置表ade_mdt

2) adet=[][] //初始化根據自適應差分進化計算的水印最佳嵌入屬性位置表adet

3) mdt=[][] //初始化根據最小差值計算的水印最佳嵌入屬性位置表mdt

4) DB←kmeans(DB,) //利用-means 算法進行數據庫分組，得到個子組

5) For=0 to?1 do //遍歷每個子組嵌入水印，得到嵌有水印的數據庫DB

6) adet←ADE(DB,,) //自適應差分進化算法計算出最佳屬性下標存放在adet數組中

7) mdt←MD(DB,,) //最小差值函數計算出差值最小的屬性下標存放在數組 mdt 中

9) adet[1][2]=?1 //如果超過有失真范圍，將有失真屬性位置下標置為?1

10) End if

11) ade_mdt← 將adet數組中下標為?1的部分用mdt的下標代替

12) For=0 to ade_mdt.GetLength(0)?1 do //遍歷當前子組嵌入水印位置表ade_mdt 的嵌入位置

13) For=1 to ade_mdt[0].length?1 do

14) If ade_mdt [][]!=?1 then

15) If<10 then…//嵌入水印數值的差值小于 10

16) 利用傳統的差分擴展技術嵌入水印W

17) Else

18) 利用改進的差分擴展技術嵌入水印W

19) End if

20) DB←根據式(17)還原嵌入水印的屬性值

21) End if

22) End for

23) End for

25) Return DB, ade_mdt

26) End for

（4）水印提取算法

在水印提取階段，同樣通過聚類算法進行分組。對每個子組提取水印比特位，由于是冗余嵌入，利用大數表決的方法確定提取的水印數值，將提取出的水印比特位按照分組順序組合在一起得到最終的水印序列，同時能恢復出原始的數據庫。

ADE-DDEW水印提取算法在利用改進的差分擴展算法進行水印提取時，通過嵌入水印時的除數和取余值恢復數據，數據可以復原，即使數據庫遭到一定破壞，提取的水印可能不完整，但數據庫可以復原如初，有效保障了數據庫的可用性。針對提取出的水印序列，根據數據壓縮恢復一維水印序列，根據SVD逆運算還原出低頻圖片，最后通過Haar小波逆變換還原出QR碼。根據掃描出的QR碼信息，可以確定泄密者的身份，識別攻擊者。特別地，即使還原的QR碼有失真，只要在一定范圍內也可以掃描出身份信息，提高了水印的魯棒性，如算法2所示。

算法2 ADE-DDEW 水印提取算法

輸入 數據庫DB，嵌入水印位置表ade_ mat，數據庫分組數，取余值Valmod

輸出 恢復的原始數據庫DB，提取的數字水印序列，還原出的 QR 碼圖像

1) DB←kmeans(DB,) //利用-means算法進行數據庫分組，得到個子組

2) For=0 to?1 do //迭代每個子組

3)0=0,1=0 //初始化記錄提取的 0、1 個數的變量，用于大數表決

4) For=0 to ade_mdt.GetLength(0)?1 do //迭代每個子組的所有元組

5)1=ade_mdt[][0],2=ade_mdt[][1] //根據 ade_mdt 選擇出嵌入水印的屬性

6) 根據式(18)對1、2進行取余操作

7) 根據式(20)提取水印的比特值W，根據式(21)和式(22)恢復屬性數值1、2

8) IfW== 0 then

9)0++ //統計提取的水印比特值為 0的個數

10) Else

11)1++ //統計提取的水印比特值為 1 的個數

12) End if

13) End for

14) If0>1then //大數表決

15)W=0 //如果提取的水印0的個數大于1的個數，則該子組的水印比特為0

16) Else

17)W=1 //否則該子組的水印比特為 1

18) End if

19)append(W) /依次組合每個子組提取的水印比特值

23) End for

24) Return DB,,QR

2 實驗與結果分析

2.1 實驗指標

本文的仿真實驗采用UCI機器學習資源庫提供的Appliances energy prediction Data Set作為數據樣本，該數據庫包含19 735個元組和29個屬性。由于ADE-DDEW水印算法是對整數型的數值屬性進行計算，所以對于浮點型屬性值進行預處理，將其擴大成整數型數據然后通過差分擴展嵌入水印，最后等比例還原成浮點型。將ADE-DDEW算法與已有的GADEW[10]、GAHSW[8]、RF-GADEW[14]和RF-GAHSW[14]等可逆數據庫水印算法進行對比實驗分析。

本文通過對比原始水印比特位和提取的水印比特位的方法來衡量數據庫水印算法的魯棒性，即水印的誤碼率（BER，bit error rate）[8]。魯棒性評價指標BER的計算如式(23)所示。

其中，為數據庫的分組數，即水印序列的長度，W和分別是嵌入水印和提取水印的第位比特值。由式(23)可知，算法的魯棒性和BER成反比，較低的誤碼率值意味著較高的水印魯棒性。

對于數據庫水印算法的嵌入容量，通過水印嵌入容量（WEC）來衡量，即計算嵌入水印的數據庫元組占數據庫元組的比例。對于數據失真，即嵌入水印后造成數據庫數據的改變量。本文通過水印嵌入前后屬性的平均值（Mean）、標準差（Std）的變化以及平均絕對誤差（MAE）來量化其統計失真，MAE的計算如式(24)所示。

2.2 相關參數分析

在將水印嵌入數據庫之前，需要對QR碼和數據庫進行預處理，使得嵌入的水印序列包含更多信息，提高嵌入容量。為了在相同長度下得到更多信息，經常采用數據壓縮技術，這其中Haar小波變換效果最好，嵌入數字QR碼和嵌入文本QR碼的小波變換對比分別如表1和表2所示。

表1 嵌入數字QR碼的小波變換對比

表2 嵌入文本QR碼的小波變換對比

壓縮率和絕對最大差異是衡量小波變換壓縮效果的指標。壓縮率越高，表示數據壓縮的能力越好，信息密度越高；絕對最大差異越大，表示數據信息的多樣性越好，過濾信號的能力越強。本文對不同像素的QR碼進行了小波變換實驗，從表1和表2可以看出，Haar小波變換的壓縮率和絕對最大差異綜合強于另外3種小波變換（Daubechies、Coiflet、Symlet）算法，這也是文本選用Haar小波變換壓縮QR碼的理由。

ADE-DDEW水印算法采用自適應差分進化算法計算最佳屬性位，不同的種群規模對算法最優解的計算有一定的影響，種群規模過大導致算法的收斂速度下降，搜索時間增加；種群規模過小容易過早收斂，全局搜索能力差，影響算法的魯棒性。對區間[10,120]的種群規模進行測試，不同種群規模下適應度值對比如圖5所示，結果顯示，當種群規模為90時，目標函數適應度值最小。

圖4 取余值Valmod與數值改變量的關系

Figure 4 The residual value Valmodis plotted against the amount of change in value

圖5 不同種群規模下適應度值對比

Figure 5 Comparison of the adaptation of different population sizes

除此之外，本文評估了迭代次數對于自適應差分進化算法的影響，分別進行了25、50、75、125、150、175和200次迭代。每迭代一次，ADE-DDEW算法給數據庫隨機產生一個新的初始種群參與族外競爭，避免差分進化陷入局部最優，適應度值和迭代次數的關系如圖6所示。可以看出，當迭代次數為200時，ADE-DDEW算法達到最低的適應度值。

圖6 適應度值和迭代次數的關系

Figure 6 Plot of the relationship between fitness value and number of iterations

圖7 權重系數與目標函數關系

Figure 7 Graph of weight coefficients versus objective function

不同的嵌入屬性列數可能會導致容量和數據失真不同，本文對10～29列的情況分別做實驗，具體結果如圖8所示。

圖8 不同嵌入屬性列數下水印嵌入容量和數據失真對比

Figure 8 Comparison of watermark embedding capacity and data distortion with different number of embedding columns

實驗結果表明，選取28列屬性嵌入水印，其嵌入容量較高、數據失真最小。因此，后面的實驗都將選取28列屬性進行水印的嵌入。

2.3 實驗過程

（1）嵌入容量和數據失真對比實驗

將本文提出的ADE-DDEW算法與已有的GADEW、RF-GADEW、GAHSW和RF-GAHSW算法進行水印嵌入容量和數據失真的對比。對于數據庫水印算法來說，嵌入容量越大，數據失真越大。各水印算法嵌入容量和數據失真對比如圖9所示。

圖9 各水印算法嵌入容量和數據失真對比

Figure 9 Comparison of embedding capacity and data distortion by watermarking algorithm

從圖9中可以看出，本文提出的ADE-DDEW算法在嵌入容量高的算法中數據失真最低，在數據失真低的算法中嵌入容量最高，有效緩解了水印嵌入容量和數據失真之間存在的矛盾。ADE-DDEW算法對數據進行了取余操作，限制了數據的變化范圍，同時浮點型化為整型計算有效降低了數值改變量，因此水印不會造成過大的數據失真，采用差分擴展算法嵌入水印同時結合最小差值和差分進化算法確定水印嵌入位置提高了水印的嵌入容量。

表3 水印嵌入前后不同數據庫水印算法的平均值和標準差統計結果

其中，Mean和Std分別代表原始數據庫的平均值和標準偏差值，Mean和Std分別代表嵌入水印后數據庫的平均值和標準偏差值。

表4 水印嵌入前后不同數據庫水印算法的平均值、標準差變化和平均絕對誤差統計結果

由表3和表4可知，ADE-DDEW算法的各個屬性在平均值和標準差方面的變化非常小，其造成的最大變化是0.015，這與GADEW、RF-GADEW、GAHSW和RF-GAHSW算法相比可以忽略不計。另外，表中有一些變化值為0，表示該屬性列沒有嵌入水印。一般來說，水印算法對數據質量的影響越小越好，對于量化屬性分布有失真的MAE來說也是如此。表中GADEW、RF-GADEW、GAHSW和RF-GAHSW算法的MAE值并不理想，分別為2.914、1.315、0.852和0.516，這意味著嵌入水印后會造成巨大的數據失真，影響數據庫的可用性，而ADE-DDEW算法的MAE值為0.019，遠遠低于其他算法。實驗結果驗證了所提ADE-DDEW算法的有效性。綜上所述，ADE-DDEW算法在統計失真方面的表現明顯優于其他算法，保障了數據庫的可用性。

（2）魯棒性實驗

本文通過檢測水印的誤碼率（水印檢測失敗的比率）來判斷在多種元組攻擊下各數據庫水印算法的魯棒性，其中誤碼率越低，說明水印魯棒性越好，當誤碼率接近零時，水印被正確地從數據庫中檢測出來。實驗分析和對比了本文提出的ADE-DDEW算法與GADEW、RF-GADEW、GAHSW和RF-GAHSW算法在刪除攻擊、修改攻擊和插入攻擊下水印的誤碼率，分別完成0、10%、20%、30%至90%的攻擊比例，取誤碼率的平均值作為最終結果。實驗結果如圖10～圖12所示。

1)元組刪除攻擊

攻擊者會隨機刪除元組以破壞水印，被刪除的元組中可能嵌有水印，如果刪除過多，會導致無法提取出正確的水印，影響版權的保護。刪除攻擊下各算法提取水印的誤碼率對比如圖10所示。

圖10 刪除攻擊下各算法提取水印的誤碼率對比

Figure 10 Comparison of BER of watermark extraction by algorithms under removal attack

從圖10可以看出，當數據庫受到嚴重刪除攻擊時，如數據庫中被刪除的元組達到90%，GADEW、RF-GADEW、GAHSW和RF-GAHSW算法提取水印的BER值分別為0.93、0.74、0.47和0.42，而ADE-DDEW算法的BER值為0.37。如果刪除的元組中含有大量的水印信息，會影響到水印的完整提取。因此，刪除攻擊對數據庫水印的影響最為嚴重。實驗還表明，隨著刪除元組數量的增加，水印提取時的誤碼率隨之增加，相較其他方法，ADE-DDEW算法的誤碼率曲線增長較為平緩且最大的誤碼率不超過0.4，在刪除攻擊下有更好的魯棒性。

2) 元組修改攻擊

攻擊者會隨機修改元組中的任意屬性值以破壞水印，被修改的屬性值中可能嵌有水印，如果修改過多，會導致無法提取出正確的水印，同時還原數據庫過程也會受到影響。修改攻擊比例下各算法提取水印的誤碼率對比如圖11所示。

圖11 修改攻擊下各算法提取水印的誤碼率對比

Figure 11 Comparison of BER of watermark extraction by each algorithm under modified attack

從圖11可以看出，修改攻擊的強度和水印的誤碼率成正比，ADE-DDEW算法的整體誤碼率明顯低于其他水印算法，即使修改了90%的元組屬性值，ADE-DDEW算法的誤碼率也只有0.25，也能恢復大部分的水印信息和原始數據，是高度穩健的水印算法，有利于溯源攻擊者。

3) 元組插入攻擊

元組插入攻擊是隨機創建元組并插入數據庫以破壞水印的一種攻擊。元組插入攻擊下提取水印的誤碼率對比如圖12所示。

實驗結果表明，對于利用差分擴展進行水印嵌入的數據庫水印算法來說，向數據庫添加元組這種攻擊方式不會對水印信息完整正確地提取造成影響，也就是說，無論插入多少元組，在插入攻擊下的誤碼率始終為0。因此，ADE-DDEW算法對插入攻擊具有極強的魯棒性。

圖12 元組插入攻擊下提取水印的誤碼率對比

Figure 12 Comparison of BER of extracted watermark under tuple insertion attack

綜上所述，ADE-DDEW算法在刪除攻擊、修改攻擊和插入攻擊下水印誤碼率增長緩慢，特別是對于插入攻擊，可以完全提取出正確的水印。可見ADE-DDEW算法可以抵御常見的數據庫攻擊，具有良好的魯棒性。

（3）溯源效果展示

ADE-DDEW算法嵌入的水印是經過壓縮的QR碼，其中文本QR碼帶有“njupt”的身份信息，數字QR碼帶有“20211216”的身份信息。提取出的水印序列通過一系列的逆運算還原出QR碼，掃描QR碼就可以得到唯一標識攻擊者的身份信息，以達到追蹤溯源的目的。本文提取攻擊實驗后的水印序列，將其還原成對應的QR碼與嵌入的QR碼進行對比，檢測算法的追蹤溯源能力。待嵌入QR碼圖像如圖13所示。

圖13 待嵌入QR碼圖像

Figure 13 QR code image to be embedded

各攻擊下提取的QR碼圖像如表5所示。QR碼有極強的容錯率，即使提取的水印存在一定的無碼率，還原的QR碼也能夠掃描出身份信息。由上述圖表可知，即使在攻擊比例高（90%）的情況下，掃描QR碼仍然可以準確無誤地掃描出“njupt”和“20211216”這兩個身份信息，能夠準確地追蹤到攻擊者。

表5 各攻擊下提取的QR碼圖像

（4）數據庫還原實驗

圖14 不同攻擊比例下ADE-DDEW算法的數據改變情況

Figure 14 Data alteration of ADE-DDEW algorithm for different attack ratios

由圖14可知，即使大部分數據被攻擊，ADE-DDEW算法也可以恢復原始數據，即使大量數據被破環，也可以恢復將近一半的數據，說明ADE-DDEW算法具有良好的還原性。

3 結束語

考慮到提高水印嵌入容量和減小數據失真存在的固有矛盾問題，本文提出了一種基于動態差分擴展的強魯棒數據庫水印算法。用QR碼作為水印載體，利用Haar小波變換進行數據壓縮并且通過SVD提取QR碼的特征值，作為待嵌入的水印序列，增大了相同水印序列長度下水印包含的信息量。同時過濾多種信號攻擊，提高圖像抵御攻擊的能力。該算法結合自適應差分進化算法和最小差值算法選擇最佳嵌入屬性位，通過動態地選取傳統差分擴展算法或改進的差分擴展技術進行水印的嵌入，以緩解傳統差分擴展算法在嵌入水印時計算效率低、數據失真大、魯棒性差的問題，提高水印嵌入容量的同時減少數據失真。本文通過實驗驗證了數據庫水印算法的可行性，該算法在一定的數據失真范圍內能有效地提高水印的嵌入容量，在數據庫遭受攻擊時表現出良好的魯棒性，能夠有效地溯源泄密者，且與現有的算法對比優勢明顯。

[1] HOLT L, MAUFE B G, WIENER A. Encoded marking of a recording signal[P]. U L Patent GB2196167A, 1988.

[2] HIMANSHU A, FAROOQ H. Development of payload capacity enhanced robust video watermarking scheme based on symmetry of circle using lifting wavelet transform and SURF[J]. Journal of Information Security and Applications, 2021, 59.

[3] SHOHIDULISLAM M, NAQVI N, ABBASI A T, et al. Robust dual domain twofold encrypted image-in-audio watermarking based on SVD[J]. Circuits, Systems, and Signal Processing, 2021 (prepublish).

[4] 趙春雨. 提高嵌入容量的水印算法研究[D]. 鄭州: 鄭州大學, 2011.

ZHAO C Y. Research on algorithm for improving the capacity of digital watermarking[D]. Zhengzhou: Zhengzhou University, 2011.

[5] ZHANG Y, YANG B, NIU X M. Reversible watermarking for relational database authentication[J]. Journal of Computers, 2006, 17(2): 59-66．

[6] HU D, ZHAO D, ZHENG S. A new robust approach for reversible database watermarking with distortion control[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(6): 1024-1037.

[7] GUPTA G, PIEPRZYK J. Reversible and blind database watermarking using difference expansion[J]. International Journal of Digital Crime and Forensics, 2009, 1(2): 42-54.

[8] JAWAD K, KHAN A. Genetic algorithm and difference expansion based reversible watermarking for relational databases [J]. Journal of Systems and Software, 2013, 86(11): 2742-2753.

[9] 邱升紅. 面向關系數據庫的可逆水印方法研究[D]. 西安: 西安電子科技大學, 2018.

QIU S H. Research on reversible watermarking methods for relational databases[D]. Xi'an: Xi'an University of Electronic Science and Technology, 2018.

[10] 宋巖, 沈泉江, 楊洪山. 基于布谷鳥算法的可逆數據庫水印方案[J]. 計算機應用與軟件, 2021, 38(12): 304-313.

SONG Y, SHEN Q H, YANG H S. A reversible database watermarking scheme based on cuckoo algorithm[J]. Computer Application and Software, 2021, 38(12): 304-313.

[11] 孔嘉琪, 王利明, 葛曉雪. 基于模擬退火和粒子群混合改進算法的數據庫水印技術[J]. 信息網絡安全, 2022, 22(5): 37-45.

KONG J Q, WANG L M, GE X X. Database watermarking technique based on simulated annealing and particle swarm hybrid improvement algorithm[J]. Information Network Security, 2022, 22(5): 37-45.

[12] SHI Y, LI X, ZHANG X, et al. Reversible data hiding: advances in the past two decades[J]. IEEE Access, 2016, 4(10): 3210-3237.

[13] GE C, SUN J, SUN Y, et al. Reversible database watermarking based on random forest and genetic algorithm[C]//2020 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC). 2020.

[14] 陳青, 夏蘭婷, 卜瑩. 基于兩級奇異值分解的魯棒水印算法[J]. 應用科學學報, 2020, 38(6): 966-975.

CHEN Q, XIA L T, BU Y. Robust watermarking algorithm based on two-level singular value decomposition[J]. Journal of Applied Sciences, 2020, 38(6): 966-975.

[15] 關虎, 張桂煊, 張樹武, 等. 基于二維碼的魯棒圖像水印技術及應用研究[J]. 有線電視技術, 2018(10): 20-26.

GUAN H, ZHANG G X, ZHANG S W, et al. Research on robust image watermarking technology and application based on QR code[J]. Cable TV Technology, 2018(10): 20-26.

[16] KLEMA V, LAUB A. The singular value decomposition: its computation and some applications[J]. Automatic Control IEEE Transactions on, 1980, 25(2): 164-176.

[17] STORNR P K．Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous spaces[R]. 1995.

[18] TIAN J. Reversible data embedding using a difference expansion[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2003, 13(8): 890-896.

Research on strong robustness watermarking algorithm based on dynamic difference expansion

WANG Tianqi1,2,3, ZHANG Yingzhou1,2,3, DI Yunlong1,2,3, LI Dingwen1,2,3, ZHU Linlin1,2,3

1. Department of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China 2. Department of Software, Nanjing University of Posts and Telecommunications, Nanjing 210023, China 3. Department of Cyberspace Security, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

A surge in the amount of information comes with the rapid development of the technology industry. Across all industries, there is a need to collect and utilize vast amounts of data. While this big data holds immense value, it also poses unprecedented challenges to the field of data security. As relational databases serve as a fundamental storage medium for data, they often contain large-scale data rich in content and privacy. In the event of a data leak, significant losses may occur, highlighting the pressing need to safeguard database ownership and verify data ownership. However, existing database watermarking technologies face an inherent tradeoff between improving watermark embedding capacity and reducing data distortion. To address this issue and enhance watermark robustness, a novel robust database watermarking algorithm based on dynamic difference expansion was introduced. The QR code was employed as the watermark, the SVD decomposition of the low frequency part of the image was utilized after Haar wavelet transform. By extracting specific feature values and using residual feature values as the watermark sequence, it was ensured that the same-length watermark sequence contains more information and the embedded watermark length can be reduced. Furthermore, by combining the adaptive differential evolution algorithm and the minimum difference algorithm, the optimal embedding attribute bits were selected to alleviate the problems of low computational efficiency, high data distortion and poor robustness of traditional difference expansion techniques in embedding watermarks, and to improve the embedding capacity of watermarks while reducing the distortion of data. Experimental results demonstrate that the proposed algorithm achieves a high watermark embedding rate with low data distortion. It is resilient against multiple attacks, exhibiting excellent robustness and strong traceability. Compared to existing algorithms, it offers distinct advantages and holds great potential for broad application in the field of data security.

database watermarking, differential evolution, difference expansion, singular value decomposition, Haar wavelet transform, quick response code

TP393

A

10.11959/j.issn.2096?109x.2023065

汪天琦（1997?），女，安徽合肥人，南京郵電大學碩士生，主要研究方向為數字水印技術。

張迎周（1978?），男，安徽廬江人，博士，南京郵電大學教授，主要研究方向為軟件與信息安全。

邸云龍（1996?），男，安徽滁州人，博士，南京郵電大學碩士生，主要研究方向為數字水印技術。

李鼎文（1998? ），男，江蘇南京人，南京郵電大學碩士生，主要研究方向為數字水印技術。

朱林林（1997?），女，山東德州人，南京郵電大學碩士生，主要研究方向為數字水印技術。

2022?04?02；

2022?11?21

張迎周，zhangyz@njupt.edu.cn

汪天琦, 張迎周, 邸云龍, 等. 基于動態差分擴展的強魯棒數據庫水印算法研究[J]. 網絡與信息安全學報, 2023, 9(5): 150-165.

WANG T Q, ZHANG Y Z, DI Y L, et al. Research on strong robustness watermarking algorithm based on dynamic difference expansion [J]. Chinese Journal of Network and Information Security, 2023, 9(5): 150-165.