魯紅　閆振福　盛剛

摘要：數(shù)據(jù)庫外包允許企業(yè)或機(jī)構(gòu)把數(shù)據(jù)庫管理工作外包給專業(yè)第三方，將精力集中在其核心業(yè)務(wù)。在數(shù)據(jù)庫外包研究領(lǐng)域中存在隱私保護(hù)、查詢完整性驗(yàn)證和用戶訪問控制等安全問題。在冗余數(shù)據(jù)方法的基礎(chǔ)上，提出對(duì)冗余數(shù)據(jù)增加隨機(jī)噪聲，為外包數(shù)據(jù)庫提供查詢結(jié)果完整性檢驗(yàn)。實(shí)驗(yàn)結(jié)果表明了該方法安全性和有效性。

關(guān)鍵詞： 數(shù)據(jù)庫外包；查詢完全性；隨機(jī)噪聲

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）30-7008-04

一些企業(yè)或機(jī)構(gòu)為降低總體成本，選擇把非核心業(yè)務(wù)外包給其他機(jī)構(gòu)。隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，完全可以把數(shù)據(jù)庫服務(wù)外包給專業(yè)的第三方，從而節(jié)省了為維護(hù)DBMS而用在硬件、軟件、場地、專業(yè)人員等方面的費(fèi)用。數(shù)據(jù)庫外包的模型見圖1[1]，該模型包括四部分：數(shù)據(jù)的所有者、客戶、可信網(wǎng)關(guān)和服務(wù)提供商。任意兩部分之間的通信都是經(jīng)過加密的。數(shù)據(jù)的所有者可以直接也可以通過可信網(wǎng)關(guān)把數(shù)據(jù)發(fā)送到服務(wù)提供商，客戶只能通過可信網(wǎng)關(guān)與服務(wù)提供商通信?？尚啪W(wǎng)關(guān)負(fù)責(zé)數(shù)據(jù)加密、數(shù)據(jù)解密和數(shù)據(jù)檢驗(yàn)等。

在數(shù)據(jù)庫外包領(lǐng)域中，有許多問題需要解決，包括數(shù)據(jù)保密，聚集查詢和查詢完整性等。數(shù)據(jù)保密是一個(gè)基本問題，因?yàn)橐粋€(gè)企業(yè)的業(yè)務(wù)數(shù)據(jù)是其核心財(cái)富。除了數(shù)據(jù)的所有者和合法的客戶能夠訪問到數(shù)據(jù)外，即使是服務(wù)提供商也不可以。由于外包數(shù)據(jù)的特點(diǎn)，傳統(tǒng)的加密加密算法如DES、RSA等都不太適合。外包的數(shù)據(jù)庫要允許客戶可以執(zhí)行標(biāo)準(zhǔn)的查詢，如求大于某個(gè)數(shù)的記錄，某列的最大值，某些值的平均值等，必然會(huì)用到數(shù)據(jù)之間的大小關(guān)系，而用DES、RSA加密過的數(shù)據(jù)之間的大小關(guān)系已經(jīng)發(fā)生了改變。文獻(xiàn)[2]中，提出了一種能夠維持?jǐn)?shù)據(jù)間的順序的加密方法。文獻(xiàn)[3][4]中，提出了解決聚集查詢的方法。

查詢是DBMS的主要任務(wù)之一，因而保證查詢的正確性也非常很重要的。查詢正確性包括查詢結(jié)果的正確性和查詢完整性。查詢結(jié)果的正確性是指查詢得到的數(shù)據(jù)沒有被修改過，而且全部來自于數(shù)據(jù)所有者，不是其他人惡意添加的。查詢完整性是指所有滿足查詢條件的數(shù)據(jù)都包括在結(jié)果集中。

在現(xiàn)有允許對(duì)加密數(shù)據(jù)進(jìn)行查詢的基礎(chǔ)之上，該文提出了一個(gè)解決查詢正確性中的查詢完整性的方法，該方法可以用來檢驗(yàn)是否所有滿足查詢條件的記錄都在結(jié)果集中。在已有的研究成果中，如文獻(xiàn)[5][6][7][8]，已經(jīng)提出了一些解決方案，但是，有些需要修改DBMS。

