一種基于差分隱私保護的skyline 查詢方法

張麗平 ，楊 玉 ，金飛虎 ，李 松 ，郝忠孝 ,2

（1. 哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080；2. 哈爾濱工業大學計算機科學與技術學院，黑龍江 哈爾濱 150001）

Skyline 查詢是解決計算機多目標優化問題的一類重要方法，由Borzony 等[1]提出，目前在位置導航、數據挖掘和推薦算法中具有越來越廣泛的應用[2-5]. 盡管skyline 查詢機制從理論上講能夠保證隱私，但在實踐中，攻擊者通過重復攻擊仍然可以獲得個人信息[6]. 因此，需要進一步研究該機制中防止重復攻擊的問題. skyline 查詢的結果為沒有被其他任何點支配的對象，也正是因為這一特性，用戶的隱私容易泄露[7]. 為進行數據的隱私保護，Dwork[8]提出了一種基于差分隱私保護的方法，通過對數據進行一般的統計分析，為隱私保護提供定量的評估技術，從而實現差分隱私保護的功能. 文獻[9]提出了一種操作方便、定量準確的方法，可以在執行獨立的差異私有機制的過程中跟蹤累積的隱私損失. 文獻[10]提出了一種基于環境中整體跡線和已發布跡線之間相互聯系的方法，該方法可以在給定查詢約束的情況下將跡線隱私泄漏的幾率最小化. 文獻[11]提出了一種設置線性查詢數量上限的方法，該方法能夠找到最優的線性查詢. 基于差分隱私的查詢機制有兩種，分別是拉普拉斯機制[12]和指數機制[13]，基于差分隱私的數據挖掘方法廣泛應用于頻繁模式挖掘[14]、MapReduce 大數據分析查詢[15]、智能權重截取算法[16]和智能電網[17].

為了解決差分隱私保護機制中重復攻擊會泄露用戶隱私的問題，國內外研究人員提出了許多解決方法. 文獻[18]為解決二維多媒體數據不均勻和精度降低的問題，提出了一種基于標準偏差圓半徑的差分隱私噪聲動態分配算法. 文獻[19]使用傳統搜索未涵蓋的屬性關聯來調查新的隱私威脅，通過配置差異隱私的噪聲參數來減輕周期滑動推理攻擊對差分隱私的影響. 文獻[20]通過對樣本數據進行訓練，獲得一個對抗性網絡數據模型，將噪聲數據添加到真實數據集中，可以在高斯分布下實現不同等級的隱私保護. 文獻[21]提出了一種用于位置數據隱私的隱私保護方法，該方法可滿足不同的隱私約束. 但是，目前這些方法都無法滿足skyline 查詢中隱私保護的要求，并且無法動態設定隱私預算值以實現不同等級的隱私保護級別. 文獻[22]提出了一種設定查詢上限的高效方法，通過計算準確性的期望值與可用于補償個人的預算值之間的平均值來確定計算查詢上限. 文獻[23]提出了一種基于環境中整體跡線和已發布跡線之間的相互聯系的方法，通過計算整體位置跡線的隱私度量值來確定接下來最優的位置跡線方案，該方法可以在給定查詢約束的情況下將跡線隱私泄漏幾率最小化. 文獻[24]提出了一種設置線性查詢數量上限的方法，通過找到最優的線性查詢，設置查詢數量的上限，使得最優的線性查詢也無法泄露過多的隱私. 但是仍然無法在分級查詢中動態改變隱私預算值的同時對查詢次數的上限進行調整.因此，文獻[25]提出了一種有效且可保護隱私的在線醫療基礎診斷框架，在該框架內通過skyline 查詢，用戶可以準確訪問在線醫療診斷服務，而無需泄露他們的醫療數據.

綜上所述，針對傳統skyline 查詢方法無法有效地解決用戶隱私泄露的問題，提出了一種基于差分隱私保護的skyline 查詢方法. 本文的主要貢獻包括3 個方面：

1） 為提高skyline 查詢的效率，提出最優主導頁的概念. 最優主導頁能夠針對skyline 查詢結果的分頁特性，確定查詢范圍的數據隱私保護等級. 針對skyline 查詢的特性提出頁敏感度的概念，頁敏感度能夠滿足ε-差分隱私.

