云存儲中數(shù)據(jù)完整性自適應審計方法

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

(西北工業(yè)大學計算機學院 西安 710129)(wanghuifeng12@163.com)

云存儲中數(shù)據(jù)完整性自適應審計方法

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

(西北工業(yè)大學計算機學院 西安 710129)(wanghuifeng12@163.com)

作為云存儲安全的重要問題，數(shù)據(jù)完整性驗證技術(shù)受到學術(shù)界和工業(yè)界的廣泛關注.為了驗證云端數(shù)據(jù)完整性,研究者提出了多個數(shù)據(jù)完整性公開審計模型.然而，現(xiàn)有的數(shù)據(jù)完整性審計模型采用固定參數(shù)審計所有文件,浪費了大量計算資源，導致系統(tǒng)審計效率不高.為了提高系統(tǒng)的審計效率，提出了一種自適應數(shù)據(jù)持有性證明方法(self-adaptive provable data possession, SA-PDP)，該方法基于文件屬性和用戶需求動態(tài)調(diào)整文件的審計方案，使得文件的審計需求和審計方案的執(zhí)行強度高度匹配.為了增強審計方案更新的靈活性，依據(jù)不同的審計需求發(fā)起者，設計了2種審計方案動態(tài)更新算法.主動更新算法保證了審計系統(tǒng)的覆蓋率，而被動更新算法能夠及時滿足文件的審計需求.實驗結(jié)果表明：相較于傳統(tǒng)方法，SA-PDP的審計總執(zhí)行時間至少減少了50%，有效增加了系統(tǒng)審計文件的數(shù)量.此外，SA-PDP方法生成的審計方案的達標率比傳統(tǒng)審計方法提高了30%.

數(shù)據(jù)安全；云存儲；數(shù)據(jù)完整性驗證；數(shù)據(jù)可持有性證明；自適應審計

云存儲服務以其高性價比、良好的擴展性和按需付費等特點受到用戶的普遍歡迎.同時，云存儲服務面臨許多安全威脅，云端文件的數(shù)據(jù)完整性容易遭受破壞.例如2011年3月谷歌Gmail郵箱出現(xiàn)故障，導致大約15萬用戶的數(shù)據(jù)丟失；2012年8月盛大云因物理服務器磁盤損壞造成用戶數(shù)據(jù)丟失[1].EMC公司指出，64%的受調(diào)查企業(yè)在過去12個月中經(jīng)歷過數(shù)據(jù)丟失或宕機事故.數(shù)據(jù)完整性驗證[1-2]作為云存儲安全的重要問題，受到學術(shù)界和工業(yè)界的廣泛關注.數(shù)據(jù)完整性驗證能夠及時發(fā)現(xiàn)數(shù)據(jù)損壞，為數(shù)據(jù)恢復贏得寶貴時間.但云存儲中文件數(shù)量龐大，數(shù)據(jù)完整性驗證面臨沉重的審計負擔，不合理的審計方案將嚴重影響系統(tǒng)的審計效率.因此，如何有效降低大規(guī)模文件的審計成本、提高系統(tǒng)的審計效率是一個亟需解決的重要問題.

近年來，研究人員針對數(shù)據(jù)完整性驗證問題提出了多種解決方案[3-20].Juels等人[3]提出了一種可檢索數(shù)據(jù)證明模型(proofs of retrievability, POR)，要求返回指定位置的“哨兵”來檢查文件損壞.但是“哨兵”數(shù)量固定，該模型只支持有限次數(shù)的審計，而重新布置“哨兵”代價高昂.Ateniese等人[4]提出一種數(shù)據(jù)持有性證明模型(provable data possession, PDP)，采用隨機抽樣方式驗證文件，使審計次數(shù)不受限制，并且PDP將認證信息與原始數(shù)據(jù)分離，保持了原始文件的獨立性.PDP已經(jīng)成為驗證云存儲數(shù)據(jù)完整性審計的主要方法.

針對PDP方法的數(shù)據(jù)動態(tài)更新、公開審計和協(xié)同存儲等問題，研究人員進行了深入研究.Erway等人[6]利用等級數(shù)據(jù)跳表實現(xiàn)了支持數(shù)據(jù)動態(tài)更新的PDP模型，但中間節(jié)點計算復雜.王聰?shù)热薣9]利用merkle hash tree結(jié)構(gòu)簡化了中間節(jié)點計算過程.朱巖和王博洋等人[11-12]利用index-hash table二維表結(jié)構(gòu)實現(xiàn)了數(shù)據(jù)的動態(tài)更新，該結(jié)構(gòu)適合更新請求較少的情景.禹勇等人[13]指出了數(shù)據(jù)更新時面臨的偽造攻擊和重放攻擊的問題，通過改進審計協(xié)議增強了系統(tǒng)的安全性.為了減輕用戶的計算負擔，基于代理的審計模型[9,14-15]將文件審計任務委托給第三方執(zhí)行，并利用隨機隱碼技術(shù)實現(xiàn)了認證過程的隱私保護.此外，朱巖等人[16]提出了多云協(xié)同存儲環(huán)境下的PDP方案，王化群等人[17]增強了該方案的安全性.賈小華等人[15]實現(xiàn)了多云環(huán)境下文件的批量審計.王博洋等人[12]提出了支持文件共享的PDP方案，實現(xiàn)了低成本的用戶共享權(quán)限的授予與回收.付艷艷等人[20]提出了面向云存儲的多副本數(shù)據(jù)完整性審計方案.

