王惠峰，李戰(zhàn)懷，張曉，孫鑒，趙曉南

(西北工業(yè)大學(xué)計算機學(xué)院，陜西西安 710072)

支持多代理的云存儲數(shù)據(jù)完整性審計方法

王惠峰，李戰(zhàn)懷，張曉，孫鑒，趙曉南

(西北工業(yè)大學(xué)計算機學(xué)院，陜西西安 710072)

由于云存儲服務(wù)面臨許多損壞數(shù)據(jù)的風(fēng)險，檢驗數(shù)據(jù)完整性便成為一個亟需解決的基本問題。數(shù)據(jù)持有性驗證（provable data possession，PDP）是檢驗云存儲數(shù)據(jù)完整性的重要方法。然而，在傳統(tǒng)的PDP模型中，單審計代理易造成單點故障并且易形成性能瓶頸。為此，提出了一種支持多代理的數(shù)據(jù)完整性審計方法（multi-proxies PDP，MP-PDP）。該方法采用循環(huán)鏈表管理多代理節(jié)點，使用審計隊列存儲文件的審計任務(wù)，實現(xiàn)了審計任務(wù)分發(fā)、節(jié)點監(jiān)控、失效節(jié)點切換和動態(tài)增加代理等功能，并且利用備份節(jié)點消除了系統(tǒng)的單點故障。實驗結(jié)果表明，MP-PDP有效減少了文件的審計執(zhí)行時間，并且能夠快速增刪審計代理。

多代理；數(shù)據(jù)持有性證明；數(shù)據(jù)完整性驗證；云存儲安全

隨著云計算技術(shù)的日益發(fā)展，公共云存儲服務(wù)已經(jīng)得到普遍的應(yīng)用，DropBox、Google Drive、金山快盤等公共云存儲產(chǎn)品的用戶數(shù)量飛速增長［1］。然而，云存儲服務(wù)面臨許多損壞數(shù)據(jù)的風(fēng)險，數(shù)據(jù)丟失事故層出不窮，如2011年3月，谷歌Gmail郵箱出現(xiàn)故障，造成大約15萬用戶的數(shù)據(jù)丟失［2］；2012年8月，國內(nèi)盛大云因物理服務(wù)器磁盤損壞造成用戶的數(shù)據(jù)部分丟失。數(shù)據(jù)存儲廠商EMC指出，64%的受調(diào)查企業(yè)在過去12個月中經(jīng)歷過數(shù)據(jù)丟失或宕機事故。及時發(fā)現(xiàn)數(shù)據(jù)損壞不僅可以打消用戶疑慮，還能為數(shù)據(jù)恢復(fù)贏得寶貴的時間。因此，驗證數(shù)據(jù)完整性是一個亟需解決的基本問題。

數(shù)據(jù)持有性驗證(provable data possession， PDP)［2-3］是檢驗云存儲數(shù)據(jù)完整性的重要方法。該方法采用抽樣策略，對云中的文件發(fā)起完整性驗證，在不下載整個文件的情況下，能夠及時識別出云中損壞數(shù)據(jù)的行為?；镜腜DP模型［2］僅僅允許文件所屬用戶執(zhí)行完整性檢測，但是用戶資源有限，執(zhí)行審計任務(wù)給用戶造成計算負(fù)擔(dān)，且基于數(shù)據(jù)擁有者的審計方式不利于云存儲審計服務(wù)的推廣。為了有效減少用戶的審計負(fù)擔(dān)，研究人員［4-7］提出基于第三方審計的公開驗證模型，利用公開密碼體制將審計任務(wù)委托給第三方審計者代為執(zhí)行。

然而，在傳統(tǒng)的PDP模型中，單審計代理易成為系統(tǒng)的性能瓶頸，限制了系統(tǒng)的橫向擴展；并且單代理節(jié)點易造成單點故障，審計代理崩潰將導(dǎo)致整個審計系統(tǒng)崩潰。