2） 為解決因噪音導致有效查詢結果的范圍無法量化的問題，引進置信區間和置信率的概念；為解決不同信任等級的用戶查詢結果相同會泄露數據隱私的問題，提出一種基于置信率的隱私預算值調節方法，對不同的信任等級的用戶設定不同的隱私預算值，實現數據的分級保護.

3） 為解決攻擊次數過多導致用戶隱私泄露的問題，提出調整隱私預算和置信率，限制查詢次數的策略，從而保護隱私數據.

1 基本定義

定義1全局敏感度[12]. 設有函數f：T→Rd，T為輸入數據集，輸出為d維實數向量. 對于T的任意鄰近數據集Ta，函數f的全局敏感度GSf= max{T,Ta} ||f(T) -f(Ta) ||1，其中，||f(T) -f(Ta) ||1是f(T) 和f(Ta) 之間的1-階范數距離，表示相差的個數，這里個數只能為1，若 ||f(T)-f(Ta) ||1=1，表示相差一個.

函數的全局敏感度由函數本身決定，不同的函數會有不同的全局敏感度. 一些函數具有較小的全局敏感度，因此，只需加入少量噪聲即可掩蓋因一個記錄被刪除對查詢結果所產生的影響，從而實現差分隱私保護. 但是仍然無法滿足某些需求，例如求平均值和中位數等函數，則具有較大的全局敏感度. 此時，敏感度可能是一個很大的值，無法滿足隱私保護的要求. 為解決該問題，進一步提出了頁敏感度的概念.

定義2頁敏感度. 設有函數f：T→Rd，T為一個輸入數據集，輸出為d維實數向量，對于輸入數據集T和任意的鄰近數據集Ta，LSf(T) = max{Ta}×||f(T) -f(Ta) ||1，稱為函數f在數據集T上的頁敏感度.

為進一步調節頁敏感度，合理設置隱私預算的值，引入了基于差異化拉普拉斯分布的置信區間和置信率的概念. 置信區間和置信率與隱私預算有關，隱私預算的大小決定隱私保護的效果，如果所添加的噪聲是有效的，則一次查詢無法獲得用戶的隱私.但是，如果攻擊者進行多次重復攻擊，并且噪聲分布符合拉普拉斯分布，實際結果就會在某一個區間. 為進一步量化該區間范圍，給出置信區間的定義如定義3 所示.

定義3置信區間. 符合拉普拉斯分布的噪聲在某一個區間范圍內，如果用 φ 代表置信區間的一半長度，則 [ -φ,φ] 為置信區間[24].

由拉普拉斯分布知置信區間是對稱的，則可以推斷出被攻擊數據的私有數據，并且可以通過累計函數計算攻擊的成功率A(T)，實際結果為

式中：ε為隱私預算值； Δf為全局敏感度； L(·) 為拉普拉斯變換.

L(ε/Δf) 的置信區間為[ μ-φ, μ+φ] ，其中，μ為位置參數，是相對于參數 φ 對稱的未知參數. 為量化計算結果在置信區間的概率，進一步給出了置信率的概念，如定義4 所示.

定義4置信率.f(T)的查詢結果落在置信區間[μ-φ, μ+φ]的概率為置信率，則置信率通過累計函數計算為[24]

根據置信率進一步量化隱私預算值ε的上界，設p為隱私泄露的概率，則

隱私預算值上界可以限制隱私預算值的大小，并且與置信率相關. 查詢結果有兩種可能性，分別是查詢結果落在置信區間和查詢結果不落在置信區間，兩種結果互斥. 設攻擊者進行查詢的總次數為C，在置信區間內的查詢結果次數為m，m為大于0 的整數，則攻擊成功的概率為

因此，若對攻擊者的成功率進行限制，使其不大于某個閾值，則能夠確定隱私預算的取值范圍. 隱私預算ε的選擇與查詢的頁敏感度LSf(T)、攻擊者的總查詢次數C、置信區間 [ -φ, φ] 和攻擊成功率pc有關，隱私預算取值范圍的計算如式（5）所示.