1 相關(guān)工作

在當(dāng)前解決數(shù)據(jù)庫外包中的查詢完整性檢驗(yàn)問題上，有兩類方法：一類運(yùn)用一些數(shù)據(jù)結(jié)構(gòu)，如 MHT [5]，aggregated signature [6]， challenge token [7]， ADG-H [8]等；另一類運(yùn)用了概率方法，如文獻(xiàn)[9][10][11]。在文獻(xiàn)[5]中，提出在數(shù)據(jù)排序的基礎(chǔ)上，在服務(wù)提供商端建立MHT[10]，用該結(jié)構(gòu)驗(yàn)證查詢結(jié)果，其需要服務(wù)提供商的協(xié)助，該方法不適合數(shù)據(jù)庫頻繁修改的情況。

文獻(xiàn)[6]在數(shù)據(jù)排序的基礎(chǔ)上，運(yùn)用了數(shù)字簽名鏈，該方法也不適合數(shù)據(jù)庫頻繁修改的情況。文獻(xiàn)[7]提出運(yùn)用令牌，用以檢測服務(wù)提供商是否查詢了所有記錄。該方法也需要服務(wù)提供商的協(xié)助，并且不能保證服務(wù)提供商把所有查詢得到的記錄返回給客戶。

在文獻(xiàn)[9]中，把一些隨機(jī)生成的偽元組插入到數(shù)據(jù)庫中，與數(shù)據(jù)所有者原來的數(shù)據(jù)混合在一起，用同一種加密方案加密，并且記錄哪些偽元組插入到數(shù)據(jù)庫中。查詢時(shí)，偽元組與真正元組一起返回到客戶端，客戶端利用這些記錄的信息判斷是否所有滿足查詢條件的偽元組都返回到客戶端。該方法較好地解決了查詢完全性問題，試驗(yàn)也表明了該方法的有效性，但是在客戶端仍然保留了過多的信息，尤其是在服務(wù)提供商端的數(shù)據(jù)庫中有較多字段的時(shí)候。

2 基于隨機(jī)噪聲的方法

在本節(jié)中，我們介紹一種簡單而有效的概率方法用以進(jìn)行數(shù)據(jù)庫外包中的查詢完全性檢驗(yàn)。數(shù)據(jù)庫T在由數(shù)據(jù)所有者經(jīng)過預(yù)處理和加密后發(fā)送到服務(wù)提供商。加密算法采用文獻(xiàn)[2]中的方法，我們的方法用在預(yù)處理過程。

在預(yù)處理階段，先根據(jù)某種策略選出一些記錄T1，然后對(duì)T1進(jìn)行一些微小的修改，得到一些新的不同與T1的T1，最后把T1插入到T，得到一個(gè)新的數(shù)據(jù)庫T。

經(jīng)過預(yù)處理，數(shù)據(jù)庫T經(jīng)過加密后，就可以發(fā)送到服務(wù)提供商端。而在服務(wù)提供商端，由于所有的數(shù)據(jù)都是經(jīng)過加密的，無法區(qū)分T1與T1，它們被視為不同的記錄，而它們的關(guān)系也不會(huì)暴露。

在由服務(wù)提供商返回給客戶的結(jié)果集R中，如果有一些記錄屬于T1，那么必然應(yīng)該有相同數(shù)量的屬于T1的記錄出現(xiàn)，并且T1與T1中的記錄是相對(duì)應(yīng)的。如果是這樣，那么就滿足查詢完全性，否則，如果結(jié)果集R中屬于T1與T1的記錄不是相對(duì)應(yīng)的，查詢完全性就遭到了破壞。這樣，就實(shí)現(xiàn)了查詢完全性驗(yàn)證的目的，不論是數(shù)據(jù)庫中的記錄還是結(jié)果集中的記錄被刪除，都能檢測到客戶得到的結(jié)果集不是其應(yīng)該得到的。

整個(gè)預(yù)處理過程可以分為兩個(gè)步驟：記錄的選擇和記錄的修改。在記錄選擇過程中，選中了一些記錄，為了提高記錄選擇的秘密性，用到了單向散列函數(shù)H[11][12]，如MD5或SHA。H的作用是將變長字符串轉(zhuǎn)換固定長度的二進(jìn)制串，如128個(gè)比特。一旦選中了一個(gè)記錄r，接著對(duì)r進(jìn)行微小修改，得到一個(gè)新記錄r（稱為重復(fù)記錄），然后將r插入T中。