以上方案為解決云存儲數(shù)據(jù)完整性審計問題提供了可行思路，為進一步研究數(shù)據(jù)完整性審計模型及算法奠定了良好的基礎.然而，現(xiàn)有方案僅考慮了單個文件的審計問題，未考慮大規(guī)模文件的協(xié)調(diào)審計問題，統(tǒng)稱為B-PDP(basic PDP)模型[15].在云存儲環(huán)境下，面對大數(shù)據(jù)量和多樣性的審計需求，現(xiàn)有方案存在的問題是：1)文件數(shù)量龐大，完成全域文件審計成本高；2)文件活躍程度不同，活躍文件不能及時得到審計，導致用戶體驗下降，不活躍文件可能被頻繁審計帶來了不必要的審計開銷；3)文件被損壞概率不同，高強度審計所有文件將導致審計負載過重，在現(xiàn)實中不可行；4)采用單一審計策略容易造成某些文件長時間得不到審計，導致審計系統(tǒng)覆蓋率不足.

為了解決以上問題，本文提出了一種綜合考慮文件審計需求、審計效率和審計覆蓋率的數(shù)據(jù)完整性自適應審計方法SA-PDP(self-adaptive provable data possession).該方法依據(jù)文件屬性制定滿足其安全需求的審計方案，協(xié)調(diào)完成全域文件的審計，具有低成本、高效率等特點，既能滿足用戶的審計需求，又能有效減少文件審計成本，提高系統(tǒng)的審計效率.

本文的主要工作及貢獻如下：

1) 設計并實現(xiàn)了SA-PDP方法，該方法能夠基于文件屬性自適應調(diào)節(jié)數(shù)據(jù)完整性審計方案，使審計方案的執(zhí)行強度與文件的審計需求高度匹配；

2) 提出了2種審計方案的動態(tài)更新算法，主動更新算法保證了審計系統(tǒng)的覆蓋率，被動更新算法能夠及時滿足文件的審計需求；

3) 提出了文件審計方案的評價標準，通過計算審計方案的執(zhí)行強度和文件的審計需求，動態(tài)描述了二者的匹配程度；

4) 實現(xiàn)了原型系統(tǒng)SA-PDP和B-PDP，分析了系統(tǒng)的存儲開銷和通信開銷，并從審計效率和審計方案的匹配度方面進行了多組對比實驗；相較于B-PDP方法，SA-PDP的審計總執(zhí)行時間減少了50%，并且SA-PDP審計方案的達標率提高了30%.

1 系統(tǒng)模型和預備知識

本節(jié)首先對數(shù)據(jù)完整性審計的系統(tǒng)模型和相關概念進行了描述與定義，然后介紹預備知識.

1.1 數(shù)據(jù)完整性審計的系統(tǒng)模型

數(shù)據(jù)完整性審計系統(tǒng)由云存儲用戶、云存儲服務器、第三方審計者組成，如圖1所示.用戶是云存儲服務的使用者；云存儲服務器為用戶提供計算和存儲服務；第三方審計者代替用戶執(zhí)行具體的審計任務，以減輕用戶的審計負擔.

Fig. 1 System model for data integrity checking圖1 數(shù)據(jù)完整性審計的系統(tǒng)模型

數(shù)據(jù)完整性審計[15]包含5個基本算法，分別是密鑰生成算法KeyGen、數(shù)據(jù)塊(data block)認證標簽生成算法TagGen、挑戰(zhàn)信息生成算法ChalGen、數(shù)據(jù)持有性證據(jù)生成算法ProofGen和證據(jù)驗證算法Verify.

數(shù)據(jù)完整性審計過程分為3個階段：

階段1. 初始化階段

用戶使用KeyGen生成數(shù)據(jù)塊認證標簽的密鑰對(sktag,pktag)和文件信息加密密鑰skHash，使用TagGen生成文件數(shù)據(jù)塊的認證標簽集合Φ={φi|i∈[1,n]}和文件的摘要信息Minfo.用戶發(fā)送(Minfo,skHash,pktag)給審計者，發(fā)送(M,Φ)給云存儲服務器.

階段2. 確認審計階段

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

階段3. 抽樣審計階段

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

1.2 審計系統(tǒng)的基本概念

審計系統(tǒng)通過制定文件的審計方案協(xié)調(diào)完成所有文件的審計任務，審計方案規(guī)定了文件的審計周期和識別率.

定義1. 審計周期T.指連續(xù)2次審計過程的間隔時間.審計周期越小，審計文件越頻繁，同時意味著審計成本隨之增大.

定義2. 識別率RR(recognition rate).指審計系統(tǒng)能夠識別出文件損壞的概率.假設文件的數(shù)據(jù)塊總數(shù)為n，數(shù)據(jù)塊損壞個數(shù)為x且相互獨立，被挑戰(zhàn)數(shù)據(jù)塊個數(shù)為c，則RR計算如下[4]：

(1)

文件的識別率不同，被查詢數(shù)據(jù)塊個數(shù)差異明顯，如圖2所示.例如，數(shù)據(jù)塊總數(shù)為10 000的文件，當RR≥99%時，c≥450；當RR≥90%時，c≥228.

