基于動(dòng)態(tài)布隆過濾器的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法

謝 麗 霞， 胡 立 杰

( 中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 天津 300300 )

0 引 言

大數(shù)據(jù)時(shí)代，作為云計(jì)算的基礎(chǔ)，云存儲(chǔ)發(fā)展迅猛．但是，日益嚴(yán)重的安全問題已經(jīng)制約了云存儲(chǔ)健康發(fā)展[1-2]．其中，云存儲(chǔ)數(shù)據(jù)的完整性是不可忽略的一個(gè)重要問題．例如：外部攻擊或云服務(wù)提供商內(nèi)部人員惡意操作導(dǎo)致數(shù)據(jù)完整性遭到破壞；云服務(wù)提供商為維護(hù)自身名譽(yù)，隱瞞數(shù)據(jù)丟失或損壞．因此，研究一種可公開驗(yàn)證的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法是很有必要的[3]．

為保護(hù)云存儲(chǔ)數(shù)據(jù)的完整性，國(guó)內(nèi)外研究者們提出了多種數(shù)據(jù)持有性驗(yàn)證方案．Ateniese等[4]提出一種數(shù)據(jù)持有性證明(provable data possession，PDP)方案，該方案雖然可降低通信開銷，但是僅適用于靜態(tài)數(shù)據(jù)的驗(yàn)證，并未考慮動(dòng)態(tài)數(shù)據(jù)的更新問題．Wang等[5]提出一種基于同態(tài)加密短消息簽名的動(dòng)態(tài)數(shù)據(jù)完整性驗(yàn)證方法，該方法支持公開驗(yàn)證和動(dòng)態(tài)數(shù)據(jù)操作，但當(dāng)校驗(yàn)元數(shù)據(jù)規(guī)模變大后插入操作的開銷將十分巨大．Li等[6]提出一種基于雙線性組的完整性驗(yàn)證方法，基于Hellman計(jì)算困難問題[7]構(gòu)造雙線性映射用于校驗(yàn)元數(shù)據(jù)計(jì)算，降低客戶端執(zhí)行驗(yàn)證協(xié)議初始化階段的成本，但是由于驗(yàn)證過程使用的結(jié)構(gòu)復(fù)雜導(dǎo)致驗(yàn)證效率降低．Hussien等[8]使用雙塊傳輸和加密散列函數(shù)的方式驗(yàn)證云存儲(chǔ)數(shù)據(jù)的完整性，可減少客戶端計(jì)算量，但是卻導(dǎo)致輔助存儲(chǔ)空間增大，隱私泄露的風(fēng)險(xiǎn)提高．Zhang等[9]使用rb2-3樹作為驗(yàn)證工具實(shí)現(xiàn)數(shù)據(jù)公開驗(yàn)證和動(dòng)態(tài)數(shù)據(jù)完整性驗(yàn)證，但該方法仍存在計(jì)算復(fù)雜、驗(yàn)證路徑過長(zhǎng)的問題．李勇等[10]和Zhang等[11]使用樹狀驗(yàn)證路徑來確定數(shù)據(jù)塊位置的正確性，減少各實(shí)體間的計(jì)算負(fù)擔(dān)，簡(jiǎn)化動(dòng)態(tài)更新過程，但是在云端計(jì)算持有證據(jù)時(shí)需要更多的輔助信息，導(dǎo)致云端與驗(yàn)證端的通信開銷增加．

針對(duì)上述方法存在持有性證明計(jì)算復(fù)雜且驗(yàn)證過程需要大量輔助存儲(chǔ)空間的不足，本文提出一種基于動(dòng)態(tài)布隆過濾器(dynamic Bloom filter，DBF)的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法．該方法使用同態(tài)哈希函數(shù)處理驗(yàn)證數(shù)據(jù)并生成用于驗(yàn)證的校驗(yàn)元，基于數(shù)據(jù)塊標(biāo)簽構(gòu)造動(dòng)態(tài)布隆過濾器且支持動(dòng)態(tài)操作，以實(shí)現(xiàn)對(duì)云存儲(chǔ)數(shù)據(jù)持有性的高效驗(yàn)證．

1 動(dòng)態(tài)布隆過濾器

1.1 BTBF結(jié)構(gòu)

