论文部分内容阅读
摘 要：本文分析了一种数据库的水印嵌入和提取检测算法，利用数值型数据允许误差，嵌入水印信息。同时，在水印提取和检测算法中采用二次投票机制，为水印提供了较好的鲁棒性。
关键字：数字水印；关系数据库；投票机制
一、背景简介
数字水印技术利用数字产品的冗余，将水印信息作为噪声嵌入数字产品，以证实它的所有权，同时不影响宿主数据的可用性。R.Agrawal 和J.Kiernan 在他们的论文［1］中指出，数值型数据存在冗余，可以将水印技术引入数据库中。同时，他们也指出数据库水印与传统水印之间存在的区别［1］：
1.1.多媒体数据拥有大量冗余比特存放水印信息；数据库由记录组成，需要将水印信息扩散到不同的记录中。
1.2.多媒体对象中不同片断之间的关系是固定不变的；关系数据库中的记录间没有对应的关系，各个字段之间也没有固定的关系。
1.3.删除或排序多媒体对象的部分，会引起人们的注意；更新操作却是正常的数据库应用。
不同的特性和应用方式，使得数据库不可能直接套用现有大量的传统数字水印技术。目前数据库水印技术主要可以分为三类：
1.4.R.Agrawal［1］、R.Sion［2］提出的方法是将数据库中所有的属性排序，利用主键选取候选记录或子集，指定嵌入的位置，最后再进行水印嵌入的操作。这类方法有个不足：
需要对字段进行预先的排序，一旦记录、字段的顺序被操纵，就会使水印检测失败。
1.5.有一些算法将整个表固定下来，再进行水印的嵌入和提取。如李德毅院士提出的云理论［3］算法。又如，人为地将表看成二维“图像”［4］，借鉴传统方法对“图像”进行水印的嵌入和提取检测。这类方法有两个问题：第一，提取水印时，需要原始的“图像”作比照；其次，固定整个表的行为是不可行的，因为更新是数据库主要的操作。
1.6.对表进行处理，将产生的水印记录插到表中［5］。这类方法没有扩散水印信息，而是集中在几条特殊的记录中，使得这种方法的抗攻击性和鲁棒性都不如前面两类方法。
二、数字水印算法分析
R.Agrawal 和Jerry Kiernan 在论文中［1］给出了一种
数字水印算法：首先对所有可用属性排序；计算F ( r .pkey)，选取记录r、属性r.Ai 和r.Ai.j，作为嵌入位；嵌入值由H(Key o r.pkey)决定。提取检测过程以同样的步骤，取出r.Ai.j 的值，并和H(Key o r.pkey)进行比较。如果匹配数/ 总数大于阈值，就接受水印存在的事实。相对于R.Agrawal 和Jerry Kiernan 的算法，结合对数据库安全应用研究，有以下几个方面值得改进：
首先，充分利用可用属性，为水印算法提供更多的冗余位，同时也能避免排序问题。
其次，用字段的特性决定具体的嵌入位置，只需要在算法初始化时计算一次。
第三，用二次投票机制：在记录一级和表一级，都要投票决定嵌入的信息。
第四，用户可选用有具体意义的水印信息，而不是用无意义的0或1表示嵌入的信息。
当用户水印和其它水印距离d越大，恶意者需要改动的记录就越多，攻击的成功率就越小。设总共有η条记录，γ决定了候选记录数量，那么共有k =η/γ条候选记录。设水印的长度为L，则水印将重复嵌入t=k/L=η/(γL)次。如果恶意者对数据库进行攻击，操纵了a条记录，其中xi表示嵌有水印W.i 的记录数量，x L表示从非候选记录集中选取的、没有嵌入任何信息的记录数量。那么：
假定水印之间的距离d=1，那么攻击者至少需要更改int(t/2+1)条指向同一位信息的记录，即存在一个i，使xi≥int(t/2+1)。
三、水印算法
水印嵌入算法的一种改进算法：
输入一个数组，数组元素值不是0就是1，Vote 函数返回投票结果∈{0，1}。Similar 函数比较W 和RW，返回两者的相似程度。阈值τ决定了是否接受W 为水印信息，不同的水印之间应该有足够的空间距离d，使水印信息不会轻易地变成其它的水印，0<τ< d 。
四、小节
本文提出的算法有以下几个特点：
1.嵌入和检测水印时，无需对记录和属性排序，也不需要固定表。重新排序表不会破坏水印信息，也不会影响水印信息的提取和检测。
2.用密钥处理r.key，使得生成的整数具有随机性，水印信息能均匀地分布到整个表中；且水印信息的每个比特嵌入的次数也大致一样。
3.从表约束条件和字段定义中得到A i允许误差d≠0，并一次性计算出MDB(Ai)，因此也提高了算法的速度。
4.将水印信息分散到许多不相干的记录中，加强了水印的抗干扰性。当重复嵌入的次数t 越大，攻击的成功率越低。
5.用大量的冗余位存放同一个比特，并结合二次投票机制，保证嵌入信息的准确性和可靠性，有效地降低各种操作对水印信息的影响。
6.本算法允许用户决定水印信息及空间距离d，用以平衡算法性能和水印的鲁棒性，提供更多的灵活性。
［参考文献］
［1］ Agrawal R，Kiernan J.Watermarking Relational Databases［C］.Proceedings of the 28th VLDB Conference，2002.
［2］ Sion R，Atallah M，Prabhakarl S.Watermarking relational databases［C］.Indiana：the Center for Education and Research in Information Assurance and Security of Purdue University，2002.
［3］ Zhang Yong，Niu Xiamu，Zhao Dongning.A Method of Protecting Relational Databases Copyright with Cloud Watermark［C］.International Journal of Information Technology，2004，(4).
［4］ Zhang Zhihao，Jin Xiaoming，Wang Jianmin，et al.Watermarking Relational Database Using Image［C］.Proceedings of the Third International Conference on Machine Learning and Cybernetics，2004，(8)：26-29.
［5］ Yingjiu Li，Vipin Swarup，Sushil Jajodia.Fingerprinting Relational Databases［C］：Schemes and Specialties. IEEE Transactions on Dependable and Secure Computing，2005，2(1).
关键字：数字水印；关系数据库；投票机制
一、背景简介
数字水印技术利用数字产品的冗余，将水印信息作为噪声嵌入数字产品，以证实它的所有权，同时不影响宿主数据的可用性。R.Agrawal 和J.Kiernan 在他们的论文［1］中指出，数值型数据存在冗余，可以将水印技术引入数据库中。同时，他们也指出数据库水印与传统水印之间存在的区别［1］：
1.1.多媒体数据拥有大量冗余比特存放水印信息；数据库由记录组成，需要将水印信息扩散到不同的记录中。
1.2.多媒体对象中不同片断之间的关系是固定不变的；关系数据库中的记录间没有对应的关系，各个字段之间也没有固定的关系。
1.3.删除或排序多媒体对象的部分，会引起人们的注意；更新操作却是正常的数据库应用。
不同的特性和应用方式，使得数据库不可能直接套用现有大量的传统数字水印技术。目前数据库水印技术主要可以分为三类：
1.4.R.Agrawal［1］、R.Sion［2］提出的方法是将数据库中所有的属性排序，利用主键选取候选记录或子集，指定嵌入的位置，最后再进行水印嵌入的操作。这类方法有个不足：
需要对字段进行预先的排序，一旦记录、字段的顺序被操纵，就会使水印检测失败。
1.5.有一些算法将整个表固定下来，再进行水印的嵌入和提取。如李德毅院士提出的云理论［3］算法。又如，人为地将表看成二维“图像”［4］，借鉴传统方法对“图像”进行水印的嵌入和提取检测。这类方法有两个问题：第一，提取水印时，需要原始的“图像”作比照；其次，固定整个表的行为是不可行的，因为更新是数据库主要的操作。
1.6.对表进行处理，将产生的水印记录插到表中［5］。这类方法没有扩散水印信息，而是集中在几条特殊的记录中，使得这种方法的抗攻击性和鲁棒性都不如前面两类方法。
二、数字水印算法分析
R.Agrawal 和Jerry Kiernan 在论文中［1］给出了一种
数字水印算法：首先对所有可用属性排序；计算F ( r .pkey)，选取记录r、属性r.Ai 和r.Ai.j，作为嵌入位；嵌入值由H(Key o r.pkey)决定。提取检测过程以同样的步骤，取出r.Ai.j 的值，并和H(Key o r.pkey)进行比较。如果匹配数/ 总数大于阈值，就接受水印存在的事实。相对于R.Agrawal 和Jerry Kiernan 的算法，结合对数据库安全应用研究，有以下几个方面值得改进：
首先，充分利用可用属性，为水印算法提供更多的冗余位，同时也能避免排序问题。
其次，用字段的特性决定具体的嵌入位置，只需要在算法初始化时计算一次。
第三，用二次投票机制：在记录一级和表一级，都要投票决定嵌入的信息。
第四，用户可选用有具体意义的水印信息，而不是用无意义的0或1表示嵌入的信息。
当用户水印和其它水印距离d越大，恶意者需要改动的记录就越多，攻击的成功率就越小。设总共有η条记录，γ决定了候选记录数量，那么共有k =η/γ条候选记录。设水印的长度为L，则水印将重复嵌入t=k/L=η/(γL)次。如果恶意者对数据库进行攻击，操纵了a条记录，其中xi表示嵌有水印W.i 的记录数量，x L表示从非候选记录集中选取的、没有嵌入任何信息的记录数量。那么：
假定水印之间的距离d=1，那么攻击者至少需要更改int(t/2+1)条指向同一位信息的记录，即存在一个i，使xi≥int(t/2+1)。
三、水印算法
水印嵌入算法的一种改进算法：
输入一个数组，数组元素值不是0就是1，Vote 函数返回投票结果∈{0，1}。Similar 函数比较W 和RW，返回两者的相似程度。阈值τ决定了是否接受W 为水印信息，不同的水印之间应该有足够的空间距离d，使水印信息不会轻易地变成其它的水印，0<τ< d 。
四、小节
本文提出的算法有以下几个特点：
1.嵌入和检测水印时，无需对记录和属性排序，也不需要固定表。重新排序表不会破坏水印信息，也不会影响水印信息的提取和检测。
2.用密钥处理r.key，使得生成的整数具有随机性，水印信息能均匀地分布到整个表中；且水印信息的每个比特嵌入的次数也大致一样。
3.从表约束条件和字段定义中得到A i允许误差d≠0，并一次性计算出MDB(Ai)，因此也提高了算法的速度。
4.将水印信息分散到许多不相干的记录中，加强了水印的抗干扰性。当重复嵌入的次数t 越大，攻击的成功率越低。
5.用大量的冗余位存放同一个比特，并结合二次投票机制，保证嵌入信息的准确性和可靠性，有效地降低各种操作对水印信息的影响。
6.本算法允许用户决定水印信息及空间距离d，用以平衡算法性能和水印的鲁棒性，提供更多的灵活性。
［参考文献］
［1］ Agrawal R，Kiernan J.Watermarking Relational Databases［C］.Proceedings of the 28th VLDB Conference，2002.
［2］ Sion R，Atallah M，Prabhakarl S.Watermarking relational databases［C］.Indiana：the Center for Education and Research in Information Assurance and Security of Purdue University，2002.
［3］ Zhang Yong，Niu Xiamu，Zhao Dongning.A Method of Protecting Relational Databases Copyright with Cloud Watermark［C］.International Journal of Information Technology，2004，(4).
［4］ Zhang Zhihao，Jin Xiaoming，Wang Jianmin，et al.Watermarking Relational Database Using Image［C］.Proceedings of the Third International Conference on Machine Learning and Cybernetics，2004，(8)：26-29.
［5］ Yingjiu Li，Vipin Swarup，Sushil Jajodia.Fingerprinting Relational Databases［C］：Schemes and Specialties. IEEE Transactions on Dependable and Secure Computing，2005，2(1).