云計算中大數據的快速數據審計算法

鄭英姿，劉 源，趙 鵬

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

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

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

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

針對上述問題，本文設計了一種新的數據結構CDDT(cloud data descriptor table)以提高大規模數據的動態更新效率，并采用代數簽名方案實現云數據的數據持有性證明，其計算成本遠低于基于同態加密系統的證明策略[12]。

1 問題模型與背景知識

1.1 RDA系統模型

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

圖1 RDA模型的主要結構

1.2 代數簽名

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

(1)

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

代數簽名具有以下3個性質：

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

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

(2)

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

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

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

(3)

證明假設文件F分為m個塊，每個塊包含n個扇區(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個比特。

性質32個文件F與G之和的代數簽名等價于2個文件簽名再求和：

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

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

Sγ(F+G)

2 算法設計與實現

2.1 遠端數據審計(RDA)算法

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

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

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

(5)

3) 證明：云服務器收到挑戰消息后需產生證明消息，證明消息為塊σ與驗證模塊標簽(μ)的消息對。證明消息的計算方法如下式所示：

(6)

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

(7)

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

2.2 動態數據更新操作

動態數據更新是RDA的關鍵需求，數據所有者可實時地更新外包數據。為了高效地實現動態外包數據更新，設計了一個新的數據結構CDDT，CDDT也可通過驗證階段抵御重放攻擊。

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

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

2.2.1修改數據操作

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

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

步驟2為修改的數據塊生成一個新標簽，具體方法如下式：

(8)

圖2 數據所有者修改 f[7]情況下CDDT的變化結果

2.2.2插入數據操作

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

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

步驟4將當前CDDT的最大范圍加1。

(9)

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

圖3 CDDT結構中插入操作的實例

2.2.3添加數據操作

圖4 CDDT中添加操作的結果實例

2.2.4刪除數據操作

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

圖5 CDDT刪除操作的實例

3 安全性分析

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

審計模塊從CSP獲得證明消息之后，驗證證明消息以確保存儲的正確性(使用式(7)驗證)?；诖鷶岛灻男再|對式(7)進行如下的擴展：

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

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

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

4 CDDT結構數量的優化設計

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

因為k≥1，所以：

因此，子CDDT的最優數量可計算如下：

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

表1 不同大小文件的k最小值、最大值與最優值

5 仿真實驗與結果分析

5.1 檢測異常行為的性能

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

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

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

(10)

同時：

(11)

因為每個塊包含n個sector(扇區)，則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)

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

圖6 檢測不同數量的外包數據塊所需的挑戰塊數量

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

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

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

5.3 RDA的實驗與分析

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

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

圖7 計算時間與更新塊數量的關系

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

圖8 不同k值下計算時間與更新塊數量的關系

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

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

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

6 結束語

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