基于線性隱藏的租戶副本混淆模型

李 琳，丁艷輝，張永新，趙曉暉

1.山東師范大學 數(shù)學與統(tǒng)計學院，濟南 250358

2.山東師范大學 信息科學與工程學院，濟南 250358

1 引言

軟件即服務(wù)（Software as a Service，SaaS）模式下，成熟的服務(wù)運營商一般采用單實例多租賃的方式，使用同一個實例為多個不同租戶同時提供服務(wù)。服務(wù)商需要建立租戶副本來保證租戶數(shù)據(jù)的訪問效率和可靠性，租戶可以根據(jù)需要定制副本數(shù)量并付費使用。因此租戶需要能夠確認系統(tǒng)是否可靠地存儲了他們的數(shù)據(jù)副本。但是，采用明文存儲的數(shù)據(jù)副本很容易受到服務(wù)提供商內(nèi)部惡意員工的合謀攻擊，比如為了節(jié)省存儲空間，只存儲租戶的一個副本，嚴重破壞租戶經(jīng)濟利益、訪問效率與數(shù)據(jù)可靠性。

現(xiàn)階段，針對服務(wù)提供商合謀欺詐的多副本存儲方案主要采用的是對不同副本采用不同的隨機數(shù)進行加密的方法[1-5]，結(jié)合隨機抽樣模型防止服務(wù)提供商惡意刪除租戶數(shù)據(jù)，保證多個副本的可靠存儲。但是加密后的數(shù)據(jù)需要進行解密才能使用，頻繁的加解密對系統(tǒng)性能影響較大。同時，這些方法主要面向的是文件系統(tǒng)存儲，通過對物理上的數(shù)據(jù)分塊進行加密來生成不同的數(shù)據(jù)副本，不適用于基于SaaS模式的多租戶共享存儲。主要原因是多租戶應(yīng)用場景下同一物理分塊數(shù)據(jù)可能包含多個租戶數(shù)據(jù)，以物理上的數(shù)據(jù)分塊為基礎(chǔ)進行加解密，破壞了租戶之間數(shù)據(jù)與性能隔離的需求。

針對上述問題，本文提出一種非加密的基于線性隱藏的多副本數(shù)據(jù)混淆存儲（Tenant Duplicate Data Obfuscation，TDDO）模型。該模型可以利用不同的混淆密鑰對租戶的副本進行混淆，服務(wù)提供商存儲混淆后的副本數(shù)據(jù)，結(jié)合文獻[6]租戶多副本抽樣檢查模型，可以有效防止服務(wù)提供商為節(jié)省存儲空間，刪除租戶不常用副本問題。并且，為了提高混淆副本可用性，基于蒙特卡羅（Monte Carlo）隨機單調(diào)函數(shù)[7]對TDDO模型進行拓展，制定查詢關(guān)鍵字上的保序策略，實現(xiàn)混淆后租戶副本數(shù)據(jù)關(guān)鍵字的保序，可以支持應(yīng)用在混淆數(shù)據(jù)上的查詢操作。通過實驗分析證明了擴展TDDO模型中的混淆矩陣構(gòu)造消耗、租戶數(shù)據(jù)重構(gòu)消耗以及混淆密鑰存儲代價等。

2 相關(guān)研究

目前，針對SaaS模式多副本的數(shù)據(jù)混淆存儲的相關(guān)研究較少，但是相關(guān)數(shù)據(jù)發(fā)布、數(shù)據(jù)外包服務(wù)和數(shù)據(jù)分析領(lǐng)域針對數(shù)據(jù)保護的研究已經(jīng)取得諸多研究成果，為SaaS模式多副本數(shù)據(jù)混淆提供了良好的借鑒?，F(xiàn)有的數(shù)據(jù)保護方法主要有數(shù)據(jù)加密、數(shù)據(jù)擾動和數(shù)據(jù)分解等。

