基于再生碼的數(shù)據(jù)完整性驗證及恢復(fù)

阮春陽，李 倫，孟慧平，魯麗萍，鄭志蘊(yùn)＋

（1.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001；2.河南財政稅務(wù)高等?？茖W(xué)校 信息工程系，河南 鄭州450002）

0 引 言

隨著技術(shù)和分布式存儲系統(tǒng)的發(fā)展，研究者們對數(shù)據(jù)可檢索證明 （proof of retrievability，POR）和數(shù)據(jù)持有證明 （provable data possession，PDP）方案進(jìn)行了許多改進(jìn)和擴(kuò)展，以期達(dá)到更小的開銷，使其擁有支持動態(tài)更新［1，2］、降 低 通 信 開 銷 和 支 持 無 限 驗 證［3，4］以 及 公 開 驗 證［5］等功能，MR－PDP［6］和HAIL［7］還將PDP和POR 從單節(jié)點(diǎn)的應(yīng)用擴(kuò)展到多服務(wù)的數(shù)據(jù)證明上。遠(yuǎn)端數(shù)據(jù)證明技術(shù)被廣泛應(yīng)用在依靠副本技術(shù)［6］和糾刪碼編碼技術(shù)［8，9］冗余存儲用戶數(shù)據(jù)的分布式系統(tǒng)中。

用戶不僅要檢測出數(shù)據(jù)是否出錯，更重要的是出錯數(shù)據(jù)能否有效地恢復(fù)。當(dāng)前云存儲系統(tǒng)使用副本和糾刪碼兩種方法對用戶數(shù)據(jù)進(jìn)行冗余存儲來保證系統(tǒng)的可靠性，修復(fù)時都需要傳輸整個文件，占用大量網(wǎng)絡(luò)資源，給分布式系統(tǒng)數(shù)據(jù)中心增加了巨大的壓力，造成的網(wǎng)絡(luò)擁堵也嚴(yán)重降低了用戶對數(shù)據(jù)讀取性能。因此，利用再生碼進(jìn)行數(shù)據(jù)完整性驗證成為當(dāng)前研究的熱點(diǎn)。

基于再生碼的數(shù)據(jù)完整性驗證及恢復(fù)是將再生碼和MD5技術(shù)結(jié)合，對存儲文件采用分片計算MD5 的方法，獲得每個分片的證據(jù)MD5，利用MD5 的唯一性，通過對比當(dāng)前各個數(shù)據(jù)片的MD5計算值與保存值，驗證文件數(shù)據(jù)是否完整。該方法對文件實施分片計算MD5，并將各個分片的MD5加密后兩次隨機(jī)存儲在各個節(jié)點(diǎn)上。當(dāng)檢測到節(jié)點(diǎn)失效時，返回失效節(jié)點(diǎn)的個數(shù)和位置，依據(jù)PM－MSR 再生碼的編碼特點(diǎn)，給出恢復(fù)出錯數(shù)據(jù)塊的方法。

1 相關(guān)技術(shù)和研究

1.1 再生碼

再生碼 （regenerating codes，RC）是Dimakis等提出的一種基于網(wǎng)絡(luò)的新型糾刪碼，其參數(shù)表示為 ｛［n，k，d］，（α，β，B）｝，將大小為B 的文件編碼存儲在n 個節(jié)點(diǎn)上，冗余度為n／k，每個節(jié)點(diǎn)存儲α數(shù)據(jù)量，修復(fù)節(jié)點(diǎn)時連接任意存活的d （k≤d≤n－1，系統(tǒng)節(jié)點(diǎn)k 為修復(fù)節(jié)點(diǎn)的最小連接個數(shù)）個節(jié)點(diǎn)，每個節(jié)點(diǎn)的下載量為β （β≤α），節(jié)點(diǎn)的修復(fù)帶寬為γ＝d·β。PM－MSR 編碼方案是Rashmi等［10］給出RC碼的最小存儲量方案，可以實現(xiàn)對損壞節(jié)點(diǎn)的精確修復(fù)。該方案中，令β＝t，取d＝2k－2，則B＝k×（k－1）×t，α＝（k－1）×t。