本文提出的DBF為B-Tree狀的布隆過濾器，即B-Tree布隆過濾器(B-Tree Bloom filter，BTBF)．BTBF不會(huì)因數(shù)據(jù)大規(guī)模增長(zhǎng)而線性退化且有較高的查找效率，與現(xiàn)有云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法相比，同樣樹高的BTBF可存儲(chǔ)更多校驗(yàn)元．

BTBF每個(gè)節(jié)點(diǎn)包含i個(gè)BF，除根節(jié)點(diǎn)外，BTBF每個(gè)節(jié)點(diǎn)可存儲(chǔ)多個(gè)關(guān)鍵字，一個(gè)4階BTBF如圖1所示．

圖1 BTBF結(jié)構(gòu)Fig.1 BTBF structure

本文提出的BTBF需滿足以下7個(gè)條件：

(1) BTBF中節(jié)點(diǎn)的關(guān)鍵字由數(shù)據(jù)塊標(biāo)簽、對(duì)應(yīng)的驗(yàn)證簽名構(gòu)成，其中驗(yàn)證簽名包括數(shù)據(jù)塊簽名和驗(yàn)證計(jì)數(shù)位；

(2) BTBF中節(jié)點(diǎn)按數(shù)據(jù)塊標(biāo)簽從大到小排列；

(3) 任意非葉子節(jié)點(diǎn)最多只有M個(gè)子節(jié)點(diǎn)，且M>2，其中M為BTBF容度；

(4) 根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)為[2，M]；

(5) 根節(jié)點(diǎn)外的非葉子節(jié)點(diǎn)數(shù)為[M/2，M]；

(6) 每個(gè)節(jié)點(diǎn)存放至少

M/2-1

個(gè)和至多M-1個(gè)布隆過濾器；

(7) 非葉子節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量比對(duì)應(yīng)子節(jié)點(diǎn)少1．

1.2 BTBF的錯(cuò)誤率

本文提出的BTBF在云存儲(chǔ)數(shù)據(jù)持有性證明中錯(cuò)誤率為固定值．傳統(tǒng)布隆過濾器存在錯(cuò)誤率和飽和度的問題[12]，由于難以預(yù)知集合中的元素?cái)?shù)量，隨著插入元素的增多飽和度會(huì)增加，錯(cuò)誤率也將隨之提高并最終導(dǎo)致布隆過濾器不可用．BTBF錯(cuò)誤率P可由特征值數(shù)量n、數(shù)位組長(zhǎng)度m和選擇哈希函數(shù)的數(shù)量k決定，P與各參數(shù)之間的關(guān)系為

(1)

云存儲(chǔ)數(shù)據(jù)持有性證明中因?yàn)閿?shù)據(jù)分塊大小固定，因此通過選擇適當(dāng)?shù)膍、n和k，可保證BTBF 錯(cuò)誤率變?yōu)橐粋€(gè)可控的固定值，避免錯(cuò)誤率升高．

2 云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法

2.1 驗(yàn)證模型

傳統(tǒng)的完整性驗(yàn)證模型不支持公開驗(yàn)證且需要在客戶端存儲(chǔ)大量數(shù)據(jù)[13]，因此本文在傳統(tǒng)云存儲(chǔ)驗(yàn)證模型的基礎(chǔ)上引入第三方驗(yàn)證平臺(tái)，云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證模型結(jié)構(gòu)如圖2所示．

圖2 云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證模型Fig.2 Cloud storage data integrity verification model

第三方數(shù)據(jù)完整性驗(yàn)證模型包含客戶端(Client Server，CS)、云服務(wù)提供商(Cloud Server Provider，CSP)和第三方驗(yàn)證平臺(tái)(Third Party Verification，TPV)，CS將數(shù)據(jù)加密上傳并生成校驗(yàn)證據(jù)，CSP存儲(chǔ)數(shù)據(jù)和生成數(shù)據(jù)持有證據(jù)應(yīng)答，TPV存儲(chǔ)校驗(yàn)證據(jù)和進(jìn)行數(shù)據(jù)完整性驗(yàn)證．

2.2 方法具體實(shí)現(xiàn)

基于DBF的云存儲(chǔ)數(shù)據(jù)持有性證明方法包括3個(gè)階段：初始化階段、挑戰(zhàn)階段和應(yīng)答階段．3個(gè)階段的具體設(shè)計(jì)如下：

(1)初始化階段

