大數據存儲中數據完整性驗證結果的檢測算法

徐光偉 白艷珂 燕彩蓉 楊延彬 黃永鋒

(東華大學計算機科學與技術學院 上海 201620)

(gwxu@dhu.edu.cn)

大數據存儲中數據完整性驗證結果的檢測算法

徐光偉 白艷珂 燕彩蓉 楊延彬 黃永鋒

(東華大學計算機科學與技術學院 上海 201620)

(gwxu@dhu.edu.cn)

云存儲作為云計算中最為廣泛的應用之一，給用戶帶來了便利的接入和共享數據的同時，也產生了數據損壞和丟失等方面的數據完整性問題.現有的遠程數據完整性驗證中都是由可信任的第三方來公開執行數據完整性驗證，這使得驗證者有提供虛假偽造的驗證結果的潛在威脅，從而使得數據完整性驗證結果不可靠，尤其是當他與云存儲提供者合謀時情況會更糟.提出一種數據驗證結果的檢測算法以抵御來自不可信驗證結果的偽造欺騙攻擊，算法中通過建立完整性驗證證據和不可信檢測證據的雙證據模式來執行交叉驗證，通過完整性驗證證據來檢測數據的完整性，利用不可信檢測證據判定數據驗證結果的正確性，此外，構建檢測樹來確保驗證結果的可靠性.理論分析和模擬結果表明：該算法通過改善有效的驗證結果來保證驗證結果的可靠性和提高驗證效率.

數據完整性驗證；不可信驗證結果；驗證結果檢測；雙證據；檢測樹

云計算是基于互聯網相關服務的可動態擴展的虛擬化資源，它通過網絡方便地按需接入和較小代價可使得用戶獲取服務提供者的網絡、服務器、存儲和應用等資源池中的可配置計算資源[1].云存儲作為云計算中最有潛力的一種應用，是通過互聯網可動態擴展虛擬化存儲的一種方式.云存儲在給用戶帶來方便的同時，也會因為用戶失去了對自己數據的絕對控制權，而使得用戶數據的可用性和安全性受到威脅.在云存儲的服務模式下，擁有可接入網絡的用戶設備既可以隨時隨地訪問自己存儲在云服務器中的數據，又能方便地按照一定規則與其他用戶設備之間共享數據.云存儲在為用戶帶來便利的同時，也會因自身的問題如病毒攻擊、操作失誤和來自網絡的惡意攻擊等，損壞或丟失用戶存儲的數據.甚至當數據損失發生時，云存儲服務提供者(cloud storage provider， CSP)為維護自身利益和聲譽，常隱瞞數據丟失或損壞.非預期的數據丟失或損壞會給數據完整性和可靠性帶來災難性后果[2].為避免云存儲中的數據損失，使用戶在有限的計算能力下確保大規模數據存儲的完整性，Deswarte等人[3]提出一種基于加密的方法來驗證遠程數據的完整性，此后，遠程數據存儲的完整性驗證成為解決這種問題的關鍵技術[4].

目前很多數據完整性驗證算法被提出[5-25]，這些算法主要分為可證明的數據持有技術(provable data possession， PDP)和可恢復證明技術(proof of retrievablity， POR)兩大類，分別從驗證的可公開性、動態數據、無狀態驗證、無塊驗證、批量驗證、隱私保護、數據機密性、多云多副本驗證等方面進行了研究，但這些算法都基于數據驗證者(data verifier，DV)會提供可靠的驗證結果而忽視了其不可信所帶來的問題.這是由于在實際的開放云存儲環境中，并不存在絕對可靠的數據驗證者，他們也會因自私或惡意而對數據驗證結果的準確性和可靠性造成危害.本文提出一種數據驗證結果的檢測算法以抵御來自不可信驗證結果的偽造欺騙攻擊，主要貢獻有4個方面：

1) 生成完整性驗證證據來檢測數據的完整性；

2) 生成不可信檢測證據來判定數據驗證結果的正確性；

3) 通過構建驗證結果的檢測樹來抵御偽造欺騙攻擊和驗證結果的不可篡改性;

4) 利用雙證據來執行交叉驗證以確保數據完整性驗證結果的可靠性.

1 相關工作

遠程數據完整性驗證隨著云存儲應用的不斷普及，越來越受到科學界和工業界的關注.自從Ateniese等人[5]和Juels等人[6]分別提出PDP和POR驗證方案以來，出現了大量的遠程數據完整性驗證算法.

