龍 曉 泉

(中移互聯(lián)網(wǎng)有限公司 廣東 廣州 510640)

基于SVR預(yù)測的可逆數(shù)據(jù)庫水印技術(shù)

龍 曉 泉

(中移互聯(lián)網(wǎng)有限公司 廣東 廣州 510640)

頻繁模式樹(FP-tree)的關(guān)聯(lián)規(guī)則是利用數(shù)據(jù)挖掘算法來確定受保護(hù)的屬性和其他數(shù)據(jù)庫之間存在的關(guān)系，支持向量回歸方法(SVR)用來預(yù)測每個(gè)受保護(hù)的屬性值。提出通過嵌入原始數(shù)據(jù)庫的重要特征來檢測數(shù)據(jù)庫是否被篡改過的實(shí)現(xiàn)方法。通過對(duì)比差值擴(kuò)展(DE)的原始值和預(yù)測值之間的差異，數(shù)據(jù)庫管理員可以在受保護(hù)的數(shù)據(jù)庫中嵌入數(shù)字水印，如果受保護(hù)的數(shù)據(jù)庫是扭曲的，在SVR功能下仍然是可以預(yù)測保護(hù)值的。FP-tree挖掘方法用于降低SVR的訓(xùn)練時(shí)間，如果該數(shù)據(jù)庫已被篡改，我們可以從受保護(hù)的數(shù)據(jù)庫中提取水印，來驗(yàn)證并定位篡改元組，恢復(fù)原來的屬性值，如果該數(shù)據(jù)庫沒有遭到攻擊，我們也可以利用水印保護(hù)數(shù)據(jù)庫。因此，提出的數(shù)據(jù)庫的電子水印方式可以有效地驗(yàn)證數(shù)據(jù)庫的完整性和保護(hù)數(shù)據(jù)庫的安全性。

數(shù)據(jù)庫水印 差值擴(kuò)展 支持向量回歸 FP-tree挖掘

0 引 言

在現(xiàn)實(shí)生活中，個(gè)人和組織都喜歡將一些數(shù)字信息存儲(chǔ)在數(shù)據(jù)庫中，便于管理。由于這些信息包含與重要決策相關(guān)的數(shù)據(jù)，因此保護(hù)數(shù)據(jù)庫免受篡改是一個(gè)重要的問題[1]。近年來，研究人員已經(jīng)開發(fā)了數(shù)據(jù)庫水印技術(shù)，把數(shù)字水印嵌入數(shù)據(jù)庫中，使得數(shù)據(jù)庫中的保護(hù)列將允許檢測是否被篡改。

在數(shù)據(jù)庫中嵌入數(shù)字水印，應(yīng)確保和保護(hù)通過使用水印技術(shù)存儲(chǔ)在數(shù)據(jù)庫中的所有列的決策數(shù)據(jù)的正確性和一致性。然而，如果數(shù)字水印嵌入在列中，并且列中的值需要修改，那么數(shù)字決策數(shù)據(jù)可能會(huì)失真，這將導(dǎo)致出現(xiàn)不正確的決策數(shù)據(jù)[2]。

在數(shù)據(jù)庫中，存儲(chǔ)的數(shù)字決策數(shù)據(jù)不允許失真，并且決策數(shù)據(jù)庫中的數(shù)據(jù)不能隨意修改。雖然目前的嵌入式水印技術(shù)可以驗(yàn)證列的正確性，但是不能恢復(fù)原始的數(shù)字?jǐn)?shù)據(jù)[3]。因此，本文針對(duì)SVR技術(shù)，將數(shù)字水印嵌入在數(shù)字決策數(shù)據(jù)庫中，驗(yàn)證是否可以恢復(fù)原來的數(shù)字?jǐn)?shù)據(jù)。