Fig. 2 The number of queried blocks under different RR圖2 不同識別率下的查詢數(shù)據(jù)塊塊數(shù)

定義3. 審計方案AP(audit plan).指執(zhí)行文件審計的具體計劃，AP由形如〈T,RR〉的二元序偶組成，T是文件的審計周期，RR是識別率.文件Mk的審計方案表示為APk.

文件M作為系統(tǒng)的審計對象，由n個數(shù)據(jù)塊組成，每個數(shù)據(jù)塊包含s個數(shù)據(jù)扇(data sector)，表示為M={mij|i∈[1,n],j∈[1,s]}.數(shù)據(jù)塊是驗證文件完整性的基本單位，數(shù)據(jù)扇是文件讀寫的基本單位.文件的屬性信息反映了文件審計需求，并據(jù)此確定文件的審計方案.

定義4. 文件屬性.描述了文件狀態(tài)和特征，由形式為〈d,h〉的二元序偶組成，d為文件的損壞概率，h為文件的訪問熱度.文件損壞概率預測文件遭到損壞的可能性大小；文件訪問熱度反映了文件在當前時間區(qū)間的活躍程度.文件Mk的屬性記為Attrk(d,h).

Fig. 3 Audit queue for storing the audit projects圖3 審計方案隊列

1.3 預備知識

雙線性對映射是執(zhí)行數(shù)據(jù)完整性驗證的基礎函數(shù)，定義如下：存在2個階數(shù)為p(p為大素數(shù))的乘法循環(huán)群G1和G2，g是群G1的生成元.如果映射e:G1×G1→G2滿足如下性質(zhì)，則稱e為雙線性對映射：

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

2) 雙線性.對于所有u,v∈G1和a,b∈p，e(ua,vb)=e(u,v)ab均成立.

3) 非退化性.e(g,g)≠1G2，其中1G2表示群G2的單位元.

2 數(shù)據(jù)完整性自適應審計模型

本節(jié)首先介紹SA-PDP模型的審計流程，然后提出文件審計方案的生成和自適應更新方法，最后給出文件審計方案的評價標準.

2.1 自適應審計模型的審計流程

定義5. SA-PDP模型由5個基本算法組成：

1)PrePDP(ζM,1λ)→(keys,ζΦ,ζMinfo,ζ(0|1)).輸入文件列表ζM和安全參數(shù)k，輸出密鑰、數(shù)據(jù)塊認證標簽列表ζΦ、文件的摘要信息列表ζMinfo、預處理結(jié)果列表ζ(0|1).

PrePDP算法循環(huán)執(zhí)行文件的數(shù)據(jù)完整性審計過程[15]的初始化階段和確認階段完成文件的預處理.keys包括密鑰對(sktag,pktag)和散列函數(shù)私鑰skHash.輸入安全參數(shù)λ，選擇sktag,skHash∈G1作為標簽私鑰和散列函數(shù)私鑰，計算pktag=gs ktag作為標簽公鑰.循環(huán)執(zhí)行TagGen處理文件列表ζM，生成文件的認證標簽集合.以文件Mk為例，生成數(shù)據(jù)塊認證標簽集合Φk.隨機選取x1,k,x2,k,…,xs,k∈p，計算uj,k=gxj,k,j∈[1,s].計算數(shù)據(jù)塊mi,k的認證標簽φi,k如下：

(2)

2)AuditProGen(ζM)→ζAP.輸入文件列表ζM，輸出文件審計方案列表ζAP.以文件Mk為例，依據(jù)文件屬性Attrk(d,h)生成文件的審計方案APk.

3)InsertQueue(ζAP)→ζQ.輸入文件審計方案列表ζAP，輸出審計隊列ζQ.

生成文件審計方案列表后，依據(jù)審計周期構(gòu)建多個審計方案隊列，如圖3所示.隊列中每個節(jié)點由形如〈FIDk,Tk,rrk〉的三元組構(gòu)成，F(xiàn)IDk是文件描述符，Tk是文件的審計周期，rrk是識別率.由InsertQueue算法將文件審計方案插入到相應的審計隊列.

4)DeQueue(ζQ)→BufQueue.輸入審計隊列ζQ，輸出審計緩存區(qū)BufQueue.

DeQueue算法定期從審計隊列取出文件審計方案并放入審計緩存區(qū)BufQueue，成為待審計文件.

5)RunPDP(BufQueue)→{0|1}.輸入審計緩沖區(qū)BufQueue，輸出審計結(jié)果{0|1}.

RunPDP算法依次取出審計緩存區(qū)中文件審計方案〈FIDk,Tk,rrk〉，執(zhí)行數(shù)據(jù)完整性審計，并輸出審計結(jié)果.根據(jù)FIDk獲得文件的摘要信息Minfo,k，運行ChalGen生成挑戰(zhàn)信息Ck.依據(jù)識別率rrk計算被挑戰(zhàn)數(shù)據(jù)塊數(shù)量并隨機挑選相應數(shù)量的數(shù)據(jù)塊組成挑戰(zhàn)集合Ik，為每個被挑戰(zhàn)數(shù)據(jù)塊生成一個隨機值vi∈*p.選取隨機值yk∈*p計算挑戰(zhàn)戳Yk=(pktag)yk.發(fā)送Ck=({i,vi}i∈Ik,Yk)給云存儲服務器.云存儲服務器運行ProofGen生成數(shù)據(jù)持有性證據(jù)Pk.證據(jù)信息Pk由標簽擁有證據(jù)TPk和數(shù)據(jù)塊擁有證據(jù)DPk組成，計算如下：