理想的情況下，成功的事件和不成功的事件互斥，ε的值接近1/2 時，則成功率近似為50%. 假設置信區間為 [ 1/2-ω,1/2+ω] ，其中，ω為用戶設定的成功率參數，取決于數據的隱私性和能夠承受攻擊的上限. 當查詢結果在置信區間的成功率大于1/2 時，可對頁敏感度進行調整，即降低頁敏感度，增加隱私保護等級，因此，置信區間成功率可以控制在用戶設定的 [ 1/2-ω,1/2+ω] 區間內.

最后，為對skyline 的查詢結果進行優化，給出最優主導頁的概念如定義5 所示.

定義5最優主導頁. 根據支配頁將skyline 查詢的輸入數據集T分為h個子數據集Tsub1,Tsub2, … ,Tsubh，在一次具體查詢中，如果查詢數據集為部分子數據集Tsubk,Tsubk+1, … ,Tsubk+z，其中k和z為正整數且0 ＜k+z≤h，則該查詢的最優主導頁為Tsubk.

2 基于差分隱私保護的skyline 查詢方法

skyline 查詢結果通常是隱私數據，故用戶的隱私更容易泄露. 為保護用戶隱私，提出了基于差分隱私保護的skyline 查詢方法，所提方法的主要思想為：根據查詢對象的范圍確定查詢的最優主導頁，從而確定頁敏感度；根據查詢者的查詢范圍、查詢次數評估查詢者的信任等級，限制查詢次數；根據頁敏感度和信任等級進一步確定隱私預算，給出查詢結果.

2.1 最優主導頁的計算方法

最優主導頁是指在一次skyline 查詢范圍中，隱私最容易被泄露的某一頁查詢結果. 最優主導頁的計算過程為：首先，通過skyline 查詢獲得查詢結果，將隱私最容易被泄露的某一頁查詢結果確定為最優主導頁；其次，遍歷數據集并實時更新查詢結果；后續依據查詢范圍的改變再動態更新最優主導頁. 如圖1 所示，圖中，Pt、Oy分別為第t頁、第y個對象.

圖1 skyline 分頁查詢示例Fig. 1 skyline paged query

首先，利用skyline 分頁查詢對所有的數據點進行分頁，查到每一頁所有不被支配的數據點，每一頁為一個隱私泄露等級的子數據集.

第一頁的第一個對象記為(P1,O1)，第一頁的對象子數據集為{(P1,O1), (P1,O2), (P1,O3), (P1,O4),(P1,O5)}，以此類推，每一頁查詢結果如表1 所示.

表1 skyline 分頁查詢結果Tab. 1 Skyline paged query results

根據所有對象的屬性向量計算第i（i= 1, 2, …）頁skyline 查詢結果，第1 頁為首次查詢確定的最優主導頁，每一次查詢的最優主導頁都代表最容易泄露當前數據隱私的子數據集.

2.2 頁敏感度的計算方法

在skyline 查詢過程中，局部敏感度計算的過程比較復雜，全局敏感度無法對子集進行分類保護；查詢次數和查詢結果的隱私泄露程度具有正相關性，頁敏感度能夠調節兩者相關性的大小.

基于差分隱私保護的查詢通過添加噪音干擾查詢結果，從而保護用戶隱私. 查詢機制有兩種，分別是拉普拉斯機制和指數機制，其中拉普拉斯機制是一種噪音干擾機制，噪音是一種滿足拉普拉斯分布（Laplace distribution）的函數. 基于拉普拉斯機制的skyline 查詢的頁敏感度為LSf(T)時，滿足ε-差分隱私.

基于以上論述，所提計算頁敏感度算法 （page sensitivity calculation algorithm，PSC_A）的主要思想為：首先，在預處理階段通過skyline 查詢結果初步確定第一次查詢的最優主導頁，并計算頁敏感度；其次，在每次查詢時遍歷數據集，將當前計算的頁數與最優主導頁進行比較，更新最優主導頁，最終，輸出頁敏感度的值. PSC_A 如算法1 所示.

算法1PSC_A /*頁敏感度計算算法*/

輸入：數據集T.

輸出：頁敏感度LSf(T).

