有選擇嵌入水印的關(guān)系數(shù)據(jù)庫管理系統(tǒng)實(shí)現(xiàn)

摘要：提出了一個可以在關(guān)系數(shù)據(jù)庫系統(tǒng)中基于不同用戶有選擇地為關(guān)系數(shù)據(jù)嵌入水印的方案，并且基于PostgreSQL實(shí)現(xiàn)其原型系統(tǒng)，命名為USWRDBMS。它在查詢數(shù)據(jù)時根據(jù)用戶的不同有選擇地為關(guān)系數(shù)據(jù)添加水印信息，可以分別為內(nèi)部用戶和外部用戶提供原始數(shù)據(jù)和嵌入水印的數(shù)據(jù)。該系統(tǒng)通過執(zhí)行特定的SQL語句來實(shí)現(xiàn)對水印參數(shù)的添加、修改和刪除，從而實(shí)現(xiàn)對關(guān)系數(shù)據(jù)版權(quán)的保護(hù)。

關(guān)鍵詞：數(shù)字水印; 選擇性； PostgreSQL

中圖分類號：TP311.132.3文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)01－0181－03

數(shù)字水印技術(shù)[1]作為實(shí)現(xiàn)版權(quán)保護(hù)的有效方法，已經(jīng)獲得了廣泛的應(yīng)用。其中關(guān)系數(shù)字水印技術(shù)作為保護(hù)關(guān)系數(shù)據(jù)版權(quán)的有效方法，近年來也已經(jīng)取得了一定的發(fā)展。

應(yīng)用關(guān)系數(shù)字水印技術(shù)，即在不影響關(guān)系數(shù)據(jù)正常使用的前提下，按照某種特定規(guī)則向關(guān)系數(shù)據(jù)中引入微小的錯誤。一旦發(fā)現(xiàn)侵權(quán)行為，就可以檢測出相應(yīng)的水印信息，以此達(dá)到保護(hù)關(guān)系數(shù)據(jù)版權(quán)的目的[2~4]。在現(xiàn)實(shí)應(yīng)用中，對所有的用戶僅提供水印數(shù)據(jù)或只提供原始數(shù)據(jù)是無法滿足需求的。對某些用戶（如內(nèi)部用戶，指可以被數(shù)據(jù)所有者信任的用戶）應(yīng)該提供原始數(shù)據(jù)；對另外一些用戶（如外部用戶，指無法被數(shù)據(jù)所有者所信任的用戶）則需要提供帶有水印的數(shù)據(jù)。因此，應(yīng)當(dāng)有選擇地針對不同的用戶添加水印以便滿足現(xiàn)實(shí)應(yīng)用的需求。

普渡大學(xué)的Radu Sion等人[3]以及IBM研究中心的Rakesh Agrawal等人[5]均通過用JDBC存取數(shù)據(jù)來為關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)批量地添加水印信息。這種方法簡單方便，但不夠靈活，無法解決上述針對不同用戶有選擇地添加水印的問題。為此，

本文提出了一個在RDBMS內(nèi)選擇性嵌入水印的方案，以PostgreSQL為基礎(chǔ)實(shí)現(xiàn)了一個原型系統(tǒng)，可以在執(zhí)行數(shù)據(jù)查詢操作時根據(jù)不同用戶有選擇性地進(jìn)行水印嵌入的操作(針對數(shù)值型數(shù)據(jù))，從而可以有效地保護(hù)關(guān)系數(shù)據(jù)的版權(quán)。更為重要的是它可以非常靈活地通過特定的SQL語言更改水印的參數(shù)，增強(qiáng)了靈活性。

1選擇性水印嵌入方案

選擇性嵌入水印方案的設(shè)計(jì)思路是通過為RDBMS擴(kuò)展水印的功能，在RDBMS內(nèi)部實(shí)現(xiàn)關(guān)系水印的嵌入，無須再借用外部工具。

該方案在傳統(tǒng)的關(guān)系數(shù)據(jù)庫管理系統(tǒng)的基礎(chǔ)上，在內(nèi)部為其增加一個水印子系統(tǒng)，通過這個子系統(tǒng)來完成關(guān)系數(shù)據(jù)的水印嵌入操作。該子系統(tǒng)可以為需要添加水印的數(shù)據(jù)嵌入水印。

