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

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

（1. 哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080；2. 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001）

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

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

綜上所述，針對(duì)傳統(tǒng)skyline 查詢方法無(wú)法有效地解決用戶隱私泄露的問(wèn)題，提出了一種基于差分隱私保護(hù)的skyline 查詢方法. 本文的主要貢獻(xiàn)包括3 個(gè)方面：

1） 為提高skyline 查詢的效率，提出最優(yōu)主導(dǎo)頁(yè)的概念. 最優(yōu)主導(dǎo)頁(yè)能夠針對(duì)skyline 查詢結(jié)果的分頁(yè)特性，確定查詢范圍的數(shù)據(jù)隱私保護(hù)等級(jí). 針對(duì)skyline 查詢的特性提出頁(yè)敏感度的概念，頁(yè)敏感度能夠滿足ε-差分隱私.

2） 為解決因噪音導(dǎo)致有效查詢結(jié)果的范圍無(wú)法量化的問(wèn)題，引進(jìn)置信區(qū)間和置信率的概念；為解決不同信任等級(jí)的用戶查詢結(jié)果相同會(huì)泄露數(shù)據(jù)隱私的問(wèn)題，提出一種基于置信率的隱私預(yù)算值調(diào)節(jié)方法，對(duì)不同的信任等級(jí)的用戶設(shè)定不同的隱私預(yù)算值，實(shí)現(xiàn)數(shù)據(jù)的分級(jí)保護(hù).

3） 為解決攻擊次數(shù)過(guò)多導(dǎo)致用戶隱私泄露的問(wèn)題，提出調(diào)整隱私預(yù)算和置信率，限制查詢次數(shù)的策略，從而保護(hù)隱私數(shù)據(jù).

1 基本定義

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

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

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

為進(jìn)一步調(diào)節(jié)頁(yè)敏感度，合理設(shè)置隱私預(yù)算的值，引入了基于差異化拉普拉斯分布的置信區(qū)間和置信率的概念. 置信區(qū)間和置信率與隱私預(yù)算有關(guān)，隱私預(yù)算的大小決定隱私保護(hù)的效果，如果所添加的噪聲是有效的，則一次查詢無(wú)法獲得用戶的隱私.但是，如果攻擊者進(jìn)行多次重復(fù)攻擊，并且噪聲分布符合拉普拉斯分布，實(shí)際結(jié)果就會(huì)在某一個(gè)區(qū)間. 為進(jìn)一步量化該區(qū)間范圍，給出置信區(qū)間的定義如定義3 所示.

定義3置信區(qū)間. 符合拉普拉斯分布的噪聲在某一個(gè)區(qū)間范圍內(nèi)，如果用 φ 代表置信區(qū)間的一半長(zhǎng)度，則 [ -φ,φ] 為置信區(qū)間[24].

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

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

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

定義4置信率.f(T)的查詢結(jié)果落在置信區(qū)間[μ-φ, μ+φ]的概率為置信率，則置信率通過(guò)累計(jì)函數(shù)計(jì)算為[24]

根據(jù)置信率進(jìn)一步量化隱私預(yù)算值ε的上界，設(shè)p為隱私泄露的概率，則

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

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

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

最后，為對(duì)skyline 的查詢結(jié)果進(jìn)行優(yōu)化，給出最優(yōu)主導(dǎo)頁(yè)的概念如定義5 所示.

定義5最優(yōu)主導(dǎo)頁(yè). 根據(jù)支配頁(yè)將skyline 查詢的輸入數(shù)據(jù)集T分為h個(gè)子數(shù)據(jù)集Tsub1,Tsub2, … ,Tsubh，在一次具體查詢中，如果查詢數(shù)據(jù)集為部分子數(shù)據(jù)集Tsubk,Tsubk+1, … ,Tsubk+z，其中k和z為正整數(shù)且0 ＜k+z≤h，則該查詢的最優(yōu)主導(dǎo)頁(yè)為T(mén)subk.

2 基于差分隱私保護(hù)的skyline 查詢方法

skyline 查詢結(jié)果通常是隱私數(shù)據(jù)，故用戶的隱私更容易泄露. 為保護(hù)用戶隱私，提出了基于差分隱私保護(hù)的skyline 查詢方法，所提方法的主要思想為：根據(jù)查詢對(duì)象的范圍確定查詢的最優(yōu)主導(dǎo)頁(yè)，從而確定頁(yè)敏感度；根據(jù)查詢者的查詢范圍、查詢次數(shù)評(píng)估查詢者的信任等級(jí)，限制查詢次數(shù)；根據(jù)頁(yè)敏感度和信任等級(jí)進(jìn)一步確定隱私預(yù)算，給出查詢結(jié)果.

