周 鵬，龍士工

(1.貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025； 2.貴州省公共大數(shù)據(jù)重點實驗室，貴州 貴陽 550025)

0 引 言

隨著分布式計算機硬件處理能力和網(wǎng)絡(luò)傳輸能力的提升，遠(yuǎn)程數(shù)據(jù)處理中心能夠給用戶提供高質(zhì)量的數(shù)據(jù)和軟件服務(wù)。云計算就在這種情況下應(yīng)運而生了，它是繼網(wǎng)格計算、對等計算、分布式計算之后的又一種新型計算模式，其核心理念是按需服務(wù)、按用收費，為用戶提供隨處可用的資源連接池。通過云計算技術(shù)，不僅使得用戶和企業(yè)可以隨時隨地通過網(wǎng)絡(luò)訪問自己的資源，同時減少了在軟硬件管理上的投入。云計算強大的計算能力和存儲能力使得用戶更愿意將復(fù)雜的任務(wù)交付給云平臺處理，然而當(dāng)用戶將大量的數(shù)據(jù)部署到云平臺時，云計算系統(tǒng)就演變成一個云存儲系統(tǒng)，使得用戶用低廉的價格就能獲得海量的存儲能力，但是高度集中的計算機資源給云存儲帶來了嚴(yán)峻的安全挑戰(zhàn)。根據(jù)Gartner調(diào)查結(jié)果顯示，曾經(jīng)70%受訪企業(yè)的CEO擔(dān)心云數(shù)據(jù)隱私被侵犯而拒絕大量使用云計算模式。而在最近幾年，各大云服務(wù)提供商也相繼暴露出安全問題，如谷歌Gmail郵箱故障和盛大云機房物理服務(wù)器磁盤故障。

在現(xiàn)有的完整性驗證方案中由于自身原因存在著較大的局限性，如早期Deswarte等人[1]提出基于MAC認(rèn)證碼驗證機制，后來又在此基礎(chǔ)上做出改進(jìn)，利用同態(tài)特性(am)=arm=(ar)m，提出了基于RSA簽名完整性驗證機制以及Dan等人[2]提出的基于BLS的短簽名機制。上述方案中都在通訊效率和計算代價上做了改進(jìn)，但是都僅針對靜態(tài)數(shù)據(jù)存儲，并不能支持動態(tài)數(shù)據(jù)更新，無法適應(yīng)動態(tài)環(huán)境。因此，Ateniese等人[3]最先開始考慮如何支持動態(tài)操作，對現(xiàn)有方案做出改進(jìn)，提出了支持部分動態(tài)更新的驗證機制，但不能進(jìn)行數(shù)據(jù)插入操作?；谶@個問題，Erway等人[4]提出了基于跳表的驗證機制來支持插入操作，但其認(rèn)證路徑過長，每次需要大量的輔助信息支持，計算代價和通訊開銷較大。后來又提出了一種以Merkle-Tree數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的方案[5-6]，該方案中存儲數(shù)據(jù)集為S,將S中的元素存儲在Hash樹的葉子結(jié)點中，并且每個結(jié)點都存儲一個標(biāo)簽值。如果該結(jié)點為葉子結(jié)點，其標(biāo)簽值與其存儲的數(shù)據(jù)相同；否則其孩子結(jié)點的標(biāo)簽值就需要通過抗碰撞哈希函數(shù)計算得出。而用戶保存數(shù)據(jù)集S的摘要值就是Merkle-Tree根結(jié)點的摘要值。相比跳表具有更簡單的數(shù)據(jù)結(jié)構(gòu)，但是造成存儲空間的極大浪費。文獻(xiàn)[18]中將樹形結(jié)構(gòu)與RSA技術(shù)相結(jié)合構(gòu)造出一種RSA樹，該方案引入?yún)?shù)ε使得樹的高度和樹的分支都為常量，因此，該方案中得到的證據(jù)大小、查找和驗證的時間復(fù)雜度為O(l)。但是該方案采用了單向累加技術(shù)，需要使用復(fù)雜的冪運算，所以實際的運行時間并不樂觀，并且RSA樹在大量數(shù)據(jù)插入操作上并不靈活，還會導(dǎo)致復(fù)雜的結(jié)構(gòu)重構(gòu)問題。