數(shù)據(jù)加密是安全的隱私保護方法，但是加密后數(shù)據(jù)可操作性大大降低，需要對密文解密后才能進行相關(guān)數(shù)據(jù)操作。因此，提高密文的檢索效率成為當今研究的熱點。在提高密文檢索效率方面，文獻[8]提出基于桶的索引分類機制，在明文索引上建立分組編號，通過桶分組方式來支持密文數(shù)據(jù)的快速查詢。文獻[9]提出保序加密（Order Preserving Encryption，OPE）算法，該算法給出了針對整數(shù)數(shù)據(jù)類型的保序加密方法，并進一步分析在數(shù)據(jù)元組上進行修改、查詢等元組操作的支持性。以文獻[9]為基礎(chǔ)，文獻[10]給出了針對數(shù)據(jù)庫中的字符數(shù)據(jù)類型的保序加密方法，文獻[11]提出可以支持查詢中的比較算符的保序加密算法，并給出了查詢優(yōu)化方案。文獻[12]針對文獻[9]中的保序加密算法存在的安全性較弱問題，進一步提出模保序加密機制，與保序加密相比較，模保序方法具有更好的安全性。但是對于實時性要求較高的多租戶應(yīng)用來說，頻繁地加解密數(shù)據(jù)對應(yīng)用性能影響仍然比較大。

數(shù)據(jù)擾動方法主要通過對原始數(shù)據(jù)進行隨機擾動實現(xiàn)數(shù)據(jù)保護，該方法在數(shù)據(jù)發(fā)布領(lǐng)域應(yīng)用較多。主要使用匿名化[13]實現(xiàn)隱私保護，通用的方法包括擾動（Perturbation）[14]、隨機（Randomization）[15]、置換（Swapping）[16]等。文獻[17-18]提出了k-anonymity機制。文獻[19]提出了l-diversity機制，文獻[20]提出了t-closeness隱私保護機制。數(shù)據(jù)發(fā)布領(lǐng)域的數(shù)據(jù)混淆方法不需要考慮如何逆向推導(dǎo)明文問題，不適用于事務(wù)性應(yīng)用。但是在數(shù)據(jù)恢復(fù)方面，相對于數(shù)據(jù)加密，匿名化方法在輔助信息足夠的情況下，數(shù)據(jù)恢復(fù)的時間代價較小。以隨機擾動方法為例，通過在原始數(shù)據(jù)中添加隨機種子和私有隨機數(shù)進行擾動來隱藏真實數(shù)據(jù)值，只要獲取了隨機種子和隨機數(shù)就可以通過逆運算快速獲取原始數(shù)據(jù)。

文獻[21-22]提出了基于秘密共享的數(shù)據(jù)分解方法，通過對數(shù)據(jù)進行多項式分解為多個子數(shù)據(jù)，分散存儲到多個不相關(guān)的數(shù)據(jù)服務(wù)器中來達到數(shù)據(jù)保護的目的，這種方法可以高效地支持選擇、投影、連接以及聚合查詢等多種數(shù)據(jù)操作。但是基于秘密共享的方法的一個重要應(yīng)用前提是多個數(shù)據(jù)服務(wù)器間不能夠進行串通，否則無法保證數(shù)據(jù)的安全性。并且基于數(shù)據(jù)分解方法對數(shù)據(jù)進行隱私保護后，任何數(shù)據(jù)的查詢訪問均需多方參與進行數(shù)據(jù)恢復(fù)，當數(shù)據(jù)規(guī)模大時，效率會急劇下降。

文獻[23]在總結(jié)分析隱私保護方法的基礎(chǔ)上，基于數(shù)據(jù)模式分解，深入研究了云環(huán)境下多租戶數(shù)據(jù)隱私保護，給出了組合隱私保護機制，較好地解決了單個數(shù)據(jù)節(jié)點上的租戶數(shù)據(jù)隱私保護問題，但是該研究沒有針對云中租戶多數(shù)據(jù)副本的應(yīng)用場景進行研究。

