基于語義的Data Cube數(shù)字水印技術(shù)

摘 要: 數(shù)字水印技術(shù)可以有效地保護版權(quán)，數(shù)據(jù)倉庫中用于OLAP(OnLine Analytical Processing，聯(lián)機分析處理)的Data Cube(數(shù)據(jù)立方體，亦稱多維數(shù)據(jù)集)不僅包含有價值的數(shù)據(jù)，而且其設(shè)計模式與分析模式也體現(xiàn)了Data Cube 擁有者的知識產(chǎn)權(quán).將數(shù)字水印技術(shù)引入Data Cube 中，并充分利用Data Cube的語義信息，從而提供一個通用、實用的Data Cube 數(shù)字水印技術(shù)解決方案.

關(guān)鍵詞:數(shù)字水印;語義;數(shù)據(jù)立方體;版權(quán)

中圖分類號: TP311文獻標(biāo)識碼:A

The Watermarking Data Cube Based on Semantic

YANG Ke-hua1， YANG Yu-hua1，2

(1.School of Computer and Communication， Hunan Univ，Changsha，Hunan 410082， China;

2.Hunan Xinhua Water Supply Company，Xinhua，Hunan 417600， China)

Abstract:Digital Watermark can protect copyright effectively. Data Cube， which used for OLAP in Data Warehouse， contains not only valuable data but also design pattern and analytical pattern，which declare the owner’s intellectual property rights. This article provides a common and practical scheme for watermarking Data Cube by merging digital watermark technology into Data Cube and using semantic information of Data Cube fully.

Key words:digital watermarking;semantics;data cube;copyrights

數(shù)字水印技術(shù)^[1]是網(wǎng)絡(luò)環(huán)境下保護版權(quán)的新型技術(shù)，主要是利用數(shù)字產(chǎn)品的數(shù)據(jù)冗余，將產(chǎn)權(quán)等信息作為附加噪聲融合在原數(shù)字產(chǎn)品當(dāng)中以嵌入隱藏信息.

基于數(shù)據(jù)倉庫的OLAP(OnLine Analytical Processing，聯(lián)機分析處理)技術(shù)可以根據(jù)用戶的需要，從不同角度對數(shù)據(jù)進行分析.每個不同的角度代表了數(shù)據(jù)分析中的一個“維”，因此也稱“多維分析”.同時，OLAP 分析也可以提供鉆取等語義操作，能夠提供更多、更豐富的報表和視圖.

Data Cube所包含的數(shù)據(jù)以及其設(shè)計模式、分析模式及語義不僅對于OLAP用戶的分析效率有著非常大的影響，同時也隱藏著許多至關(guān)重要的信息.因此隨著OLAP技術(shù)的廣泛使用，Data Cube面臨著版權(quán)保護與安全控制的問題，也隨之產(chǎn)生了在Data Cube中嵌入水印信息的需求.目前學(xué)術(shù)界的相關(guān)研究都集中在關(guān)系數(shù)據(jù)庫水印技術(shù)上，文獻[23]提出了在關(guān)系數(shù)據(jù)庫中嵌入有實際意義信息的方法，文獻[4]基于中國剩余定理，提出了一種數(shù)據(jù)庫水印技術(shù)，文獻[56]提出關(guān)系數(shù)據(jù)庫水印技術(shù)，由于Data Cube的基表元組一般采用關(guān)系數(shù)據(jù)庫進行存儲，所以這些技術(shù)對于Data Cube中嵌入水印有一定的借鑒意義.但Data Cube的數(shù)據(jù)模型采用的是多維模型，這與關(guān)系數(shù)據(jù)庫的數(shù)據(jù)模型有所不同，目前學(xué)術(shù)界尚未對Data Cube中嵌入數(shù)字水印有專門的研究.同時Data Cube中的各個單元格數(shù)據(jù)之間有一定的層次關(guān)系與語義關(guān)系，Data Cube的設(shè)計與使用方式與傳統(tǒng)關(guān)系數(shù)據(jù)庫均有很大不同.因此本文在對單元格之間的語義關(guān)系進行形式化描述的基礎(chǔ)上，針對Data Cube的特性設(shè)計了一種有實用價值的Data Cube數(shù)字水印技術(shù).