基于上述完整性認(rèn)證方案所存在的不足，從存儲空間和通信效率角度出發(fā)，并與現(xiàn)有方案相結(jié)合，本文引入了一種平衡二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)——結(jié)點大小平衡樹(Size Balance Tree， SBT)，二叉排序樹的結(jié)構(gòu)特點使得數(shù)據(jù)的查找非常高效，可以快速定位到目標(biāo)結(jié)點；同時平衡二叉樹的結(jié)構(gòu)特點又能夠很好地維持樹的高度以至不退化為鏈表，保證了數(shù)據(jù)查找和更新的效率。

1 云存儲環(huán)境下的數(shù)據(jù)完整性證明

1.1 數(shù)據(jù)存儲模型

云存儲環(huán)境下的體系架構(gòu)一般基于2種基礎(chǔ)模型，分別為兩方模型和三方模型。三方模型即引入了可信第三方審計(Third Party Auditor， TPA)，具有更多的審計經(jīng)驗和能力，替代用戶對云存儲中的數(shù)據(jù)執(zhí)行審計任務(wù)，也減輕了在驗證階段用戶所需要的計算負(fù)擔(dān)。其結(jié)構(gòu)關(guān)系如圖1所示。

在三方模型中，由于接入云中的設(shè)備受到計算資源的限制，用戶不可能將大量的時間和精力花費在對云數(shù)據(jù)的完整性檢測上，往往將其交付給經(jīng)驗豐富的第三方來完成。因此，驗證方只需要擁有少量的公開信息即可完成完整性驗證。而在兩方模型中，沒有第三方審計，只有云存儲用戶和云服務(wù)提供商，用戶本身就具有三方模型中的審計功能。由于在這2種存儲模型中，三方模型的自身優(yōu)勢更符合云存儲的特性，所以本文中對云存儲環(huán)境下的數(shù)據(jù)完整性研究，都是基于三方模型展開。

圖1 云環(huán)境下存儲模型

1.2 構(gòu)建框架

數(shù)據(jù)完整性證明機制由Setup和Challege這2個階段構(gòu)成，通過隨機數(shù)據(jù)抽樣的方式對云存儲中數(shù)據(jù)進(jìn)行完整性驗證。具體實現(xiàn)由如下4個多項式時間算法組成：

1)keyGen(1k)→(pk,sk)。密鑰對生成算法，由用戶來執(zhí)行。算法以安全參數(shù)k作為輸入，輸出密鑰對(pk,sk)作為返回值。

2)TagBlock(sk,f)→η。數(shù)據(jù)塊標(biāo)簽生成算法，由用戶來執(zhí)行。算法以私鑰和文件f作為輸入，將每個文件生成的標(biāo)簽集合η輸出作為認(rèn)證的元數(shù)據(jù)。

3)GenProof(pk,f,η,chal)→ρ。證據(jù)生成算法，該算法在服務(wù)器上運行。將用戶公鑰pk、文件f、認(rèn)證的標(biāo)簽集合η以及用戶的挑戰(zhàn)請求chal作為輸入，生成這次請求的驗證證據(jù)ρ返回。

4)CheckProof(pk,ρ,chal)→(″true″,″false″)。證據(jù)驗證算法，由可信第三方TPA執(zhí)行。該算法將用戶的公鑰pk、服務(wù)器生成的證據(jù)ρ以及用戶挑戰(zhàn)請求chal作為輸入?yún)?shù)返回驗證成功或者失敗。

上述算法在數(shù)據(jù)完整性證明機制具體實施過程中可以分為2個階段:Setup階段和Challege階段。

1)Setup階段：初始化階段。用戶首先運行keyGen(·)算法生成密鑰對(pk,sk)；然后對文件f分塊，執(zhí)行TagBlock(·)算法為每個數(shù)據(jù)塊fi生成標(biāo)簽集合η={ηf1,ηf2,…,ηfn}；最后將數(shù)據(jù)文件f和標(biāo)簽集合η發(fā)送給云服務(wù)器，刪除本地{f,η}。