(3)

其中，MPj是數(shù)據(jù)扇的線性集合，計算如下：

(4)

云服務器將數(shù)據(jù)持有性證據(jù)Pk發(fā)送給審計者.審計者運行Verify算法驗證數(shù)據(jù)持有性證據(jù)Pk.首先計算挑戰(zhàn)散列值的連乘積Hchal,k，計算如下：

(5)

然后，驗證Pk是否滿足下式：

DPk×e(Hchal,k,pktag)=e(TPk,gyk).

(6)

若滿足式(6)，輸出1，表示文件完好；反之，輸出0，表示文件被損壞.

SA-PDP審計過程由3個階段組成：初始化階段、審計方案生成階段和定期審計階段，如圖4所示.1)初始化階段進行PDP方案的預處理，生成數(shù)據(jù)塊認證信息并確保數(shù)據(jù)及相應信息正確存儲到云端；2)審計方案生成階段，審計者依據(jù)文件的屬性信息生成審計方案并創(chuàng)建文件審計隊列；3)定期審計階段，審計者定期從文件審計隊列獲取文件審計方案并執(zhí)行數(shù)據(jù)完整性審計.

Fig. 4 Audit process of SA-PDP圖4 SA-PDP的審計流程

2.2 文件審計方案的生成

文件審計方案規(guī)定了文件的審計周期和執(zhí)行強度.審計方案由文件的審計需求決定，而文件屬性信息是文件審計需求的集中體現(xiàn).在文件審計方案生成時，首先記錄文件的屬性信息；然后，依據(jù)屬性信息生成文件的審計方案.

文件屬性記錄了文件損壞概率和文件訪問熱度信息，由損壞概率級別dk、損壞次數(shù)、訪問熱度級別hk、訪問次數(shù)組成，如圖5所示.初始化階段設置文件屬性為0，在固定時間段內(nèi)記錄文件屬性值.例如，在審計周期T0～T1之間，文件Mk屬性值變動被及時記錄到文件屬性結(jié)構(gòu).為減少成本，此過程只記錄屬性變動的文件.記錄時間段內(nèi)損壞次數(shù)和訪問次數(shù)是決定屬性級別的依據(jù)，在時間段結(jié)束時進行屬性級別更改，并重置損壞次數(shù)和訪問次數(shù)值，進入下一個時間段執(zhí)行.

Fig. 5 Process of updating file attributes圖5 文件屬性的更新過程

在記錄時間段結(jié)束時，依據(jù)文件損壞次數(shù)和訪問次數(shù)設置文件損壞概率級別和文件訪問熱度級別，如表1、表2所示.設定損壞概率級別總數(shù)為dmax，訪問熱度級別總數(shù)為hmax，由表1可得dmax=3，由表2可得hmax=5.屬性級別更新分為降級操作和升級操作.降級操作針對前一個審計周期屬性中級別變動文件，檢驗當前審計周期內(nèi)該文件屬性，如果屬性值低于當前屬性級別的最低閾值則執(zhí)行屬性降級操作；反之，保持屬性級別不變.升級操作針對當前審計周期屬性變動的文件，依據(jù)文件屬性映射表設定文件屬性級別.當前審計周期結(jié)束時，重置屬性級別變動文件的損壞次數(shù)和訪問次數(shù)值.

Table 1 Mapping Table of Levels of Damage Probability

Table 2 Mapping Table of Levels of Access Popularity

審計方案由審計周期和識別率組成，依據(jù)服務等級協(xié)議設定審計周期級別LT和識別率級別LRR，如表3、表4所示.設定審計周期的級別總數(shù)為LTmax，識別率的級別總數(shù)為LRRmax，表3中LTmax=5，表4中LRRmax=3.

Table 3 Mapping Table of Levels of Audit Period

Table 4 Mapping Table of Levels of Recognition Rate

確立文件審計周期級別LTk時，首先依據(jù)文件屬性值〈dk,hk〉，分別計算由文件損壞概率確立的審計周期級別LTdk和由文件訪問熱度確立的審計周期級別LThk，然后取二者的最小值，計算如下：

LTk=min{LTdk,LThk}=

(7)

確立文件識別率級別LRRk時，首先依據(jù)文件屬性值〈dk,hk〉，分別計算由文件損壞概率確立的識別率級別LRRdk和由文件訪問熱度確立的識別率級別LRRhk，然后取二者的最大值，計算如下：

LRRk=max{LRRdk,LRRhk}=

(8)

獲得審計周期級別LTk和識別率的級別LRRk后，由表3、表4可得到文件的審計周期Tk和識別率rrk.

2.3 審計方案的自適應更新過程

定義6. SA-PDP審計方案自適應更新過程由2個算法組成：

1)UPGen(ζM)→ζAPU.輸入屬性值變動的文件列表ζMU，輸出待更新的審計方案列表ζAPU.

