垂直分布數據集上的安全Skyline查詢算法

吳吉斌，王箭

（南京航空航天大學計算機科學與技術學院，江蘇南京211106）

Skyline查詢[1]能從大量多維數據中篩選出人們感興趣的數據，是一種重要的數據分析方法，并在推薦系統等場景中有廣泛的應用。2001年，Borzsonyi等[2]研究了大規模數據集上的skyline查詢算法。此后，Skyline查詢在分布式存儲及其相關領域受到廣泛關注[3-7]。Balke等在中首次提出了垂直分布數據集上Skyline查詢方案，但該方案中每個服務器只能存儲一維數據，當處理多維數據時開銷巨大。Trimponias等在文獻[7]中提出了一種垂直劃分Skyline查詢算法VPS（vertical partition skyline）。該方案中每個服務器可存儲任意維度的數據，降低了多維度數據集計算時的硬件開銷。然而目前僅有的兩種垂直分布數據集上的Skyline查詢方案沒有考慮數據集的隱私保護需求，查詢過程中數據均以明文形式傳輸，服務器中存儲的數據直接泄露給查詢端，造成敏感數據泄露。現實生活中查詢服務提供商一般為商業公司，并將其服務器內存儲的數據集視為商業機密。因此如何實現垂直分布數據集上保護隱私的Skyline查詢成為目前亟待解決的問題。

隨著隱私保護需求的不斷增長，分布式數據集上保護隱私的Skyline查詢方案受到了越來越多的關注。Bothe等在[8]中提出了使用可逆矩陣加密數據并進行Skyline查詢的方案。文獻[9]中提出了基于0-1編碼技術[10]的安全Skyline查詢技術。Liu等在[11]中提出了一種基于使用Paillier算法[12]加密的雙服務器Skyline查詢方案。然而，以上方案在數據比較過程中，服務器均需擁有數據點的所有維度，因此不適用于垂直劃分數據集上的Skyline查詢。本文提出了垂直分布式的保護隱私Skyline查詢方案PPVPS。該方案使用安全多方和積協議對不同參與方之間的交互數據加密，實現待查詢數據集的隱私保護，并能實現抗合謀攻擊。最后通過理論分析證明了該方案的安全性，并通過模擬實驗對協議運行效率進行了評估。

1 預備知識

1.1 Skyline查詢

Skyline查詢是一種數據分析方式，是指從給定d維度數據集DS中，選出子集S，其中子集S中的所有數據點不被任意其他數據點支配。這里支配是指對于d維數據點P和Q，如果數據點P每個維度都不比數據點Q差，并且數據點P至少有一個維度上比數據點Q好，那么就稱數據點P支配數據點Q。這里假設數據點每個維度上的較小值優于較大值，比如對顧客而言，商品價格越低越優。對于給定數據集DS中的數據點P，若數據點P支配該數據集內較多的數據點，則稱該數據點為錨點，記做Panc。

定義1（帕累托一致函數）對任意函數f，如果向量 P1支配向量 P2，一定存在 f（P1）f（P2），則稱函數 f為帕累托一致函數。

這里通過一個例子介紹skyline查詢在推薦系統中的應用。假設某旅客要去海邊旅游，需要訂一個價格便宜并且離海邊近的酒店。某旅游公司的數據庫中存儲了各個酒店的價格和到海邊的距離，如圖1所示，以每個點表示一個酒店，其中x軸表示酒店價格，y軸表示酒店到海邊的距離。對于圖中的酒店A和酒店B，酒店A的價格和到海岸的距離都小于酒店B，因此酒店A支配酒店B。圖中不存在某酒店價格和到海岸的距離均小于酒店A，因此酒店A不被任何其他酒店支配，酒店A是Skyline點。可以看出虛線相連的4個點是這些酒店中的Skyline點。

圖1 Skyline查詢經典案例

假設 d 維數據集 DS={P1，P2，…，Pn}垂直分布在m個服務器中。這里以m為2舉例，數據垂直分布方式如圖2所示，服務器N1和N2分別存儲數據點不同維度，并且除數據點的ID外，兩服務器存儲維度不重復。

圖2 垂直分布示意圖

1.2 VPS算法

2013年，Trimponias等[7]提出了一種垂直分布數據集上的Skyline查詢算法VPS。假設d維數據集 DS={P1，P2，…，Pn}垂直分布在 m 個服務器中，則數據點Pi的維度和為：

假設數據點P在服務器Ni中的投影為P.Di，則數據點P在服務器Ni中的維度和為fsum（P.Di）。服務器按fsum從小到大順序排列數據點，查詢端Client初始化Panc為空，該算法執行過程如下。

1）選擇未返回Panc的服務器Ni，發送Ni序列頂端數據點P到查詢端

2）若數據點P與Panc的維度和滿足fsum（P）

3）重復1-2，直到所有服務器返回Panc。

4）所有服務器計算Panc的本地支配區間，將不被Panc支配的數據點發送到查詢端