針對以上問題，本文提出了一種支持多代理的數(shù)據(jù)完整性審計方法。該方法基于主從結(jié)構(gòu)設(shè)計，主節(jié)點采用循環(huán)鏈表管理多代理節(jié)點，使用審計隊列存儲文件的審計任務(wù)，實現(xiàn)了審計任務(wù)分發(fā)、節(jié)點監(jiān)控、失效節(jié)點切換和動態(tài)增加代理等功能。從節(jié)點執(zhí)行審計任務(wù)，并且利用備份節(jié)點消除系統(tǒng)的單點故障。實驗結(jié)果表明，MP-PDP能有效減少文件的審計執(zhí)行時間，并且能夠快速增刪審計代理。

1　系統(tǒng)結(jié)構(gòu)

1.1系統(tǒng)模型

基于審計代理的數(shù)據(jù)完整性驗證模型，如圖1所示，由用戶、云存儲服務(wù)提供商、第三方審計者組成。用戶是云存儲服務(wù)的使用者；云服務(wù)提供商為用戶提供計算或者存儲服務(wù)，具備強大的計算能力和存儲能力；第三方審計者又稱為審計代理，代替用戶執(zhí)行具體的審計任務(wù)，以減輕用戶的審計負(fù)擔(dān)。

圖1　基于第三方審計的公開驗證模型

1.2基礎(chǔ)知識

文件M由n個數(shù)據(jù)塊組成，每個數(shù)據(jù)塊由s個數(shù)據(jù)扇組成，表示為M＝｛mij｜i∈［1，n］，j∈［1， s］｝。其中，數(shù)據(jù)塊(data block)是驗證文件完整性的基本單位，數(shù)據(jù)扇(data sector)是文件讀寫的基本單位。

雙線性對映射是執(zhí)行數(shù)據(jù)塊認(rèn)證的基礎(chǔ)函數(shù)，定義如下［6?7］：存在2個階數(shù)為p(p為大素數(shù))的乘法循環(huán)群G1和G2，G1的生成元為g。若映射e：G1× G1→G2滿足以下條件，則稱e為雙線性對映射：

1)可計算性，存在一個高效的算法可以計算出映射e；

2)雙線性，對于所有u，v∈G1和a，b∈Zp， e(ua，ub)＝e(u，v)ab均成立；

3)非退化性，e(g，g)≠1。

1.3數(shù)據(jù)完整性的審計過程

數(shù)據(jù)完整性的審計模型［7］由5個算法(KeyGen，TagGen，Chall，ProofGen，Verify)構(gòu)成，分述如下：

1)密鑰生成算法KeyGen其輸入為系統(tǒng)安全參數(shù)λ，輸出為密鑰對(skt，pkt)和加密密鑰skh。其中：密鑰對(skt，pkt)用于生成數(shù)據(jù)塊認(rèn)證標(biāo)簽；skh用于加密文件摘要信息Minfo，如文件名、數(shù)據(jù)塊總數(shù)等。

2)認(rèn)證標(biāo)簽生成算法TagGen其輸入為文件M和私鑰(skt，skh)，輸出為文件數(shù)據(jù)塊的認(rèn)證標(biāo)簽集合T＝｛ti｜i∈［1，n］｝和文件信息集合Minfo。其中：ti的計算方法如(1)式所示，Wi＝FID‖i是數(shù)據(jù)塊位置信息，h(skh，?)是文件信息加密函數(shù)，uj是G1類型的隨機值。

3)挑戰(zhàn)信息生成算法Chall其輸入為文件的摘要信息Minfo，輸出挑戰(zhàn)信息C＝(｛i，vi｜i∈Q｝， R)。其中：i是被挑戰(zhàn)數(shù)據(jù)塊mi的索引，Q是i的集合，vi∈Zp是伴隨mi的隨機值，R＝gr是輔助值，r∈是隨機值是小于p且與其互素的正整數(shù)。