Ateniese等人[5]首次提出數據持有性證明的PDP模型，并利用RSA同態技術來驗證遠程存儲數據的完整性，方案中采用隨機抽樣技術進行概率性驗證，以減少數據驗證過程中的計算量和通信量，但這種方法并不支持遠程數據的動態操作.Juels等人[6]首次探索可恢復證明的 POR模型來確保遠程數據存儲可持有和可提取.Hovav等人[7]提出一種支持數據恢復的緊湊型POR.Erway等人[8]提出一種基于Rank的跳躍列表結構實現支持全動態(數據插入、刪除、增加、修改等)操作的PDP方案，但卻不能很好地保護用戶數據的隱私.為了提高遠程數據驗證的效率，Wang等人[9]利用Merkle Hash樹構建了一種支持批量驗證的方案，并同時支持數據的動態操作和公開校驗.后來，Wang等人[10]進一步利用隨機掩碼、加密盲化技術設計了一種能夠保護數據隱私的可公開驗證方案，它不僅可以防止惡意攻擊者獲得用戶數據的真實內容，也可以防止將真實內容泄露給第三方驗證者.Zhu等人[11]考慮多個云服務提供商在協同存儲和共同維護客戶數據的情況下，提出一種基于同態驗證響應和Hash索引層次的合作PDP方案.Yang等人[12]提出了一種高效和隱私保護的數據審計協議，以支持在沒有任何可信的組織者組織的情況下，多數據所有者和多個云存儲的數據動態操作和批量審計.Wang等人[13]使用代理重簽名技術允許云服務器在個別用戶撤銷簽名時代表仍然存在的用戶執行對存儲數據的重簽名.我們在文獻[14]中提出一種概率驗證的算法以抵御遠程數據存儲數據完整性遭受破壞時的欺騙攻擊.譚霜等人[25]提出一種基于格的數據完整性驗證方法.

但上述這些算法都是在假設驗證者完全可信的前提下，或者校驗者只會竊取用戶的隱私數據，并不會對數據驗證本身有任何欺騙行為.只是在Armknecht等人[23]的工作中假定驗證者在未執行數據驗證任務時給出欺騙數據所有者的驗證結果，從而提出一種判定數據驗證者的驗證結果是否可信的檢測算法.算法中在用戶上傳文件之前，驗證者也對文件生成一份驗證標簽.在挑戰時，服務器對來自數據所有者和驗證者的2個不同標簽也生成相應的驗證證據，以此來判斷驗證者的結果是否保持一致.但這種算法需要在數據上傳之前，首先需要指定驗證者身份(這有明顯的合謀攻擊之嫌)，并且該驗證者也需要存儲每次驗證的日志文件(這將占用驗證者的存儲空間).

數據的完整性是數據所有者進行遠程數據存儲時最為關注的核心，本文將研究數據存儲提供者和數據驗證者都不可信時的驗證檢測算法，以盡可能少的檢測計算、存儲和傳輸開銷，保證其可靠性和有效性.

2 驗證模型與問題提出

2.1驗證模型

我們選取現有的數據驗證算法中普遍采用的基于第三方的可公開驗證模型來描述數據完整性驗證的過程和數據流向，如圖1所示：

Fig. 1 Data verification model圖1 數據驗證模型圖

驗證模型主要包括3個實體，即數據所有者(data owner， DO)、云存儲提供者和驗證者.CSP為DO提供自由存取的數據存儲服務時，也根據協議享受數據驗證服務.當應DV的請求對CSP發起數據完整性挑戰后，CSP根據DV提供的驗證參數進行計算，然后將證據返回給DV，DV比較數據證據和DO提供的數據標簽來判定相應的存儲數據是否完整或已損壞.數據驗證過程由如下5個階段來描述.

1) KeyGen(·)→(sk,pk).DO利用密鑰生成算法產生公私密鑰對(其中sk為私鑰，pk為公鑰)，并對外公布公鑰pk信息.

2) TagGen(sk,M)→Φ.DO利用自己的私鑰sk對數據塊集合M中的第i個數據塊mi(i∈[1,n])計算其相應的數據標簽ti，最后將所有的數據標簽信息放入標簽集合Φ中，即Φ={ti}.

3) ChalGen(M)→Ω.DV接受DO發布的數據驗證任務，對其中所包含的待驗證數據塊mi產生挑戰隨機數vi，并和其相應的數據塊索引組成挑戰集合Ω={i,vi}，向CSP發起挑戰.

4) ProofGen(M,Φ,Ω)→P.CSP接受DV的挑戰后，根據挑戰集合Ω和待驗證的數據塊集合M、標簽集合Φ等計算得到待驗證數據塊的數據完整性證據集合，并將這些證據返回給DV作為判定依據.

5) Verify(Ω,P,pk)→truefalse.DV利用DO的公鑰pk，Ω，P來判定CSP提供的數據完整性證據，并將判定結果發送給DO.

本文做了如下一些假設：

