隱私保護下的組最近鄰查詢算法研究

劉曉樂　李　博

(河南工程學院計算機學院　河南 鄭州 451191)

?

隱私保護下的組最近鄰查詢算法研究

劉曉樂李博

(河南工程學院計算機學院河南 鄭州 451191)

摘要針對現有的組最近鄰GNN(Group Nearest Neighbor)查詢的隱私保護算法沒有考慮地圖匹配攻擊的問題，在無可信第三方的模型下，提出基于三階段的保護用戶位置隱私的組最近鄰算法SFR(Send-Filter-Refine)。發送階段中用戶向服務商發送可防御地圖匹配攻擊的矩形區域來代替精確位置；過濾階段中服務商利用各區域計算所有可能成為結果的數據點并回傳給用戶；求精階段為了防止發起查詢的用戶間的隱私泄露，通過用戶間的無序交互來得到最終的查詢結果,并提出多個剪枝策略來加快查詢速度。基于真實路網的實驗結果表明，SFR與傳統方法相比，有更高的查詢效率和更低的受攻擊率。

關鍵詞組最近鄰隱私保護位置服務提供商

0引言

近年來，隨著移動計算技術和通信技術的不斷發展，隨時隨地獲得個人精確位置成為可能，基于位置的服務LBS(Location Based Service)受到人們的普遍關注。組最近鄰GNN查詢[1]是最近鄰NN查詢[2]的一種變體，它查找的是到給定多個查詢對象距離之和最小的點。GNN查詢在現實生活中有廣泛的應用，例如，由多個社區所組成的社交網絡中，查找各個社區的領導者/核心，可以查找到該社區中各成員距離和(表示成員間的熟悉程度)最小的人；同一城市的一組用戶想查詢一家離他們距離之和最小的餐館作為見面地點等。

然而，用戶在享用LBS的同時，包含他們精確位置的信息被位置服務提供商LSP(Location Service Provider)所獲取。LSP能夠根據這些信息得到用戶的生活方式、健康狀況和政治背景等[3]。個人隱私泄露問題逐漸引起廣大學者的關注[4-6]。

圖1　用戶的精確位置及相應的位置區域

為了在提供LBS的同時，保護用戶的隱私，一種解決方法是利用可信的第三團體TTP(Trusted Third Party)在用戶和LSP之間進行通信[7]。這種方法有一定的局限：(1)所有用戶將位置信息暴露給TTP，存在單點被攻擊的危險；(2)用戶的隱私只在當前時刻被保護，不能保證“相關攻擊”(如用戶運動的歷史軌跡)。另一種常用的方法是用戶向LSP發送一個位置范圍(通常是一個矩形)來代替精確的位置[3]，如圖1所示，用矩形區域代替精確位置點。LSP返回該矩形下所有可能成為查詢結果的數據點，用戶再根據自己的精確位置，從這些點中直接找到最終的結果。這種無TTP參與的模型，避免了上述問題。本文采取的就是無TTP模型。

盡管無TTP模型下的NN查詢相關的隱私保護技術有很多[8]。但由于GNN查詢中發出查詢的用戶有多個，它的查詢結果取決于所有查詢用戶的位置，單個用戶無法只根據自己的精確位置信息來得到GNN結果。因此，傳統用于NN查詢的隱私保護技術無法直接應用到GNN查詢中。文獻[9]首次解決了隱私保護下的GNN查詢算法，但算法使用簡單的矩形區域代替用戶的精確位置，容易受到地圖匹配的攻擊。例如，攻擊者在獲取地圖信息后，可通過地圖匹配的方法排除一些障礙區域(如湖泊等)，從而大大增加攻擊的概率。此外，地圖中所包含一些如醫院、減肥中心等重要的語義信息，簡單的矩形區域可能包含這些敏感信息，也容易泄露用戶個人隱私。另外，發出GNN查詢的用戶雖然有可能彼此熟識，但用戶之間也需要保護位置隱私，這為隱私保護下的GNN查詢提出了新的挑戰。

