一种基于RS纠错码的关系型数据库水印算法*

刘 可，刘 杰，刘尚麟

(1.中国人民解放军92723部队，北京 100000；2.中国电子科技集团公司第三十研究所，四川 成都 610041)

一种基于RS纠错码的关系型数据库水印算法*

刘 可1，刘 杰2，刘尚麟2

(1.中国人民解放军92723部队，北京 100000；2.中国电子科技集团公司第三十研究所，四川 成都 610041)

数字水印在实现关系型数据库版权保护方面是一种有效的手段。鉴于此，提出一种基于RS纠错码的关系型数据库水印算法。该算法在数据库水印插入过程中，利用RS纠错码对元组信息进行处理，使得处理后的数据库数据存在校验位，从而在其中部分数据丢失后，可以通过其余的数据对原始数据进行恢复。将这里所提水印算法与当前著名的数据库水印算法进行对比实验，实验结果验证了本算法的有效性。

关系数据库；数字水印；RS纠错码；校验位

0 引 言

数据时代的到来，使数据版权保护问题越来越受重视。特别是在关系型数据库版权保护方面，非法拷贝和恶意篡改时常发生，给数据库合法所有者造成了巨大损失。近几年兴起的关系数据库水印技术可以较好地保护数据库数据版权，因而成为学界研究的热点[1]。

国内外众多学者对关系数据库水印算法开展了大量研究，并且取得了众多成果[2]。在关系型数据库中，通过修改数据元组的值来实现数字水印的方法最初是由Agrawal等人[3]提出的。他们通过修改关系型数据库数值型元组的最低有效位（LSB）实现水印的插入。最近，比较有代表性的工作主要有：王振等人[4]提出了一种基于分存分组的关系数据库数字水印算法；Saman等人[5]提出了一种健壮的可逆关系数据库水印方法；Shyamala等人[6]提出了基于可信计算方法的数值型数据库水印方法；Kanimozhi等人[7]提出了一种基于数值扭曲最小化的数值型数据库水印方法；Jawad等人[8]提出了一种基于差分扩展和遗传算法的关系数据库可逆水印方法。以上研究成果在关系数据库版权保护方面发挥了巨大作用。但是，前述方法对关系数据库水印的插入和提取过程中出现的元组数据错误，以及在数据库遭受数据篡改攻击时对水印的保护，显得较为薄弱。

本文提出一种基于RS纠错码的关系型数据库水印算法。该算法聚焦于关系型数据库中数值型水印，主要思路是对数据库中的数值型属性数据作微小修改，在一定误差范围内不改变数据的统计特性。算法的创新之处在于，根据数据库的特点和相应的插入方式对其进行改进，形成了具有纠错能力的关系型数据库数字水印算法，从而加强了数据库水印的健壮性。利用RS纠错码对数据信息进行处理，使得处理后的数据存在校验位。当其中部分数据丢失后，便可以通过其余的数据对原始数据进行恢复，从而可以较好地防止数据库由于信息的部分删除而造成水印的提取不成功。

本文结构如下：首先介绍关系型数据库水印技术的研究现状，其次介绍提出的基于RS纠错码的关系型数据库水印算法的细节，再次给出算法的实验分析，最后总结全文，并为今后的工作提供有价值的建议。

1 数据库水印算法

在进行水印信息插入前，要对每一个元组进行编号，并按照编号顺序依次插入水印。每一个编号的取值由元组所在行的主码、某个密钥值K和元组取值决定。利用单向哈希函数计算出每一个编号值。对于元组值r.Ai，属性名为Ai，所在元组的主码为其编号为

为了保证关系型数据库的数据统计特性不被破坏，在水印插入时需要对元组数值的更改范围进行限制。在水印插入过程中，只对约束范围内的元组进行水印插入操作。设b%为所有属性值可允许的变化范围，则根据b的取值可以计算出每个元组数值最低有效位的可变范围。

对于关系型数据库R中的每一个属性值r.Ai，水印插入算法的具体步骤描述如下：

步骤一：计算每一个元组r.Ai在约束b%下最低有效位可更改的范围ε；

步骤二：若每一个元组r.Ai的ε≠0，则计算否则返回步骤一，计算下一个元组值；

步骤四：返回步骤一，计算下一个元组值，直到计算完关系型数据库R中的所有数值型元组。

2 基于RS纠错码的水印算法

2.1 RS纠错码