在查詢時(shí)，需要改寫查詢語句以使重復(fù)記錄與其對(duì)應(yīng)原始記錄一起包含在結(jié)果集中，這個(gè)過程非常關(guān)鍵。

在接下來的預(yù)處理和查詢語句改寫兩節(jié)中，將詳細(xì)介紹基于隨機(jī)噪聲的方法。

2.1 預(yù)處理過程

算法 PreProcessing （T， key， k， m） 給出了預(yù)處理過程的步驟。參數(shù)T代表數(shù)據(jù)庫，key為數(shù)據(jù)所有者的密碼，k，m為兩個(gè)整數(shù)，也由數(shù)據(jù)所有者擁有。參數(shù)key，k，m是用來提高記錄選擇的秘密性和隨機(jī)性，k也用來決定要選擇多少記錄作為重復(fù)記錄。r.PK表示記錄r的關(guān)鍵詞。符號(hào)⊕為字符串連接符。endprint

對(duì)數(shù)據(jù)庫T中的每一個(gè)記錄r，如果表達(dá)式 H（r.PK⊕key） mod k 的值等于m，那么r就被選中用以生成一個(gè)新記錄r，r的每個(gè)屬性的值都是對(duì)r相對(duì)應(yīng)的屬性值進(jìn)行微小的修改得到的。即r的每個(gè)屬性的值與r相對(duì)應(yīng)的屬性值差別很小，至于相差多少，可以由數(shù)據(jù)所有者決定，也可以根據(jù)屬性的性質(zhì)決定?？梢詾?.01，0.1，1，3等。為描述簡單起見，在本文中，我們選擇修改值為0.5。然后將r插入數(shù)據(jù)庫中。在服務(wù)提供商端，由于所有數(shù)據(jù)都是加密的，所以r與r的關(guān)系不會(huì)輕易暴露。

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

為了能夠區(qū)分開T中的重復(fù)記錄和非重復(fù)記錄，我們采用文獻(xiàn)[9]的方法，即在數(shù)據(jù)庫中增加一個(gè)列ah，對(duì)于非重復(fù)記錄r，ah的值為

[H（r.pk⊕r.a1⊕r.a2⊕...⊕r.an⊕key）] （1）

對(duì)于重復(fù)記錄，ah的值為

[H（r.pk⊕r.a1⊕r.a2⊕...⊕r.an⊕key）+1] （2）

這樣，當(dāng)在客戶端需要檢驗(yàn)查詢完整性時(shí)，列ah的值可以用來區(qū)分重復(fù)記錄和非重復(fù)記錄。

2.2 查詢語句改寫

生成與插入重復(fù)記錄的目的就是為了在查詢時(shí)，重復(fù)記錄能夠與非重復(fù)記錄一起返回到客戶端。通過檢查重復(fù)記錄與非重復(fù)記錄的對(duì)應(yīng)關(guān)系，就可以判斷服務(wù)提供商是否返回了所有應(yīng)該返回的記錄。如果一個(gè)重復(fù)記錄應(yīng)該在但是沒有結(jié)果集中，客戶端就有充分的理由認(rèn)為查詢完全性遭到了破環(huán)。

而如果將客戶的查詢語句直接發(fā)送到服務(wù)提供商而不做任何處理，那么插入的重復(fù)記錄就沒有任何意義，查詢完整性檢驗(yàn)也得不到保證。為了使重復(fù)記錄與非重復(fù)記錄一起返回到客戶端，就改寫客戶的查詢語句。查詢語句改寫工作由可信網(wǎng)關(guān)完成，即相關(guān)參數(shù)需要保留在可信網(wǎng)關(guān)。

改寫規(guī)則為：如果原始查詢條件為等于，則改寫為大于等于和小于；如果原始查詢條件為小于，則不必改寫；如果查詢條件為大于，則改寫后仍為大于，但范圍要擴(kuò)大。當(dāng)然，查詢語句的改寫該取決于微小修改的程度。