使用傳統(tǒng)的糾刪碼，要修復(fù)任何一個節(jié)點(diǎn)，系統(tǒng)都需要先恢復(fù)出整個文件然后再生成待修復(fù)節(jié)點(diǎn)數(shù)據(jù)。再生碼充分利用網(wǎng)絡(luò)傳輸?shù)奶匦?，減少連接的幫助節(jié)點(diǎn)的個數(shù)，使用更小的修復(fù)帶寬，只需要對小于原文件的數(shù)據(jù)塊進(jìn)行線性處理后，便可以精確恢復(fù)出失效節(jié)點(diǎn)的數(shù)據(jù)。Dimakis等［11］經(jīng)過實驗驗證，對于1 M 大小的文件，在系統(tǒng)節(jié)點(diǎn)k＝7、冗余編碼達(dá)到n＝14，并且系統(tǒng)中存活節(jié)點(diǎn)最多n－1的時候，在傳統(tǒng)的MDS糾刪碼的系統(tǒng)中，恢復(fù)數(shù)據(jù)需要新節(jié)點(diǎn)傳輸與原始文件大小相等的1 M 數(shù)據(jù)量，而使用再生碼編碼的系統(tǒng)，新節(jié)點(diǎn)需要的下載量只有0.16 M，使帶寬消耗節(jié)約了84%，大大減小了恢復(fù)節(jié)點(diǎn)的帶寬。云存儲最主要的應(yīng)用是對海量數(shù)據(jù)的歸檔存儲，采用再生碼進(jìn)行冗余存儲，可以在較小冗余度下有效保證系統(tǒng)的可靠性，節(jié)約存儲空間的消耗，并且大大降低系統(tǒng)因修復(fù)造成的帶寬浪費(fèi)。

1.2 研究現(xiàn)狀

再生碼因其極小的修復(fù)帶寬而受到研究者們的關(guān)注，并被廣泛應(yīng)用到分布式系統(tǒng)的研究中。針對再生碼的特點(diǎn)，設(shè)計不同的存儲方案和數(shù)據(jù)完整性驗證方案，對于驗證分布式系統(tǒng)數(shù)據(jù)安全性是很有意義的。傳統(tǒng)的方案在驗證文件完整性時，通常將整個文件進(jìn)行某種哈希計算，將結(jié)果加密保存在本地，驗證時服務(wù)器對被挑戰(zhàn)的數(shù)據(jù)塊做同樣的哈希函數(shù)計算，并將得到的哈希值與本地保存的哈希值進(jìn)行對比，帶來額外的計算開銷和本地存儲開銷。多次驗證時，每次都需要重新計算整個文件的哈希值，這將給系統(tǒng)增加嚴(yán)重的計算負(fù)擔(dān)，且存在本地證據(jù)數(shù)據(jù)丟失的風(fēng)險。RDC－NC方案［12］將傳統(tǒng)的基于單節(jié)點(diǎn)數(shù)據(jù)完整性驗證方案直接擴(kuò)展為基于再生碼編碼的多節(jié)點(diǎn)分布式存儲系統(tǒng)的應(yīng)用。該方案將文件分塊編碼的同時，對每個編碼塊生成證據(jù)挑戰(zhàn)標(biāo)簽和修復(fù)標(biāo)簽，服務(wù)器利用請求塊和相應(yīng)的標(biāo)簽生成證據(jù)作為驗證和修復(fù)工作的依據(jù)。但這些證據(jù)的生成是基于RSA （非對稱加密算法）的模指運(yùn)算，在有限域上進(jìn)行以文件數(shù)據(jù)塊為指數(shù)的運(yùn)算，并且RDC－NC 方案依靠用戶端進(jìn)行編碼生成和證據(jù)計算，給用戶服務(wù)器帶來巨大的計算負(fù)擔(dān)，并且還將消耗用戶本地存儲空間來保存相當(dāng)量的證據(jù)數(shù)據(jù)。文獻(xiàn) ［13］中，作者簡化了用戶保存文件的操作，將文件的編碼計算操作和驗證工作都移交給云服務(wù)器，利用網(wǎng)絡(luò)編碼F－MSR （functional minimum－storage regenerating code）實現(xiàn)對數(shù)據(jù)完整性的驗證，利用F－MSR包含糾錯碼的特性及其編碼矩陣秩的特征來驗證數(shù)據(jù)塊，但每驗證一個數(shù)據(jù)塊需要連接其它k 個數(shù)據(jù)塊，如果對所有數(shù)據(jù)塊驗證時，則循環(huán)操作將浪費(fèi)系統(tǒng)資源。