1 基本概念與定義

為了便于說明，我們使用商品銷售表作為事例，基表有三個維(地區(qū)，產(chǎn)品，時間)，其中地區(qū)維有兩個層次(地區(qū)，省)，產(chǎn)品維為單層次維，時間維有兩個層次(年，季度)，度量為(銷售額).基表的一個實例如表1所示.基表所對應(yīng)的Data Cube單元格如表2所示，其中的“*”表示“ALL”.本例中假設(shè)聚集函數(shù)為AVG.

表1 基表T

Tab.1 Base table T

元組

序號地區(qū)地區(qū)省產(chǎn)品

名稱時間年季度銷售額AEasternCTP1200316BEasternCTP22003112CWesternUTP1200339

表2 基表T對應(yīng)的Data Cube Cubesales單元格

Tab.2 Cells in Data Cube Cubesales of base table T

地區(qū)地區(qū)省產(chǎn)品

名稱時間年季度平均值包含的元組EasternCTP1200316AEasternCTP22003112BWesternUTP1200339CEastern*P1200316A**P12003*7.5A，C******A，B，C

定義1(維層次坐標(biāo)聚集關(guān)系∠) 設(shè)Di為DataCube的第i個維，有h個層次，則單元格A在此維上的坐標(biāo)可以記為Ai=[ai1，ai2，…，aih(huán)](aij(1≤j≤h)為各層次上的坐標(biāo)，最高層次坐標(biāo)為ai1，最低層次坐標(biāo)為aih(huán).設(shè)Bi為單元格B在維Di上的坐標(biāo)，定義Bi∠Ai為:當(dāng)且僅當(dāng)存在整數(shù)s≤h+1，使得:

1)對于所有滿足條件0

2)對于所有滿足條件s≤n≤h的整數(shù)n，都有ain=“*”，bin≠“*”.其中*表示ALL.

定義2(DataCube單元格間的聚集關(guān)系) 將單元格A記為[A1，A2，…，Ad，m]的形式(d為維數(shù))，其中m為聚集值，Ai為單元格在第i維上的坐標(biāo)，如定義1所示.則兩個單元格A與B之間的關(guān)系可定義為:[A1，A2，…，Ad，ma][B1，B2，…，Bd，mb]，當(dāng)且僅當(dāng)對于每個i(1≤i≤d)，都有Ai∠Bi.并定義一個在所有的維、層次及度量上取空值的空單元格R1，對于所有單元格R，均有R1R.

單元格間的聚集關(guān)系定義的是某個單元格是否可以由另一個單元格在一個或多個維上進行聚集得到.

定義3(單元格所包含的基表元組集) 對于單元格Cell，如果其聚集值是由基表元組t1，t2，…，tn計算得到，則稱集合{ti|1≤i≤n}為單元格所包含的基表元組集，記做{Cell}，即{Cell}={t1，t2，…，tn}.

湖南大學(xué)學(xué)報(自然科學(xué)版)2010年

第2期楊科華等:基于語義的Data Cube數(shù)字水印技術(shù)

例如，{[(*，*)，P1，(2003，*)，7.5]}={A，C}，而{[(*，*)，*，(*，*)，*]}={A，B，C}.

定理1 單元格間的聚集關(guān)系具有自反性，反對稱性，傳遞性.設(shè)RS為DataCube中所有單元格的集合，則(RS∪R1，)為一個偏序集.證明略.

定理2 對于兩個單元格C1，C2，如果有C1C2，則有{C1}{C2}.證明略.

定義4(單元格的聚集度) 對于一個單元格Cell，設(shè)其第i個維坐標(biāo)上包含“*”(或ALL)的個數(shù)為Aggi，則此單元格的聚集度記為|Cell|，且|Cell|=∑di=1Aggi(d為維數(shù)).

