云計算中大數(shù)據(jù)的快速數(shù)據(jù)審計算法

鄭英姿，劉 源，趙 鵬

(1.廣東技術(shù)師范大學(xué)天河學(xué)院 計算機(jī)科學(xué)與工程學(xué)院, 廣州 510540；2.桂林理工大學(xué) 信息科學(xué)與工程學(xué)院， 廣西 桂林 541004；3.太原師范學(xué)院 計算機(jī)科學(xué)與技術(shù)系， 太原 030619)

隨著電信4G網(wǎng)絡(luò)與移動互聯(lián)網(wǎng)的迅猛發(fā)展，許多用戶與企業(yè)使用智能移動設(shè)備通過電信網(wǎng)絡(luò)將本地的隱私數(shù)據(jù)保存于云存儲中，從而降低本地的存儲負(fù)擔(dān)，同時有助于數(shù)據(jù)的分享[1-2]。由于云服務(wù)器是半可信的，所以用戶需對云端數(shù)據(jù)進(jìn)行定期審計，方可保證云端數(shù)據(jù)的完整性與安全性[3-4]。

為了提高云端數(shù)據(jù)的安全性，研究者提出了許多針對數(shù)據(jù)完整性的審計算法，主要包括2種類型：數(shù)據(jù)擁有性證明(PDR)[5]、數(shù)據(jù)可取回性證明(POR)[6]。數(shù)據(jù)擁有性證明允許用戶隨時知道其數(shù)據(jù)是否仍然有效地保存于云存儲平臺中，以及是否可以隨時、隨地訪問該數(shù)據(jù)；數(shù)據(jù)可取回性證明驗(yàn)證云數(shù)據(jù)的完整性狀態(tài)，并在損壞小于一定程度時修復(fù)數(shù)據(jù)。

WANG等[7]基于文獻(xiàn)[8]提出了一種帶隱私保護(hù)的審計方案，該方案既具有審計能力也保護(hù)了隱私，但其分塊策略為每個數(shù)據(jù)塊引入了驗(yàn)證標(biāo)簽，極大地提高了存儲的成本。傳統(tǒng)的完整性驗(yàn)證技術(shù)(hash函數(shù)、簽名等)無法應(yīng)用于云存儲場景[9]，許多研究人員設(shè)計了遠(yuǎn)程數(shù)據(jù)審計(RDA)技術(shù)，通過生成隨機(jī)的挑戰(zhàn)驗(yàn)證數(shù)據(jù)持有的證明[10]。可靠的RDA應(yīng)當(dāng)具備以下5點(diǎn)性質(zhì)[11]：① 計算成本、存儲成本及通信成本較低；② 具備公/私鑰2種驗(yàn)證模式；③ 應(yīng)頻繁使用不同的挑戰(zhàn)進(jìn)行驗(yàn)證；④ 可檢測潛在數(shù)據(jù)占用的概率；⑤ 具有動態(tài)的遠(yuǎn)程更新能力。移動智能設(shè)備的計算能力、4G網(wǎng)絡(luò)的通信能力都為有限資源，而已有的RDA方案需頻繁地進(jìn)行驗(yàn)證，為數(shù)據(jù)所有者帶來了不可忽略的計算與通信負(fù)擔(dān)。

針對上述問題，本文設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)CDDT(cloud data descriptor table)以提高大規(guī)模數(shù)據(jù)的動態(tài)更新效率，并采用代數(shù)簽名方案實(shí)現(xiàn)云數(shù)據(jù)的數(shù)據(jù)持有性證明，其計算成本遠(yuǎn)低于基于同態(tài)加密系統(tǒng)的證明策略[12]。

1 問題模型與背景知識

1.1 RDA系統(tǒng)模型

圖1所示是RDA模型的主要結(jié)構(gòu)。RDA模型共包含4個主要實(shí)體：① 數(shù)據(jù)所有者DO：個人、企業(yè)將數(shù)據(jù)上傳到云空間中，后期對外包數(shù)據(jù)進(jìn)行修改、刪除、插入與添加等更新操作；② 云存儲服務(wù)器(CSP)：具有大量的計算資源與存儲資源；③ 第三方審計單位(TPA)：對云存儲內(nèi)的信息進(jìn)行審計有助于降低DO的數(shù)據(jù)審計開銷；④ 用戶：DO已認(rèn)證的受信任用戶，對外包數(shù)據(jù)具有預(yù)定的訪問能力。

