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

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

(gwxu@dhu.edu.cn)

大數(shù)據(jù)存儲中數(shù)據(jù)完整性驗證結(jié)果的檢測算法

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

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

(gwxu@dhu.edu.cn)

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

數(shù)據(jù)完整性驗證；不可信驗證結(jié)果；驗證結(jié)果檢測；雙證據(jù)；檢測樹

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

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

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

2) 生成不可信檢測證據(jù)來判定數(shù)據(jù)驗證結(jié)果的正確性；

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

4) 利用雙證據(jù)來執(zhí)行交叉驗證以確保數(shù)據(jù)完整性驗證結(jié)果的可靠性.

1 相關(guān)工作

遠程數(shù)據(jù)完整性驗證隨著云存儲應(yīng)用的不斷普及，越來越受到科學(xué)界和工業(yè)界的關(guān)注.自從Ateniese等人[5]和Juels等人[6]分別提出PDP和POR驗證方案以來，出現(xiàn)了大量的遠程數(shù)據(jù)完整性驗證算法.

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

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

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

2 驗證模型與問題提出

2.1驗證模型

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

Fig. 1 Data verification model圖1 數(shù)據(jù)驗證模型圖

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

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

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

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

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

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

本文做了如下一些假設(shè)：

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

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

2.2對手模型

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

2.3問題提出

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

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

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

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

3 不可信驗證結(jié)果的檢測算法

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

3.1不可信驗證結(jié)果的檢測證據(jù)生成

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

定義1. 完整性驗證證據(jù). CSP接受DV的挑戰(zhàn)后，發(fā)送給DV的面向待驗證數(shù)據(jù)所生成的完整性擁有的驗證證據(jù)，被標記為P.

定義2. 不可信檢測證據(jù). CSP接受DV的挑戰(zhàn)后，發(fā)送給DO的面向DV的不可信驗證結(jié)果的檢測證據(jù), 被標記為P′.

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

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

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

其中，vi為p中選取的對應(yīng)于每個數(shù)據(jù)塊mi的一個隨機數(shù)，r為p中任意選取的隨機數(shù)，u為群G1中的一個元素，g2為群G2的生成元，R為挑戰(zhàn)標記.

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

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

3.2不可信驗證結(jié)果的檢測

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

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

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

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

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

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

3.3不可信驗證的檢測算法

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

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

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

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

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

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

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

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

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

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

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

數(shù)據(jù)完整性證據(jù)P1中的數(shù)據(jù)證據(jù)DP1計算公式為

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

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

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

此外，DV構(gòu)建驗證結(jié)果的檢測樹，并計算根節(jié)點的φ值，與Ri一起發(fā)送給DO.

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

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

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

φ′=φ，

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

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

3.4分段檢測的支持

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

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

1)DO計算相應(yīng)的數(shù)據(jù)塊mi的標簽為

檢測證據(jù)中數(shù)據(jù)證據(jù)的計算為

4 算法安全性分析

4.1檢測的正確性分析

檢測算法是否能夠?qū)?shù)據(jù)完整性的DV提供的驗證結(jié)果進行檢測，依賴于算法的正確性，即式(6)和式(7)是否成立.式(7)的正確性證明如下.

證明.

證畢.

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

4.2抵御攻擊能力分析

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

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

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

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

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

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

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

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

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

5 實驗分析

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

1) 驗證能力

Fig. 5 Verification capability圖5 驗證能力

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

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

2) 存儲開銷

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

Fig. 6 Storage cost圖6 存儲開銷

3) 傳輸開銷

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

Fig. 7 Transmission cost圖7 傳輸開銷

4) 驗證的可靠性

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

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

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

6 總 結(jié)

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

[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) (譚霜, 何力, 陳志坤, 等. 云存儲中一種基于格的數(shù)據(jù)完整性驗證方法[J]. 計算機研究與發(fā)展, 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

上海自然科學(xué)基金項目(15ZR1400900，15ZR1400300，16ZR1401100)；上海市教育科研項目(C160076)；國家自然科學(xué)基金項目(61402100,61772128)；同濟大學(xué)高密度人居環(huán)境生態(tài)與節(jié)能教育部重點實驗室種子基金項目；東華大學(xué)中央高?；究蒲袠I(yè)務(wù)費專項資金項目(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