1) DV主動承擔數據驗證任務而不受CSP和DO控制，且DV數量足夠多可保證驗證任務都能被執行.

2) DV的不可信行為表現為返回給DO的驗證結果是偽造的.其原因可能是自私或惡意(如自身設備性能和能耗受限等)，使得他在無力承擔這些數據驗證任務而做出偽證.

2.2對手模型

正如引言所述，現有的數據驗證主要是針對云存儲提供者可能存在的數據損壞欺騙行為.而執行數據驗證任務的DV也可能返回虛假偽造的驗證結果.此時，由于現有的數據驗證模型中沒有應對的檢測機制，會導致DO在面對驗證者的驗證結果時只能盲目服從，而喪失了自己作為數據完整性驗證的主體作用.此外，如果不可信CSP和DV進行合謀欺騙，那會對DO造成更大的損失.

2.3問題提出

從數據驗證模型和對手攻擊中可以看出，需要在現有的模型中增加對不可信驗證結果的檢測，以解決現有算法中的3個問題：

1) 識別CSP提供的不可信驗證數據；

2) 識別DV提供的不可信驗證結果；

3) 識別不可信CSP和DV的合謀攻擊.

3 不可信驗證結果的檢測算法

為便于描述，一些符號定義為：Q是挑戰集合；ti是數據塊mi的標簽；P是完整性驗證證據；P′是不可信檢測證據；sk是私鑰；pk1，pk2是2個公鑰；e是群G1，G2到群GT的雙線性映射；TP{·}是標簽證據；DP{·}是實際數據證據.

3.1不可信驗證結果的檢測證據生成

傳統的數據驗證方案中，CSP接受DV的挑戰后，在ProofGen(·)階段根據挑戰集合Q和待驗證的數據塊mi組成的數據集合M、標簽集合Φ等計算待驗證數據塊的數據完整性證據集合P，并將其返回給DV作為判定依據.在我們的算法中，增加一個不可信驗證結果的檢測證據以判別DV的虛假驗證結果.

定義1. 完整性驗證證據. CSP接受DV的挑戰后，發送給DV的面向待驗證數據所生成的完整性擁有的驗證證據，被標記為P.

定義2. 不可信檢測證據. CSP接受DV的挑戰后，發送給DO的面向DV的不可信驗證結果的檢測證據, 被標記為P′.

為此，在ProofGen(·)階段，CSP除計算完整性驗證證據以外，還要增加一個不可信驗證結果的檢測證據P′，具體過程如下：

1) 在KeyGen(·)階段，在安全參數確定后，通過執行概率性算法多產生一個公鑰pk2.

2) 在ProofGen(·)階段，不可信檢測證據P′={TP2,DP2}中實際數據證據DP2的計算公式為

其中，vi為p中選取的對應于每個數據塊mi的一個隨機數，r為p中任意選取的隨機數，u為群G1中的一個元素，g2為群G2的生成元，R為挑戰標記.

不可信檢測證據P′={TP2,DP2}中標簽證據TP2的計算公式為

3)CSP發送檢測證據P′給DO作為不可信驗證結果的檢測依據.這些證據的生成算法見4.3節.

3.2不可信驗證結果的檢測

云存儲環境下的數據驗證中，通常數據的驗證量比較大.此外，驗證者的設備能力差異，都制約著所有數據驗證任務由一個DV來執行，因此，驗證任務可由多個DV采用分布式處理的方式來執行.在此，我們以一個DV所完成的數據驗證結果為例，來研究其不可信驗證結果的檢測方法.為避免檢測過程中DV為應對DO的檢測而臨時篡改數據，我們引入Merkle Hash樹技術[26]來建立驗證結果的檢測樹.

Merkle Hash樹是一棵二叉樹，其每個葉子節點對應一個數據塊mi的驗證結果Ri，每個非葉子節點值為其子節點的Hash值，最后構成檢測樹由DV發送給DO.為區分不同數據塊的驗證結果，我們用每個數據塊mi的身份標識mi,id和DV的驗證結果(truefalse)組合而成，即mi→Ri.給定一個k位返回值的Hash函數f:{0,1}→{0,1}k，例如Hash函數MD5和SHA-2.樹中的非葉子節點H(Ri‖Ri+1)的值為其左右2個子節點Ri和Ri+1級聯后的Hash值，即H(Ri‖Ri+1)=f(Ri+Ri+1)，其中的“+”表示級聯運算.如圖2所示，我們建立了一個由8個被驗證數據塊組成的檢測樹，其中的葉子節點R1和R2分別是數據塊m1和m2的驗證結果，非葉子節點H(R1‖R2)是2個葉子節點R1和R2級聯后的Hash值.依次從葉子節點向根節點級聯運算，最后得到根節點的Hash值φ=H(R1‖R8) .