MD5是一種散列函數(shù)，被廣泛應(yīng)用在計算機(jī)安全領(lǐng)域，經(jīng)過不可逆的信息轉(zhuǎn)換計算，可以為任何格式、任何大小和任意數(shù)量的文件數(shù)據(jù)生成一個唯一的 “數(shù)字指紋”，從而將任意長度的字符串?dāng)?shù)據(jù)映射成為僅128位長的長整型數(shù)據(jù)［14］。隨著文件內(nèi)容發(fā)生變動，所對應(yīng)的文件MD5值也發(fā)生相應(yīng)的變化，因此，可以用文件的MD5特性來驗證文件是否丟失、篡改，從而驗證文件的完整性。

基于再生碼的數(shù)據(jù)完整性驗證及恢復(fù)將MD5應(yīng)用到再生碼的驗證方案中，采用分片計算MD5的方式，避免存儲預(yù)處理階段計算整個文件而帶來的極大的計算開銷，并且以后每次驗證時只涉及要驗證的數(shù)據(jù)塊的計算?？紤]到用戶的存儲負(fù)擔(dān)和證據(jù)丟失風(fēng)險，將生成的證據(jù)MD5偽隨機(jī)存儲該文件的各個數(shù)據(jù)節(jié)點(diǎn)上。

2 基于再生碼的數(shù)據(jù)完整性驗證

2.1 基于MD5的驗證方案

驗證方案首先將文件按照PM－MSR 再生碼編碼方案進(jìn)行編碼后，對各個編碼分片分別計算其MD5值并利用偽隨機(jī)函數(shù)將證據(jù)數(shù)據(jù)雙重映射到不同數(shù)據(jù)節(jié)點(diǎn)上保存。

驗證方案中使用參數(shù)說明如下：

N：文件的分片數(shù)，將文件按照編碼參數(shù) ［n，k，d］的PM－MSR 再生碼方案進(jìn)行分片，得到N＝k×（k－1）＋1；

Mi：第i個數(shù)據(jù)分片的指紋標(biāo)簽；

k：對稱加密密鑰；

gm：標(biāo)簽生成密鑰gm，Mi中的一個隨機(jī)元素；

σ（·）： ｛0，1｝k× ｛1，2，…，N｝→ ｛1，2，…，N｝，偽隨機(jī)放置函數(shù)PRP （pseudo random permutation），確定隨機(jī)數(shù)據(jù)塊的位置；

Sig（·）：｛0，1｝＊→M，無密鑰MD5計算函數(shù)，為每個數(shù)據(jù)分片生成MD5標(biāo)簽。

對基于再生碼編碼的文件實施的分片計算MD5并存儲的處理過程如圖1所示。

圖1 再生碼分片數(shù)據(jù)標(biāo)簽存儲過程

由圖1所示過程可知，首先將原文件分為N 個分片，對每個文件分片bi計算其對應(yīng)的MD5值Mi，然后將每個Mi隨機(jī)存儲在其它數(shù)據(jù)分片上，也即每個存儲節(jié)點(diǎn)上隨機(jī)保存著除本節(jié)點(diǎn)數(shù)據(jù)分片外的兩個其它數(shù)據(jù)分片的MD5值。

2.2 證據(jù)生成與保存

基于MD5的驗證方案通過對比當(dāng)前保存文件的MD5計算值與原始文件的MD5 保存值來進(jìn)行驗證文件的完整性。因此，文件上傳到服務(wù)器的同時需要進(jìn)行證據(jù)MD5的計算和保存。

2.2.1 計算MD5標(biāo)簽

為了保障數(shù)據(jù)分片的MD5標(biāo)簽的安全存儲，需要將其加密保存。使用指紋生成函數(shù)Sig（·）為每個數(shù)據(jù)分片生成獨(dú)一無二的數(shù)字指紋，得到每個分片唯一的MD5值。bi表示文件的第i個分片，1≤i≤k×（k－1）＋1，bi所對應(yīng)的指紋標(biāo)簽用Mi表示。MD5數(shù)據(jù)指紋生成過程如圖2所示。