首先，CS對(duì)存儲(chǔ)數(shù)據(jù)進(jìn)行預(yù)處理，然后，將數(shù)據(jù)和校驗(yàn)證據(jù)分別上傳給CSP和TPV，過程設(shè)計(jì)如下：

(a)CS將數(shù)據(jù)F分割為大小固定的數(shù)據(jù)塊m1，m2，…，mv，對(duì)數(shù)據(jù)塊mi(i=1，2，…，v)進(jìn)行預(yù)處理，生成對(duì)應(yīng)數(shù)據(jù)塊的特征值向量Ai=(ai1

ai2…aiv)(i=1，2，…，v)，通過k個(gè)同態(tài)哈希函數(shù)生成數(shù)據(jù)塊驗(yàn)證簽名bfi(bfi為BF生成的數(shù)位組，i=1，2，…，v)，然后將數(shù)據(jù)塊m1，m2，…，mv和請(qǐng)求CREAT={(num1：bf1)，(num2：bf2)，…，(numv：bfv)}分別上傳到CSP和TPV，上傳結(jié)束對(duì)數(shù)據(jù)進(jìn)行一次完整性校驗(yàn)，校驗(yàn)成功后CS將刪除本地存放的數(shù)據(jù)．

(b)CSP存儲(chǔ)CS上傳的數(shù)據(jù)塊m1，m2，…，mv，TPV接受CREAT請(qǐng)求后存儲(chǔ)數(shù)據(jù)塊驗(yàn)證簽名集bf1，bf2，…，bfv，初始化驗(yàn)證計(jì)數(shù)位并生成BTBF，要求BTBF容度M≥4．BTBF的關(guān)鍵字由數(shù)據(jù)塊驗(yàn)證簽名bfi和數(shù)據(jù)塊標(biāo)簽numi組成．

(2)挑戰(zhàn)階段

初始化完成后，CS可發(fā)起挑戰(zhàn)請(qǐng)求CHL，TPV生成驗(yàn)證請(qǐng)求TPV_CHL．過程設(shè)計(jì)如下：

CS發(fā)起挑戰(zhàn)請(qǐng)求CHL，TPV接受請(qǐng)求后在BTBF驗(yàn)證樹中隨機(jī)選擇一條或多條驗(yàn)證路徑S=(num1num2…nums)，其中numi(i=1，2，…，s)為數(shù)據(jù)塊標(biāo)簽，數(shù)據(jù)驗(yàn)證率c≥80%，即驗(yàn)證塊數(shù)量需大于數(shù)據(jù)塊總數(shù)的80%．TPV將生成的隨機(jī)路徑S封裝為驗(yàn)證請(qǐng)求TPV_CHL={S1,S2,…,Ss}發(fā)送給CSP，要求CSP提供驗(yàn)證請(qǐng)求中包含數(shù)據(jù)塊的持有證據(jù)．

(3)應(yīng)答階段

CSP在接受驗(yàn)證請(qǐng)求后，根據(jù)TPV_CHL生成對(duì)應(yīng)數(shù)據(jù)塊持有證據(jù)交由TPV進(jìn)行持有性驗(yàn)證，過程設(shè)計(jì)如下：

CSP接受TPV_CHL請(qǐng)求后，根據(jù)請(qǐng)求中包含的數(shù)據(jù)塊標(biāo)簽numi查找對(duì)應(yīng)的數(shù)據(jù)塊mi，生成校驗(yàn)元向量Ai=(ai1ai2…aiv)(i=1，2…，v)，通過k個(gè)同態(tài)哈希函數(shù)生成長(zhǎng)度為s的數(shù)據(jù)持有證據(jù)cfi，生成應(yīng)答R=(cf1cf2…cfs)并反饋給TPV，TPV計(jì)算校驗(yàn)結(jié)果α：

(2)

其中s為隨機(jī)驗(yàn)證路徑長(zhǎng)度．若α=0，則云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證成功，TPV向CS返回結(jié)果“TRUE”，否則驗(yàn)證失敗，返回結(jié)果“FALSE”，BTBF節(jié)點(diǎn)參與驗(yàn)證后需對(duì)該節(jié)點(diǎn)的校驗(yàn)計(jì)數(shù)位bc進(jìn)行自增操作．

2.3 數(shù)據(jù)動(dòng)態(tài)操作

