文｜李俊平，羅國星 電子科技大學(xué)計算機科學(xué)與工程學(xué)院

1 前言

云存儲服務(wù)屬于基礎(chǔ)架構(gòu)即服務(wù)（IaaS）的范疇，是云計算服務(wù)的最基本服務(wù)形式之一。在云存儲服務(wù)中，云服務(wù)提供商（CSP）為用戶提供無限量的空間供其存儲海量數(shù)據(jù)，并從中收取少量費用，這就為用戶省去了購買存儲設(shè)備的費用。一項調(diào)查結(jié)果顯示，56%的云用戶使用的是IaaS服務(wù)，并且絕大部分IaaS用戶使用的是云存儲服務(wù)和虛擬機租借服務(wù)。由此可見，云存儲服務(wù)在所有云服務(wù)中占據(jù)著非常重要的地位，可以為CSP帶來可觀的經(jīng)濟收益。

然而，用戶在使用云存儲服務(wù)過程中也有很多擔(dān)憂。一項國外調(diào)查結(jié)果[1]顯示，81%的云用戶關(guān)注云數(shù)據(jù)的安全性和機密性，其中數(shù)據(jù)“安全性”指的是數(shù)據(jù)可靠性和完整性。顯然，數(shù)據(jù)安全性和機密性是云服務(wù)中用戶最關(guān)心的問題。

為了保證云端數(shù)據(jù)安全性，CSP（如Google，使用GFS[2]系統(tǒng)）會為每一份數(shù)據(jù)保存多份備份數(shù)據(jù)，當(dāng)發(fā)生數(shù)據(jù)損壞時就可以從完整的數(shù)據(jù)副本里恢復(fù)出正確數(shù)據(jù)。顯然，備份數(shù)據(jù)越多數(shù)據(jù)越安全，但同時卻也降低了云存儲空間的有效利用率。此外，就機密性來說，一般情況下，用戶在存儲數(shù)據(jù)的時候會先將數(shù)據(jù)進行加密，然后將密文存于云端，這就可以避免數(shù)據(jù)信息泄露。

我們提出了一個空間高效的、面向用戶的、安全、可調(diào)節(jié)數(shù)據(jù)存儲方案。本方案基于Shamir秘密分享方案[3]，可以在保證提供與GFS系統(tǒng)相同數(shù)據(jù)安全性的同時有效減少空間使用量。并且，本方案使得用戶可以估計自己數(shù)據(jù)安全性并以此為依據(jù)選擇備份數(shù)據(jù)的數(shù)量。該機制的引入對于用戶和CSP均有好處，對用戶來說，用戶可以租用適當(dāng)?shù)拇鎯臻g，從而節(jié)約存儲費用；而對CSP來說，可以獲得更多的空間服務(wù)更大量的用戶。此外，本方案還可以為備份數(shù)據(jù)提供一定程度上的數(shù)據(jù)機密性。最后，在用戶下載數(shù)據(jù)的時候本方案可以提供不同安全級別的數(shù)據(jù)傳輸模式。

2 相關(guān)工作和設(shè)計目標

GFS[2]系統(tǒng)包括了兩個部分：Master服務(wù)器和Chunk服務(wù)器集群。其中，Master服務(wù)器負責(zé)與用戶的交互和對Chunk服務(wù)器集群的管理。而Chunk服務(wù)器集群負責(zé)存儲用戶的數(shù)據(jù)并接受Master服務(wù)器的調(diào)度和控制。當(dāng)用戶存儲數(shù)據(jù)時，數(shù)據(jù)會被分成固定大小的數(shù)據(jù)分塊存儲在Chunk服務(wù)器集群之中。為了保證數(shù)據(jù)的安全性，GFS為每一個數(shù)據(jù)分塊備份三份數(shù)據(jù)副本。此模式下，GFS系統(tǒng)的有效空間利用率為25%。

