佟 德 宇,朱 長 青,任 娜

(1.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗室，江蘇 南京 210023;2.江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023)

?

一種不依賴主鍵的地理數(shù)據(jù)庫水印算法

佟 德 宇,朱 長 青,任 娜

(1.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗室，江蘇 南京 210023;2.江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023)

根據(jù)數(shù)字水印技術(shù)，結(jié)合地理數(shù)據(jù)庫中數(shù)據(jù)的坐標(biāo)屬性和特點(diǎn)，分析了傳統(tǒng)數(shù)據(jù)庫水印算法存在的主鍵依賴和嵌入不均勻等問題，提出了一種不依賴主鍵的地理數(shù)據(jù)庫水印算法，通過對地理數(shù)據(jù)進(jìn)行可嵌位的分離和映射，建立雙重定位機(jī)制,實(shí)現(xiàn)了水印信息的同步，并引入校驗方法增強(qiáng)水印算法的魯棒性。實(shí)驗結(jié)果表明，該算法能夠較好地抵抗數(shù)據(jù)庫的常用攻擊方式，具有較強(qiáng)的可行性和實(shí)用價值。

地理數(shù)據(jù)庫；數(shù)字水印；主鍵；魯棒性

0 引言

地理數(shù)據(jù)庫實(shí)現(xiàn)了空間數(shù)據(jù)和屬性數(shù)據(jù)共同存儲于關(guān)系數(shù)據(jù)庫中，構(gòu)建和維護(hù)地理數(shù)據(jù)庫是一項龐大而復(fù)雜的工程，其蘊(yùn)含著地理數(shù)據(jù)本身的使用價值和數(shù)據(jù)所有者的版權(quán)價值。隨著信息交流的網(wǎng)絡(luò)化、多元化、共享化的發(fā)展，地理數(shù)據(jù)庫的安全問題越來越突出，從技術(shù)層面實(shí)現(xiàn)地理數(shù)據(jù)庫的安全保護(hù)十分迫切。

數(shù)字水印被廣泛應(yīng)用于各種數(shù)字媒介的版權(quán)保護(hù)中。近幾年不少學(xué)者在數(shù)字水印應(yīng)用于地理數(shù)據(jù)方面進(jìn)行了深入研究，主要集中于矢量數(shù)據(jù)和柵格數(shù)據(jù)的數(shù)字水印算法研究[1-7]。數(shù)據(jù)庫數(shù)字水印方面，Khanna等在數(shù)據(jù)庫安全管理中引入數(shù)字水印[8]，Rakesh提出了基于最低有效位的關(guān)系型數(shù)據(jù)庫水印算法[9]，牛夏牧結(jié)合誤差控制改進(jìn)了基于最低有效位的水印算法，并從理論上對魯棒性進(jìn)行了分析[10]，其他多種依賴主鍵的數(shù)字水印算法也被提出[11-13]，這些算法均是通過對主鍵進(jìn)行Hash運(yùn)算以實(shí)現(xiàn)水印信息的定位，因而水印算法對數(shù)據(jù)庫的主鍵具有嚴(yán)重的依賴性。本文提出一種不依賴主鍵的地理數(shù)據(jù)庫水印算法，建立新的水印位映射機(jī)制，增強(qiáng)地理數(shù)據(jù)庫水印算法的魯棒性。

1 問題分析

由于數(shù)據(jù)庫表的無序排列特性，在設(shè)計數(shù)據(jù)庫水印算法時，需要考慮水印的定位問題。以傳統(tǒng)的AHK數(shù)據(jù)庫水印算法為例[9]，設(shè)數(shù)據(jù)庫主鍵為PK，地理數(shù)據(jù)庫中地理數(shù)據(jù)R以點(diǎn)坐標(biāo)(x,y)(k=1,2,…,m)為單位進(jìn)行存儲。傳統(tǒng)的水印信息定位方法如下：

WM=G(Seed)={wm[i],i=0,1,…,n-1},

wm[i]∈{0,1}

(1)

其中：n為水印長度，Hash表示單向散列函數(shù)。該函數(shù)能夠?qū)⑤斎霐?shù)據(jù)不可逆地映射到固定長度的數(shù)值區(qū)間，但此類算法有如下不足：

(1)無法抵抗針對主鍵的數(shù)據(jù)庫攻擊。在地理數(shù)據(jù)庫中，主鍵作為某一地理位置的唯一標(biāo)識，本身不具有實(shí)際地理意義。但盜版者一旦非法得到地理數(shù)據(jù)庫，只需更改、刪除主鍵，直接使用篩選出包含實(shí)際價值的地理坐標(biāo)，就能夠造成版權(quán)數(shù)據(jù)的侵權(quán)。