基于DBF的數(shù)據(jù)持有性驗(yàn)證方法可支持包括更新、插入和刪除的數(shù)據(jù)操作．

2.3.1 數(shù)據(jù)更新算法 當(dāng)用戶更新數(shù)據(jù)塊mi(i=1，2，…，v)時(shí)，BTBF云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法的處理過程設(shè)計(jì)如下：

(a)CS計(jì)算更新數(shù)據(jù)塊mi的標(biāo)簽值numi和簽名bfi，分別向云存儲(chǔ)服務(wù)器和TPV發(fā)送更新請(qǐng)求Update_C={numi：mi}和Update_T={numi：bfi}．

(b)云存儲(chǔ)服務(wù)器接收更新請(qǐng)求Update_C={numi：mi}后，根據(jù)標(biāo)簽值numi尋找存儲(chǔ)在云端的數(shù)據(jù)塊，用mi替換原有數(shù)據(jù)塊m′i．

(c)TPV接收更新請(qǐng)求Update_T={numi：bfi}后，根據(jù)numi在BTBF中查找對(duì)應(yīng)的校驗(yàn)數(shù)位組并替換為bfi，并將節(jié)點(diǎn)驗(yàn)證計(jì)數(shù)位bci初始化為0．

(d)當(dāng)云存儲(chǔ)服務(wù)器和TPV進(jìn)行更新操作后，CS對(duì)云存儲(chǔ)服務(wù)器進(jìn)行一次數(shù)據(jù)完整性校驗(yàn)，校驗(yàn)成功后CS刪除本地存儲(chǔ)的mi．

(a)CS計(jì)算插入數(shù)據(jù)塊mi的標(biāo)簽值numi以及簽名bfi，分別向云存儲(chǔ)服務(wù)器和TPV發(fā)送插入請(qǐng)求Insert_C={numi：mi}和Insert_T={numi：bfi}．

(b)CSP接收請(qǐng)求Insert_C={numi：mi}后，存儲(chǔ)接收的數(shù)據(jù)塊mi．

(c)TPV接收插入請(qǐng)求Insert_T={numi：bfi}后，首先在BTBF中根據(jù)numi查找數(shù)據(jù)塊簽名bfi的插入位置，然后將bfi插入到節(jié)點(diǎn)中．插入完成后需對(duì)插入的節(jié)點(diǎn)進(jìn)行判斷，若該節(jié)點(diǎn)存放的數(shù)據(jù)塊簽名數(shù)量大于M，則需分裂該節(jié)點(diǎn)并對(duì)BTBF進(jìn)行調(diào)整，保證在完成插入操作后仍能滿足BTBF的7個(gè)條件．

(d)當(dāng)CSP和TPV全部進(jìn)行插入操作后，CS對(duì)云存儲(chǔ)服務(wù)器進(jìn)行一次數(shù)據(jù)完整性校驗(yàn)，校驗(yàn)成功后CS刪除本地存儲(chǔ)的mi．

2.3.3 數(shù)據(jù)刪除算法 當(dāng)用戶刪除數(shù)據(jù)塊mi(i=1，2，…，v)時(shí)，BTBF云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法的處理過程設(shè)計(jì)如下：

(a)CS查找刪除數(shù)據(jù)的標(biāo)簽值numi，分別向云存儲(chǔ)服務(wù)器和TPV發(fā)送刪除請(qǐng)求Delete_C={numi}和Delete_T={numi}．

由于進(jìn)化的觀念所強(qiáng)調(diào)的時(shí)代性和進(jìn)步性，“國(guó)故”終究只是過去式，無法真正從“古”來到“今”。胡適說文言文是“死文字”，決不能做出有生命有價(jià)值的現(xiàn)代文學(xué)。他主張“歷史的真理論”，認(rèn)為真理的價(jià)值只是“擺過渡，做過媒”，可以隨時(shí)換掉、趕走。這樣的“國(guó)故”即使被“整理”出來龍去脈，其價(jià)值最終也極易被“評(píng)判”為陳設(shè)在博物館的、沒有生命的展品。時(shí)間之流終究被“評(píng)判”之利刀斬?cái)酁楣沤竦膱?jiān)硬對(duì)峙，已“死”的過去走不進(jìn)現(xiàn)在和將來的生命。所以，“評(píng)判的態(tài)度”不僅要求人們認(rèn)清古今變易的大勢(shì)所趨，更要做“反對(duì)調(diào)和”的“革新家”，將目光聚焦于現(xiàn)在與未來。在胡適看來，生乎今之世而反古之道，是有違進(jìn)化之跡的背時(shí)逆流。

