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

0 引言

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

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

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

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

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

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

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

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

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

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

圖2 公司員工檔案文檔與結構圖

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

圖3 公司員工檔案值索引

圖4 公司員工檔案結構索引

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

2.1 加密模型

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

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

a）值檢索算法

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

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

算法1：

輸入：明文XQuery語句

輸出：檢索結果

Begin_of_Alorithm

{

Read（PlainQuery）；//讀入明文的XQuery語句

PlainNode=Analyse.FindNode（PlainQuery）;//分析明文的XQuery語句，并找到檢索標簽

CipherNode=Encrypt（PlainNode）;// 加密明文標簽

SearchTID=FindValue（CipherNode）;//在值索引中找到對應的TID

Ciphertext=FindNodeValue（SearchTID）;//根據(jù) TID 在結構索引中找到對應的密文

Result=Decrypt（Ciphertext）;//對密文進行解密，得到檢索結果

Output（Result）;//返回數(shù)據(jù)，輸出檢索結果

}

End_of_Algorithm

2.2 范圍檢索算法

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

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

算法2：

輸入：明文XQuery語句

輸出：檢索結果

Begin_of_Alorithm

{

Read（PlainQuery）；//讀入明文的XQuery語句

PlainNode=Analyse.FindNode（PlainQuery）；//分析明文的XQuery語句，并找到檢索標簽

CipherNode=Encrypt（PlainNode）；//對明文標簽進行加密

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

For（SearchTIDS）//分別對每個TID進行檢索

{

Ciphertext=FindNodeValue（SearchTID）；//根據(jù) TID 在結構索引中找到對應的密文

Resulti=Decrypt（Ciphertext）；//對密文進行解密，得到一個檢索結果

Output（Resulti）；// 返回數(shù)據(jù)，輸出檢索結果

}

}

End_of_Algorithm

3 結論

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

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

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

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

[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]王迪，劉國華，于醒兵.基于多重桶劃分的密文索引技術.電子技術應用: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)，施伯樂.基于商用數(shù)據(jù)庫管理系統(tǒng)的字符串數(shù)據(jù)的加密存儲與查詢[J].小型微型計算機系統(tǒng):2005，11:11.