4)數(shù)據(jù)持有性的證據(jù)生成算法ProofGen其輸入為文件M、數(shù)據(jù)塊的認(rèn)證標(biāo)簽集合T和文件的挑戰(zhàn)信息C；輸出為數(shù)據(jù)持有性證據(jù)P＝(TP，DP)。TP是被挑戰(zhàn)數(shù)據(jù)塊的標(biāo)簽證據(jù)信息，其計算方法如(2)式所示；DP是被挑戰(zhàn)數(shù)據(jù)塊的證據(jù)信息，其計算方法如(3)式所示，而MPj是數(shù)據(jù)扇的線性組合，其計算方法如(4)式所示。

5)Verify算法用來驗證服務(wù)器返回的數(shù)據(jù)持有性證據(jù)，輸入為挑戰(zhàn)信息C、數(shù)據(jù)持有性證據(jù)P、公鑰pkt和文件摘要信息Minfo。若等(5)式成立，則輸出0，表示文件完好；反之，輸出1，表示文件損壞。其中，Hchal是被挑戰(zhàn)數(shù)據(jù)塊摘要信息的哈希值的連乘積，按(6)式計算。

數(shù)據(jù)完整性的審計過程分3個階段執(zhí)行：

階段1：初始化階段

用戶使用KeyGen生成密鑰對(skt，pkt)和加密密鑰skh，使用TagGen生成數(shù)據(jù)塊的認(rèn)證標(biāo)簽集合T和文件摘要信息Minfo。用戶發(fā)送(Minfo，skh，pkt)給審計者，發(fā)送(M，T)到云服務(wù)器。

階段2：確認(rèn)審計階段

審計者使用Chall生成挑戰(zhàn)信息C并將其發(fā)送給云服務(wù)器。云服務(wù)器使用ProofGen生成數(shù)據(jù)持有性證據(jù)P，并返回給審計者。審計者使用Verify驗證接收到的證據(jù)信息P，若通過審計，表明文件已經(jīng)完好存儲到云服務(wù)器，可刪除本地副本。

階段3：抽樣審計階段

定期執(zhí)行階段2，抽樣檢測云端數(shù)據(jù)的完整性。

1.4支持多代理的數(shù)據(jù)完整性審計模型

支持多代理的數(shù)據(jù)完整性審計模型，是在原始模型［7］的基礎(chǔ)上經(jīng)擴展實現(xiàn)的，如圖2所示。

圖2　多代理結(jié)構(gòu)示意圖

多代理結(jié)構(gòu)是由主代理節(jié)點、備份節(jié)點和審計代理等三部分通過網(wǎng)絡(luò)連接構(gòu)成。主代理節(jié)點是審計系統(tǒng)的管理者，主要完成審計任務(wù)分配、審計代理的監(jiān)控、失效代理的切換和審計代理的動態(tài)擴展等功能。備份節(jié)點是主代理節(jié)點的備份，用于接管出現(xiàn)故障的主代理節(jié)點，消除審計系統(tǒng)的單點故障。審計代理是審計任務(wù)的實際執(zhí)行者，接收主代理節(jié)點分配的審計任務(wù)并向其返回審計結(jié)果。

2　多審計代理的功能實現(xiàn)

本節(jié)首先介紹多審計代理結(jié)構(gòu)所需的數(shù)據(jù)結(jié)構(gòu)，然后介紹各個功能的實現(xiàn)過程。

定義1 審計任務(wù)(audit task，AT)是執(zhí)行文件完整性審計的基本單位，可用一個二元組結(jié)構(gòu)＜FID，rr＞描述。其中，F(xiàn)ID(file identifier)是文件識別符，它規(guī)定了審計任務(wù)的執(zhí)行對象；rr(recognion rate)是錯誤識別率，規(guī)定了審計的執(zhí)行強度。