(b)云存儲(chǔ)服務(wù)器接收Delete_C={numi}后，根據(jù)數(shù)據(jù)塊標(biāo)簽numi查找數(shù)據(jù)塊并刪除．

(c)TPV接收Delete_T={numi}后，在BTBF 中查找數(shù)據(jù)塊標(biāo)簽為numi的節(jié)點(diǎn)并刪除該節(jié)點(diǎn)中對(duì)應(yīng)的關(guān)鍵字．節(jié)點(diǎn)在數(shù)據(jù)塊刪除后，需要判斷該節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)量是否滿足每個(gè)節(jié)點(diǎn)至少存放和至多M-1的條件．如果該節(jié)點(diǎn)不滿足，BTBF樹需要對(duì)該節(jié)點(diǎn)和鄰近節(jié)點(diǎn)進(jìn)行合并，使得樹仍滿足BTBF條件．

M/2-1

(d)當(dāng)CSP和TPV分別進(jìn)行刪除操作后，CS對(duì)云存儲(chǔ)服務(wù)器進(jìn)行一次數(shù)據(jù)完整性校驗(yàn)，校驗(yàn)成功后CS刪除操作完成．

本文提出的基于DBF的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法的動(dòng)態(tài)操作與傳統(tǒng)方法相比具有以下特點(diǎn)：

(1)更新操作不只在葉子節(jié)點(diǎn)處進(jìn)行，BTBF樹的內(nèi)部均可進(jìn)行更新操作，優(yōu)化存儲(chǔ)空間．

(2)刪除操作只針對(duì)刪除節(jié)點(diǎn)，不需對(duì)其他節(jié)點(diǎn)進(jìn)行更新操作，減少刪除造成的冗余計(jì)算．

(3)與常用的默克爾哈希樹相比，BTBF的插入操作優(yōu)化驗(yàn)證樹的高度，避免大量執(zhí)行插入操作后驗(yàn)證樹退化為線性結(jié)構(gòu)，提高數(shù)據(jù)完整性驗(yàn)證效率．

3 驗(yàn)證的安全性分析

對(duì)基于DBF的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法分別從驗(yàn)證正確性、數(shù)據(jù)保密性、持有證明不可偽造性和抗重放攻擊等幾方面進(jìn)行分析．

3.1 正確性分析

BTBF在云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證中存在由假陽性問題造成的錯(cuò)誤率，因此本文采用多個(gè)數(shù)位組構(gòu)成驗(yàn)證路徑的方式降低錯(cuò)誤率，使得驗(yàn)證的正確率達(dá)到100%，布隆過濾器的錯(cuò)誤率[14]如表1所示．

設(shè)BTBF高為h，容度為M，隨機(jī)驗(yàn)證路徑S的長(zhǎng)度為s，單個(gè)BTBF節(jié)點(diǎn)驗(yàn)證錯(cuò)誤率為f．則數(shù)據(jù)驗(yàn)證率c=sh/(Mh-1)，單條驗(yàn)證路徑錯(cuò)誤率Ps=fsh．驗(yàn)證過程中，當(dāng)sh≥3時(shí)，若f≤0.01，則Ps≤1×10-6．

表1 布隆過濾器錯(cuò)誤率Tab.1 Bloom filter′s error rate

在本文方法中，f設(shè)為≤0.01的固定值，同時(shí)設(shè)定c≥80%，則sh≥0.8(Mh-1)．為提高驗(yàn)證效率設(shè)定M≥4，此時(shí)得到sh≥3．因此本文提出的方法錯(cuò)誤率Ps≤1×10-6，趨近于0．

可見，本文方法使用BTBF驗(yàn)證正確率可達(dá)到100%．

3.2 保密性分析

第三方平臺(tái)通過兩種方式得到用戶有效數(shù)據(jù)：方式一為第三方平臺(tái)通過CS上傳的校驗(yàn)證據(jù)，方式二為CSP提供的持有證據(jù)．

