基于動態布隆過濾器的云存儲數據持有性驗證方法

謝 麗 霞， 胡 立 杰

( 中國民航大學 計算機科學與技術學院， 天津 300300 )

0 引 言

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

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

針對上述方法存在持有性證明計算復雜且驗證過程需要大量輔助存儲空間的不足，本文提出一種基于動態布隆過濾器(dynamic Bloom filter，DBF)的云存儲數據持有性驗證方法．該方法使用同態哈希函數處理驗證數據并生成用于驗證的校驗元，基于數據塊標簽構造動態布隆過濾器且支持動態操作，以實現對云存儲數據持有性的高效驗證．

1 動態布隆過濾器

1.1 BTBF結構

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

BTBF每個節點包含i個BF，除根節點外，BTBF每個節點可存儲多個關鍵字，一個4階BTBF如圖1所示．

圖1 BTBF結構Fig.1 BTBF structure

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

(1) BTBF中節點的關鍵字由數據塊標簽、對應的驗證簽名構成，其中驗證簽名包括數據塊簽名和驗證計數位；

(2) BTBF中節點按數據塊標簽從大到小排列；

(3) 任意非葉子節點最多只有M個子節點，且M>2，其中M為BTBF容度；

(4) 根節點的子節點數為[2，M]；

(5) 根節點外的非葉子節點數為[M/2，M]；

(6) 每個節點存放至少

M/2-1

個和至多M-1個布隆過濾器；

(7) 非葉子節點的關鍵字數量比對應子節點少1．

1.2 BTBF的錯誤率

本文提出的BTBF在云存儲數據持有性證明中錯誤率為固定值．傳統布隆過濾器存在錯誤率和飽和度的問題[12]，由于難以預知集合中的元素數量，隨著插入元素的增多飽和度會增加，錯誤率也將隨之提高并最終導致布隆過濾器不可用．BTBF錯誤率P可由特征值數量n、數位組長度m和選擇哈希函數的數量k決定，P與各參數之間的關系為

(1)

云存儲數據持有性證明中因為數據分塊大小固定，因此通過選擇適當的m、n和k，可保證BTBF 錯誤率變為一個可控的固定值，避免錯誤率升高．

2 云存儲數據持有性驗證方法

2.1 驗證模型

傳統的完整性驗證模型不支持公開驗證且需要在客戶端存儲大量數據[13]，因此本文在傳統云存儲驗證模型的基礎上引入第三方驗證平臺，云存儲數據完整性驗證模型結構如圖2所示．

圖2 云存儲數據完整性驗證模型Fig.2 Cloud storage data integrity verification model

第三方數據完整性驗證模型包含客戶端(Client Server，CS)、云服務提供商(Cloud Server Provider，CSP)和第三方驗證平臺(Third Party Verification，TPV)，CS將數據加密上傳并生成校驗證據，CSP存儲數據和生成數據持有證據應答，TPV存儲校驗證據和進行數據完整性驗證．

2.2 方法具體實現

基于DBF的云存儲數據持有性證明方法包括3個階段：初始化階段、挑戰階段和應答階段．3個階段的具體設計如下：

(1)初始化階段

首先，CS對存儲數據進行預處理，然后，將數據和校驗證據分別上傳給CSP和TPV，過程設計如下：

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

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

(b)CSP存儲CS上傳的數據塊m1，m2，…，mv，TPV接受CREAT請求后存儲數據塊驗證簽名集bf1，bf2，…，bfv，初始化驗證計數位并生成BTBF，要求BTBF容度M≥4．BTBF的關鍵字由數據塊驗證簽名bfi和數據塊標簽numi組成．

(2)挑戰階段

初始化完成后，CS可發起挑戰請求CHL，TPV生成驗證請求TPV_CHL．過程設計如下：

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

(3)應答階段

CSP在接受驗證請求后，根據TPV_CHL生成對應數據塊持有證據交由TPV進行持有性驗證，過程設計如下：

CSP接受TPV_CHL請求后，根據請求中包含的數據塊標簽numi查找對應的數據塊mi，生成校驗元向量Ai=(ai1ai2…aiv)(i=1，2…，v)，通過k個同態哈希函數生成長度為s的數據持有證據cfi，生成應答R=(cf1cf2…cfs)并反饋給TPV，TPV計算校驗結果α：

(2)

其中s為隨機驗證路徑長度．若α=0，則云存儲數據完整性驗證成功，TPV向CS返回結果“TRUE”，否則驗證失敗，返回結果“FALSE”，BTBF節點參與驗證后需對該節點的校驗計數位bc進行自增操作．

