（教育技术学专业论文）基于gaaa的关系数据库水印优化算法研究.pdf

摘要 摘要 2 l 世纪，被称为“第四媒体的i n t e m e t 已成为现今世界上最大的信息载体，它在推动 社会各行各业发展与变革的同时，也为现代远程教育的发展提供了契机，插上了腾飞的翅 膀。在i n t e m e t 上传播的数字资源易于复制、修改和传播的特性使教育资源的共享更加便捷， 但同时也给资源窃取者带来了可乘之机。如何才能让用户既能充分享受i n t e m e t 的便利，又 能有效地保护数字产品知识产权，日益成为人们关注的话题。因此，数字水印技术作为一 种有效解决版权问题的关键技术成为人们研究的热点。数据库是远程教育资源的主要载 体，通过对其版权进行保护来实现数字教育资源知识产权的保护是一种行之有效的方法。 而解决数据库版权保护问题的关键，不仅有赖于人们版权保护意识的增强，更取决于版权 保护技术的发展。【l 】因此，关系数据库水印技术作为数据库版权保护的新兴技术日益受到 人们的重视，并逐渐被广泛地研究和应用。 本文首先概述了数据库水印的研究和发展现状，根据已有的嵌入式数据库水印算法通 常面临着数字水印技术和数据库使用价值之间存在矛盾的现状，提出了对关系数据库水印 进行优化研究的方案。进而，如何保证水印嵌入量、嵌入位置和嵌入强度最优成为本文研 究的重点。由于利用遗传算法优化关系数据库水印存在着时间耗费大、水印信息泄露等缺 点，而g a a a 算法恰恰克服了遗传算法的局限性，因此成为关系数据库水印优化算法的最 佳选择。主要研究内容及成果如下： 首先，介绍了关系数据库水印技术的基本理论，并在前人研究成果的基础上总结并提 出了优化关系数据库水印的一般思路，从而为关系数据库水印优化方案的具体实施奠定了 基础。 其次，在分析前人关系数据库水印算法优缺点的基础上，提出了基于遗传算法的关系 数据库水印优化算法。此算法不但对水印信息的产生过程进行了优化，也对水印的嵌入过 程进行了优化，大大提高了水印的抗攻击能力。 最后，本文在对关系数据库的特点进行详细分析的基础上，提出了基于g a a a 的关系 数据库水印优化算法。该算法首先利用差错控制技术预处理水印信息；接着利用g a a a 算 法优化选择关系数据库水印的嵌入位置；最后，利用多数选举机制来提高水印的正确提取 能力。 本文重点介绍了基于g a a a 的关系数据库水印优化算法，并通过实验证明了本文所提 出的关系数据库水印优化算法具有嵌入灵活方便、安全性高和抗攻击能力强等特点。 关键字：数据库水印：遗传算法；版权保护：g a a a ；水印优化算法 a b s t r a c t a b s t r a c t i nt h e 21s tc e n t u r y , i n t e m e th a sb e c o m et h el a r g e s ti n f o r m a t i o nc a r d e ri nt h ew o r l d i t p r o m o t e st h ed e v e l o p m e n ta n dc h a n g ei na l lw a l k so fl i f e ，a n dp r o v i d e sa no p p o r t u n i t yf o rt h e d e v e l o p m e n to fm o d e md i s t a n c ee d u c a t i o n o nt h ei n t e m e t ，t h ed i g i t a lr e s o u r c e sa r ee a s yt o c o p y , m o d i f ya n dd i f f u s e ，s ot h a ti t i sm o r ec o n v e n i e n tf o rt h o s ew h os t e a lt h e m a sar e s u l t ， d i g i t a lw a t e r m a r k i n ga sa ne f f e c t i v es o l u t i o nt oc o p y r i g h ti s s u e sb e c o m e sah o ts p o t d a t a b a s e s a r et h em a i nc a r r i e rf o rd i s t a n c ee d u c a t i o nr e s o u r c e s ，s ot h e i rc o p y r i g h ti s s u e sa r em o r e i m p o r t a n t t h ec o p y r i g h tp r o t e c t i o nf o rd a t a b a s e si sn o to n l yd e t e r m i n e db yt h ee n h a n c e m e n to f p e o p l e sc o p y r i g h tp r o t e c t i o nc o n s c i o u s n e s s ，b u ta l s ob yt h ep r o g r e s so fc o p y r i g h tp r o t e c t i o n t e c h n o l o g y i l lt h u s ，t h ed a t a b a s ew a t e r m a r k i n gt e c h n o l o g ya san e wt e c h n o l o g yf o rd a t a b a s e c o p y r i g h tp r o t e c t i o ni sb e e nt a k e nm o r es e r i o u s l yb yp e o p l ea n db e e nw i d e l yu s e d i nt h i sp a p e r , w eo u t l i n et h ed e v e l o p m e n ta n dr e s e a r c hs t a t u so ft h ed a t a b a s ew a t e r m a r k i n g a tf i r s t ，o nt h eb a s i so ft h ee m b e d d e dd a t a b a s ew a t e r m a r k i n ga l g o r i t h ma r eo f t e nf a c e d 诵t l lt h e c o n t r a d i c t i o nb e t w e e nd i g i t a lw a t e r m a r k i n gt e c h n o l o g ya n dd a t a b a s et e c h n o l o g y , w h i c hm a d e t h eo p t i m i z i n go fr e l a t i o n a ld a t a b a s ew a t e r m a r k i n gan e c e s s i t y f u r t h e r m o r e ，h o wt oe n s u r et h e a m o u n to fw a t e r m a r ki n f o r m a t i o n ，t h el o c a t i o nt ob em a r k e da n dt h es t r e n g t ho fe m b e d d i n ga r e o p t i m a lb e c o m e st h ef o c u so ft h i ss t u d y b e c a u s eu s i n gt h eg e n e t i ca l g o r i t h mt oo p t i m i z et h e r e l a t i o n a ld a t a b a s ew a t e r m a r k i n gi st i m e c o n s u m i n g ，a n dt h ew a t e r m a r ki n f o r m a t i o ni se a s yt o d i s c l o s u r e ，w h i l et h eg a a aa l g o r i t h mju s to v e r c o m e st h el i m i t a t i o n so ft h eg e n e t i ca l g o r i t h m ，s o i tb e c o m e sab e s tc h o i c e t h em a i nr e s e a r c hc o n t e n ta n dr e s u l ta r ea sf o l l o w s ： f i r s t l y , w ei n t r o d u c ea no v e r v i e wo ft h ew a t e r m a r k i n gr e l a t i o n a ld a t a b a s e sb a s i ct h e o r y o n t h eb a s i so fs u m m a r i z i n gt h ee x p e r i e n c e sa c c u m u l a t e d ，w ep r e s e n tag e n e r a li d e ao fo p t i m i z i n g r e l a t i o n a ld a t a b a s ew a t e r m a r k i n g ，a n dt h i sl a yt h eg r o u n d w o r kf o rt h en e x ts t e p s e c o n d l y , an e w r e l a t i o n a ld a t a b a s e w a t e r m a r k i n ga l g o r i t h mb a s e d o nt h ei m p r o v e d g e n e t i ca l g o r i t h m i s p r e s e n t e d i nt h i sa l g o r i t h m ，t h ew a t e r m a r kg e n e r a t i o np r o c e s si so p t i m i z e d ，a n dt h ew a t e r m a r k e m b e d d i n gp r o c e s si sa l s oo p t i m i z e d ，w h i c he n h a n c et h ea n t i - a t t a c kc a p a b i l i t yo ft h ew a t e r m a r k g r e a t l y f i n a l l y , o nt h eb a s i so fa n a l y z i n gt h ec h a r a c t e r i s t i c so fr e l a t i o n a ld a t a b a s e ，w ep r e s e n ta w a t e r m a r k i n ga l g o r i t h mb a s e do ng a a a t h i sp a p e rf o c u s e so nr e l a t i o n a ld a t a b a s eb a s e do ng a a aw a t e r m a r ko p t i m i z a t i o n a l g o r i t h m e x p e r i m e n t sc l e a r l ys h o wt h a tt h ep r o p o s e dd a t a b a s ew a t e r m a r ka l g o r i t h mi sf l e x i b l e a n dc o n v e n i e n t t h i st e c h n i q u ei sr e s i l i e n tt od e l e t i o n ，i n s e r t i o na n do t h e ra t t a c k s k e y w o r d s ：r e l a t i o n a ld a t a b a s ew a t e r m a r k i n g ；g a ；c o p y r i g h tp r o t e c t i o n ；g a a a ： t h e o p t i m i z a t i o no fw a t e r m a r k i n g i i 目录 目录 摘要i a b s t r a c t i i 第1 章绪论l 1 1 关系数据库水印技术的研究背景和现状1 1 2 研究的意义3 1 3 研究的主要内容和创新点3 1 4 论文的结构安排4 第2 章关系数据库数字水印技术概述6 2 1 关系数据库和数字库水印简介6 2 2 数据库水印分析6 2 2 1 数据库对水印技术的要求7 2 2 2 一般数据库数字水印技术的理论分析8 2 2 3 关系数据库中数字水印的攻击9 2 2 4 理想的数据库水印技术1 0 2 3 关系数据库水印优化的必要性与可行性分析1 0 2 3 1 必要性分析l o 2 3 2 可行性分析1 l 2 4 关系数据库水印优化的一般思路1 1 2 5 现有的关系数据库水印优化算法1 2 2 5 1 模式搜索算法1 2 2 5 2 遗传算法1 2 2 5 3 混合遗传算法1 3 第3 章基于g a 的关系数据库水印优化算法15 3 1 基于g a 的关系数据库水印优化算法产生的缘由1 5 3 2 基于g a 的关系数据库水印算法框架1 5 3 3 基于g a 的关系数据库水印优化算法的一般过程1 6 3 3 1 水印预处理1 6 3 3 2 元组的标记和选择1 8 3 3 3 数据库元组的分组1 9 3 3 4 水印信息的优化嵌入过程2 0 3 3 5 水印提取与检测算法2 l 3 4 算法仿真2 4 目录 3 4 1 算法仿真实验环境2 4 3 4 2 实验结果2 5 3 4 3 小结2 7 第4 章基于g a a a 的关系数据库水印优化算法2 9 4 1g a a a 算法简介2 9 4 2 基于g a a a 的关系数据库水印优化算法的设计思路3 1 4 3 基于g a a a 的关系数据库水印优化算法的一般过程3 2 4 3 1 水印生成算法3 2 4 3 2 关系数据库水印嵌入算法描述3 3 4 3 3 水印提取与检测算法3 5 4 4 算法仿真3 6 4 4 1 算法仿真实验环境3 6 4 4 2 透明性测试3 7 4 4 3 鲁棒性测试3 7 4 4 4 小结3 9 第5 章总结与展望4 1 5 1 总结4 l 5 2 本文的主要创新点4 2 5 3 不足和工作展望4 2 5 3 1 研究中的不足4 2 5 3 2 工作展望4 2 参考文献4 4 读硕士学位期间发表的论文4 6 致谢4 7 图1 - 1 水印的嵌入4 图卜2 水印的检测4 图2 - 1 关系数据库水印嵌入模型8 图2 - 2 关系数据库水印嵌入模型9 图2 3 关系数据库水印优化的一般思路图1 2 图2 - 4 遗传算法的基本流程图1 3 图2 5 混合遗传算法构成示意图1 4 图3 - 1 基于g a 的数据库水印优化算法框图1 5 图3 - 2 水印生成图1 7 图3 - 3 完整性检测2 3 i v 目录 图3 4 水印的恢复 图3 - 5 实验数据库的设计表图 图3 6 遗传算法搜索最优解的过程 图3 7 嵌入前后元组的比较 图3 8 对子集删除攻击的弹性比较 图3 - 9 对子集增加攻击的弹性比较 图3 1 0 对子集更改攻击的弹性比较 图4 1g a a a 算法流程图 图4 2 基于g a a a 的关系数据库水印模型 图4 - 3 水印生成算法 图4 - 4 基于g a a a 的关系数据水印嵌入算法 图4 - 5g a a a 搜索最优解的过程 图4 7 子集选择攻击后水印检测率 图4 - 8 子集更改攻击后水印检测率 图4 9 子集增加后水印的检测率 表3 一l 算法参数定义 表3 - 2 水印多数选举过程 表3 3t h e0g e n e r a t i o n 表4 - 1 加入水印对数据库集中量数的影响 表4 2 子集选取攻击后检测结果 表4 3 子集更改攻击后检测结果 表4 4 子集增加攻击后检测结果 v 3 4 5 6 6 7 7 l 2 2 4 7 8 8 9 6 2 5 7 8 8 9 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 l 2 2 3 3 3 3 第1 章绪论 第1 章绪论 本章首先概述了关系数据库水印技术的研究背景和意义，并对关系数据库水印技术的 研究进展和发展现状做了重点阐述；其次，介绍了本文的主要研究内容和创新点：最后， 给出了全文的结构安排。 1 1 关系数据库水印技术的研究背景和现状 随着数据库技术和网络技术应用范围的只益扩大，数字远程教育日益兴起。数据库是 数字化远程教育资源最主要的存储形式，它在信息时代的远程教育中发挥着举足轻重的作 用。数据库具有信息存储容量大、检索方便快捷、操作使用简单、实用性强等特点，因此， 数据库技术使远程教育资源的共享和传播更加简单，同时非授权用户对远程教育资源的窃 取和篡改也更加方便，导致教育作品侵权问题同益严重。目前，尊重和保护知识产权已成 为世界潮流，如何防止网络上未经授权的教育资源扩散成为当前数据库版权保护所要研究 的重点课题之一。数据库水印技术作为一种有效解决数据库版权问题的新兴技术由此成为 人们研究的热点。 目前，多媒体数字水印算法已逐渐成熟，软件产品也很早上市，但关系数据库数据对 象与多媒体数据对象两者特点之间的差别决定着多媒体数字水印算法无法直接应用于关 系数据库。因此，关系数据库水印技术的研究难度很大，研究进展缓慢。i b ma l m a d e r l 研 究中心的r a g r a w a l 和j k i e m a n 及美国p u r d u e 大学的r s i o n 等学者于2 0 0 2 年先后提出将数 字水印技术应用于关系数据库的安全控制领域【2 儿引。自他们在数据库水印领域开展的开创 性研究以来，数据库数字水印技术受到人们越来越多关注。关系数据库水印的目的是通过 数字水印技术对关系数据库的进行完整性控制、真实性验证，以此来保护关系数据库。大 约从2 0 0 3 年开始，我国学者也开始了对数据库水印技术方面的研究。哈尔滨工业大学的牛 夏牧教授等人于2 0 0 3 年提出了一种可以在关系数据库中嵌入具有实际意义字符串的数据 库水印算法【4 l 。2 0 0 4 年，清华大学软件学院的张指浩等人提出了一种将图像作为水印信息 嵌入载体数据库的新型数据库水印算法。此外，国内外其他水印研究人员也为推进数据库 水印技术的发展做了许多努力f 5 】- 【9 l 。 ( 1 ) 2 0 0 2 年，r a g r a w a l 等人首次进行了向关系数据库中嵌入比特位模式水印的实验【l 0 1 。 在不影响关系数据库有用性的前提下，通过对关系数据库中某些数值型属性的最低有效位 ( l e a s ts i g n i f i c a n tb i t s ，l s b ) 进行位操作，引入少量的误差，以此来实现关系数据库水印信 息的嵌入过程。该方案的优点是实现简单方便，但缺点是数字水印的嵌入对关系数据库数 据修改较大，若关系数据库数据容量较小，则数字水印的嵌入就很容易影响到数据库的有 用性，因此利用该方案很难向关系数据库中嵌入有实际意义的水印信息。 ( 2 ) 美国p u r d u e 大学的r s i o n 等人提出了基于“均方差 误差校验的关系数据库水印算 第1 章绪论 法，该算法对数值相差不大、具有相同分布的关系数据比较适用。但由于关系数据中不同 字段的取值范围可能相差较大，这就导致了这种算法只能适用于关系数据的部分数据项， 从而限制了水印的嵌入位置和容量【l 。 ( 3 ) 新加坡管理大学的y i n g i i ul i 等人提出了一种可用于数字水印和数字指纹的关系数 据库水印算法，并且他们还对数值型数据集虚拟键( v i r t u a lp r i m a r yk e y ) 的构造方法进行了 一系列研究i l2 1 。利用该算法关系型数据库中的所有元组依据一些安全参数被秘密分组，水 印被独立的嵌入到各分组中，因此水印嵌入导致对关系数据库的修改可以被定位到具体的 元组。 ( 4 ) 解放军通信工程学院的张勇在云模型理论的基础上提出了基于主键值和内容为特 征的数据库水印方案。但对于一个多维的正态云，若每一维用三个数字特征完整地表示， 然后将这些数字特征作为水印，则数据库能嵌入的有意义的信息量相当有限，进而导致利 用这种方案很难向数据库中嵌入有意义的水印信息1 1 3 1 。 ( 5 ) 在研究多媒体数字水印的基础上，哈尔滨工业大学的孙圣和、陆哲明、牛夏牧等 教授也提出了相应的数据库数字水印算法【1 4 l 。 ( 6 ) p u r d u e 大学的m o h a m e ds h e h a b 等人把关系数据库水印的嵌入过程作为一个求约束 条件下的最优化问题，提出了利用遗传算法和模式搜索等算法来优化数据库水印的方案。 与此同时，该方案还提出了一种新的元组分组方案，该方案不依赖数据库中标志元组进行 分组，因此可以有效的抵抗水印中同步误差。同时，在解码过程中设定最佳阈值，使得解 码过程的错误降到最低，使该算法的鲁棒性大大提耐”j 。 随着关系数据库水印研究的不断增多，不同的关系数据库水印方案纷纷问世。目前， 大多数的关系数据库水印算法主要是通过在一定误差范围内修改数据来进行水印嵌入，即 “嵌入式 的关系数据库数字水印技术，研究的热点也主要集中在向关系数据库中数值型 数据添加水印的方法，向非数值型数据类型中添加水印的研究还非常少。此外，关系数据 库水印技术研究热点主要集中在水印的嵌入和水印检测过程，关于关系数据库水印优化方 面的研究还刚刚起步，研究成果还相对较少，并且存在着以下几个方面的不足： 首先，己有的关系数据库水印方案的都是要通过修改数据库数值型属性的值来完成水 印的嵌入操作，这必然导致数据库的使用价值与数据库水印技术在一定程度上产生矛盾。 如果要确保数据库的使用价值就必须最大限度的减少水印嵌入量，但这样必定会影响到数 字水印算法的鲁棒性。 其次，数据库只有允许一定误差的前提下才能进行水印信息的嵌入操作，这使水印嵌 入方案的鲁棒性和安全性受到限制，同时也增加了水印嵌入的难度。 因此，本文在总结己有工作的基础上，针对前人提出的关系数据库水印优化算法的局 限性，提出了基于遗传算法的关系数据库水印优化算法。并在此基础上，充分利用混合遗 传算法中g a a a 算法的优点，提出了基于g a a a 的关系数据库水印优化算法。该算法可以 最大限度的协调数字水印的鲁棒性、透明性和数据库的使用价值之间的矛盾，起到了对关 2 第l 章绪论 系数据库水印进行优化的作用。 1 2 研究的意义 在网络信息化时代，随着远程教育和计算机技术的同益普及化，关系数据库技术已经 广泛应用于社会的各个行业，并在人们的社会工作、学习和同常生活中发挥着越来越重要 的作用。随着人们知识产权保护意识的增强以及数据库技术的r 益进步，数据库的信息安 全问题受到越来越多的关注和重视。数据库数字水印是在不影响数据库有用性的前提下， 将代表数据库所有者版权的水印信息嵌入到关系数据库中，从而有效的将关系数据库与其 拥有者紧密联系起来，进而达到对数据库版权保护的目的。 关系数据库数字水印技术的研究，不但可以为数据库的版权保护提供新的有效的技术 支撑，进而提高数据库的安全性，而且能够为网络上共享教育资源的知识产权保护提供有 力技术保障。因此，研究关系数据库数字水印进而实现对关系数据库的版权保护有着非常 重要的学术意义和应用价值。与此同时，数据库水印技术的研究能有效的促进远程教育的 推广和应用。无论是从理论、技术层面上，还是在应用层面上讲，关系数据库数字水印技 术的研究都具有深远的意义。数据库数字水印作为数据库安全领域的新生事物，尽管其研 究还刚刚起步，但其研究具有很重要的理论意义和广阔的应用前景。 1 3 研究的主要内容和创新点 本文将在对当前关系数据库水印算法进行系统梳理的基础上，将关系数据库水印信息 的预处理过程和水印信息的嵌入过程均视为求解一定约束条件下的最优化问题，提出了利 用遗传算法、g a a a 等求解约束优化问题的关键技术来优化关系数据库水印的初步设想。 在详细分析关系数据库水印优化的必要性和可行性的基础上，本文首先总结并提出了关系 数据库水印优化的一般思路，然后，对关系数据库水印优化算法的具体实现做了深入研究， 最后，本文通过仿真实验验证了本文提出的算法的可行性和有效性。论文的主要内容和创 新点如下： ( 1 ) 嵌入式数据库水印的基本思想 设给定数据库关系表r ( m s a ，a 1 ，a 2 ，a v ) ，其中，m s a 表示关键属性，a i ，a 2 ， a v 表示关系表r 中的v 个属性。表中某些数值型属性值，例如某些属性值的最低有效位( 1 e s s s i g n i f i c a n td i g i t ，l s d ) ，可以有微小的改变而不会导致数据的使用价值降低，而另外一些 属性，例如关键属性( m o s ts i g n i f i c a n ta t t r i b u t e s ，m s a ) ，是不允许用户改动的，一旦数据窃 取者改变了这些属性值，关系数据库的有用性将会大大降低或丧失。因此，将水印信息转 换成比特流，通过修改关系数据库中的某些属性值，可以将水印信息嵌入到数据库中，以 此实现对数据库的版权保护。嵌入式关系数据库水印的嵌入算法与提取算法的模型分别如 下图1 1 与1 2 所示。 3 第l 章绪论 图1 - 1 水印的嵌入 图1 - 2 水印的检测 ( 2 ) 关系数据库水印优化的一般思路 首先，利用优化算法优化水印信息，提取出最有代表性的水印信息值，使关系数据库 待嵌入的水印信息量最优，从而最小化了水印信息量，进而保证了关系数据库水印具有较 好的透明性。 其次，利用优化算法选择最优的水印嵌入位置。由于在关系数据库中每个属性的可允 许改变的阈值不同，因此可以利用优化算法在不破坏关系数据库的有用性的前提下选择最 优的水印嵌入位置和嵌入强度。 ( 3 ) 基于遗传算法的关系数据库水印优化算法 在关系数据库水印优化的一般思路的指导下，并总结i ； 人的研究成果，本文提出了基 于遗传算法的关系数据库水印优化算法。首先利用遗传算法对水印信息进行预处理，接着， 利用遗传算法寻求最优的嵌入位置，从而实现将处理后的水印信息嵌入到数据库相应的元 组当中，以此来弥补原有关系数据库算法水印稳健性差的缺点。 ( 4 ) 基于g a a a 的关系数据库水印优化算法 为了克服遗传算法在某些情况下收敛性差的缺点，本文提出了基于g a a a 的关系数据 库水印优化算法。利用g a a a 算法对水印进行预处理，而后利用g a a a 算法寻求最优的嵌 入位置，实现将最具有代表性的水印信息以最优的嵌入强度嵌入到数据库最优的元组当 中，以此来达到对关系数据库水印进行优化的目的。 1 4 论文的结构安排 论文的结构如下： 4 第l 章绪论 第一章，绪论。主要介绍了关系数据库水印的研究背景和意义，并重点阐述了数据库 水印的发展现状，并列出了全文的主要工作和创新点。 第二章，关系数据库数字水印技术概述。首先阐述了数字库水印的基本概念，并对一 般的关系数据库水印技术、数据库水印的特点以及数据库水印的常见攻击等基本理论做了 详细阐述。在分析关系数据库水印优化的必要性和可行性的f j i 提下，总结并提出了关系数 据库水印优化的一般思路。 第三章，基于遗传算法的关系数据库水印优化算法。在分析前人提出的关系数据库水 印算法优缺点的基础上，提出基于遗传的关系数据库水印优化算法。此算法不但对水印信 息产生的过程进行了优化，也对水印的嵌入过程进行了优化，大大提高了水印的抗攻击能 力。实验结果证实了本算法的可行性、有效性和鲁棒性。 第四章，基于g a a a 的关系数据库水印优化算法。在对关系数据库的特点进行详细分 析的基础上，提出了基于g a a a 的关系数据库水印优化算法。首先，将g a a a 算法优化 处理后的水印信息利用差错控制技术进行编码：接着利用g a a a 算法优化选择关系数据库 水印最佳嵌入位置；最后，利用多数选举机制来提高水印的正确提取能力。 第五章，总结与展望。对本文的研究进行了全面的总结，并在指出本文研究不足的同 时提出今后工作的展望 第2 章关系数据库数水印技术概述 第2 章关系数据库数字水印技术概述 2 1 关系数据库和数据库水印简介 关系型数据库是由e e c o d d 在2 0 世纪7 0 年代初提出的以关系模型为基础数据库系 统。其中，关系模型是建立在e r 模型和关系概念基础上的一种数据模型。经过近半个世 纪的发展，数据库技术现在已经比较成熟。微软的s q l s e r v e r 2 0 0 5 、o r a c l e 公司的o r a c l e 9 、 i b m 公司的d b 2 、m y s q l 和a b 公司的m y s q l 等都是关系型数据库管理系统中比较典 型的代表。 数据库水印技术是数据库安全领域内一项非常有意义的技术，它是指在不破坏数据库 内容和数据库可用性的前提下，借助信号处理的方法向数据库中嵌入难以去除的隐蔽的水 印标记。当数据库发生版权纠纷时，人们就可以通过相应的水印提取算法将嵌入在数据库 中的水印标记提取出来并进行验证，进而达到声明数据库数据版权的目的1 1 6 1 。随着数据库 技术的快速发展，作为数据库安全领域的一种重要技术，数据库数字水印研究受到越来越 多的关注，并成为计算机科学技术中发展最快、应用最广的技术之一。 2 2 数据库水印分析 对数字水印进行分类的方法很多，分类的角度和出发点不同导致了数字水印分类的不 同。按水印的抗攻击能力，数据库水印可以分为鲁棒性数字水印和脆弱性水印。前者主要 应用于数据库的版权保护，后者则主要应用于数据的篡改和完整性检测。本文研究的是用 来进行版权保护的鲁棒性水印。由于数据库数据与多媒体数据相比具有很大的特殊性，而 且在关系数据库中很难找到水印标记可嵌入的可辨认的冗余空间，因而研究关系数据库水 印具有一定的难度。为了更好的研究和探讨关系数据库水印技术，下面首先来分析一下关 系数据库中的关系数据和多媒体数据之间的区别。它们之间的区别主要表现在以下几个方 面2 1 【17 1 。 ( 1 ) 关系数据具有最小的冗余度 关系数据库是由大量的元组组成的，数据库元组具有相对的独立性。关系数据库以面 向系统的观点组织数据，因此关系数据具有最小的冗余度。多媒体数据对象是由大量的位 组成的，并且许多冗余位可以用来隐藏水印信息，因此，水印可以分散地隐藏在这些单独 的对象罩面。 ( 2 ) 关系数据具有无序性 关系数据库具有高度的数据独立性，构成数据库的元组之间及属性之间是无序的，数 据问不存在依赖关系，元组之间和属性之间的顺序可以任意改变，没有相对稳定的空间结 构。多媒体数据对象各个点之间存在着空间上的有序关系，相近位置还具有相似模糊性， 可以通过差值补间。 6 第2 章关系数据库数水印技术概述 ( 3 ) 关系数据具有灵活性 关系数据库数据具有灵活性，需要用户对它进行经常的维护和更新。数据库管理系统 也不是简单的把数据进行堆积，而是在记录数据信息的基础上具有编辑、修改等很多的管 理功能。此外，关系数据库中的数据往往需要进行逻辑或算术等运算。多媒体数据一旦编 制而成，一般很少进行更新，而且对多媒体数据人们一般很少进行逻辑或算术运算。 ( 4 ) 关系数据的机读性 关系数据一般是通过关系数据库管理系统进行管理，具有机读性，因此，简单的去掉 关系数据库中的某些元组或用其它类似的元组来替换关系数据库中某些元组都很难被人 们发现。因为静态的多媒体数据一般更新较少，如果多媒体数据对象某个部分被删除或替 换，很容易引起知觉上的变化而被人们发现。因此，多媒体数字水印技术可以基于人类视 觉模型( h v s ) 或听觉模型( h a s ) 来实现水印信息的隐蔽嵌入。 由上述可知，关系数据对象和多媒体数据对象之间的差别很大，导致了多媒体数字水 印技术不能直接应用于关系数据库，以至于研究关系数据库数字水印技术存在着很大的难 度i 引。 2 2 1 数据库对水印技术的要求 水印信息嵌入引入的误差必须在用户可容忍的误差范围之内，即数据库水印的嵌入不 会导致数据库有用性丧失。如果把数字水印嵌入关系数据库的过程视为在较强背景载体上 叠加一个较弱的信号，则要满足叠加的水印信号强度低于数据库可用性所允许的失真度门 限值。关系数据库是一种特殊的记录数据的载体，它对水印技术的要求可总结如下 1 9 1 2 0 1 。 ( 1 ) 透明性 关系数据库中的数据对象具有很强的语法结构和语法意义，冗余度非常小。水印信息 只能在不影响数据的可用性的前提下进行嵌入，水印的嵌入不能破坏原始数据库的语法结 构和语法意义。 ( 2 ) 安全性 一般情况下，关系数据库中的数据在应用过程中需要进行一系列运算，而且关系数据 库数据正常的维护更新比较频繁。在应用中，关系数据库也有可能受到攻击者的恶意攻击。 这就必须要求关系数据库数字水印在关系数据一系列的运算、更新或攻击后，水印仍能附 着于关系数据库的数据对象之上。 ( 3 ) 盲检性 一般而言，数据库的数据量一般比较大，维护和更新也比较频繁。为了减轻水印检测 系统的负担，必须要求水印的检测过程不能依靠可能已经更新的原始数据库或原始水印信 息就能将水印检测出来。 7 第2 章关系数据库数字水印技术概述 2 2 2 一般数据库数字水印技术的理论分析 目前，关系数据库水印研究的热点主要集中在以关系数据库允许一定量误差为前提的 “嵌入式 的数字水印技术上，这种技术只适合于特定的数据库。虽然各种嵌入式的数据 库数字水印算法具体实现过程各异，但各种算法在原理上基本相似，主要包含水印嵌入和 水印检测两个核心过程。通常而言，水印的检测过程是水印嵌入过程的逆过程1 8 】【1 9 】。 ( 1 ) 水印嵌入过程 数据库数字水印的嵌入过程是将数字水印信号自适应地叠加到关系数据库的某些元 组和属性当中。这个过程通常包括原始数据库、水印信息、嵌入密钥和嵌入算法等四个核 心要素，涉及水印嵌入位置、嵌入强度和嵌入方式等几个关键问题。一般而言，关系数据 库水印嵌入算法的研究主要取决于数据库水印信号容量和新的嵌入通道的寻找。关系数据 库水印的嵌入模型如图2 1 所示。 图2 - 1 关系数据厍水印嵌入模型 ( 2 ) 水印检测过程 当关系数据库发生版权纠纷时，人们就可以通过水印提取算法提取水印信息从而对数 据库的版权归属进行判决。水印检测过程的任务是判断待检测的关系数据中是否含有指定 的水印信息，检测的结果依赖于给定的决策阈值【2 1 1 。数据库水印的检测过程主要包含检测 密钥、待检测的数据库和检测算法三个核心要素。水印检测过程的输入是检测密钥和待检 测的关系数据库，有时还需要原始水印信息或原始数据库的参与；水印检测过程的输出是 提取出的水印信号或表明待检测数据库中存在给定水印信息的某种可信度值。水印验证 时，只需要计算检测到的水印信息与原始水印信息之间的相似度或相关性。水印的检测模 型如图2 2 所示。 8 第2 章关系数据库数水印技术概述 待检测数据库 原始数据库 图2 2 关系数据库水印嵌入模型 2 2 3 关系数据库中数字水印的攻击 关系数据库水印技术在保护数据库知识产权方面是一种很有前景的方法。随着人们知 识产权意识的增强以及数字水印技术的进步，数据库水印技术在数据库版权方面也起到了 很大的作用。但与此同时，各种数据库数字水印的攻击技术也与日剧增。因此，人们对数 据库水印的稳健性要求也要来越高。 与静态的多媒体数据不同，关系数据库数据需要定期维护更新，嵌入到关系数据库中 的水印标记不能因此被删除，否则，关系数据库水印技术在数据库的版权保护中变得毫无 意义。除此之外，数据窃取者如果在无意中获知关系数据中嵌入了水印信息，他们就会采 取各种形式的恶意攻击，试图删除嵌入在关系数据库中的水印信息，或者用其他方法声明 自己对关系数据的伪所有权【2 2 1 。因此，关系数据库水印应能够抵抗数据窃取者各种形式的 恶意攻击有效的保护数据的所有权。目前，关系数据库水印常见的恶意攻击方式有以下几 种【1 3 】1 2 3 】。 子集增加攻击：数据窃取者向水印数据库中添加一些结构相似的属性和元组，这样会 增加数据库水印提取的难度，甚至导致嵌入在关系数据库中的水印信息无法被正确提取出 来。 子集选取攻击：数据窃取者仅使用水印数据库的部分元组和属性，企图能够擦除嵌入 在关系数据库中的水印信息。 子集更改攻击：数据窃取者通过更改水印数据库中的部分属性值，以此希望能够擦除 嵌入在数据库中的水印信息。 添加攻击：数据窃取者向窃取来的水印数据库中重复添加自己的水印信息，并声明自 己对关系数据库的所有权。 混合和匹配攻击：数据窃取者比较和分析包含相似信息的多个关系数据库，并从中选 择不相连的多个元组创建新的关系数据库。 可逆性攻击：假若数据窃取者在其偷来的关系数据库中发现了一个虚幻的水印，因此 9 第2 章关系数据库数水印技术概述 声称自己对关系数据的所有权。然而实际上数据窃取者所声称的水印只是随机出现的水 印。 关系数据库水印攻击的实质是导致关系数据库部分属性值的匹配信息丢失，使得水印 检出率降低。针对不同的关系数据库水印算法，数据窃取者采用的攻击方式各不相同，但 每个水印算法都应能够有效抵抗各种形式的攻击，都应具有较强的鲁棒性。 2 2 4 理想的数据库水印技术 关系数据库本身的特征决定了关系数据库水印技术比多媒体水印技术有更大的挑战。 关系数据库水印算法应充分考虑到关系数据库本身的特点以及各种形式的攻击，其基本要 求就是关系数据库水印算法要在鲁棒性、透明性之间折中考虑。关系数据库水印嵌入算法 的关键是保持数据库本身的结构不变，外键值的变动不能改变数据表之间的正常连接。理 想的关系数据库数字水印技术应具备以下特点【1 6 】1 1 8 】。 ( 1 ) 鲁棒性强 数据库在使用过程中通常需要正常的维护和更新，而且时刻面临着数据窃取者的恶意 攻击和修改，这就要求数据库经过善意的更新或恶意攻击后，水印信息应能保持一