首先，CS將數(shù)據(jù)文件F分為固定大小的數(shù)據(jù)塊m1，m2，…，mv，數(shù)據(jù)塊mi生成校驗(yàn)元向量Ai=(ai1ai2…aiv)(i=1，2，…，v)，通過k個(gè)哈希函數(shù)生成長(zhǎng)度為m的數(shù)據(jù)塊簽名bfi．由于Ai為mi的特征值并只含有部分原始數(shù)據(jù)，經(jīng)過k個(gè)哈希函數(shù)生成數(shù)位組后，為僅包含0和1的序列．由于哈希過程不可逆，攻擊方不能通過bfi逆向得到原始數(shù)據(jù)，因此可保證有效數(shù)據(jù)不被TPV獲得．

其次，CSP提供的持有性證明cfi同樣是經(jīng)過哈希函數(shù)處理后的數(shù)位組，這是個(gè)不可逆的過程，因此攻擊者無法通過持有性證明獲得有效數(shù)據(jù)．

所以，本文方法可防止數(shù)據(jù)隱私泄露，保證TPV不能得到客戶有效數(shù)據(jù)．

3.3 抗偽造攻擊和抗重放攻擊分析

首先，假設(shè)攻擊方偽造數(shù)據(jù)持有證據(jù)(Rp=(cf′1cf′2…cf′s))，其中，cf′i(i=1，2，…，s，s為驗(yàn)證路徑S長(zhǎng)度)為數(shù)據(jù)標(biāo)簽．其中對(duì)于BTBF單個(gè)節(jié)點(diǎn)關(guān)鍵字偽造成功的成功率Pl=1/2m，那么單條隨機(jī)驗(yàn)證路徑S的持有證據(jù)偽造的成功率為Ps：

(3)

當(dāng)攻擊方對(duì)多條隨機(jī)路徑發(fā)起聯(lián)合攻擊時(shí)，多條路徑的持有證據(jù)需同時(shí)通過TPV的持有驗(yàn)證，因此對(duì)于w條隨機(jī)路徑聯(lián)合攻擊成功概率Pc可通過Ps得到：

(4)

w條隨機(jī)路徑聯(lián)合攻擊的成功概率Pc會(huì)隨著s和w的增大而逐漸減小，由于m≥6，則Pc遠(yuǎn)小于0.015 6，可認(rèn)為攻擊方對(duì)多條路徑聯(lián)合攻擊的成功概率為0．因此，本文提出的方法，當(dāng)驗(yàn)證的數(shù)據(jù)規(guī)模越大時(shí)，抵抗偽造攻擊的能力越強(qiáng)．

本文的云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證方法為動(dòng)態(tài)驗(yàn)證方法，所以TPV存儲(chǔ)的校驗(yàn)數(shù)據(jù)會(huì)隨時(shí)間變化而變化．當(dāng)攻擊方在BTBF樹更新后進(jìn)行攻擊時(shí)，由于BTBF驗(yàn)證樹會(huì)因?yàn)楦虏僮靼l(fā)生改變，重放已有的持有證據(jù)并不能通過TPV的完整性驗(yàn)證；當(dāng)攻擊方在BTBF樹未更新時(shí)進(jìn)行重放攻擊，由于BTBF關(guān)鍵字中包括驗(yàn)證計(jì)數(shù)位，在驗(yàn)證計(jì)數(shù)位未完全消耗的情況下，每次驗(yàn)證時(shí)驗(yàn)證計(jì)數(shù)位不同，因此重放已有的持有證據(jù)，并不能通過TPV的完整性驗(yàn)證．當(dāng)在BTBF節(jié)點(diǎn)計(jì)數(shù)位未消耗完畢時(shí)，本文提出的方法可抵抗重放攻擊．

4 實(shí)驗(yàn)與結(jié)果

本文主要針對(duì)基于DBF的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)重點(diǎn)為持有性證明計(jì)算開銷、輔助存儲(chǔ)空間和BTBF性能．在Linux下使用Python語言實(shí)現(xiàn)本文模型的核心功能，其中動(dòng)態(tài)操作和BF計(jì)算使用Python的Btrees模塊和PybloomFiltermmap模塊實(shí)現(xiàn)，實(shí)驗(yàn)數(shù)據(jù)集為47 000個(gè)隨機(jī)生成的數(shù)據(jù)文件，數(shù)據(jù)集大小為2 048 MB．

4.1 計(jì)算開銷