(2)水印信息嵌入的不完全性。式(1)的水印定位機(jī)制難以保證水印嵌入的均勻性。在理想的狀態(tài)下，Hash函數(shù)通過對水印位的滿映射，實(shí)現(xiàn)水印信息的完全嵌入，但是實(shí)際中函數(shù)的散列映射存在碰撞問題。例如，若水印算法實(shí)現(xiàn)了數(shù)據(jù)庫每個元組嵌入水印中的1位，當(dāng)水印信息長度為200位而數(shù)據(jù)元組正好為200個時，在保證Hash函數(shù)映射滿足完全隨機(jī)性條件下，則200個元組正好嵌入200位水印的概率P1為：

(2)

由式(2)知，P1為極小的數(shù)，故當(dāng)可嵌入的數(shù)據(jù)量較小時，水印信息難以實(shí)現(xiàn)完全的嵌入，從而導(dǎo)致算法的魯棒性較差。

由上述分析可知，依賴主鍵的數(shù)據(jù)庫水印算法在特定的攻擊方式下魯棒性較低，且水印嵌入不夠均勻，存在著嵌入水印后提取水印可能不完整的問題。

2 不依賴主鍵的地理數(shù)據(jù)庫水印算法

2.1 算法思想

根據(jù)前述分析，在設(shè)計不依賴主鍵的水印算法時，需解決數(shù)據(jù)中嵌入的水印與二值序列同步問題。本文根據(jù)地理數(shù)據(jù)的特點(diǎn)和使用特性，通過坐標(biāo)本身實(shí)現(xiàn)區(qū)間定位，使算法具有雙重定位特征。水印嵌入時將信息量較少的區(qū)間定位值與水印值共同嵌入，這樣既保證了對地理數(shù)據(jù)坐標(biāo)改動的程度較小，又保證了水印值和水印位置的同步，在保證地理數(shù)據(jù)使用價值的基礎(chǔ)上實(shí)現(xiàn)水印的嵌入和檢測。

本文算法以矢量地理數(shù)據(jù)庫為例。由于不同數(shù)據(jù)庫在存儲、結(jié)構(gòu)、模型等方面存在差異性，所以本算法研究不涉及具體的數(shù)據(jù)庫，以抽象的矢量地理數(shù)據(jù)模型為水印嵌入和檢測的載體。在矢量地理數(shù)據(jù)模型中，以點(diǎn)模型為例闡述地理數(shù)據(jù)庫水印算法。線模型、面模型可視為由點(diǎn)模型的序列構(gòu)成，因此提出的地理數(shù)據(jù)庫水印算法也適用于線模型、面模型。

2.2 水印信息生成

水印算法采用無意義水印信息，使用隨機(jī)的種子數(shù)Seed產(chǎn)生長度為n的偽隨機(jī)二值序列WM：

WM=G(Seed)={wm[i],i=0,1,…,n-1},

wm[i]∈{0,1}

(3)

設(shè)n=m×j，其中m和j均為正整數(shù)，則水印信息WM可分為m組，每組j位，將一維的偽隨機(jī)二值序列轉(zhuǎn)變?yōu)槎S的二值矩陣：

(4)

2.3 水印嵌入算法

記地理數(shù)據(jù)庫中每個元組為R，該元組包含的地理點(diǎn)坐標(biāo)分別為R.x、R.y。水印嵌入過程中，需遍歷每個元組R，將十進(jìn)制的R.x、R.y轉(zhuǎn)為二進(jìn)制：

(5)

其中:b表示不可嵌位，c表示可嵌位。

借助式(4)的定位機(jī)制，r和p以較少的嵌入容量實(shí)現(xiàn)了水印區(qū)間定位和區(qū)間內(nèi)部定位。為避免其他未嵌入水印的數(shù)據(jù)對水印檢測造成干擾，提高水印提取的正確率，在水印算法設(shè)計時引入校驗機(jī)制，對區(qū)間內(nèi)部定位和水印值進(jìn)行校驗，從而增強(qiáng)水印算法的魯棒性。