Fig. 2 Check tree of verification results圖2 驗證結果的檢測樹

不可信驗證結果的檢測原理是:當DV執行完驗證任務后，發送每個數據塊的驗證結果和檢測樹的根節點值φ給DO.若DO懷疑來自DV的驗證結果，他任意抽取一個數據塊的驗證結果進行檢測.為方便描述，任意選取一個數據塊mi來研究其檢測過程.

DO得到DV對數據塊mi的驗證結果Ri后.他首先利用來自CSP的TP2，DP2，pk2檢測驗證結果Ri的正確性.如果Ri不正確，那么表明DV提供了虛假的驗證結果;如果Ri正確，這也不能證明DV是誠實的，因為可能是在他被要求提供該數據塊的驗證結果時重新計算所得的.此時，DO利用正確的Ri和相應的各兄弟節點，重新構造一顆從該葉子節點到根節點的樹，并獲得重構后的根節點值φ′，由于Hash函數是單向函數，通過比較根節點的值φ和φ′是否相等，可以判定葉子節點對應的驗證結果是否真實.我們以圖2中的葉子節點R4為例敘述其過程.

DO收到DV發送的根節點φ值后，隨機選擇一個葉子節點R4來檢測驗證結果.DO利用DV提供的R3，H(R1‖R2)，H(R1‖R4)，H(R5‖R8)值重構從葉子節點R4到根節點的路徑(圖2中虛線箭頭所指路徑)，并重新計算根節點的值φ′.如果重新計算的φ′與DV原來發送的φ值相等，即φ′=φ，則表示DV的驗證結果是真實的，否則是虛假的.

3.3不可信驗證的檢測算法

本文提出的算法不僅能驗證CSP存儲的數據完整性，還能檢測DV的驗證結果的可靠性和有效性.

為此，需要在傳統的數據驗證模型基礎上進行必要的完善.在圖3中，相對于現有模型，我們增加了步驟④(檢測證據的生成和發送)和步驟⑥(驗證結果的檢測).不可信驗證結果的檢測流程如圖4所示：

Fig. 3 Check scheme of untrusted verification results圖3 不可信驗證結果的檢測方案

Fig. 4 Check process of untrusted verification results圖4 不可信驗證結果的檢測過程

群G1，G2，GT是具有相同大素數p階的乘法循環群，g1，g2分別是群G1，G2的生成元，p是模p的剩余類，e:G1×G2→GT是群G1，G2到GT的雙線性映射，h:{0,1}*→G1是一個Hash映射.算法的詳細描述如下：

1) KeyGen(λ)→(sk,pk1,pk2).在給定輸入安全參數后，執行一個概率性算法，生成DO的私有密鑰sk和公有密鑰{pk1,pk2}.隨機選擇sk∈p作為DO的私有密鑰，相應的公鑰為pk1=，pk2=，并將{pk1,pk2}公開.

2) TagGen(sk,M)→Φ.DO讀取經加密重新編碼后的文件M和自己的私鑰sk，生成文件M中各數據塊mi的相應標簽ti.為了增加數據處理的安全性，在p中隨機選擇一個隨機數a，并計算u=.DO將已加密的數據文件M按照約定分割成固定大小的n個數據塊，然后對每一個數據塊mi(i∈[1,n])，計算其相應的數據標簽

ti=(h(Wi)×umi)s k，

其中Wi=Mi d‖i，且Mi d是文件M的標識，i是數據塊的索引號，‖代表數據的連接操作.將所有生成的數據塊標簽ti放入標簽集合Φ.隨后將數據文件M和標簽集合Φ一起上傳至CSP的空間保存.

3) ChalGen(M)→Ω.DV選取數據文件M中的c≤n個數據塊發起挑戰，并產生相應的挑戰信息.該算法根據DO的請求，在數據文件M中隨機選取c個索引號，組成挑戰數據塊索引集合Q.并為每一個待驗證的數據塊索引i在p中任意選取一個隨機數vi與之對應，即產生二元組(i,vi)(i∈Q).另在p中選取一個隨機數r，計算挑戰標記最后將所有的二元組(i,vi)和挑戰標記放在一起組成挑戰Ω={(i,vi)i∈Q,R}，并向CSP發起數據完整性挑戰.

4) ProofGen(M,Φ,Ω)→(P1,P2).CSP根據數據文件M和數據文件對應的標簽集合Φ，以及來自DV的挑戰信息Ω，計算相應的數據完整性證據P1(包括標簽證據TP1和數據證據DP1)和驗證結果檢測證據P2中的數據證據DP2.數據完整性證據P1中的標簽證據TP1計算公式為

