基于支持快速查询的嵌入式数据库加密技术研究

黎 明

(广东理工学院 信息技术学院,广东 肇庆 526100)

随着计算机应用的普及和信息技术的不断发展,与之息息相关的数据库技术的发展也日趋成熟与完善,应用范围越来越广泛。数据库技术是计算机信息技术的重要组成部分,数据库中包含了用户隐私、商业机密等各种重要信息,因此容易成为受到攻击并进行数据窃取的目标[1]。目前常规的访问控制手段,对于重要数据以及敏感数据来说,难以起到完备的保护作用。因此,借助加密算法加密数据库中的数据,已成为一种常见的数据库数据保护手段[2]。此类方法能够较好地提升数据库的安全性,但是数据在被加密之后,往往容易失去数据本身具有的相似性、有序性以及可比性,这对加密数据来说,显然会影响查询效率[3-4]。如何保证密文数据库在起到加密保护作用的同时,也能够实现快速查询,成为业界研究的重难点。目前已有的针对嵌入式加密数据库的快速查询方案,在针对划分值的提取上仍然存在有待改进之处。本研究针对常见的缺陷,提出以最佳桶划分为基础依据的嵌入式加密数据库快速查询与储存的方案。

1 以最佳桶划分为依据的数据库加密方案

1.1 快速查询的嵌入式数据库加密

数据库加密的具体流程可以简述如下:

设原始数据表为ω(k,j),那么针对该数据表分类的公式为

(1)

式(1)中:加密数据的属性通过Kjk表示,标类号通过li表示,数据中待分类的部分通过λi表示,数据属性对应独立条件通过δ表示。加密过程为

(2)

式(2)中:H_exch为数据加密后的密文,随机数的生成通过Q(I)完成,以实现密钥的初始化功能,响应系统中初始的参数值用μ表示,由加密属性推得关键数的索引用m(k,v)表示,相邻的加密数据中二次迭代的对应通过AS(i,θ)表示,加密属性提取后对应的划分值通过ξ(i,k)表示,ψ为不用加密数据类对应的权重参数。

分类隐私加密方式为

(3)

1.1.1 字符型数据加密的存储

图1 存储字符型数据加密流程

1.1.2 字符型数据加密的查询

针对字符串加密进行SQL(Structured Query Language)查询,可以通过两阶段查询方式来实现[6]。初次查询是粗糙查询,主要的方式是过滤待查询字符串当中的索引字段。但在过滤的过程中,可能会错漏掉部分字段,产生一定的“伪记录”,因此需进行第二次查询(精确查询),对模糊查询得到的结果,再次进行SQL语句查询。在实际实施过程中,通过随机映射函数的方式进行查询,如对Ai=b进行查询时,得到的映射函数可表示为

MapQAi(b)=IdentQAi(lj)

(4)

式(4)中,包含b对应的划分用lj表示。当Ai>b时进行查询,此时的映射函数应当满足条件MapQAi>b,且映射值包含的划分{li,li+1,…,lj}应当全部大于b对应的值;同样当Ai

图2 字符型数据加密查询流程

1.2 分析改进算法

1.2.1 分析正确性

改进算法进行的两个阶段的查询,在模糊查询也即第一次查询时,选定的记录中必然包含所有符合条件的记录;在精确查询也即第二次查询的过程中,首次查询漏掉的不符合条件的查询记录一定会被过滤掉。因此通过两阶段查询,能够获得目标需求的所有准确集合。

1.2.2 分析查询效率

与等深或等宽划分相比,以最佳桶划分为基础的查询方式具有最低的查询成本以及更高的查询效率[7]。理论上,对桶划分策略衡量的参数依据,应当是错检元组的总数。当划分桶区间当中包含的属性值为X时,错检元组的总数为

(5)

也就是说,当限定了桶划分的区间数目时,要保证查询获得最高的命中率,就要使用最小的错检元组的总数XF。

以等深划分或最佳桶划分为依据的过滤效率的对比,可以通过对各划分当中错检元组的总数进行计算来实现。如

(6)

其中:(a,4)表示在输入当中,共有4个字符串是以a开头的,其他组同理。如果设在划分子区当中,上限数目X=4,那么划分方式为等深划分时,划分区间的分布为{a,b,c},{d},{e,f},{g,h,i,j},错检元组的总数求得为130;当划分方式采用最佳桶划分时,划分所得的划分区间的分布为{a,b,c},{d,e},{f,g},{h,i,j},错检元组的总数求得为120。其错检元组分组示意图如图3所示。