圖1 RDA模型的主要結(jié)構(gòu)

1.2 代數(shù)簽名

代數(shù)簽名是一種hash函數(shù)，代數(shù)簽名的主要性質(zhì)是對隨機(jī)塊總和的簽名等價于各塊簽名之和[13]。文件F(包含n個數(shù)據(jù)塊)的代數(shù)簽名可如下計算：

(1)

式中:γ是伽羅華域的元素，包含多個元素γ=(γ1,γ2,…,γn)。

代數(shù)簽名具有以下3個性質(zhì)：

性質(zhì)1長度為r的多個塊f[i]的代數(shù)簽名f[j]計算如下：

Sγ(f[i]|f[j])=Sγ(f[i])⊕rγSγ(f[j])

(2)

性質(zhì)2文件F若干個塊之和的簽名等價于各塊的簽名再求和：

Sγ(f[1])+Sγ(f[2])+…+Sγ(f[m])=

Sγ(f[1]+f[2]+…+f[m])

(3)

證明假設(shè)文件F分為m個塊，每個塊包含n個扇區(qū)(sector)，可得：

Sγ(f[1])+Sγ(f[2])+…+Sγ(f[m])=

f[2][j]+…+f[m][j])=

Sγ(f[1]+f[2]+…+f[m])

(4)

式中：f[i][j]表示文件F中塊i的第j個比特。

性質(zhì)32個文件F與G之和的代數(shù)簽名等價于2個文件簽名再求和：

Sγ(F+G)=Sγ(F)+Sγ(G)

證明計算2個文件F與G的簽名之和(分別包含n個塊)：

Sγ(F+G)

2 算法設(shè)計與實(shí)現(xiàn)

2.1 遠(yuǎn)端數(shù)據(jù)審計(RDA)算法

假設(shè)輸入文件F通過數(shù)據(jù)分段技術(shù)分為m個數(shù)據(jù)塊，其中每個塊包含n個扇區(qū)。如果最后一塊的扇區(qū)數(shù)量小于n，則需增加該塊的大小，增加的數(shù)據(jù)設(shè)為f[m][j]=0(j≤n)。本方案包含以下4個階段：

1) 建立階段：首先DO使用KenGen算法生成公鑰與秘鑰(KenGen(1k)→(pk,sk))，其中k是一個安全參數(shù)；然后，計算每個輸入文件各塊的唯一標(biāo)簽(metadata)，具體計算方法如下：

Ti=Sγ(f[i]‖(IDF‖i‖Li‖Vi))

(5)

3) 證明：云服務(wù)器收到挑戰(zhàn)消息后需產(chǎn)生證明消息，證明消息為塊σ與驗(yàn)證模塊標(biāo)簽(μ)的消息對。證明消息的計算方法如下式所示：

(6)

4) 驗(yàn)證：DO收到證明消息(μ,σ)后，基于塊標(biāo)簽的代數(shù)簽名DO驗(yàn)證塊的完整性，如下式所示：

(7)

為了提高本方法的安全性，在建立步驟中DO使用DO的私鑰對文件id簽名，然后在驗(yàn)證步驟中使用DO的公鑰對簽名進(jìn)行驗(yàn)證。

2.2 動態(tài)數(shù)據(jù)更新操作

動態(tài)數(shù)據(jù)更新是RDA的關(guān)鍵需求，數(shù)據(jù)所有者可實(shí)時地更新外包數(shù)據(jù)。為了高效地實(shí)現(xiàn)動態(tài)外包數(shù)據(jù)更新，設(shè)計了一個新的數(shù)據(jù)結(jié)構(gòu)CDDT，CDDT也可通過驗(yàn)證階段抵御重放攻擊。

CDDT包含兩個關(guān)鍵部分：① 邏輯序號(Li)，表示了數(shù)據(jù)塊的原序號；② 版本號(Vi)，表示塊的當(dāng)前版本號(更新次數(shù))。如果DO更新一個數(shù)據(jù)塊，CDDT中對應(yīng)的Vi加1，表示該塊被修改。DO在將數(shù)據(jù)上傳至云服務(wù)器之前為各文件生成CDDT數(shù)據(jù)結(jié)構(gòu)，然后通過更新操作管理CDDT或交給TPA管理。

