基于B＋树的索引字段加密
王正飞1, 2，汪 卫3，施伯乐3
(1. 湖南商学院 计算机系，湖南 长沙，410205；
2. 国防科技大学 计算机学院 并行与分布式处理国家重点实验室， 湖南 长沙，410073；
3. 复旦大学 计算机学院，上海，200433)
摘 要：
摘 要：针对索引字段加密难的问题，提出一种基于B+树的索引字段加密处理技术。该技术采用DBMS内部加密机制，选取在页/段映射到块时使用加密组件对索引字段进行加密，它能够使加密后的索引仍然保持有序，不会失去索引的快速查询功能。为了进一步保证索引字段本身的安全性，对索引按结点实施加密。实验中，模拟Postgresql中B+树的构造方法，研究基于B+树的加密索引字段的查询性能，并在页结点数和B+树深度参数变化时，对分结点加密的查询性能进行测试。研究结果表明：基于B+树的索引字段加密的查询速度虽然比明文查询速度下降20%左右，但采用分结点加密方式能够有效地减少解密代价，避免索引字段加密对查询性能产生较大影响。
关键词：
中图分类号：TP311 文献标志码：A 文章编号：1672-7207(2009)06-1660-06
Encryption over index fields based B+ tree
WANG Zheng-fei1, 2, WANG Wei3, SHI Bo-le3
(1. Department of Computer, Hunan Business College, Changsha 410205, China;
2. National Key Laboratory for Parallel and Distributed Processing, School of Computer,
National University of Defense Technology, Changsha 410073, China;
3. School of Computer Science, Fudan University, Shanghai 200433, China)
Abstract: In order to solve the problem of encrypting the index fields, a new way, i.e., encryption over the index fields based B+ tree, was proposed. The encrypted mechanism inside DBMS was adopted, the index fields were encrypted by the encryption component during the process of mapping page or segment to block. The new method could preserve its order after the index fields was encrypted, and the function of fast querying was not lost. Furthermore, in order to ensure the security, the index itself was encrypted according to each node. In the experiments, the B+ tree was constructed by simulating the Postgresql. Querying performance over the encrypted index fields was studied, and the querying performance over each encrypted node was tested by varying the numbers of the pages and B+ tree depths. The results show that the query velocity over the encrypted index fields can be accepted although it decreases by about 20% compared with the plaintext, and encryption over each node can efficiently reduce the decryption cost so as to avoid the influence of querying on the encrypted index fields.
Key words: database security; encryption; B+ tree; index; query
随着电子商务和电子政务的快速发展，越来越多的重要信息存储在网络数据库中，因此，如何保障这些信息的安全性十分重要。传统的物理安全、操作系统安全机制和数据库访问控制机制为网络数据库提供了一定的安全措施和技术，但这些方法并不能有效满足网络数据库安全的需求，特别是无法保证一些重要部门数据和敏感数据的安全[1-3]。造成不安全的原因主要是原始数据以可读形式存放在数据库中[4-5]。若对数据库中的数据进行加密处理，则上述问题可以得到解决，即使某一用户非法入侵到系统中或者盗得数据存储介质，没有相应的解密密钥，仍然不能得到所需数据。当数据库中存储密文数据时，查询密文数据的速度急剧下降。为了平衡数据库中敏感信息的安全和查询性能，一些研究者对数据库加密进行了研究。Ahitub等[6]提出了一种同态加密方法。从安全角度看，这种加密方法本身具有其固有的缺陷，因为它要求密文数据仍然保持有序性，这与安全的加密算法是相悖的。Hacigumus等[7-8]在将数据库作为一种服务的背景下，提出了对加密数据查询的方法，给出最优分桶算法，使得查询代价最少。但是，这种方法对于多表连接查询的代价非常大。Agrawal等[9]提出了一种保持有序的加密方法，即给定1个目标分布函数，对明文进行转换得到密文，使得密文不仅保持有序，而且服从某一目标函数的分布。由于其密文保持有序，所以，无须解密就可以直接对密文进行等值和范围查询，也可以进行MAX，MIN，COUNT和ORDER BY查询。但由于密文保持有序性，采用这种方法容易遭受选择密文的攻击。也就是说，如果攻击者能够选择一定数量的明文(或密文)，并且把它们加密(或解密)成对应的密文(或明文)，那么，他就能够以较大的概率估计密文对应的明文。类似地，若攻击者知道这个域的一些信息，则他能够以较大的概率估计密文对应的明文。Bouganim等[10]认为，智能卡具有加密和查询处理能力，它把数据加密后存储在服务器中，密钥也存储在智能卡中。查询时，智能卡能够对等值查询语句进行转换，使之能够对密文数据进行查询。但是，它不能对实数类数据进行范围查询。Song等[11]使用序列加密(Stream cipher)方法对文本数据进行加密处理，这样，无须解密而直接对加密文本搜索关键词，但是，这种方法没有在数据库中得到应用。王正飞等[12-13]对数据库中字符型数据的加密以及加密数据的快速查询进行了研究。
索引字段的加密一直是数据库加密中一个难点。在关系数据库中，索引是一种用来提高查询速度的重要技术，它主要利用索引的有序性来实现数据的快速查询。但是，数据加密之后，密文数据失去了有序性，对密文数据建立索引也就失去了意义。Oracle和IBM等企业不支持对数据库中索引字段进行加密处 理[15-16]。本文作者提出一种基于B+树索引字段加密的体系结构，一方面能够对索引字段进行加密，另一方面能够保证索引的有序性，不会影响索引本身的快速查询功能。此外，考虑到索引本身的安全性，对索引也实施加密处理。
1 基于B+树索引字段加密的体系结构
在对索引字段进行加密时，关键之处是在加密之前利用B+树对加密字段建立了索引，这样，能够保证索引的有序性。为此，采用DBMS内部加密机制，其体系结构如图1所示。数据从外部流入DBMS内部时，经过DBMS内部一系列的映射转换后，最终以文件形式存储在磁盘。为了实现在加密之前建立索引，选择了在页、段以文件形式存储到磁盘时进行加密[14]。一方面，索引是在明文状态下建立，有序性得到保证；另一方面，调用加密组件对索引本身进行加密，防止索引本身信息泄露。这种加密设计方法已经在开源的Postgresql中被实现。
图1 基于B+树索引字段加密的体系结构
Fig.1 Structure of encryption over index fields based on B+ tree
对索引B+树进行加密时，加密算法不会导致存储空间增加。通常，B+树结点指针包含2部分，即数据块的地址和该键对应的记录在块内的偏移地址。数据块的地址不会发生变化。虽然数据加密后，存储空间增加，但由于1个块的填充度一般为2/3左右，且数据加密后增加的存储空间较少，不会出现块中存储的记录数减少的情形，所以，指针中的数据块地址不会变化。此外，该键对应的记录在块内的偏移地址不会发生变化。数据块中的字段值加密后，存储空间的增加只是影响磁盘块中各记录指针的偏移地址，如图2所示(其中，linpN表示指向第N条记录的指针)，并不会影响B+树中结点指针的偏移地址。
图2 数据块的内部结构
Fig.2 Inner structure of data block
2 索引B+树的建立和加密
2.1 索引B+树的建立
B+树是DBMS中最常用的索引结构，通常由键和指针对组成。在B+树中，键K通过指针指向数据文件中键值为K的记录。查询时，首先查找B+树中匹配的键，然后，根据其指针找到相应的记录。由于B+树所占存储空间远小于其对应的数据文件所占的存储空间，特别是当内存容纳不下数据文件却能容纳B+树时，利用B+树处理查询的速度迅速提高。此外，由于键按顺序进行排列，可以使用B+树快速查找键值为K的记录。例如：有n个索引块，通常只需查找log2n个块，就能查询键值为K的记录。
为了能够在图1所示的体系结构中建立索引B+树，需要在系统表中增加2个关系表，即Enc_field和Enc_keys，它们分别包含加密字段的信息以及加密密钥信息。关系Enc_field的模式为Enc_fields(fid, DB_name, Rel_name, Field_name)，其中：fid为主键；表示加密字段的编号；DB_name表示数据库名；Rel_name表示关系表名；Field_name表示字段名。关系Enc_keys的模式为Enc_keys(kid, fid, key)，其中：Kid为主键，表示密钥的编号；Fid为关系Enc_field的外键；Key表示密钥。
具体来说，索引B+树的建立过程如下：
a. SQL语句经ODBC(JDBC)传入到DBMS内部，经解释器分析后，识别SQL中关键字信息。
b. 利用系统表中Enc_field的信息，验证存储的数据中是否有需要加密的索引字段。
c. 若需要加密，则调用索引创建程序，建立B+树；然后，在写数据到磁盘时，调用加密算法对需索引字段进行加密处理。
d. 在关系表Enc_keys中增加1条记录，记录存储该字段的加密密钥信息。
例1 当数据文件的索引字段值为2，3，5，7，11，13，17，19，23，29，31，37，41，43和47时，在对这些字段值加密之前，建立1个B+树，如图3所示。
图3 B+树结构
Fig.3 Structure of B+ tree
2.2 索引B+树的加密存储
利用索引技术可以实现对加密数据的快速查询，但是，B+树中的键以明文形式存在，这无疑给系统带来潜在的危险。狡猾的攻击者总是能够从系统的最薄弱环节发动攻击，因此，对B+树也要进行加密处理。对B+树进行加密处理时，一种简单的想法是：存储时，对整个B+树进行加密；查询时，先解密B+树，然后，根据B+树定位数据文件的加密记录，对满足条件的记录进行解密。由于B+树所占存储空间远小于数据文件所占的存储空间，采用这种方法比直接解密整个数据文件迅速。
但是，在利用传统索引文件(如B+树)进行查询时，往往只需要访问少数结点数。若对索引文件采用分结点的加密方法，则在查询索引文件时只需要解密少数的结点，而无需解密整个索引文件，这样，查询速度得到较大提高。因此，根据B+树的结构特点，进行分结点加密。在后面的实验中，将比较这几种加密方法查询速度的差异。如图3所示，B+树由许多结点组 成，通常有3层：根、中间层和叶，但也可以是任意层，各层对应的结点分别为根结点、内部结点和叶结点。可以对各个结点进行加密，而由于1个结点对应1个物理存储块(block)，所以，采用分组加密(block cipher)算法。
对B+树中的结点进行分组加密(如图4所示)，发现B+树经过加密后，尽管各结点存储的是密文，但其对应明文结点中的键仍然保持有序，也就是说，分结点加密并不会改变各结点中对应明文键的有序排列。
图4 B+树中各结点的加密
Fig.4 Encryption on each node of B+ tree
3 基于B+树的加密索引字段查询
建立了B+树后，可以实现对索引进行快速查询。其原因有：
a. B+树是对分结点进行加密，只需要对很少的结点进行解密。一般地，B+树的深度不会超过3层[7]，因此，只需要解密3个结点。若把根结点保留在内存中，则只需要解密2个结点，性能会更好。
b. 利用B+树，可以准确定位到数据文件中的记录，也就是说，只需要解密满足查询条件的记录，而不需要对其他记录解密，大大减少了解密记录所花费的时间，极大地提高了系统的查询速度。
对加密数据的查询分2步进行，如图5所示。首先，对B+树进行查询，找到满足查询条件的B+树各结点；然后，通过结点的指针定位数据块中的记录。由于B+树和数据文件中的记录是以加密方式存储的，所以，还要利用系统表和解密组件进行解密处理。
图5 加密数据的查询流程
Fig.5 Process of querying over encrypted data
查询加密索引字段数的算法如下。
输入：查询sql语句；
输出：返回查询记录。
a. 查询请求经ODBC(JDBC)传入到DBMS，由解释器验证查询目标是否正确，检查SQL语法是否正确，然后，建立查询树。查询树经重写和优化后，转入查询执行器。
b. 查询B+树，找到满足条件的B+树各结点。
1) 基础：若键处于叶结点，则解密叶结点，在其键值中查找；若第i个键满足条件，则第i个指针可使人们找到所需记录。
2) 归纳：若键处于内部结点，则首先解密该子树的根结点，把查找键与根结点的键值比较，找到合适的下一个子树。重复这一过程，直到找到叶结点为止。
3) 根据B+树各结点的指针找到相匹配的记录，并对记录中的加密字段值进行解密。
4) 返回解密记录。
4 实 验
实验目的是检测索引字段加密后的查询性能。第1个实验是比较建有索引的明文、直接加密索引字段和本文提出的基于B+树的索引字段加密3种不同方法的查询性能；第2个实验是比较索引B+树在不同加密方式中的查询速度。根据TPC-H标准，利用dbgen工具自动生成数据库，比例因子取0.01，数据库容量为10 M。TPC-H的数据库包括8个表，其中，customer用作本次实验的数据源，对它们的字段comment作为索引字段进行加密处理。加密算法是safer++，由C语言编写；分组长度为128位，密钥长度为128位，实验环境为Windows NT操作系统，CPU为P4 2.8 GHz，内存为1 024 MB。
4.1 实验1：基于B+树加密索引字段的查询性能测试
在第1个实验中，比较建有索引的明文、直接加密索引字段和本文提出的基于B+树索引字段加密3种不同方法的查询时间，实验结果如图6所示。其中，SQL语句为：select * from lineitem where comment like “查询字符串”。图6所示为查询记录数不同时3种 查询方法所花费的时间，其中：X轴表示需查询记录数，Y轴表示查询时间。可以看出，采用本文提出的方法所花费的查询时间处于采用另外2种方法所花费的时间之间，且比较接近明文索引所花费的时间。而直接加密索引字段的查询时间显著增加，这主要是由于对传统索引字段加密后，索引已经失去加快查询的功能。
1—明文索引；2—本文方法；3—直接加密
图6 不同加密方式下的查询时间
Fig.6 Query time at different encrypted styles
4.2 实验2：索引B+树在不同加密方式中的查询性能
在第2个实验中，比较3种不同的索引加密方式。第1种方式是整个B+树加密，第2种方式是B+树分结点加密，第3种方式是不对B+树加密。表1所示为B+树中页结点数变化对查询速度的影响。假定B+树的深度为3，叶结点的个数由36增加到256，Enc_whole，Enc_node和None_enc分别表示上面所说的第1，2和3共3种加密方法，发现：
表1 页结点数变化对查询时间的影响
Table 1 Effect of querying time on varying page nodes
a. 对于Enc_whole，查询B+树所花费的时间随着B+树叶结点个数增加而呈线性增加。这主要是因为B+树中的叶结点个数增加，所需要解密的结点数增加，并且解密叶结点的个数大大超过内部结点解密的个数。
b. 对于Enc_node，查询B+树所花费的时间不会增加。这主要是因为对B+树查询的结点数一般为B+树的深度，需要解密的结点数也为B+树的深度，并不会随着叶结点的增加而增加。表2所示为B+树中B+树深度变化对查询速度的影响。假定叶结点数为256，B+树的深度由2增加到5，则：
表2 B+树深度变化对查询时间的影响
Table 2 Effect of querying time on varying B+ tree
1) 对于整个B+树加密的方法，查询B+树所花费的时间随着B+树叶结点个数增加而缓慢地增加。其主要原因是这种方法所花费的大部分时间在解密整个B+树，但由于B+树的叶结点为常数，B+树的全部结点数随着B+树深度增加而略有增加。
2) 对于第2种加密方法，随着树深度增加，查询时间相应增加。这主要是因为B+树深度增加，解密的结点数相应增加。
3) 对于第3种加密方法，查询时间没有显著变化。
5 结 论
a. 提出一种基于B+树的索引字段加密的体系结构，选取在页/段映射到块时使用加密组件对索引字段进行加密，它能够使加密后的索引仍然保持有序，不会失去索引的快速查询功能，从而提高加密数据的查询速度。
b. 为了更好地保证系统的安全性，对B+树实施分结点加密，使得敏感字段的信息不从B+树中泄漏。采用该方法能够有效地减少解密时间，避免索引字段加密对查询速度产生较大影响。
参考文献：
[1] Bertino E, Sandhu R. Database security concepts approaches and challenges[J]. IEEE Transactions on Dependable and Secure Computing, 2005, 2(1): 2-19.
[2] Gabriel G, Panos K, Khoshgozaran A, et al. Private queries in location based services: Anonymizers are not necessary[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. Vancouver: ACM Press, 2008: 121-132.
[3] Ateniese G, Kevin F, Matthew G, et al. Improved proxy re-encryption schemes with applications to secure distributed storage[J]. ACM Transactions on Information and System Security, 2006, 9(4): 1-30.
[4] Awadelkarim A M, Idris N B. An effective security interoperability archetype for secure multilevel databases[J]. Asian Journal of Information Technology, 2006, 5(4): 418-428.
[5] ZHU Jing-bo. Database encryption scheme for enhanced security and easy sharing[J]. Application Research of Computers, 2007, 24(3): 128-131.
[6] Ahitub N, Lapid C, Neumann S. Processing encrypted data[J]. Communications of the ACM, 1987, 30(9): 777-780.
[7] Hacigumus H, Lyer B, Mehrotra S. Providing database as a service[C]//Proceedings of the ICDE. San Jose: IEEE Press, 2002: 29-38.
[8] Hacigumus H, Lyer B, LI Chen, et al. Executing SQL over encrypted data in the database server provider model[C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison. Wisconsin: ACM Press, 2002: 216-227.
[9] Agrawal R, Kirenan J, Srikant R, et al. Order-preserving encryption for numeric data[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Paris: ACM Press, 2004: 563-574.
[10] Bouganim L, Pucheral P. Chip-secured data access: Confidential data on untrusted servers[C]//Proceedings of 28th International Conference on Very Large Databases. Hong Kong: ACM Press, 2002: 131-142.
[11] SONG Xiao-dong, Wagner D, Perring A. Practical techniques for searches on encrypted data[C]//IEEE Symposium on Security and Privacy. 2000: 44-55.
[12] 王正飞, 汪 卫, 施伯乐. 加密数据的一种高效查询方法[J]. 计算机工程与应用, 2008, 44(12): 29-33.
WANG Zheng-fei, WANG wei, SHI bo-le. An efficient method of querying the encrypted data[J]. Computer Engineering and Application, 2008, 44(12): 29-33.
[13] 李亚秀, 刘国华. 数据库中字符数据的加密方法[J]. 计算机工程, 2007, 33(6): 120-122.
LI Ya-xiu, LIU Guo-hua. Encryption method for character data in the database[J]. Computer Engineering, 2007, 33(6): 120-122.
[14] Garcia-Molina, Jeffery D, Ullman, et al. 数据库系统实现[M]. 杨冬青, 唐世渭, 徐其钧, 等译. 北京: 机械工业出版社, 2002.
Garcia-Molina, Jeffery D, Ullman, et al. Database system implementation[M]. YANG Dong-qing, TANG Shi-wei, XU Qi-jun, et al, tran. Beijing: China Machine Press, 2002.
[15] Oracle. Oracle9i Database Security for Business[R]. California: Oracle, 2001.
[16] IBM Corporation. IBM DB2 universal database Version 7.2/Version 7.1 Fix- Pak 3- release notes[R]. New York: IBM, 2001.
收稿日期：2009-05-20；修回日期：2009-07-28
基金项目：国家重点基础研究发展规划(“973”计划)项目(2005CB321800)；湖南省教育厅科研基金资助项目(07C400)
通信作者：王正飞(1970-)，男，湖南衡阳人，博士，副教授，从事数据库安全、加密等研究；电话：13974822370；E-mail: feizhengwang@163.com