綜上，租戶副本數(shù)據(jù)混淆解決方案可以借鑒隨機擾動[14]方法的思想。假設(shè)數(shù)據(jù)庫R中數(shù)據(jù)元組為rj=，基于隨機擾動的副本混淆方法是對R中的每一個屬性值aij，隨機選取T個隨機值產(chǎn)生T個擾動副本集合其中V為混淆密鑰，并且對于攻擊者而言，只能看到擾動后的副本數(shù)據(jù)，不同的租戶副本有著不同的數(shù)據(jù)表達方式。

但是這種基于全隨機數(shù)的副本混淆方案，使得每個租戶需要保存T個混淆矩陣V存儲對應(yīng)每個的隨機數(shù)，來滿足數(shù)據(jù)恢復(fù)的需要。V中元素的多少與副本中所有屬性值個數(shù)相同。假設(shè)隨機值大小為，則密鑰大小。這樣混淆密鑰V存儲隨著數(shù)據(jù)增多呈倍數(shù)增加。輔助信息存儲代價比較大，靈活性差。

針對上述問題，本文根據(jù)線性隱藏[24]方案提出了一個租戶數(shù)據(jù)副本混淆模型TDDO，然后基于Monte Carlo隨機函數(shù)擴展TDDO模型來支持關(guān)鍵字上的保序，最后給出TDDO模型的安全性分析以及實驗分析。

3 基于線性隱藏的租戶數(shù)據(jù)副本混淆模型

定義1（副本混淆）針對租戶數(shù)據(jù)進行混淆，獲得T個不同的數(shù)據(jù)副本，分別存儲在服務(wù)提供商T個不同的數(shù)據(jù)服務(wù)器上。

定義2（混淆算法EK）用來對租戶副本進行混淆，對于租戶的邏輯視圖R，通過混淆算法，針對數(shù)據(jù)元組進行混淆獲得T個不同的數(shù)據(jù)副本為混淆密鑰，保存在可信第三方中。

定義3（重構(gòu)算法E-1）通過重構(gòu)算法，將混淆后的數(shù)據(jù)還原為原始數(shù)據(jù)R。

TDDO模型主要步驟包括：

（1）生成隨機向量Vk。

根據(jù)租戶定制副本數(shù)量T，生成T個隨機向量集合 {Vk=(vki)1≤i≤n}1≤k≤T,Vik∈Z ，其中 vki與 R 中數(shù)據(jù)元組 rj={aij}1≤i≤n存在一一對應(yīng)關(guān)系 ψ,即 rj←ψ(vki)。Vk為副本混淆的隨機種子，Vk和ψ需要作為密鑰保存在可信第三方上。

（2）針對每個副本建立混淆矩陣VMk。

首先，利用m個簡單多項式函數(shù)集合F={f1,f2,…,fm}建立中間向量 process vector[j],j=1,2,…,m,并且這m個多項式函數(shù)中至少有一個函數(shù)是可逆的，例如{f1(x)=c0x+c1,f2(x)=c2x2+c3,f3(x)=c4x3+c5},其中ci是常系數(shù)。使用m個函數(shù) fj(x)(j=1,2,…,m)，建立 process vector[j]為：

然后，根據(jù)生成的中間向量集合process vector[j],j=1,2,…,m，利用隨機可逆矩陣M對 process vector[m]進行線性隱藏，得到對應(yīng)vki的如下：

此時，M∈GLn(Z)是用來產(chǎn)生混淆向量的混淆密鑰矩陣，假設(shè)并且這樣針對副本的混淆矩陣每個副本的混淆密鑰Kk=(Vk,F,M,ψ)，包括隨機種子Vk，函數(shù)集合F以及混淆密鑰矩陣M。Kk是作為輔助混淆信息存儲在可信第三方上的，服務(wù)提供商無法獲得Kk的任何信息。

根據(jù)步驟（1）和步驟（2）建立生成混淆矩陣VMk后，對于R中的每個數(shù)據(jù)元組rj={aij}1≤i≤n，找到對應(yīng)的vki，計算對應(yīng)rj的混淆值，對副本中每個屬性進行混淆，得到獲得混淆后副本

TDDO模型中的副本混淆算法如下：

算法1副本混淆算法EK

輸入：租戶數(shù)據(jù)R，混淆密鑰K（隨機種子Vk,函數(shù)集合F,淆密鑰矩陣M）。