從上述分析可以得知，當(dāng)前的云存儲服務(wù)系統(tǒng)有效空間利用率非常低，并且云系統(tǒng)并不為備份數(shù)據(jù)提供數(shù)據(jù)機密性。因此，本文提出了一個空間高效的、面向用戶的、安全、可調(diào)節(jié)數(shù)據(jù)存儲方案。其具體設(shè)計目標包括：1.空間高效性，方案空間利用率應(yīng)比較高；2.方案應(yīng)該是面向用戶的，用戶可以自己估計數(shù)據(jù)的安全性，并根據(jù)安全需求個性化設(shè)置備份數(shù)據(jù)的數(shù)量；3.方案是安全的，方案能為備份數(shù)據(jù)提供一定程度上的數(shù)據(jù)機密性；4.方案是可調(diào)節(jié)的，當(dāng)用戶下載數(shù)據(jù)時系統(tǒng)能為用戶提供不同安全級別的傳輸模式。

3 方案

3.1 系統(tǒng)架構(gòu)

圖1 系統(tǒng)架構(gòu)圖

系統(tǒng)架構(gòu)圖如圖1所示，系統(tǒng)包括用戶模塊和CSP模塊。用戶模塊即使用云存儲服務(wù)的用戶，CSP模塊即云系統(tǒng)模塊。如GFS一樣，CSP模塊也包括了兩類服務(wù)器：Master服務(wù)器和Storage服務(wù)器。

在我們的系統(tǒng)中，用戶模塊除了可以向CSP模塊租用云服務(wù)以外還可以：1. 根據(jù)自己實際安全需求個性化定制自己備份數(shù)據(jù)副本的數(shù)量；2.下載數(shù)據(jù)時可以選擇不同安全級別的傳輸模式。

在CSP模塊中，Master服務(wù)器主要負責(zé)與用戶進行請求交互、管理Storage服務(wù)器集群、根據(jù)用戶設(shè)置的參數(shù)引導(dǎo)Storage服務(wù)器備份數(shù)據(jù)等。而Storage服務(wù)器則主要負責(zé)存儲數(shù)據(jù)、在Master服務(wù)器的引導(dǎo)下備份數(shù)據(jù)等。

在我們的方案中，當(dāng)用戶想要將數(shù)據(jù)存儲至云端的時候，他首先應(yīng)該個性化定制他的數(shù)據(jù)備份方案（即，確定備份數(shù)據(jù)的數(shù)量）。接著他向Master服務(wù)器提出存儲請求，Master服務(wù)器根據(jù)用戶的數(shù)據(jù)總量和備份方案選擇是否向用戶提供云存儲服務(wù)。

3.2 數(shù)據(jù)備份方案

我們的存儲方案與GFS系統(tǒng)一樣，存儲數(shù)據(jù)時用戶數(shù)據(jù)會首先被分成固定大小的數(shù)據(jù)分塊，然后再備份并存儲。但我們的數(shù)據(jù)備份方案卻與GFS完全不一樣。我們的方案基于（K,N）-Shamir秘密分享方案[3]，是一個空間高效性的、面向用戶的備份過程。當(dāng)用戶擁有N中的任意K份數(shù)據(jù)就能恢復(fù)出原始數(shù)據(jù)，具體過程如下所示。

