一種基于RS糾錯碼的關系型數據庫水印算法*

劉 可，劉 杰，劉尚麟

(1.中國人民解放軍92723部隊，北京 100000；2.中國電子科技集團公司第三十研究所，四川 成都 610041)

一種基于RS糾錯碼的關系型數據庫水印算法*

劉 可1，劉 杰2，劉尚麟2

(1.中國人民解放軍92723部隊，北京 100000；2.中國電子科技集團公司第三十研究所，四川 成都 610041)

數字水印在實現關系型數據庫版權保護方面是一種有效的手段。鑒于此，提出一種基于RS糾錯碼的關系型數據庫水印算法。該算法在數據庫水印插入過程中，利用RS糾錯碼對元組信息進行處理，使得處理后的數據庫數據存在校驗位，從而在其中部分數據丟失后，可以通過其余的數據對原始數據進行恢復。將這里所提水印算法與當前著名的數據庫水印算法進行對比實驗，實驗結果驗證了本算法的有效性。

關系數據庫；數字水印；RS糾錯碼；校驗位

0 引 言

數據時代的到來，使數據版權保護問題越來越受重視。特別是在關系型數據庫版權保護方面，非法拷貝和惡意篡改時常發(fā)生，給數據庫合法所有者造成了巨大損失。近幾年興起的關系數據庫水印技術可以較好地保護數據庫數據版權，因而成為學界研究的熱點[1]。

國內外眾多學者對關系數據庫水印算法開展了大量研究，并且取得了眾多成果[2]。在關系型數據庫中，通過修改數據元組的值來實現數字水印的方法最初是由Agrawal等人[3]提出的。他們通過修改關系型數據庫數值型元組的最低有效位（LSB）實現水印的插入。最近，比較有代表性的工作主要有：王振等人[4]提出了一種基于分存分組的關系數據庫數字水印算法；Saman等人[5]提出了一種健壯的可逆關系數據庫水印方法；Shyamala等人[6]提出了基于可信計算方法的數值型數據庫水印方法；Kanimozhi等人[7]提出了一種基于數值扭曲最小化的數值型數據庫水印方法；Jawad等人[8]提出了一種基于差分擴展和遺傳算法的關系數據庫可逆水印方法。以上研究成果在關系數據庫版權保護方面發(fā)揮了巨大作用。但是，前述方法對關系數據庫水印的插入和提取過程中出現的元組數據錯誤，以及在數據庫遭受數據篡改攻擊時對水印的保護，顯得較為薄弱。

本文提出一種基于RS糾錯碼的關系型數據庫水印算法。該算法聚焦于關系型數據庫中數值型水印，主要思路是對數據庫中的數值型屬性數據作微小修改，在一定誤差范圍內不改變數據的統(tǒng)計特性。算法的創(chuàng)新之處在于，根據數據庫的特點和相應的插入方式對其進行改進，形成了具有糾錯能力的關系型數據庫數字水印算法，從而加強了數據庫水印的健壯性。利用RS糾錯碼對數據信息進行處理，使得處理后的數據存在校驗位。當其中部分數據丟失后，便可以通過其余的數據對原始數據進行恢復，從而可以較好地防止數據庫由于信息的部分刪除而造成水印的提取不成功。

本文結構如下：首先介紹關系型數據庫水印技術的研究現狀，其次介紹提出的基于RS糾錯碼的關系型數據庫水印算法的細節(jié)，再次給出算法的實驗分析，最后總結全文，并為今后的工作提供有價值的建議。

1 數據庫水印算法

在進行水印信息插入前，要對每一個元組進行編號，并按照編號順序依次插入水印。每一個編號的取值由元組所在行的主碼、某個密鑰值K和元組取值決定。利用單向哈希函數計算出每一個編號值。對于元組值r.Ai，屬性名為Ai，所在元組的主碼為其編號為

為了保證關系型數據庫的數據統(tǒng)計特性不被破壞，在水印插入時需要對元組數值的更改范圍進行限制。在水印插入過程中，只對約束范圍內的元組進行水印插入操作。設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個連續(xù)的符號錯誤，但不能修正3個或者3個以上的符號錯誤。對于一個信息碼多項式RS校驗碼生成多項式的一般形式如下：

式中，通常取k0=0或者k0=1，而(n-k)≥2t（t為要修正的錯誤符號數）。RS碼的錯誤修正過程包含三個部分：①計算校正子；②計算錯誤位置；③計算錯誤值。

2.2 數據庫行主碼計算

一般，數據表中每一列均有相應的主碼，而行方向則沒有主碼。在本算法中，需要為每一行設置相應的主碼，且該主碼具有如下特點：

（1）在原始數據表中不存在，需根據該行的數據內容計算獲得；

（2）不包含允許打入水印的部分，以避免主碼不能正確恢復；

（3）不包含會因為在表中插入數據而發(fā)生改變的數據內容，如代表行數的ID列。