圖2 MD5數(shù)據(jù)指紋生成過程

算法實現(xiàn)函數(shù)為：TagGen（G（f），K，gm）→M 。其中G（f）為 文 件 信 息，包 含 文 件 名 和 分 塊 數(shù)，G（f）＝G（fileName N），訪問用戶在使用相同加密參數(shù)上傳數(shù)據(jù)時，攻擊者Adversary利用獲得的其它文件加密信息來破解該文件的信息。輸出參數(shù)M 為數(shù)據(jù)標(biāo)簽的集，M ＝｛M1，M2，M3，…，MN｝。

算法1：每個分片的加密MD5生成算法。

2.2.2 存儲文件MD5值

傳統(tǒng)的POR 和PDP 方法在驗證數(shù)據(jù)完整性時，通常將證據(jù)數(shù)據(jù)保存在用戶本地，或者也將其上傳到云中，需要時再下載，增加了用戶的本地存儲負(fù)擔(dān)和管理風(fēng)險，而存儲在云中需要為這些數(shù)據(jù)重新定位、管理元數(shù)據(jù)等，也增加了云服務(wù)器的負(fù)擔(dān)。本文利用偽隨機(jī)函數(shù)將證據(jù)數(shù)據(jù)映射到服務(wù)器節(jié)點(diǎn)上，并直接保存在文件數(shù)據(jù)片上。證據(jù)的存放策略如圖3所示。

圖3 數(shù)據(jù)片MD5值的映射存儲過程

圖3所示的存儲過程中，使用標(biāo)簽生成算法得到文件的數(shù)據(jù)分片標(biāo)簽集合M，使用偽隨機(jī)放置函數(shù)將每個MD5標(biāo)簽隨機(jī)放置在兩個不同的節(jié)點(diǎn)分片bi上保存，減少了單獨(dú)管理證據(jù)數(shù)據(jù)的工作量。同時為了防止由于數(shù)據(jù)節(jié)點(diǎn)損壞導(dǎo)致的證據(jù)數(shù)據(jù)破壞，采用一個MD5值兩次隨機(jī)映射分別保存在兩個數(shù)據(jù)分片中，隨機(jī)映射也有效抵制了服務(wù)器節(jié)點(diǎn)相互欺騙的風(fēng)險。在保存之前還應(yīng)對每個標(biāo)簽數(shù)據(jù)做處理：T（Mi）＝T（Index Mi），隱形的將其所對應(yīng)的分片索引信息加入到標(biāo)簽中。

算法2：MD5的偽隨機(jī)存儲算法。

數(shù)據(jù)指紋MD5生成并存儲完畢，將整個數(shù)據(jù)分片存儲元數(shù)據(jù)發(fā)送給元數(shù)據(jù)服務(wù)器，而用戶只需要保存k和gm等加密參數(shù)，方便后期的數(shù)據(jù)驗證。

2.3 完整性驗證

當(dāng)用戶的數(shù)據(jù)長久存儲在云存儲服務(wù)器上而又不常訪問的情況下，用戶便可以根據(jù)自己保存的加密參數(shù)對存儲在云中的數(shù)據(jù)完整性進(jìn)行驗證。用戶服務(wù)器發(fā)送要驗證的文件和數(shù)據(jù)塊索引的挑戰(zhàn)信息s（f，Ref），云服務(wù)器接收到s后，首先驗證用戶的權(quán)限，通過權(quán)限驗證后，將存儲的MD5標(biāo)簽值與對該數(shù)據(jù)塊重新計算的MD5值返回給用戶，用戶通過保存的k 和gm計算對比MD5值的一致性，從而實現(xiàn)對文件數(shù)據(jù)完整性的驗證。

實現(xiàn)算法為：TagVeri（fileName，ref，k，gm）→ （result，location）。result 返 回 數(shù) 據(jù) 的 驗 證 結(jié) 果，result＝TRUE時，代表數(shù)據(jù)完好無損，損壞位置location的值為0；result＝FLASE 時，代表數(shù)據(jù)塊有損壞，location 返回?fù)p壞數(shù)據(jù)塊的位置集合。

算法3：完整性驗證算法。