图3 错检元组分组示意

也就是说,通过最佳桶划分的方式,能够保证在加密数据库当中得到的错误元更少,查询效率更高。等深划分和最佳桶划分通过在500条的随机字符串当中的查询代价的对比如图4所示。

图4 等深划分与最佳桶划分的查询代价对比

1.2.3 选取划分桶的数量

选取划分桶的数量,首先应当设定相应待加密字段的阈值。提高划分桶的数量在一定程度上来说是为了能够得到更好的查询效率,但是并不是越高的划分桶数量就能获得越高的查询效率。一是因为划分桶数量的刻意提高容易降低对应的索引字段的安全性,当过滤效率不是100%时,设置划分值不仅是无意义的,而且会对原方案的安全性造成破坏;二是因为划分桶的数量提升到一定的阈值时,过滤效率将不再提升,只停留在当前阶段,这就使得攻击者能够通过划分值对原字符串进行推测。在改进算法当中,主要考虑两个因素对划分桶数量的选定的影响:一是设定相应的加密字段的阈值;二是在设定阈值条件下,选择划分桶的最大可行数量[8]。

2 实验设计与结果分析

仿真实验采用的操作系统为Windows 7,服务器数据库为SQL Server 2008,数据表选用AdventrueWorks中的Person.asses。实验的数据源选择数据表记录中的前1 000条,加密处理的敏感字段为AddressLine1字段。采用高级加密标准(Advanced Encryption Standard, AES)加密算法进行敏感字段的加密,密钥长度选取128 bit。

2.1 测试查询时间效率

对以最佳桶划分为依据的方式以及解密之后再进行查询的方式进行对比试验时,需将对应的查询条件设定为Ai=b,试验结果如图5所示。

图5 不同划分方法查询时间比较

从图5可以看出,在划分桶数量不断增加的过程当中,最佳桶划分以及等深划分的方式查询需要的时间不断缩短,也就是说其查询效率不断提升。其中,通过最佳桶划分方式面对不同划分个数需要的时间均值为53.07 ms,通过等深划分的时间均值为57.89 ms,相较而言,最佳桶划分所需查询时间更短。

2.2 测试过滤效率

图6 不同划分方法过滤效率比较

从图6可以看出:解密后查询的方式不涉及过滤效率,过滤效率曲线为0。最佳桶划分以及等深划分两种方式对于加密数据都具有一定的过滤能力。在划分桶不断增加的过程中,两种方式的过滤能力也不断提高。相比之下,最佳桶划分的过滤效率更高,消耗资源更少,任务执行更加稳定。

2.3 隐私数据分类误差对比

SQL Server 2008数据库中,在选定的数据表Person.asses中随机选取1 000条数据,对选取的数据进行加密并进行隐私数据分类,并计算其误差概率,实验结果如图7所示。

图7 不同划分方法误差概率比较

从图7可以看出,通过解密后查询的方式对隐私数据的划分误差约为0.8%,等深划分对隐私数据的划分误差约为0.4%,基于最佳桶划分的方式在0.2%之内。在对隐私数据的划分误差上,最佳桶划分相比其他方式更为精确。

2.4 测试可靠性

在数据库中随机选取不同数量数据进行数据加密,选取的数据数量分别为500,1 000,1 500,2 000,2 500,3 000条,通过虚拟非授权用户对加密数据进行非法解密,依靠解密率比较数据加密技术的可靠性,实验结果如图8所示。

图8 不同划分方式可靠性比较

从图8可以看出,解密后查询以及等深划分的方式数据加密技术的可靠性均超过0.7%,基于最佳桶划分的方式数据库加密的可靠性约为0.5%。故最佳桶划分的方式相比其他方式可靠性更高。

3 结 语

通过以最佳桶划分为依据的方式对划分值进行提取,来实现嵌入式数据库加密当中的快速查询。同时,通过与等深划分以及解密之后再进行查询的方式进行实验对比,进一步验证了最佳桶划分的方式具有更高的过滤效率、更短的查询时间,证明最佳桶划分的查询方式针对字符段数据以及动态数据具有更好的查询效果。