擴(kuò)展水印功能后的RDBMS不在數(shù)據(jù)庫系統(tǒng)內(nèi)保存嵌入水印的數(shù)據(jù)，只保存原始數(shù)據(jù)；水印的嵌入是在RDBMS執(zhí)行數(shù)據(jù)查詢時根據(jù)用戶的不同有選擇地進(jìn)行。

擴(kuò)展水印功能后的RDBMS在讀取數(shù)據(jù)庫的數(shù)據(jù)時，會首先把數(shù)據(jù)傳遞給水印子系統(tǒng)，由該系統(tǒng)判斷對該用戶是否應(yīng)該添加水印。如果需要添加水印則進(jìn)行相應(yīng)的水印嵌入操作；如果不需要添加就不進(jìn)行水印嵌入操作。然后水印子系統(tǒng)將數(shù)據(jù)傳遞給執(zhí)行引擎進(jìn)行下一步查詢處理操作，直到查詢過程執(zhí)行完畢；執(zhí)行引擎再將最后的查詢結(jié)果返回給用戶。查詢過程如圖1示。

如圖1所示，watermark sys是選擇性水印嵌入方案中需要添加的水印子系統(tǒng)。其主要功能是根據(jù)不同用戶有選擇地添加水印。其中：data代表原始數(shù)據(jù)；data代表嵌入水印的數(shù)據(jù)。在本文后面的圖表中也采用同樣的表示。括號里的data指的是當(dāng)內(nèi)部用戶執(zhí)行查詢時的數(shù)據(jù)（原始數(shù)據(jù)）。

2選擇性水印嵌入方案實(shí)現(xiàn)

2．1選擇PostgreSQL進(jìn)行水印功能擴(kuò)展

為了驗(yàn)證選擇性水印嵌入方案的可行性，本文以PostgreSQL為基礎(chǔ)實(shí)現(xiàn)了原型系統(tǒng)，增加了水印功能。

選擇PostgreSQL的主要原因在于它具有良好的擴(kuò)展性。PostgreSQL是表驅(qū)動的關(guān)系數(shù)據(jù)庫管理系統(tǒng)。其系統(tǒng)表（數(shù)據(jù)字典）存儲了相對于標(biāo)準(zhǔn)的關(guān)系數(shù)據(jù)庫管理系統(tǒng)更多的內(nèi)容，而且可以被用戶修改[6]。因此相對于其他的開源數(shù)據(jù)庫系統(tǒng)如MySQL擴(kuò)展起來更為方便。

選擇PostgreSQL 7.3.10版本來擴(kuò)展選擇性水印嵌入功能，并將擴(kuò)展后的原型系統(tǒng)命名為USWRDBMS (user based selective watermarking RDBMS)。

2．2定義查詢水印數(shù)據(jù)的權(quán)限

在USWRDBMS的實(shí)現(xiàn)過程中，為了實(shí)現(xiàn)有選擇嵌入水印的功能，定義了新的數(shù)據(jù)查詢權(quán)限selectWithWM。這個權(quán)限的含義是在某個表上擁有該權(quán)限的用戶可以查詢得到嵌入水印后的數(shù)據(jù)，但無法訪問原始數(shù)據(jù)。

在使用USWRDBMS的數(shù)據(jù)庫系統(tǒng)中，僅為外部用戶授予相應(yīng)表上的selectWithWM權(quán)限，意味著外部用戶僅僅只能查詢到嵌入水印的數(shù)據(jù)。對于內(nèi)部用戶，則授予select權(quán)限，這個權(quán)限使內(nèi)部用戶可以獲取原始數(shù)據(jù)。

SelectWithWM訪問權(quán)限的賦予是通過表的所有者在執(zhí)行水印嵌入指令時同時賦予外部用戶的。而USWRDBMS在執(zhí)行數(shù)據(jù)查詢會根據(jù)用戶所擁有的訪問權(quán)限的不同而決定是否為數(shù)據(jù)嵌入水印。

2．3體系結(jié)構(gòu)