定義2 審計隊列(audit queue，AQ)是審計任務(wù)的存儲結(jié)構(gòu)，如圖3所示。每個執(zhí)行代理對應(yīng)一個審計隊列，審計任務(wù)依次進入隊列，審計任務(wù)執(zhí)行完畢后，便從審計隊列移除。審計隊列結(jié)構(gòu)包含隊列頭指針head和隊列尾指針tail，隊列長度length可以選擇設(shè)置。

2.1審計任務(wù)分配

審計任務(wù)分配模塊負(fù)責(zé)接收文件的審計任務(wù)，并執(zhí)行分配算法(assignment algorithm，AA)將其插入到相應(yīng)的審計隊列。依據(jù)分配算法不同，分為任務(wù)平均分配算法(average AA，AAA)和最短隊列優(yōu)先任務(wù)分配算法(shortest queue first AA，SAA)。為方便描述，定義符號如表1所示。

圖3　審計隊列結(jié)構(gòu)示意圖

表1　符號定義

任務(wù)平均分配算法將審計任務(wù)平均分配給每個審計隊列，如算法1所示。首先，使用循環(huán)鏈表串聯(lián)審計隊列，并將指針Y指向待分配的審計隊列，如圖4所示；然后，將審計任務(wù)分配給指針Y指向的審計隊列，并后移指針Y；循環(huán)執(zhí)行第二步，分配后續(xù)的審計任務(wù)。

圖4　循環(huán)鏈表結(jié)構(gòu)示意圖

算法1任務(wù)平均分配算法

任務(wù)平均分配算法要求審計代理具備相同的審計性能，否則將造成審計代理負(fù)載失衡，即部分審計代理積壓審計任務(wù)，部分審計代理因提前完成審計任務(wù)而閑置。

最短隊列優(yōu)先任務(wù)分配算法將審計任務(wù)總是分配給長度最短的審計隊列，如算法2所示。首先，比較審計隊列長度，移動指針P指向長度最短的審計隊列；其次，將審計任務(wù)分配給指針P指向的審計隊列，同時增加該隊列長度；從審計隊列移除已完成審計任務(wù)并減少該隊列的長度；重新將指針P指向長度最短的隊列；最后，重復(fù)執(zhí)行第二步，分配后續(xù)的審計任務(wù)。

算法2 最短隊列優(yōu)先任務(wù)分配算法

2.2審計節(jié)點的狀態(tài)監(jiān)控

采用定期發(fā)送心跳信息方法，監(jiān)控審計節(jié)點的狀態(tài)。倘若被監(jiān)控節(jié)點不能按時返回心跳信息，表明節(jié)點出現(xiàn)故障。如果主代理節(jié)點故障，則啟動備份節(jié)點予以修復(fù)。如果審計代理故障，則執(zhí)行失效審計節(jié)點的動態(tài)切換予以修復(fù)。

2.3失效審計節(jié)點的動態(tài)切換

切換失效的審計節(jié)點將重新分配該審計節(jié)點的審計任務(wù)，并由其他審計代理代為執(zhí)行，如算法3所示。發(fā)現(xiàn)失效審計節(jié)點后，首先，找到對應(yīng)于該失效節(jié)點的審計隊列(假設(shè)為AQj)；其次，從循環(huán)鏈表中刪除審計隊列AQj；最后，按照審計任務(wù)分配算法重新分配審計隊列AQj的審計任務(wù)。

算法3 失效審計節(jié)點的切換算法

2.4代理節(jié)點的動態(tài)增加

代理節(jié)點的動態(tài)增加過程如算法4所示。首先，生成新代理的審計隊列，并將其插入到循環(huán)鏈表；然后，執(zhí)行任務(wù)分配算法AA為其動態(tài)添加審計任務(wù)，使該隊列的審計任務(wù)數(shù)與其他隊列保持平衡。

算法4 代理節(jié)點的動態(tài)增加算法

3　實驗結(jié)果分析