5）查詢端在剩余數據點上計算Skyline

文獻[7]給出了該算法詳細的正確性分析和準確性證明。但該算法中數據以明文形式傳輸，服務器存儲的數據直接泄露給查詢端，無法滿足用戶隱私保護需求。

1.3 安全多方和積協議

Yang等在文獻[13]中提出了一種抗合謀攻擊的安全多方和積協議SPOS（Secure Product of Summations Protocol），該協議使用同態加密[12]實現安全多方和積的計算，并能夠抵抗合謀攻擊。該協議假設有m個參與方且第i個參與方Ni有數據（xi，r）i，m方合作計算并保證計算過程中任意參與方無法獲得其他參與方的任何有效數據。該協議中參與方是平等的，在計算過程中每個參與方執行相同的操作，不存在中間節點。

文獻[13]中對該協議的安全性進行了詳細的證明。在半誠實模型下，該協議是（m-1）-隱私[14]的，即前m-1個參與方共謀，也無法推測出第m個參與方的有效數據。

2 隱私保護的垂直劃分skyline查詢

本節介紹隱私保護的垂直劃分Skyline查詢協議（PPVPS），該協議能實現垂直劃分數據集上的安全Skyline查詢。

2.1 系統模型

圖3 系統模型

如圖3所示，該系統模型包括一個客戶端（Client）和 m（m>1）個服務器{N1，N2，…，Nm}。包含 n 個 d 維數據點的數據集 DS={P1，P2，…，Pn}垂直分布在m個服務器中。假設集合Di中不存在完全相同的兩個點，即任意兩個點Pa.Di=（Pai1，Pai2，…，Paik）和 Pb=（Pbi1，Pbi2，…，Pbik），至少存在一個正整數 j∈[1，k]，滿足 Paij≠Pbij。客戶端的目標是從數據集DS中查找出所有的skyline點。由于每個子數據集包含了隱私信息，每個服務器所持有的子數據集既不愿意發送給其他的服務器，也不愿意泄漏給客戶端。

2.2 PPVPS協議

該協議可以分為三個部分：第一部分篩選錨點，第二部分篩選出不被錨點支配的數據點，第三部分在篩選出的數據上計算skyline。

第一部分（步驟1-6）服務器先對數據進行預處理，按照fsum值從小到大的順序生成序列Li。客戶端選擇一個未返回當前錨點的服務器，返回該服務器序列頂端的數據點P的ID。其中數據點P不能屬于序列VS，否則重新返回下一個數據點。如果Panc為空，則令Panc=P，否則客戶端將數據點P和錨點Panc的ID發送給所有服務器。

對于服務器Ni，該服務器計算fsum（Panc.Di）和fsum（P.Di）的值，并令xi=fsum（Panc.Di）-fsum（P.Di），并生成隨機正整數ri。根據SPOS，客戶端生成p，其中p=因為所以若p>0，可得 fsum（Panc）-fsum（P）>0，即 fsum（P）0，則令Panc=P。重復步驟2-5直至所有服務器返回當前錨點。

第二部分（步驟7）服務器返回不被錨點支配的數據點的ID。若該數據點未在第一部分中返回客戶端，則客戶端將該數據點插入序列VS尾部。值得注意的是，第一部分和第二部分中數據點按服務器序列順序返回，因此序列VS中排在前面的數據點一定不被排在后面的數據點支配。假設序列VS中排在前面的數據點P1被排在后面的數據點P2支配，因此任意服務器Ni中P2至少有一個維度小于P1，因此在Ni中P2的各維度值之和一定小于P1的各維度值之和，即滿足fsum（P2.Di）

第三部分（步驟8-12）是在序列VS的數據上計算SKY。客戶端選取序列VS前端的數據點P和集合SKY中的數據點P*，如果SKY為空，則將數據點P放入集合SKY。否則客戶端將數據點P和數據點P*的ID發送到服務器。

協議隱私保護的垂直劃分skyline查詢算法（PPVPS）輸入：服務器輸入數據集DS輸出：客戶端輸出SKY 1．客戶端初始化 Panc= φ，VS= φ 2．客戶端選定任意未返回當前錨點的服務器Ni，并按順序返回序列Li頂端數據P（P∈VS）的ID，并將P存入序列VS 3．若Panc=φ，則令Panc=P，否則將P和Panc的ID發送到所有服務器4．任意服務器Ni計算xi=fsum（Panc.Di）-fsum（P.Di）5．客戶端計算p=SPOS（xi，ri），i=1，2，…，m。如果p>0則令Panc=P 6．重復步驟2-5直到所有服務器返回當前錨點7．任意服務器Ni將所有不被錨點本地支配的數據P的ID返回客戶端，如果P∈VS，將P插入序列VS尾部8．客戶端初始化SKY=φ 9．客戶端按順序選取VS頂端元素P，若SKY=φ，則將數據點P加入集合SKY，否則選取SKY集合內任意數據P*，并將P和P*的ID發送到所有服務器10．對于服務器 Ni，如果 P*.Di支配 P.Di，則服務器 Ni令 xi=0，否則令 xi=random（0，1）11．客戶端計算p=（xi，ri），i=1，2，…，m。若對于任意P*都有p≠0，則將P加入集合SKY 12．重復9-11直到序列VS內所有元素被選取，輸出SKY