實(shí)現(xiàn)后的USWRDBMS共有七個子模塊，相對于PostgreSQL增加了watermark sys子模塊用于實(shí)現(xiàn)水印嵌入的操作。PostgreSQL在執(zhí)行查詢命令時，對于每個查詢操作指令，經(jīng)過分析器（parser）、重寫器（rewriter）、規(guī)劃器（planner）三個階段處理，最后生成查詢計(jì)劃交由執(zhí)行器（executor）執(zhí)行。執(zhí)行器遞歸地執(zhí)行查詢計(jì)劃，抽取所需要的行集合。PostgreSQL的執(zhí)行器實(shí)際上是一個需求拉動的流水線機(jī)制。 每次調(diào)用一個規(guī)劃節(jié)點(diǎn)時，它都必須給出更多的一行，或匯報它已經(jīng)完成行的傳遞了[6]。

執(zhí)行器在每次發(fā)生實(shí)際的讀取表操作時，都將根據(jù)水印相關(guān)的參數(shù)來調(diào)用watermark sys執(zhí)行水印的嵌入操作。圖2是select查詢命令的執(zhí)行工作流圖。 

2．4水印嵌入的實(shí)現(xiàn)描述

PostgreSQL的執(zhí)行器采用iterator結(jié)構(gòu)，每次調(diào)用一個節(jié)點(diǎn)就返回一個tuple。在每次讀取表時，會調(diào)用SeqScan掃描節(jié)點(diǎn)從磁盤上讀取一個tuple。為了添加水印，應(yīng)該在讀取原始數(shù)據(jù)時根據(jù)相關(guān)的水印參數(shù)完成相關(guān)的水印嵌入操作。因此需要修改SeqScan節(jié)點(diǎn)（ExecSeqScan函數(shù)，在src\\backend\\executor\odeSeqScan.c文件中）以完成嵌入水印工作。

重寫ExecSeqScan函數(shù)用于實(shí)現(xiàn)水印的嵌入。以下是重寫后的函數(shù)：

TupleTableSlot*ExecSeqScan(SeqScan *node)

{ 

returExecScanSeq(node， (ExecScanAccessMtd)SeqNext);

}

ExecSeqScan通過調(diào)用ExecScanSeq來完成操作：

TupleTableSlot*ExecScanSeq(Scan *node， ExecScanAccessMtd accessMtd){

for( ;; )

{

從磁盤中取出一個tuple；

if(tuple為空)return NULL；

if(node >css_currentRelation >rd_rel >relwmratio !=0 該用戶沒有權(quán)限獲取原始數(shù)據(jù))

{

查詢該tuple所在的表的水印參數(shù)；

嵌入水印，得到tuple*；

if( tuple* 滿足查詢條件)

return tuple*；

else continue；

}

else if(tuple 滿足查詢條件) 

return tuple;

else continue；

}}

圖2查詢命令的執(zhí)行工作流

2．5算法描述

版權(quán)人需要確定的參數(shù)分別是：

a)版權(quán)人密鑰κ。在水印嵌入算法公開的情況下，通過版權(quán)人提供密鑰來提高嵌入水印的安全性以及抗攻擊的能力是必要的。

b)用于嵌入的屬性列名。該參數(shù)用于接收版權(quán)人給定的所需嵌入水印屬性列名；用戶可以給定1~3個屬性作為水印嵌入列；系統(tǒng)可以允許對三個屬性列同時進(jìn)行水印嵌入操作。

c)嵌入比例（ratio）。用于確定關(guān)系數(shù)據(jù)庫中用來嵌入水印元組的多少。一方面可以降低對關(guān)系數(shù)據(jù)修改的程度，增加其可用性；另外也進(jìn)一步提高了水印信息在關(guān)系數(shù)據(jù)中的隱匿性。

算法描述中用到的符號如表1所示。具體算法如下：

foreach tuple τ∈R do //R為當(dāng)前關(guān)系數(shù)據(jù)庫

foreach appointed attribute i do/*i 是由用戶指定要嵌入水印的屬性*/

if(MD5 (κ ο MD5(MSB ο κ)) mod γ==0) then 

int j=M mod 2

if(MD5 (κ ο MSB) is even)then

set LSB[j] of i to 0