本文解決了GNN查詢的隱私保護問題，所提出的基于三階段的查詢算法SFR。不僅可有效防御地圖匹配攻擊，還能保護發起查詢的各個用戶間的位置隱私。在發送階段，用戶結合地圖中的語義信息向LSP發送各自的位置區域來代替精確位置，避免用戶位置隱私的泄露并防御地圖匹配攻擊；在過濾階段，提出了針對位置區域的GNN查詢算法，所提的剪枝策略能夠有效過濾掉那些一定不是結果的數據點；最后在求精階段計算出最終精確的GNN結果，用戶間進行的無序交互，避免了用戶間的隱私泄露，并最終得到正確的查詢結果。

最后，基于真實城市路網，對本文所提算法SFR與文獻[9]所提的算法IPPF進行了性能比較和驗證。實驗結果表明，與IPPF相比，SFR有更高的查詢效率和更低的受攻擊率。

1問題定義

本文假設用戶和LSP通過網絡(移動網絡或因特網)互相連接，查詢集合Q由n個用戶u1,u2, …,un組成，它們相應的位置用l1,l2, …,ln來表示，被查詢的數據點集合用P表示。下面列出了傳統針對點的GNN查詢以及隱私保護下針對區域的GNN查詢的形式化定義。

隱私保護下的GNN查詢中，LSP只知道各用戶的位置區域，所有用戶到數據點的距離之和是一個范圍，而不是一個值，因此無法直接得到精確的GNN結果。算法SFR先執行針對這些區域的GNN查詢，來得到所有可能成為結果的數據點，放在候選集合Scnd中。Scnd中的對象都是可能成為最終GNN結果的點，所有可能成為GNN結果的點也一定在Scnd中。本文在下一節中對如何快速得到Scnd，以及如何利用Scnd進一步得到最終的GNN結果進行了詳細的介紹。

2隱私保護下的GNN查詢算法SFR

SFR采用無TTP模型，即不存在任何中心節點參與查詢運算，但由于GNN查詢結果取決于所有發出查詢用戶的精確位置，單個用戶無法直接根據自己的位置計算出結果，這給無TTP模型下的GNN查詢帶來了難度和挑戰。

本文提出了由協調者參與的查詢算法框架，在進行GNN查詢之前，系統隨機選取一個協調者，用來協助系統完成隱私保護下的GNN查詢。該協調者可以是發出GNN查詢的其中一個用戶，也可以是系統中不參與查詢的其他用戶。它與中心節點的不同之處在于，不同的GNN查詢，系統所選取的協調者是不同的，從而消除了單個節點被攻擊的危險。此外，協調者只能獲得用戶的ID以及它所發出的查詢類型，而不知道用戶所在的位置，進而保護了用戶與協調者之間的位置隱私。本節將對基于三階段的SFR算法進行詳細介紹。

2.1發送階段

發出GNN查詢的組內每個用戶首先向協調者注冊自己的ID(如IP地址、電話號碼等)，并從協調者處獲得一個查詢ID(QID)。再結合地圖中的語義信息，生成自己的安全位置區域，把該區域和QID發送給LSP，在因特網中發送時可采用假名服務[10]的方法，在無線個人區域網絡(如藍牙或802.11)中發送時可采用隨機選取節點[8]的方法。這些技術能夠向LSP隱藏用戶的ID信息。最后，協調者只把與GNN查詢有關的信息(QID、組查詢用戶個數)發送給LSP。

生成用戶的安全位置區域首先要考慮地圖匹配攻擊，這是因為攻擊者在獲取地圖信息后，可通過地圖匹配的方法排除一些行人車輛無法到達的障礙區域(如湖泊等)，從而增加攻擊的概率；其次還要考慮地圖中包含的重要語義信息的泄露，這是因為地圖文件不僅包含位置坐標等信息，還包含著更重要的語義信息，如醫院、減肥中心和軍事要地等。攻擊者可根據一些敏感的語義信息來獲取用戶生活方式、健康狀況和政治背景等個人隱私。