1） 執行skyline 查詢，通過skyline 查詢結果初步確定第一次查詢的最優主導頁；

2） 對skyline 查詢數據集T進行遍歷，計算每一個對象的頁數；

3） 將當前計算的頁數與最優主導頁進行比較；

4） 如果當前數據對象的頁數小于最優主導頁，則更新最優主導頁；

5） 計算當前最優主導頁的頁敏感度LSf(T)；

6） 返回頁敏感度LSf(T).

2.3 基于置信率的隱私預算值調節方法

針對不同的隱私泄露等級的子數據集，為了差異性地保護隱私，利用基于拉普拉斯分布的差分隱私保護機制保護數據隱私. 傳統的隱私保護方法可以通過引入隨機性增加干擾，達到對隱私的有效保護. 設x為查詢參數變量，Nnoise是服從某種隨機分布的噪聲，則f(x) ＝Ccount(x) +Nnoise，其中，Ccount(x)為針對x的統計函數. 在傳統的差分隱私保護方法中，無法對輸出的結果進行特定的處理，針對skyline 分頁查詢結果集中的數據隱私保護等級不同的問題，為進一步對不同隱私等級的數據進行分級調節，提出基于置信率的隱私預算值調節方法.

利用拉普拉斯機制執行ε-差分隱私保護，將滿足拉普拉斯分布的隨機噪聲添加到查詢結果中，拉普拉斯機制滿足

拉普拉斯噪聲計算公式為

式中：b＞ 0 為尺度參數.

設b=ε/ Δf， μ = 0，則

對于任意絕對值變量，累計函數為

添加的噪聲大小與隱私預算值ε和 Δf密切相關，ε的取值越小，隱私保護效果越好，但是數據的有效性越低；ε的取值越大，數據的隱私保護則效果越差，但是數據的有效性越高. 基于以上論述分析，所提出的基于置信率的隱私預算值調節算法（privacy budget adjustment algorithm for confidence rate，PBAACR_A）如算法2 所示.

算法2PBAACR_A /*隱私預算值調節算法*/

輸入：查詢數據集T, 置信區間[1/2-ω,1/2+ω]，查詢次數C.

輸出：隱私預算值.

1） 調用PSC_A 算法計算頁敏感度；

2） 針對置信區間 [ 1/2-ω,1/2+ω] ，利用頁敏感度和式（2）計算置信率；

3） 利用式（3）計算隱私預算值；

4） 基于拉普拉斯機制執行ε-差分隱私，利用拉普拉斯噪聲計算公式（式（7））將滿足拉普拉斯分布的隨機噪聲添加到查詢結果中；

5） 對置信區間 [ 1/2-ω,1/2+ω] 的隱私預算值進行判斷，如果滿足該置信區間的置信率要求，則輸出隱私預算值；否則，隱私預算值設置為0.

2.4 基于差分隱私保護的skyline 查詢算法

基于頁敏感度計算和隱私預算值調節方法，針對skyline 查詢的次數過多導致用戶隱私可能泄露的情況，可采取限制用戶查詢次數的策略加大隱私保護力度. 在置信區間為 [ 1/2-ω,1/2+ω] 的情況下可根據隱私預算值和全局敏感度計算出置信率. 查詢結果滿足ε-差分隱私的查詢次數上限設為c，當查詢次數達到c時，需要對用戶信任等級和隱私參數重新計算，再利用PBAACR_A算法對隱私預算值進行調節，最終得到滿足隱私保護要求的skyline查詢結果.

進一步給出基于差分隱私保護的skyline 查詢算法（skyline query algorithm for differential privacy protection，SQADP_A ），該算法首先計算隱私預算值；其次，基于隱私預算值更新查詢次數上限；對每次查詢結果進行判斷；查詢完成后再計算頁敏感度；最后，利用拉普拉斯機制添加噪音，輸出skyline 查詢結果. SQADP_A 如算法3 所示.

算法3SQADP_A /*基于差分隱私保護的skyline 查詢算法*/

輸入：查詢數據集T，置信區間 [ 1/2-ω,1/2+ω] ，查詢總次數C，滿足ε-差分隱私的查詢次數最大值c.

