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

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

1.山東師范大學 數學與統計學院，濟南 250358

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

1 引言

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

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

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

2 相關研究

目前，針對SaaS模式多副本的數據混淆存儲的相關研究較少，但是相關數據發布、數據外包服務和數據分析領域針對數據保護的研究已經取得諸多研究成果，為SaaS模式多副本數據混淆提供了良好的借鑒。現有的數據保護方法主要有數據加密、數據擾動和數據分解等。

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

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

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

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

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

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

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

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

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

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

定義3（重構算法E-1）通過重構算法，將混淆后的數據還原為原始數據R。

TDDO模型主要步驟包括：

（1）生成隨機向量Vk。

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

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

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

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

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

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

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

算法1副本混淆算法EK

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

輸出：混淆副本Rˇ。

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

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

4 TDDO模型擴展

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

4.1 擴展TDDO模型中隨機單調遞增函數

Monte Carlo隨機單調函數是一個隨機產生的單調函數 y=f(x)，其中 fl(x)≤f(x)≤fu(x),fl(x)和 fu(x)是給定的上下界函數，fl(x)和 fu(x)都是單調遞增函數，并且它們之間的封閉區間（envelope）足夠寬。

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

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

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

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

策略1全保序策略（Full Order-Preserving Strategy，FOS）。在FOS中，一個副本的混淆矩陣VMk中的每一混淆列都與關鍵字A的原始數據保持相同的順序。可以通過控制混淆矩陣M中參數選擇來實現FOS。最簡單的方法為限制 ?δij∈M,δij＞0,并且所有 fi∈G(x)為Dom(A)上的單調遞增函數。

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

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

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

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

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

4.3 安全性分析

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

5 實驗

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

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

圖1 混淆矩陣VM k的構造代價

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

圖2 密鑰存儲代價

圖3 副本重構代價

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

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

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

6 結束語

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