有些人通過使用獨(dú)特的特征來表示關(guān)系數(shù)據(jù)，給數(shù)字水印帶來新的挑戰(zhàn)。通過提取嵌入的數(shù)字水印來檢測數(shù)據(jù)庫是否被篡改[4-5]。嵌入的水印可以用于任何關(guān)系數(shù)據(jù)庫。然而，如果發(fā)生篡改攻擊，向數(shù)據(jù)庫插入新屬性，那么提取的水印可能不正確。

還有些人提出了一種通過在數(shù)據(jù)庫中建立附加信息的索引表來嵌入水印的數(shù)據(jù)庫水印技術(shù)[6-7]。通過改變索引表中的序列而不改變數(shù)據(jù)表中內(nèi)容的值來嵌入水印。因此，在數(shù)據(jù)庫中的內(nèi)容不會(huì)受影響，并且在嵌入水印之后無需修改。然而，由于索引值是在數(shù)據(jù)庫內(nèi)容上的附加信息，如果索引值被刪除或重新建立，水印有可能是錯(cuò)誤的或可能會(huì)完全消失[8]。

為了解決上述問題，本文所提出的方法是，通過使用FP-tree的數(shù)據(jù)挖掘來保護(hù)數(shù)字決策數(shù)據(jù)庫中的重要列，從而過濾掉受保護(hù)列和其他列之間的關(guān)系。在許多用于數(shù)據(jù)挖掘技術(shù)的方法中，F(xiàn)P-tree的數(shù)據(jù)挖掘在實(shí)際運(yùn)行中已經(jīng)顯示出高水平的效率。因此，F(xiàn)P-tree技術(shù)已成為最常見的數(shù)據(jù)挖掘方法。FP-tree的數(shù)據(jù)挖掘技術(shù)主要統(tǒng)計(jì)數(shù)據(jù)庫中列的出現(xiàn)次數(shù)[9]。列出現(xiàn)的次數(shù)越多，說明越重要。我們需要做的就是選定重要的列，建立一個(gè)樹形結(jié)構(gòu)以防止多次掃描、節(jié)省時(shí)間[10]。

接著，在SVR中，通過FP-tree的數(shù)據(jù)挖掘中所選擇列的值來計(jì)算保護(hù)列的預(yù)測值。通過預(yù)測值和原始保護(hù)列之間的差異，以及回歸差值擴(kuò)展(RDE)，將水印嵌入保護(hù)列中。該方法的優(yōu)點(diǎn)在于區(qū)分有數(shù)字水印的數(shù)字?jǐn)?shù)據(jù)庫和原始數(shù)據(jù)庫之間的微小差異[11]。因此，該方法可確定決策數(shù)據(jù)庫中的值是否已被惡意篡改，并確定已被篡改的列。相反，如果嵌入有水印的數(shù)字決策數(shù)據(jù)庫沒有被篡改，則列中的值可以恢復(fù)為具有RDE的原始值。這種方法具有非常好的檢出率。

1 解決方案

在該方案中，通過使用FP-tree的數(shù)據(jù)挖掘改進(jìn)了數(shù)據(jù)庫表中重要特征。然后，將挖掘結(jié)果中受保護(hù)字段的相關(guān)重要特征進(jìn)一步由SVR來預(yù)測保護(hù)。因此，可以計(jì)算每條記錄中保護(hù)字段的預(yù)測值和原始值之間的差。另一方面，DE是一種可逆的隱藏方案。提出了基于DE可逆水印的基本方法來選擇嵌入目標(biāo)值。通過這個(gè)目標(biāo)值和最低有效位(LSB)的替換方式，將結(jié)果更新到表中。所提出的技術(shù)方案如圖1所示。

圖1 SVR培訓(xùn)和嵌入程序圖

1.1 FP-tree 特征挖掘