數據完整性證據P1中的數據證據DP1計算公式為

CSP將數據完整性證據P1=(TP1,DP1)發送給DV.同時，CSP按照式(1)和式(2)計算驗證結果檢測證據P2=(TP2,DP2)并發送給DO.

5) VerifyData(Ω,P1,pk1)→(i,truefalse).DV接收到CSP發送的數據完整性證據P1后，利用數據完整性驗證算法驗證數據的完整性，根據挑戰信息Ω 和公鑰pk1做出數據是否完整的判斷，如果數據完整則輸出true，否則輸出false.其判斷公式為

如果式(6)成立，則向DO報告數據完整，否則報告數據損壞，輸出數據完整性的驗證結果Ri={i,truefalse}.

此外，DV構建驗證結果的檢測樹，并計算根節點的φ值，與Ri一起發送給DO.

6) ResultCheck(Ri,DP2,φ)→YN.DO利用CSP發送的驗證結果檢測證據P2、檢測DV發送的驗證結果Ri和檢測樹的φ值，判定驗證結果的正確性.DV首先利用CSP發送的驗證結果檢測證據P2中的TP2和DP2來判定公式

是否滿足.如果式(7)不成立，則說明數據是不完整的;如果成立，則需要根據檢測樹來進一步判定DV是否提供虛假檢測結果.

DO任意選擇一個數據塊的驗證結果Ri，利用DV發來的該節點在檢測樹中的所有兄弟節點，重構檢測樹并計算根節點值φ′.比較φ與φ′的值，若

φ′=φ，

則說明DV正確執行了驗證任務并輸出Y，否則說明其未按照約定執行驗證任務并輸出N.

經過VerifyData(·)和ResultCheck(·)的檢測，可識別CSP和DV是否提供了可信的驗證結果.

3.4分段檢測的支持

考慮到數據在分塊的基礎上還有進一步劃分數據段的方式[12]，為提高檢測證據生成的適應性，我們也提供了這種方式下的生成方法.假設數據塊mi被分成s個數據段mij(j∈[1,s])，則不可信檢測證據的生成過程如下:

DO在p中選取s個隨機數，即a1，a2，…，as∈p，并計算uj=∈G1.利用這些參數對所有數據段進行聚合處理，即檢測證據的生成過程如下：

1)DO計算相應的數據塊mi的標簽為

檢測證據中數據證據的計算為

4 算法安全性分析

4.1檢測的正確性分析

檢測算法是否能夠對數據完整性的DV提供的驗證結果進行檢測，依賴于算法的正確性，即式(6)和式(7)是否成立.式(7)的正確性證明如下.

證明.

證畢.

式(6)的正確性證明與式(7)證明相似，此處省略.

4.2抵御攻擊能力分析

本文提出的遠程數據完整性驗證的檢測算法，其安全性建立在離散對數的假設之上.我們首先給出安全性定義域假設.

計算性Diffie-Hellman問題(簡稱CDH問題)： 設a∈將g1，∈G1，h∈G1作為輸入，輸出ha∈G1.

計算性離散對數問題(簡稱DL問題) 群G是具有素數(p)階的循環群，g是群G的生成元，即g=G，?γ∈G，輸入γ，輸出a∈使得ga=γ.

定義3. 離散對數計算假設(簡稱DL假設).存在一個可以忽略的概率εgt;0，任意敵手利用一個可能的多項式時間算法Θ在群G上求解DL問題的概率滿足：

P(Θ(g,γ)=a|ga=γ)lt;ε .

求解DL問題的可能性等價于在中隨機選擇一個元素進行碰撞攻擊，即對于元素γ=ga，在中隨機選取一個元素a′，使得γ=ga′，由于|G|=|p,所以必須有a=a′，那么明顯，其碰撞的概率為P(·)=1p(p為一個足夠大的素數)，因此滿足P(·)lt;ε .也就是說，對于任何一個可能的多項式算法，求解DL問題的概率幾乎是可以忽略的，即任意敵手求解DL問題的概率接近于0.那么，在DL假設成立的情況下，在群G上解決DL問題在計算上是不可能或者困難的.

云存儲提供者偽造攻擊：CSP試圖通過DV的數據完整性驗證，即滿足式(6)的驗證，正如在文獻[8]中描述的，在計算上是不可行的，CSP無法進行隱藏偽造攻擊，本文將不再贅述其分析過程.

驗證者偽造驗證結果攻擊：DV試圖通過DO對其驗證結果的檢測，即滿足式(7)和式(8)的驗證.對于式(7)，其中的關鍵數據DP2，TP2盡管都是由CSP產生的，但根據同態驗證的原理，它們是無法偽造的.對于式(8)，根據檢測樹的構建原理，DV一旦提供了φ值后，DO生成φ′值時，他是無法參與偽造的.因此，從上述分析可以看出，DV也無法偽造驗證結果進行攻擊.

