一種基于分塊混淆的動態數據隱私保護機制

張宏磊 史玉良 張世棟 周中民 崔立真

(山東大學計算機科學與技術學院 濟南 250101) (yanlei1214@126.com)

?

一種基于分塊混淆的動態數據隱私保護機制

張宏磊 史玉良 張世棟 周中民 崔立真

(山東大學計算機科學與技術學院 濟南 250101) (yanlei1214@126.com)

云計算環境下，基于分塊混淆的隱私保護機制通過對租戶個性化隱私保護需求及應用性能的有效結合，實現了隱私信息在明文狀態下的保護.然而隨著云端多租戶應用的持續運行，一方面，租戶數據的插入、刪除和修改等業務操作將會影響底層數據存儲的分布狀態，使分塊間的關聯關系因數據分布的不均勻而面臨極大的泄露風險；另一方面，攻擊者仍然可以通過局部時間內各分塊的操作日志以及對應的數據快照分析出部分隱私信息.針對上述挑戰，在三方安全交互模型的基礎上，提出一種面向分塊混淆的動態數據隱私保護機制.該機制通過可信第三方對新插入和修改的數據進行緩存并在滿足條件時將數據進行分組和存儲；通過保留關鍵分片來保證刪除操作中被刪數據和剩余數據的隱私安全；通過偽造數據回收機制實現存儲資源消耗的降低和應用性能的優化.通過實驗證明，提出的動態數據隱私保護機制具有較好的可行性和實用性.

多租戶；分塊混淆；動態數據；隱私保護；可信第三方

隨著云計算的迅速發展，具有多租戶特點的軟件即服務(software as a service, SaaS)應用以其低費用、規模效益的商業運營模式和單實例、按需定制的軟件交付特點，被越來越多的企業和服務商所采用.

在SaaS應用中，一方面，租戶通過按需租賃和個性化定制，在滿足自身業務需要的同時，節省了用于基礎設施和后續升級、維護、管理等方面的高昂費用；另一方面，通過與SaaS服務商簽訂服務等級協議(service level agreement， SLA)，保證了應用的服務質量，維護了租戶和服務商雙方的利益.

然而，隨著SaaS應用的廣泛推廣和使用，租戶隱私數據在云中的安全性也受到了越來越多的關注.在多租戶應用中，為了滿足租戶對數據進行業務操作的需求，租戶敏感數據通常需要以明文的形式在非完全可信的服務商處進行存儲和處理，使租戶的隱私數據脫離了租戶的直接控制，可能被服務提供商惡意泄露.例如，在利益的驅動下，服務商可以將租賃其應用的某公司的產品定價信息及其客戶關系轉賣給其競爭對手，導致該公司經濟利益受損.

針對SaaS應用面臨的租戶隱私泄露問題，我們在文獻[1]中提出了一種基于分塊混淆的數據組合隱私保護機制：1)根據租戶定制的隱私約束將組合隱私屬性切分到不同的分塊中并混淆不同分片間的關聯關系；2)針對分塊中數據分布不均衡導致的隱私泄露問題，提出基于偽造數據的均衡化機制，通過添加偽造數據使各分塊的分布達到均衡；3)通過與可信第三方進行交互構建混淆數據的重構機制，保證租戶隱私數據的可用性.

文獻[2-3]在此基礎上又分別從不同方面進行了補充和優化.文獻[2]基于租戶的個性化隱私保護和事務處理需求，提出了基于策略的個性化隱私保護機制；文獻[3]通過鍵能算法對屬性進行聚類，將關聯程度較高的屬性盡量分到同一分塊中，通過減少分塊間的連接次數對應用性能進行提高.

然而在云計算環境下，隨著多租戶應用的持續運行，租戶對數據的增加、刪除、修改等業務操作將導致底層數據存儲的持續變化，各分塊的分布規律也將相應地發生變化，當數據分布不再均勻時，分片間的關聯關系將以較大概率面臨著被泄露的風險.另一方面，若攻擊者可以獲取局部時間內各分塊的操作日志和數據快照，仍然可以通過對比分析推測出這部分數據中蘊含的隱私信息，這就要求所采取的隱私保護機制必須能適應這種變化，確保租戶的隱私保護需求持續得到滿足.

針對上述挑戰，本文提出基于分塊混淆的動態數據隱私保護機制，該機制以水平分組為單位對租戶業務操作進行處理，通過可信第三方對新插入和修改的數據進行緩存并在滿足條件時將數據進行分組并上傳至存儲層進行存儲；通過保留關鍵分片來保證刪除操作中被刪數據和剩余數據的隱私安全；最后提出偽造數據回收機制，降低了存儲資源的消耗并實現了應用性能的優化.論文最后進行了實驗驗證和性能評估，實驗結果表明：該機制使租戶隱私在業務處理過程中得到有效保護的同時，也具有良好的處理性能.

1 相關工作