定義5(單元格的路徑) 對于DataCube中的某個單元格Cellk(k為此單元格聚集度)，任取基表元組t∈{Cellk}，且Cell0為基表元組t所對應(yīng)的單元格，如果存在單元格序列Cell0Cell1…Cellk-1Cellk，使得任取整數(shù)0≤i

由定理1及定理2可知，DataCube的任一單元格都具有至少一條路徑，并且由定義可知，這也是一條關(guān)系下的最長路徑.

2 水印信息的嵌入與驗證

在嵌入水印之前，需要首先對基表元組進行編號，為了保證算法的魯棒性，還必須在編號時引入一個密鑰值Key，我們使用文獻[7]中的單向hash函數(shù)來計算編號.對于基表元組T，用εcell來表示某個單元格度量值誤差范圍內(nèi)允許嵌入水印信息的最低有效位數(shù)，并設(shè)其所有屬性值字符串方式連接的二進制串為T.str，度量值為T.value，則基表元組T的編號T.no=hash(Key，T.value，T.str)，此函數(shù)的算法復(fù)雜度為O(1)，如果基表元組有n個，則計算全部元組編號的算法復(fù)雜度為O(n)，并且當(dāng)數(shù)據(jù)發(fā)生增刪改等情況時，只需要再調(diào)用此函數(shù)進行編號的重計算即可.

算法1 嵌入水印信息.

1)選取某個單元格Cell，計算其聚集值k，εcell.

2)Ifεcell=0，則返回步驟1)另外選取.

3)對于{Cell}中的每一個基表元組對應(yīng)的單元格Cell0，找出其所有的路徑Cell0Cell1…Cellk-1Cell，并調(diào)用過程InsertWatermark(path)進行水印信息嵌入算法InsertWatermark(pathCell0Cell1…Cellk-1Cellk):

Fori=1tok

If εcell=0thencontinue;//如果不適合嵌入水印則不嵌入

wm=∑T∈{Celli}T.nomod 2m;//計算水印信息

將單元格Celli的最低m位設(shè)置為wm;//嵌入水印信息

EndFor.

由算法1可以看出，嵌入算法的實質(zhì)在與某個單元格有語義關(guān)系的單元格中嵌入一種匹配關(guān)系，這種水印信息與語義相關(guān)，因此在嵌入時能充分利用路徑來加快嵌入速度，并且在DataCube壓縮時，也能夠保證算法的有效性.驗證算法則用來驗證這種匹配關(guān)系是否存在，由于還需要考慮到DataCube可能在嵌入水印后受到攻擊，因此還需要記錄匹配的程度，即引入一個匹配度閾值pmin.pmin的值可以根據(jù)DataCube的大小及路徑的平均長度進行選取.

算法2 驗證水印.

1)對于需要驗證的單元格Cell，計算其聚集值k.

2)對于{Cell}中的每一個基表元組對應(yīng)的單元格Cell0，找出其所有的路徑Cell0Cell1…Cellk-1Cell，并對于每一條路徑，從Cell1開始進行驗證，如果從單元格Celli開始的水印信息不符合，則此路徑的匹配度pj=(i-1)/k.

3)此單元格的匹配度為所有路徑的平均值，即pCell=1n∑nj=1pj，其中n為單元格Cell的所有路徑的數(shù)目.

4)如果這個單元格的匹配度大于閾值pmin，即可判斷DataCube中嵌入了水印.

由上面的嵌入算法與驗證算法可以看出，對于某一個單元格，可以判斷出是否在這個單元格及與其語義相關(guān)的單元格嵌入了水印，如果將判斷結(jié)果用“0”，“1”表示，那么對于多個bit位的二進制信息，可以在DataCube中找尋若干個相互之間沒有語義關(guān)系的單元格，并根據(jù)bit位為0或1來選擇嵌入或不嵌入水印信息.當(dāng)提取水印時，則是根據(jù)順序?qū)@些單元格進行驗證，并將判斷結(jié)果進行拼接，即可以得到嵌入的多位bit位水印.