對于任意服務器Ni，如果P*.Di本地支配P.Di，則令xi=0，否則令xi為正隨機數，并生成隨機正整數ri。隨后根據SPOS，客戶端生成因為不等式0恒成立，所以若p≠0則≠0，即數據點P不被數據點P*全局支配。如果數據點P不被集合SKY內任意數據點支配，則將數據點P是Skyline點，并將其放入集合SKY。重復步驟9-11直至序列VS內的所有數據點被選取。協議完成后，集合SKY是最終篩選出的Skyline點集合。

3 協議分析

3.1 正確性分析

定理1 在半誠實模型下，本文所提出的PPVPS能夠正確地計算出所有的Skyline點。

證明：證明可以分為兩點，第二部分執行完畢后所有的Skyline點都被返回客戶端；第三部分中只需判斷后選中的數據點是否被SKY集合內的數據點支配，即可確定該數據點是否為Skyline點。第一點：假設某Skyline點P未返回客戶端，因為該點是Skyline點，所以點P某維度一定優于錨點，則該點在某服務器內不被錨點支配。服務器會將不被錨點支配的數據點返回客戶端，因此該點在第二部分完成時一定已被返回客戶端。第二點：第三部分客戶端按fsum從小到大的順序對數據點排序，fsum是帕累托一致函數，因此序列前端的數據點一定不被序列后端的數據點支配，因此只需要判斷后選中的數據點是否被SKY集合內的數據點支配。

3.2 安全性分析

定理2 （[15]）假設g可以安全約減成f，并且f是安全的，那么一定存在一個協議安全的計算g。

文獻[15]中Goldreich提出安全性約減理論，該理論提出如果一個協議能夠使用f安全的計算g，則稱g可安全約減成f。

定理3 在半誠實模型下，本文提出的PPVPS能是（m-1）-隱私的，可以抵抗合謀攻擊。

證明：PPVPS協議的數據交互有兩類：客戶端和服務器間傳輸的數據點ID和調用協議SPOS的輸入和輸出。顯然參與方無法通過數據點ID推導出相關隱私信息，并且協議SPOS是（m-1）-隱私的，PPVPS協議可安全約減為協議SPOS，因此PPVPS協議是（m-1）-隱私的，可以抵抗合謀攻擊。

4 實驗評估

本實驗以多臺 Ubuntu 12.04，3.40GHz CPU，8GB RAM的臺式機模擬服務器，以一臺Windows7，2.20GHz CPU，8GB RAM的臺式機模擬查詢端。實驗數據集采用的是skyline查詢經典數據集Core和NBA。其中數據集Core含有68K條9維數據記錄，共有1533個skyline點。數據集NBA含有21K條8維數據記錄，共有1195個skyline點，數據集的相關信息如表1所示。

表1 數據集信息

該實驗過程利用Socket實現服務器與查詢端之間的數據通信。本實驗結果受到待測試數據集基數和服務器數量的影響，并且不同數據集錨點分布不同，會對實驗結果造成一定的影響。圖4展示了在Core數據集中，PP-VPS協議和VPS協議在服務器數量從2增長到9的過程中的計算時間。當服務器數量從2增長到5時，PPVPS協議運行時間從65.849秒增加到200.945秒。當服務器數量小于5時，PPVPS和VPS算法執行時間近似，當服務器數量大于5時，PPVPS執行時間出現較快增長。

圖4 Core實驗結果對比

圖5展示了在NBA數據集中，PPVPS協議和VPS協議在服務器數量從2增長到8的過程中的計算時間變化曲線。從圖中可以看出，隨著服務器數量從2增加到5，協議運行時間從19.013 s增加到63.354 s，當服務器數量逐漸增加到8時，VPS協議和PPVPS協議的計算時間出現波動，這是因為數據集的分布影響錨點篩選，從而影響協議運行時間。

圖5 NBA實驗結果對比

當服務器數量較少時，PPVPS協議在實現安全Skyline查詢的條件下，計算時間與VPS協議近似，該實驗證明了PPVPS協議的可行性。

5 結束語

提出了一種垂直分布數據集上保護隱私的Skyline查詢協議。理論分析顯示本方案能夠正確地實現Skyline查詢，并保護數據集的隱私信息。在參與者合謀攻擊的情況下，依然可以確保隱私信息的安全。進一步，還通過理論分析和模擬實驗對新協議的運行效率進行了評估，結果顯示可以取得較高的運行效率。在未來的工作中，將著重研究協議效率的提升和通信復雜度的降低，使其在現實中得到廣泛的應用。