輸出：混淆副本Rˇ。

算法1的復(fù)雜度為O(mn),在實際應(yīng)用中因為m＜＜n,所以算法1的近似復(fù)雜度為O(n)。對租戶數(shù)據(jù)R進行混淆時，需要根據(jù)隨機種子進行mn次計算獲取混淆矩陣，租戶只需要保存好n個隨機值、T個函數(shù)集合、T個混淆矩陣以及對應(yīng)關(guān)系ψ就能夠生成混淆數(shù)值對租戶數(shù)據(jù)進行混淆。設(shè)隨機值大小為|I|,函數(shù)大小為密鑰K的大小為則有在實際應(yīng)用中因為m＜＜n，所以基于隨機擾動的多副本混淆方案中密鑰大小大約為TDDO模型中密鑰大小的(T×m-2)×n倍。由此可見，TDDO模型大大減小了混淆密鑰的存儲空間。

TDDO模型中的副本重構(gòu)算法，可以看做是混淆算法的逆過程E-1，重構(gòu)副本原始數(shù)據(jù)的一個關(guān)鍵前提是確定vki與元組rj的對應(yīng)關(guān)系ψ,否則重構(gòu)無法實現(xiàn)。為此TDDO模型需要額外保存至少一個副本中的物理表GUID與vki的對應(yīng)關(guān)系，否則無法重構(gòu)副本原始數(shù)據(jù)。上述算法主要針對數(shù)值型數(shù)據(jù)，如果屬性值為非數(shù)值型數(shù)據(jù)，可以將屬性值轉(zhuǎn)化為數(shù)值進行計算。

4 TDDO模型擴展

為了降低密鑰復(fù)雜性，可以用租戶數(shù)據(jù)主關(guān)鍵字代替隨機向量Vk的方法，這樣可以根據(jù)關(guān)鍵字以及混淆值快速定位租戶副本數(shù)據(jù)，而不需要保存對應(yīng)關(guān)系ψ,但是這樣喪失了vki的隨機性，如果攻擊者獲取了部分關(guān)鍵字明文信息，攻擊者有可能根據(jù)混淆后的關(guān)鍵字反推出混淆信息。針對這個問題，本文使用Monte Carlo隨機函數(shù)擴展TDDO模型，在這個模型中，利用元組關(guān)鍵字作為混淆向量，基于Monte Carlo隨機函數(shù)構(gòu)建在關(guān)鍵字屬性上保序的擴展TDDO模型。

4.1 擴展TDDO模型中隨機單調(diào)遞增函數(shù)

Monte Carlo隨機單調(diào)函數(shù)是一個隨機產(chǎn)生的單調(diào)函數(shù) y=f(x)，其中 fl(x)≤f(x)≤fu(x),fl(x)和 fu(x)是給定的上下界函數(shù)，fl(x)和 fu(x)都是單調(diào)遞增函數(shù)，并且它們之間的封閉區(qū)間（envelope）足夠?qū)挕?/p>

首先，在Dom(A)上隨機選擇N個數(shù)據(jù)點 p,amin=p1＜p2＜…＜pN=amax；然后，在的一些分布中隨機選擇ymin，方便起見，假設(shè)ymin=G(amin)=fl(amin)，同樣假設(shè)。接著，對每個 pi，在中隨機選擇 yi，建立N個隨機數(shù)值對，并且y1＜y2＜…＜yN。最后，在 (p1,y1),(p2,y2),…,(pN,yN)利用拉格朗日差法建立函數(shù)集合i=1,2,…,N-1。

擴展TDDO模型中的副本混淆算法EK與副本重構(gòu)算法E-1與上節(jié)類似。擴展TDDO模型中混淆密鑰Kk=(A,G(x),M,p)。

4.2 擴展TDDO模型中的保序策略

針對TDDO模型中混淆副本查詢關(guān)鍵字屬性上的保序問題，制定保序策略。本文主要給出了全保序策略和1-保序策略。