這里主要討論每一行的主碼r.P.如何生成。此處不可采用普通的自增列等較為容易改變的標識作為每一行的主碼，必須采用與此行內容相關的一些信息作為本行的主碼，以便降低因為人為因素破壞數據庫，而導致水印無法被正常檢測。

步驟一：以每一行為一個單位，置字符串str為空，從第一個數據開始；

步驟二：判斷該數據是否為數值型，如果是，計算r.Bi在約束b%下最低有效位可更改的范圍ε，去除可更改范圍后，記其值為tmp，如果不是，則其中||表示鏈接；

根據上述主碼生成算法，便可獲得每一行的主碼，以用于后續(xù)水印算法中。

2.3 水印的生成及插入

利用RS糾錯碼對數據信息進行處理，使得處理后的數據庫數據存在校驗位，當其中部分數據丟失后，便可以通過其余的數據對原始數據進行恢復，從而進一步增強數字水印的健壯性。

水印插入算法過程如下：

步驟一：將需要插入的信息按照字節(jié)進行編碼，如編碼成一個長度為k的字節(jié)數組

步驟三：根據數據長度n和信息長度k，生成相應的編碼矩陣G；

步驟五：設置一個密鑰值K；

步驟六：對進行處理的數據庫表行和數值型屬性列進行編號。行編號是進行兩次哈希迭代的結果。每個數值型屬性列編號其中r.P通過主碼生成算法計算獲得；

步驟七：將所有行MAC按照升序排序；

步驟九：從第一個MAC分區(qū)的第一行開始，每行中，確定r.Ai在約束b %下最低有效位可更改的范圍ε≠0的元組數據，依照升序逐分區(qū)逐行插入數字水印比特列。

水印插入示意如圖1所示。在上述數字水印插入算法中，按照MAC排序和分區(qū)對整個數據庫進行亂序，因此每一個比特均會在數據庫中嵌入多次。同時，利用RS糾錯碼，可以在部分字符丟失或者出錯的情況下對其進行糾錯。

圖1 水印插入示意

2.4 水印的提取

數字水印提取算法是將嵌入數據庫的水印提取出來，以便進行版權認證。

水印提取算法過程如下：

步驟一：讀取密鑰值K；

步驟三：對MAC進行升序排序和分區(qū)，分區(qū)方法采用位置標記

步驟四：按照插入順序，從第一個分區(qū)插入水印的r.Ai屬性列的最低比特位提取水印比特；

步驟五：對記錄的數據按位進行分類，列成表格。假設每一行只插入一個比特的數據，共m行，插入字符串的比特位數num，則建立的表格為

步驟七：對糾錯后的字符串進行解碼，獲得相應的水印信息。

3 實驗結果和分析

為了驗證本文所提出的關系型數據庫水印算法的有效性，以某醫(yī)院電子病歷數據庫進行實驗。實驗環(huán)境為3.2 GHz CPU，8 GB內存，Windows 8操作系統(tǒng)。水印數據的插入實驗程序與水印數據的檢測程序使用軟件Matlab 7.0完成，并利用JDBC連接SQL Server2008。該電子病歷數據庫共有8個數值型屬性，共包含100 000個元組。在實驗中選取參數b%=0.1%，嵌入字符串“CETC30”（按照ASCII碼的編碼規(guī)則，將字符串轉換為二進制比特串）。

將本文所提算法（RS）與文獻[6]提出的SRW算法和文獻[7]提出的DMW算法進行對比實驗。通過模擬子集選取攻擊和子集更改攻擊，對本文提出的水印算法進行測試，從而對本文所提水印算法的不可見性和健壯性進行驗證。

本文所提算法水印信息嵌入前后關系型數據庫統(tǒng)計信息變化如表1所示。

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

從表1的均值和方差數據變化中可以看出，利用本文提出的基于RS糾錯碼的關系型數據庫水印算法將水印插入后，對原數據的統(tǒng)計特性影響不大，即該水印算法具有良好的不可見性。

通過子集選取攻擊、子集增加攻擊和子集更改攻擊對本文所提算法進行攻擊性測試，以驗證該算法的健壯性。

進行子集抽取攻擊的實驗結果如表2所示。從表2中可以看出，抽取的數據比例越高，檢測出的水印信息與原水印信息相似度就越高。當抽取數據的比例為100%時，相似度為1。

進行子集更改攻擊的實驗結果如表3所示。從表3中可以看出，對子集修改得越多，相應提取出的水印信息相似度就越低。當沒有任何修改時，相似度為1。

表2 子集抽取攻擊后相似度變化

表3 子集更改攻擊后相似度變化

綜合表2和表3可以看出，本文所提水印算法（RS）均優(yōu)于SRW和DMW算法，且在子集更改攻擊實驗中具有明顯優(yōu)勢。究其原因，在于本文所提算法中的糾錯機制發(fā)揮了良好作用。

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] 孔德麗,崔新春,耿海亭等.基于身份認證的買方-賣方數字水印協(xié)議[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)