當(dāng)用戶輸入的挑戰(zhàn)塊參數(shù)ref 為0 時，對所有的塊都進(jìn)行完整性驗證。循環(huán)訪問數(shù)據(jù)塊，計算數(shù)據(jù)塊的MD5、取回保存在數(shù)據(jù)塊中的其它證據(jù)MD5，并將其按照其所對應(yīng)的塊索引號寫入相應(yīng)的對比數(shù)組中，循環(huán)過程見表1。

用戶通過得到的返回信息 （result，location）可以判斷自己的文件是否損壞，以及損壞情況下的損壞位置，以便于及時對損壞數(shù)據(jù)塊進(jìn)行修復(fù)。

表1 循環(huán)計算MD5并獲取證據(jù)

3 數(shù)據(jù)的恢復(fù)

當(dāng)用戶檢測到存儲在遠(yuǎn)端的數(shù)據(jù)出錯時，最關(guān)心的就是數(shù)據(jù)能不能恢復(fù)，恢復(fù)效率有多高，是否能精確修復(fù)。根據(jù)2.3節(jié)的敘述，當(dāng)檢測到系統(tǒng)中有節(jié)點(diǎn)失效或出錯時，系統(tǒng)返回出錯節(jié)點(diǎn)的位置，依靠PM＿M(jìn)SR 再生碼的特點(diǎn)，在節(jié)約帶寬的情況下精確修復(fù)損壞數(shù)據(jù)塊。使用PM ＿M(jìn)SR 編碼時，在修復(fù)失效數(shù)據(jù)節(jié)點(diǎn)時，需要連接d 個幫助節(jié)點(diǎn)，其中d ＝2α。每個節(jié)點(diǎn)上存儲的編碼向量Ci＝Ri·D（b），與數(shù)據(jù)矩陣R 中的向量Ri相關(guān)，修復(fù)失效節(jié)點(diǎn)f時，利用數(shù)據(jù)矩陣秩rank（R）＝2α的特性對數(shù)據(jù)塊f 進(jìn)行精確修復(fù)。修復(fù)過程如圖4所示。

圖4 連接任意d個節(jié)點(diǎn)恢復(fù)節(jié)點(diǎn)f

（1）從剩下存活的節(jié)點(diǎn)當(dāng)中任取d 個節(jié)點(diǎn)｛h1，h2，h3，…，hd－1，hd｝，每個節(jié)點(diǎn)的編碼向量為Ch1＝Rh1·D（b）。

（2）節(jié)點(diǎn)f 對應(yīng)的數(shù)據(jù)矩陣向量為Rf。將每個節(jié)點(diǎn)的編碼向量Ch1與在節(jié)點(diǎn)內(nèi)做運(yùn)算Ch1·后，將結(jié)果上傳給要修復(fù)的新數(shù)據(jù)節(jié)點(diǎn)Q。

（3）新節(jié)點(diǎn)fnew接收到d 個節(jié)點(diǎn)上傳的修復(fù)信息，將它們組成（d×1）的矩陣W 并開始進(jìn)行修復(fù)操作。

由于Ch1＝Rh1D（b，并且D（b）＝［XY］T，因此有

也即M ＝Rd×2αD（b）＝R2α×2αD（b）。rank（R）＝2α可知矩陣R 中任意2α行線性無關(guān)，即R2α×2α可逆。因此在矩陣M 的左側(cè)乘以R2α×2α的逆矩陣可得

由于X 和Y 為對稱矩陣，因此有

也即節(jié)點(diǎn)f 的編碼向量Cf＝RfD（b）＝（R·M）T。至此新節(jié)點(diǎn)fnew對損壞節(jié)點(diǎn)f 完成精確修復(fù)。

4 分析與實驗

為了檢驗方案的可行性和有效性，采用分析加實驗的方式，分別對基于MD5的方案的訪問開銷、可行性概率、驗證準(zhǔn)確度和修復(fù)帶寬、存儲開銷和通信開銷，以及抵抗攻擊性能等方面進(jìn)行分析驗證。

4.1 訪問開銷