具體的水印嵌入步驟如下：1)讀取數(shù)據(jù)：取數(shù)據(jù)表中第一個元組Ri，元組Ri中地理點(diǎn)坐標(biāo)為Ri.x、Ri.y，根據(jù)式(5)，提取坐標(biāo)的不可嵌位記為xb、yb，提取坐標(biāo)的可嵌位記為xc、yc；2)映射水印位：計算r=Hash(xb°yb)modm，其中°為連接操作，Hash函數(shù)為自定義的散列函數(shù)，具有單向性、敏感性、安全性；3)生成初始水印信息：E=p°wm[r,p]；4)計算校驗碼：計算初始水印信息E的循環(huán)冗余校驗(CRC)碼,校驗碼為g，則g=CRC(r°p°wm[r,p]，經(jīng)過CRC校驗后的水印信息E′=E°g；5)嵌入水印：將E′嵌入至xc、yc中，完成對Ri元組的水印嵌入；6)循環(huán)嵌入：重復(fù)上述步驟，直至所有元組嵌入水印。

2.4 水印檢測算法

水印檢測為水印嵌入的逆過程，算法步驟如下：1)讀取數(shù)據(jù)：取待檢測數(shù)據(jù)表中第一個元組Ri，元組Ri中地理點(diǎn)坐標(biāo)為Ri.x、Ri.y，根據(jù)式(5)，提取坐標(biāo)的不可嵌位記為xb、yb，提取坐標(biāo)的可嵌位記為xc、yc；2)提取水印信息：從xc、yc中提取出待檢測信息E′為E°g；3)校驗水印信息：對待檢測信息E進(jìn)行CRC校驗，若通過校驗則繼續(xù)步驟4，否則略過該元組，跳至步驟1檢測下一元組；4)映射水印位：計算r=Hash(xb°yb)modm；5)記錄水印信息：從E中提取p°wm[r,p]，則該元組檢測出的水印信息記錄為wm[r×j+p]=wm[r,p]；6)循環(huán)檢測：重復(fù)上述步驟，直至處理完全部待檢測數(shù)據(jù)。

3 實(shí)驗結(jié)果和分析

3.1 實(shí)驗過程

本實(shí)驗的地理數(shù)據(jù)庫采用某地地物點(diǎn)數(shù)據(jù)集合，包含地物經(jīng)緯度坐標(biāo)，數(shù)據(jù)表中共有2 000個元組。取水印長度n為224，分組位數(shù)j為14，根據(jù)式(4)將一維的224位水印信息轉(zhuǎn)換為16*14的二值矩陣。使用本文提出的算法嵌入并檢測水印，其中嵌入方法采用量化方法以實(shí)現(xiàn)盲檢，CRC校驗多項式為x4+x+1。對嵌入水印后的地理數(shù)據(jù)庫進(jìn)行常見的數(shù)據(jù)增加、刪除、更新等攻擊行為，檢測攻擊后的地理數(shù)據(jù)庫水印信息并計算相關(guān)系數(shù)。

設(shè)原始水印信息為，檢測出的水印信息為W′，水印位數(shù)為N，相關(guān)系數(shù)NC計算方法如下：

(6)

其中，XNOR為同或操作。設(shè)置相關(guān)系數(shù)NC的檢測閾值為0.8，當(dāng)NC高于0.8時，表明水印能夠正確地檢測匹配，即檢測數(shù)據(jù)中包含版權(quán)信息。

3.2 結(jié)果與分析

對嵌入水印后未遭受攻擊的數(shù)據(jù)庫進(jìn)行水印檢測，計算出的相關(guān)系數(shù)為1，即嵌入的水印信息在正常情況下可以被完整地提取出來，表明水印算法具有可行性。對嵌入水印后的數(shù)據(jù)庫進(jìn)行數(shù)據(jù)增加攻擊、更新攻擊、刪除攻擊、數(shù)據(jù)表結(jié)構(gòu)攻擊實(shí)驗。

(1)數(shù)據(jù)增加攻擊。在數(shù)據(jù)表中增加不包含水印的數(shù)據(jù)元組，計算相關(guān)系數(shù)，結(jié)果如表1所示。由表1可見，增加8倍于原數(shù)據(jù)量的無水印數(shù)據(jù)時，相關(guān)系數(shù)為1；增加24倍于原數(shù)據(jù)量的無水印數(shù)據(jù)時，相關(guān)系數(shù)仍然超過0.8的檢測閾值，說明水印能夠正確地檢測匹配。因此，算法對增加數(shù)據(jù)的數(shù)據(jù)庫攻擊方式具有好的魯棒性。

表1 數(shù)據(jù)增加攻擊結(jié)果

Table1Detectedwatermarkcorrelationcoefficientundertheattackofaddingdata