在執(zhí)行DeQueue(ζQ)后，檢測文件的屬性變化.如果文件屬性變化不符合當前審計方案的閾值，執(zhí)行審計方案更新操作.以Mk為例，根據(jù)變動的文件屬性值Attrk，生成更新的文件審計方案APU,k.所有待更新的審計方案組成審計方案更新列表ζAPU.

依據(jù)方案更新請求的發(fā)起者不同，審計方案更新算法分為主動更新算法(active audit plan self-adaptive update, AASU)和被動更新算法(lazy audit plan self-adaptive update, LASU).由審計者主動檢測文件審計方案變更需求的算法，稱為主動更新算法；由被審計文件發(fā)起的審計方案更新請求的算法，稱為被動更新算法.主動更新算法保證審計系統(tǒng)具有高覆蓋率，而被動更新算法能夠及時滿足文件的審計需求.為了便于描述，定義相關符號，如表5所示：

Table 5 Definition of Symbols of Update Algorithm

主動更新算法AASU在文件審計完成后，獲取文件最新的屬性值進行更新需求判斷，如果原始方案的執(zhí)行強度與審計需求不符，重新生成新方案并插入到新隊列；否則，保持原有審計方案不變，插入到原始隊列.AASU算法不僅能保證審計方案匹配度，并且覆蓋了所有文件，具有通用性.AASU算法的不足在于無論文件屬性變化與否，都需要進行方案更新檢查，造成系統(tǒng)資源的浪費，并且AASU更新方案具有滯后性，對于屬性發(fā)生變化的文件只有等到審計完成后才能執(zhí)行審計方案的變更.

算法1. 審計方案的主動更新算法AASU.

輸入：ζQ，Θ；

輸出：ζQU.

① 在最大審計周期Tmax內(nèi)：

② for (i=1；i≤LTmax；i++) {

③ for (j=1；j≤η；j++){

④ 獲取并執(zhí)行審計隊列Qi中第j個審計方案APj；

⑤ 獲取文件屬性值〈dk,hk〉；

⑥ 計算審計方案的執(zhí)行強度與文件審 計需求差χj；

⑦ if (χj>Θ)生成新審計方案并插入相應審計隊列；

⑧ else 保持原始審計方案APj不變，插 入到原始隊列；

⑨ }

⑩ }

與主動更新算法不同，被動更新算法LASU由屬性變化的文件向?qū)徲嫹桨戈犃邪l(fā)起審計方案更新請求，避免了大量審計方案的更新需求判斷，并且提高了方案更新的時效性.

被動更新算法LASU增加了文件屬性的更新狀態(tài)位，以空間換時間，避免了完成審計后更新閾值的判斷，并且文件屬性變動后可以即刻修改文件的更新方案，解決了更新審計方案滯后的問題.

算法2. 審計方案的被動更新算法LASU.

輸入：ζQ，Θ；

輸出：ζQU.

① 在最大審計周期Tmax內(nèi)：

② if (文件屬性改變) {

③ 根據(jù)文件屬性變化計算文件的審計需求差值χ；

④ if (χ>Θ){

⑤ 生成新審計方案并插入相應隊列；

⑥ 設置S=1(默認為0)；

⑦ }

⑧ }