2)Challege階段：用戶挑戰(zhàn)請求階段?？尚诺谌阶鳛門PA向云服務(wù)器周期性地發(fā)起完整性驗證。從文件f中隨機選取c個數(shù)據(jù)塊{f1,f2,…,fc}生成挑戰(zhàn)請求chal發(fā)送給云服務(wù)器。

服務(wù)器作為證明者，通過存儲在服務(wù)器上的{f,η}，執(zhí)行GenProof(·)生成驗證證據(jù)ρ返回給驗證者,TPA作為驗證者收到證據(jù)后，執(zhí)行CheckProof(·)驗證證據(jù)是否正確。

2 基于SBT全結(jié)點存儲的數(shù)據(jù)完整性方法

2.1 結(jié)點大小平衡樹——SBT

2.1.1 SBT的結(jié)構(gòu)

SBT本身也是一棵二叉排序樹,其性質(zhì)如下：

1)若左子樹非空，則左子樹上的所有結(jié)點關(guān)鍵字值均小于根結(jié)點的關(guān)鍵字值。

2)若右子樹非空，則右子樹上的所有結(jié)點關(guān)鍵字值均大于根結(jié)點的關(guān)鍵字值。

3)左、右子樹本身也分別是一顆二叉排序樹。

其又具備了平衡二叉樹的特點。為了避免樹的高度增長過快，降低二叉排序樹的性能，規(guī)定在插入和刪除操作時，保證任意結(jié)點的左、右子樹高度差絕對值不超過1。它的優(yōu)點是可以高效動態(tài)地維護(hù)二叉排序樹的高度，如果樹中出現(xiàn)結(jié)點不平衡的情況，需要進(jìn)行左旋或右旋操作來保持平衡，并且旋轉(zhuǎn)操作不需要額外的存儲空間。

SBT中的平衡性是通過其定義的結(jié)點大小，即以該結(jié)點為根的結(jié)點的個數(shù)之間的關(guān)系來維持的。其結(jié)構(gòu)如圖2所示。

圖2 SBT結(jié)構(gòu)圖

SBT樹中的每一個結(jié)點應(yīng)滿足如下性質(zhì)：

1)s[left[A]]≥s[right[right[A]]],s[right[left[A]]]

2)s[right[A]]≥s[left[left[A]]],s[left[right[A]]]

其中s[A]指的是以結(jié)點A為根的子結(jié)點的個數(shù)，left[A]指的是A的左孩子，right[A]指的是A的右孩子。在圖2中該性質(zhì)體現(xiàn)為：

s[L]≥s[D],s[E]& s[R]≥s[B],s[C]

如果在SBT上進(jìn)行刪除或者插入操作后，可能導(dǎo)致SBT上結(jié)點不滿足上述性質(zhì)，則需要執(zhí)行Maintain()函數(shù)以調(diào)整樹的高度來維持樹的平衡。

以圖2中SBT為例，假如出現(xiàn)s[B]>s[R]的情況，則需要通過以下步驟對其進(jìn)行修復(fù)：

1)首先對根結(jié)點A進(jìn)行右旋轉(zhuǎn)Right-Rotate(A)操作，使得SBT由圖2轉(zhuǎn)化為圖3。

2)右旋操作后可能還會出現(xiàn)s[D]>s[C]或者s[E]>s[C],同樣不滿足上述性質(zhì)，所以還需要對A執(zhí)行Maintain()操作；

3)圖3中L的右子樹可能由于步驟2中的不斷調(diào)整出現(xiàn)不滿足性質(zhì)的情況，因此最后還需要對L執(zhí)行Maintain()操作。

圖3 右旋A后結(jié)構(gòu)圖

2.2 數(shù)據(jù)結(jié)構(gòu)可認(rèn)證化

基于SBT結(jié)構(gòu)構(gòu)建起來的全結(jié)點存儲樹A中每個結(jié)點都存儲著如下3個字段：

1)該結(jié)點中存儲的數(shù)據(jù)Dv4。

2)該結(jié)點數(shù)據(jù)的摘要值Hv=h(Dv4)。