在開始階段，原始數(shù)據(jù)庫O的重要特征是選擇使用FP-tree的數(shù)據(jù)挖掘技術(shù)。FP-tree結(jié)構(gòu)可以找出受保護(hù)屬性的關(guān)聯(lián)特征。首先，計(jì)算特征的數(shù)量。其次，為頻繁屬性創(chuàng)建樹形結(jié)構(gòu)。

步驟1計(jì)算每個(gè)屬性值的頻率。

步驟2為數(shù)據(jù)庫O構(gòu)建FP-tree。

表1是在超市中交易表的例子；編號(hào)列表示不同購買者；購買項(xiàng)目代表交易數(shù)據(jù)；頻繁項(xiàng)使用統(tǒng)計(jì)后的支持度閾值方法進(jìn)行過濾。假設(shè)最小支持度閾值為3。支持度模式為a，其中a表示一組項(xiàng)目，是包含在事務(wù)數(shù)據(jù)庫中的事務(wù)數(shù)目。

表1 事務(wù)表的例子

例如，集合收集頻繁項(xiàng)如下：

<(a:3),(b:3),(c:4),(d:1),(e:1),)(f:4),(g:1),(h:1),(i:1),(j:1),(k:1),(l:2),(m:3),(n:1),(o:2),(p:3),(s:1)>，在該集合中，c表示特征，數(shù)字4表示支持度。此購買項(xiàng)目的訂單很重要，因?yàn)闃涞拿總€(gè)路徑都將遵循此順序。頻繁項(xiàng)會(huì)通過最小支持度閾值過濾。

首先，會(huì)對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行掃描導(dǎo)出一個(gè)頻繁項(xiàng)的列表。其次，會(huì)對(duì)一個(gè)空的樹創(chuàng)建根值。在編號(hào)1中插入這些頻繁項(xiàng)目集合<(f:1),(c:1),(a:1),(m:1),(p:1)>得到如圖2(a)所示的樹。在編號(hào)2中插入這些頻繁項(xiàng)目集合<(f:1),(c:1),(a:1),(b:1),(m:1)>得到如圖2(b)所示的樹。由于在路徑(f,c,a,m,p)中存在頻繁項(xiàng)目(f,c,a)，所以頻繁項(xiàng)目列表中的每個(gè)節(jié)點(diǎn)的數(shù)目就增加1，新創(chuàng)建的(b:1)節(jié)點(diǎn)就作為(a:2)的子節(jié)點(diǎn)鏈接。

在編號(hào)5中插入這些頻繁項(xiàng)目集合<(f:1),(c:1),(a:1),(m:1),(p:1)>得到如圖2(c)所示的樹，并構(gòu)造最終的FP-tree。

圖2 集合收集頻繁項(xiàng)目順序圖

1.2 SVR訓(xùn)練算法

在上述理論基礎(chǔ)上，F(xiàn)P-tree中的屬性存儲(chǔ)在表X中。接下來，表X中的重要特征被選擇用于訓(xùn)練過程。使用SVR可以涉及訓(xùn)練樣本，并從SVR獲得訓(xùn)練函數(shù)f(Y)。

輸入：數(shù)據(jù)庫O和表X與屬性A1，A2，…，Ag；

輸出：訓(xùn)練后的SVR函數(shù)f(Y)。

步驟1使用表X中的屬性來預(yù)測數(shù)據(jù)庫O中的受保護(hù)屬性。訓(xùn)練數(shù)據(jù)集T可以表示為：T={sj|sj={A1,j,A2,j,…,Ag,j},j=1, 2,…,n}。其中：sj被定義為數(shù)據(jù)庫O中的第j個(gè)選擇的訓(xùn)練元組。

步驟2通過使用訓(xùn)練元組T來訓(xùn)練SVR模型以獲得SVR函數(shù)f(Y)。

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

在這個(gè)階段，對(duì)于數(shù)據(jù)庫O中的受保護(hù)目標(biāo)屬性U，提出在水印嵌入過程使用數(shù)據(jù)庫O和SVR預(yù)測函數(shù)f(Y)中的目標(biāo)屬性U使用差值擴(kuò)展(DE)來嵌入水印。水印W可以被分成1-LSB位，2-LSB位或3-LSB位，用于嵌入到修改后的U中。