采用 ［n，k，d］編碼時，對于FMSR－DIP 方 案［13］，每驗證一個數(shù)據(jù)塊都需要訪問剩余節(jié)點(diǎn)中任意k 個節(jié)點(diǎn)做輔助。而使用本文中基于MD5的方法驗證時，將每個分片的消息摘要MD5使用偽隨機(jī)函數(shù)兩次隨機(jī)存儲在n 個分片上，每個分片不保存自己的MD5，即對于數(shù)據(jù)塊Bi來說，數(shù)據(jù)塊的證據(jù)Mi不會存儲在Bi上，則訪問是從剩下的n－1個數(shù)據(jù)分片上來查找其MD5值。此時對于數(shù)據(jù)分片i來說要找到其所對應(yīng)的Mi，訪問數(shù)據(jù)分片的平均個數(shù)Vi為

根據(jù)式 （4），計算不同的參數(shù)n 和k 所對應(yīng)的編碼方案所需要平均訪問的數(shù)據(jù)塊數(shù)如圖5所示。

從圖5中也可以看出，相同編碼參數(shù)下隨機(jī)驗證一個數(shù)據(jù)塊的完整性時，F(xiàn)MSR－DIP 方案中需要訪問的數(shù)據(jù)塊

圖5 驗證一個數(shù)據(jù)塊時平均訪問的塊數(shù)

數(shù)要遠(yuǎn)遠(yuǎn)多于基于MD5 實現(xiàn)的再生碼數(shù)據(jù)完整性驗證方案，并且FMSR－DIP方案的平均訪問塊數(shù)隨著編碼系數(shù)k的增加而線性增加，而基于MD5的驗證方案的平均訪問塊數(shù)受參數(shù)n 和k 的共同影響，并不隨著k 的增加而明顯增加，平均訪問塊數(shù)相對穩(wěn)定且少。

4.2 可行性概率

當(dāng)進(jìn)行概率驗證時，用戶隨機(jī)挑戰(zhàn)某個數(shù)據(jù)節(jié)點(diǎn)的可用性，驗證能夠進(jìn)行的概率稱為方案的可行性概率。對于基于MD5的數(shù)據(jù)完整性驗證方案來說，要驗證一個數(shù)據(jù)塊，只需要在剩余的n－1個數(shù)據(jù)分片中找到保存的MD5證據(jù)數(shù)據(jù)；而FMSR－DIP方案中要驗證一個數(shù)據(jù)塊，需要保證剩余的n－1個數(shù)據(jù)塊中至少有k個數(shù)據(jù)塊時完好無損的。當(dāng)數(shù)據(jù)節(jié)點(diǎn)損壞的概率為p、編碼參數(shù)為 （n，k）時，只考慮驗證可以進(jìn)行而暫時忽略恢復(fù)工作能夠進(jìn)行時，基于MD5的再生碼驗證方案可行性概率為

而對于FMSR－DIP方案，系統(tǒng)能夠容忍n－k個節(jié)點(diǎn)失效，但是當(dāng)系統(tǒng)中出現(xiàn)n－k－1個節(jié)點(diǎn)失效時，便不能在進(jìn)行有效驗證了。FMSR－DIP 方案中驗證能夠進(jìn)行的可行性概率為

根據(jù)式 （5）和式 （6），參數(shù)n＝30時，兩種基于再生碼的驗證方案的可行性概率如圖6、圖7所示。

從圖6、圖7看出，對于不同的參數(shù)k，基于MD5的驗證方案的可行性概率并不受到影響，而只有當(dāng)節(jié)點(diǎn)損壞率p不同時，ζMD5 會有所不同：ζMD5 會隨著p 的增大而有所降低，但ζMD5 受影響而降低的幅度并不大；而ζFMSR－DIP 受參數(shù)k的影響大，會隨著k 增大而大幅度下降，并且當(dāng)p 增大時，ζFMSR－DIP 的下降轉(zhuǎn)折點(diǎn)對應(yīng)的k值越來越小，也即ζFMSR－DIP在k值較小的情況下便失去了其驗證可行性較高的優(yōu)勢，基于MD5的驗證方案驗證可行性保持穩(wěn)定，并且優(yōu)勢突出。

4.3 文件的驗證準(zhǔn)確度和修復(fù)帶寬

圖6 節(jié)點(diǎn)損壞率，p＝0.3

圖7 節(jié)點(diǎn)損壞率，p＝0.4

