游軍，盧選民，周亞建，劉念

0 引言

隨著信息技術(shù)的快速發(fā)展，外包數(shù)據(jù)庫(kù)[1][2]（DAS:databaseas a service）模式越來(lái)越受到人們的青睞。DAS為用戶提供海量的數(shù)據(jù)信息儲(chǔ)存空間和高效查詢機(jī)制，減少了維護(hù)數(shù)據(jù)信息而帶來(lái)的大量的額外開(kāi)銷。數(shù)據(jù)庫(kù)存儲(chǔ)的內(nèi)容往往涉及到用戶的隱秘信息，而對(duì)數(shù)據(jù)庫(kù)安全構(gòu)成威脅的不僅僅是來(lái)自于外部的攻擊者，第三方的服務(wù)提供商可能是最危險(xiǎn)的潛在攻擊者。因此，DAS的安全性受到嚴(yán)峻挑戰(zhàn)。

XML[3]（Extensible Markup Language）即可擴(kuò)展標(biāo)記語(yǔ)言已經(jīng)成為Internet上數(shù)據(jù)表示和數(shù)據(jù)交換的標(biāo)準(zhǔn)，由于XML數(shù)據(jù)模型與傳統(tǒng)的關(guān)系模型存在著較大區(qū)別，在進(jìn)行數(shù)據(jù)庫(kù)存儲(chǔ)時(shí)，往往需要進(jìn)行拆散處理或采用大型對(duì)象存儲(chǔ)，導(dǎo)致了數(shù)據(jù)庫(kù)性能降低、管理困難、查詢的復(fù)雜性增加等問(wèn)題。

XML數(shù)據(jù)庫(kù)以DAS模式運(yùn)行時(shí)，其安全性依賴于兩個(gè)方面[4]：一是操作系統(tǒng)本身提供的安全性；二是應(yīng)用程序設(shè)置的訪問(wèn)控制機(jī)制。目前Oracle，IBM等大型數(shù)據(jù)庫(kù)管理系統(tǒng)，已經(jīng)提供了一些安全措施，例如權(quán)限機(jī)制、審計(jì)功能等，但這些措施只能滿足基本的安全要求，而對(duì)DBA（Data Base Administrator）的攻擊和數(shù)據(jù)文件的保護(hù)，仍然缺乏有效的防御措施。對(duì)一些隱秘的數(shù)據(jù)信息，以密文的方式存儲(chǔ)和傳輸，并且可以對(duì)XML數(shù)據(jù)庫(kù)中的密文信息直接進(jìn)行操作，上述的安全問(wèn)題就能迎刃而解，但如何對(duì)XML密文數(shù)據(jù)庫(kù)建立安全索引機(jī)制，實(shí)現(xiàn)快速檢索成為新的亟待解決的問(wèn)題[5][6][7]。

2005年，M.Schrefl[5]等提出一種安全索引機(jī)制，分別在客戶端和服務(wù)器端，建立索引:在客戶端建立唯一標(biāo)識(shí)符的查詢路徑索引XML Schema，在服務(wù)器端建立兩個(gè)Hash索引，一個(gè)Hash索引用于已知標(biāo)簽值讀取查詢路徑，一個(gè)Hash索引用于已知路徑讀取查詢標(biāo)簽值，并提出了利用隨機(jī)數(shù)來(lái)抵御頻率攻擊。但是這種機(jī)制不支持范圍檢索，并對(duì)客戶端與服務(wù)器端之間的通信帶寬提出比較嚴(yán)格的要求。同時(shí)，查詢效率并也不是很高。H.Wang[6]提出了在XML密文數(shù)據(jù)庫(kù)中建立結(jié)構(gòu)索引和值索引，在值索引中采用OPES技術(shù)[7]支持范圍檢索，并提出節(jié)點(diǎn)拆分和DSI的方法改變頻率分布，有效抵御基于頻率的數(shù)據(jù)庫(kù)攻擊，但OPES造成數(shù)據(jù)量增加，也間接影響了數(shù)據(jù)庫(kù)檢索性能，同時(shí)由于結(jié)構(gòu)索引是對(duì)XML進(jìn)行整體編碼，當(dāng)對(duì)XML進(jìn)行更新時(shí)，則結(jié)構(gòu)索引要重新進(jìn)行編碼，造成更新效率低下。

