基于決策樹的數據庫脆弱水印算法研究＊

（1.空軍后勤部指揮自動化站 北京 100720）（2.第二炮兵后勤部信息中心 北京 100820）

1 引言

關系型數據庫是以二維表作為數據模型的數據庫系統，自20世紀70年代發展至今，特別是互聯網遠程訪問數據庫操作普遍化，關系數據庫水印技術成為一種有效版權保護技術逐步得到重視。關系數據庫數字水印是指在不破壞關系數據庫數據可用性的前提下，在關系數據庫的冗余空間中嵌入水印信息，實現保護關系數據庫版權或斷定其是否遭到攻擊和篡改的目的［1］。數字水印包括魯棒水印和脆弱水印，脆弱水印主要用于數據的真偽辨別和完整性鑒定，能夠敏感發現對數字作品任何形式的改變，從而確保能夠檢測對數字作品的篡改。

文章主要對關系數據庫脆弱水印技術進行研究，在保護數據庫數據準確性基礎上，按照決策樹算法分組，并對利用元組屬性數據最低有效位采用漢明碼編碼等方法進行數據檢測，并嵌入水印信息實現數據庫脆弱水印的構建。

2 數字水印技術

目前數據庫水印算法主要是利用一定失真范圍內的數據變形來嵌入水印。IBM Almaden 研究中心R.Agrawal于2002年提出了對關系數據庫中數值型屬性值進行標記的策略，利用數值型元組存在的冗余空間，對某些數值屬性的最低有效位（LSB）進行位操作，從而實現水印信息的嵌入［2］。R.Sion等人 進一步對關系數據庫水印進行研究，采用給定數值型項目集合S＝｛s1，s2，s3，…，sn｝以及一個排序密鑰K，根據標準化項目的最大意義比特位的加密鍵值哈希對其進行秘密排序，構建子集Si用于嵌入比特位水印標記［3］。牛夏牧等人對關系數據庫數字水印進一步研究加入小量有實際意義水印的技術，清華大學張志浩等人2004年提出把一幅圖像嵌入到關系數據庫中的水印算法［4］。

Guo等人提出了數據庫脆弱水印算法，將數據庫元組劃分到不同分組中，生成由屬性水印和元組水印構成的分組水印矩陣，從而定位數據篡改位置［5］。Hsien-Chu Wu等人根據數據庫關系數據之間存在相關性，運用支持向量回歸（SVR）訓練樣本，得到屬性的最佳關系模型，然后選取一個屬性作為目標值，剩余屬性作為SVR 訓練特征值進行訓練，生成Huffman編碼，并利用私鑰進行加密放在數據庫后作為有效負載信息隨著數據庫一起傳輸，作為檢測篡改的脆弱水?。?］。

3 改進型C4.5決策樹

決策樹是數據挖掘分類方法中的常用方法，能夠以圖形化的形式表現挖掘結果，從而方便使用者快速作出決策或預測。其中，ID3算法是J.R.Quinlan于1986年首先提出的一個經典決策樹算法，該算法以信息論為基礎，把信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行劃分［7］。該算法最大的不足是每次分裂傾向于選擇取值較多的屬性且不能處理連續型數據。

為了解決ID3算法不足，Quinlan在1993年在繼承決策樹基本構造思想基礎上提出C4.5算法，該算法用信息增益率代替信息熵作為選擇分裂屬性的標準，對連續數值進行離散化，并遞歸生成一個判定樹［8］。

C4.5算法策略如下：1）判定樹以代表訓練樣本的單個節點開始；2）如果樣本都在同一個類，則該節點成為樹葉，并用該類標記；3）否則，使用稱為信息增益率的基于熵的度量作為啟發信息，選擇最好將樣本分類的屬性作為該節點的“測試”或“判定”屬性；4）對測試屬性的每個已知的值，創建一個分枝，并以此為根據劃分樣本；5）使用同樣的過程，遞歸地形成每個劃分上的樣本判定樹。當出現下列情況時停止遞歸劃分：給定節點的所有樣本屬于同一類：沒有剩余屬性可以用來進一步劃分樣本；沒有剩余樣本。

