一种不依赖主键的地理数据库水印算法

佟 德 宇,朱 长 青,任 娜

(1.南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210023;2.江苏省地理信息资源开发与利用协同创新中心，江苏 南京 210023)



一种不依赖主键的地理数据库水印算法

佟 德 宇,朱 长 青,任 娜

(1.南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210023;2.江苏省地理信息资源开发与利用协同创新中心，江苏 南京 210023)

根据数字水印技术，结合地理数据库中数据的坐标属性和特点，分析了传统数据库水印算法存在的主键依赖和嵌入不均匀等问题，提出了一种不依赖主键的地理数据库水印算法，通过对地理数据进行可嵌位的分离和映射，建立双重定位机制,实现了水印信息的同步，并引入校验方法增强水印算法的鲁棒性。实验结果表明，该算法能够较好地抵抗数据库的常用攻击方式，具有较强的可行性和实用价值。

地理数据库；数字水印；主键；鲁棒性

0 引言

地理数据库实现了空间数据和属性数据共同存储于关系数据库中，构建和维护地理数据库是一项庞大而复杂的工程，其蕴含着地理数据本身的使用价值和数据所有者的版权价值。随着信息交流的网络化、多元化、共享化的发展，地理数据库的安全问题越来越突出，从技术层面实现地理数据库的安全保护十分迫切。

数字水印被广泛应用于各种数字媒介的版权保护中。近几年不少学者在数字水印应用于地理数据方面进行了深入研究，主要集中于矢量数据和栅格数据的数字水印算法研究[1-7]。数据库数字水印方面，Khanna等在数据库安全管理中引入数字水印[8]，Rakesh提出了基于最低有效位的关系型数据库水印算法[9]，牛夏牧结合误差控制改进了基于最低有效位的水印算法，并从理论上对鲁棒性进行了分析[10]，其他多种依赖主键的数字水印算法也被提出[11-13]，这些算法均是通过对主键进行Hash运算以实现水印信息的定位，因而水印算法对数据库的主键具有严重的依赖性。本文提出一种不依赖主键的地理数据库水印算法，建立新的水印位映射机制，增强地理数据库水印算法的鲁棒性。

1 问题分析

由于数据库表的无序排列特性，在设计数据库水印算法时，需要考虑水印的定位问题。以传统的AHK数据库水印算法为例[9]，设数据库主键为PK，地理数据库中地理数据R以点坐标(x,y)(k=1,2,…,m)为单位进行存储。传统的水印信息定位方法如下：

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

wm[i]∈{0,1}

(1)

其中：n为水印长度，Hash表示单向散列函数。该函数能够将输入数据不可逆地映射到固定长度的数值区间，但此类算法有如下不足：

(1)无法抵抗针对主键的数据库攻击。在地理数据库中，主键作为某一地理位置的唯一标识，本身不具有实际地理意义。但盗版者一旦非法得到地理数据库，只需更改、删除主键，直接使用筛选出包含实际价值的地理坐标，就能够造成版权数据的侵权。

(2)水印信息嵌入的不完全性。式(1)的水印定位机制难以保证水印嵌入的均匀性。在理想的状态下，Hash函数通过对水印位的满映射，实现水印信息的完全嵌入，但是实际中函数的散列映射存在碰撞问题。例如，若水印算法实现了数据库每个元组嵌入水印中的1位，当水印信息长度为200位而数据元组正好为200个时，在保证Hash函数映射满足完全随机性条件下，则200个元组正好嵌入200位水印的概率P1为：

(2)

由式(2)知，P1为极小的数，故当可嵌入的数据量较小时，水印信息难以实现完全的嵌入，从而导致算法的鲁棒性较差。

由上述分析可知，依赖主键的数据库水印算法在特定的攻击方式下鲁棒性较低，且水印嵌入不够均匀，存在着嵌入水印后提取水印可能不完整的问题。

2 不依赖主键的地理数据库水印算法

2.1 算法思想

根据前述分析，在设计不依赖主键的水印算法时，需解决数据中嵌入的水印与二值序列同步问题。本文根据地理数据的特点和使用特性，通过坐标本身实现区间定位，使算法具有双重定位特征。水印嵌入时将信息量较少的区间定位值与水印值共同嵌入，这样既保证了对地理数据坐标改动的程度较小，又保证了水印值和水印位置的同步，在保证地理数据使用价值的基础上实现水印的嵌入和检测。

本文算法以矢量地理数据库为例。由于不同数据库在存储、结构、模型等方面存在差异性，所以本算法研究不涉及具体的数据库，以抽象的矢量地理数据模型为水印嵌入和检测的载体。在矢量地理数据模型中，以点模型为例阐述地理数据库水印算法。线模型、面模型可视为由点模型的序列构成，因此提出的地理数据库水印算法也适用于线模型、面模型。

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位，将一维的伪随机二值序列转变为二维的二值矩阵：

(4)

2.3 水印嵌入算法

记地理数据库中每个元组为R，该元组包含的地理点坐标分别为R.x、R.y。水印嵌入过程中，需遍历每个元组R，将十进制的R.x、R.y转为二进制：

(5)

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

借助式(4)的定位机制，r和p以较少的嵌入容量实现了水印区间定位和区间内部定位。为避免其他未嵌入水印的数据对水印检测造成干扰，提高水印提取的正确率，在水印算法设计时引入校验机制，对区间内部定位和水印值进行校验，从而增强水印算法的鲁棒性。

具体的水印嵌入步骤如下：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的循环冗余校验(CRC)码,校验码为g，则g=CRC(r∘p∘wm[r,p]，经过CRC校验后的水印信息E′=E∘g；5)嵌入水印：将E′嵌入至xc、yc中，完成对Ri元组的水印嵌入；6)循环嵌入：重复上述步骤，直至所有元组嵌入水印。

2.4 水印检测算法

水印检测为水印嵌入的逆过程，算法步骤如下：1)读取数据：取待检测数据表中第一个元组Ri，元组Ri中地理点坐标为Ri.x、Ri.y，根据式(5)，提取坐标的不可嵌位记为xb、yb，提取坐标的可嵌位记为xc、yc；2)提取水印信息：从xc、yc中提取出待检测信息E′为E∘g；3)校验水印信息：对待检测信息E进行CRC校验，若通过校验则继续步骤4，否则略过该元组，跳至步骤1检测下一元组；4)映射水印位：计算r=Hash(xb∘yb)modm；5)记录水印信息：从E中提取p∘wm[r,p]，则该元组检测出的水印信息记录为wm[r×j+p]=wm[r,p]；6)循环检测：重复上述步骤，直至处理完全部待检测数据。

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)相比，本算法完全嵌入的概率比传统算法有非常大的提升，表明本算法对小数据量的情形具有更好的适用性，嵌入的水印信息更加完备，鲁棒性更强。

4 结论

针对地理数据库的安全保护需求，本文以矢量地理数据库为研究对象，在分析传统数据库水印算法不足的基础上，提出了不依赖主键的地理数据库水印算法，并建立了双重映射和冗余校验机制，克服了主键依赖性和水印分布不均匀性。实验表明该算法具有较好的鲁棒性和实用性，对于地理数据的安全保护具有重要意义。本文提出的水印算法主要针对矢量地理数据库的几何数据，将来可从属性数据的角度出发，研究地理数据库的非数值水印算法。

[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