對整個文件驗證時，需分別計算每個文件塊的MD5，并且把計算結(jié)果和每個分片上保存的兩個其它數(shù)據(jù)分片的證據(jù)MD5，一同發(fā)送給驗證請求者。

當(dāng)參數(shù)n＝9、k＝5，局域網(wǎng)的帶寬為100Mbps，對分別對文件大小B＝200 M 和B＝500 M 的文件進(jìn)行編碼，文件的驗證時間見表2?？梢钥闯龉?jié)點(diǎn)出錯個數(shù)對檢測時間的影響并不大，大文件的數(shù)據(jù)塊較大，在驗證時需要計算MD5，因此大文件的驗證時間比小文件的驗證時間長些。

表2 不同失效節(jié)點(diǎn)下的檢測時間／s

能夠準(zhǔn)確檢驗文件的各個數(shù)據(jù)塊中的數(shù)據(jù)是否損壞或者被篡改的比例稱為驗證準(zhǔn)確度，用C 表示。系統(tǒng)檢測出節(jié)點(diǎn)損壞后進(jìn)行修復(fù)時的帶寬開銷稱為修復(fù)帶寬，用γ 表示。同樣用參數(shù)n＝9，k＝5，對B＝200 M 的文件進(jìn)行編碼存儲，人為隨機(jī)破壞其中幾個數(shù)據(jù)節(jié)點(diǎn)，驗證方案的準(zhǔn)確度C和修復(fù)帶寬γ。在不同失效節(jié)點(diǎn)個數(shù)下，其準(zhǔn)確度和修復(fù)帶寬見表3。

表3 方案的平均有效性和準(zhǔn)確度

按照編碼參數(shù)為 （9，5）進(jìn)行編碼的存儲系統(tǒng)，可以容忍系統(tǒng)損壞的節(jié)點(diǎn)個數(shù)為9－5＝4，此時系統(tǒng)可進(jìn)行修復(fù)，由表3看出驗證有效性在90%以上；而當(dāng)損壞節(jié)點(diǎn)個數(shù)較少時，系統(tǒng)的修復(fù)帶寬遠(yuǎn)小于文件的大小，只有當(dāng)損壞節(jié)點(diǎn)個數(shù)在可修復(fù)臨界點(diǎn)時，系統(tǒng)的修復(fù)帶寬較大，與文件大小相同。

4.4 存儲開銷和通信開銷

基于MD5的數(shù)據(jù)完整性驗證，將證據(jù)數(shù)據(jù)即每個數(shù)據(jù)片的MD5，存儲在其它數(shù)據(jù)分片上，而用戶只需要保存密鑰k和gm；驗證服務(wù)只需要從每個服務(wù)器上下載兩個MD5值以及請求驗證數(shù)據(jù)塊的MD5計算值，每個服務(wù)器節(jié)點(diǎn)之間的通信只有MD5值的信息，而單個MD5為128bit，所以服務(wù)器間的通信開銷僅僅為幾個字。

4.5 抗攻擊性

在0 節(jié)描述的MD5 存儲方案中，將每個數(shù)據(jù)塊的MD5都加密后隨機(jī)存儲在其它數(shù)據(jù)塊上，并且采用兩次隨機(jī)存儲的方法，當(dāng)系統(tǒng)受到Adversary的攻擊時，即便獲得了數(shù)據(jù)塊i的一個MD5存儲節(jié)點(diǎn)的信息，攻擊者沒有用戶的密鑰仍然不能獲得相應(yīng)的MD5信息，即使攻擊者惡意篡改了該塊上存儲的MD5值，系統(tǒng)中還有另外一個數(shù)據(jù)塊上存有備份，而攻擊者要準(zhǔn)確找到另一個存儲摘要信息Mi的概率1／（n－2），這將大大降低系統(tǒng)驗證時被攻擊的概率，有效保證了驗證結(jié)果的真實可靠性。

5 結(jié)束語

本文依據(jù)MD5可以唯一標(biāo)示字符串的特性，提出并實現(xiàn)基于PM＿M(jìn)SR 再生碼的數(shù)據(jù)完整性驗證方案。為減小系統(tǒng)的計算開銷，該方案突破傳統(tǒng)方式中對整個文件計算MD5，而是對文件實施分片計算MD5，并且將各個分片的MD5加密后兩次隨機(jī)存儲在各個節(jié)點(diǎn)上。當(dāng)檢測到節(jié)點(diǎn)失效時，返回失效節(jié)點(diǎn)的個數(shù)和位置，并且依據(jù)PM－MSR 再生碼的編碼特點(diǎn)，給出恢復(fù)出錯數(shù)據(jù)塊的方法。