⑨ for (i=1；i≤LTmax；i++) {

⑩ for (j=1；j≤η；j++){

2.4 文件審計方案的評價標準

審計方案的好壞由文件審計的執(zhí)行總時間、系統(tǒng)可審計文件數(shù)量、審計方案的匹配度進行評價.為了論述方便，定義審計方案相關符號，如表6所示：

Table 6 Definition of Symbols of Audit Plan

定義7. 文件審計的執(zhí)行總時間E.指審計期間內(nèi)，所有被審計文件的執(zhí)行時間總和.假設文件列表為{M1,M2,…,MN}，對文件Mi共執(zhí)行numi次審計，第j次的執(zhí)行時間為εi,j，則E計算為

(9)

文件審計的執(zhí)行總時間反映了系統(tǒng)的審計開銷，執(zhí)行總時間越大，審計代價越高.審計系統(tǒng)設計的目標是在滿足審計需求的前提下，盡可能減少文件的總執(zhí)行時間.

定義8. 系統(tǒng)可審計文件數(shù)量NUM.指在審計期間內(nèi)，系統(tǒng)已經(jīng)審計的文件總數(shù).設定文件的審計周期從小到大排列為{T1,T2,…,TD}，審計周期Ti中文件的平均執(zhí)行時間為τi，則NUM的理論值為

(10)

其中，T0=0，表示開始時刻.由于在審計周期Ti內(nèi)存在系統(tǒng)空閑情況，故系統(tǒng)可審計文件數(shù)量小于理論值.特別地，當系統(tǒng)以固定周期Ti審計文件，系統(tǒng)可審計文件數(shù)量計算為

(11)

當審計周期Ti過小，導致系統(tǒng)審計能力迅速達到最大值；當審計周期Ti過大，雖然增加了審計文件數(shù)量，但將出現(xiàn)文件長時間不能審計而系統(tǒng)處于空閑的情況，不僅造成系統(tǒng)資源浪費，并導致用戶體驗下降.因此，應當將文件審計任務有序分布在多個審計周期內(nèi)，既能充分利用系統(tǒng)計算資源，提高文件審計數(shù)量，又能及時滿足文件的審計需求.

審計方案的匹配度反映了審計方案的執(zhí)行強度是否適當，量化文件審計需求和審計方案的執(zhí)行強度予以評價.

定義9. 審計需求R(audit requirement).指文件執(zhí)行數(shù)據(jù)完整性審計的迫切程度，R∈(0,100].文件審計需求最大值表示為Rmax(默認值100).

文件審計需求和文件屬性〈dk,hk〉密切相關，通過歸一化方法將單個因素的影響映射到文件審計需求R的值域，并依據(jù)影響因素的權(quán)重值計算文件審計需求:

(12)

其中，α1和α2分別是損壞概率和訪問熱度的權(quán)重值，且α1+α2=1.假定dmax=10，hmax=10，α1=α2=0.5，文件屬性Attr〈2,5〉，文件的安全需求Rk=35.

定義10. 審計方案執(zhí)行強度(execution strength,ES).ES反映了審計方案檢錯能力和力度,它的最大值表示為ESmax(默認值100).

在文件審計方案〈tk,rrk〉中，文件審計周期分為LTmax個級別，識別率分為LRRmax個級別.審計方案的執(zhí)行強度計算為

(13)其中，β1和β2分別是審計周期和識別率的權(quán)重值，且β1+β2=1.假定LTmax=10，LRRmax=10，β1=β2=0.5，對于審計方案AP〈2,5〉的執(zhí)行強度ES=35.

定義11. 期望強度(EES).EES表示與文件審計需求相匹配的審計方案所需的最小執(zhí)行強度，其計算為

(14)

定義12. 匹配度(match degree,MD).MD表示期望強度與文件實際執(zhí)行強度的匹配程度，其計算為

(15)

MD的大小反映了文件審計方案與最優(yōu)化審計方案的偏離程度，MD數(shù)值為正表示審計方案的執(zhí)行強度高于文件的審計需求；MD數(shù)值為負表示審計方案的執(zhí)行強度弱于文件的審計需求；MD數(shù)值為0表示實際審計方案與文件審計需求正相符.MD過高浪費系統(tǒng)的計算資源，MD過低不能滿足文件的審計需求.

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

3.1 實驗環(huán)境

本文利用PBC庫(pbc-0.5.14)實現(xiàn)了自適應審計的原型系統(tǒng)SA-PDP及對比系統(tǒng)B-PDP，采用C語言開發(fā)，系統(tǒng)參數(shù)為Ubuntu 12.04.3 LTS，Linux 3.8.0-29(x86_64)，4x Intel?Xeon?CPU E5502 @ 1.87 GHz，內(nèi)存16 GB，硬盤ATA Hitachi HTS54501 150 GB.在每個審計周期，按照二八定律生成不同熱度的文件并隨機損壞文件，測試文件大小1 MB.

3.2 存儲開銷和通信開銷分析

為了完成文件自適應審計，云存儲服務器首先記錄文件的屬性信息〈dk,hk〉，然后在文件審計時將其隨證據(jù)信息一起返回給審計者，最后審計者依據(jù)文件屬性〈dk,hk〉更新文件的審計方案〈FIDk,tk,rrk〉.本文方案額外增加的存儲開銷(單位為B)和通信開銷分別為3|int|+|FID|+|float|和2|int|，其中|int|是整型變量的大小，|float|是浮點型變量的大小，|FID|是文件標識的大小.在原型系統(tǒng)SA-PDP中，|int|=4 B，|float|=4 B，|FID|=216 B.每個文件額外增加的存儲開銷和通信開銷分別為232 B和8 B，在可接受的范圍之內(nèi).

3.3 審計效率測試

Fig. 6 Comparison of the total audit time at different numbers of files圖6 不同文件數(shù)目下審計總執(zhí)行時間對比

設定測試時間為72 h，文件數(shù)量為500～1 500，統(tǒng)計審計過程文件的總執(zhí)行時間，如圖6所示.相較于B-PDP，SA-PDP的文件總執(zhí)行時間至少減少了50%，并且SA-PDP審計時間增長趨勢平緩.這是因為，B-PDP按照固定頻率審計文件造成文件被頻繁審計，而SA-PDP按照文件審計需求把文件審計任務分布在多個時間周期內(nèi)，消除了不必要的審計.SA-PDP節(jié)省時間越多，可以審計的文件數(shù)量越多.SA-PDP模型中LASU方法的審計執(zhí)行時間略高于AASU方法.這是因為，采用LASU時，文件要求系統(tǒng)響應其審計請求，造成文件審計次數(shù)增多；LASU犧牲部分審計效率而增加了文件的審計強度.

設定測試時間為72 h，每小時向?qū)徲嬒到y(tǒng)增加4 000個文件，測試系統(tǒng)可審計文件數(shù)量，如圖7所示.審計初期，B-PDP審計文件數(shù)量多于SA-PDP，LASU方法審計文件多于AASU方法；而SA-PDP可審計文件最大能力明顯高于B-PDP.SA-PDP方法將審計任務分布于多個周期，審計初期，部分文件不在審計周期內(nèi)而不被審計.由于LASU方法主動提交審計請求使其初期審計文件次數(shù)多于AASU方法.審計后期，由于B-PDP頻繁審計浪費大量計算資源，使系統(tǒng)過早達到審計極限.而LASU方法積極的審計特性犧牲了部分計算資源，使審計文件數(shù)量低于AASU方法.

Fig. 7 Comparison of the number of audit files at different audit time圖7 不同審計時間內(nèi)可審計文件數(shù)量對比

3.4 審計方案的匹配度比較

首先，依據(jù)一個測試實例，計算并比較不同模型審計方案的匹配度;然后，在實際運行環(huán)境中測試審計方案的動態(tài)匹配程度.

測試實例設計如下：按照二八定律劃分不同熱度、不同損壞概率的文件數(shù)量，計算采用不同模型生成的文件審計方案的匹配度.設定參數(shù)α1=α2=0.5，β1=β2=0.5，dmax=3，hmax=5，LTmax=5，LRRmax=3.由式(12)求得不同屬性文件的審計需求.以屬性〈1,1〉為例，該類型文件的審計需求R〈1,1〉=26.7.

表7顯示了采用不同模型生成審計方案的匹配度.B-PDP模型針對所有文件統(tǒng)一采用適中執(zhí)行強度的審計方案，即AP=〈72 h,95%〉.SA-PDP模型首先依據(jù)文件屬性計算審計需求，然后由式(7)(8)生成與之對應的審計方案.根據(jù)文件的審計需求和生成的審計方案，結(jié)合式(14)(15)計算B-PDP模型和SA-PDP模型生成審計方案的匹配度.

可以看出，采用SA-PDP模型生成的審計方案匹配度為0，即文件審計方案執(zhí)行強度與文件審計需求正相符；采用B-PDP模型針對所有文件采用固定審計方案，匹配度圍繞0波動，表現(xiàn)為審計方案強于或者弱于文件的審計需求.因此，SA-PDP模型可以在滿足文件審計需求的前提下執(zhí)行適當強度的審計方案，克服了B-PDP模型采用過強或者過弱審計方案的問題，并將釋放出的資源用于審計更多文件.

在實際運行環(huán)境中，當審計方案執(zhí)行完畢后，計算審計方案的匹配度，圖8顯示了所有文件的審計方案在不同匹配度的分布.可以看到，B-PDP模型的審計方案較為平均地分布在不同匹配度；而SA-PDP模型的審計方案集中分布于匹配度0周圍.在SA-PDP模型中，與文件審計請求匹配的審計方案比例達到53%，而在B-PDP模型中僅達到了20%.這就表明，相較于B-PDP，SA-PDP更能滿足文件的審計需求，審計方案的匹配率提高了30%以上.此外，結(jié)合圖6和圖8可以看出，SA-PDP不僅滿足了文件的審計請求，并有效減輕了系統(tǒng)的審計負擔.

Fig. 9 The audit number of audit plans at different match degrees圖9 審計次數(shù)在不同匹配度下的分布

圖9比較了審計方案的主動更新算法AASU和被動更新算法LASU的文件審計次數(shù).2種算法匹配度分布基本相同，表明2種審計方案更新算法在滿足文件審計需求的效果基本一致.相較于主動更新算法AASU，被動更新算法LASU算法執(zhí)行了更多次的審計.這是因為，被動更新算法LASU為了及時響應文件的審計請求，接收了更多熱點文件的審計請求.這就表明，LASU算法在滿足文件審計請求的同時，比AASU算法具有更強的審計強度.

4 結(jié)束語

本文設計并實現(xiàn)了一種云存儲環(huán)境下數(shù)據(jù)完整性自適應審計方法SA-PDP.該方法能夠基于文件的屬性信息動態(tài)調(diào)整文件的審計方案，協(xié)調(diào)完成全域文件的審計，不僅能夠滿足文件的審計需求，還能有效減少了系統(tǒng)的審計成本，提高系統(tǒng)的審計效率.后續(xù)工作將針對審計代理的可擴展性和可用性問題進行深入研究.

[1]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)(譚霜, 賈焰, 韓偉紅. 云存儲中的數(shù)據(jù)完整性證明研究及進展[J]. 計算機學報, 2015, 38(1): 164-177)

