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

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

0 引 言

隨著技術(shù)和分布式存儲(chǔ)系統(tǒng)的發(fā)展，研究者們對(duì)數(shù)據(jù)可檢索證明 （proof of retrievability，POR）和數(shù)據(jù)持有證明 （provable data possession，PDP）方案進(jìn)行了許多改進(jìn)和擴(kuò)展，以期達(dá)到更小的開銷，使其擁有支持動(dòng)態(tài)更新［1，2］、降 低 通 信 開 銷 和 支 持 無 限 驗(yàn) 證［3，4］以 及 公 開 驗(yàn) 證［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］冗余存儲(chǔ)用戶數(shù)據(jù)的分布式系統(tǒng)中。

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

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

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

1.1 再生碼

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

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

1.2 研究現(xiàn)狀

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

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

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

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

2.1 基于MD5的驗(yàn)證方案

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

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

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

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

k：對(duì)稱加密密鑰；

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

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

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

對(duì)基于再生碼編碼的文件實(shí)施的分片計(jì)算MD5并存儲(chǔ)的處理過程如圖1所示。

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

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

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

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

2.2.1 計(jì)算MD5標(biāo)簽

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

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

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

算法1：每個(gè)分片的加密MD5生成算法。

2.2.2 存儲(chǔ)文件MD5值

傳統(tǒng)的POR 和PDP 方法在驗(yàn)證數(shù)據(jù)完整性時(shí)，通常將證據(jù)數(shù)據(jù)保存在用戶本地，或者也將其上傳到云中，需要時(shí)再下載，增加了用戶的本地存儲(chǔ)負(fù)擔(dān)和管理風(fēng)險(xiǎn)，而存儲(chǔ)在云中需要為這些數(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值的映射存儲(chǔ)過程

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

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

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

2.3 完整性驗(yàn)證

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

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

算法3：完整性驗(yàn)證算法。

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

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

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

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

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

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

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

（2）節(jié)點(diǎn)f 對(duì)應(yīng)的數(shù)據(jù)矩陣向量為Rf。將每個(gè)節(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 個(gè)節(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 為對(duì)稱矩陣，因此有

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

4 分析與實(shí)驗(yàn)

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

4.1 訪問開銷

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

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

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

圖5 驗(yàn)證一個(gè)數(shù)據(jù)塊時(shí)平均訪問的塊數(shù)

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

4.2 可行性概率

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 存儲(chǔ)開銷和通信開銷

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

4.5 抗攻擊性

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

5 結(jié)束語

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

分析與實(shí)驗(yàn)結(jié)果表明，該方案有效對(duì)遠(yuǎn)端數(shù)據(jù)進(jìn)行了完整性驗(yàn)證，減小了用戶保存證據(jù)的存儲(chǔ)開銷和驗(yàn)證的通信開銷，系統(tǒng)修復(fù)帶寬低，同時(shí)方案也大大降低系統(tǒng)驗(yàn)證時(shí)被攻擊的概率。未來的工作中還可以加入第三方可信驗(yàn)證，在不向第三方泄露用戶數(shù)據(jù)的情況下，讓第三方代理用戶的驗(yàn)證工作，釋放用戶親自驗(yàn)證的負(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é)報(bào)，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）. ［于洋洋，虞慧群，范貴生.一種云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證方法 ［J］.華東理工大學(xué)學(xué)報(bào) （自然科學(xué)版），2013，39 （2）：211－216.］