支持多代理的云存儲數據完整性審計方法

王惠峰，李戰懷，張曉，孫鑒，趙曉南

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

支持多代理的云存儲數據完整性審計方法

王惠峰，李戰懷，張曉，孫鑒，趙曉南

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

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

多代理；數據持有性證明；數據完整性驗證；云存儲安全

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

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

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

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

1　系統結構

1.1系統模型

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

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

1.2基礎知識

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

雙線性對映射是執行數據塊認證的基礎函數，定義如下［6?7］：存在2個階數為p(p為大素數)的乘法循環群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數據完整性的審計過程

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

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

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

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

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

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

數據完整性的審計過程分3個階段執行：

階段1：初始化階段

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

階段2：確認審計階段

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

階段3：抽樣審計階段

定期執行階段2，抽樣檢測云端數據的完整性。

1.4支持多代理的數據完整性審計模型

支持多代理的數據完整性審計模型，是在原始模型［7］的基礎上經擴展實現的，如圖2所示。

圖2　多代理結構示意圖

多代理結構是由主代理節點、備份節點和審計代理等三部分通過網絡連接構成。主代理節點是審計系統的管理者，主要完成審計任務分配、審計代理的監控、失效代理的切換和審計代理的動態擴展等功能。備份節點是主代理節點的備份，用于接管出現故障的主代理節點，消除審計系統的單點故障。審計代理是審計任務的實際執行者，接收主代理節點分配的審計任務并向其返回審計結果。

2　多審計代理的功能實現

本節首先介紹多審計代理結構所需的數據結構，然后介紹各個功能的實現過程。

定義1 審計任務(audit task，AT)是執行文件完整性審計的基本單位，可用一個二元組結構＜FID，rr＞描述。其中，FID(file identifier)是文件識別符，它規定了審計任務的執行對象；rr(recognion rate)是錯誤識別率，規定了審計的執行強度。

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

2.1審計任務分配

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

圖3　審計隊列結構示意圖

表1　符號定義

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

圖4　循環鏈表結構示意圖

算法1任務平均分配算法

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

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

算法2 最短隊列優先任務分配算法

2.2審計節點的狀態監控

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

2.3失效審計節點的動態切換

切換失效的審計節點將重新分配該審計節點的審計任務，并由其他審計代理代為執行，如算法3所示。發現失效審計節點后，首先，找到對應于該失效節點的審計隊列(假設為AQj)；其次，從循環鏈表中刪除審計隊列AQj；最后，按照審計任務分配算法重新分配審計隊列AQj的審計任務。

算法3 失效審計節點的切換算法

2.4代理節點的動態增加

代理節點的動態增加過程如算法4所示。首先，生成新代理的審計隊列，并將其插入到循環鏈表；然后，執行任務分配算法AA為其動態添加審計任務，使該隊列的審計任務數與其他隊列保持平衡。

算法4 代理節點的動態增加算法

3　實驗結果分析

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

3.1實驗環境

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

3.2實驗結果與分析

1)審計文件執行時間

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

圖5　審計文件的執行時間

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

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

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

圖6　替換失效代理節點的執行時間

3)動態增加代理節點的執行時間

設定不同代理數，比較了不同任務分配算法動態增加審計代理節點的執行時間。

從圖7可以看出，隨著文件數量的增加，任務平均分配算法AAA的執行時間呈線性增長，而最短隊列優先任務分配算法SAA的執行時間增長較為平緩。其原因是，AAA算法將調動所有代理向新審計代理轉移審計任務，而SAA算法只需將新來的審計任務轉移給新審計代理，保持其他審計代理不變，因此節省了大量的網絡開銷。

圖7　動態增加代理節點切換的執行時間

4　結 論

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

［1］ 李暉，孫文海，李鳳華，等.公共云存儲服務數據安全及隱私保護技術綜述［J］.計算機研究與發展，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］ 譚霜，賈焰，韓偉紅.云存儲中的數據完整性證明研究及進展［J］.計算機學報，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”高技術研究發展計劃基金(2013AA01A215)、國家自然科學基金(61472323)、中央高校基本科研業務費專項資金(3102015JSJ0009)與華為創新基金(YB2014040023)資助

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