分析與實驗結(jié)果表明，該方案有效對遠(yuǎn)端數(shù)據(jù)進(jìn)行了完整性驗證，減小了用戶保存證據(jù)的存儲開銷和驗證的通信開銷，系統(tǒng)修復(fù)帶寬低，同時方案也大大降低系統(tǒng)驗證時被攻擊的概率。未來的工作中還可以加入第三方可信驗證，在不向第三方泄露用戶數(shù)據(jù)的情況下，讓第三方代理用戶的驗證工作，釋放用戶親自驗證的負(fù)擔(dān)。

［1］Wang C，Wang Q，Ren K，et al.Privacy－preserving public auditing for data storage security in cloud computing ［C］／／INFOCOM，Proceedings IEEE，2010：1－9.

［2］Erway C，Küp üA，Papamanthou C，et al.Dynamic provable data possession ［C］／／Proceedings of the 16th ACM Conference on Computer and Communications Security，2009：213－222.

［3］CHEN Lanxiang.A homomorphic hashing based provable data possession ［J］.Journal of Electronics ＆Information Technology，2011，33 （9）：2199－2204 （in Chinese）.［陳蘭香.一種基于同態(tài)Hash的數(shù)據(jù)持有性證明方法 ［J］.電子與信息學(xué)報，2011，33 （9）：2199－2204.］

［4］Shacham H，Waters B.Compact proofs of retrievability ［G］.LNCS 5350：Advances in Cryptology－ASIACRYPT 2008.Springer Berlin Heidelberg，2008：90－107.

［5］Wang Q，Wang C，Li J，et al.Enabling public verifiability and data dynamics for storage security in cloud computing ［G］.LNCS 5789：Computer Security－ESORICS.Springer Berlin Heidelberg，2009：355－370.

［6］Curtmola R，Khan O，Burns R，et al.MR－PDP：Multiplereplica provable data possession ［C］／／28th International Conference on Distributed Computing Systems，2008：411－420.

［7］Bowers KD，Juels A，Oprea A.HAIL：A high－availability and integrity layer for cloud storage ［C］／／Proceedings of the 16th ACM Conference on Computer and Communications Security，2009：187－198.

［8］Wang C，Wang Q，Ren K，et al.Ensuring data storage security in cloud computing ［C］／／Proc 17th Int’l Workshop Quality of Service，2009.

［9］Liu G，Lou YX，Liu SL.Data integrity check and repair in distributed storage network ［C］／／3rd International Conference on Information，Electronic and Computer Science，2011.

［10］Rashmi KV，Shah NB，Kumar PV.Optimal exact－regenerating codes for distributed storage at the MSR and MBR points via a product－matrix construction ［J］.IEEE Transactions on Information Theory，2011，57 （8）：5227－5239.

［11］Dimakis AG，Godfrey PB，Wu Y，et al.Network coding for distributed storage systems［J］.IEEE Transactions on Information Theory，2010，56 （9）：4539－4551.

［12］Chen B，Curtmola R，Ateniese G，et al.Remote data checking for network coding－based distributed storage systems［C］／／Proceedings of the ACM Workshop On Cloud Computing Security Workshop，2010：31－42.

［13］Chen HCH，Lee PPC.Enabling data integrity protection in regenerating－coding－based cloud storage：Theory and implementation ［J］.IEEE Transactions on Parallel and Distributed Systems，2014，25 （2）：407－416.

［14］YU Yangyang，YU Huiqun，F(xiàn)AN Guisheng.A method of cloud storage data integrity verification ［J］.Journal of East China University of Science and Technology （Natural Science Edition），2013，39 （2）：211－216 （in Chinese）. ［于洋洋，虞慧群，范貴生.一種云存儲數(shù)據(jù)完整性驗證方法 ［J］.華東理工大學(xué)學(xué)報 （自然科學(xué)版），2013，39 （2）：211－216.］