2.3 數據動態操作

基于DBF的數據持有性驗證方法可支持包括更新、插入和刪除的數據操作．

2.3.1 數據更新算法 當用戶更新數據塊mi(i=1，2，…，v)時，BTBF云存儲數據持有性驗證方法的處理過程設計如下：

(a)CS計算更新數據塊mi的標簽值numi和簽名bfi，分別向云存儲服務器和TPV發送更新請求Update_C={numi：mi}和Update_T={numi：bfi}．

(b)云存儲服務器接收更新請求Update_C={numi：mi}后，根據標簽值numi尋找存儲在云端的數據塊，用mi替換原有數據塊m′i．

(c)TPV接收更新請求Update_T={numi：bfi}后，根據numi在BTBF中查找對應的校驗數位組并替換為bfi，并將節點驗證計數位bci初始化為0．

(d)當云存儲服務器和TPV進行更新操作后，CS對云存儲服務器進行一次數據完整性校驗，校驗成功后CS刪除本地存儲的mi．

(a)CS計算插入數據塊mi的標簽值numi以及簽名bfi，分別向云存儲服務器和TPV發送插入請求Insert_C={numi：mi}和Insert_T={numi：bfi}．

(b)CSP接收請求Insert_C={numi：mi}后，存儲接收的數據塊mi．

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

(d)當CSP和TPV全部進行插入操作后，CS對云存儲服務器進行一次數據完整性校驗，校驗成功后CS刪除本地存儲的mi．

2.3.3 數據刪除算法 當用戶刪除數據塊mi(i=1，2，…，v)時，BTBF云存儲數據持有性驗證方法的處理過程設計如下：

(a)CS查找刪除數據的標簽值numi，分別向云存儲服務器和TPV發送刪除請求Delete_C={numi}和Delete_T={numi}．

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

(b)云存儲服務器接收Delete_C={numi}后，根據數據塊標簽numi查找數據塊并刪除．

(c)TPV接收Delete_T={numi}后，在BTBF 中查找數據塊標簽為numi的節點并刪除該節點中對應的關鍵字．節點在數據塊刪除后，需要判斷該節點關鍵字數量是否滿足每個節點至少存放和至多M-1的條件．如果該節點不滿足，BTBF樹需要對該節點和鄰近節點進行合并，使得樹仍滿足BTBF條件．

M/2-1

(d)當CSP和TPV分別進行刪除操作后，CS對云存儲服務器進行一次數據完整性校驗，校驗成功后CS刪除操作完成．

本文提出的基于DBF的云存儲數據持有性驗證方法的動態操作與傳統方法相比具有以下特點：

(1)更新操作不只在葉子節點處進行，BTBF樹的內部均可進行更新操作，優化存儲空間．

(2)刪除操作只針對刪除節點，不需對其他節點進行更新操作，減少刪除造成的冗余計算．

(3)與常用的默克爾哈希樹相比，BTBF的插入操作優化驗證樹的高度，避免大量執行插入操作后驗證樹退化為線性結構，提高數據完整性驗證效率．

3 驗證的安全性分析

對基于DBF的云存儲數據持有性驗證方法分別從驗證正確性、數據保密性、持有證明不可偽造性和抗重放攻擊等幾方面進行分析．

3.1 正確性分析

BTBF在云存儲數據持有性驗證中存在由假陽性問題造成的錯誤率，因此本文采用多個數位組構成驗證路徑的方式降低錯誤率，使得驗證的正確率達到100%，布隆過濾器的錯誤率[14]如表1所示．

設BTBF高為h，容度為M，隨機驗證路徑S的長度為s，單個BTBF節點驗證錯誤率為f．則數據驗證率c=sh/(Mh-1)，單條驗證路徑錯誤率Ps=fsh．驗證過程中，當sh≥3時，若f≤0.01，則Ps≤1×10-6．

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

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

可見，本文方法使用BTBF驗證正確率可達到100%．

3.2 保密性分析

第三方平臺通過兩種方式得到用戶有效數據：方式一為第三方平臺通過CS上傳的校驗證據，方式二為CSP提供的持有證據．

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

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

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

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

首先，假設攻擊方偽造數據持有證據(Rp=(cf′1cf′2…cf′s))，其中，cf′i(i=1，2，…，s，s為驗證路徑S長度)為數據標簽．其中對于BTBF單個節點關鍵字偽造成功的成功率Pl=1/2m，那么單條隨機驗證路徑S的持有證據偽造的成功率為Ps：