3)該結(jié)點上的聯(lián)合摘要值Hsum(v)：如果該結(jié)點為底層葉結(jié)點，則Hsum=Hv；若該結(jié)點中只存在右孩子結(jié)點，則Hsum=h(Hv,Hsum(v.getLeft))；如果該結(jié)點只存在左孩子結(jié)點，則Hsum=h(Hv,Hsum(v.getRight))；如果該結(jié)點左孩子和右孩子結(jié)點都存在，則Hsum=h(Hv,Hsum(v.getLeft),Hsum(v.getRight))。

圖4 可認(rèn)證的SBT結(jié)構(gòu)示意圖

云存儲環(huán)境中某個數(shù)據(jù)集的哈希摘要值為Digest(A)，即在驗證過程中用來進(jìn)行對比的摘要值，就是該結(jié)點大小平衡樹的聯(lián)合摘要值。一個可認(rèn)證的結(jié)點大小平衡樹結(jié)構(gòu)示意圖見圖4

2.3 驗證過程

當(dāng)用戶發(fā)送一個檢測數(shù)據(jù)請求到云服務(wù)器時，假如服務(wù)器在全結(jié)點存儲樹中找到存儲著目標(biāo)數(shù)據(jù)對應(yīng)的目標(biāo)結(jié)點target時，并且服務(wù)器會記錄root到target的查找路徑path={v0(target)→v1→…→vl-1→vl(root)}。此時，服務(wù)器還會給審計第三方TPA返回Yes并返回相應(yīng)的證據(jù)ρ={η,λ1,λ2，…,λl}。其中η的定義如下：

1)如果v0是葉子結(jié)點，則η={Dv0}。

2)如果v0不是葉子結(jié)點，則η={Dv0,Hsum(v0.getLeft),Hsum(v0.getRight)}。

λ的定義如下：

1)如果vi-1為左孩子結(jié)點，則λi={Hvi,Hsum(vi-1),Hsum(vi.getRight)}。

2)如果vi-1為右孩子結(jié)點，則λi={Hvi,Hsum(vi.getLeft),Hsum(vi-1)}。

以圖4所示的可認(rèn)證的SBT為例，如果需要驗證的數(shù)據(jù)塊為Dv4,則證據(jù)ρ生成信息示例如圖5所示。

圖5 證據(jù)ρ生成示意圖

當(dāng)可信第三方TPA收到云服務(wù)器返回的證據(jù)ρ時，將進(jìn)行如下驗證過程：

1)計算目標(biāo)結(jié)點v0的摘要值，即a=h(Dv0)，如果v0是葉子結(jié)點，則驗證a=Hsum(Dv0)是否成立；否則，驗證h(a,Hsum(v0.getLeft),Hsum(v0.getRight))=Hsum(v0)是否成立。

2)對于路徑中的某個結(jié)點vi，即λi(i

3)對于根結(jié)點vl，即λl，同理如果vi-1為根的左孩子結(jié)點則計算h(Hvl,Hsum(vl-1),Hsum(vl.getRight))；否則計算h(Hvl,Hsum(vl-1),Hsum(vl.getLeft))；并與用戶之前發(fā)送給TPA的數(shù)據(jù)摘要值Digest(A)作比較。

圖6 完整性驗證過程示意圖

如果上述驗證過程全部成立，則證明云服務(wù)器返回的證據(jù)ρ是正確的，即所查詢的數(shù)據(jù)是完整的；否則，用戶就會認(rèn)為該數(shù)據(jù)已被修改或者偽造，此時就需要采取數(shù)據(jù)恢復(fù)技術(shù)對云存儲中的數(shù)據(jù)進(jìn)行恢復(fù)操作。

以圖5結(jié)構(gòu)為例，其數(shù)據(jù)完整性驗證過程如圖6所示。

3 結(jié)果分析

通過上述分析，可得到如下結(jié)論：

1)對于查詢驗證操作，SBT認(rèn)證及Merkle-Tree認(rèn)證算法的時間復(fù)雜度在同一數(shù)量級，均為O(logn)。而與RSA樹認(rèn)證相對比，這2種認(rèn)證方案都使用了哈希函數(shù)替代復(fù)雜的模冪運算，因此計算上更加簡單。