為了評估MP-PDP的性能，對MP-PDP進行了仿真實驗，比較了MP-PDP模型與PDP模型的審計執(zhí)行時間，并且測試了替換失效代理和增加審計代理的性能開銷。

3.1實驗環(huán)境

采用C語言實現(xiàn)了原型系統(tǒng)MP-PDP，將該系統(tǒng)運行于浪潮AS300N服務(wù)器，運行環(huán)境：Ubuntu 12.04.3 LTS，Linux 3.8.0-29(x86－64)，4x Intel(R) Xeon(R)CPU E5502＠1.87 GHz，內(nèi)存16 GB，硬盤ATA Hitachi HTS54501 150 GB。

3.2實驗結(jié)果與分析

1)審計文件執(zhí)行時間

設(shè)置不同代理數(shù)，對不同數(shù)量的文件(100～500)執(zhí)行數(shù)據(jù)完整性審計，審計周期為4 h，循環(huán)審計72 h，并統(tǒng)計審計執(zhí)行的時間。從圖5可以看出，與單代理模型(代理數(shù)為1)比較，采用多代理審計模型明顯減少了審計執(zhí)行時間，并且審計文件數(shù)量越大，執(zhí)行時間減少得越明顯。相較于任務(wù)平均分配算法AAA，最短隊列優(yōu)先分配算法SAA進一步減少了系統(tǒng)的審計執(zhí)行時間。

圖5　審計文件的執(zhí)行時間

審計執(zhí)行時間減少的原因，是多個審計代理分擔(dān)了審計任務(wù)，使得同一時刻可以并行審計多個文件。由于存在通信和計算開銷，審計執(zhí)行時間不能隨審計代理的數(shù)量增加而成倍減少。但是，在不同情況下，通信成本占總開銷比重基本固定。因此，隨著審計代理數(shù)量增加，審計執(zhí)行時間的減少越顯著。采用5個代理時，減少的審計執(zhí)行時間約為80%。

2)切換失效代理的執(zhí)行時間

對不同代理數(shù)的設(shè)定，比較不同任務(wù)分配算法(AAA和SAA)切換失效代理節(jié)點的執(zhí)行時間。從圖6可以看出，最短隊列優(yōu)先任務(wù)分配算法SAA所需時間，明顯低于任務(wù)平均分配算法AAA，并且隨著文件數(shù)量增加，SAA的執(zhí)行時間減少得越顯著。其原因是，SAA算法將失效代理節(jié)點未完成的審計任務(wù)，集中分配給審計任務(wù)數(shù)最少的節(jié)點，避免了與多個代理間建立連接和傳輸?shù)男阅荛_銷，而AAA算法需要將審計任務(wù)平均分配給存活的多個審計代理，網(wǎng)絡(luò)連接和傳輸會導(dǎo)致較大的性能開銷。

圖6　替換失效代理節(jié)點的執(zhí)行時間

3)動態(tài)增加代理節(jié)點的執(zhí)行時間

設(shè)定不同代理數(shù)，比較了不同任務(wù)分配算法動態(tài)增加審計代理節(jié)點的執(zhí)行時間。

從圖7可以看出，隨著文件數(shù)量的增加，任務(wù)平均分配算法AAA的執(zhí)行時間呈線性增長，而最短隊列優(yōu)先任務(wù)分配算法SAA的執(zhí)行時間增長較為平緩。其原因是，AAA算法將調(diào)動所有代理向新審計代理轉(zhuǎn)移審計任務(wù)，而SAA算法只需將新來的審計任務(wù)轉(zhuǎn)移給新審計代理，保持其他審計代理不變，因此節(jié)省了大量的網(wǎng)絡(luò)開銷。

圖7　動態(tài)增加代理節(jié)點切換的執(zhí)行時間

4　結(jié) 論