2.1 最優(yōu)主導(dǎo)頁(yè)的計(jì)算方法

最優(yōu)主導(dǎo)頁(yè)是指在一次skyline 查詢范圍中，隱私最容易被泄露的某一頁(yè)查詢結(jié)果. 最優(yōu)主導(dǎo)頁(yè)的計(jì)算過(guò)程為：首先，通過(guò)skyline 查詢獲得查詢結(jié)果，將隱私最容易被泄露的某一頁(yè)查詢結(jié)果確定為最優(yōu)主導(dǎo)頁(yè)；其次，遍歷數(shù)據(jù)集并實(shí)時(shí)更新查詢結(jié)果；后續(xù)依據(jù)查詢范圍的改變?cè)賱?dòng)態(tài)更新最優(yōu)主導(dǎo)頁(yè). 如圖1 所示，圖中，Pt、Oy分別為第t頁(yè)、第y個(gè)對(duì)象.

圖1 skyline 分頁(yè)查詢示例Fig. 1 skyline paged query

首先，利用skyline 分頁(yè)查詢對(duì)所有的數(shù)據(jù)點(diǎn)進(jìn)行分頁(yè)，查到每一頁(yè)所有不被支配的數(shù)據(jù)點(diǎn)，每一頁(yè)為一個(gè)隱私泄露等級(jí)的子數(shù)據(jù)集.

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

表1 skyline 分頁(yè)查詢結(jié)果Tab. 1 Skyline paged query results

根據(jù)所有對(duì)象的屬性向量計(jì)算第i（i= 1, 2, …）頁(yè)skyline 查詢結(jié)果，第1 頁(yè)為首次查詢確定的最優(yōu)主導(dǎo)頁(yè)，每一次查詢的最優(yōu)主導(dǎo)頁(yè)都代表最容易泄露當(dāng)前數(shù)據(jù)隱私的子數(shù)據(jù)集.

2.2 頁(yè)敏感度的計(jì)算方法

在skyline 查詢過(guò)程中，局部敏感度計(jì)算的過(guò)程比較復(fù)雜，全局敏感度無(wú)法對(duì)子集進(jìn)行分類保護(hù)；查詢次數(shù)和查詢結(jié)果的隱私泄露程度具有正相關(guān)性，頁(yè)敏感度能夠調(diào)節(jié)兩者相關(guān)性的大小.

基于差分隱私保護(hù)的查詢通過(guò)添加噪音干擾查詢結(jié)果，從而保護(hù)用戶隱私. 查詢機(jī)制有兩種，分別是拉普拉斯機(jī)制和指數(shù)機(jī)制，其中拉普拉斯機(jī)制是一種噪音干擾機(jī)制，噪音是一種滿足拉普拉斯分布（Laplace distribution）的函數(shù). 基于拉普拉斯機(jī)制的skyline 查詢的頁(yè)敏感度為L(zhǎng)Sf(T)時(shí)，滿足ε-差分隱私.

基于以上論述，所提計(jì)算頁(yè)敏感度算法 （page sensitivity calculation algorithm，PSC_A）的主要思想為：首先，在預(yù)處理階段通過(guò)skyline 查詢結(jié)果初步確定第一次查詢的最優(yōu)主導(dǎo)頁(yè)，并計(jì)算頁(yè)敏感度；其次，在每次查詢時(shí)遍歷數(shù)據(jù)集，將當(dāng)前計(jì)算的頁(yè)數(shù)與最優(yōu)主導(dǎo)頁(yè)進(jìn)行比較，更新最優(yōu)主導(dǎo)頁(yè)，最終，輸出頁(yè)敏感度的值. PSC_A 如算法1 所示.

算法1PSC_A /*頁(yè)敏感度計(jì)算算法*/

輸入：數(shù)據(jù)集T.

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

1） 執(zhí)行skyline 查詢，通過(guò)skyline 查詢結(jié)果初步確定第一次查詢的最優(yōu)主導(dǎo)頁(yè)；

2） 對(duì)skyline 查詢數(shù)據(jù)集T進(jìn)行遍歷，計(jì)算每一個(gè)對(duì)象的頁(yè)數(shù)；

3） 將當(dāng)前計(jì)算的頁(yè)數(shù)與最優(yōu)主導(dǎo)頁(yè)進(jìn)行比較；

4） 如果當(dāng)前數(shù)據(jù)對(duì)象的頁(yè)數(shù)小于最優(yōu)主導(dǎo)頁(yè)，則更新最優(yōu)主導(dǎo)頁(yè)；

5） 計(jì)算當(dāng)前最優(yōu)主導(dǎo)頁(yè)的頁(yè)敏感度LSf(T)；

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

2.3 基于置信率的隱私預(yù)算值調(diào)節(jié)方法

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

