XML密文数据库检索模型的研究

游军，卢选民，周亚建，刘念

0 引言

随着信息技术的快速发展，外包数据库[1][2]（DAS:databaseas a service）模式越来越受到人们的青睐。DAS为用户提供海量的数据信息储存空间和高效查询机制，减少了维护数据信息而带来的大量的额外开销。数据库存储的内容往往涉及到用户的隐秘信息，而对数据库安全构成威胁的不仅仅是来自于外部的攻击者，第三方的服务提供商可能是最危险的潜在攻击者。因此，DAS的安全性受到严峻挑战。

XML[3]（Extensible Markup Language）即可扩展标记语言已经成为Internet上数据表示和数据交换的标准，由于XML数据模型与传统的关系模型存在着较大区别，在进行数据库存储时，往往需要进行拆散处理或采用大型对象存储，导致了数据库性能降低、管理困难、查询的复杂性增加等问题。

XML数据库以DAS模式运行时，其安全性依赖于两个方面[4]：一是操作系统本身提供的安全性；二是应用程序设置的访问控制机制。目前Oracle，IBM等大型数据库管理系统，已经提供了一些安全措施，例如权限机制、审计功能等，但这些措施只能满足基本的安全要求，而对DBA（Data Base Administrator）的攻击和数据文件的保护，仍然缺乏有效的防御措施。对一些隐秘的数据信息，以密文的方式存储和传输，并且可以对XML数据库中的密文信息直接进行操作，上述的安全问题就能迎刃而解，但如何对XML密文数据库建立安全索引机制，实现快速检索成为新的亟待解决的问题[5][6][7]。

2005年，M.Schrefl[5]等提出一种安全索引机制，分别在客户端和服务器端，建立索引:在客户端建立唯一标识符的查询路径索引XML Schema，在服务器端建立两个Hash索引，一个Hash索引用于已知标签值读取查询路径，一个Hash索引用于已知路径读取查询标签值，并提出了利用随机数来抵御频率攻击。但是这种机制不支持范围检索，并对客户端与服务器端之间的通信带宽提出比较严格的要求。同时，查询效率并也不是很高。H.Wang[6]提出了在XML密文数据库中建立结构索引和值索引，在值索引中采用OPES技术[7]支持范围检索，并提出节点拆分和DSI的方法改变频率分布，有效抵御基于频率的数据库攻击，但OPES造成数据量增加，也间接影响了数据库检索性能，同时由于结构索引是对XML进行整体编码，当对XML进行更新时，则结构索引要重新进行编码，造成更新效率低下。

因此，本文提出通过对XML密文数据库建立值索引和结构索引，并对值索引和结构索引中的入口地址进行分桶管理的模型，减少了I/O次数，有效提高了密文检索速度，不仅实现对精确值的快速查询，也支持范围查询，同时保证数据的安全性和更新效率。

1 XML数据库密文索引机制

在保证查询效率和安全性的基础上，考虑到XML数据库的特性，在对XML文档进行加密时，不仅仅要对值进行加密，而且也要对XML标签和标签之间的关系进行加密。由于本文采用的索引机制将XML标签关系打乱，所以间接实现了标签之间关系的加密。

设XML节点值加密、标签加密的函数分别为EV{}、ET{}。在XML文档中，分别对每一个一级标签分配唯一标识符TID，记录每个标签中的值入口地址Vadd，并对值的入口地址根据值的字符、数量等特性进行分桶处理，依据上述思想，可以设计XML密文数据库的值索引和结构索引，如图1所示。在图1a中，值索引记录了每个标签加密值的桶号。图1b中记录每个一级标签唯一标识符所对应的子标签的入口地址。

下面以具体的实例来说明XML数据库的索引机制。设一个公司员工档案的关系中包含有一个根root标签employees，一个一级标签employee，两个二级标签id、information，在information中包括3个三级标签name、salary、position，记录了两条记录，如图2所示。

图1 XML密文数据库索引机制

图2 公司员工档案文档与结构图

图3，图4是对公司员工档案建立值索引和结构索引，入口地址取XML文档的字符数（不包括空格），分别对name、salary、position 3个标签进行加密，加密后分别为ET{name}、ET{salary}、ET{position}，对3个标签中的值分别进行不同的分桶管理策略，对name和position标签的值，可以用字母频率特征值提取[8]等方法进行分桶管理，对salary标签的值，可以用二维分割[4]的方法进行分桶管理，实现了I/O数量的最优化。由于公司员工档案XML文档中，含的数据比较少，所以将其分为两个桶，在公司员工档案XML文档中，分别对两个一级标签Employee分配了唯一标识符 TID=1，TID=2，并记录一级标签中包含的id、information，ET（name）、ET（salary）、ET（position）的入口地址。