針對重要語義信息的保護問題，系統先在地圖上定義了幾個類型的重點保護區域(如醫院、減肥中心、心理診所等)，先離線預計算出這些區域對應的一些安全區域，使得安全區域要么不包括重要區域，要么包含k種重要區域。若用戶處在這些重點保護區域內，直接為其生成安全區域。當用戶所要保護的語義類型不在系統的預計算列表中時，系統再為用戶在線構建安全的位置區域。發送階段的安全區域生成算法見算法1。

算法1安全區域生成算法

輸入：N個用戶的精確位置(*ax, *ay), 障礙閾值δ;

輸出：N個用戶的安全區域(*lx, *ly, *hx, *hy);

1.for(i =1toN)

2.if(該點處在預計算的重點保護區域內)

3.return相應的(lx[i], ly[i], hx[i], hy[i]);

4.else

5.生成一個包含點(ax[i], ay[i])、長寬各為

1000的矩形(lx[i], ly[i], hx[i], hy[i]);

6.Swhole= 1000000;

7.計算該矩形內障礙空間的面積Sobstacle;

9.改變矩形或增加長和寬;

10. 重新計算Swhole；

11.return滿足閥值的lx[i],ly[i],hx[i],hy[i];

2.2過濾階段

LSP接到GNN查詢請求后，執行RGNN查詢。由于用戶的位置是一個區域，數據點與查詢用戶間的距離是一個范圍而不是一個固定值，許多數據點都可能成為最終的結果。過濾階段的目的就是如何快速得到RGNN定義中的候選集合Scnd，使得Scnd中的對象都是可能成為最終GNN結果的點，而所有可能成為GNN結果的點也一定在Scnd中。本文改進傳統最佳優先BF(Best-First)[11]查找算法，提出了MBF(ModifiedBest-First)算法來執行RGNN查詢。

MBF算法與BF算法的執行過程類似，但由于MBF處理的是多個區域(矩形)，元素到多個矩形的距離之和是一個范圍，因此查找過程以及算法結束條件更加復雜。算法的思想就是按照ds值由小到大來處理R*樹中的結點，直到找到某結點。若其ds值大于當前所處理過的結點中最小的dl值，剩下結點中的數據點就可以被過濾掉。具體見算法2。

算法2過濾算法MBF (Modified Best-First)

輸入：N個用戶的位置區域(*lx,*ly,*hx,*hy),R*樹;

輸出：可能成為結果的候選集合Scnd;

1.Scnd初始化為空;

2.優先隊列PQ初始化為R*樹的根結點root;

3.全局變量minmaxdist= root.dl;

4.while (PQ不為空) do

5.從PQ中取一個結點pc;

6.if (pc.ds>minmaxdist) returnScnd;

7.minmaxdist= min{minmaxdist,pc.dl};

8.if (pc是中間結點)

9.計算每個孩子的ds值并按升序插到PQ中;

10.else

11.將pc插入到集合Scnd中;

12.returnScnd;

初始時把根結點(root)放入優先隊列PQ中，優先隊列中的元素(中間結點MBR或者是葉子結點存儲的數據點)按照其ds進行升序排列。算法不斷地從隊列中取出有最小ds的元素進行處理。記錄和更新全局變量minmaxdist使它始終是所有被處理過的數據點的dl的最小值(行3和7)。這樣，當從優先隊列中取出的元素pc的ds大于minmaxdist時，pc以及優先隊列中的其他元素就可被剪枝掉(行6)，在pc之前被處理的數據點則被放入候選集合中(行11)。下面給出MBF算法的正確性證明。

定理1假設minmaxdist是某數據點p到各查詢矩形最大距離之和，pc是從當前從優先隊列中取出的元素，若ds(pc)>minmaxdist，則pc以及優先隊列中的剩余元素不可能是最終的GNN查詢結果。

證明：反證法。假設最終的GNN結果是pc或優先隊列中剩余元素中的其中一個，記作pr。根據RGNN的定義可知，無論發出查詢的n個用戶處在查詢矩形的哪個位置，pr到這n個用戶的距離之和都要小于其他數據點。根據已知條件pc.ds>minmaxdist，且優先隊列是按照各元素的ds值進行升序排列，因此pr.ds>pc.ds>minmaxdist。也就是說，無論發出查詢的n個用戶處在查詢矩形的哪個位置，p到這n個用戶的距離之和都要小于pr。與假設相矛盾，定理成立，證畢。