具體地，假設(shè)修改值為0.5，并且T有一個(gè)整數(shù)字段 price，給出一個(gè)查詢語句q：Select * from T where price = E （100），其中E為加密算法。

如果將q直接發(fā)給服務(wù)提供商，那么在服務(wù)提供商返回的結(jié)果集Tq中，只有符合查詢條件的非重復(fù)記錄，而沒有任何的重復(fù)記錄，這樣就不能保證查詢完全性，客戶端沒有任何能力檢測服務(wù)提供商是否返回了所有符合查詢條件的記錄。

而如果將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應(yīng)該改寫為

q： Select * from T where price > E （100） and price

聯(lián)合查詢也需要改寫，如聯(lián)合查詢q為下列形式（仍然假設(shè)T1與T2都有一個(gè)整數(shù)列price）：

q： select * from T1， T2 where T1.price = E （100） and （T2.price > E （500） or T2.price < E （50））

那么q應(yīng)該改寫為

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 查詢完全性檢驗(yàn)

收到由服務(wù)提供商返回的查詢結(jié)果集R，可信網(wǎng)關(guān)開始檢驗(yàn)查詢完全性，具體見算法Verify （R， key， k， m）。R表示結(jié)果集，key， k， m 與算法PreProcessing的相同。

對(duì)R中的每個(gè)記錄r，首先計(jì)算用公式1計(jì)算AH，如果AH的值不等于r.ah也不等于r.ah+1，那么記錄r就不是由數(shù)據(jù)擁有者插入的，或者記錄r的屬性值被該過，檢驗(yàn)過程結(jié)束，返回false，這一步可以保證r來自數(shù)據(jù)擁有者，不論r是重復(fù)記錄還是非重復(fù)記錄；其次，如果r為非重復(fù)記錄且應(yīng)該對(duì)應(yīng)一個(gè)重復(fù)記錄，即r.ah等于AH并且H （ r.PK⊕key ） mod k等于m，則變量OriginalCount加1，如果r為重復(fù)記錄，即r.ah等于AH+1，則變量DuplicateCount加1；最后，如果變量OriginalCount與DuplicateCount值相等，則表示查詢完全性檢驗(yàn)通過，返回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 實(shí)驗(yàn)

本節(jié)通過實(shí)驗(yàn)來檢驗(yàn)基于隨機(jī)噪聲的方法的安全性。

實(shí)驗(yàn)用的數(shù)據(jù)集來自Forest Cover Type數(shù)據(jù)庫，可以從University of California的Irvine KDD Archive得到。該數(shù)據(jù)集共有581012行，61列，試驗(yàn)中取其前10列，再另加一個(gè)主鍵。數(shù)據(jù)庫用MySql5.5，用JDBC連接客戶端和服務(wù)提供商。

由于隨機(jī)噪聲方法中，添加了一個(gè)特殊列ah，該列可以用來檢驗(yàn)記錄數(shù)據(jù)的正確性，即是否被修改過，是否是來自數(shù)據(jù)擁有者。所以，試驗(yàn)中只需考慮刪除記錄攻擊和刪除查詢結(jié)果集記錄攻擊，即刪除數(shù)據(jù)庫中記錄的攻擊和刪除查詢結(jié)果集中記錄的攻擊，其他攻擊方式不必再考慮。

3.1 數(shù)據(jù)庫記錄刪除攻擊試驗(yàn)

本節(jié)模擬數(shù)據(jù)庫記錄刪除攻擊試驗(yàn)，每次攻擊從數(shù)據(jù)庫中隨機(jī)刪除n個(gè)記錄，對(duì)每個(gè)n做100次，統(tǒng)計(jì)沒能檢測出攻擊的次數(shù)，n從1逐漸增加到30。

在圖2中，k設(shè)為11（見3.2.1節(jié)算法PreProcessing），從而重復(fù)記錄為非重復(fù)記錄的1/11道5/11。例如，當(dāng)僅有1/11的重復(fù)記錄時(shí)，如果有超過15個(gè)記錄被刪除，那么該攻擊將以不低于0.8的概率被檢測到。

3.2 查詢結(jié)果集記錄刪除攻擊試驗(yàn)