[2]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)(李暉, 孫文海, 李鳳華, 等. 公共云存儲服務數(shù)據(jù)安全及隱私保護技術(shù)綜述[J]. 計算機研究與發(fā)展, 2014, 51(7): 1397-1409)

[3]Juels A, Kaliski Jr B 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

[4]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

[5]Shacham H, Waters B. Compact proofs of retrievability[C]Proc of the 14th Int Conf on Theory and Application of Cryptology and Information Security. Berlin: Springer, 2008: 90-107

[6]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

[7]Wang Qian, Wang Cong, Li Jin, et al. Enabling public verifiability and data dynamics for storage security in cloud computing[C]Proc of the 14th European Symp on Research in Computer Security. Berlin: Springer, 2009: 355-370

[8]Qin Zhiguang, Wang Shiyu, Zhao Yang, et al. An auditing protocol for data storage in cloud computing with data dynamics[J]. Journal of Computer Research and Development, 2015, 52(10): 2192-2199 (in Chinese)(秦志光, 王士雨, 趙洋, 等. 云存儲服務的動態(tài)數(shù)據(jù)完整性審計方[J]. 計算機研究與發(fā)展, 2015, 52(10): 2192-2199)

[9]Wang Cong, Chow S S M, Wang Qian, et al. Privacy-preserving public auditing for secure cloud storage[J]. IEEE Trans on Computers, 2013, 62(2): 362-375