2)在支持動態(tài)數(shù)據(jù)集方面，Merkle-Tree認(rèn)證采用2-3樹支持動態(tài)數(shù)據(jù)集，而RSA樹認(rèn)證是將成員哈希分組為固定大小的Bucket來支持動態(tài)數(shù)據(jù)集。因此這2種方式都不可避免地導(dǎo)致了認(rèn)證結(jié)構(gòu)的周期性重構(gòu)。

3)SBT結(jié)構(gòu)具有良好的自平衡性，能夠有效地控制樹高，使其趨近于完全二叉樹。二叉樹上的查詢和更新操作時間復(fù)雜度都和樹高有關(guān)，相對于非平衡樹而言，SBT結(jié)構(gòu)在數(shù)據(jù)操作效率上大大提高，將時間復(fù)雜度維持在O(logn)。此外，SBT認(rèn)證也可以完全避免認(rèn)證結(jié)構(gòu)周期性重構(gòu)。針對上述方案在插入操作中的重構(gòu)分析，分別對SBT、Merkle-Tree、RSA樹插入100萬、200萬、500萬、1000萬以及2000萬個隨機值，重構(gòu)時間統(tǒng)計如圖7所示。

圖7 重構(gòu)時間統(tǒng)計圖

因此，對于大規(guī)模并且需頻繁更新的數(shù)據(jù)集，該方案具有明顯的優(yōu)勢。為了驗證該樹形結(jié)構(gòu)更適合構(gòu)建數(shù)據(jù)認(rèn)證，下面通過實驗將SBT與AVL樹、Treap進(jìn)行比較，評估基于SBT全結(jié)點存儲云數(shù)據(jù)完整性驗證方案中查詢和更新的時間復(fù)雜度。

3.1 數(shù)據(jù)更新操作分析

圖8 插入操作時間統(tǒng)計圖

針對基于SBT上插入操作分析，在SBT、AVL和Treap結(jié)構(gòu)中分別插入100萬、500萬、1000萬、2000萬以及5000萬個隨機值，時間統(tǒng)計見圖8。

圖9 刪除操作時間統(tǒng)計圖

針對基于SBT上刪除操作分析，在具有100萬、500萬、1000萬、2000萬以及5000萬個隨機值的SBT、AVL和Treap結(jié)構(gòu)中，分別刪除100萬個值所用時間，刪除操作時間統(tǒng)計如圖9所示。

3.2 驗證過程分析

針對基于結(jié)點大小二叉樹上的查詢驗證操作的時間分析，在具有100萬、500萬、1000萬、2000萬以及5000萬個隨機值的SBT、AVL和Treap結(jié)構(gòu)中分別查詢100萬個目標(biāo)值運行結(jié)果時間統(tǒng)計如圖10所示。

圖10 查詢驗證操作平均時間統(tǒng)計圖

對于用戶向云服務(wù)器發(fā)送驗證請求時，服務(wù)器在生成證據(jù)信息過程中，沒必要進(jìn)行數(shù)據(jù)摘要值的重新計算，只需要在認(rèn)證化的SBT中找到相應(yīng)的數(shù)據(jù)結(jié)點，并把根結(jié)點到該目標(biāo)結(jié)點路徑上的結(jié)點摘要值及其子結(jié)點和兄弟結(jié)點作為返回值，返回的摘要值的個數(shù)與SBT的高度之間呈線性關(guān)系?？尚诺谌絋PA在對返回的證據(jù)進(jìn)行驗證時，僅需進(jìn)行O(logn)次哈希計算即可。

3.3 安全性分析

基于SBT認(rèn)證的安全性與基于Merkle-Tree的認(rèn)證相同，其安全性保證都是以其哈希函數(shù)的抗碰撞性為基礎(chǔ)實現(xiàn)。

4 結(jié)束語