else

set LSB[j] of i to 1

end

2．6水印參數(shù)的存儲

數(shù)據(jù)庫系統(tǒng)內(nèi)的每張表均有自己獨(dú)立的水印參數(shù)，所以需要準(zhǔn)確存儲每張表的水印參數(shù)。在PostgreSQL中，pg_class系統(tǒng)表描述了每張表的基本屬性，數(shù)據(jù)庫中的每一張表均在pg_class系統(tǒng)中擁有惟一的一條記錄。因此，擴(kuò)展pg_class系統(tǒng)表的字段且用于存儲嵌入水印的參數(shù)是非常合適而且容易的，并且易于查詢和修改。

USWRDBMS在pg_class系統(tǒng)表添加五個新的字段用于存儲水印參數(shù)，具體如表2所示。

表2為pg_class系統(tǒng)表新添加的字段

屬性名數(shù)據(jù)類型含義舉例

relwmkeysNameData密鑰keys

relwmattr1NameData應(yīng)嵌入水印的屬性salary

relwmattr2NameData應(yīng)嵌入水印的屬性stature

relwmattr3NameData應(yīng)嵌入水印的屬性weight

relwmratioint4嵌入比例的倒數(shù)，0表示無水印2

舉例來說，假設(shè)數(shù)據(jù)庫系統(tǒng)內(nèi)存在表person_info，并且需要為其中的salary、stature、weight三個屬性添加水印，密鑰設(shè)置為keys，嵌入比例為50%，則pg_class系統(tǒng)表內(nèi)相關(guān)字段的存儲信息應(yīng)為表2中第一列所示。

2．7定義添加和刪除水印的DDL操作命令

USWRDBMS專門定義了兩條DDL語句用于水印的操作，功能分別是為表添加水印和刪除表上已經(jīng)存在的水印。

1）添加水印的SQL語句 

描述：將水印參數(shù)存入與該表相關(guān)的pg_class系統(tǒng)表記錄中，并且授予相應(yīng)的用戶水印訪問權(quán)限。

格式：

Add Watermark into table_name Values (WMKeys wm_keys WMAtt attr1 [， attr2[， attr3 ]] WMRatio wm_ratio) to user_list

參數(shù)：table_name為需要嵌入水印的表名；

wm_keys為密鑰；

attr1、attr2、attr3為要嵌入水印的屬性名；

wm_ratio為嵌入比例；

user_list表示對這些用戶只提供水印數(shù)據(jù)。

權(quán)限：只有表的所有者才可以執(zhí)行該語句。

2）刪除水印的SQL語句

描述：清除該表對應(yīng)的pg_class系統(tǒng)表記錄的相關(guān)水印參數(shù)，并將嵌入比例置0，同時將所有的水印訪問權(quán)限收回。

格式：Drop Watermark from table_name

參數(shù)：table_name是需要刪除掉水印的表名。

權(quán)限：只有表的所有者才可以執(zhí)行該語句。

3實(shí)驗(yàn)結(jié)果

本文選取了一組醫(yī)療數(shù)據(jù)作為測試數(shù)據(jù)集。該數(shù)據(jù)集是由千葉大學(xué)收集，記錄了膠原病病人的每次就診檢查記錄，共有57 543條詳細(xì)的記錄[7]。

由于該數(shù)據(jù)集有許多屬性，同時為了簡化驗(yàn)證過程，去除了一些屬性，只保留了七個屬性，分別是ID（病歷號）、date（時間）、GOT(谷 草轉(zhuǎn)氨酶)、GPT(谷 丙轉(zhuǎn)氨酶)、LDH(乳酸晚氫酶)、ALP(堿性磷酸酶)和TP(總蛋白)。

在使用USWRDBMS建立的數(shù)據(jù)庫系統(tǒng)內(nèi)建立表diseases，它具有以上所述的七個屬性；然后將數(shù)據(jù)集中的數(shù)據(jù)導(dǎo)入，表的所有者為postgres(內(nèi)部用戶)，并創(chuàng)建假想的外部用戶terry；接著由所有者postgres執(zhí)行水印嵌入的DDL命令：Add Watermark into diseases Values (WMKeys ′mykeys′ WMAtt LDH WMRatio 1) to terry，即為表diseases中的LDH屬性添加水印，密鑰為mykeys，嵌入比例為100%，同時授予用戶terry對嵌入水印數(shù)據(jù)的查詢權(quán)限；最后分別使用postgres(表所有者)和terry（外部用戶）登錄數(shù)據(jù)庫系統(tǒng)并查詢表diseases，得到原始數(shù)據(jù)和嵌入水印后的數(shù)據(jù)。