為驗(yàn)證數(shù)據(jù)持有性證明計(jì)算更簡(jiǎn)單，分析并計(jì)算BTBF方法、MHT方法[5]、rb2-3方法[9]以及UpdateTrees方法[11]的各項(xiàng)時(shí)間復(fù)雜度，記錄如表2(其中n為數(shù)據(jù)塊數(shù)量，K為常數(shù)，D為動(dòng)態(tài)操作的數(shù)量)．

由表2所見，BTBF方法與rb2-3方法的CSP時(shí)間復(fù)雜度最小，都可以達(dá)到常量級(jí)；但是本文提出的BTBF方法在樹操作時(shí)間復(fù)雜度上明顯優(yōu)于其他幾種方法．

然后對(duì)BTBF和rb2-3兩種方法CSP的計(jì)算時(shí)間進(jìn)行對(duì)比，設(shè)置數(shù)據(jù)分塊大小為5 MB，BTBF 數(shù)位組長(zhǎng)度為20 000，單個(gè)BTBF節(jié)點(diǎn)錯(cuò)誤率為0.1%．在實(shí)驗(yàn)中，統(tǒng)計(jì)并記錄100、200、300、400和500塊數(shù)據(jù)塊下，兩種方法CSP計(jì)算持有證據(jù)的時(shí)間，結(jié)果取10次平均值，實(shí)驗(yàn)結(jié)果如圖3所示．

表2 驗(yàn)證方法時(shí)間復(fù)雜度對(duì)比Tab.2 Verification method′s time complexity comparison

圖3 不同數(shù)據(jù)量的持有證據(jù)計(jì)算時(shí)間Fig.3 The calculation time of different data volume of provable data possession verification

由圖3可見：本文提出的BTBF方法持有性證明的計(jì)算時(shí)間明顯少于rb2-3方法，并且隨著處理規(guī)模的增大，時(shí)間差異逐漸增大．本文提出的BTBF方法計(jì)算更加簡(jiǎn)單，計(jì)算時(shí)間開銷更小．

4.2 輔助存儲(chǔ)空間

對(duì)比BTBF方法和rb2-3方法的輔助存儲(chǔ)空間，設(shè)置單個(gè)BTBF節(jié)點(diǎn)錯(cuò)誤率為0.1%，數(shù)位組長(zhǎng)度為20 000，數(shù)據(jù)分塊大小為5 MB；分別統(tǒng)計(jì)BTBF方法和rb2-3方法在128、256、512、1 024和2 048 MB數(shù)據(jù)量下的輔助存儲(chǔ)，結(jié)果如表3所示．

從表3可見：(1)相同數(shù)據(jù)規(guī)模下BTBF使用的輔助存儲(chǔ)空間遠(yuǎn)小于rb2-3方法；(2)BTBF的輔助存儲(chǔ)空間與所驗(yàn)證的數(shù)據(jù)規(guī)模大小呈線性相關(guān)，輔助存儲(chǔ)空間大小可控．本文提出的BTBF方法具有更優(yōu)的輔助存儲(chǔ)，可提高云存儲(chǔ)數(shù)據(jù)的完整性驗(yàn)證效率．

表3 輔助存儲(chǔ)開銷對(duì)比Tab.3 Auxiliary storage′s overhead comparison

4.3 BTBF性能

為驗(yàn)證BTBF的性能，分別對(duì)BTBF生成和查詢時(shí)間進(jìn)行實(shí)驗(yàn)，設(shè)置數(shù)據(jù)分塊大小為5 MB，BTBF數(shù)位組長(zhǎng)度為20 000，單個(gè)BTBF節(jié)點(diǎn)錯(cuò)誤率為0.1%．在實(shí)驗(yàn)中，獲取并統(tǒng)計(jì)BTBF生成和查詢時(shí)間，結(jié)果取平均值，實(shí)驗(yàn)結(jié)果如圖4所示．

圖4 BTBF生成和查詢時(shí)間Fig.4 BTBF generation and query time

從圖4可見：(1)BTBF驗(yàn)證樹的生成和查詢時(shí)間降低到20 ms以下，計(jì)算時(shí)間有效降低；(2)BTBF的生成時(shí)間增長(zhǎng)速率較緩慢，不會(huì)因需校驗(yàn)的數(shù)據(jù)量變大而導(dǎo)致生成時(shí)間快速增長(zhǎng)．BTBF 避免了因?yàn)閿?shù)據(jù)規(guī)模增大而線性退化最終導(dǎo)致驗(yàn)證效率降低的問題．