利用拉普拉斯機(jī)制執(zhí)行ε-差分隱私保護(hù)，將滿足拉普拉斯分布的隨機(jī)噪聲添加到查詢結(jié)果中，拉普拉斯機(jī)制滿足

拉普拉斯噪聲計(jì)算公式為

式中：b＞ 0 為尺度參數(shù).

設(shè)b=ε/ Δf， μ = 0，則

對(duì)于任意絕對(duì)值變量，累計(jì)函數(shù)為

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

算法2PBAACR_A /*隱私預(yù)算值調(diào)節(jié)算法*/

輸入：查詢數(shù)據(jù)集T, 置信區(qū)間[1/2-ω,1/2+ω]，查詢次數(shù)C.

輸出：隱私預(yù)算值.

1） 調(diào)用PSC_A 算法計(jì)算頁(yè)敏感度；

2） 針對(duì)置信區(qū)間 [ 1/2-ω,1/2+ω] ，利用頁(yè)敏感度和式（2）計(jì)算置信率；

3） 利用式（3）計(jì)算隱私預(yù)算值；

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

5） 對(duì)置信區(qū)間 [ 1/2-ω,1/2+ω] 的隱私預(yù)算值進(jìn)行判斷，如果滿足該置信區(qū)間的置信率要求，則輸出隱私預(yù)算值；否則，隱私預(yù)算值設(shè)置為0.

2.4 基于差分隱私保護(hù)的skyline 查詢算法

基于頁(yè)敏感度計(jì)算和隱私預(yù)算值調(diào)節(jié)方法，針對(duì)skyline 查詢的次數(shù)過(guò)多導(dǎo)致用戶隱私可能泄露的情況，可采取限制用戶查詢次數(shù)的策略加大隱私保護(hù)力度. 在置信區(qū)間為 [ 1/2-ω,1/2+ω] 的情況下可根據(jù)隱私預(yù)算值和全局敏感度計(jì)算出置信率. 查詢結(jié)果滿足ε-差分隱私的查詢次數(shù)上限設(shè)為c，當(dāng)查詢次數(shù)達(dá)到c時(shí)，需要對(duì)用戶信任等級(jí)和隱私參數(shù)重新計(jì)算，再利用PBAACR_A算法對(duì)隱私預(yù)算值進(jìn)行調(diào)節(jié)，最終得到滿足隱私保護(hù)要求的skyline查詢結(jié)果.

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

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

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

輸出：skyline 查詢結(jié)果.

1） 調(diào)用PBAACR_A 算法得出隱私預(yù)算值；

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

3） 基于置信區(qū)間 [ 1/2-ω,1/2+ω] 計(jì)算置信率；

4） 遍歷查詢數(shù)據(jù)集T中的所有子數(shù)據(jù)集；

5） 針對(duì)相鄰子數(shù)據(jù)集進(jìn)行skyline 查詢，得到查詢結(jié)果集；

6） 計(jì)算頁(yè)敏感度；

7） 利用拉普拉斯機(jī)制，根據(jù)隱私預(yù)算值和頁(yè)敏感度對(duì)查詢結(jié)果集添加噪音；

8） 發(fā)布skyline 查詢結(jié)果.

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

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

為構(gòu)造對(duì)比算法，對(duì)文獻(xiàn)[20]所提算法和文獻(xiàn)[21]所提算法的關(guān)鍵步驟進(jìn)行適當(dāng)?shù)男薷? 在文獻(xiàn)[20]所提算法進(jìn)行剪枝之前增加了最優(yōu)主導(dǎo)頁(yè)的計(jì)算，并將敏感度更改為頁(yè)敏感度，簡(jiǎn)稱為OGWP （optimizing GAN obfuscator with pruning）算法；在文獻(xiàn)[21]所提算法進(jìn)行信息熵的計(jì)算之前增加最優(yōu)主導(dǎo)頁(yè)的計(jì)算，并將敏感度的計(jì)算更改為動(dòng)態(tài)調(diào)節(jié)敏感度，簡(jiǎn)稱為FOQIL （find the optimal quantization interval length）算法. 本節(jié)將本文所提SQADP_A 算法與OGWP 算法、FOQIL 算法進(jìn)行對(duì)比實(shí)驗(yàn)，驗(yàn)證所提算法的可行性和有效性.

