基于動態(tài)差分擴展的強魯棒數(shù)據(jù)庫水印算法研究

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

基于動態(tài)差分擴展的強魯棒數(shù)據(jù)庫水印算法研究

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

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

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

數(shù)據(jù)庫水?。徊罘诌M化；差分擴展；SVD；Haar小波變換；QR碼

0 引言

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

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

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

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

1 本文算法

1.1 算法框架

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

1.2 數(shù)據(jù)庫水印預處理

圖1 算法的總體框架

Figure 1 General framework of the algorithm

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

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

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

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

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

圖2 水印SVD流程

Figure 2 Watermark singular value decomposition flow

1.3 算法設計

（1）數(shù)據(jù)庫分組

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

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

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

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

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

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

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

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

步驟5 根據(jù)步驟1重新隨機產(chǎn)生一個新的初始種群，分別計算和的適應度函數(shù)。

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

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

（3）水印嵌入算法

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

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

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

圖3 傳統(tǒng)的差分擴展和改進的差分擴展算法應嵌入水印后的數(shù)據(jù)改變量對比

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

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

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

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

輸出 嵌有水印的數(shù)據(jù)庫DB，最終的嵌入水印位置表ade_mdt

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

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

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

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

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

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

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

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

10) End if

11) ade_mdt← 將adet數(shù)組中下標為?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…//嵌入水印數(shù)值的差值小于 10

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

17) Else

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

19) End if

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

21) End if

22) End for

23) End for

25) Return DB, ade_mdt

26) End for

（4）水印提取算法

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

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

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

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

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

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

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

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

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

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

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

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

8) IfW== 0 then

9)0++ //統(tǒng)計提取的水印比特值為 0的個數(shù)

10) Else

11)1++ //統(tǒng)計提取的水印比特值為 1 的個數(shù)

12) End if

13) End for

14) If0>1then //大數(shù)表決

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

16) Else

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

18) End if

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

23) End for

24) Return DB,,QR

2 實驗與結(jié)果分析

2.1 實驗指標

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

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

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

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

2.2 相關參數(shù)分析

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

表1 嵌入數(shù)字QR碼的小波變換對比

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

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

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

圖4 取余值Valmod與數(shù)值改變量的關系

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

圖5 不同種群規(guī)模下適應度值對比

Figure 5 Comparison of the adaptation of different population sizes

除此之外，本文評估了迭代次數(shù)對于自適應差分進化算法的影響，分別進行了25、50、75、125、150、175和200次迭代。每迭代一次，ADE-DDEW算法給數(shù)據(jù)庫隨機產(chǎn)生一個新的初始種群參與族外競爭，避免差分進化陷入局部最優(yōu)，適應度值和迭代次數(shù)的關系如圖6所示?？梢钥闯?，當?shù)螖?shù)為200時，ADE-DDEW算法達到最低的適應度值。

圖6 適應度值和迭代次數(shù)的關系

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

圖7 權重系數(shù)與目標函數(shù)關系

Figure 7 Graph of weight coefficients versus objective function

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

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

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

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

2.3 實驗過程

（1）嵌入容量和數(shù)據(jù)失真對比實驗

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

圖9 各水印算法嵌入容量和數(shù)據(jù)失真對比

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

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

表3 水印嵌入前后不同數(shù)據(jù)庫水印算法的平均值和標準差統(tǒng)計結(jié)果

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

表4 水印嵌入前后不同數(shù)據(jù)庫水印算法的平均值、標準差變化和平均絕對誤差統(tǒng)計結(jié)果

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

（2）魯棒性實驗

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

1)元組刪除攻擊

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

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

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

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

2) 元組修改攻擊

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

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

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

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

3) 元組插入攻擊

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

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

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

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

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

（3）溯源效果展示

ADE-DDEW算法嵌入的水印是經(jīng)過壓縮的QR碼，其中文本QR碼帶有“njupt”的身份信息，數(shù)字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）數(shù)據(jù)庫還原實驗

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

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

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

3 結(jié)束語

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

[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] 邱升紅. 面向關系數(shù)據(jù)庫的可逆水印方法研究[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] 宋巖, 沈泉江, 楊洪山. 基于布谷鳥算法的可逆數(shù)據(jù)庫水印方案[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] 孔嘉琪, 王利明, 葛曉雪. 基于模擬退火和粒子群混合改進算法的數(shù)據(jù)庫水印技術[J]. 信息網(wǎng)絡安全, 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?），女，安徽合肥人，南京郵電大學碩士生，主要研究方向為數(shù)字水印技術。

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

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

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

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

2022?04?02；

2022?11?21

張迎周，zhangyz@njupt.edu.cn

汪天琦, 張迎周, 邸云龍, 等. 基于動態(tài)差分擴展的強魯棒數(shù)據(jù)庫水印算法研究[J]. 網(wǎng)絡與信息安全學報, 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.