本節(jié)模擬查詢結(jié)果集記錄刪除攻擊試驗(yàn)。為得到查詢結(jié)果集，用如下形式的查詢語句：

Select * from T where a1>=v1 and a2

隨機(jī)生成100個(gè)數(shù)據(jù)對(duì)v1， v2 （v1

4 結(jié)論

目前，數(shù)據(jù)庫外包是一個(gè)新的研究領(lǐng)域，其應(yīng)用有利于許多企業(yè)的發(fā)展。一些企業(yè)可以提供專業(yè)的數(shù)據(jù)庫服務(wù)，充當(dāng)數(shù)據(jù)庫服務(wù)提供商的角色，而另一些企業(yè)可以把自己的數(shù)據(jù)庫外包給專業(yè)的公司，這也符合社會(huì)分工的原則。外包中，安全和服務(wù)質(zhì)量都很重要，而查詢完整性就是服務(wù)質(zhì)量的一個(gè)重要方面。該文提出的隨機(jī)噪聲驗(yàn)證外包數(shù)據(jù)庫查詢完全性問題的方法，不需要服務(wù)提供商的任何協(xié)助，而且可以有效地解決查詢完全性驗(yàn)證問題，并且驗(yàn)證過程并不復(fù)雜。

參考文獻(xiàn)：