C4.5算法對于連續性數值進行基于增益率劃分為不同區間，從而完成離散化操作。首先使用快速排序算法對屬性值進行排序，然后計算信息增益，并確定最大信息增益為局部閾值，在用順序查找的方法尋找最接近但不超過局部閾值的實際數值為該連續屬性的分割閾值。

在樹的每個節點使用信息增益率的度量選擇測試屬性，選擇具有最高信息增益的屬性作為當前節點的劃分屬性。假設S是s個數據樣本的集合，類標號屬性具有m個不同值（或連續屬性分割為m個數值區間），定義m個不同的類Ci（i為正整數），si是類Ci中的樣本數。那么對給定樣本的期望信息為

其中Pi為任意樣本屬于Ci的概率，假設Pi估計為s1／s。

對于分類屬性A，假設具有v個不同的值（a1，a2，…，av），那么數據樣本總集合S可以劃分為v個子集（s1，s2，…，sv），其中Sj是S中具有aj的樣本，sij是子集Sj中Ci的樣本數。那么，在屬性A上劃分子集的熵為

那么，針對屬性A劃分的信息增益為

屬性A對類別集合C的信息增益率為

針對在關系數據庫水印技術中的具體應用，對C4.5決策樹算法進行優化改進，主要集中在兩個方面：一是引入模糊數學方法改進連續數值分割方法；二是建立決策樹子樹剪割原則，優化決策樹結構。

在采用常規方法根據最大增益求得分割的最大閾值，在此基礎上引入模糊隸屬函數方法的三角函數法［9］，既根據C4.5基本方法準確分割決策樹又能減少計算量并有效提高后續數據庫水印的魯棒性。三角模糊數引入連續值分割先要對分割最大閾值進行模糊化處理，假設某屬性C的分割最大閾值為VGmax，對于屬性C中取值最小值Vmin和最大值Vmax，那么屬性分為｛Vmin，VGmax｝和｛VGmax，Vmax｝兩個部分，并針對性求得兩個部分的最大分割閾值VGmax1和VGmax2。對于屬性C的最大分割閾值VGmax分〈a1λ，VGmax1，β1λ〉和〈a2λ，VGmax2，β2λ〉兩個部分，其中a1＝VGmax1-Vmin1，a2＝VGmax2-Vmin2，β1 ＝Vmax1-VGmax1，β2 ＝Vmax2-VGmin2，λ為三角模糊系數λ∈［0，1］。通過調整λ的大小控制閾值劃分區間的大小，從而控制劃分子樹的大小。

在關系數據庫的水印技術應用中，根據嵌入水印位數W的不同，以及數據庫嵌入比例r的不同，對決策樹子樹大小有一定要求，從而提供一種子樹剪割原則，即作為n層決策樹的第i層葉子節點，符合該節點屬性的元組數m應當滿足公式：

即當符合某節點屬性要求的元組數目小于上公式要求時，即可剪除該子樹不再繼續進行分割劃分，從而有效提高決策樹構建速度。

4 水印嵌入算法

對數據庫數據進行水印信息嵌入，主要針對文本和數值兩種類型數據進行嵌入，為了確保關系完整性和數據準確性，采用不同的嵌入方法和數據對象篩選原則。

4.1 文本型數據嵌入方法

對于文本型數據水印嵌入，為了確保水印信息的隱蔽性，采用在文本數據最后加入“空格”方法實現水印嵌入。當水印序列為“0”時，該元組屬性文本數據結尾不加入空格；當水印序列為“1”時，該元組屬性文本數據結尾加入空格。在水印檢測時，通過比較文本長度和空格位置，當兩者一致時則提取“0”，否則，當兩者不一致時提取“1”。

4.2 數值型數據嵌入方法

對于數值型數據水印嵌入，主要利用數值型數據的最低有效位（LSB）進行嵌入，基本要求是數值型數據的字段長度低于最低有效位數，根據長度相差多少確定嵌入信息量的大小，可以填充信息的位數成為可填充位。這里主要嵌入三種信息，一是水印信息，二是奇偶校驗信息，三是漢明糾錯碼信息，根據可嵌入最低有效位的位數來按照重要性依次嵌入三種不同信息：

1）水印信息嵌入