如果需在數(shù)據(jù)庫第i個塊之后插入新數(shù)據(jù)，審計模塊必須移動n-i個塊，由此導(dǎo)致審計模塊中過多的計算開銷。為了解決該問題，將CDDT分為k個子CDDT，每個子CDDT大小為n/k，此時在第i塊插入新塊，DO僅需移位n/k-i個塊。該設(shè)計方案降低了大型文件的動態(tài)更新成本。

2.2.1修改數(shù)據(jù)操作

數(shù)據(jù)修改是RDA的一個重要操作，允許DO僅改變少量的塊來更新外包文件，從而避免下載整個文件。假設(shè)修改文件f[i]第i個塊，修改后文件表示為f′[i]，DO的修改算法如下：

步驟1通過比較i與每個子CDDT的范圍搜索請求塊在CDDT中的準(zhǔn)確位置，將塊的版本號加1：Vi=Vi+1。

步驟2為修改的數(shù)據(jù)塊生成一個新標(biāo)簽，具體方法如下式：

(8)

圖2 數(shù)據(jù)所有者修改 f[7]情況下CDDT的變化結(jié)果

2.2.2插入數(shù)據(jù)操作

假設(shè)在文件第i個塊f[i]之后插入一個新的數(shù)據(jù)塊(f*[i+1])，DO的插入算法如下所示：

步驟1基于CDDT的范圍搜索文件F的第i個塊，識別出CDDT中新塊l的準(zhǔn)確位置。

步驟4將當(dāng)前CDDT的最大范圍加1。

(9)

CSP收到插入消息后，在外包文件中位置i之后插入對應(yīng)的新塊。圖3描述了CDDT結(jié)構(gòu)中插入操作的實(shí)例：在文件第7個塊后插入一個新塊，DO僅需將子CDDT最后3項向下移一位，插入的新塊為CDDT2[3]={16,1}，然后增加該子CDDT的最大范圍與下一個子CDDT的最小范圍。

圖3 CDDT結(jié)構(gòu)中插入操作的實(shí)例

2.2.3添加數(shù)據(jù)操作

圖4 CDDT中添加操作的結(jié)果實(shí)例

2.2.4刪除數(shù)據(jù)操作

刪除操作是插入操作的逆操作，將外包文件中第i個塊刪除。首先，DO基于各子CDDT的最大、最小范圍，搜索第i個塊的子CDDT位置(p)；然后，通過將所有的后續(xù)塊(n/k-p)向上移一位來刪除塊p；最終，DO發(fā)送一個刪除消息(IDF,i)至CSP。圖5所示是CDDT刪除操作的實(shí)例，將CDDT1[5]向上移位至CDDT1[4],并將CDDT1,CDDT2,…,CDDTn范圍分別減一。

圖5 CDDT刪除操作的實(shí)例

3 安全性分析

Sγ(IDF‖i‖Li‖Vi)=

審計模塊從CSP獲得證明消息之后，驗(yàn)證證明消息以確保存儲的正確性(使用式(7)驗(yàn)證)?；诖鷶?shù)簽名的性質(zhì)對式(7)進(jìn)行如下的擴(kuò)展：

Sγ(f[cs1]+…+f[csc])=

Sγ(f[cs1]+…+Sγ(f[csc]))=

本方案使用代數(shù)簽名產(chǎn)生一個小數(shù)據(jù)量作為每個塊的簽名，但可追蹤外包文件任意的修改操作。代數(shù)簽名也可驗(yàn)證分布式存儲系統(tǒng)中的分布式大數(shù)據(jù)，其計算與通信成本較低。另一方面，代數(shù)簽名中產(chǎn)生沖突的概率是可忽略的，例如：如果簽名的長度是64比特，產(chǎn)生沖突的概率僅為2-64。綜上所述，代數(shù)簽名技術(shù)對認(rèn)證外包數(shù)據(jù)的正確性是有效的，對于DO為移動設(shè)備的情況，效果尤佳。

4 CDDT結(jié)構(gòu)數(shù)量的優(yōu)化設(shè)計

文獻(xiàn)[15]插入或刪除一個塊，審計模塊需將剩余的數(shù)據(jù)塊依次移位，其審計模塊的計算復(fù)雜度為O(n)。本文提出的新數(shù)據(jù)結(jié)構(gòu)解決了該問題，將數(shù)據(jù)塊保存于k個列表中。本方案審計模塊的計算復(fù)雜度僅為O(n/k)，搜索塊位置最差情況的計算復(fù)雜度為O(k)。本方案優(yōu)于文獻(xiàn)[15]的前提條件為：