針對現(xiàn)有的數(shù)據(jù)完整性模型中單代理節(jié)點易造成單點故障并易形成性能瓶頸等問題，本文提出了一種支持多代理的數(shù)據(jù)完整性審計方法MP-PDP。該方法采用主從結(jié)構(gòu)，實現(xiàn)了審計任務(wù)分發(fā)、節(jié)點監(jiān)控、失效代理的替換和審計代理的動態(tài)增加等功能，并且利用備份節(jié)點消除了系統(tǒng)的單點故障。實驗結(jié)果表明，該方法可有效提高系統(tǒng)的審計效率，并且能夠快速增刪審計代理。

［1］ 李暉，孫文海，李鳳華，等.公共云存儲服務(wù)數(shù)據(jù)安全及隱私保護技術(shù)綜述［J］.計算機研究與發(fā)展，2014，51(7)：1397-1409

Li Hui，Sun Wenhai，Li Fenghua，et al.Secure and Privacy-Preserving Data Storage Service in Public Cloud［J］.Journal of Computer Research and Development，2014，51(7)：1397-1409(in Chinese)

［2］ 譚霜，賈焰，韓偉紅.云存儲中的數(shù)據(jù)完整性證明研究及進展［J］.計算機學(xué)報，2015，38(1)：164-177

Tan Shuang，Jia Yan，Han Weihong.Research and Development of Provable Data Integrity in Cloud Storage［J］.Chinese Journal of Computers，2015，38(1)：164-177(in Chinese)

［3］ Ateniese G，Burns R，Curtmola R，et al.Remote Data Checking Using Provable Data Possession［J］.ACM Trans on Information and System Security，2011，14(1)：12

［4］ Wang Cong，Chow S S M，Wang Q，et al.Privacy-Preserving Public Auditing for Secure Cloud Storage［J］.IEEE Trans on Computers，2013，62(2)：362-375

［5］ Zhu Y，Hu H，Ahn G J，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

［6］ Wang Boyang，Li Baochun，Li Hui.Oruta：Privacy-Preserving Public Auditing for Shared Data in the Cloud［C］//IEEE Trans on Cloud Computing，2014，1：43-56

［7］ Yang K，Jia X.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

An Audit Method of Data Integrity for SuPPorting MultiPle Proxies in Cloud ComPuting

Wang Huifeng，Li Zhanhuai，Zhang Xiao，Sun Jian，Zhao Xiaonan
(Department of Computer Science and Engineering，Northwestern Polytechnical University，Xi′an 710072，China)

Since cloud storage service faces many security risks that can damage data，checking data integrity has become increasingly urgent.Provable Data Possession(PDP)is an important method for verifying data integrity in cloud computing.But the single proxy in the traditional PDP models easily becomes the single point of failure and catches the performance bottleneck.So we propose an improved PDP，called MP-PDP by us，for supporting mutiple proxies in cloud computing.It adopts a circular linked list and uses audit queues to store the audit tasks.It achieves such functions as assigning audit tasks，monitoring nodes，switching failed node and dynamically adding proxy and uses the backup node for eliminating the single point of failure.The experimental results indicate that MP-PDP can efficiently reduce the audit time for files and quickly add or delete the audit proxy.

algorithms，big data，conceptual design，cost reduction，design of experiments，dynamic models，dynamical systems，efficiency，fault tolerance，mathematical models，monitoring，scalability，software reliability，switching frequency；cloud storage security，data integrity checking，multiple proxies， PDP(provable data possession)

TP309.2

A

1000-2758(2016)02-0343-06

2015-04-17基金項目：國家“863”高技術(shù)研究發(fā)展計劃基金(2013AA01A215)、國家自然科學(xué)基金(61472323)、中央高?；究蒲袠I(yè)務(wù)費專項資金(3102015JSJ0009)與華為創(chuàng)新基金(YB2014040023)資助

王惠峰(1986—)，西北工業(yè)大學(xué)博士研究生，主要從事云存儲安全、云存儲評測的研究。