當(dāng)Storage服務(wù)器收到用戶的數(shù)據(jù)之后，它會以數(shù)據(jù)分塊為單位對數(shù)據(jù)進行備份，我們以一個數(shù)據(jù)分塊（記作D）為例來講解數(shù)據(jù)備份過程。服務(wù)器首先將數(shù)據(jù)分塊D分成多份更小的單位數(shù)據(jù)塊（記作URP），于是我們就可以用有序?qū)?i,URPi)來表示D，即D={(i,URPi)┤0

然后我們可以從f(x)上采集不同于之前K個點的其他N個點。這N個點即是Storage服務(wù)器備份完成的數(shù)據(jù)。使用N個中的任意K個點即能重構(gòu)出多項式f(x)，從f(x)中抽取出原始的K個點就能恢復(fù)出原始數(shù)據(jù)。

顯然，只要保證N個點中的K個點正確我們即能輕易地恢復(fù)出原始數(shù)據(jù)，因此我們的方案能保證很強的數(shù)據(jù)安全性。假設(shè)我們用ρ表示一個URP的出錯概率，PS表示D的備份數(shù)據(jù)所能提供的數(shù)據(jù)安全性，于是我們可以用公式（2）來量化我們的數(shù)據(jù)安全性：

值得注意的是，公式（2）中的K是由云服務(wù)商根據(jù)系統(tǒng)能力來確定，備份數(shù)據(jù)的數(shù)量N是由用戶根據(jù)自己的安全需求來確定。

3.3 數(shù)據(jù)存儲過程

在我們的系統(tǒng)中，當(dāng)用戶需要存儲數(shù)據(jù)到云端時。他首先根據(jù)自己的安全需求和公式（2）確定備份數(shù)據(jù)的數(shù)量N，即個性化定制備份方案。

當(dāng)N確定之后，用戶會向Master服務(wù)器發(fā)出請求并告知其數(shù)據(jù)存儲需求，即數(shù)據(jù)存儲總量和備份方案。Master服務(wù)器收到請求之后會根據(jù)用戶的存儲需求確定所有數(shù)據(jù)（包括原始數(shù)據(jù)和備份數(shù)據(jù)）的存儲位置。接著Master服務(wù)器會通知各Storage服務(wù)器準備接收數(shù)據(jù)并按照用戶的備份方案來備份數(shù)據(jù)。當(dāng)上述過程完成之后，Master服務(wù)器會告訴用戶數(shù)據(jù)的存儲位置。接著用戶可以上傳所有數(shù)據(jù)到指定的Storage服務(wù)器。各Storage服務(wù)器收到數(shù)據(jù)之后在Master服務(wù)器的指令引導(dǎo)下完成數(shù)據(jù)的備份和存儲。

值得注意的是，為了保證數(shù)據(jù)的安全性，用戶原始數(shù)據(jù)和備份數(shù)據(jù)所存儲的位置不能相同。當(dāng)Storage服務(wù)器備份完數(shù)據(jù)之后需要將備份數(shù)據(jù)發(fā)送到其他Storage服務(wù)器保存，以提高數(shù)據(jù)的存儲安全性。

3.4 數(shù)據(jù)下載過程

當(dāng)用戶需要從云端下載數(shù)據(jù)時，它會向Master服務(wù)器發(fā)出下載請求，請求中還應(yīng)包含用戶指定的數(shù)據(jù)傳輸模式：即傳輸備份數(shù)據(jù)或者傳輸原始數(shù)據(jù)。

如果用戶選擇傳輸備份數(shù)據(jù)，它應(yīng)該指定傳輸備份數(shù)據(jù)中的特定K個數(shù)據(jù)。在該傳輸模式下，數(shù)據(jù)傳輸?shù)目偭坎]有發(fā)生變化，因為一個數(shù)據(jù)分塊（D）所占空間等于K個單位數(shù)據(jù)塊（URP）所占空間。然而，由于傳輸?shù)氖荎個備份數(shù)據(jù)，這些數(shù)據(jù)是原始數(shù)據(jù)的映射，相當(dāng)于對原始數(shù)據(jù)的加密，即便傳輸過程中被敵手竊取了這些備份數(shù)據(jù)，只要敵手不知道各URP的序列號敵手就無法恢復(fù)出原始數(shù)據(jù)。因此，此模式下傳輸安全級別較高。

如果用戶選擇傳輸原始數(shù)據(jù)，則敵手竊取到的內(nèi)容即是原始數(shù)據(jù)。顯然，該傳輸模式安全級別較低。

4 方案分析

4.1 數(shù)據(jù)存儲安全性

