基于決策樹的數(shù)據(jù)庫脆弱水印算法研究＊

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

1 引言

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

文章主要對(duì)關(guān)系數(shù)據(jù)庫脆弱水印技術(shù)進(jìn)行研究，在保護(hù)數(shù)據(jù)庫數(shù)據(jù)準(zhǔn)確性基礎(chǔ)上，按照決策樹算法分組，并對(duì)利用元組屬性數(shù)據(jù)最低有效位采用漢明碼編碼等方法進(jìn)行數(shù)據(jù)檢測，并嵌入水印信息實(shí)現(xiàn)數(shù)據(jù)庫脆弱水印的構(gòu)建。

2 數(shù)字水印技術(shù)

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

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

3 改進(jìn)型C4.5決策樹

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

為了解決ID3算法不足，Quinlan在1993年在繼承決策樹基本構(gòu)造思想基礎(chǔ)上提出C4.5算法，該算法用信息增益率代替信息熵作為選擇分裂屬性的標(biāo)準(zhǔn)，對(duì)連續(xù)數(shù)值進(jìn)行離散化，并遞歸生成一個(gè)判定樹［8］。

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

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

在樹的每個(gè)節(jié)點(diǎn)使用信息增益率的度量選擇測試屬性，選擇具有最高信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的劃分屬性。假設(shè)S是s個(gè)數(shù)據(jù)樣本的集合，類標(biāo)號(hào)屬性具有m個(gè)不同值（或連續(xù)屬性分割為m個(gè)數(shù)值區(qū)間），定義m個(gè)不同的類Ci（i為正整數(shù)），si是類Ci中的樣本數(shù)。那么對(duì)給定樣本的期望信息為

其中Pi為任意樣本屬于Ci的概率，假設(shè)Pi估計(jì)為s1／s。

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

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

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

針對(duì)在關(guān)系數(shù)據(jù)庫水印技術(shù)中的具體應(yīng)用，對(duì)C4.5決策樹算法進(jìn)行優(yōu)化改進(jìn)，主要集中在兩個(gè)方面：一是引入模糊數(shù)學(xué)方法改進(jìn)連續(xù)數(shù)值分割方法；二是建立決策樹子樹剪割原則，優(yōu)化決策樹結(jié)構(gòu)。

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

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

即當(dāng)符合某節(jié)點(diǎn)屬性要求的元組數(shù)目小于上公式要求時(shí)，即可剪除該子樹不再繼續(xù)進(jìn)行分割劃分，從而有效提高決策樹構(gòu)建速度。

4 水印嵌入算法

對(duì)數(shù)據(jù)庫數(shù)據(jù)進(jìn)行水印信息嵌入，主要針對(duì)文本和數(shù)值兩種類型數(shù)據(jù)進(jìn)行嵌入，為了確保關(guān)系完整性和數(shù)據(jù)準(zhǔn)確性，采用不同的嵌入方法和數(shù)據(jù)對(duì)象篩選原則。

4.1 文本型數(shù)據(jù)嵌入方法

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

4.2 數(shù)值型數(shù)據(jù)嵌入方法

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

1）水印信息嵌入

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

2）奇偶校驗(yàn)信息嵌入

在嵌入水印信息后，如果仍有可填充位，那么結(jié)合數(shù)據(jù)信息的奇偶數(shù)，對(duì)填充進(jìn)行填充。如果校驗(yàn)的數(shù)據(jù)中有奇數(shù)個(gè)奇數(shù)，那么填充“1”，如果有偶數(shù)個(gè)奇數(shù)，那么填充“0”。

3）漢明碼嵌入

漢明碼是一種能自動(dòng)檢測并糾正一重錯(cuò)的線性糾錯(cuò)碼［10］，設(shè)數(shù)據(jù)位數(shù)為m，校驗(yàn)位數(shù)為k，總編碼數(shù)為n＝m＋k，那么根據(jù)漢明不等式：

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

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

5 基于決策樹的數(shù)據(jù)庫脆弱水印技術(shù)

5.1 一種新的數(shù)據(jù)庫脆弱水印模型

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

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

Step1：