增加元組數(shù)增加元組數(shù)占總元組數(shù)的百分比(%)相關(guān)系數(shù)1000501200010014000200180004001160008000．99102400012000．98213200016000．91964000020000．89294800024000．8482

(2)數(shù)據(jù)刪除攻擊。在嵌入水印的數(shù)據(jù)表中隨機(jī)刪除一定數(shù)量的元組，計算相關(guān)系數(shù)，結(jié)果如表2所示。由表2可見，在刪除80%的數(shù)據(jù)時，相關(guān)系數(shù)仍然為1；刪除85%的數(shù)據(jù)時，相關(guān)系數(shù)在0.9以上，仍能夠正確地檢測水印。實(shí)驗說明本文算法具有較好的抵抗刪除攻擊的能力。

表2 數(shù)據(jù)刪除攻擊結(jié)果

Table 2 Detected watermark correlation coefficient under the attack of deleting data

刪除元組數(shù)刪除元組數(shù)占總元組數(shù)的百分比(%)相關(guān)系數(shù)20010140020160030180040110005011200601140070116008011700850．91961800900．6696

(3) 數(shù)據(jù)更新攻擊。數(shù)據(jù)更新攻擊的本質(zhì)是刪除含水印數(shù)據(jù)并增加不含水印的數(shù)據(jù)，在數(shù)據(jù)庫攻擊方式中攻擊強(qiáng)度很大，對算法的魯棒性提出了更高的要求。數(shù)據(jù)更新攻擊后計算相關(guān)系數(shù)，結(jié)果如表3所示。由表3可見，在60%的數(shù)據(jù)量受到更新時，相關(guān)系數(shù)仍為1；當(dāng)更新80%的數(shù)據(jù)量時，相關(guān)系數(shù)有所降低但仍能正確檢測匹配水印信息。實(shí)驗證明本文算法對數(shù)據(jù)更新攻擊具有較好的魯棒性。

表3 數(shù)據(jù)更新攻擊結(jié)果

Table 3 Detected watermark correlation coefficient under the attack of updating data

更新元組數(shù)更新元組數(shù)占總元組數(shù)的百分比(%)相關(guān)系數(shù)200101400201600301800401100050112006011400700．98211600800．87501700850．7321

(4)數(shù)據(jù)表結(jié)構(gòu)修改攻擊。為驗證算法對主鍵攻擊的魯棒性，數(shù)據(jù)表結(jié)構(gòu)修改攻擊中包括刪除主鍵、更新主鍵等操作。計算相關(guān)系數(shù)，結(jié)果如表4所示。由表4可見，在修改表結(jié)構(gòu)的各種攻擊下相關(guān)系數(shù)仍為1。這是因為在針對數(shù)據(jù)表的結(jié)構(gòu)攻擊中，由于算法不依賴主鍵及其他數(shù)據(jù)，水印的定位和值只與地理數(shù)據(jù)本身有關(guān)，故任何對數(shù)據(jù)表結(jié)構(gòu)的修改(如刪除主鍵、更新主鍵、修改屬性列等操作)均不會對水印造成破壞，實(shí)驗結(jié)果與理論分析一致。由此可見，算法能夠抵抗數(shù)據(jù)表結(jié)構(gòu)修改攻擊。

表4 數(shù)據(jù)表結(jié)構(gòu)修改攻擊結(jié)果

Table 4 Detected watermark correlation coefficient under the attack of modifying data table structure

修改表結(jié)構(gòu)方式相關(guān)系數(shù)刪除主鍵1更新主鍵1修改屬性列1

3.3 水印均勻分布性的定量比較

在小數(shù)據(jù)量的情形下，對比式(2)，采用相同的水印信息長度200位，使用本文提出的水印算法對200個元組進(jìn)行水印嵌入，r取8，則水印能夠均勻、完全地嵌入元組中的概率P2為：

1.16×1078P1

(7)

因此，與式(2)相比，本算法完全嵌入的概率比傳統(tǒng)算法有非常大的提升，表明本算法對小數(shù)據(jù)量的情形具有更好的適用性，嵌入的水印信息更加完備，魯棒性更強(qiáng)。

4 結(jié)論