2.3求精階段

求精階段是保護用戶與LSP之間以及用戶彼此間隱私的關鍵，該階段的目的是在不泄露用戶隱私的前提下，對Scnd中的數據點進行求精計算，進而得到最終正確的GNN結果。

假設發出GNN查詢的用戶有4個，過濾階段得到的候選集中有5個數據點。用戶與各數據點間的距離如表1所示。為保護用戶與LSP間的隱私，用戶不會把位置信息發送給LSP，而是通過用戶間的交互，把最終的距離和發送給LSP。如表2所示，u1把其到p1的距離2發送給u2，u2再用其到p1的距離更新當前和，即得到11，并發送給u3。最后，u4計算出全部和24，發送給LSP。以此類推，計算出所有點的距離和，和最小的點就是最終結果，即p4。

表1　用戶與Scnd中各數據點的精確距離

表2　用戶更新與Scnd中各數據點的距離和

以上方法在用戶之間進行距離傳遞時，可能會在彼此間泄露隱私。例如u1總是把自己到其他數據點的距離傳遞給u2，u2就可以根據u1到任意兩個數據點的距離來得到u1的精確位置。為了保護用戶間的隱私，SFR在更新距離和時，對Scnd中不同的數據點，用戶的交互(更新)順序隨機產生。當GNN查詢只有2個用戶時，先更新距離的第一個用戶會把自己的位置信息暴露給第二個用戶。這種情況下，協調者需要充當第三個用戶參與交互。由于用戶只向協調者發送QID以及更新后的距離信息，并不會暴露自己的ID和位置信息，從而保護了用戶的隱私。

此外，為了提高計算效率，本文還提出了剪枝算法來優化求精過程。SFR用一個全局變量SUM記錄當前已計算的距離和的最小值用來剪枝。若某用戶更新后的距離和大于SUM，則該數據點就可被剪枝掉，無需再計算其他用戶到該點的距離，從而減少了計算代價。具體算法見算法3。

算法3優化求精算法

輸入：用戶個數N, 候選集合Scnd以及候選對象個數M;

輸出：查詢結果rst;

1.全局變量SUM= ∞; *sum=0;

2.for (i= 1 toM)

3.隨機產生用戶的一個更新順序list;

4.for (j= 1 toN)

5.計算用戶list[j]到對象Scnd[i]的距離dist；

6.sum[i] =sum[i] +dist;

7.if (sum[i] >SUM)

8.break;