5 結(jié) 語

本文提出一種基于DBF的云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證方法．該方法通過使用動(dòng)態(tài)布隆過濾器處理特征值向量生成數(shù)據(jù)塊標(biāo)簽，減少客戶端計(jì)算量；使用隨機(jī)驗(yàn)證路徑對(duì)云存儲(chǔ)數(shù)據(jù)進(jìn)行持有性驗(yàn)證；將TPV存儲(chǔ)空間變成與校驗(yàn)元數(shù)據(jù)規(guī)模相關(guān)的值，并且支持?jǐn)?shù)據(jù)全動(dòng)態(tài)操作．實(shí)驗(yàn)表明該方法提高了云存儲(chǔ)數(shù)據(jù)持有性驗(yàn)證效率．

[1] 馮登國(guó),張 敏,張 妍,等. 云計(jì)算安全研究[J]. 軟件學(xué)報(bào), 2011,22(1):71-83.

FENG Dengguo, ZHANG Min, ZHANG Yan,etal. Study on cloud computing security [J].JournalofSoftware, 2011,22(1):71-83. (in Chinese)

[2]ALI M, KHAN S U, VASILAKOS A V. Security in cloud computing: Opportunities and challenges [J].InformationSciences, 2015,305(1):357-383.

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

TAN Shuang, JIA Yan, HAN Weihong. Research and development of provable data integrity in cloud storage [J].ChineseJournalofComputers, 2015,38(1):164-177. (in Chinese)

[4]ATENIESE G, BURNS R, CURTMOLA R,etal. Provable data possession at untrusted stores [C] //CCS′07:Proceedingsofthe14thACMConferenceonComputerandCommunicationsSecurity. NY :ACM Press, 2007:598-609.

[5]WANG Qian, WANG Cong, LI Jin,etal. Enabling public verifiability and data dynamics for storage security in cloud computing [J].LectureNotesinComputerScience, 2009,5789LNCS:355-370.

[6]LI Aiping, TAN Shuang, JIA Yan. A method for achieving provable data integrity in cloud computing [J].JournalofSupercomputing, 2016,72(1):1-7.

[7]ESCALA A, HEROLD G, KILTZ E,etal. An algebraic framework for Diffie-Hellman assumptions [J].LectureNotesinComputerScience, 2013,8043LNCS(PART 2):129-147.

[8]HUSSIEN Z A, JIN Hai, ABDULJABBAR A,etal. Public auditing for secure data storage in cloud through a third party auditor using modern ciphertext [C] //Proceedingsofthe201511thInternationalConferenceonInformationAssuranceandSecurity,IAS2015. Marrakesh: IEEE Press, 2015:73-78.

[9]ZHANG Jianhong, MENG Hongxin, YU Yong. Achieving public verifiability and data dynamics for cloud data in the standard model [J].ClusterComputing, 2017,20(3):2641-2653.

[10]李 勇,姚 戈,雷麗楠,等. 基于多分支路徑樹的云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證機(jī)制[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016,56(5):504-510.

LI Yong, YAO Ge, LEI Linan,etal. LBT-based cloud data integrity verification scheme [J].JournalofTsinghuaUniversity(ScienceandTechnology), 2016,56(5):504-510. (in Chinese)

[11]ZHANG Yihua, BLANTON M. Efficient dynamic provable possession of remote data via update trees [C] //ASIACCS2013-Proceedingsofthe8thACMSIGSACSymposiumonInformation,ComputerandCommunicationsSecurity. NY: ACM, 2013.

[12]SATO F, WAKABAYASHI S. Bloom filters based on the B-tree [C] //ProceedingsoftheInternationalConferenceonComplex,IntelligentandSoftwareIntensiveSystems,CISIS2009. Fukuoka: IEEE Computer Society, 2009:500-505.

[13]SHIMBRE N, DESHPANDE P. Enhancing distributed data storage security for cloud computing using TPA and AES algorithm [C] //Proceedings—1stInternationalConferenceonComputing,Communication,ControlandAutomation,ICCUBEA2015. Piscataway: IEEE, 2015:35-39.

[14]BRODER A, MITZENMACHER M. Network applications of Bloom filters: a survey [J].InternetMathematics, 2004,1(4):485-509.