針對地理數(shù)據(jù)庫的安全保護(hù)需求，本文以矢量地理數(shù)據(jù)庫為研究對象，在分析傳統(tǒng)數(shù)據(jù)庫水印算法不足的基礎(chǔ)上，提出了不依賴主鍵的地理數(shù)據(jù)庫水印算法，并建立了雙重映射和冗余校驗機(jī)制，克服了主鍵依賴性和水印分布不均勻性。實(shí)驗表明該算法具有較好的魯棒性和實(shí)用性，對于地理數(shù)據(jù)的安全保護(hù)具有重要意義。本文提出的水印算法主要針對矢量地理數(shù)據(jù)庫的幾何數(shù)據(jù)，將來可從屬性數(shù)據(jù)的角度出發(fā)，研究地理數(shù)據(jù)庫的非數(shù)值水印算法。

[1]SHUJUND,LIANGL,SENC.Researchonadigitalwatermarkingalgorithmsuitabletovectormap[A].ProceedingsoftheIEEEInternationalConferenceonAutomationandLogistics[C].Jinan:IEEE,2007.1236-1240.

[2]OHBUCHIR,UEDAH,ENDOHS.Robustwatermarkingofvectordigitalmaps[A].ProceedingoftheIEEEInternationalConferenceonMultimediaandExpo[C].Lausanne:IEEE,2002.577-580.

[3] 許德合,朱長青,王奇勝.利用QIM的DFT矢量空間數(shù)據(jù)盲水印模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2010(9):1100-1103.

[4] 王奇勝,朱長青,許德合.利用DFT相位的矢量地理空間數(shù)據(jù)水印方法[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2011,36(5):523-526.

[5] 任娜,朱長青,王志偉.基于映射機(jī)制的遙感影像盲水印算法[J].測繪學(xué)報,2011,40(5):623-627.

[6] 符浩軍,朱長青,繆劍,等.基于小波變換的數(shù)字柵格地圖復(fù)合式水印算法[J].測繪學(xué)報,2011,40(3):394-400.

[7] 任娜,朱長青,王志偉.抗幾何攻擊的高分辨率遙感影像半盲水印算法[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2011,36(3):329-332.

[8]KHANNAS,ZANEF.Watermarkingmaps:Hidinginformationinstructureddata[A].ProceedingsoftheEleventhAnnualACM-SIAMSymposiumonDiscreteAlgorithms[C].SocietyforIndustrialandAppliedMathematics,2000.596-605.

[9]RAKESHA,KIERNANJ.Watermarkingrelationaldatabases[A].Proceedingsofthe28thInternationalConferenceonVeryLargeDataBases[C].VLDBEndowment,2002.155-166.

[10] 牛夏牧,趙亮,黃文軍,等.利用數(shù)字水印技術(shù)實(shí)現(xiàn)數(shù)據(jù)庫的版權(quán)保護(hù)[J].電子學(xué)報,2003,31(12):2050-2053.

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

[12] 張勇,牛夏牧.一種用于關(guān)系數(shù)據(jù)庫的可逆水印技術(shù)[J].電子學(xué)報,2006,34(12):2425-2428.

[13] 馬瑞敏,陳繼紅,朱燕瓊.一種基于混沌加密的關(guān)系數(shù)據(jù)庫水印算法[J].南通大學(xué)學(xué)報(自然科學(xué)版),2012,11(1):13-17.

A Watermarking Algorithm of Geographical Database Not Depending on Primary Keys

TONG De-yu,ZHU Chang-qing,REN Na

(KeyLaboratoryofVirtualGeographicEnvironmentofMinistryofEducation,NanjingNormalUniversity,Nanjing210023;JiangsuCenterforCollaborativeInnovationinGeographicalInformationResourceDevelopmentandApplication,Nanjing210023,China)

Based on the technology of digital watermarking,the disadvantages of traditional database watermarking algorithms are analyzed in this paper.Taking the features of geographical data and its coordinates into consideration,a new watermarking algorithm for geographic database that does not depend on primary key is proposed.The algorithm splits embedded bit from geographic data,builds the mapping and positioning mechanism to realize the synchronization of watermark information.In addition,the check method is used to enhance robustness of watermark.Experiment results show that the proposed algorithm has quite good resistance to common database attacks,with a strong feasibility and significance in practical applications.

geographical database;digital watermarking;primary key;robust

2014-10-15；

2015-03-20

國家社科基金重大項目(11&ZD162);國家自然科學(xué)基金項目(41301413);江蘇省青年基金項目(BK20130903)

佟德宇(1989-)，男，博士研究生，主要研究方向為地理空間數(shù)據(jù)安全。E-mail:tdytdy@qq.com

10.3969/j.issn.1672-0504.2015.05.018

TP301.6

A

1672-0504(2015)05-0086-04