輸入：數(shù)據(jù)庫O，經(jīng)過訓(xùn)練的SVR函數(shù)f(Y)和水印W；

輸出：嵌入到數(shù)據(jù)庫O′。

第一步將目標(biāo)值Ui與訓(xùn)練的SVR函數(shù)值f(yi)進(jìn)行比較。如果Ui小于f(yi)，則定義di=f(yi)-Ui，并且轉(zhuǎn)到第二步；否則定義di=Ui-f(yi)并轉(zhuǎn)到第三步。實(shí)驗(yàn)數(shù)據(jù)假定Ui為16，f(yi)為7，則di為9。

第四步重復(fù)第一步至第三步，直到所有的水印信息都嵌入到數(shù)據(jù)庫O中，并獲得水印數(shù)據(jù)庫O′。

1.4 數(shù)據(jù)庫水印的提取

在我們提出的方案中，為了驗(yàn)證數(shù)據(jù)庫的內(nèi)容，通過數(shù)據(jù)挖掘可以發(fā)現(xiàn)重要的特征，并且使用SVR來預(yù)測f(Y)。我們使用DE的概念從受保護(hù)的目標(biāo)值中提取嵌入的水印。并獲得水印和目標(biāo)值。如果水印已經(jīng)被破壞，則該數(shù)據(jù)庫被篡改。否則，數(shù)據(jù)庫將顯示原始值。數(shù)據(jù)庫水印提取的過程如圖3所示。

圖3 檢測與恢復(fù)過程圖

輸出：懷疑的水印W′。

第二步訓(xùn)練SVR模型通過訓(xùn)練元組集T′獲得SVR函數(shù)f(Y)。

第七步將提取的水印和原始水印進(jìn)行比較，以確定數(shù)據(jù)庫是否被篡改。

2 實(shí)驗(yàn)結(jié)果與分析

在實(shí)驗(yàn)結(jié)果中，兩個(gè)不同的數(shù)據(jù)庫虹膜(Iris)和鮑魚(Abalone)，被用作測試數(shù)據(jù)庫。其中第二個(gè)鮑魚是使用FP-tree數(shù)據(jù)挖掘進(jìn)行測試。使用FP-tree數(shù)據(jù)挖掘方法可以極大提升檢出率。

采用的SVR工具是LIBSVM。虹膜數(shù)據(jù)庫有150個(gè)元組和5個(gè)屬性。訓(xùn)練參數(shù)包括可平衡參數(shù)C(C=3)和最小擬合誤差ε(ε=0.1)；訓(xùn)練元組的數(shù)目為150。這些屬性包括：萼片長度、萼片寬度、花瓣長度、花瓣寬度和類別。實(shí)驗(yàn)結(jié)果如表2所示。

表2 改裝“Iris數(shù)據(jù)庫”的實(shí)驗(yàn)結(jié)果

鮑魚數(shù)據(jù)庫的元組數(shù)為4 096，有8個(gè)屬性。屬性包括：性別、長度、直徑、高度、整體重量，、脫殼重量、臟器重量和殼重。平衡參數(shù)C(C=3)和最小擬合誤差ε(ε=0.1)，訓(xùn)練元組數(shù)為1 000。實(shí)驗(yàn)結(jié)果如表3所示。

表3 改裝“Abalone數(shù)據(jù)庫”的實(shí)驗(yàn)結(jié)果

由表2、表3的結(jié)果得出，在Abalone數(shù)據(jù)庫的中，嵌入1-LBS的水印平均檢測率為58.5%；嵌入2-LBS的水印接近88%；嵌入3-LBS的水印接近98.8%。與Iris數(shù)據(jù)庫相比，它在元組復(fù)雜度提高26倍的情況下，依然大大提升了檢出率(參見圖4)。