3 魯棒性分析及參數(shù)選擇

Data Cube數(shù)字水印技術(shù)的目的是為了實現(xiàn)Data Cube的版權(quán)保護，即通過Data Cube里的水印信息證明Data Cube的所有權(quán)，在數(shù)據(jù)庫的數(shù)字水印技術(shù)中，主要考慮以下3種情況下對水印信息的影響:1)子集選取;2)子集增加;3)子集更改.

但Data Cube與一般關(guān)系數(shù)據(jù)庫的存儲與使用方式均有很大的不同，主要表現(xiàn)在:

1)Data Cube在存儲時，往往都要進行壓縮，即只存儲基表與一部分單元格.當(dāng)需要查詢的單元格沒有存儲時，則根據(jù)聚集關(guān)系來進行計算，得到單元格的聚集值，從而節(jié)省空間.

2)盜用者也可能只要獲取Data Cube的一部分數(shù)據(jù)，也可能得到有用的信息，因此在Data Cube中嵌入數(shù)字水印，要求在子集選取攻擊方面有更好的魯棒性.但Data Cube子集選取必須是選取符合某個性質(zhì)的子集，這與數(shù)據(jù)庫的隨機子集選取有很大不同.

3)Data Cube的數(shù)據(jù)在從數(shù)據(jù)倉庫抽取并聚集生成后，很少會再進行修改，但有可能再進行增加，并重新生成聚集值.盜用者也有可能去增加數(shù)據(jù)，并重新計算，這一點與數(shù)據(jù)庫的子集增加概念是一樣的.

對于Data Cube壓縮，為了使壓縮后仍能正確驗證水印信息，應(yīng)盡量選取聚集度k較大的單元格，因為嵌入算法將在這個單元格的所有路徑上的單元格都嵌入水印信息，k越大，保留水印信息的單元格也就越多，但k值的增大，使得算法執(zhí)行時間加長，同時也使得與此單元格無語義相關(guān)的單元格數(shù)目減少，可能最后無法嵌入多位bit信息.另一方面，單元格的k值越大，其對應(yīng)的基表元組集也就越大，因此當(dāng)盜用者進行子集選取時，所選取的子集包含于這個基表元組集中的概率就越大，也就能提高水印驗證時的水印匹配率.但是，當(dāng)新增加子集時，與這個基表元組集在某個維上相同的概率也就越大，從而會引起聚集值的重新計算，從而降低水印匹配率.

4 仿真實驗

仿真實驗所采用的數(shù)據(jù)集為TPC-R^[8]，TPC-R實驗數(shù)據(jù)集由dbgen程序產(chǎn)生(scale factor為0.15)，共包括910 732個元組(大約121.4 MB)，數(shù)據(jù)集共有OrderKey， PartKey， SuppKey， ShipDate， CommuniteDate， RecieptDate 6個維.其中OrderKey維包含ALL， Region， Nation， Customer層次;PartKey維包含ALL， Brand， Type， Part層次;SuppKey維包含ALL， Region， Nation， Supplier;而其他3個維包含的層次均為ALL，Year，Month，Date.嵌入水印信息為“Hunan University”.實驗是在一臺Intel Pentium E雙核1.8 GHz，2G內(nèi)存，運行Windows 2003 Server的PC機上執(zhí)行的.

實驗1測試了數(shù)字水印在度量值上引起的整體誤差，選擇了在不同單元格集上嵌入水印信息.其結(jié)果如表3所示，由實驗結(jié)果可以看出，嵌入水印所引入的誤差非常微小.同時，單元格聚集度平均值對于整體誤差并沒有明顯影響.

表3 水印信息對整體誤差的影響

Tab.3 Effect of watermark on global error