目前，云計算的優(yōu)勢使得越來越多的企業(yè)和個人更愿意將數(shù)據(jù)交付到平臺處理，這給云存儲的普及帶來了非常可觀的發(fā)展前景，然而數(shù)據(jù)本身的不確定性以及云服務(wù)器的不完全可信又使得云存儲下的數(shù)據(jù)安全難以得到保障。針對數(shù)據(jù)完整性驗證問題，本文提出了一種基于SBT全結(jié)點存儲的數(shù)據(jù)完整性驗證方案，并詳細(xì)地介紹了云存儲下完整性驗證框架和基于結(jié)點大小平衡樹全結(jié)點存儲的數(shù)據(jù)驗證過程。全結(jié)點存儲相比葉結(jié)點存儲無疑減少了服務(wù)器上的存儲開銷，也降低了樹的高度，再者SBT本身具有二叉排序樹和二叉平衡樹的結(jié)構(gòu)特性，不僅使得數(shù)據(jù)查找時非常高效，同時又很好地維持了樹的高度，也保證了數(shù)據(jù)更新操作時的效率。

參考文獻(xiàn)：

[1] Deswarte Y, Quisquater J J, Sa?dane A. Remote integrity checking[M]// IFIP International Federation for Information Processing. Springer, 2004,140.

[2] Dan B, Lynn B, Shacham H. Shortsignatures from the weil pairing[M]// Advances in Cryptology—ASIACRYPT 2001. Springer Berlin Heidelberg, 2001:514-532.

[3] Ateniese G, Pietro R D, Mancini L V, et al. Scalable and efficient provable data possession[C]// Proceedings of the 4th International Conference on Security and Privacy in Communication Netowrks. ACM, 2008:1-10.

[4] Erway C, Papamanthou C, Tamassia R. Dynamic provable data possession[C]// ACM Conference on Computer and Communications Security. 2009:213-222.

[5] Merkle R C. A certified digital signature[J]. Lecture Notes in Computer Science, 1990,435:218-238.

[6] Merkle R C. Protocols for public key cryptosystems[C]// Proceedings of IEEE Symposium on Security and Privacy. 1980,3:122.

[7] 任化強. 云環(huán)境下操作外包的動態(tài)審計方案設(shè)計與實現(xiàn)[D]. 成都:電子科技大學(xué), 2016.

[8] 鄧曉鵬,馬自堂,高敏霞,等. 一種基于雙線性對的云數(shù)據(jù)完整性驗證算法[J]. 計算機應(yīng)用研究, 2013,30(7):2124-2127.

[9] 李瑩,張永勝,馬潔. 一種基于H-MHT的動態(tài)數(shù)據(jù)完整性檢查方案[J]. 計算機應(yīng)用研究, 2015,32(12):3710-3713.

[10] 張亮. 云存儲數(shù)據(jù)完整性檢測技術(shù)研究[D]. 大連:大連理工大學(xué), 2014.

[11] 譚霜,賈焰,韓偉紅. 云存儲中的數(shù)據(jù)完整性證明研究及進(jìn)展[J]. 計算機學(xué)報, 2015,38(1):164-177.

[12] 秦志光,王士雨,趙洋,等. 云存儲服務(wù)的動態(tài)數(shù)據(jù)完整性審計方案[J]. 計算機研究與發(fā)展, 2015,52(10):2192-2199.

[13] 姚戈. 云存儲數(shù)據(jù)完整性驗證機制研究[D]. 北京:北京交通大學(xué), 2016.

[14] 趙宇龍. 云存儲中第三方審計機構(gòu)在數(shù)據(jù)完整性驗證中的應(yīng)用[D]. 成都:電子科技大學(xué), 2015.

[15] 杜朝暉,王建璽. 云存儲中利用TPA的數(shù)據(jù)隱私保護(hù)公共審計方案[J]. 電子技術(shù)應(yīng)用, 2015,41(5):123-125.

[16] 邢建川,韓帥. 一種基于哈希樹的數(shù)據(jù)動態(tài)操作可驗證性方法: 中國, CN103218574A[P]. 2013-07-24.

[17] Motghare S, Khandait S P, Mohod P S. Framework of data integrity for cross cloud environment using CPDP scheme[J]. International Journal of Advanced Research in Computer Science, 2013,4(2):55.

[18] Papamanthou C, Tamassia R, Triandopoulos N. Authenticated hash tables based on cryptographic accumulators[J]. Algorithmica, 2016,74(2):664-712.

[19] Rao S, Gujrathi S, Sanghvi M, et al. Analysis on data integrity in cloud environment[J]. IOSR Journal of Computer Engineering, 2014,16:71-76.