輸出：skyline 查詢結果.

1） 調用PBAACR_A 算法得出隱私預算值；

2） 判斷隱私預算值，若隱私預算值為0，則更新查詢次數上限，重新計算隱私預算值；若隱私預算值不為0，則增加查詢次數；

3） 基于置信區間 [ 1/2-ω,1/2+ω] 計算置信率；

4） 遍歷查詢數據集T中的所有子數據集；

5） 針對相鄰子數據集進行skyline 查詢，得到查詢結果集；

6） 計算頁敏感度；

7） 利用拉普拉斯機制，根據隱私預算值和頁敏感度對查詢結果集添加噪音；

8） 發布skyline 查詢結果.

3 實驗評估

3.1 實驗環境

為更好地保護隱私，本實驗加入人工合成的人名、性別和年齡等信息. 人名為隨機生成的3 個漢字，性別為男或者女，年齡為0 ～ 100 周歲的整數，符合正態分布. 實驗環境為Microsoft Windows 10，Core (TM) i7- 3537U CPU@ 2.00 GHz （2 501 MHz）處理器，4 GB 內存. 假設人名、性別和年齡均為隱私數據，本實驗分析skyline 查詢的效率、查詢結果的可靠性以及查詢結果的隱私泄露程度.

為構造對比算法，對文獻[20]所提算法和文獻[21]所提算法的關鍵步驟進行適當的修改. 在文獻[20]所提算法進行剪枝之前增加了最優主導頁的計算，并將敏感度更改為頁敏感度，簡稱為OGWP （optimizing GAN obfuscator with pruning）算法；在文獻[21]所提算法進行信息熵的計算之前增加最優主導頁的計算，并將敏感度的計算更改為動態調節敏感度，簡稱為FOQIL （find the optimal quantization interval length）算法. 本節將本文所提SQADP_A 算法與OGWP 算法、FOQIL 算法進行對比實驗，驗證所提算法的可行性和有效性.

3.2 實驗結果分析

實驗1本實驗主要對比3 種算法的數據規模對算法執行時間的影響. 圖2 展示了數據集對象數量從64 kB 增長到1 024 kB 時3 種算法的查詢效率對比結果，分別分析數據規模的不同對CPU 運行時間的影響. 由于剪枝算法能夠剪掉一部分無效對象，且最優主導頁是動態更新的，所以3 種算法在數據規模較小的時候相差不大，但是隨著數據規模的增加，FOQIL 算法需要額外處理的數據量較多，因此，對很多無效的對象進行最優主導頁和信息熵的計算量也增加，查詢效率相對較低. 梯度修剪策略由于沒有涉及到大量的復雜計算，而是基于高斯分布針對不同場景進行差異化剪枝，因此，OGWP 算法效率較高.

圖2 數據規模對查詢效率的影響Fig. 2 Effect of data size on query efficiency

實驗2本實驗主要評估數據規模對查詢結果可靠性的影響. SQADP_A 算法依據剪枝規則和存在概率排序規則進行查詢. 實驗中數據項泄露數為結果集中隱私數據數量，因變量為數據集的規模，在5 個不同規模的數據集上進行查詢. 如圖3 所示，因為每次skyline 查詢的結果輸出后，才作為計算頁敏感度的剪枝結果，所以SQADP_A 算法的輸出結果集的無效數據最少. 與SQADP_A 算法相比，FOQIL 算法的查詢結果隱私項較少，隱私保護等級較高，但是由于涉及到大量的計算，查詢效率較低.OGWP 算法輸出結果的隱私數據數量高于FOQIL算法和SQADP_A 算法，隱私保護效果最差. 因此，由實驗結果可知：如果不考慮查詢時間的影響，FOQIL 算法和SQADP_A 算法更能保護用戶隱私.此外，雖然FOQIL 算法和SQADP_A 算法的隱私保護等級相差不大，但是，SQADP_A 算法的查詢速度更快. 因此，隨著數據規模的增加，SQADP_A 算法能在查詢速度較快的情況下增強查詢結果的隱私保護.

圖3 數據規模對查詢結果可靠性的影響Fig. 3 Effect of data size on the reliability of query results