因此，本文提出通過(guò)對(duì)XML密文數(shù)據(jù)庫(kù)建立值索引和結(jié)構(gòu)索引，并對(duì)值索引和結(jié)構(gòu)索引中的入口地址進(jìn)行分桶管理的模型，減少了I/O次數(shù)，有效提高了密文檢索速度，不僅實(shí)現(xiàn)對(duì)精確值的快速查詢，也支持范圍查詢，同時(shí)保證數(shù)據(jù)的安全性和更新效率。

1 XML數(shù)據(jù)庫(kù)密文索引機(jī)制

在保證查詢效率和安全性的基礎(chǔ)上，考慮到XML數(shù)據(jù)庫(kù)的特性，在對(duì)XML文檔進(jìn)行加密時(shí)，不僅僅要對(duì)值進(jìn)行加密，而且也要對(duì)XML標(biāo)簽和標(biāo)簽之間的關(guān)系進(jìn)行加密。由于本文采用的索引機(jī)制將XML標(biāo)簽關(guān)系打亂，所以間接實(shí)現(xiàn)了標(biāo)簽之間關(guān)系的加密。

設(shè)XML節(jié)點(diǎn)值加密、標(biāo)簽加密的函數(shù)分別為EV{}、ET{}。在XML文檔中，分別對(duì)每一個(gè)一級(jí)標(biāo)簽分配唯一標(biāo)識(shí)符TID，記錄每個(gè)標(biāo)簽中的值入口地址Vadd，并對(duì)值的入口地址根據(jù)值的字符、數(shù)量等特性進(jìn)行分桶處理，依據(jù)上述思想，可以設(shè)計(jì)XML密文數(shù)據(jù)庫(kù)的值索引和結(jié)構(gòu)索引，如圖1所示。在圖1a中，值索引記錄了每個(gè)標(biāo)簽加密值的桶號(hào)。圖1b中記錄每個(gè)一級(jí)標(biāo)簽唯一標(biāo)識(shí)符所對(duì)應(yīng)的子標(biāo)簽的入口地址。

下面以具體的實(shí)例來(lái)說(shuō)明XML數(shù)據(jù)庫(kù)的索引機(jī)制。設(shè)一個(gè)公司員工檔案的關(guān)系中包含有一個(gè)根root標(biāo)簽employees，一個(gè)一級(jí)標(biāo)簽employee，兩個(gè)二級(jí)標(biāo)簽id、information，在information中包括3個(gè)三級(jí)標(biāo)簽name、salary、position，記錄了兩條記錄，如圖2所示。

圖1 XML密文數(shù)據(jù)庫(kù)索引機(jī)制

圖2 公司員工檔案文檔與結(jié)構(gòu)圖

圖3，圖4是對(duì)公司員工檔案建立值索引和結(jié)構(gòu)索引，入口地址取XML文檔的字符數(shù)（不包括空格），分別對(duì)name、salary、position 3個(gè)標(biāo)簽進(jìn)行加密，加密后分別為ET{name}、ET{salary}、ET{position}，對(duì)3個(gè)標(biāo)簽中的值分別進(jìn)行不同的分桶管理策略，對(duì)name和position標(biāo)簽的值，可以用字母頻率特征值提取[8]等方法進(jìn)行分桶管理，對(duì)salary標(biāo)簽的值，可以用二維分割[4]的方法進(jìn)行分桶管理，實(shí)現(xiàn)了I/O數(shù)量的最優(yōu)化。由于公司員工檔案XML文檔中，含的數(shù)據(jù)比較少，所以將其分為兩個(gè)桶，在公司員工檔案XML文檔中，分別對(duì)兩個(gè)一級(jí)標(biāo)簽Employee分配了唯一標(biāo)識(shí)符 TID=1，TID=2，并記錄一級(jí)標(biāo)簽中包含的id、information，ET（name）、ET（salary）、ET（position）的入口地址。

圖3 公司員工檔案值索引

圖4 公司員工檔案結(jié)構(gòu)索引

2 XML密文數(shù)據(jù)庫(kù)檢索模型

2.1 加密模型