3.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)1本實(shí)驗(yàn)主要對(duì)比3 種算法的數(shù)據(jù)規(guī)模對(duì)算法執(zhí)行時(shí)間的影響. 圖2 展示了數(shù)據(jù)集對(duì)象數(shù)量從64 kB 增長(zhǎng)到1 024 kB 時(shí)3 種算法的查詢效率對(duì)比結(jié)果，分別分析數(shù)據(jù)規(guī)模的不同對(duì)CPU 運(yùn)行時(shí)間的影響. 由于剪枝算法能夠剪掉一部分無(wú)效對(duì)象，且最優(yōu)主導(dǎo)頁(yè)是動(dòng)態(tài)更新的，所以3 種算法在數(shù)據(jù)規(guī)模較小的時(shí)候相差不大，但是隨著數(shù)據(jù)規(guī)模的增加，F(xiàn)OQIL 算法需要額外處理的數(shù)據(jù)量較多，因此，對(duì)很多無(wú)效的對(duì)象進(jìn)行最優(yōu)主導(dǎo)頁(yè)和信息熵的計(jì)算量也增加，查詢效率相對(duì)較低. 梯度修剪策略由于沒(méi)有涉及到大量的復(fù)雜計(jì)算，而是基于高斯分布針對(duì)不同場(chǎng)景進(jìn)行差異化剪枝，因此，OGWP 算法效率較高.

圖2 數(shù)據(jù)規(guī)模對(duì)查詢效率的影響Fig. 2 Effect of data size on query efficiency

實(shí)驗(yàn)2本實(shí)驗(yàn)主要評(píng)估數(shù)據(jù)規(guī)模對(duì)查詢結(jié)果可靠性的影響. SQADP_A 算法依據(jù)剪枝規(guī)則和存在概率排序規(guī)則進(jìn)行查詢. 實(shí)驗(yàn)中數(shù)據(jù)項(xiàng)泄露數(shù)為結(jié)果集中隱私數(shù)據(jù)數(shù)量，因變量為數(shù)據(jù)集的規(guī)模，在5 個(gè)不同規(guī)模的數(shù)據(jù)集上進(jìn)行查詢. 如圖3 所示，因?yàn)槊看蝧kyline 查詢的結(jié)果輸出后，才作為計(jì)算頁(yè)敏感度的剪枝結(jié)果，所以SQADP_A 算法的輸出結(jié)果集的無(wú)效數(shù)據(jù)最少. 與SQADP_A 算法相比，F(xiàn)OQIL 算法的查詢結(jié)果隱私項(xiàng)較少，隱私保護(hù)等級(jí)較高，但是由于涉及到大量的計(jì)算，查詢效率較低.OGWP 算法輸出結(jié)果的隱私數(shù)據(jù)數(shù)量高于FOQIL算法和SQADP_A 算法，隱私保護(hù)效果最差. 因此，由實(shí)驗(yàn)結(jié)果可知：如果不考慮查詢時(shí)間的影響，F(xiàn)OQIL 算法和SQADP_A 算法更能保護(hù)用戶隱私.此外，雖然FOQIL 算法和SQADP_A 算法的隱私保護(hù)等級(jí)相差不大，但是，SQADP_A 算法的查詢速度更快. 因此，隨著數(shù)據(jù)規(guī)模的增加，SQADP_A 算法能在查詢速度較快的情況下增強(qiáng)查詢結(jié)果的隱私保護(hù).

圖3 數(shù)據(jù)規(guī)模對(duì)查詢結(jié)果可靠性的影響Fig. 3 Effect of data size on the reliability of query results

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

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

實(shí)驗(yàn)4本實(shí)驗(yàn)評(píng)估了3 種算法中的隱私預(yù)算值設(shè)定對(duì)skyline 查詢結(jié)果集中隱私泄露程度的影響，數(shù)據(jù)規(guī)模為256 kB，隱私預(yù)算值分別設(shè)為10.0、5.0、0.8、0.5、0.4，實(shí)驗(yàn)結(jié)果如圖5 所示. 由實(shí)驗(yàn)結(jié)果可知：隱私預(yù)算值設(shè)定較低的情況下3 種算法的隱私泄露程度沒(méi)有明顯的區(qū)別，3 種算法在隱私預(yù)算設(shè)定為0.4 時(shí)的隱私泄露的差距較小，但是隨著隱私預(yù)算值設(shè)定值的增加，SQADP_A 算法的隱私泄露程度逐漸收斂，并且在隱私預(yù)算值較?。ㄐ∮?.0）的情況下，SQADP_A 算法的隱私保護(hù)效果最好. 隱私預(yù)算設(shè)定值為10.0 時(shí)，OGWP 算法的隱私泄露程度較高，隨著隱私預(yù)算值的增加，F(xiàn)OQIL 算法的隱私保護(hù)效果有降低的趨勢(shì).

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

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

圖6 隱私預(yù)算值對(duì)skyline 查詢結(jié)果集中準(zhǔn)確率的影響Fig. 6 Effect of privacy budget value on the accuracy of skyline query result set

4 結(jié) 論

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