策略1全保序策略（Full Order-Preserving Strategy，F(xiàn)OS）。在FOS中，一個副本的混淆矩陣VMk中的每一混淆列都與關(guān)鍵字A的原始數(shù)據(jù)保持相同的順序?？梢酝ㄟ^控制混淆矩陣M中參數(shù)選擇來實現(xiàn)FOS。最簡單的方法為限制 ?δij∈M,δij＞0,并且所有 fi∈G(x)為Dom(A)上的單調(diào)遞增函數(shù)。

推論1在FOS策略下，混淆矩陣VMk中的每一混淆列都與關(guān)鍵字A的原始數(shù)據(jù)保持相同的順序。（證明過程略）

實現(xiàn)FOS較為簡單，但是由于VMk中每一混淆列都保持原始數(shù)據(jù)的順序，如果攻擊者獲取了部分副本明文信息，他有可能根據(jù)保序關(guān)系以及混淆后副本數(shù)據(jù)反推出部分混淆信息，從而推測出部分混淆密鑰K。為了提高安全性，提出1-保序策略。1-保序策略中只有一個混淆列是保序的。

推論2在POS策略下，混淆矩陣VMk中的混淆列shadow(ai,1)與關(guān)鍵字A的原始數(shù)據(jù)保持相同的順序，其余列不保序。（證明過程與證明1相似）

根據(jù)POS策略，在擴展TDDO模型中，租戶數(shù)據(jù)可以隨時進行更新、插入以及刪除操作，只需要根據(jù)混淆密鑰計算相對應(yīng)屬性的混淆值，就可以快速地計算對應(yīng)混淆副本中的值，而不需要影響其他數(shù)據(jù)。

以插入數(shù)據(jù)為例，假設(shè)租戶插入關(guān)鍵字為ap的數(shù)據(jù)rp，數(shù)據(jù)引擎收到更新請求后，對rp進行混淆，得到T個不同的，然后根據(jù)POS策略插入到相對應(yīng)的混淆副本中，同時更新混淆密鑰。相對于加密的副本混淆方法，TDDO模型具有更高的數(shù)據(jù)處理效率。

4.3 安全性分析

假設(shè)攻擊模型為服務(wù)提供商端的惡意內(nèi)部員工在租戶數(shù)據(jù)不進行數(shù)據(jù)保護的情況下，可以獲得租戶所有副本的明文數(shù)據(jù)，這樣惡意人員之間能夠互相串通來刪除租戶整個數(shù)據(jù)副本，但是基于可信平臺技術(shù)，惡意內(nèi)部人員無法窺視租戶應(yīng)用運行過程，不能夠獲得租戶應(yīng)用過程中產(chǎn)生的任何中間結(jié)果和明文數(shù)據(jù)。TDDO模型通過對R不同的副本進行混淆處理，生成不同的副本數(shù)據(jù)，這樣同一數(shù)據(jù)元組混淆后具有m種不同的存儲內(nèi)容。結(jié)合文獻[6]抽樣方法，當惡意內(nèi)部人員串通勾結(jié)刪除了租戶的一個混淆副本后，在可信第三方針對該混淆副本進行抽樣檢查時，惡意內(nèi)部人員無法通過偽造抽樣數(shù)據(jù)元組的方法來達到欺騙驗證者的目的。同時，由于對應(yīng)同一租戶應(yīng)用邏輯視圖的不同數(shù)據(jù)副本具有不同的混淆存儲內(nèi)容，攻擊者無法利用別的數(shù)據(jù)節(jié)點上的混淆副本來取代本地存儲的副本數(shù)據(jù)，從而可以有效地杜絕服務(wù)提供商惡意刪除租戶副本數(shù)據(jù)。

5 實驗

本文通過實驗來驗證擴展TDDO模型的有效性。主要從混淆矩陣VMk的構(gòu)造代價、密鑰存儲代價、副本重構(gòu)代價、查詢性能幾方面來驗證TDDO模型的性能。從平臺租戶數(shù)據(jù)中隨機選取1×105個元組作為基礎(chǔ)實驗數(shù)據(jù)。