在這里，我們將比較GFS系統(tǒng)備份方案和我們的備份方案所能提供的數(shù)據(jù)安全性。為了使得比較標準一致，我們將GFS系統(tǒng)的數(shù)據(jù)分塊分成NBlock個更小的單位數(shù)據(jù)塊（記作unitreplica），具體做法與我們的存儲方案做法一樣。同樣的，我們用ρ表示單位數(shù)據(jù)塊出錯概率，NGFS表示GFS系統(tǒng)中備份數(shù)據(jù)的數(shù)量，于是GFS系統(tǒng)中備份數(shù)據(jù)所能提供的安全性可以用公式（3）表示：

其中，NBlock與公式（2）中的K的意義完全一樣，而公式（2）中的N=NGFS*NBlock。

如果我們令NBlock=10、ρ=0.01，則根據(jù)公式（2）和公式（3）我們可以得出備份數(shù)據(jù)所提供的數(shù)據(jù)安全性，結(jié)果如圖2所示：

圖2 數(shù)據(jù)安全性（NBlock=10，ρ=0.01）

圖2中，橫坐標是備份數(shù)據(jù)的數(shù)量，縱坐標是備份數(shù)據(jù)所提供的安全性。需要注意的是，在GFS系統(tǒng)中，由于備份方案是復(fù)制整個數(shù)據(jù)分塊，所以，單位數(shù)據(jù)塊的數(shù)量的增長應(yīng)該是按照NBlock的倍數(shù)增長方式進行的：即NBlock=10時，當(dāng)單位數(shù)據(jù)塊數(shù)量為10時，備份了一個數(shù)據(jù)，為20時，備份了兩個數(shù)據(jù)，以此類推。因此，當(dāng)NBlock處于10～20之間時，由于GFS沒有完整的備份完第二個數(shù)據(jù)副本，因此其提供的安全性并沒有增長。

從圖2中我們可以看出，在備份數(shù)據(jù)數(shù)量達到12時我們的方案即能提供99.98%的安全性。而在GFS系統(tǒng)中，要達到同等級別的數(shù)據(jù)安全性則需要備份三份（即NGFS=3）完整數(shù)據(jù)，即備份數(shù)據(jù)數(shù)量為30（3*NBlock）。此時，我們的方案可以比GFS節(jié)約60%((30-12)/30*100%)的存儲空間。

同樣的，當(dāng)NBlock和ρ的值發(fā)生變化時，根據(jù)公式（2）和公式（3）我們依然能得出如圖2所示的同等結(jié)論：我們的存儲方案提供與GFS系統(tǒng)同等數(shù)據(jù)安全性的情況下能比后者節(jié)約大量的存儲空間。因此，我們的方案有著非常高的空間利用率。

4.2 數(shù)據(jù)機密性

從本文3.2節(jié)中我們知道，我們的備份數(shù)據(jù)是從原始的K個單位數(shù)據(jù)中映射出來的N個單位數(shù)據(jù)，這N個數(shù)據(jù)與原來的K個數(shù)據(jù)完全不同。敵手在不知道各單位數(shù)據(jù)的具體序列的情況下，即便竊取了所有數(shù)據(jù)也無法重構(gòu)出原始數(shù)據(jù)，因此可以看作是對原始數(shù)據(jù)的一次加密。所以，我們的方案能為備份數(shù)據(jù)提供一定程度的數(shù)據(jù)機密性。

4.3 傳輸安全級別

從本文3.4節(jié)的介紹可知，用戶在下載數(shù)據(jù)的時候有兩種安全級別的傳輸模式：高安全傳輸模式和低安全傳輸模式。

然而，高安全傳輸模式并不是完美無瑕的。在高安全傳輸模式中，用戶下載完數(shù)據(jù)之后還需要利用公式（1）恢復(fù)出原始數(shù)據(jù)，與低安全傳輸模式相比，此模式下計算開銷相對較大、用戶等待時間相對較長。因此，高安全傳輸模式不適合對數(shù)據(jù)讀取及時性要求比較高的場景。