本文运用到的RS（Reed-Solomon）纠错码在伽罗华域（Galois Field，GF）中运算。RS的编码是计算信息码符多项式除以校验码生成多项式之后的余数。例如，（26，22）RS码表示长度共26个符号，其中信息代码的长度为22，校验码有4个校验符号。在这由26个符号组成的码块中，可以修正这个码块中出现的2个分散的或者2个连续的符号错误，但不能修正3个或者3个以上的符号错误。对于一个信息码多项式RS校验码生成多项式的一般形式如下：

式中，通常取k0=0或者k0=1，而(n-k)≥2t（t为要修正的错误符号数）。RS码的错误修正过程包含三个部分：①计算校正子；②计算错误位置；③计算错误值。

2.2 数据库行主码计算

一般，数据表中每一列均有相应的主码，而行方向则没有主码。在本算法中，需要为每一行设置相应的主码，且该主码具有如下特点：

（1）在原始数据表中不存在，需根据该行的数据内容计算获得；

（2）不包含允许打入水印的部分，以避免主码不能正确恢复；

（3）不包含会因为在表中插入数据而发生改变的数据内容，如代表行数的ID列。

这里主要讨论每一行的主码r.P.如何生成。此处不可采用普通的自增列等较为容易改变的标识作为每一行的主码，必须采用与此行内容相关的一些信息作为本行的主码，以便降低因为人为因素破坏数据库，而导致水印无法被正常检测。

步骤一：以每一行为一个单位，置字符串str为空，从第一个数据开始；

步骤二：判断该数据是否为数值型，如果是，计算r.Bi在约束b%下最低有效位可更改的范围ε，去除可更改范围后，记其值为tmp，如果不是，则其中||表示链接；

根据上述主码生成算法，便可获得每一行的主码，以用于后续水印算法中。

2.3 水印的生成及插入

利用RS纠错码对数据信息进行处理，使得处理后的数据库数据存在校验位，当其中部分数据丢失后，便可以通过其余的数据对原始数据进行恢复，从而进一步增强数字水印的健壮性。

水印插入算法过程如下：

步骤一：将需要插入的信息按照字节进行编码，如编码成一个长度为k的字节数组

步骤三：根据数据长度n和信息长度k，生成相应的编码矩阵G；

步骤五：设置一个密钥值K；

步骤六：对进行处理的数据库表行和数值型属性列进行编号。行编号是进行两次哈希迭代的结果。每个数值型属性列编号其中r.P通过主码生成算法计算获得；

步骤七：将所有行MAC按照升序排序；

步骤九：从第一个MAC分区的第一行开始，每行中，确定r.Ai在约束b %下最低有效位可更改的范围ε≠0的元组数据，依照升序逐分区逐行插入数字水印比特列。

水印插入示意如图1所示。在上述数字水印插入算法中，按照MAC排序和分区对整个数据库进行乱序，因此每一个比特均会在数据库中嵌入多次。同时，利用RS纠错码，可以在部分字符丢失或者出错的情况下对其进行纠错。

图1 水印插入示意

2.4 水印的提取

数字水印提取算法是将嵌入数据库的水印提取出来，以便进行版权认证。

水印提取算法过程如下：

步骤一：读取密钥值K；

步骤三：对MAC进行升序排序和分区，分区方法采用位置标记

步骤四：按照插入顺序，从第一个分区插入水印的r.Ai属性列的最低比特位提取水印比特；

步骤五：对记录的数据按位进行分类，列成表格。假设每一行只插入一个比特的数据，共m行，插入字符串的比特位数num，则建立的表格为

步骤七：对纠错后的字符串进行解码，获得相应的水印信息。

3 实验结果和分析

为了验证本文所提出的关系型数据库水印算法的有效性，以某医院电子病历数据库进行实验。实验环境为3.2 GHz CPU，8 GB内存，Windows 8操作系统。水印数据的插入实验程序与水印数据的检测程序使用软件Matlab 7.0完成，并利用JDBC连接SQL Server2008。该电子病历数据库共有8个数值型属性，共包含100 000个元组。在实验中选取参数b%=0.1%，嵌入字符串“CETC30”（按照ASCII码的编码规则，将字符串转换为二进制比特串）。

将本文所提算法（RS）与文献[6]提出的SRW算法和文献[7]提出的DMW算法进行对比实验。通过模拟子集选取攻击和子集更改攻击，对本文提出的水印算法进行测试，从而对本文所提水印算法的不可见性和健壮性进行验证。

本文所提算法水印信息嵌入前后关系型数据库统计信息变化如表1所示。

表1 水印信息嵌入前后均值方差的变化

从表1的均值和方差数据变化中可以看出，利用本文提出的基于RS纠错码的关系型数据库水印算法将水印插入后，对原数据的统计特性影响不大，即该水印算法具有良好的不可见性。