實驗3本實驗評估了隱私預算值調節策略和梯度修剪策略對算法輸出結果集的隱私泄露程度的影響. 實驗中采用控制變量法保證隱私預算值計算的策略不同，結果如 圖4 所示. 由圖4 可知：兩種查詢算法在skyline查詢過程中采用不同的策略，其查詢結果集中的有效的隱私泄露數具有顯著差異；隱私預算值調節策略更適應于對skyline 查詢隱私保護要求較高的場所，skyline 查詢的查詢結果為沒有被其他任何點支配的對象，關于skyline 查詢的查詢結果通常是隱私數據，因此，這種方式可以用較小的時間代價換取隱私保護等級的增加；而梯度修剪策略雖然具有較快的查詢速度，但是隱私泄露程度隨著數據規模的增加而快速增加. 故如果對skyline查詢結果的隱私保護有較高要求則可以采用隱私預算值調節策略，對查詢速度有較高要求則可以采用梯度修剪策略.

圖4 兩種策略對查詢結果隱私泄露程度的影響Fig. 4 Effect of two strategies on the degree of privacy disclosure of query results

實驗4本實驗評估了3 種算法中的隱私預算值設定對skyline 查詢結果集中隱私泄露程度的影響，數據規模為256 kB，隱私預算值分別設為10.0、5.0、0.8、0.5、0.4，實驗結果如圖5 所示. 由實驗結果可知：隱私預算值設定較低的情況下3 種算法的隱私泄露程度沒有明顯的區別，3 種算法在隱私預算設定為0.4 時的隱私泄露的差距較小，但是隨著隱私預算值設定值的增加，SQADP_A 算法的隱私泄露程度逐漸收斂，并且在隱私預算值較小（小于5.0）的情況下，SQADP_A 算法的隱私保護效果最好. 隱私預算設定值為10.0 時，OGWP 算法的隱私泄露程度較高，隨著隱私預算值的增加，FOQIL 算法的隱私保護效果有降低的趨勢.

圖5 隱私預算值對隱私泄露程度的影響Fig. 5 Effect of privacy budget value on privacy disclosure

實驗5本實驗評估了3 種算法中的隱私預算值設定對skyline 查詢結果集中準確率的影響，實驗結果如圖6 所示. 由圖6 可知：隱私預算值設定較低的情況下，OGWP 算法的查詢準確率最低；隨著隱私預算值的增加，OGWP 算法的隱私保護效果變差，OGWP 算法的查詢準確率卻有所提高. 在隱私預算值設定較低的情況下，SQADP_A 算法的查詢準確率最高，當隱私預算設定為0.8 以內時其查詢準確率沒有明顯的變化，當隱私預算值設定大于0.8 時，查詢準確率有明顯變高的趨勢. FOQIL 算法在隱私預算設定較低的時候也有較高的準確率，隱私預算值設定為0.8 以內時，準確率變化依舊不明顯，甚至有降低的趨勢；當隱私預算的值大于0.8 后準確率逐漸增加. 由實驗可知：在skyline 查詢結果中，SQADP_A 算法的準確率相對最高.

圖6 隱私預算值對skyline 查詢結果集中準確率的影響Fig. 6 Effect of privacy budget value on the accuracy of skyline query result set

4 結 論

skyline 查詢的隱私保護問題受到越來越廣泛的關注，差分隱私能夠有效地保護skyline 查詢結果中不同子結果頁的隱私. 本文研究了基于差分隱私保護的skyline 查詢方法，提出了有效的頁敏感度計算方法和隱私預算值調節策略. 頁敏感度的計算能夠有效地適用于skyline 查詢方法，基于置信率和置信區間的隱私預算值調節策略確保了數據對象的有效性. 最后給出了基于拉普拉斯機制進行查詢結果隱私保護的SQADP_A 算法. 通過實驗表明：所提方法能減少skyline 查詢結果的隱私泄露數量，為用戶提供有效的隱私保護. 未來將深入研究不確定高維skyline 查詢過程中的數據隱私問題，使得在執行多次查詢時，查詢結果不僅能保證數據的有效性，也能保證數據的隱私性.