9.if (j==N&&sum[i]

10.SUM=sum[i];

11.rst=Scnd[i];

12.returnrst;

根據算法3，表3給出了優化后的求精算法的一個測試用例。根據表1中用戶與數據點的實際距離可知，p2經過各用戶的更新，所得到的SUM值13是當前最小的距離和(行9-11)。對于p3，在u4更新完距離和后，當前距離和16大于13，因此p3可直接被剪枝，u1到p3的距離無需計算(行7-8)。同理，計算p5時，也減少了兩個用戶的距離計算。最終的結果rst就是p4。

表3優化后的求精過程

3實驗結果

為驗證本文所提算法SFR的有效性，本節在真實城市路網上生成數據集對算法SFR以及文獻[9]所提的算法IPPF從查詢效率和受攻擊率兩個角度進行了對比實驗。兩個算法的區別之一是SFR在生成安全區域時考慮了地圖匹配攻擊，產生的區域可能比算法IPPF要大，但可以減少受攻擊的次數。區別之二是在用戶更新時，SFR考慮了用戶間的隱私泄露問題，并提出了優化的求精算法。

3.1實驗環境

本文使用Oldenburg(德國城市)真實的道路網絡，并基于該路網定義了一些障礙空間(每10條街道產生一個100×100的障礙區域)以及一些包含語義信息的點(每條街道平均產生五個語義點，代表超市、餐廳、商場、醫院等)。假設攻擊者了解地圖的這些信息，當用戶發出一個矩形區域時，攻擊者先根據地圖信息去掉該矩形區域內的障礙空間，再從剩余區域內隨機選擇一個語義點作為攻擊，如果與該用戶的實際位置一致，則認為用戶隱私泄露。

查詢算法的響應時間是衡量算法性能最重要的標準之一。當被查詢數據點的個數、發出查詢的用戶個數以及用戶發送給LSP的位置區域面積這三個因素的規模增大時，算法響應時間的增加速度能夠反映算法的可擴展性。因此，本文實驗中分別考察了這三個因素對查詢算法響應時間的影響，從而驗證算法的可擴展性。對于隱私保護下的查詢算法來說，除了算法的響應時間，其受攻擊率是另外一個重要的衡量標準。顯然，用戶發送給LSP的位置區域面積與受攻擊率之間的關系較為密切，因此，本文在實驗中還考察了該因素對查詢算法受攻擊率的影響。其中數據點個數從5000增加到20 000，20 000是默認值。用戶個數從4到1024以4的倍數增長，默認值是64。位置區域大小則從2002增加到10002，默認值是6002。在研究一種參數對算法效率的影響時，其他參數設置為默認值。每組實驗中，執行100次GNN查詢，再取平均值用來分析。

本文所有算法都使用標準C++在Windows 7操作系統下實現，電腦配置為：Intel Core2 CPU, 2.20 GHz,2 GB內存，500 GB硬盤。

3.2結果分析

圖2列出了被查詢的數據點個數對SFR和IPPF算法響應時間的影響。可以看出，隨著數據點個數的增加，兩個算法的響應時間都有所增加。這是因為被查詢點越多，需要進行的距離計算越多。另外，可能成為用戶組最近鄰結果的對象數目也會增加，從而導致過濾階段得到的候選結果增多，求精階段用戶所需要更新的距離也隨之增加。從圖中還可以看出，SFR查詢效率略微高于IPPF。這是由于SFR算法在求精階段利用保存的全局變量對候選結果進行剪枝，減少了用戶到候選結果之間距離的計算代價，從而提高了整體的查詢效率。

圖2　數據點個數對算法響應時間的影響

圖3給出了兩種算法響應時間隨著同一查詢集合內用戶個數增加的變化趨勢。用戶個數增多，所需的距離計算增多，用戶與LSP交互過程中需要傳輸的數據也增多。另外傳送給LSP的矩形增多，也會使可能成為組最近鄰的候選對象增多，增加了后續剪枝和交互的計算代價，因此兩個算法的響應時間都有所增加。與IPPF相比，SFR算法響應時間增加得比較緩慢，表現出了良好的擴展性。

圖3　用戶個數對算法響應時間的影響

圖4和圖5分別列出了用戶向LSP發送的位置區域的大小對SFR和IPPF算法在查詢響應時間和受攻擊率兩方面的影響。對于算法IPPF來說，橫坐標的值就代表用戶發出的位置區域的邊長；而對SFR來說，由于考慮地圖匹配攻擊，算法會在默認區域的基礎上，通過調整位置或大小來滿足指定的障礙閾值δ，因此一般會比原區域略大一些。從圖4可以看出，隨著區域的增大，兩種算法的響應時間都增加了。主要原因就是區域的增加使得LSP計算的可能成為組最近鄰結果的對象變多，增加了求精階段的計算代價。與IPPF相比，SFR查詢時間的變化較小，這是因為SFR在位置區域默認較小時，考慮到地圖匹配攻擊，也會將大的區域發送給LSP，因此響應時間變化不明顯。

從圖5可以看出，區域的增大，使得IPPF的受攻擊率有所下降。這是因為區域增大，攻擊者能夠猜到用戶真實位置的概率會下降，因此受到攻擊的次數變少。而對SFR來說，受攻擊率并沒有受區域大小的變化有太大的影響，始終都保持在一個較低的受攻擊率，這是由于無論默認的區域是多大，SFR在發送階段都考慮了可能遭受的地圖匹配攻擊，因此能夠一直保持較高的隱私保護能力。

圖4　位置區域大小對算法響應時間的影響

圖5　位置區域大小對算法受攻擊率的影響

4結語

本文基于無TTP模型，提出了隱私保護下的基于三階段的GNN查詢算法SFR。首先用戶向LSP只發送能有效防御地圖匹配攻擊的位置區域來隱藏各自的真實位置信息；其次，基于這些位置區域，LSP利用剪枝策略過濾掉那些不可能成為查詢結果的數據點，快速得到候選集合；最后通過用戶之間的交互，從候選集中查找最終的結果，在交互過程中不僅充分考慮了用戶間的隱私保護問題，還提出了剪枝算法來優化計算過程。基于真實城市路網下的實驗結果表明，SFR與傳統方法相比，有較高的查詢效率和較低的受攻擊率。

參考文獻

[1] Deng K, Sadiq S, Zhou X F, et al. On group nearest neighbor query processing[J].IEEE Transactions on Knowledge and Data Engineering (TKDE), 2012,24(2):295-308.

[2] Chatzimlioudis G, Zeinalipour-Yazti D, Lee W Q, et al. Continuous all k-nearest-neighbor querying in smartphone networks[C]//Proceedings of the 13th International Conference on Mobile Data Management，MDM’12, 2012:79-88.

[3] Shin K G, Ju X, Chen Z, et al. Privacy protection for users of location-based services[J].Wireless Communications,2012,19(1): 30-39.

[4] 朱青, 趙桐, 王珊. 面向查詢服務的數據隱私保護算法[J].計算機學報, 2010,33(8):1315-1323.

[5] 李瑋, 楊庚. 保護隱私性與完整性的低能耗數據融合算法[J].計算機應用,2013,33(9):2505-2510, 2515.

[6] 崔麗群，張明杰.車載網絡中隱私保護方法[J]. 計算機應用, 2013, 33(9):2516-2519, 2524.

[7] Wernke M, Skvortsov P, Durr F, et al. A classification of location privacy attacks and approaches[J].Personal and ubiquitous computing, 2014,18(1):163-175.

[8] Wernke M, Durr F, Rothermel K. PShare: Ensuring location privacy in non-trusted systems through multi-secret sharing[J]. Pervasive and Mobile Computing, 2013,9(3):339-352.

[9] Hashem T, Kulik L, Zhang R. Privacy preserving group nearest neighbor queries[C]//In EDBT, 2010:489-500.

[10] Vu K, Zheng R, Gao J. Efficient algorithms for k-anonymous location privacy in participatory sensing[C]//Proceedings of the 2012 International Conference on INFOCOM, 2012:2399-2407.

[11] Hjaltason G R, Samet H. Distance browsing in spatial databases[J].Acm Transactions on Database System,1999,24(2):265-318.

[12] Beckmann N, Kriegel H P, Schneider R, et al. The R*tree: an efficient and robust access method for points and rectangles[J].Acm Sigmod Record,1990,19(2):322-331.

ON GROUP NEAREST NEIGHBOUR QUERY ALGORITHM FOR PRIVACY-PRESERVING

Liu XiaoleLi Bo

(SchoolofComputer,HenanInstituteofEngineering,Zhengzhou451191,Henan,China)

AbstractExisting private-preserving algorithm for group nearest neighbour (GNN) query ignores map matching attacks. To avoid this problem, we proposed a GNN algorithm for preserving the privacy of users location, which is based on three phases of send-filter-refine (SFR), in the model of no-trusted third party. In sending phase, users send the rectangular regions capable of defending map matching attacks instead of accurate locations to location service provider (LSP). In filtering phase, LSP utilises these regions to calculate all the points possibly being the GNN results and returns them to users. And in refining phase, in order to prevent revealing the privacies among those users initiating queries, the final query result is obtained by unordered interactions between users, and we proposed a couple of pruning strategies to speed up the query. Result of the experiment based on real road network showed that SFR had higher query efficiency and lower rate of being attacked than the traditional algorithm.

KeywordsGroup nearest neighbourPrivacy-preservingLocation service provider

收稿日期：2014-09-02。國家自然科學基金項目(61301232)；河南省科技廳基礎與前沿技術研究計劃項目(142300410131)。劉曉樂，講師，主研領域：計算機應用，網絡信息安全。李博，講師。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.075