一種不依賴主鍵的地理數據庫水印算法

佟 德 宇,朱 長 青,任 娜

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

?

一種不依賴主鍵的地理數據庫水印算法

佟 德 宇,朱 長 青,任 娜

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

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

地理數據庫；數字水?。恢麈I；魯棒性

0 引言

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

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

1 問題分析

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

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

wm[i]∈{0,1}

(1)

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

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

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

(2)

由式(2)知，P1為極小的數，故當可嵌入的數據量較小時，水印信息難以實現完全的嵌入，從而導致算法的魯棒性較差。

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

2 不依賴主鍵的地理數據庫水印算法

2.1 算法思想

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

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

2.2 水印信息生成

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

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

wm[i]∈{0,1}

(3)

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

(4)

2.3 水印嵌入算法

記地理數據庫中每個元組為R，該元組包含的地理點坐標分別為R.x、R.y。水印嵌入過程中，需遍歷每個元組R，將十進制的R.x、R.y轉為二進制：

(5)

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

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

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

2.4 水印檢測算法

水印檢測為水印嵌入的逆過程，算法步驟如下：1)讀取數據：取待檢測數據表中第一個元組Ri，元組Ri中地理點坐標為Ri.x、Ri.y，根據式(5)，提取坐標的不可嵌位記為xb、yb，提取坐標的可嵌位記為xc、yc；2)提取水印信息：從xc、yc中提取出待檢測信息E′為E°g；3)校驗水印信息：對待檢測信息E進行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)檢測：重復上述步驟，直至處理完全部待檢測數據。

3 實驗結果和分析

3.1 實驗過程

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

設原始水印信息為，檢測出的水印信息為W′，水印位數為N，相關系數NC計算方法如下：

(6)

其中，XNOR為同或操作。設置相關系數NC的檢測閾值為0.8，當NC高于0.8時，表明水印能夠正確地檢測匹配，即檢測數據中包含版權信息。

3.2 結果與分析

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

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

表1 數據增加攻擊結果

Table1Detectedwatermarkcorrelationcoefficientundertheattackofaddingdata

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

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

表2 數據刪除攻擊結果

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

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

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

表3 數據更新攻擊結果

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

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

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

表4 數據表結構修改攻擊結果

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

修改表結構方式相關系數刪除主鍵1更新主鍵1修改屬性列1

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

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

1.16×1078P1

(7)

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

4 結論

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

[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矢量空間數據盲水印模型[J].武漢大學學報(信息科學版),2010(9):1100-1103.

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

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

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

[7] 任娜,朱長青,王志偉.抗幾何攻擊的高分辨率遙感影像半盲水印算法[J].武漢大學學報(信息科學版),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] 牛夏牧,趙亮,黃文軍,等.利用數字水印技術實現數據庫的版權保護[J].電子學報,2003,31(12):2050-2053.

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

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

[13] 馬瑞敏,陳繼紅,朱燕瓊.一種基于混沌加密的關系數據庫水印算法[J].南通大學學報(自然科學版),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);國家自然科學基金項目(41301413);江蘇省青年基金項目(BK20130903)

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

10.3969/j.issn.1672-0504.2015.05.018

TP301.6

A

1672-0504(2015)05-0086-04