部分查詢結(jié)果如表3所示。從中可以看出postgres、terry分別得到了不同的查詢結(jié)果(嵌入水印的數(shù)據(jù)已經(jīng)用斜體標(biāo)出)。Terry得到的數(shù)據(jù)與postgres得到的原始數(shù)據(jù)相比，由于嵌入水印而有細(xì)微的不同，表明該原型系統(tǒng)可以成功地對外部用戶獲取的數(shù)據(jù)有效地添加水印。由算法可知，為了標(biāo)記水印而修改了屬性的最后兩位有效位，并且針對每個屬性值最多只修改一位的值。因此，引入的誤差范圍是[-2，2]。在一些對數(shù)據(jù)精確度要求并不是很高的應(yīng)用，如定性的數(shù)據(jù)挖掘應(yīng)用中，水印引入的誤差并不會影響數(shù)據(jù)的可用性；而且通過減少嵌入比例可以進(jìn)一步減小誤差。

由以上的實(shí)驗(yàn)和分析可知，該原型系統(tǒng)可以有效完成選擇性嵌入水印的功能，證明了選擇性水印嵌入方案的可行性。同時由于采用的算法引入的誤差并不大，在特定的應(yīng)用背景下，該原型系統(tǒng)具有良好的可用性。

4結(jié)束語

本文基于關(guān)系數(shù)據(jù)版權(quán)保護(hù)的需要，提出了一個在數(shù)據(jù)庫系統(tǒng)內(nèi)選擇性水印嵌入的方案，并且基于PostgreSQL實(shí)現(xiàn)了該方案，驗(yàn)證了其可行性。

該方案在執(zhí)行關(guān)系查詢時有選擇性地為關(guān)系數(shù)據(jù)嵌入水印。其優(yōu)點(diǎn)是不必在數(shù)據(jù)庫中同時保存原始數(shù)據(jù)和水印數(shù)據(jù)，僅需保存原始數(shù)據(jù)，節(jié)約了存儲資源；同時，可以非常容易地更改嵌入水印的參數(shù)(通過兩條DDL語句的搭配使用)，具有較大的靈活性。

本文提出并實(shí)現(xiàn)了選擇性水印嵌入方案，初步探索了如何在關(guān)系數(shù)據(jù)庫系統(tǒng)中有效應(yīng)用數(shù)字水印技術(shù)。當(dāng)然還有很多問題需要進(jìn)一步研究，如設(shè)計(jì)更為有效的關(guān)系數(shù)據(jù)水印算法等。

參考文獻(xiàn)：

[1]KATZENBEISSE S， PETITCOLAS F A P. Information hiding techniques for steganography and digital watermarking[M]. Norwood: Artech House， 2000.

[2]AGRAWAL R， KIERNAN J. Watermarking relational databases[C]//Proc of the 28th Int’l Conference on Very Large Databases. Hong Kong:[s.n.]， 2002.

[3]SION R， ATALLAH M， PRABHAKAR S. Rights protection for relational data[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2003：98 109.

[4]SION R， ATALLAH M， PRABHAKAR S. Watermarking relational databases[R]. Indiana:Center for Education and Reasearch，Purdue University， 2002: 1－24.

[5]AGRAWAL R， HAAS P J， KIERNAN J. A system for watermarking relational databases[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2003:674.

[6]The PostgreSQL Global Development Group. PostgreSQL 7.3.2 programmer’s guide[EB/OL]. [2006].http://www.postgresql.org/files/documentation/pdf/7.3/programmer－7.3.2 US.pdf.

[7]Chiba University Hospital. Collagen diseases datasets[EB/OL].(1999). http://lisp.vse.cz/pkdd99/Challenge/chall.htm.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”