[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. （下轉(zhuǎn)第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] 盛剛，溫濤，郭權(quán).云計(jì)算中偏好Top-k查詢結(jié)果的驗(yàn)證[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，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 實(shí)驗(yàn)

本節(jié)通過實(shí)驗(yàn)來檢驗(yàn)基于隨機(jī)噪聲的方法的安全性。

實(shí)驗(yàn)用的數(shù)據(jù)集來自Forest Cover Type數(shù)據(jù)庫，可以從University of California的Irvine KDD Archive得到。該數(shù)據(jù)集共有581012行，61列，試驗(yàn)中取其前10列，再另加一個(gè)主鍵。數(shù)據(jù)庫用MySql5.5，用JDBC連接客戶端和服務(wù)提供商。

由于隨機(jī)噪聲方法中，添加了一個(gè)特殊列ah，該列可以用來檢驗(yàn)記錄數(shù)據(jù)的正確性，即是否被修改過，是否是來自數(shù)據(jù)擁有者。所以，試驗(yàn)中只需考慮刪除記錄攻擊和刪除查詢結(jié)果集記錄攻擊，即刪除數(shù)據(jù)庫中記錄的攻擊和刪除查詢結(jié)果集中記錄的攻擊，其他攻擊方式不必再考慮。

3.1 數(shù)據(jù)庫記錄刪除攻擊試驗(yàn)

本節(jié)模擬數(shù)據(jù)庫記錄刪除攻擊試驗(yàn)，每次攻擊從數(shù)據(jù)庫中隨機(jī)刪除n個(gè)記錄，對(duì)每個(gè)n做100次，統(tǒng)計(jì)沒能檢測出攻擊的次數(shù)，n從1逐漸增加到30。

在圖2中，k設(shè)為11（見3.2.1節(jié)算法PreProcessing），從而重復(fù)記錄為非重復(fù)記錄的1/11道5/11。例如，當(dāng)僅有1/11的重復(fù)記錄時(shí)，如果有超過15個(gè)記錄被刪除，那么該攻擊將以不低于0.8的概率被檢測到。

3.2 查詢結(jié)果集記錄刪除攻擊試驗(yàn)

本節(jié)模擬查詢結(jié)果集記錄刪除攻擊試驗(yàn)。為得到查詢結(jié)果集，用如下形式的查詢語句：

Select * from T where a1>=v1 and a2

隨機(jī)生成100個(gè)數(shù)據(jù)對(duì)v1， v2 （v1

4 結(jié)論

目前，數(shù)據(jù)庫外包是一個(gè)新的研究領(lǐng)域，其應(yīng)用有利于許多企業(yè)的發(fā)展。一些企業(yè)可以提供專業(yè)的數(shù)據(jù)庫服務(wù)，充當(dāng)數(shù)據(jù)庫服務(wù)提供商的角色，而另一些企業(yè)可以把自己的數(shù)據(jù)庫外包給專業(yè)的公司，這也符合社會(huì)分工的原則。外包中，安全和服務(wù)質(zhì)量都很重要，而查詢完整性就是服務(wù)質(zhì)量的一個(gè)重要方面。該文提出的隨機(jī)噪聲驗(yàn)證外包數(shù)據(jù)庫查詢完全性問題的方法，不需要服務(wù)提供商的任何協(xié)助，而且可以有效地解決查詢完全性驗(yàn)證問題，并且驗(yàn)證過程并不復(fù)雜。

參考文獻(xiàn)：

[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. （下轉(zhuǎn)第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] 盛剛，溫濤，郭權(quán).云計(jì)算中偏好Top-k查詢結(jié)果的驗(yàn)證[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，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 實(shí)驗(yàn)

本節(jié)通過實(shí)驗(yàn)來檢驗(yàn)基于隨機(jī)噪聲的方法的安全性。

實(shí)驗(yàn)用的數(shù)據(jù)集來自Forest Cover Type數(shù)據(jù)庫，可以從University of California的Irvine KDD Archive得到。該數(shù)據(jù)集共有581012行，61列，試驗(yàn)中取其前10列，再另加一個(gè)主鍵。數(shù)據(jù)庫用MySql5.5，用JDBC連接客戶端和服務(wù)提供商。

由于隨機(jī)噪聲方法中，添加了一個(gè)特殊列ah，該列可以用來檢驗(yàn)記錄數(shù)據(jù)的正確性，即是否被修改過，是否是來自數(shù)據(jù)擁有者。所以，試驗(yàn)中只需考慮刪除記錄攻擊和刪除查詢結(jié)果集記錄攻擊，即刪除數(shù)據(jù)庫中記錄的攻擊和刪除查詢結(jié)果集中記錄的攻擊，其他攻擊方式不必再考慮。

3.1 數(shù)據(jù)庫記錄刪除攻擊試驗(yàn)

本節(jié)模擬數(shù)據(jù)庫記錄刪除攻擊試驗(yàn)，每次攻擊從數(shù)據(jù)庫中隨機(jī)刪除n個(gè)記錄，對(duì)每個(gè)n做100次，統(tǒng)計(jì)沒能檢測出攻擊的次數(shù)，n從1逐漸增加到30。

在圖2中，k設(shè)為11（見3.2.1節(jié)算法PreProcessing），從而重復(fù)記錄為非重復(fù)記錄的1/11道5/11。例如，當(dāng)僅有1/11的重復(fù)記錄時(shí)，如果有超過15個(gè)記錄被刪除，那么該攻擊將以不低于0.8的概率被檢測到。

3.2 查詢結(jié)果集記錄刪除攻擊試驗(yàn)

本節(jié)模擬查詢結(jié)果集記錄刪除攻擊試驗(yàn)。為得到查詢結(jié)果集，用如下形式的查詢語句：

Select * from T where a1>=v1 and a2

隨機(jī)生成100個(gè)數(shù)據(jù)對(duì)v1， v2 （v1

4 結(jié)論

目前，數(shù)據(jù)庫外包是一個(gè)新的研究領(lǐng)域，其應(yīng)用有利于許多企業(yè)的發(fā)展。一些企業(yè)可以提供專業(yè)的數(shù)據(jù)庫服務(wù)，充當(dāng)數(shù)據(jù)庫服務(wù)提供商的角色，而另一些企業(yè)可以把自己的數(shù)據(jù)庫外包給專業(yè)的公司，這也符合社會(huì)分工的原則。外包中，安全和服務(wù)質(zhì)量都很重要，而查詢完整性就是服務(wù)質(zhì)量的一個(gè)重要方面。該文提出的隨機(jī)噪聲驗(yàn)證外包數(shù)據(jù)庫查詢完全性問題的方法，不需要服務(wù)提供商的任何協(xié)助，而且可以有效地解決查詢完全性驗(yàn)證問題，并且驗(yàn)證過程并不復(fù)雜。

參考文獻(xiàn)：

[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. （下轉(zhuǎn)第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] 盛剛，溫濤，郭權(quán).云計(jì)算中偏好Top-k查詢結(jié)果的驗(yàn)證[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，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.