4.4 備份過程計算開銷

在我們的備份方案中，備份時間TS可以用公式（4）表示：

其中，Tr(s)是讀取大小為s的數(shù)據(jù)所需時間，Tb(s)是備份數(shù)據(jù)所需時間，Tt(s)是傳輸備份數(shù)據(jù)到其他Storage服務(wù)器所需時間，Tw(s)是Storage服務(wù)器存儲備份數(shù)據(jù)所需時間。由于，數(shù)據(jù)讀取和數(shù)據(jù)備份并發(fā)進行，數(shù)據(jù)傳輸和數(shù)據(jù)存儲并發(fā)進行。因此，我們可以認為TS≈Tb(s)+Tt(s)。同時，在公式（1）中的各系數(shù)li(x)獨立于用戶數(shù)據(jù)URPi，可以預(yù)先計算出來。于是，我們在備份的過程中只需要計算公式：

的計算開銷，該公式的計算時間為Tb(s)≈N*K*Tmul(p)，其中，Tmul(p)表示計算有限域Z p上的一次乘法所需時間。再者，如果我們用Tur表示服務(wù)器傳輸單位數(shù)據(jù)塊所需時間，則傳輸備份數(shù)據(jù)所需時間Tt(s)=N*Tur=N*K*Tur/K。于是，TS≈N*K*(Tmul(p)+Tur/K)。又根據(jù)公式（2）可知，N和K大小相差不大，因此，備份方案的時間復(fù)雜度約為O(K2)。

5 結(jié)論

云存儲服務(wù)是云計算服務(wù)的基本服務(wù)形式之一，用戶對云服務(wù)的最大擔(dān)憂是數(shù)據(jù)的安全性。我們調(diào)研了各大CSP，如，Google、Amazon和Microsoft等，發(fā)現(xiàn)在這些云系統(tǒng)中保證數(shù)據(jù)安全性的機制是簡單的存儲多份相同數(shù)據(jù)，這極大降低了存儲空間的利用率。因此，我們設(shè)計了一個基于秘密分享方案的、空間高效的、面向用戶的、安全、可調(diào)節(jié)數(shù)據(jù)存儲方案。方案中利用拉格朗日插值公式和秘密分享技術(shù)備份用戶數(shù)據(jù)，從而達到了對數(shù)據(jù)加密和提高空間利用率雙重目的。本文詳細介紹了方案的架構(gòu)，并結(jié)合設(shè)計目標對方案做了詳盡的分析，完全達到了既定目標。最后，我們通過分析可知備份過程的時間復(fù)雜度為O(K2)，當(dāng)K取值合理時，備份時間開銷是完全可接受的。

[1] Wu J, Ping L, Ge X, et al. Cloud storage as the infrastructure of cloud computing[C]//Intelligent Computing and Cognitive Informatics (ICICCI), 2010 International Conference on. IEEE, 2010: 380-383.

[2] Ghemawat S, Gobioff H, Leung S T. The Google fi le system[C]//ACM SIGOPS Operating Systems Review. ACM, 2003,37(5): 29-43.

[3]Parakh A, Kak S. Space eff i cient secret sharing for implicit data security[J]. Information Sciences, 2011, 181(2): 335-341.

[4]Quadling D A. Lagrange's Interpolation Formula[J]. The Mathematical Gazette, 1966, 50(374): 372-375.

[5]Z. Zheng and M. R. Lyu.A qos-aware fault tolerant middleware fordependable service composition. In DSN , pages 239–248, 2009.

[6] S. Dustdar and L. Juszczyk.Dynamic replication and synchronizationof web services for high availability in mobile ad-hoc networks. ServiceOriented Computing and Applications (SOCA), 1(1):19–33, 2007.

[7]Triantaf i llou P, Taylor D. Using multiple replica classes to improve performance in distributedsystems[C]//Distributed Computing Systems, 1991., 11th International Conference on. IEEE, 1991: 420-428.