根據要嵌入屬性Ai的各元組有效位，選擇要嵌入水印最低有效位r，根據要嵌入水印序列信息，為“1”時嵌入1，為“0”時嵌入0，對于某元組該屬性的最低有效位q（q＜r），將其中q～r位用0填充。

2）奇偶校驗信息嵌入

在嵌入水印信息后，如果仍有可填充位，那么結合數據信息的奇偶數，對填充進行填充。如果校驗的數據中有奇數個奇數，那么填充“1”，如果有偶數個奇數，那么填充“0”。

3）漢明碼嵌入

漢明碼是一種能自動檢測并糾正一重錯的線性糾錯碼［10］，設數據位數為m，校驗位數為k，總編碼數為n＝m＋k，那么根據漢明不等式：

采用（7，4）分組碼最小碼距d＝3，能夠糾1個錯或檢2個錯，假設A＝a1a2a3a4，那么添加校驗位a5＝a1＋a2＋a3，a6＝a2＋a3＋a4，a7＝a1＋a3＋a4，其中“＋”表示位的“與”運算，最后構造含有糾錯位的漢明碼為A＝a1a2a3a4a5a6a7。根據漢明糾錯編碼要求，按照屬性數值數據進行漢明編碼添加在填充位中。

那么假設某元組屬性數據為7.04，該屬性所有元組最低有效位為0.001，定義長度為16，分析有效填充位為7位，水印信息為1，根據水印嵌入算法，那么按照步驟1，q＝2，r＝4，在第5位嵌入1，空余為嵌入0，得到7.0401。按照步驟2，數值數據7.0401中共有奇數個奇數，應該填充1，得到數據7.04011，最后對數據7.04011按照（7，4）漢明編碼，對7.04011按照4位分組編碼根據漢明編碼，并轉換為8進制數據，得到最后編碼數據7.0401186。

5 基于決策樹的數據庫脆弱水印技術

5.1 一種新的數據庫脆弱水印模型

關系數據庫水印技術主要包括關系數據庫水印嵌入系統和水印提取和檢測系統。為了模型描述方便，假設對象關系數據庫為R＝（P，A1，A2，…An），其中P為數據庫中的主鍵，即為不變屬性，也表示為最大意義屬性MSA，Ai（0＜i＜n＋1，i為自然數）為其他屬性［11］，這里可以是數值型也可以是文本型。W為構造的K位水印，β為從關系數據庫中構造提取水印序列的算法。那么應當有：

這里重點對數據庫水印模型的脆弱水印構造算法進行研究。脆弱水印構造算法基本思想是采用改進的C4.5決策樹算法對關系數據庫屬性Ai進行分劃，根據分劃后的分組，分組中對元組屬性P經引入密鑰η，結合水印W的位數K，和進行排序變換的MSA 屬性P，進行hash（η，K，P）函數變換［12］進行排序，然后按照水印W逐步嵌入到各個元組的屬性Ai中。其基本步驟為

Step1：

對除MSA 屬性P外的屬性Ai進行C4.5算法決策樹構建，形成Ai：｛（a1，a2），（a3，a4），…｝的子樹劃分結構，針對Ai的屬性數據類型不同分為三種劃分方法：

1）對于離散型數據，直接按照較多離散點進行劃分；

2）對于連續性數值數據，采用第3節中改進型分割最大閾值方法進行劃分；

3）對于文本數據，通過length（）等函數進行轉變為連續的數值數據，按方法1或2進行。

Step2：

對Ai劃分的n個分組，各個分組采用hash（η，K，P）函數進行變換，根據沖突情況定義“0”，“1”，根據按水印W序列進行元組排序，并記錄MSA 屬性P的序列。

Step3：

各個分組中對各個屬性進行水印W的嵌入，其中文本型數據按照4.1節方法嵌入，數值型數據按照4.2節方法嵌入并根據可嵌入位多少選擇性進行校驗位的嵌入。

Step4：

對于關系數據庫R中的其他屬性，按照step2，step3的方法，進行多組的W水印的嵌入。