图3 公司员工档案值索引

图4 公司员工档案结构索引

2 XML密文数据库检索模型

2.1 加密模型

XML密文数据库检索模型如图5所示，用户输入检索条件后，首先对Xquery语句进行分析，将XML检索分解为对各个标签的子检索，对需要发送给服务器端对应的标签的桶信号进行加密，服务器端将对应的桶返回给客户端，客户端对桶中的加密信息进行解密，并根据检索条件进行精确检索，当返回的桶中没有要检索的结果，再次向服务器发送加密的信号，服务器端再次返回桶，客户端再次对桶中的加密信息进行解密，直到得到最后的检索结果。

图5 XML密文数据库检索模型

a）值检索算法

以公司员工档案XML数据库为例进行XQuery值检索，用户输入的XQuery查询语句如图6所示，根据XQuery检索条件，在值索引中找到标签＜name＞的值为“you”的记录，获取这条记录一级标签的TID，然后在结构索引中，根据TID的值找到对应标签salary的值，最后返回检索结果，检索过程的描述如算法1所示。

图6 XQuery对XML数据库精确检索

算法1：

输入：明文XQuery语句

输出：检索结果

Begin_of_Alorithm

{

Read（PlainQuery）；//读入明文的XQuery语句

PlainNode=Analyse.FindNode（PlainQuery）;//分析明文的XQuery语句，并找到检索标签

CipherNode=Encrypt（PlainNode）;// 加密明文标签

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

Ciphertext=FindNodeValue（SearchTID）;//根据 TID 在结构索引中找到对应的密文

Result=Decrypt（Ciphertext）;//对密文进行解密，得到检索结果

Output（Result）;//返回数据，输出检索结果

}

End_of_Algorithm

2.2 范围检索算法

当用户对XML数据库进行范围检索的时，XQuery语句如图7所示，根据XQuery检索条件，在值索引中找到标签＜salary＞，对＜salary＞进行范围检索，并获取满足检索条件记录的一级标签的TID，根据每个TID，分别找到对应标签name的值，最后返回检索结果。检索算法与值检索步骤大体相同，但返回的TID的数量比较多，根据每个TID，分别进行检索，检索过程如算法2描述。

图7 XQuery对XML数据库范围检索

算法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）；//根据 TID 在结构索引中找到对应的密文

Resulti=Decrypt（Ciphertext）；//对密文进行解密，得到一个检索结果

Output（Resulti）；// 返回数据，输出检索结果

}

}

End_of_Algorithm

3 结论

本文建立了一种基于XML密文数据库的检索模型，通过建立值索引和结构索引，并对值索引和结构索引中的入口地址进行分桶管理，实现了对数据的快速检索。

当XML数据库中的XML文档中含有N（N≥0）个一级标签，有L（L≥0）个加密标签，在不建立索引时，对密文解密的次数为N*L。当采用本文提出的索引方案，对值检索最多要对密文解密的次数为log2N+2次，对范围查询最多为log2N+（N+1）次。从解密的次数上，采用索引方法有明显的优势，提高了检索的效率。由于采用了对一级标签分配TID的方案，也使当对XML进行更新时，不要重新进行编码，只要增加TID，就能实现索引的更新，更新效率也得到了本质的提高。

从安全性的角度看，若攻击者已知某一密文数据的明文及该数据在密文索引文件中的位置，可以对数据库进行已知明文的攻击，而对于DES 算法加密的数据用穷举搜索的方法是很难见效的。若攻击者已知某一类密文数据和对应的明文及该类数据在索引文件中对应位置，可利用已知密文数据的顺序判断出其他密文的取值范围，一定要进行对入口地址的密码破译运算，这同样是不可能的。

由于建立索引的策略都是独立的，并且每个标签建立索引也是独立的，信息泄露程度非常小，所以攻击者无法从复合索引中分析出索引的信息。因此，该模型也有效保证了密文数据库的安全性。

[1]Divyakant Agrawal，Amr EI Abbadi，Fatih 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，France:ACM SIGMOD，2004:563-576.

[8]王正飞，汪卫，施伯乐.基于商用数据库管理系统的字符串数据的加密存储与查询[J].小型微型计算机系统:2005，11:11.