通过子集选取攻击、子集增加攻击和子集更改攻击对本文所提算法进行攻击性测试，以验证该算法的健壮性。

进行子集抽取攻击的实验结果如表2所示。从表2中可以看出，抽取的数据比例越高，检测出的水印信息与原水印信息相似度就越高。当抽取数据的比例为100%时，相似度为1。

进行子集更改攻击的实验结果如表3所示。从表3中可以看出，对子集修改得越多，相应提取出的水印信息相似度就越低。当没有任何修改时，相似度为1。

表2 子集抽取攻击后相似度变化

表3 子集更改攻击后相似度变化

综合表2和表3可以看出，本文所提水印算法（RS）均优于SRW和DMW算法，且在子集更改攻击实验中具有明显优势。究其原因，在于本文所提算法中的纠错机制发挥了良好作用。

4 结 语

本文在当前流行的关系型数据库版权保护方法的基础上，提出了一种基于RS纠错码的关系型数据库水印算法。该算法在水印插入过程中，利用RS纠错码对元组信息进行处理，使得部分数据丢失的情况下，仍然可以通过其余的数据对原始数据进行恢复。同时，通过对比实验验证了本文所提算法的有效性。未来，可以从水印作用的数据类型方面开展进一步研究。

[1] Rucha D.K,Dipak V.P.Watermarking of Relational Databases:Survey[J].International Research Journal of Engineering and Technology(IRJET),2015, 2(09):785-791.

[2] 孔德丽,崔新春,耿海亭等.基于身份认证的买方-卖方数字水印协议[J].通信技术,2015,48(08):968-973. KONG De-li,CUI Xin-chun,GENG Hai-ting,et al.A Buyer-Seller Digital Watermarking Protocol Based on Identity Authentication[J].Communications Technology,2015,48(08):968-973.

[3] Rakesh A.Jerry K.Watermarking Relational Databases[C].Proc of the 28th VLDB Conference,Hongko ng,China:IEEE,2002:155-166.

[4] 王振,李建民,周南润等.基于分存分组的关系数据库数字水印算法[J].通信技术,2009,42(04):132-138. WANG Zhen,LI Jian-min,ZHOU Nan-run,et al.Digital Watermarking Algorithm for Relational Database Based on Sharing and Grouping[J].Communications Technology,2009,42(04):132-138.

[5] Saman I,Kamran M,Zahid A.RRW-A Robust and Reversible Watermarking Technique for Relational Data[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(04):1-9.

[6] Shyamala G,Jasmine I,Selvakumari J,et al .Secure and Reliable Watermarking in Relational Databases[J]. International Journal of Computer Trends and Technology,2014,27(04):23-29.

[7] Shymala G,Kanimozhi C,KAVYA SP.An Efficient Distortion Minimizing Technique for Watermarking Relational Databases[J].International Journal of Scientific and Technology Research,2015,4(11):34-42.

[8] Jawad K,Khan A.Genetic Algorithm and Difference Expansion based Reversible Watermarking for Relational Databases[J].Journal of System and Software,2013,86(11):2742-2753.

A RS Error Correcting Coding based Watermarking Algorithm for Relational
Database

LIU Ke1,LIU Jie2,LIU Shang-lin2
(1.Unit 92723 of PLA, Beijing 100000, China; 2.No.30 Institute of CETC, Chengdu Sichuan 610041, China）

Digital watermarking is an effective way for the copyright protection of relational database systems. This paper proposes a RS error correcting coding based watermarking algorithm for relational database. The proposed algorithm utilizes the RS error correcting coding to process the tuple data in the watermarking insertion procedure. Once part of the data is missing, it could recovery the original data according to the rest of data. It compares the proposed watermarking algorithm with the recent famous ones, and the experimental results demonstrate the effectiveness of the proposed watermarking algorithm.

Relational database;Digital watermarking;RS error correcting coding;Check bit

TP393；TN915

：A

：1002-0802(2016)-06-0764-05

10.3969/j.issn.1002-0802.2016.06.021

刘 可（1974—），男，硕士，工程师，主要研究方向为信息安全；

刘 杰（1984—），男，博士，工程师，主要研究方向为机器学习、信息安全；

刘尚麟（1969—），男，硕士，高级工程师，主要研究方向为信息安全。

2016-02-08;

：2016-05-09 Received date:2016-02-08;Revised date:2016-05-09

国家自然科学基金（No.61309034）

Foundation Item: National Natural Science Foundation of China (No.61309034)