因?yàn)閗≥1，所以：

因此，子CDDT的最優(yōu)數(shù)量可計算如下：

表1所示是1～100 GB文件的最小、最大與最優(yōu)的子CDDT表數(shù)量(k)，假設(shè)每個塊的大小為4 kB。

表1 不同大小文件的k最小值、最大值與最優(yōu)值

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 檢測異常行為的性能

本方法采用隨機(jī)采樣的策略以降低CSP的負(fù)載，將輸入文件F分為若干塊m，隨機(jī)選擇少量的塊c作為一個挑戰(zhàn)。

假設(shè)CSP修改m個外包塊中的y個塊，則修改塊的概率等于py=y/m。假設(shè)c是挑戰(zhàn)步驟中DO需驗(yàn)證的外包數(shù)據(jù)塊數(shù)，n是每塊的sector(扇區(qū))數(shù)量。假設(shè)x是離散的隨機(jī)變量，表示DO選擇的塊數(shù)量，假設(shè)Px(x≥1)表示DO選擇的塊至少有一個被服務(wù)器修改的概率，可如下計算Px：

Px(x≥1)=1-Px(x=1)=

(10)

同時：

(11)

因?yàn)槊總€塊包含n個sector(扇區(qū))，則sector粒度的概率(ps)可如下計算：

py≥1-(1-ps)n?

(1-py)c≤((1-ps)n)c?

1-(1-py)c≥1-(1-ps)nc?

px(x≥1)≥1-(1-ps)nc

另一方面：

(12)

假設(shè)DO將1 GB文件分為125 000個塊，塊大小為8 kB，將各塊上傳到云存儲。圖6所示是檢測不同數(shù)量的外包數(shù)據(jù)塊所需的挑戰(zhàn)塊數(shù)量。如果服務(wù)器的Py=0.1，則DO需隨機(jī)地選擇98個塊作為一個挑戰(zhàn)，方可獲得0.999 99以上的Px，因此在保持高檢測率的前提下，可通過增加破壞塊的數(shù)量降低挑戰(zhàn)塊的數(shù)量。

圖6 檢測不同數(shù)量的外包數(shù)據(jù)塊所需的挑戰(zhàn)塊數(shù)量

5.2 RDA的通信與計算成本分析

RDA有3個重要的性能指標(biāo)：① 通信成本；② 數(shù)據(jù)審計的計算成本；③ 動態(tài)數(shù)據(jù)更新的計算成本。將本方法與文獻(xiàn)[16](EPA)、文獻(xiàn)[15](ESDA)進(jìn)行比較。EPA是一種動態(tài)的云計算數(shù)據(jù)審計技術(shù)，該技術(shù)考慮了TPA以及動態(tài)云存儲的驗(yàn)證，與本算法考慮的要素較為接近。ESDA是一種考慮隱私保護(hù)的云計算數(shù)據(jù)審計技術(shù)，該技術(shù)也支持動態(tài)數(shù)據(jù)操作，并且實(shí)現(xiàn)了較好的審計效果。表2所示是3種RDA方案的比較結(jié)果。EPA在動態(tài)數(shù)據(jù)更新操作中的計算開銷最大，原因在于EPA中使用MHT數(shù)據(jù)結(jié)構(gòu)來檢查外包數(shù)據(jù)塊的完整性與更新操作，復(fù)雜度較高。ESDA在添加操作與修改操作的計算方面復(fù)雜度較低(O(c))，但在插入與刪除操作中更新一個塊，驗(yàn)證模塊必須將數(shù)據(jù)結(jié)構(gòu)中的m-i個實(shí)體進(jìn)行移位，其計算復(fù)雜度為O(m)。本文設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)(CDDT)來降低計算成本，插入或刪除一個數(shù)據(jù)塊，審計模塊僅移位一部分的外包數(shù)據(jù)塊(n/k-i)，審計模塊的計算成本為O(n/k)。

表2 3種審計算法不同模塊的通信與計算成本

5.3 RDA的實(shí)驗(yàn)與分析