實驗2與實驗3對水印進行魯棒性測試，實驗2模擬了Data Cube壓縮與基于語義的單元格選取，不同壓縮選取比例與選取單元格聚集度平均值對水印匹配度的影響，其結(jié)果如圖1所示.由圖1可以看出，當(dāng)選取嵌入水印信息的單元格集聚集度平均值越高時，壓縮選取比例對水印匹配度的影響就越小.

Data Cube壓縮選取比例/%

圖1 Data Cube壓縮/選取比例對水印匹配度的影響

Fig.1 Effect of compression-choose on match

實驗3則測試了當(dāng)子集增加時，所增加子集比例對水印匹配度的影響，其結(jié)果如圖2所示.由圖2可以看出，當(dāng)選取嵌入水印信息的單元格集聚集度平均值越高時，所增加子集比例對水印匹配度的影響就越大.

實驗2與實驗3的實驗結(jié)果與第3節(jié)的分析結(jié)果是一致的，因此對于每個特定的Data Cube，水印系統(tǒng)應(yīng)綜合系統(tǒng)誤差、壓縮比例及子集增加頻率等多方面因素選取合適的參數(shù)值. 子集增加比例/%

圖2 Data Cube子集增加比例對水印匹配度的影響

Fig.2 Effect of subset increase on match

5 總 結(jié)

數(shù)字水印處理技術(shù)是解決數(shù)字產(chǎn)品知識產(chǎn)權(quán)問題的最有效和最有潛力的技術(shù).本文根據(jù)Data Cube 中單元格的語義信息來嵌入數(shù)字水印，并探討了嵌入多位水印信息的方法，理論分析與實驗均表明算法具有較好的魯棒性和不可見性，能夠很好地解決Data Cube的版權(quán)保護問題.在今后的研究工作中，我們還將進一步研究各種參數(shù)對于水印信息匹配的影響，并探討用戶將OLAP分析結(jié)果導(dǎo)出成其他格式(例如TXT，XML)后水印信息丟失的解決方案，充分發(fā)揮基于語義的數(shù)字水印嵌入方法的優(yōu)勢.

參考文獻

[1] KZTZENBEISSE S，PETITEOLAS F. Information hiding techniques for steganography and digital watermarking[M].Boston， London:Artech House，1999.

[2] SION R，ATALLAH M，PRABHAKAR S.Ownership proofs for categorical data[C]//Procof the IEEE International Conference on Data Engineering， Boston， 2004:584-596.

[3] GUO H，LI Y，LIU A， et al.A fragile watermarking scheme for detecting malicious modifications of database relations[J]. Information Sciences，2006， 176(10):1350-1378.

[4] 張桂芳，孫星明，肖湘蓉，等. 基于中國剩余定理的數(shù)據(jù)庫水印技術(shù)[J]. 計算機工程與應(yīng)用，2006，42(7):135-136.

ZHANG Gui-fang，SUN Xing-ming，XIAO Xiang-rong，et al.Database watermarking based on Chinese remainder theorem[J].Computer Engineering and Applications，2006，42(7):135-136.(In Chinese)

[5] 張勇，趙東寧，李德毅. 關(guān)系數(shù)據(jù)庫數(shù)字水印技術(shù)[J].計算機工程與應(yīng)用，2003，39(25): 193-195.

ZHANG Yong，ZHAO Dong-ning，LI De-yi.Digital watermarking for relational databases[J].Couputer Engineering and Applications，2003，39(25):193-195.(In Chinese)

[6] XIAO Xiang-rong，SUNXing-ming， CHEN Ming-gang. Second-LSB-dependent robust watermarking for relational database[C]// Proceedings of The Third International Symposium on Information Assurance and Security (IAS’07) ManchesterUK:IEEE Press， 2007.

[7] ATALLAH M，WAGSTAFF S. Waterarking with quadratic residues[C]//Proc of IS T/SPIE Conference on Security and Watermarking of Multimedia Contents.San Jose，CA，USA:SPIE，1999.

[8] Transaction Processing Performance Council TPC. TPC benchmarks H and R (decision support)[EB/OL].[1999-10]. http://www.tpc.org/.