針對隱私保護，數據加密和數據混淆是目前比較成熟的2種解決方案.但是加密后的數據往往丟失了可操作性，因此提高密文檢索速度和處理效率是加密隱私保護的研究熱點.文獻[4]分析了云計算的特征，提出一種在云中實現隱私保護的關鍵詞檢索模式，它支持服務提供商可以參與部分解密工作以減少客戶端負擔，同時在加密數據上實現關鍵詞檢索，以保護租戶數據隱私和用戶查詢隱私；文獻[5]利用“理想格(ideal lattice)”的數學對象構造了隱私同態(privacy homomorphism)算法，使人們可以充分地操作加密狀態的數據，加密方法對數據處理性能有較大影響，研究者提出通過其他方式來防止泄露隱私；文獻[6]提出了(α,k)-匿名原則，其在保證數據表滿足k-匿名化原則的同時，要求每個等價類中任一敏感屬性值相關記錄的百分比不高于α，從而避免攻擊者利用一致性攻擊和背景知識攻擊來確認敏感數據與個人身份的聯系；文獻[7]提出l-diversity原則，要求每個等價類的敏感屬性至少有l個不同的值，使得攻擊者最多以1l的概率確認某個體的敏感信息；文獻[8]有效結合了信息分解和數據加密，提出使用隱私約束的概念來實現信息分解，提出隱私約束的概念，用來描述需要經過加密保護的數據屬性和同時出現會泄露隱私的數據屬性組合，根據這些隱私約束，經過信息分解得到滿足要求的分塊模式，其中各個數據分塊之間的關聯關系保存在客戶端；文獻[9]針對事務數據庫隱私保護發布的數據安全性與效用性不足，提出了一種有效的滿足差分隱私約束的事物數據發布策略(transaction data publication strategy， TDPS)，該策略基于項集I，構建事務數據庫D的完整樹Trie，然后基于壓縮感知技術對完整樹添加滿足拆分隱私約束的噪音得到含噪Trie樹，最后在此樹上進行頻繁項集挖掘任務，很好地保護了數據隱私.但是，這些研究主要面向的是數據發布領域中的隱私保護問題，很少涉及對隱私數據的增刪改操作.

對于動態數據的隱私保護，目前已經有多鐘不同的方法相繼被提出[10-14]，但是這些方法解決的也大都是面向數據發布和數據挖掘中的動態數據隱私保護，并不適合SaaS應用中的隱私保護.

文獻[10]對持續增長數據集的隱私保護做了相應的研究，其思路是新的記錄要插入必須滿足2個限定條件：1)待插入記錄數不能少于一定的數量；2)待插入的記錄集要符合l-diversity 技術的要求.如果有其一達不到要求就不能插入.該方法存在數據更新不及時且數據的更新只局限于插入這一種操作的問題.同樣地，文獻[11]和文獻[12]中提出的方法也只是針對插入操作對數據進行隱私保護，而在SaaS應用中租戶需要經常對數據進行插入、刪除和修改等操作，因此這些方法并不適應于SaaS應用.文獻[13]提出了m-invariance匿名機制，其核心思想是在數據集的任何一個快照中，一條指定的數據記錄都只能被放置在具有固定的隱私屬性集的分片中，該方法很好地解決了數據發布過程中的值相關攻擊.文獻[14]針對數據發布中存在的值等價攻擊問題，在文獻[13]的基礎上利用“最小割”算法提出了一種基于圖的匿名算法，該算法同時對值相關攻擊和值等價攻擊問題進行了保護.文獻[15]針對動態變化的外包數據庫的隱私保護問題，在數據分解的基礎上提出將用戶最近插入和修改的數據通過加密后存放到外包數據庫中，將加密秘鑰保存在客戶端，在刪除數據時只刪除包含識別信息的部分數據，該方法要求客戶端保存加密秘鑰并且需要明確區分標識信息和敏感信息，并且在業務操作中需要頻繁進行加密和解密操作.而在SaaS應用中，租戶不需要存儲任何信息或擁有任何計算能力，并且租戶需要能夠對隱私需求進行個性化定制，指定的隱私約束中往往無法明確區分識別信息和敏感信息，因此文獻[15]中的隱私保護方法并不能完全適合SaaS應用的動態隱私保護.

雖然上面提出的各種方法很好地應對了數據發布和數據挖掘中存在的各種動態隱私保護問題，但由于SaaS應用與數據發布具有完全不同的特點，使得上述方法都不能完全適應于SaaS應用.文獻[1]針對SaaS應用，提出一種基于分塊的隱私保護機制，根據租戶提出的隱私約束將租戶數據中的組合隱私分解到不同的數據分塊中，并隱藏分片之間的關聯關系，實現了明文狀態下的SaaS數據隱私保護，通過插入偽造數據的方式，確保各分塊中數據分布的持續均衡，防止服務運營商泄露租戶的數據組合隱私，但該文獻并沒有提及租戶對數據進行插入、刪除和修改時如何對隱私數據進行保護，存在泄露數據塊關聯關系的危險.

2 問題分析

隨著信息技術的高速發展，對數據的采集、存儲和分析變得更加方便和快捷，技術手段也更加先進和完善.在現實生活中，由于企業管理和權限分配的不完善，云計算服務中經常會發生服務商或數據庫管理員(本文將惡意泄露租戶隱私的相關人員統稱為攻擊者)通過各種技術手段惡意獲取用戶數據及其變更記錄，并通過分析后泄露用戶隱私的情況.雖然租戶數據在存儲到云端之前已經通過分塊混淆隱藏了不同分片之間的關聯關系，但攻擊者仍然可以通過對數據變更后各分塊的不均勻分布情況或者數據變更日志及相應的局部數據快照進行分析得到部分租戶的隱私信息.下面我們將通過圖1所示示例對文獻[1]所提隱私保護機制在租戶進行業務操作時面臨的隱私泄露威脅及其他不足分別進行分析.