XML密文數(shù)據(jù)庫(kù)檢索模型如圖5所示，用戶輸入檢索條件后，首先對(duì)Xquery語(yǔ)句進(jìn)行分析，將XML檢索分解為對(duì)各個(gè)標(biāo)簽的子檢索，對(duì)需要發(fā)送給服務(wù)器端對(duì)應(yīng)的標(biāo)簽的桶信號(hào)進(jìn)行加密，服務(wù)器端將對(duì)應(yīng)的桶返回給客戶端，客戶端對(duì)桶中的加密信息進(jìn)行解密，并根據(jù)檢索條件進(jìn)行精確檢索，當(dāng)返回的桶中沒(méi)有要檢索的結(jié)果，再次向服務(wù)器發(fā)送加密的信號(hào)，服務(wù)器端再次返回桶，客戶端再次對(duì)桶中的加密信息進(jìn)行解密，直到得到最后的檢索結(jié)果。

圖5 XML密文數(shù)據(jù)庫(kù)檢索模型

a）值檢索算法

以公司員工檔案XML數(shù)據(jù)庫(kù)為例進(jìn)行XQuery值檢索，用戶輸入的XQuery查詢語(yǔ)句如圖6所示，根據(jù)XQuery檢索條件，在值索引中找到標(biāo)簽＜name＞的值為“you”的記錄，獲取這條記錄一級(jí)標(biāo)簽的TID，然后在結(jié)構(gòu)索引中，根據(jù)TID的值找到對(duì)應(yīng)標(biāo)簽salary的值，最后返回檢索結(jié)果，檢索過(guò)程的描述如算法1所示。

圖6 XQuery對(duì)XML數(shù)據(jù)庫(kù)精確檢索

算法1：

輸入：明文XQuery語(yǔ)句

輸出：檢索結(jié)果

Begin_of_Alorithm

{

Read（PlainQuery）；//讀入明文的XQuery語(yǔ)句

PlainNode=Analyse.FindNode（PlainQuery）;//分析明文的XQuery語(yǔ)句，并找到檢索標(biāo)簽

CipherNode=Encrypt（PlainNode）;// 加密明文標(biāo)簽

SearchTID=FindValue（CipherNode）;//在值索引中找到對(duì)應(yīng)的TID

Ciphertext=FindNodeValue（SearchTID）;//根據(jù) TID 在結(jié)構(gòu)索引中找到對(duì)應(yīng)的密文

Result=Decrypt（Ciphertext）;//對(duì)密文進(jìn)行解密，得到檢索結(jié)果

Output（Result）;//返回?cái)?shù)據(jù)，輸出檢索結(jié)果

}

End_of_Algorithm

2.2 范圍檢索算法

當(dāng)用戶對(duì)XML數(shù)據(jù)庫(kù)進(jìn)行范圍檢索的時(shí)，XQuery語(yǔ)句如圖7所示，根據(jù)XQuery檢索條件，在值索引中找到標(biāo)簽＜salary＞，對(duì)＜salary＞進(jìn)行范圍檢索，并獲取滿足檢索條件記錄的一級(jí)標(biāo)簽的TID，根據(jù)每個(gè)TID，分別找到對(duì)應(yīng)標(biāo)簽name的值，最后返回檢索結(jié)果。檢索算法與值檢索步驟大體相同，但返回的TID的數(shù)量比較多，根據(jù)每個(gè)TID，分別進(jìn)行檢索，檢索過(guò)程如算法2描述。

圖7 XQuery對(duì)XML數(shù)據(jù)庫(kù)范圍檢索

算法2：

輸入：明文XQuery語(yǔ)句

輸出：檢索結(jié)果

Begin_of_Alorithm

{

Read（PlainQuery）；//讀入明文的XQuery語(yǔ)句

PlainNode=Analyse.FindNode（PlainQuery）；//分析明文的XQuery語(yǔ)句，并找到檢索標(biāo)簽

CipherNode=Encrypt（PlainNode）；//對(duì)明文標(biāo)簽進(jìn)行加密

SearchTIDS=FindValue（CipherNode）；//在值索引中找到符合檢索條件的TIDS

For（SearchTIDS）//分別對(duì)每個(gè)TID進(jìn)行檢索

{

Ciphertext=FindNodeValue（SearchTID）；//根據(jù) TID 在結(jié)構(gòu)索引中找到對(duì)應(yīng)的密文

Resulti=Decrypt（Ciphertext）；//對(duì)密文進(jìn)行解密，得到一個(gè)檢索結(jié)果

Output（Resulti）；// 返回?cái)?shù)據(jù)，輸出檢索結(jié)果

}

}