此外，DO不必每次親自檢測數據的完整性，否則就喪失了DV執行數據驗證的作用.因此，DO對DV的驗證結果執行的是隨機檢測方式，即隨機對DV返回的驗證結果進行檢測.此時，DV在每次驗證后提交給DO的每個數據塊驗證結果可通過檢測的概率是1/2.當DO執行多個數據塊(如x塊)檢測后，驗證結果能夠通過檢測的概率是(1/2)x.例如當x≥5時，DV的驗證結果能夠通過用戶驗證的概率小于5%.所以DO執行一定數量的數據塊完整性驗證結果的檢測后，就能識別不可信的DV.

5 實驗分析

實驗在1臺雙CPU(主頻Xeon E5-2403 1.8 GHz)、8 GB內存的服務器上搭建云存儲服務環境，采用2臺CPU(主頻Intel Core i5-4210M 2.60 GHz)、8 GB內存的筆記本電腦分別作為數據所有者和驗證者.檢測算法用Java語言編寫，利用JPBC函數庫實現.為測試我們提出算法的有效性，命名提出的算法為CIVR(check algorithm of incredible verification results)，并選擇算法W-POR[12]和Fortress[23]作對比分析.實驗中測試數據為20次的平均值.

1) 驗證能力

Fig. 5 Verification capability圖5 驗證能力

驗證能力指的是驗證相同數量的數據塊時所耗費的計算時間，讓每個數據塊大小為32 KB，其實驗結果如圖5所示:

從圖5可以看出，CIVR的數據驗證能力與Fortress相似，但都稍遜于W-POR.其原因在于CIVR和Fortress都需要服務器生成2對驗證證據，而W-POR在數據驗證過程中只產生1對驗證證據，這節省了服務器生成證據的計算開銷，也節省了數據驗證的時間.但考慮到實際云計算環境中云服務器的強大運算能力，生成證據的時間差別可以由分布式計算來彌補.

2) 存儲開銷

存儲開銷指的是數據驗證過程中各驗證方所產生的驗證數據存儲量.3種算法的實驗結果如圖6所示.可以看出，CIVR和W-POR的存儲開銷相似，且都近似為Fortress的一半，且它們與實際數據的大小成正比關系，隨著數據塊數的增加，它們也線性增加.這些算法的存儲開銷差別主要體現在數據標簽的存儲量上.由于在Fortress中，云存儲提供者除了要保存數據所有者計算的一套標簽外，還要保存驗證者計算的一套標簽，在相同數據塊數量和每個標簽大小相同時，存儲總量增加了1倍.

Fig. 6 Storage cost圖6 存儲開銷

3) 傳輸開銷

傳輸開銷指的是數據驗證過程中各驗證方之間所產生的驗證數據傳輸量.3種算法的實驗結果如圖7所示.可以看出，CIVR和W-POR的傳輸開銷都比Fortress的小，且CIVR略微高于W-POR.在驗證傳輸開銷的構成中，主要有數據塊標簽的傳輸量，以及驗證時各種驗證參數和驗證證據的傳輸量.其中，Fortress需要傳輸2套標簽，所以傳輸量會比其他2個算法接近高出一倍.此外，由于在CIVR和Fortress在驗證時都需要傳輸2對證據(或標簽)，因此，它們這部分的傳輸量都要高于W-POR.但由于批量處理集成后的2對證據(或標簽)的傳輸量非常小，其大小近似于一個數據塊的標簽大小，所以相對于W-POR的傳輸量增加是可以忽略的.

Fig. 7 Transmission cost圖7 傳輸開銷

4) 驗證的可靠性

驗證的可靠性指的是驗證者提供的所有驗證結果中，可以確保驗證結果具有可靠性的數量占接受驗證的數據量的比值.讓在接受驗證的數據塊中都存在云存儲提供者和驗證者的合謀欺騙，在此情況下3種算法的實驗結果如圖8所示.可以看出，CIVR和Fortress可以達到100%，而W-POR算法為0.這主要是因為CIVR和Fortress不僅能分別識別云存儲提供者的不可信驗證結果，而且還能識別驗證者的不可信驗證結果；然而，W-POR只能抵御公開數據完整性驗證中不可信云存儲提供者的欺騙攻擊.

Fig. 8 Reliability of verification results圖8 驗證結果的可靠性

綜上所述，CIVR結合了W-POR和Fortress的優點，且避免了Fortress由于增加了1套數據標簽和日志文件的額外存儲量.此外，CIVR在密鑰的管理上也區別于Fortress.在Fortress中，當驗證者在接受數據所有者的質疑時，需要公開自己的私鑰而使得所有上傳到云存儲提供者空間中的數據標簽失效.而CIVR的私鑰一直不被公開，所以安全性更高.