圖4 實(shí)驗(yàn)結(jié)果對(duì)比(以2-LSBsBits為例)

為了對(duì)比使用FP-tree前后對(duì)數(shù)據(jù)庫防篡改的實(shí)際效果，作者對(duì)虹膜和鮑魚兩個(gè)數(shù)據(jù)庫O1和O2分別實(shí)施了兩組對(duì)照實(shí)驗(yàn)。我們關(guān)注三個(gè)指標(biāo)的對(duì)比分析：

檢測率 = 成功檢出的篡改數(shù)量/總篡改數(shù)量

誤報(bào)率 = 誤報(bào)為異常的數(shù)量/總事件數(shù)

漏檢率 = 漏報(bào)未檢出的篡改數(shù)量/總事件數(shù)

我們?nèi)藶橹圃鞂?duì)目標(biāo)數(shù)據(jù)庫的篡改，對(duì)兩個(gè)數(shù)據(jù)庫進(jìn)行了多組實(shí)驗(yàn)測試，選取兩組典型測試數(shù)據(jù)，第一組數(shù)據(jù)為使用了FP-tree算法訓(xùn)練，第二組數(shù)據(jù)未使用FP-tree算法訓(xùn)練，兩組的操作總數(shù)均為100次，實(shí)驗(yàn)結(jié)果如表4、表5所示。

表4 虹膜數(shù)據(jù)庫O2的實(shí)驗(yàn)結(jié)果

表5 鮑魚數(shù)據(jù)庫O2的實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)結(jié)果中，兩個(gè)不同的數(shù)據(jù)庫兩組對(duì)照實(shí)驗(yàn)數(shù)據(jù)對(duì)比非常明顯，在虹膜數(shù)據(jù)庫中，應(yīng)用了FP-tree算法的檢測率提升12.25%，誤報(bào)率降低2%，漏檢率降低8%。在另一組鮑魚數(shù)據(jù)庫的實(shí)驗(yàn)結(jié)果中，應(yīng)用了FP-tree算法訓(xùn)練的實(shí)驗(yàn)結(jié)果較比未應(yīng)用FP-tree算法的實(shí)驗(yàn)數(shù)據(jù)檢測率提升22.12%，誤報(bào)率降低1%，漏檢率降低7%。

這意味著幾乎所有被篡改的數(shù)據(jù)都可以被成功檢測和定位。實(shí)驗(yàn)結(jié)果表明，上述提出的方法確實(shí)可以保持?jǐn)?shù)據(jù)庫內(nèi)容的完整性。值得注意的是，通過前面的數(shù)據(jù)挖掘，我們可以減少SVR在后續(xù)步驟中的訓(xùn)練時(shí)間。假設(shè)數(shù)據(jù)維度是相當(dāng)高的，我們要找出重要的特征?？梢韵仍跀?shù)據(jù)沒有被篡改的情況下，建議通過程序來恢復(fù)原始值。在恢復(fù)過程中，可以通過預(yù)測值和li來獲得原始的目標(biāo)屬性。總的來說，恢復(fù)數(shù)據(jù)庫的內(nèi)容是這個(gè)新方法中最重要的特征。它可以有效地降低管理成本。

3 結(jié) 語