End_of_Algorithm

3 結(jié)論

本文建立了一種基于XML密文數(shù)據(jù)庫(kù)的檢索模型，通過(guò)建立值索引和結(jié)構(gòu)索引，并對(duì)值索引和結(jié)構(gòu)索引中的入口地址進(jìn)行分桶管理，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的快速檢索。

當(dāng)XML數(shù)據(jù)庫(kù)中的XML文檔中含有N（N≥0）個(gè)一級(jí)標(biāo)簽，有L（L≥0）個(gè)加密標(biāo)簽，在不建立索引時(shí)，對(duì)密文解密的次數(shù)為N*L。當(dāng)采用本文提出的索引方案，對(duì)值檢索最多要對(duì)密文解密的次數(shù)為log2N+2次，對(duì)范圍查詢最多為log2N+（N+1）次。從解密的次數(shù)上，采用索引方法有明顯的優(yōu)勢(shì)，提高了檢索的效率。由于采用了對(duì)一級(jí)標(biāo)簽分配TID的方案，也使當(dāng)對(duì)XML進(jìn)行更新時(shí)，不要重新進(jìn)行編碼，只要增加TID，就能實(shí)現(xiàn)索引的更新，更新效率也得到了本質(zhì)的提高。

從安全性的角度看，若攻擊者已知某一密文數(shù)據(jù)的明文及該數(shù)據(jù)在密文索引文件中的位置，可以對(duì)數(shù)據(jù)庫(kù)進(jìn)行已知明文的攻擊，而對(duì)于DES 算法加密的數(shù)據(jù)用窮舉搜索的方法是很難見(jiàn)效的。若攻擊者已知某一類密文數(shù)據(jù)和對(duì)應(yīng)的明文及該類數(shù)據(jù)在索引文件中對(duì)應(yīng)位置，可利用已知密文數(shù)據(jù)的順序判斷出其他密文的取值范圍，一定要進(jìn)行對(duì)入口地址的密碼破譯運(yùn)算，這同樣是不可能的。

由于建立索引的策略都是獨(dú)立的，并且每個(gè)標(biāo)簽建立索引也是獨(dú)立的，信息泄露程度非常小，所以攻擊者無(wú)法從復(fù)合索引中分析出索引的信息。因此，該模型也有效保證了密文數(shù)據(jù)庫(kù)的安全性。

[1]Divyakant Agrawal，Amr EI Abbadi，F(xiàn)atih Emekci.et al.Database Management as a Service:Challenges and Opportunities.Shanghai，China: Data Engineering，2009.ICDE '09.IEEE 25th International Conference，2009:1709-1716.

[2]Hakan Hacigumus，Bala Iyer，Sharad Mehrotra.Providing Database as a Service.San Jose，CA:Data Engineering，2002.Proceedings.18th International Conference，2002:29-38.

[3]Extensible Markup Language.XML 1.0.http://www.w3.org/TR/REC-xml，October 2000.

[4]王迪，劉國(guó)華，于醒兵.基于多重桶劃分的密文索引技術(shù).電子技術(shù)應(yīng)用:2007，3:141.

[5]Schrefl M，Grun K，Dorm J.et al.Ensuring Privacyof Electronic Documents through Semantic-Based Encrypted Query Processing.Tokyo，Japan:21st International Conference on Data Engineering Workshops，2005:1191.

[6]Wang H，Lakshmanan L.Efficient Secure Query Evaluation over Encrypted XML Databases.Seoul，Korea: 32nd International Conference on Very Large Data Bases，2006:127-138.

[7]Agrawal R，Kiernan J，Srikant R.et，al.Order preserving encryption for numeric data.Paris，F(xiàn)rance:ACM SIGMOD，2004:563-576.

[8]王正飛，汪衛(wèi)，施伯樂(lè).基于商用數(shù)據(jù)庫(kù)管理系統(tǒng)的字符串?dāng)?shù)據(jù)的加密存儲(chǔ)與查詢[J].小型微型計(jì)算機(jī)系統(tǒng):2005，11:11.