6 總 結

為避免數據完整性驗證中因驗證結果被偽造欺騙而導致驗證結果的不可靠問題，本文提供一種數據驗證結果的檢測算法以抵御這種不可信驗證結果的偽造欺騙攻擊，算法中引入雙驗證證據來交叉檢測驗證結果，并構建檢測樹來保證檢測的可靠性.該算法在驗證過程中進一步保證了驗證的可靠性.未來，我們將進一步優化算法提高算法的驗證能力.

[1]Mell P, Grance T. NIST definition of cloud computing, 800-145[R]. Gaithersburg, MD: NIST Special Publication, 2016

[2]Li Mingqiang, Shu Jiwu. Preventing silent data corruptions from propagating during data reconstruction[J]. IEEE Trans on Computers, 2010, 59(12): 1611-1624

[3]Deswarte Y, Quisquater J, Sa?dane A. Remote integrity checking[C]Proc of the 6th Working Conf on Integrity and Internal Control in Information Systems(IICIS’04). London: Chapman amp; Hall, 2004: 1-11

[4]Ren Kui, Wang Cong, Wang Qian. Security challenges for the public cloud[J]. IEEE Internet Computing, 2012, 16(1): 69-73

[5]Ateniese G, Burns R, Curtmola R, et al. Provable data possession at untrusted Stores[C]Proc of the 14th ACM Conf on Computer and Communications Security. New York: ACM, 2007: 598-609

[6]Juels A, Burton S. Pors: Proofs of retrievability for large files[C]Proc of the 14th ACM Conf on Computer and Communications Security. New York: ACM, 2007: 584-597

[7]Hovav S, Brent W. Compact proofs of retrievability[C]Proc of the 14th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2008: 90-107

[8]Erway C, Küp?ü A, Papamanthou C, et al. Dynamic provable data possession[C]Proc of the 16th ACM Conf on Computer and Communications Security. New York: ACM, 2009: 213-222

[9]Wang Qian, Wang Cong, Ren Kui, et al. Enabling public auditability and data dynamics for storage security in cloud computing[J]. IEEE Trans on Parallel and Distributed Systems, 2011, 22(5): 847-859

[10]Wang Cong, Chow S, Wang Qian, et al. Privacy-preserving public auditing for secure cloud storage[J]. IEEE Trans on Computers, 2013, 62( 2): 362-375

[11]Zhu Yan, Hu Hongxin, Ahn G, et al. Cooperative provable data possession for integrity verification in multicloud storage[J]. IEEE Trans on Parallel and Distributed Systems, 2012, 23(12): 2231-2244

[12]Yang Kan, Jia Xiaohua. An efficient and secure dynamic auditing protocol for data storage in cloud computing[J]. IEEE Trans on Parallel and Distributed Systems, 2013, 24(9): 1717-1726

[13]Wang Boyang, Li Baochun, Li Hui. Public auditing for shared data with efficient user revocation in the cloud[C]Proc of IEEE INFOCOM. Piscataway, NJ: IEEE, 2013: 2904-2912

[14]Xu Guangwei, Yang Yanbin, Yan Cairong, et al. A probabilistic verification algorithm against spoofing attacks on remote data storage[J]. International Journal of High Performance Computing and Networking, 2016, 9(3): 218-229

[15] Ren Yongjun, Yang Zhengqi, Wang Jin, et al. Attributed based provable data possession in public cloud storage[C]Proc of the 10th Int Conf on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP). Piscataway, NJ: IEEE, 2014: 710-713

[16]Yu Xiaojun, Wen Qiaoyan. MF-PDP: Multi-function provable data possession scheme in cloud computing[C]Proc of the 3rd IEEE Int Conf on Cloud Computing and Intelligence Systems. Piscataway, NJ: IEEE, 2014: 597-603

[17] Ren Yongjun, Shen Jian, Wang Jin, et al. Outsourced data tagging via authority and delegable auditing for cloud storage[C]Proc of the Int Carnahan Conf on Security Technology (ICCST). Piscataway, NJ: IEEE, 2015: 131-134

[18] Thao T, Kho L, Lim A. SW-POR: A novel POR scheme using Slepian-Wolf coding for cloud storage[C]Proc of Ubiquitous Intelligence and Computing, the 11th IEEE Int Conf on Autonomic and Trusted Computing, and the 14th IEEE Int Conf on Scalable Computing and Communications. Piscataway, NJ: IEEE, 2014: 464-472

