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

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

中圖分類號(hào): TP311文獻(xiàn)標(biāo)識(shí)碼: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)境下保護(hù)版權(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)機(jī)分析處理)技術(shù)可以根據(jù)用戶的需要，從不同角度對(duì)數(shù)據(jù)進(jìn)行分析.每個(gè)不同的角度代表了數(shù)據(jù)分析中的一個(gè)“維”，因此也稱“多維分析”.同時(shí)，OLAP 分析也可以提供鉆取等語義操作，能夠提供更多、更豐富的報(bào)表和視圖.

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

1 基本概念與定義

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

表1 基表T

Tab.1 Base table T

元組

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

名稱時(shí)間年季度銷售額AEasternCTP1200316BEasternCTP22003112CWesternUTP1200339

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

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

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

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

定義1(維層次坐標(biāo)聚集關(guān)系∠) 設(shè)Di為DataCube的第i個(gè)維，有h個(gè)層次，則單元格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)對(duì)于所有滿足條件0

2)對(duì)于所有滿足條件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所示.則兩個(gè)單元格A與B之間的關(guān)系可定義為:[A1，A2，…，Ad，ma][B1，B2，…，Bd，mb]，當(dāng)且僅當(dāng)對(duì)于每個(gè)i(1≤i≤d)，都有Ai∠Bi.并定義一個(gè)在所有的維、層次及度量上取空值的空單元格R1，對(duì)于所有單元格R，均有R1R.

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

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

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

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

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

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

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

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

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

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

2 水印信息的嵌入與驗(yàn)證

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

算法1 嵌入水印信息.

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

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

3)對(duì)于{Cell}中的每一個(gè)基表元組對(duì)應(yīng)的單元格Cell0，找出其所有的路徑Cell0Cell1…Cellk-1Cell，并調(diào)用過程InsertWatermark(path)進(jìn)行水印信息嵌入算法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;//計(jì)算水印信息

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

EndFor.

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

算法2 驗(yàn)證水印.

1)對(duì)于需要驗(yàn)證的單元格Cell，計(jì)算其聚集值k.

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

表3 水印信息對(duì)整體誤差的影響

Tab.3 Effect of watermark on global error

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

Data Cube壓縮選取比例/%

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

Fig.1 Effect of compression-choose on match

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

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

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

Fig.2 Effect of subset increase on match

5 總 結(jié)

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

參考文獻(xiàn)

[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]. 計(jì)算機(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].計(jì)算機(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/.