對(duì)除MSA 屬性P外的屬性Ai進(jìn)行C4.5算法決策樹構(gòu)建，形成Ai：｛（a1，a2），（a3，a4），…｝的子樹劃分結(jié)構(gòu)，針對(duì)Ai的屬性數(shù)據(jù)類型不同分為三種劃分方法：

1）對(duì)于離散型數(shù)據(jù)，直接按照較多離散點(diǎn)進(jìn)行劃分；

2）對(duì)于連續(xù)性數(shù)值數(shù)據(jù)，采用第3節(jié)中改進(jìn)型分割最大閾值方法進(jìn)行劃分；

3）對(duì)于文本數(shù)據(jù)，通過length（）等函數(shù)進(jìn)行轉(zhuǎn)變?yōu)檫B續(xù)的數(shù)值數(shù)據(jù)，按方法1或2進(jìn)行。

Step2：

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

Step3：

各個(gè)分組中對(duì)各個(gè)屬性進(jìn)行水印W的嵌入，其中文本型數(shù)據(jù)按照4.1節(jié)方法嵌入，數(shù)值型數(shù)據(jù)按照4.2節(jié)方法嵌入并根據(jù)可嵌入位多少選擇性進(jìn)行校驗(yàn)位的嵌入。

Step4：

對(duì)于關(guān)系數(shù)據(jù)庫R中的其他屬性，按照step2，step3的方法，進(jìn)行多組的W水印的嵌入。

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

5.2 算法分析

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

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

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

3）對(duì)原數(shù)據(jù)影響小：通過對(duì)原始數(shù)據(jù)添加空格和在最低有效位嵌入方法，對(duì)原始數(shù)據(jù)影響有限。

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

6 結(jié)語

本文提出了一種新的關(guān)系數(shù)據(jù)庫脆弱水印模型，該模型是基于改進(jìn)型C4.5決策樹算法進(jìn)行關(guān)系數(shù)據(jù)庫脆弱水印構(gòu)建，重點(diǎn)研究了脆弱水印構(gòu)建算法實(shí)現(xiàn)，并定性分析了該算法優(yōu)點(diǎn)。通過研究分析發(fā)現(xiàn)，對(duì)比傳統(tǒng)的關(guān)系數(shù)據(jù)庫水印算法，本文提出新的關(guān)系數(shù)據(jù)庫脆弱水印算法能夠有效檢測數(shù)據(jù)庫篡改的位置，具備適用性強(qiáng)、較好的隱蔽性、安全性和敏感性。

［1］胡斌.關(guān)系數(shù)據(jù)庫數(shù)字水印技術(shù)的研究與應(yīng)用［D］.長沙：中南大學(xué)圖書館，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］牛夏牧，趙亮，黃文軍，等.利用數(shù)字水印技術(shù)實(shí)現(xiàn)數(shù)據(jù)庫的版權(quán)保護(hù)［J］.電子學(xué)報(bào)，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］張立忠，蔣楠，張洋.基于關(guān)系數(shù)據(jù)庫的脆弱性水印算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，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］楊綸標(biāo)，高英儀.模糊數(shù)學(xué)原理及應(yīng)用［M］.廣州：華南理工大學(xué)出版社，2001：50-55.

［10］陳惠明.一種具有糾錯(cuò)能力的半脆弱水印算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2012，22（4）：242-245.

［11］張浩，黃敏，曹加恒.數(shù)據(jù)庫水印中的標(biāo)記算法［J］.計(jì)算機(jī)應(yīng)用研究，2005：42-44.

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

［13］蒙應(yīng)杰，吳超，張文，等.關(guān)系數(shù)據(jù)庫零水印注冊方案的研究［J］.計(jì)算機(jī)工程，2007，33（2）：133-136.

［14］武榮，曹加恒，黃敏，等.關(guān)系數(shù)據(jù)庫的數(shù)字水印新技術(shù)［J］.武漢大學(xué)學(xué)報(bào)，2005，51（5）：589-593.

［15］王娟.數(shù)字圖像脆弱水印現(xiàn)狀研究［J］.計(jì)算機(jī)與數(shù)字工程，2009（10）.