Fig. 1 Diagram of data updating.圖1 數據變更示意圖

圖1中Snapshot1是進行業務操作前根據文獻[1]提出的方法對租戶數據的邏輯視圖進行分塊后得到的數據對象物理存儲模式，Snapshot2是對Snapshot1分別執行了1次插入、刪除和修改后得到的數據對象物理存儲模式.表1為通過某種工具或技術獲取的這段時間內租戶對數據庫的業務操作日志.

1) 通過操作日志和數據快照泄露租戶隱私

當攻擊者獲取到數據變更日志(表1)以及變更前后的數據快照Snapshot1和Snapshot2后，通過日志可以發現這3個分塊同時插入和刪除過分片，通過對比Snapshot1和Snapshot2可以推測出該過程刪除了1條關于Bob的數據并且Bob患有疾病Measles，新增了1條Greg的數據且Greg患有疾病Flu.由于同時在Chunk2和Chunk3中分別修改了1個分片的取值，可以推斷出43歲且原先郵編為62 000的那位病人其患病信息已由Measles變更為Flu且其郵編也發生了變化.

2) 分塊數據不均勻導致租戶隱私泄露

3) 由分塊均衡引起的偽造數據激增問題

圖1中，業務操作完成后，Chunk3中分片只有2種取值：Cancer和Flu，且取值Flu所占比例為23.此時要使其符合租戶指定的隱私保護水平要求13，則Chunk3中的分片數量至少需要達到12條，即至少需要向Chunk3中插入6條偽造數據進行均衡.此時偽造數據占總數據量的比值將達到12，在云計算環境中，隨著用戶數據量的急劇增加，較高的偽造數據占比不僅會浪費大量的存儲空間，而且也會導致應用性能的急劇下降.另一方面，文獻[1]提出的均衡策略是通過不斷插入偽造分片實現的，隨著應用的持續運行，系統中的偽造數據會一直增加，而在數據量較大時，再想通過刪除偽造數據來實現數據均衡將需要付出巨大的計算代價.

從上面的舉例分析可以看到，如果直接將租戶的業務操作作用于云端數據，不僅會直接泄露本次被操作的租戶的隱私信息，還會導致表中其他隱私數據因為分塊中數據分布的不均勻而引起泄露.此外不合理的均衡機制也會導致系統因較高的偽造數據占比而付出較大的存儲消耗和性能代價.

因此，為了應對SaaS應用中因多租戶對數據的業務操作而引起的隱私泄露和分塊均衡問題，本文提出先對數據進行水平分組，并以更細粒度的水平分組為單位對租戶數據進行隱私保護，引入分塊信息熵對分塊的均衡狀態進行評估，通過保證各水平分組在租戶業務操作中的安全性，實現對整體隱私數據的保護.通過在水平分組時對分組均衡狀態的兼顧以及后續對分組合并和偽造數據的回收，降低偽造數據對應用性能的影響.

3 動態數據隱私保護框架

針對租戶業務操作過程所面對的隱私泄露問題及其他不足，本文提出了基于分塊混淆的動態數據隱私保護框架，如圖2所示.該模型共包含應用層、隱私保護層、存儲層和可信第三方4個部分.其中應用層負責管理租戶租賃的應用并對租戶的業務請求做出響應；隱私保護層負責對租戶提交的業務請求進行處理并根據租戶定制的隱私保護需求在處理過程中對租戶隱私進行保護；存儲層負責對分塊處理后的租戶數據進行存儲；可信第三方負責管理租戶最新更新的數據以及租戶的隱私保護策略，并通過身份認證機制防止攻擊者冒用身份對數據和隱私保護策略越權訪問.

Fig. 2 Dynamic privacy protection framework.圖2 動態隱私保護框架

圖2所示的框架中，應用層接收到租戶的業務請求后，通過步驟①將請求轉發至數據更新模塊進行處理；數據更新模塊根據請求類型決定需要對存儲層和可信第三方中分別進行哪些操作，并通過步驟②分別發送對應的操作指令；身份驗證模塊負責對操作進行驗證；臨時數據管理模塊負責對最近更新的數據進行分組，分組完成后將通知分塊處理模塊；分塊處理模塊通過步驟③從可信第三方調用分塊策略對臨時數據分組進行分塊處理，分塊完成后通過步驟④通知均衡模塊對各分塊添加的偽造數據進行均衡數理，并通過步驟⑤將均衡后的分塊存入存儲層；偽造數據回收模塊通過步驟⑥對存儲層中各分組數據剩余量進行監控，定時回收多余偽造數據.

4 動態數據隱私保護機制的實現

第2，3節舉例分析了SaaS應用持續運行過程中因租戶業務操作引起的隱私泄露和分塊均衡問題，并針對這些問題提出了基于分塊混淆的動態數據隱私保護框架.本節將在第3節的基礎上，詳細介紹該框架的相關概念及具體實現，并將通過具體的公式和定理證明通過該框架對數據進行業務操作時可有效防止租戶隱私的泄露.下面首先給出相關定義.

4.1 相關定義