混淆矩陣VMk的構(gòu)造代價實驗主要驗證不同數(shù)據(jù)字段數(shù)目情況下，構(gòu)造混淆矩陣VMk的時間代價消耗。假設(shè)租戶數(shù)據(jù)集合為T，并且T中元組數(shù)目取值范圍是（1×104，2×104，3×104，4×104，5×104），當 T 中數(shù)據(jù)字段數(shù)目為n=3,4,5時，構(gòu)造混淆矩陣VMk的時間消耗如圖1所示。從圖中可知，混淆矩陣的構(gòu)造時間隨著租戶數(shù)據(jù)字段和數(shù)據(jù)元組數(shù)目的增加而呈現(xiàn)線性增加。造成該現(xiàn)象的原因是要對租戶數(shù)據(jù)中每個字段屬性值進行覆蓋，混淆矩陣的規(guī)模會隨著租戶數(shù)據(jù)的增多而增大，因此構(gòu)造時間也相應(yīng)變長。

圖1 混淆矩陣VM k的構(gòu)造代價

密鑰存儲代價實驗主要對基于隨機混淆方法、TDDO模型以及擴展TDDO模型的密鑰存儲代價進行比較。在實驗中，租戶數(shù)據(jù)集元組數(shù)目變化范圍是（1×104～1×105），測試在租戶邏輯視圖數(shù)據(jù)字段數(shù)目n=3以及定制副本數(shù)目T=3的情況下，三種混淆方法的輔助密鑰存儲代價。從圖2中可以看出，隨著租戶數(shù)據(jù)集內(nèi)元組數(shù)目的增大，可信第三方輔助存儲的密鑰呈線性增長，其中擴展TDDO模型方法具有最小的輔助密鑰存儲空間代價，大約為隨機混淆方法存儲代價的1/3。造成該現(xiàn)象的主要原因是擴展TDDO模型只需要存儲密鑰構(gòu)成規(guī)則函數(shù)，而隨機混淆方法需要存儲對應(yīng)租戶所有字段屬性值的混淆矩陣。

圖2 密鑰存儲代價

圖3 副本重構(gòu)代價

查詢性能實驗主要測試基于隨機擾動方法、擴展TDDO模型在保序關(guān)鍵字上與直接在數(shù)據(jù)明文上進行范圍查詢的時間消耗。測試在T中數(shù)據(jù)字段數(shù)目n=3的情況下，分別在租戶數(shù)據(jù)集元組數(shù)據(jù)集上對1×104，2×104，3×104個數(shù)據(jù)元組隨機進行100次范圍查詢的平均時間消耗，如圖4所示。

圖4 索引驗證方法對多租戶查詢性能的影響

從圖4中可以看出，擴展TDDO模型在保序關(guān)鍵字上的范圍數(shù)據(jù)查詢操作，相對于直接在明文數(shù)據(jù)上進行操作處理開銷略大，性能接近。查詢性能遠高于基于隨機擾動的方法，主要原因是如果混淆后的查詢關(guān)鍵字與關(guān)鍵字明文數(shù)據(jù)順序保持一致，只需要計算兩個邊界值就可對混淆數(shù)據(jù)進行范圍查詢。而基于隨機擾動的方法需要預(yù)先查找到對應(yīng)明文關(guān)鍵字的所有隨機值，并計算出所有的查詢關(guān)鍵字進行查詢，因此擴展TDDO模型在保序關(guān)鍵字上具有較好的查詢性能。

6 結(jié)束語

本文針對租戶多副本的存儲安全問題，提出一種可以抵御服務(wù)提供商合謀欺詐的基于線性隱藏的多副本數(shù)據(jù)混淆存儲TDDO模型。該模型可以有效防止服務(wù)提供商為節(jié)省存儲空間刪除租戶不常用副本問題，保證租戶副本完整性。為了提高混淆副本的可用性和查詢效率，基于Mont Carlo隨機函數(shù)對TDDO模型進行擴展，提出了查詢關(guān)鍵字保序的混淆策略。最后，通過分析實驗證明了TDDO模型的安全性和有效性。