(3)

當攻擊方對多條隨機路徑發起聯合攻擊時，多條路徑的持有證據需同時通過TPV的持有驗證，因此對于w條隨機路徑聯合攻擊成功概率Pc可通過Ps得到：

(4)

w條隨機路徑聯合攻擊的成功概率Pc會隨著s和w的增大而逐漸減小，由于m≥6，則Pc遠小于0.015 6，可認為攻擊方對多條路徑聯合攻擊的成功概率為0．因此，本文提出的方法，當驗證的數據規模越大時，抵抗偽造攻擊的能力越強．

本文的云存儲數據完整性驗證方法為動態驗證方法，所以TPV存儲的校驗數據會隨時間變化而變化．當攻擊方在BTBF樹更新后進行攻擊時，由于BTBF驗證樹會因為更新操作發生改變，重放已有的持有證據并不能通過TPV的完整性驗證；當攻擊方在BTBF樹未更新時進行重放攻擊，由于BTBF關鍵字中包括驗證計數位，在驗證計數位未完全消耗的情況下，每次驗證時驗證計數位不同，因此重放已有的持有證據，并不能通過TPV的完整性驗證．當在BTBF節點計數位未消耗完畢時，本文提出的方法可抵抗重放攻擊．

4 實驗與結果

本文主要針對基于DBF的云存儲數據持有性驗證方法進行實驗，實驗重點為持有性證明計算開銷、輔助存儲空間和BTBF性能．在Linux下使用Python語言實現本文模型的核心功能，其中動態操作和BF計算使用Python的Btrees模塊和PybloomFiltermmap模塊實現，實驗數據集為47 000個隨機生成的數據文件，數據集大小為2 048 MB．

4.1 計算開銷

為驗證數據持有性證明計算更簡單，分析并計算BTBF方法、MHT方法[5]、rb2-3方法[9]以及UpdateTrees方法[11]的各項時間復雜度，記錄如表2(其中n為數據塊數量，K為常數，D為動態操作的數量)．

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

然后對BTBF和rb2-3兩種方法CSP的計算時間進行對比，設置數據分塊大小為5 MB，BTBF 數位組長度為20 000，單個BTBF節點錯誤率為0.1%．在實驗中，統計并記錄100、200、300、400和500塊數據塊下，兩種方法CSP計算持有證據的時間，結果取10次平均值，實驗結果如圖3所示．

表2 驗證方法時間復雜度對比Tab.2 Verification method′s time complexity comparison

圖3 不同數據量的持有證據計算時間Fig.3 The calculation time of different data volume of provable data possession verification

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

4.2 輔助存儲空間

對比BTBF方法和rb2-3方法的輔助存儲空間，設置單個BTBF節點錯誤率為0.1%，數位組長度為20 000，數據分塊大小為5 MB；分別統計BTBF方法和rb2-3方法在128、256、512、1 024和2 048 MB數據量下的輔助存儲，結果如表3所示．

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

表3 輔助存儲開銷對比Tab.3 Auxiliary storage′s overhead comparison

4.3 BTBF性能

為驗證BTBF的性能，分別對BTBF生成和查詢時間進行實驗，設置數據分塊大小為5 MB，BTBF數位組長度為20 000，單個BTBF節點錯誤率為0.1%．在實驗中，獲取并統計BTBF生成和查詢時間，結果取平均值，實驗結果如圖4所示．

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

從圖4可見：(1)BTBF驗證樹的生成和查詢時間降低到20 ms以下，計算時間有效降低；(2)BTBF的生成時間增長速率較緩慢，不會因需校驗的數據量變大而導致生成時間快速增長．BTBF 避免了因為數據規模增大而線性退化最終導致驗證效率降低的問題．

5 結 語

本文提出一種基于DBF的云存儲數據持有性驗證方法．該方法通過使用動態布隆過濾器處理特征值向量生成數據塊標簽，減少客戶端計算量；使用隨機驗證路徑對云存儲數據進行持有性驗證；將TPV存儲空間變成與校驗元數據規模相關的值，并且支持數據全動態操作．實驗表明該方法提高了云存儲數據持有性驗證效率．

[1] 馮登國,張 敏,張 妍,等. 云計算安全研究[J]. 軟件學報, 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]譚 霜,賈 焰,韓偉紅. 云存儲中的數據完整性證明研究及進展[J]. 計算機學報, 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]李 勇,姚 戈,雷麗楠,等. 基于多分支路徑樹的云存儲數據完整性驗證機制[J]. 清華大學學報(自然科學版), 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.