外包数据库中基于随机噪声的查询完全性验证
2014-11-19 18:47鲁红闫振福盛刚
电脑知识与技术 2014年30期
鲁红 闫振福 盛刚
摘要：数据库外包允许企业或机构把数据库管理工作外包给专业第三方，将精力集中在其核心业务。在数据库外包研究领域中存在隐私保护、查询完整性验证和用户访问控制等安全问题。在冗余数据方法的基础上，提出对冗余数据增加随机噪声，为外包数据库提供查询结果完整性检验。实验结果表明了该方法安全性和有效性。
关键词： 数据库外包；查询完全性；随机噪声
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）30-7008-04
一些企业或机构为降低总体成本，选择把非核心业务外包给其他机构。随着网络技术的快速发展，完全可以把数据库服务外包给专业的第三方，从而节省了为维护DBMS而用在硬件、软件、场地、专业人员等方面的费用。数据库外包的模型见图1[1]，该模型包括四部分：数据的所有者、客户、可信网关和服务提供商。任意两部分之间的通信都是经过加密的。数据的所有者可以直接也可以通过可信网关把数据发送到服务提供商，客户只能通过可信网关与服务提供商通信。可信网关负责数据加密、数据解密和数据检验等。
在数据库外包领域中，有许多问题需要解决，包括数据保密，聚集查询和查询完整性等。数据保密是一个基本问题，因为一个企业的业务数据是其核心财富。除了数据的所有者和合法的客户能够访问到数据外，即使是服务提供商也不可以。由于外包数据的特点，传统的加密加密算法如DES、RSA等都不太适合。外包的数据库要允许客户可以执行标准的查询，如求大于某个数的记录，某列的最大值，某些值的平均值等，必然会用到数据之间的大小关系，而用DES、RSA加密过的数据之间的大小关系已经发生了改变。文献[2]中，提出了一种能够维持数据间的顺序的加密方法。文献[3][4]中，提出了解决聚集查询的方法。
查询是DBMS的主要任务之一，因而保证查询的正确性也非常很重要的。查询正确性包括查询结果的正确性和查询完整性。查询结果的正确性是指查询得到的数据没有被修改过，而且全部来自于数据所有者，不是其他人恶意添加的。查询完整性是指所有满足查询条件的数据都包括在结果集中。
在现有允许对加密数据进行查询的基础之上，该文提出了一个解决查询正确性中的查询完整性的方法，该方法可以用来检验是否所有满足查询条件的记录都在结果集中。在已有的研究成果中，如文献[5][6][7][8]，已经提出了一些解决方案，但是，有些需要修改DBMS。
1 相关工作
在当前解决数据库外包中的查询完整性检验问题上，有两类方法：一类运用一些数据结构，如 MHT [5]，aggregated signature [6]， challenge token [7]， ADG-H [8]等；另一类运用了概率方法，如文献[9][10][11]。在文献[5]中，提出在数据排序的基础上，在服务提供商端建立MHT[10]，用该结构验证查询结果，其需要服务提供商的协助，该方法不适合数据库频繁修改的情况。
文献[6]在数据排序的基础上，运用了数字签名链，该方法也不适合数据库频繁修改的情况。文献[7]提出运用令牌，用以检测服务提供商是否查询了所有记录。该方法也需要服务提供商的协助，并且不能保证服务提供商把所有查询得到的记录返回给客户。
在文献[9]中，把一些随机生成的伪元组插入到数据库中，与数据所有者原来的数据混合在一起，用同一种加密方案加密，并且记录哪些伪元组插入到数据库中。查询时，伪元组与真正元组一起返回到客户端，客户端利用这些记录的信息判断是否所有满足查询条件的伪元组都返回到客户端。该方法较好地解决了查询完全性问题，试验也表明了该方法的有效性，但是在客户端仍然保留了过多的信息，尤其是在服务提供商端的数据库中有较多字段的时候。
2 基于随机噪声的方法
在本节中，我们介绍一种简单而有效的概率方法用以进行数据库外包中的查询完全性检验。数据库T在由数据所有者经过预处理和加密后发送到服务提供商。加密算法采用文献[2]中的方法，我们的方法用在预处理过程。
在预处理阶段，先根据某种策略选出一些记录T1，然后对T1进行一些微小的修改，得到一些新的不同与T1的T1，最后把T1插入到T，得到一个新的数据库T。
经过预处理，数据库T经过加密后，就可以发送到服务提供商端。而在服务提供商端，由于所有的数据都是经过加密的，无法区分T1与T1，它们被视为不同的记录，而它们的关系也不会暴露。
在由服务提供商返回给客户的结果集R中，如果有一些记录属于T1，那么必然应该有相同数量的属于T1的记录出现，并且T1与T1中的记录是相对应的。如果是这样，那么就满足查询完全性，否则，如果结果集R中属于T1与T1的记录不是相对应的，查询完全性就遭到了破坏。这样，就实现了查询完全性验证的目的，不论是数据库中的记录还是结果集中的记录被删除，都能检测到客户得到的结果集不是其应该得到的。
整个预处理过程可以分为两个步骤：记录的选择和记录的修改。在记录选择过程中，选中了一些记录，为了提高记录选择的秘密性，用到了单向散列函数H[11][12]，如MD5或SHA。H的作用是将变长字符串转换固定长度的二进制串，如128个比特。一旦选中了一个记录r，接着对r进行微小修改，得到一个新记录r（称为重复记录），然后将r插入T中。
在查询时，需要改写查询语句以使重复记录与其对应原始记录一起包含在结果集中，这个过程非常关键。
在接下来的预处理和查询语句改写两节中，将详细介绍基于随机噪声的方法。
2.1 预处理过程
算法 PreProcessing （T， key， k， m） 给出了预处理过程的步骤。参数T代表数据库，key为数据所有者的密码，k，m为两个整数，也由数据所有者拥有。参数key，k，m是用来提高记录选择的秘密性和随机性，k也用来决定要选择多少记录作为重复记录。r.PK表示记录r的关键词。符号⊕为字符串连接符。endprint
对数据库T中的每一个记录r，如果表达式 H（r.PK⊕key） mod k 的值等于m，那么r就被选中用以生成一个新记录r，r的每个属性的值都是对r相对应的属性值进行微小的修改得到的。即r的每个属性的值与r相对应的属性值差别很小，至于相差多少，可以由数据所有者决定，也可以根据属性的性质决定。可以为0.01，0.1，1，3等。为描述简单起见，在本文中，我们选择修改值为0.5。然后将r插入数据库中。在服务提供商端，由于所有数据都是加密的，所以r与r的关系不会轻易暴露。
PreProcessing （T， key， k， m）
S = {}
Foreach tuple r T do
If H（r.PK⊕key） mod k is equal to m then
r = SubtleModification （r）
S = S + r
Endif
Endfor
End
为了能够区分开T中的重复记录和非重复记录，我们采用文献[9]的方法，即在数据库中增加一个列ah，对于非重复记录r，ah的值为
[H（r.pk⊕r.a1⊕r.a2⊕...⊕r.an⊕key）] （1）
对于重复记录，ah的值为
[H（r.pk⊕r.a1⊕r.a2⊕...⊕r.an⊕key）+1] （2）
这样，当在客户端需要检验查询完整性时，列ah的值可以用来区分重复记录和非重复记录。
2.2 查询语句改写
生成与插入重复记录的目的就是为了在查询时，重复记录能够与非重复记录一起返回到客户端。通过检查重复记录与非重复记录的对应关系，就可以判断服务提供商是否返回了所有应该返回的记录。如果一个重复记录应该在但是没有结果集中，客户端就有充分的理由认为查询完全性遭到了破环。
而如果将客户的查询语句直接发送到服务提供商而不做任何处理，那么插入的重复记录就没有任何意义，查询完整性检验也得不到保证。为了使重复记录与非重复记录一起返回到客户端，就改写客户的查询语句。查询语句改写工作由可信网关完成，即相关参数需要保留在可信网关。
改写规则为：如果原始查询条件为等于，则改写为大于等于和小于；如果原始查询条件为小于，则不必改写；如果查询条件为大于，则改写后仍为大于，但范围要扩大。当然，查询语句的改写该取决于微小修改的程度。
具体地，假设修改值为0.5，并且T有一个整数字段 price，给出一个查询语句q：Select * from T where price = E （100），其中E为加密算法。
如果将q直接发给服务提供商，那么在服务提供商返回的结果集Tq中，只有符合查询条件的非重复记录，而没有任何的重复记录，这样就不能保证查询完全性，客户端没有任何能力检测服务提供商是否返回了所有符合查询条件的记录。
而如果将q改写为q： Select * from T where price >= E （100） and price 同样，如果查询语句q为下列形式： q： Select * from T where price > E （100） and price < E （200）， 那么q应该改写为 q： Select * from T where price > E （100） and price 联合查询也需要改写，如联合查询q为下列形式（仍然假设T1与T2都有一个整数列price）： q： select * from T1， T2 where T1.price = E （100） and （T2.price > E （500） or T2.price < E （50）） 那么q应该改写为 q： Select * from T1， T2 where T1. price >= E （100） and T1.price and （T2.price > E （500） or T2.price < E （50+1） ） 2.3 查询完全性检验 收到由服务提供商返回的查询结果集R，可信网关开始检验查询完全性，具体见算法Verify （R， key， k， m）。R表示结果集，key， k， m 与算法PreProcessing的相同。 对R中的每个记录r，首先计算用公式1计算AH，如果AH的值不等于r.ah也不等于r.ah+1，那么记录r就不是由数据拥有者插入的，或者记录r的属性值被该过，检验过程结束，返回false，这一步可以保证r来自数据拥有者，不论r是重复记录还是非重复记录；其次，如果r为非重复记录且应该对应一个重复记录，即r.ah等于AH并且H （ r.PK⊕key ） mod k等于m，则变量OriginalCount加1，如果r为重复记录，即r.ah等于AH+1，则变量DuplicateCount加1；最后，如果变量OriginalCount与DuplicateCount值相等，则表示查询完全性检验通过，返回true，否则不通过，返回false。
Boolean Verify （R， key， k， m）
OriginalCount = 0
DuplicateCount = 0
Foreach tuple r R do
AH =
If （ r.ah ！= AH ） and （ r.ah ！=1+ AH ） then
return false
Endif
If （ r.ah == AH ） and （ H （ r.PK⊕key ） mod k == m ） then
OriginalCount++
Else if （ r.ah==1+ AH ） then
DuplicateCount++
Endif
Endfor
return （ OriginalCount == DuplicateCount ）
End
3 实验
本节通过实验来检验基于随机噪声的方法的安全性。
实验用的数据集来自Forest Cover Type数据库，可以从University of California的Irvine KDD Archive得到。该数据集共有581012行，61列，试验中取其前10列，再另加一个主键。数据库用MySql5.5，用JDBC连接客户端和服务提供商。
由于随机噪声方法中，添加了一个特殊列ah，该列可以用来检验记录数据的正确性，即是否被修改过，是否是来自数据拥有者。所以，试验中只需考虑删除记录攻击和删除查询结果集记录攻击，即删除数据库中记录的攻击和删除查询结果集中记录的攻击，其他攻击方式不必再考虑。
3.1 数据库记录删除攻击试验
本节模拟数据库记录删除攻击试验，每次攻击从数据库中随机删除n个记录，对每个n做100次，统计没能检测出攻击的次数，n从1逐渐增加到30。
在图2中，k设为11（见3.2.1节算法PreProcessing），从而重复记录为非重复记录的1/11道5/11。例如，当仅有1/11的重复记录时，如果有超过15个记录被删除，那么该攻击将以不低于0.8的概率被检测到。
3.2 查询结果集记录删除攻击试验
本节模拟查询结果集记录删除攻击试验。为得到查询结果集，用如下形式的查询语句：
Select * from T where a1>=v1 and a2 随机生成100个数据对v1， v2 （v1 4 结论 目前，数据库外包是一个新的研究领域，其应用有利于许多企业的发展。一些企业可以提供专业的数据库服务，充当数据库服务提供商的角色，而另一些企业可以把自己的数据库外包给专业的公司，这也符合社会分工的原则。外包中，安全和服务质量都很重要，而查询完整性就是服务质量的一个重要方面。该文提出的随机噪声验证外包数据库查询完全性问题的方法，不需要服务提供商的任何协助，而且可以有效地解决查询完全性验证问题，并且验证过程并不复杂。 参考文献： [1] Hakan Hacigumus，Sharad Mehrotra，Balakrishna R Iyer.Providing database as a service[C].Proceedings of ICDE，IEEE Press，2002：29-40. [2] Rakesh Agrawal，Jerry Kiernan，Ramakrishnan Srikant，Yirong Xu.Order-preserving encryption for numeric data[C].Proceedings of SIGMOD，ACM Press，2004：563-574. （下转第7018页） （上接第7011页） [3] Hakan Hacigumus，Bala lyer，Chen Li，Sharad Mehrotra.Executing SQL over Encrypted Data in the Database-Service-Provider Model[C].Proceedings of SIGMOD，ACM Press，2002：216-227. [4] Tingjian Ge，Stan Zdonik.Answering Aggregation Queries in a Secure System Model[C]. Proceedings of VLDB，IEEE Press，2007：519-530. [5] Premkumar T Devanbu， ichael Gertz，Charles U Martel，Stuart G.Stubblebine. Authentic third-party data publication[C].Proceedings of DBSec，IFIP Press，2000：101-112. [6] HweeHwa Pang，Arpit Jain，Krithi Ramamritham，Kian-Lee Tan Verifying completeness of relational query results in data publishing[C].Proceedings of SIGMOD，ACM Press，2005：407-418. [7] Radu Sion.Query execution assurance for outsourced databases[C].Proceedings of VLDB，ACM Press，2005：601-612. [8] 盛刚，温涛，郭权.云计算中偏好Top-k查询结果的验证[J].吉林大学学报：工学版，2014， 44（1）：164-170. [9] Min Xie，Haixun Wang，Jian Yin，Xiaofeng Meng.Integrity Auditing of Outsourced Data[C]. Proceedings of VLDB，IEEE Press，2007：782-793. [10] Wang H， Yin J，Perng C.Dual encryption for query integrity assurance[C].Proceedings of CIKM， ACM Press，2008：863-872. [11] Ku W，Hu L，Shahabi C.A query integrity assurance scheme for accessing outsourced spatial databases[J].GeoInformatica，2013 ，77（1）：97-124. [12] Min Xie，Haixun Wang，Jian Yin.Providing Freshness Guarantees for Outsourced Databases[C]. Proceedings of EDBT，IEEE Press，2008：323-332.
Boolean Verify （R， key， k， m）
OriginalCount = 0
DuplicateCount = 0
Foreach tuple r R do
AH =
If （ r.ah ！= AH ） and （ r.ah ！=1+ AH ） then
return false
Endif
If （ r.ah == AH ） and （ H （ r.PK⊕key ） mod k == m ） then
OriginalCount++
Else if （ r.ah==1+ AH ） then
DuplicateCount++
Endif
Endfor
return （ OriginalCount == DuplicateCount ）
End
3 实验
本节通过实验来检验基于随机噪声的方法的安全性。
实验用的数据集来自Forest Cover Type数据库，可以从University of California的Irvine KDD Archive得到。该数据集共有581012行，61列，试验中取其前10列，再另加一个主键。数据库用MySql5.5，用JDBC连接客户端和服务提供商。
由于随机噪声方法中，添加了一个特殊列ah，该列可以用来检验记录数据的正确性，即是否被修改过，是否是来自数据拥有者。所以，试验中只需考虑删除记录攻击和删除查询结果集记录攻击，即删除数据库中记录的攻击和删除查询结果集中记录的攻击，其他攻击方式不必再考虑。
3.1 数据库记录删除攻击试验
本节模拟数据库记录删除攻击试验，每次攻击从数据库中随机删除n个记录，对每个n做100次，统计没能检测出攻击的次数，n从1逐渐增加到30。
在图2中，k设为11（见3.2.1节算法PreProcessing），从而重复记录为非重复记录的1/11道5/11。例如，当仅有1/11的重复记录时，如果有超过15个记录被删除，那么该攻击将以不低于0.8的概率被检测到。
3.2 查询结果集记录删除攻击试验
本节模拟查询结果集记录删除攻击试验。为得到查询结果集，用如下形式的查询语句：
Select * from T where a1>=v1 and a2 随机生成100个数据对v1， v2 （v1 4 结论 目前，数据库外包是一个新的研究领域，其应用有利于许多企业的发展。一些企业可以提供专业的数据库服务，充当数据库服务提供商的角色，而另一些企业可以把自己的数据库外包给专业的公司，这也符合社会分工的原则。外包中，安全和服务质量都很重要，而查询完整性就是服务质量的一个重要方面。该文提出的随机噪声验证外包数据库查询完全性问题的方法，不需要服务提供商的任何协助，而且可以有效地解决查询完全性验证问题，并且验证过程并不复杂。 参考文献： [1] Hakan Hacigumus，Sharad Mehrotra，Balakrishna R Iyer.Providing database as a service[C].Proceedings of ICDE，IEEE Press，2002：29-40. [2] Rakesh Agrawal，Jerry Kiernan，Ramakrishnan Srikant，Yirong Xu.Order-preserving encryption for numeric data[C].Proceedings of SIGMOD，ACM Press，2004：563-574. （下转第7018页） （上接第7011页） [3] Hakan Hacigumus，Bala lyer，Chen Li，Sharad Mehrotra.Executing SQL over Encrypted Data in the Database-Service-Provider Model[C].Proceedings of SIGMOD，ACM Press，2002：216-227. [4] Tingjian Ge，Stan Zdonik.Answering Aggregation Queries in a Secure System Model[C]. Proceedings of VLDB，IEEE Press，2007：519-530. [5] Premkumar T Devanbu， ichael Gertz，Charles U Martel，Stuart G.Stubblebine. Authentic third-party data publication[C].Proceedings of DBSec，IFIP Press，2000：101-112. [6] HweeHwa Pang，Arpit Jain，Krithi Ramamritham，Kian-Lee Tan Verifying completeness of relational query results in data publishing[C].Proceedings of SIGMOD，ACM Press，2005：407-418. [7] Radu Sion.Query execution assurance for outsourced databases[C].Proceedings of VLDB，ACM Press，2005：601-612. [8] 盛刚，温涛，郭权.云计算中偏好Top-k查询结果的验证[J].吉林大学学报：工学版，2014， 44（1）：164-170. [9] Min Xie，Haixun Wang，Jian Yin，Xiaofeng Meng.Integrity Auditing of Outsourced Data[C]. Proceedings of VLDB，IEEE Press，2007：782-793. [10] Wang H， Yin J，Perng C.Dual encryption for query integrity assurance[C].Proceedings of CIKM， ACM Press，2008：863-872. [11] Ku W，Hu L，Shahabi C.A query integrity assurance scheme for accessing outsourced spatial databases[J].GeoInformatica，2013 ，77（1）：97-124. [12] Min Xie，Haixun Wang，Jian Yin.Providing Freshness Guarantees for Outsourced Databases[C]. Proceedings of EDBT，IEEE Press，2008：323-332.
Boolean Verify （R， key， k， m）
OriginalCount = 0
DuplicateCount = 0
Foreach tuple r R do
AH =
If （ r.ah ！= AH ） and （ r.ah ！=1+ AH ） then
return false
Endif
If （ r.ah == AH ） and （ H （ r.PK⊕key ） mod k == m ） then
OriginalCount++
Else if （ r.ah==1+ AH ） then
DuplicateCount++
Endif
Endfor
return （ OriginalCount == DuplicateCount ）
End
3 实验
本节通过实验来检验基于随机噪声的方法的安全性。
实验用的数据集来自Forest Cover Type数据库，可以从University of California的Irvine KDD Archive得到。该数据集共有581012行，61列，试验中取其前10列，再另加一个主键。数据库用MySql5.5，用JDBC连接客户端和服务提供商。
由于随机噪声方法中，添加了一个特殊列ah，该列可以用来检验记录数据的正确性，即是否被修改过，是否是来自数据拥有者。所以，试验中只需考虑删除记录攻击和删除查询结果集记录攻击，即删除数据库中记录的攻击和删除查询结果集中记录的攻击，其他攻击方式不必再考虑。
3.1 数据库记录删除攻击试验
本节模拟数据库记录删除攻击试验，每次攻击从数据库中随机删除n个记录，对每个n做100次，统计没能检测出攻击的次数，n从1逐渐增加到30。
在图2中，k设为11（见3.2.1节算法PreProcessing），从而重复记录为非重复记录的1/11道5/11。例如，当仅有1/11的重复记录时，如果有超过15个记录被删除，那么该攻击将以不低于0.8的概率被检测到。
3.2 查询结果集记录删除攻击试验
本节模拟查询结果集记录删除攻击试验。为得到查询结果集，用如下形式的查询语句：
Select * from T where a1>=v1 and a2 随机生成100个数据对v1， v2 （v1 4 结论 目前，数据库外包是一个新的研究领域，其应用有利于许多企业的发展。一些企业可以提供专业的数据库服务，充当数据库服务提供商的角色，而另一些企业可以把自己的数据库外包给专业的公司，这也符合社会分工的原则。外包中，安全和服务质量都很重要，而查询完整性就是服务质量的一个重要方面。该文提出的随机噪声验证外包数据库查询完全性问题的方法，不需要服务提供商的任何协助，而且可以有效地解决查询完全性验证问题，并且验证过程并不复杂。 参考文献： [1] Hakan Hacigumus，Sharad Mehrotra，Balakrishna R Iyer.Providing database as a service[C].Proceedings of ICDE，IEEE Press，2002：29-40. [2] Rakesh Agrawal，Jerry Kiernan，Ramakrishnan Srikant，Yirong Xu.Order-preserving encryption for numeric data[C].Proceedings of SIGMOD，ACM Press，2004：563-574. （下转第7018页） （上接第7011页） [3] Hakan Hacigumus，Bala lyer，Chen Li，Sharad Mehrotra.Executing SQL over Encrypted Data in the Database-Service-Provider Model[C].Proceedings of SIGMOD，ACM Press，2002：216-227. [4] Tingjian Ge，Stan Zdonik.Answering Aggregation Queries in a Secure System Model[C]. Proceedings of VLDB，IEEE Press，2007：519-530. [5] Premkumar T Devanbu， ichael Gertz，Charles U Martel，Stuart G.Stubblebine. Authentic third-party data publication[C].Proceedings of DBSec，IFIP Press，2000：101-112. [6] HweeHwa Pang，Arpit Jain，Krithi Ramamritham，Kian-Lee Tan Verifying completeness of relational query results in data publishing[C].Proceedings of SIGMOD，ACM Press，2005：407-418. [7] Radu Sion.Query execution assurance for outsourced databases[C].Proceedings of VLDB，ACM Press，2005：601-612. [8] 盛刚，温涛，郭权.云计算中偏好Top-k查询结果的验证[J].吉林大学学报：工学版，2014， 44（1）：164-170. [9] Min Xie，Haixun Wang，Jian Yin，Xiaofeng Meng.Integrity Auditing of Outsourced Data[C]. Proceedings of VLDB，IEEE Press，2007：782-793. [10] Wang H， Yin J，Perng C.Dual encryption for query integrity assurance[C].Proceedings of CIKM， ACM Press，2008：863-872. [11] Ku W，Hu L，Shahabi C.A query integrity assurance scheme for accessing outsourced spatial databases[J].GeoInformatica，2013 ，77（1）：97-124. [12] Min Xie，Haixun Wang，Jian Yin.Providing Freshness Guarantees for Outsourced Databases[C]. Proceedings of EDBT，IEEE Press，2008：323-332.