[19]Huang Kun, Liu Jian, Xian Ming, et al. Enabling dynamic proof of retrievability in regenerating-coding-based cloud storage[C]Proc of IEEE Int Conf on Communications Workshops (ICC). Piscataway, NJ: IEEE, 2014: 712-717

[20]Omote K, Thao T. A new efficient and secure POR scheme based on network coding[C]Proc of the 28th IEEE Int Conf on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2014: 98-105

[21]Liu Dongxi, Zic J. Proofs of encrypted data retrievability with probabilistic and homomorphic message authenticators[C]Proc of IEEE TrustcomBigDataSEISPA, Vol1. Piscataway, NJ: IEEE, 2015: 897-904

[22]Liu Chang, Yang Chi, Zhang Xuyuan, et al. External integrity verification for outsourced big data in cloud and IoT: A big picture[J]. Future Generation Computer Systems, 2015, 49: 58-67

[23]Armknecht F, Bohli J, Karame G, et al. Outsourced proofs of retrievability[C]Proc of ACM SIGSAC Conf on Computer and Communications Security (CCS’14). New York: ACM, 2014: 831-843

[24]Sookhak M, Talebian H, Ahmed E, et al. A review on remote data auditing in single cloud server: Taxonomy and open issues[J]. Journal of Network and Computer Applications, 2014, 43(5): 121-141

[25] Tan Shuang, He Li, Chen Zhikun, et al. A method of provable data integrity based on lattice in cloud storage[J]. Journal of Computer Research and Development, 2015, 52(8): 1862-1872 (in Chinese) (譚霜, 何力, 陳志坤, 等. 云存儲中一種基于格的數據完整性驗證方法[J]. 計算機研究與發展, 2015, 52(8): 1862-1872)

[26]Merkle R. A digital signature based on a conventional encryption function[G]LNCS 293: Proc of Advances in Cryptology—CRYPTO’87. Berlin: Springer, 1987: 369-378

XuGuangwei, born in 1969. PhD, associate professor. His main research interests include the data integrity verification and data privacy protection, parallel and distributed computing, QoS of the wireless and sensor networks.

BaiYanke, born in 1993. Master candidate. Her main research interests include the verification of data integrity and data security.

YanCairong, born in 1978. PhD, associate professor. Her main research interests include parallel and distributed computing, cloud computing, and big data processing.

YangYanbin, born in 1991. Master candidate. His main research interests include the verification of data integrity and data security.

HuangYongfeng, born in 1971. PhD, associate professor. His main research interests include parallel and distributed computing, and big data processing.

CheckAlgorithmofDataIntegrityVerificationResultsinBigDataStorage

Xu Guangwei, Bai Yanke, Yan Cairong, Yang Yanbin, and Huang Yongfeng

(College of Computer Science and Technology, Donghua University, Shanghai 201620)

Cloud storage is one of the most widely used applications in cloud computing. It makes it convenient for users to access and share the data yet producing data integrity issues such as data corruption and loss. The existing remote data verification algorithms are based on the trusted third party who works as a public verifier to verify the outsourced data integrity. In this case, the verifier has a potential threat to provide false verification results, which cannot ensure the reliability of data verification. Especially, the situation can be even worse while the verifier is in collusion with the cloud storage providers. In this paper, we propose a check algorithm of incredible verification results in data integrity verification (CIVR) to resist the attacks of forgery and deception in incredible verification results. We utilize double verification proofs, i.e., integrity verification proof and incredible check proof, to execute the cross check. The integrity verification proof is to verify whether the data are intact. The incredible check proof is to check whether the verification results are correct. Moreover, the algorithm constructs the check tree to ensure the reliability of verification results. Theoretical analysis and simulation results show that the proposed algorithm can guarantee the reliability of verification results and increase the efficiency by improving the valid verification.

data integrity verification; incredible verification results; verification results checking; dual proofs; check tree

2016-11-15；

2017-06-27

上海自然科學基金項目(15ZR1400900，15ZR1400300，16ZR1401100)；上海市教育科研項目(C160076)；國家自然科學基金項目(61402100,61772128)；同濟大學高密度人居環境生態與節能教育部重點實驗室種子基金項目；東華大學中央高校基本科研業務費專項資金項目(2232015D3-29)

This work was supported by the Natural Science Foundation of Shanghai (15ZR1400900, 15ZR1400300, 16ZR1401100), Shanghai Education and Scientific Research Project (C160076), the National Natural Science Foundation of China (61402100, 61772128), the Key Laboratory of Ecology and Energy-Saving Study of Dense Habitat of Ministry of Education (Tongji University), and the Fundamental Research Funds for the Central Universities of Donghua University (2232015D3-29).

燕彩蓉(cryan@dhu.edu.cn)

TP391