定義1. 水平分組G.G是租戶數據邏輯視圖T的一個子集，因此租戶數據邏輯視圖T可以表示為T=∪Gi(1≤i≤m)，且其中任意2個不同的水平分組Gi和Gj均不重疊，即Gi∩Gj=φ(1≤i

定義2. 隱私保護策略(privacy protection strategy， PPS).根據租戶提出的隱私約束將邏輯視圖T的屬性集Attrs={A1,A2,…,An}劃分為幾個不同子集，即Attrs=∪subAttrsi(i=1,2,…,k)，其中k為分塊數，使得每個子集均不違背隱私約束條件，且任意2個子集均不相互重疊，即subAttrsi∩subAttrsj=φ(1≤i

定義3. 分塊信息熵H(X).給定一個數據分塊X，分塊中分片的值域為{v1,v2,…,vn}，對應的每個取值出現的概率為{p(v1),p(v2),…,p(vn)}，則該分塊的信息熵為

(1)

其中,a表示為對數所使用的底，通常α=2，對應熵的單位為b.數據分塊中的各分片取值越均勻則其信息熵越大，當各分片取值出現的概率均相等時，該分塊的信息熵取得最大值;反之，當只有一種分片出現時其熵值最小為0.

定義4. 分片依賴p(x/y).用條件概率進行表示，其中x表示分塊A中屬性X的某一取值，y表示分塊B中屬性Y的某一取值，此時稱分塊A中X取值為x的分片以概率p(x/y)依賴于分塊B中Y取值為y的分片.

在實際應用中，分片依賴的概念是普遍存在的，譬如公司中員工工資水平與其職位的關系.假設某公司普通員工的工資水平一般為3 000～5 000元，部門經理的工資水平為5 000～8 000元，但5 000～8 000元工資段也有約15%的是業績突出的普通員工，而3 000～5 000元工資段也有5%的是業績較差的部門經理，此時若給定某一工資水平為6 500元，則我們可以以85%的概率推斷其為某一部門經理，即工資為6 500元的分片以85%的概率依賴于職位為“部門經理”的分片.此時，即使包含工資和職位屬性的2個分塊均已均衡，仍然可以以較大概率對分片進行關聯.

為了描述在不同分塊中的屬性存在依賴關系時的數據均衡程度，本文引入了塊間條件熵的概念.

定義5. 塊間條件熵H(Y/X).表示在已知隨機變量X值的前提下，隨機變量Y的信息熵還有多少，用來衡量在已知隨機變量X的條件下隨機變量Y的不確定性.表示為

(2)

通過式(2)可以證明，當Y的值完全由X確定時，H(Y/X)取得最小值0;反之，當且僅當X和Y為相互獨立變量時，H(Y/X)取最大值.

定義6. 臨時更新表U.該表設置在可信第三方，用來存儲租戶最近更新的數據，其形式為

(id,A1,A2,…,An,Time)，

其中,id為該記錄的全局唯一標識，在分塊時用來產生各分片的DSID;Time字段為一個時間戳，用來標識該條數據插入或修改的時間.

4.2 動態數據隱私保護的具體實現

文獻[1-2]中為防止租戶的隱私保護策略被攻擊者惡意獲取，提出使用可信第三方對隱私保護策略進行管理，并通過身份驗證機制阻止攻擊者的惡意請求.本文在可信第三方的基礎上增設了臨時數據管理模塊，主要負責對租戶最近更新的數據進行臨時存儲，并在生成水平分組后對水平分組進行垂直分塊并存至存儲層.通過可信第三方的身份認證機制防止臨時數據被惡意獲取，使臨時數據可以安全地以明文形式進行存儲，保證了租戶請求數據時的響應時間.

4.2.1 插入數據

設租戶Tenanti在時刻t1提交的原始插入請求為

INSERT INTOTVALUES(a1,a2,…,an).

根據第2節分析，若直接將數據寫入云端數據庫各分塊中，則各分塊將同時增加相同數目的記錄，攻擊者可以根據租戶操作行為推測出新增分片間的關聯關系，使租戶的這部分隱私面臨很大的泄露風險.因此本機制需要對原始插入請求進行如下轉換：

INSERT INTOUVALUES(id,a1,a2,…,an,t1)，

轉換過程將新插入的數據添加全局id和時間戳t1后插入臨時表U中臨時存儲，當表U中數據量大于設定閾值Nmax時，調用分組生成算法3對表U中數據進行水平分組，并以水平分組為單位對數據進行分塊和均衡，最后存入存儲層.由于對表U的操作發生在可信第三方，數據存儲到存儲層時雖然將分組信息暴露給了攻擊者，但分組內各分塊已進行均衡處理，因此整個分組和插入過程也是可靠的.

4.2.2 刪除數據

對于臨時更新表U中的數據，刪除操作發生在可信第三方，直接將對應數據刪除即可.而對應于存儲層各分塊中的數據，同時執行刪除操作會引起隱私泄露，因此在刪除數據時需要對部分分塊中的數據進行保留，為此首先引入以下概念.

定義7. 關鍵屬性(key attribute， KA).指隱私約束中敏感程度較高的屬性，由租戶在隱私保護需求中指定.例如不相容約束{Owner，Age，Zip，Disease}中，病人對于Disease屬性更為敏感，當病人身份信息被泄露時，仍希望其疾病信息能夠得到保護，因此保證包含Disease屬性分塊的安全更加重要.

定義8. 關鍵分塊(key chunk， KC).本文把包含有關鍵屬性的分塊稱為關鍵分塊.

定義9. 低權重分塊(lower weighted chunk, LWC).指在業務處理過程中，除關鍵分塊外，涉及頻率最低的分塊，該分塊中數據量的大小不會對業務處理效率產生太大影響.

定義10. 不相容分塊(mutually exclusive chunks, MEC).本文將同一不相容隱私約束所涉及的所有分塊稱為一組不相容分塊(如圖1中Chunk1，Chunk2，Chunk3即為一組不相容分塊)，當隱私需求中包含多個不相容約束時，則對應的分塊結果中會存在多組不相容分塊.

在進行刪除處理時，對于同一組不相容分塊，保留被刪數據在關鍵分塊和低權重分塊中的分片，此時攻擊者最多只能對同一條數據的部分分片進行重構，無法破壞隱私約束，保證了租戶隱私的安全.刪除算法的過程描述如下：

算法1. 數據刪除算法.

輸入：數據對象物理視圖DOPV、臨時更新表U、隱私分塊策略pps、刪除條件rc;

輸出：數據刪除操作執行結果.

① 從U中刪除符合rc的數據；

② 獲取除關鍵分塊和低權重分塊的所有分塊號，存入數組chunk；

③ 根據算法4獲取DOPV中符合條件rc的原始數據的全局標識resultSet；

④ for eachidinresultSetdo

fori=0 tochunk.length-1 do

計算id在chunk[i]中的DSID編號并刪除其在chunk[i]中對應的分片；

⑤ end for

⑥ end for

下面提出2個輔助定理證明在分組信息暴露的場景下，算法1在刪除操作時不會引起隱私泄露.

定理1. 對于一個不相容分塊組，保持某一分塊數據不變，在每次刪除數據時只刪除其余分塊中的數據，則數據刪除后各分塊的信息熵大于等于數據刪除前各分塊信息熵.

證明. 設某不相容分塊組包含C1和C2這2個分塊，在執行刪除請求時只刪除C2中的分片，由于分塊C1中的數據分布始終不變，所以分塊C1的信息熵也保持不變.對于分塊C2，設刪除分片前的數據分布為{p(v1),p(v2),…,p(vn)}，根據最大熵的含義，在已知部分知識的前提下，關于未知部分最合理的推斷就是符合已知知識的最隨機的推斷，因此我們總能找到一種數據填充方式使補充后數據分布為{p1(v1),p1(v2),…,p1(vn)}，并且有：

即攻擊者推測的分塊C2的當前熵值只能大于或等于其初始熵值，即在對分塊中數據分布無背景知識的前提下，攻擊者只能以C2分塊符合盡量均勻分布來對隱私進行猜測.

證畢.

定理2. 對于一個不相容分塊組，保持某一分塊數據不變，在每次刪除數據時只刪除其余分塊中的數據，則數據刪除后各分塊的條件熵大于等于數據刪除前各分塊條件熵.

證明. 設事件X和Y分別表示從分塊C1和C2中取值事件，在本文我們只關心給定X=xi猜測Y=yj需要的信息熵或者給定Y=yj猜測X=xi需要的信息熵，因此只需要證明H(Y/X=x)和H(X/Y=y)不減即可.由

可知X的取值不變，而給定x，y時P(x/y)是保持不變的，因此H(X/Y=y)保持初始大小.而對于H(Y/X=x)，則

當刪除分塊C2中的分片后可能導致Y的取值數目減少，但在無背景知識時，攻擊者只能認為Y可以取剩余取值之外的其他取值，即Y的取值數目只能大于或等于初始數目使得H(Y/X=x)大于或等于其初始值.

證畢.

由輔助定理1和定理2可知，當只刪除部分分片時，總能夠保持各分塊的熵值和分塊間的條件熵值是不減的，因此在刪除過程中不會因熵值的減少而泄露租戶隱私.

隨著SaaS應用的不斷運行，云端數據庫中可能會逐漸出現這樣的情況，即一個水平分組中的數據經過多次刪除和修改后只剩下極少量有效數據，為了保證刪除數據時租戶的隱私安全，需要完整保留關鍵分塊和低權重分塊的數據，同時還有數據均衡時的偽造數據，此時為了存儲這少量數據就需要付出比較大的存儲代價，而當這種水平分組的數量越來越多時，較大的偽造數據占比也會對查詢效率造成較大影響.

因此本文在設計算法時，增加了偽造數據回收機制，當一個水平分組中的剩余數據所占比例小于設定的下限值Tremain時，將剩余數據插入臨時更新表U中，并將該分組中的所有數據刪除，對表U中數據進行分組后重新進行存儲.算法過程描述如下：

算法2. 偽造數據回收.

輸入：分組信息表group_info、剩余數據占比閾值Tremain；

輸出：偽造數據回收操作執行結果.

① for eachgidingroup_infodo

② ifremain/tatal

③ 調用算法4獲取分組gid中剩余數據對應的全局id的集合resultSet；

④ for eachidinresultSet

⑤ 將id對應的原始數據插入U中；

⑥ end for

⑦ 調用算法1，將分組gid所有數據從存儲層中刪除；

⑧ end if

⑨ end for

4.2.3 修改數據

對于臨時更新表U中的數據，修改操作發生在可信第三方，直接修改對應數據即可.而對應于存儲層各分塊中的數據，由于同時對各分塊執行修改操作會引起隱私泄露，因此本文的處理方式是將修改后得到的數據直接插入臨時更新表U中進行存儲，并同時將原始數據從存儲層各分塊中刪除.在4.2.2節中證明了刪除算法1的刪除過程是安全的，而插入操作發生在可信第三方，因此整個修改過程是安全的.

4.2.4 分組生成及數據分塊

算法3. 分組生成和分塊算法.

輸入：臨時數據表U、最小組大小N、最小分塊熵H1和最小條件熵H2;

輸出：分組g.

① 創建空組g(g中元素為U中記錄的唯一標識)；

② 對表U中關鍵屬性的取值按其出現頻率從小到大進行排序；

③ whileg.length

按照步驟②中的排序結果，依次選取關鍵屬性取值，并將包含此取值的數據id取值加入g；

④ end while

⑤ 從表U的剩余數據中依次選取數據r，若將其加入g后對應各分塊的熵值都不小于H1，則將r.id加入g；

⑥ 調用分塊策略對g中數據進行分塊；

⑦ 根據H1和H2構造偽造數據對各分塊進行均衡；

⑧ 將各分塊數據存入存儲層；

⑨ returng.

算法3中，以關鍵屬性為基準進行分組，分組結果中首先保證關鍵分塊盡量均衡.行②首先將關鍵屬性依其出現頻率進行排序，行③一次選取出現頻率較小的關鍵屬性并將其對應的數據加入分組中，這樣可以使分組中關鍵屬性有較多的取值，分布更加均勻.行④采用貪心思想，從剩余分塊中依次選取數據進行嘗試，將其加入g時能使各分塊的熵值不小于H1，則接受其加入g；行⑤～⑦在產生分組g后，調用分塊策略對分組進行分塊，并采用文獻[1]的均衡方法對各分塊進行均衡處理.

4.2.5 隱私數據重構

隱私數據經過分塊混淆后，其數據可用性也隨之喪失，而在SaaS應用中租戶需要頻繁對原始數據進行訪問、刪除和修改等.因此，如何對隱私數據進行快速重構成為SaaS應用隱私保護的一大關鍵問題.

對隱私數據進行分塊時，會根據原始數據的全局id為每個分片生成1個唯一的分片標識DSID，該標識主要用于對原始數據進行重構并對偽造數據進行過濾.算法4為基于可信第三方的原始數據重構算法，輸入為數據對象物理視圖DOPV、租戶隱私分塊策略pps和重構條件rc，輸出為滿足條件的原始記錄的全局id.算法4首行先根據分塊策略將重構條件rc劃分為rc={rc1,rc2,…,rci,…,rck}，其中k為分塊數，rci為分塊Chunki上的重構條件；行②在每個分塊Chunki上查詢符合條件rci的DSID并將其轉換為全局id后放入集合idSeti中，行⑤對所有idSet求交集，得到最終符合重構條件rc的原始數據全局id集合resultSet；行⑥將resultSet中偽造數據對應的全局id進行過濾；行⑦將rc和resultSet緩存到cache中，提高下次相同重構請求的執行效率.算法描述如下：

算法4. 隱私數據重構算法.

輸入：數據對象物理視圖DOPV、隱私分塊策略pps、重構條件rc;

輸出：原始數據全局id集合resultSet.

① 根據pps劃分重構條件rc；

② fori=1 tokdo

③ 查詢分塊Chunki上符合rci的DSID，將其對應的全局id放入集合idSeti;

④ end for

⑥ 過濾resultSet中偽造數據對應的全局id；

⑦ 將rc和resultSet存入cache；

⑧ returnresultSet.

算法4中，在各分塊中查詢符合條件的DSID采取并行執行方式，查詢時間與數據量大小成正比關系.設所有N為idSet長度的最大值，若采用二路歸并求交，則其時間復雜度為O(N2lbk).一般情況下，符合條件的N取值都不是很大，因此該時間復雜度在可接受范圍內.

5 實驗評估

5.1 實驗環境

為進行實驗，作者采用從本實驗室云計算平臺申請的虛擬機作為可信第三方，其配置為8核、16 GB內存和500 GB硬盤.用MongoDB3.0.0存儲租戶隱私保護策略，用Mysql5.6.22存儲臨時更新表數據.

用1臺浪潮刀片服務器模擬部署多租戶應用，配置為12核CPU(主頻3.10 GHz)、32 GB內存、2TB硬盤.存儲層同樣使用Mysql5.6.22做存儲數據庫，多租戶應用使用Java1.8編寫程序進行模擬.

數據集取自本實驗室社保項目內部測試數據集的參保人醫療登記基本信息表中的數據，數據量大小為300萬條左右.數據選取了姓氏(已模糊處理)、醫療人員類別、性別、年齡、信任等級、孤寡類別、單位組織、醫療賬戶以及其他屬性等共20個屬性進行實驗.不相容隱私約束為姓氏、性別、年齡、單位組織.

Fig. 3 The change of business operation with the increasing of data volume.圖3 業務操作隨數據量增加的變化

5.2 業務處理開銷實驗

圖3為在本文提出的動態數據隱私保護機制下，增刪改3種不同操作在不同數據量下的操作處理時間，橫軸為數據量大小，縱軸為響應時間.

從圖3可以看出，由于新插入數據總是被存儲到臨時表中，而表U中只存儲少量數據并且數據量基本保持穩定，所以插入數據的處理速度很快，只有幾十毫秒左右.而對于刪除和修改操作，由于需要首先對被更新的數據進行重構，導致其處理時間大大增加，并且隨著數據量的增大而線性增加.

圖4將本文提出的方法與其他3種方法在業務處理效率方面進行了對比.方法A為不進行隱私保護，本文提出動態隱私保護機制，采用文獻[1]中的分塊策略，方法B為文獻[1]提出的隱私保護機制，方法C為文獻[3]對數據屬性進行聚類后的隱私保護方法.數據量大小為200萬條左右，查詢、插入和修改這3類業務操作中每類操作涉及的屬性數又分為2，4，6，8，10這5個級別，實驗結果采用所有級別處理時間的平均值.

Fig. 4 The business operation costs of different methods.圖4 不同方法下業務操作開銷

從圖4可以看出，不進行隱私保護時處理速度最快，而本文方法和方法B雖然查詢、刪除和修改都受制于數據量大小，但由于在相同數據量時，本文提出的隱私保護方法中偽造數據相對減少，所以總體上本文方法比文獻[1]的方法B在性能上還是有所提升;方法C由于對數據屬性按業務操作進行了聚類，所以處理效率要比方法B要高，但受偽造數據的影響，還是要比本文方法效率差一些.

5.3 偽造數據占比實驗

圖5對比了在分塊最小信息熵取3時，本文方法、方法B、方法C中偽造數據占比隨時間的變化.從圖5可以看出，當使用方法B、方法C時，偽造數據占比會隨著應用的運行逐漸增加，并且開始階段提升的幅度比較大.其原因在于在較短時間內數據集中姓氏和年齡的分布并不完全與總體分布一致，數據分布比較不均勻，當數據量隨時間逐漸增加時，其分布越接近于總體分布，但是隨著對數據操作次數的不斷增加，需要增加更多偽造數據進行均衡.而本文方法中由于分組時盡量選取使分組數據分布均勻的數據組成分組，輔以偽造數據回收模塊對偽造數據的回收處理，使整個過程中偽造數據占比都比較穩定.

Fig. 5 The change of bogus data ratio over time.圖5 偽造數據占比隨時間的變化

圖6對比了偽造數據占比隨分組大小產生的變化.當分組較小時，由于分組取值個數相對較少，導致分組內數據分布不均勻，要進行均衡需要添加較多偽造數據；隨著分組大小的逐漸增大，分片取值個數逐漸增加，分塊分布逐漸均勻；而當分組大小繼續增加時，分組內數據分布逐漸接近整體分布，由于總體分布中姓氏和年齡并不是服從均勻分布的，所以分組再次趨向于不均勻狀態，導致偽造數據占比又重新升高.

Fig. 6 The change of bogus data ratio with the size of group.圖6 偽造數據占比隨分組大小的變化

從以上2個實驗對比可以看出，相對文獻[1]中的方法B，本文提出的隱私保護機制具有更高的操作效率，而且隨著應用的不斷運行，其偽造數據占比更低且始終保持穩定.

6 總結與未來工作

對于SaaS應用而言，現有的隱私保護機制缺乏對租戶業務操作的有效支持，難以保證數據動態變化過程中租戶隱私信息的安全.本文針對SaaS模式下由租戶業務操作引起的隱私泄露問題以及偽造數據占比較高的不足，提出了基于分塊混淆的動態數據隱私保護機制.該機制將租戶最新插入和修改的數據在可信第三方進行緩存，當具備分塊條件時再將數據以分組為單位分塊均衡后存入存儲層；對于刪除操作，保留關鍵分塊和低權重分塊中的數據不被刪除，防止攻擊者通過數據操作行為對租戶隱私進行重構；最后提出偽造數據回收機制對存儲層冗余的偽造數據進行回收，降低偽造數據占總數據量的比例.實驗結果證明，本文所提出的動態數據隱私保護機制，在保證租戶隱私的同時，對應用的性能也起到了很好的優化效果.下一步工作將主要研究數據動態變化過程中，不同的租戶數據放置策略對應用性能的影響.

[1]Zhang Kun, Li Qingzhong, Shi Yuliang. Research on data combination privacy preservation mechanism for SaaS[J]. Chinese Journal of Computers, 2010, 33(11): 2044-2054 (in Chinese)

(張坤, 李慶忠, 史玉良. 面向SaaS應用的數據組合隱私保護機制研究[J]. 計算機學報, 2010, 33(11): 2044-2054)

[2]Shi Yuliang, Jiang Zhen, Zhang Kun. Policy-based customized privacy preserving mechanism for SaaS applications[G] //LNCS 7861: Proc of the 8th Int Conf on Grid and Pervasive Computing. Berlin: Springer, 2013: 491-500

[3]Shao Yali, Shi Yuliang, Li Hui. A novel cloud data fragmentation cluster-based privacy preserving mechanism[J]. International Journal of Grid & Distributed Computing, 2014, 7(4): 21-32

[4]Liu Qin, Wang Guojun, Wu Jie. An efficient privacy preserving keyword search scheme in cloud computing[C] //Proc of the 12th IEEE Int Conf on Computational Science and Engineering. Piscataway, NJ: IEEE, 2009: 715-720

[5]Gentry C. Fully homomorphic encryption using ideal lattices[C] //Proc of the 41st ACM Symp on Theory of Computing. New York: ACM, 2009: 169-178

[6]Wong R C W, Li J, Fu A W C, et al. (α,k)-anonymity: An enhancedk-anonymity model for privacy-preserving data publishing[C] //Proc of the ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 754-759

[7]Machanavajjhala A, Gehrke J, Kifer D.l-diversity: Privacy beyondk-anonymity[C] //Proc of the 22nd Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2006: 24-35

[8]Ciriani V, Di Vimercati S D C, Foresti S, et al. Fragmentation an encryption to enforce privacy in data storage[G] //LNCS 4734: Proc of the 12th European Symp on Research in Computer Security. Berlin: Springer, 2007: 171-186

[9]Ouyang Jia, Yin Jian, Liu Shaopeng, et al. An effective differential privacy transaction data publication strategy[J]. Journal of Computer Research and Development, 2014, 51(10): 2195-2205 (in Chinese)

(歐陽佳, 印鑒, 劉少鵬, 等. 一種有效的差分隱私事務數據發布策略[J]. 計算機研究與發展, 2014, 51(10): 2195-2205)

[10]Byun J W, Sohn Y, Bertino E, et al. Secure anonymization for incremental datasets[G] //LNCS 4165: Proc of SDM 2006. Berlin: Springer, 2006: 48-63

[11]Pei Jian, Xu Jian, Wang Zhibin, et al. Maintainingk-anonymity against incremental updates[C] //Proc of the 19th Int Conf on Scientific and Statistical Database Management. Piscataway, NJ: IEEE, 2007: 5-14

[12]Byun J W, Li T, Bertino E, et al. Privacy-preserving incremental data dissemination[J]. Journal of Computer Security, 2009, 17(1): 43-68

[13]Xiao Xiaokui, Tao Yufei.m-invariance: Towards privacy preserving re-publication of dynamic datasets[C] //Proc of the 2007 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2007: 689-700

[14]He Y, Barman S, Naughton J F. Preventing equivalence attacks in updated, anonymized data[C] //Proc of the 27th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2011: 529-540

[15]Nergiz A E, Clifton C, Malluhi Q M. Updating outsourced anatomized private databases[C] //Proc of the 16th Int Conf on Extending Database Technology. New York: ACM, 2013: 179-190

Zhang Honglei, born in 1987. Master from the School of Computer Science and Technology, Shandong University. His main research interests include cloud computing, privacy preserving.

Shi Yuliang, born in 1978. PhD and associate professor in the School of Computer Science and Technology, Shandong University. Member of China Computer Federation. His main research interests include service computing, cloud computing and database.

Zhang Shidong, born in 1969. PhD and professor in the School of Computer Science and Technology, Shandong University. His main research interests include database, Web data integration and cloud computing (zsd@sdu.edu.cn).

Zhou Zhongmin, born in 1989. Master from the School of Computer Science and Technology, Shandong University. His main research interests include cloud computing, privacy preserving (zhoumin_12@163.com).

Cui Lizhen, born in 1976. Professor in the School of Computer Science and Technology, Shandong University. Senior member of China Computer Federation. His main research interests include cloud data management and workflow management (clz@sdu.edu.cn).

A Privacy Protection Mechanism for Dynamic Data Based on Partition-Confusion

Zhang Honglei, Shi Yuliang, Zhang Shidong, Zhou Zhongmin, and Cui Lizhen

(SchoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

Under the cloud computing environment, the privacy protection in the plaintext state can be realized, by the partition-confusion-based privacy protection mechanism which effectively combines tenants’ personalized privacy protection requirements and application performance. However, as the multi-tenant applications continue to run, on the one hand, the insertion, deletion, modification and other business operations of the tenant data can affect the distribution of the underlying data storage, making the relationships between the chunks in a significant risk of leakage due to the uneven data distribution; on the other hand, the attacker can still analyze a part of private information by the operation log of every chunk and the snapshot of the corresponding data in the local time. In response to these challenges, the present paper proposes a dynamic data privacy protection mechanism for partition confusion on the basis of the tripartite security interaction model. This mechanism can cache the data newly inserted and modified by a trusted third party and then group and upload it under the proper conditions; retaining key fragmentation in the deletion operation can ensure the privacy of the deleted and remained data; the falsifying data collection mechanism can achieve lower consumption of resources storage and optimize the application performance. The experimental result proves that the dynamic data privacy protection mechanism proposed in this paper has better feasibility and practicality.

multi-tenancy; partition confusion; dynamic data; privacy protection; trusted third party

2015-06-16；

2015-09-07

國家自然科學基金項目(61272241,61572295)；科技部創新方法工作專項(2015IM010200)；山東省泰山產業領軍人才工程專項經費；山東省科技重大專項(2015ZDXX0201B03,2015ZDXX0201A04,2015ZDJQ01002)

史玉良(shiyuliang@sdu.edu.cn)

TP309.2

The research work was supported by the National Natural Science Foundation of China (61272241, 61572295), the Innovation Methods Work Special Project (2015IM010200), the Taishan Industrial Experts Programme of Shandong Province, and the Shandong Province Science and Technology Major Special Project (2015ZDXX0201B03, 2015ZDXX0201A04, 2015ZDJQ01002).