使用Eualyptus IaaS云對本文RDA進(jìn)行實(shí)驗(yàn)。Eucalyptus是基于Linux的開源軟件，可安裝于linux操作系統(tǒng)上[17]。本文實(shí)驗(yàn)基于Intel 酷睿i3處理器，主頻為3.7 GHz，采用C語言編程實(shí)現(xiàn)。使用PBC(版本0.5.14)仿真EPA與ESDA的數(shù)據(jù)審計方案，EPA與ESDA均使用160比特的橢圓曲線。每組實(shí)驗(yàn)獨(dú)立運(yùn)行20次，將平均值作為最終的結(jié)果。

首先，測試本方案對數(shù)據(jù)頻繁更新的效果。選擇1 GB的外包文件，共有125 000個數(shù)據(jù)塊，將更新的塊數(shù)量設(shè)為100～1 000，間隔設(shè)為8。圖7所示是計算時間與更新塊數(shù)量的關(guān)系，EPA的插入與刪除操作中，審計模塊需在MHT樹中搜索目標(biāo)塊的精確位置，并重新計算新葉節(jié)點(diǎn)的hash值，導(dǎo)致審計模塊的計算成本較高。ESDA搜索塊i的位置后，對于插入與刪除操作，審計模塊需將剩下的n-i個塊進(jìn)行移位，如果多次進(jìn)行該處理，則會導(dǎo)致較高的計算成本。本方案通過使用10個CDDT極大地降低了計算成本，效果優(yōu)于其他兩種算法。

圖7 計算時間與更新塊數(shù)量的關(guān)系

第2組實(shí)驗(yàn)測試了子表數(shù)量k對數(shù)據(jù)更新計算成本的影響。圖8所示是不同k值下計算時間與更新塊數(shù)量的關(guān)系，k值越高，計算時間越低。當(dāng)更新數(shù)據(jù)塊數(shù)量較高時，審計模塊產(chǎn)生不可忽略的計算開銷?？赏ㄟ^最優(yōu)k值降低計算成本，例如：當(dāng)k=100時，插入1 000個塊所需的計算時間為0.156 s，k值提高為353時，其計算時間降為0.140 s。

圖8 不同k值下計算時間與更新塊數(shù)量的關(guān)系

第3組實(shí)驗(yàn)測試了文件大小對動態(tài)數(shù)據(jù)更新計算成本的影響。將文件大小設(shè)為1～10 GB，對外包文件隨機(jī)地插入或刪除100個塊。圖9所示是3種RDA方案對大型文件審計的計算時間。對于10 GB的文件，EPA需管理MHT中大量的數(shù)據(jù)集，其計算時間最高；ESDA的審計模塊在插入與刪除一個數(shù)據(jù)塊時需對大量的塊進(jìn)行移位操作，消耗了較高的計算時間；本方法受益于子CDDT劃分的設(shè)計，使用10個子CDDT與代數(shù)簽名方案提高了計算效率，可看出本算法對大規(guī)模文件具有較好的效果，明顯優(yōu)于EPA與ESDA兩種算法。

圖9 3種RDA方案對大型文件審計的計算時間

第4組實(shí)驗(yàn)測試了本方法對大型文件的效率。圖10所示是本方案隨著數(shù)據(jù)塊數(shù)量與文件大小增加的計算時間。對于1 GB的文件，更新 1 000個塊所需的時間為0.218 s；對于100 GB的文件，更新 1 000個塊所需的時間為10.811 s。圖10的結(jié)果顯示，若保持k值與文件大小同步增加，可保持較低的計算時間，可見本算法適用于大數(shù)據(jù)審計的場景。

6 結(jié)束語

移動智能設(shè)備的普及使得云存儲成為電信網(wǎng)絡(luò)的一個重要應(yīng)用。為了保證云端外包數(shù)據(jù)的完整性與安全性，移動智能設(shè)備需對外包數(shù)據(jù)進(jìn)行頻繁的審計，為了降低移動智能設(shè)備在審計操作中的計算與通信成本，設(shè)計了一種針對云存儲大數(shù)據(jù)的RDA算法。提出了CDDT代替對云端數(shù)據(jù)的直接操作，通過將CDDT分為若干子CDDT降低CDDT操作的搜索與計算成本。此外，使用代數(shù)簽名簡單有效地完成了RDA的挑戰(zhàn)與證明操作。實(shí)驗(yàn)結(jié)果表明，本算法極大地降低了云端外包數(shù)據(jù)審計的計算與通信成本，優(yōu)于其他的審計算法。