在本文中，我們提出了一種基于SVR預(yù)測的可逆水印算法，該算法使用FP-free的數(shù)據(jù)挖掘方法，用來驗(yàn)證數(shù)據(jù)庫的內(nèi)容。首先，使用FP-free關(guān)聯(lián)規(guī)則挖掘重要特征，關(guān)聯(lián)規(guī)則將會(huì)選擇最相關(guān)的一個(gè)數(shù)據(jù)。此數(shù)據(jù)的特征將被用于SVR的預(yù)測，這種方法的主要目的是為了防止在SVR預(yù)測期間維度很高時(shí)，訓(xùn)練時(shí)間會(huì)變得太長。因此，通過關(guān)聯(lián)規(guī)則的挖掘，該方法可以大大減少因SVR訓(xùn)練造成的時(shí)間浪費(fèi)。在計(jì)算SVR預(yù)測與原始值之間差異時(shí)，我們可以使用DE方法作為嵌入數(shù)字水印的基本概念。如果數(shù)據(jù)庫受到攻擊并被惡意篡改，則SVR預(yù)測值可能會(huì)產(chǎn)生差異；我們可以用這種方法提取水印，然后計(jì)算和定位被攻擊的記錄。在不被攻擊的情況下，可以通過提取水印來恢復(fù)原始數(shù)據(jù)庫。

[1] 王奎,孫天凱,丁賓.脆弱水印技術(shù)在關(guān)系數(shù)據(jù)庫保護(hù)中的應(yīng)用研究[J].福建電腦,2012,28(11):16-17.

[2] 周飛,趙懷勛.基于混沌的DCT域關(guān)系數(shù)據(jù)庫水印算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(2):786-788.

[3] 高領(lǐng)云.關(guān)系數(shù)據(jù)庫脆弱性數(shù)字水印技術(shù)的研究[D].湖南:湖南大學(xué),2013.

[4] 劉芳,汪玉凱.一種基于差值直方圖平移的多層可逆水印算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(1):303-307.

[5] 劉瑞.可逆水印技術(shù)及其在加密域的研究算法[D].北京:北京交通大學(xué),2015.

[6] 陳進(jìn)東,潘豐.基于在線支持向量回歸的非線性模型預(yù)測控制方法[J].控制與決策,2014(3):460-464.

[7] Clarke S M,Griebsch J H,Simpson T W.Analysis of Support Vector Regression for Approximation of Complex Engineering Analyses[C]//ASME 2003 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference.American Society of Mechanical Engineers,2005:1077-1087.

[8] Choi W Y,Choi D H,Cha K J.Robust estimation of support vector regression via residual bootstrap adoption[J].Journal of Mechanical Science & Technology,2015,29(1):279-289.

[9] 李少華,呂志旺,車德勇,等.基于有序FP-tree的最大頻繁項(xiàng)集挖掘算法[J].東北師大學(xué)報(bào)(自然科學(xué)),2016,48(2):65-69.

[10] 吳倩.基于壓縮FP-tree的頻繁項(xiàng)集快速挖掘算法研究[D].上海:華東理工大學(xué),2015.

[11] 付冬梅,王志強(qiáng).基于FP—tree和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法及應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(4):1013-1015.

REVERSIBLEDATABASEWATERMARKINGTECHNOLOGYBASEDONSVRPREDICTION

Long Xiaoquan

(ChinaMobileInternetCompanyLimited,Guangzhou510640,Guangdong,China)

The association rule of FP-tree (frequent pattern tree) uses data mining algorithm to determine the relationship between protected property and other databases. SVR (Support vector regression) method is used to predict each protected attribute value. We propose a method to detect whether the database has been tampered with by embedding the important feature of the original database. By comparing the difference between original and predicted values of the DE (difference expansion), the database administrator can embed digital watermark in a protected database. If the protected database is distorted, it is still possible to predict the protection value under the SVR function. In this paper, FP-tree mining method is used to reduce the training time of SVR. If the database has been tampered with, we can extract the watermark from the protected database to verify and locate the tampered tuples and restore the original attribute value. If the database is not under attack, we can also use the protection of database watermarking. Therefore, the database can effectively verify the integrity of the database and protect the security of the database.

Database watermarking Difference expansion Support vector regression FP-tree mining

2016-11-05。龍曉泉，碩士，主研領(lǐng)域：數(shù)據(jù)庫技術(shù)。

TP3

A

10.3969/j.issn.1000-386x.2017.12.012