[10]Zhu Yan, Wang Huaixi, Hu Zexing, et al. Efficient provable data possession for hybrid clouds[C]Proc of the 17th ACM Conf on Computer and Communications Security. New York: ACM, 2010: 756-758

[11]Zhu Yan, Ahn G J, Hu Hongxin, et al. Dynamic audit services for outsourced storages in clouds[J]. IEEE Trans on Services Computing, 2013, 6(2): 227-238

[12]Wang Boyang, Li Baochun, Li Hui. Oruta: Privacy-preserving public auditing for shared data in the cloud[J]. IEEE Trans on Cloud Computing, 2014, 2(1): 43-56

[13]Yu Yong, Ni Jianbing, Au M H, et al. Improved security of a dynamic remote data possession checking protocol for cloud storage[J]. Expert Systems with Applications, 2014, 41(17): 7789-7796

[14]Wang Boyang, Li Baochun, Li Hui. Knox: Privacy-preserving auditing for shared data with large groups in the cloud[C]Proc of the 10th Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2012: 507-525

[15]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

[16]Zhu Yan, Hu Hongxin, 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

[17]Wang Huaqun, Zhang Yuqing. On the knowledge soundness of a cooperative provable data possession scheme in multicloud storage[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(1): 264-267

[18]Wang Huaqun. Proxy provable data possession in public clouds[J]. IEEE Trans on Services Computing, 2013, 6(4): 551-559

[19]Wang Huaqun. Identity-based distributed provable data possession in multicloud storage[J]. IEEE Trans on Services Computing, 2015, 8(2): 328-340

[20]Fu Yanyan, Zhang Min, Chen Kaiqu, et al. Proofs of data possession of multiple copies[J]. Journal of Computer Research and Development, 2014, 51(7): 1410-1416 (in Chinese)(付艷艷, 張敏, 陳開渠, 等. 面向云存儲的多副本文件完整性驗證方案[J]. 計算機研究與發(fā)展, 2014, 51(7): 1410-1416)

Wang Huifeng, born in 1986. PhD candidate in Northwestern Polytechnical University. His main research interests include cloud computing, data security, and massive data storage.

Li Zhanhuai, born in 1961. Professor and PhD supervisor. His main research interests include database theory and massive data storage (lizhh@nwpu.edu.cn).

Zhang Xiao, born in 1978. PhD and associate professor. His main research interestes include green storage and massive data storage (zhangxiao@nwpu.edu.cn).

Sun Jian, born in 1982. PhD candidate. His main research interestes include cloud storage and green storage (qwert3277@163.com).

Zhao Xiaonan, born in 1979. Lecturer and PhD. Her main research interestes include hierarchical storage and cloud storage (zhaoxn@nwpu.edu.cn).

A Self-Adaptive Audit Method of Data Integrity in the Cloud Storage

Wang Huifeng, Li Zhanhuai, Zhang Xiao, Sun Jian, and Zhao Xiaonan

(SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi’an710129)

As an important issue of cloud storage security, data integrity checking has attracted a lot of attention from academia and industry. In order to verify data integrity in the cloud, the researchers have proposed many public audit schemes for data integrity. However, most of the existing schemes are inefficient and waste much computing resource because they adopt fixed parameters for auditing all the files. In other words, they have not considered the issue of coordinating and auditing the large-scale files. In order to improve the audit efficiency of the system, we propose a self-adaptive provable data possession (SA-PDP), which uses a self-adaptive algorithm to adjust the audit tasks for different files and manage the tasks by the audit queues. By the quantitative analysis of the audit requirements of files, it can dynamically adjust the audit plans, which guarantees the dynamic matching between the audit requirements of files and the execution strength of audit plans. In order to enhance the flexibility of updating audit plans, SA-PDP designs two different update algorithms of audit plans on the basis of different initiators. The active update algorithm ensures that the audit system has high coverage rate while the lazy update algorithm can make the audit system timely meet the audit requirements of files. Experimental results show that SA-PDP can reduce more than 50% of the total audit time than the traditional method. And SA-PDP effectively increases the number of audit files in the audit system. Compared with the traditional audit method, SA-PDP can improve the standard-reaching rate of audit plans by more than 30%.

data security; cloud storage; data integrity checking; provable data possession; self-adaptive audit

2015-10-12；

2016-02-16

國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2013AA01A215)；國家自然科學基金項目(61472323,61502392)；中央高校基本科研業(yè)務費專項資金項目(3102015JSJ0009)；華為創(chuàng)新基金項目(YB2014040023) This work was supported by the National High Technology Research and Development Program of China (863 Program) (2013AA01A215), the National Natural Science Foundation of China (61472323, 61502392), the Fundamental Research Funds for the Central Universities (3102015JSJ0009), and the Huawei Innovation Fund (YB2014040023).

張曉(zhangxiao@nwpu.edu.cn)

TP309.2

k是

符和數(shù)據(jù)塊索引的連接，Wi,k=FID‖i，mij,k是文件Mk的數(shù)據(jù)塊mi,k的第j個數(shù)據(jù)扇.文件Mk的認證標簽集合為Φk={φi,k|i∈[1,n]}.循環(huán)生成各個文件列表的認證標簽集合ζΦ={Φk|k∈[1,N]}，N為文件總數(shù).循環(huán)執(zhí)行確認審計階段操作，保證文件正確存儲到云端.