在數據庫水印檢測中，通過存儲的決策樹分組方法對數據庫元組數據分組，然后屬性P的序列按照hash（η，K，P）變換，生成根據元組提取的水印序列W0，并與水印W進行比較得到篡改的元組，隨后對除去篡改元組的其余元組數據屬性按照水印嵌入算法進行逆向提取，通過大數選舉［13］和與標準水印W比較，得到篡改的屬性，從而確定數據庫中篡改的元組和屬性。

5.2 算法分析

關系數據庫的脆弱水印算法的評價標準主要是：隱蔽性、安全性、敏感性、較大的水印容量和較低復雜度［14］。本算法通過在C4.5算法中引入模糊三角函數并根據水印信息量制定剪切子樹原則，提高決策樹構建靈活度和速度。并利用改進型C4.5算法對關系數據庫屬性進行分割構建決策樹，通過對屬性分割子樹的MSA 屬性進行hash變換嵌入水印并進行檢測確定篡改元組，并在各屬性中的可嵌入位嵌入水印信息和相關校驗位進行檢測定位篡改屬性，分析優點在于：

1）敏感性高：通過分組對篡改元組列進行定位，并通過屬性數據中的水印信息、糾錯碼等進行屬性檢測和定位，能夠有效進行篡改定位。

2）適用范圍廣：本算法適用于數值型、文本型等不同數據類型屬性水印算法構建，具有更加廣泛適用性。

3）對原數據影響?。和ㄟ^對原始數據添加空格和在最低有效位嵌入方法，對原始數據影響有限。

4）具有較高的隱蔽性、安全性和較大的水印容量、較低復雜度。

6 結語

本文提出了一種新的關系數據庫脆弱水印模型，該模型是基于改進型C4.5決策樹算法進行關系數據庫脆弱水印構建，重點研究了脆弱水印構建算法實現，并定性分析了該算法優點。通過研究分析發現，對比傳統的關系數據庫水印算法，本文提出新的關系數據庫脆弱水印算法能夠有效檢測數據庫篡改的位置，具備適用性強、較好的隱蔽性、安全性和敏感性。

［1］胡斌.關系數據庫數字水印技術的研究與應用［D］.長沙：中南大學圖書館，2007：23-25.

［2］Agraw R，Kieman J.Watermarking relation database［C］／／Proceeding of the 28th VLDB Conference.Hong Kong：Hong Kong University of Science＆Technology，2002：155-166.

［3］Radu S，Mikhail A，Suni P.Rights protection for relational data［C］／／Proceeding of the 2003 ACM SIGMOD International Conference on Management of Data.San Diego，California：ACM SIGMOD，2003：98-109.

［4］牛夏牧，趙亮，黃文軍，等.利用數字水印技術實現數據庫的版權保護［J］.電子學報，2003，31（12A）：2050-2054.

［5］Huiping Guo，Yingjiu Li，Anyi Liu，et al.A fragile watermark-ing scheme for detecting malicious modifications of database relations［J］.Information Sciences，2006，176（10）：1350-1378.

［6］張立忠，蔣楠，張洋.基于關系數據庫的脆弱性水印算法研究［J］.計算機工程與應用，2008，44（29）：157-160.

［7］Quinlan J R.Induction of decision tree［J］.Machine learning，1986（1）：81-86.

［8］Quinlan J R.C4.5：Programs for machine learning［M］.San Mateo：Morgan Kaufmann Publishers Inc，1993：17-42.

［9］楊綸標，高英儀.模糊數學原理及應用［M］.廣州：華南理工大學出版社，2001：50-55.

［10］陳惠明.一種具有糾錯能力的半脆弱水印算法［J］.計算機技術與發展，2012，22（4）：242-245.

［11］張浩，黃敏，曹加恒.數據庫水印中的標記算法［J］.計算機應用研究，2005：42-44.

［12］黃子龍，張政保，文家福，等.一種基于Hash函數的脆弱水印算法［J］.計算機技術與發展，2011，21（2）：151-154.

［13］蒙應杰，吳超，張文，等.關系數據庫零水印注冊方案的研究［J］.計算機工程，2007，33（2）：133-136.

［14］武榮，曹加恒，黃敏，等.關系數據庫的數字水印新技術［J］.武漢大學學報，2005，51（5）：589-593.

［15］王娟.數字圖像脆弱水印現狀研究［J］.計算機與數字工程，2009（10）.