基于半可信服務器的位置隱私保護策略

陳 林，沈 航,2，白光偉，牛曉磊

(1.南京工業大學 計算機科學與技術學院，江蘇 南京 211816；2.南京大學 計算機軟件新技術國家重點實驗室，江蘇 南京 210093)

0 引 言

隨著無線通信技術的發展，基于位置的服務開始通過智能手機向用戶提供位置感知服務[1]。為保護用戶隱私不直接被LBS提供商獲取，提出了多種解決方案，其中較多的是通過可信第三方服務器[2]將用戶信息經過加工再發送給LBS提供商。這種方法使LBS無法直接獲取用戶隱私，但是第三方服務器一般是具有計算能力的邊緣節點或其它移動設備，容易被攻擊者攻擊，造成用戶隱私泄露。對此相關研究人員提出了許多隱藏位置的技術。Pahins和Stephens將這些隱藏真實位置信息的技術分為匿名和混淆[3]。雖然用戶在與第三方服務器共享數據之前，通過匿名方法呈現數據來保護隱私，但是，攻擊者可以通過背景知識，從假數據中推斷用戶的真實信息[4,5]。在混淆領域，信息在發送給第三方服務器前，真實位置被假的位置所取代。基于差分隱私的噪聲是混淆領域中的主流技術[5,6]，該方法大多是將隨機噪聲用于混淆用戶的真實位置[7,8]。然而，隨機噪聲具有一定的概率分布，攻擊者使用統計方法推斷出真實位置。

本文提出基于半可信服務器的隱私保護方法，該方法中，用戶將信息發送給半可信服務器之前，對其真實位置進行擾動。與傳統的噪聲擾動不同，該方法通過使用隨機函數來進行擾動，使得攻擊者無法通過傳統推測獲得真實數據。用戶在將擾動后的請求發送給服務器后，服務器采用基于時間混淆的k匿名機制后發送給LBS。實驗結果表明，本文提出的混淆算法能防止用戶被半可信服務器攻擊推測，減小了LBS成功重構用戶軌跡的概率。

1 相關工作

近年來，針對第三方服務器和LBS服務器可能會帶來的隱私泄露問題，相關研究人員提出了多種解決方案。

大多的解決方法是通過混淆技術向第三方服務器發送不準確的位置來保護位置隱私。這個技術可以分為兩類：基于差分隱私(differential privacy)的噪聲和基于網格的方法。前者是通過在發送給第三方服務器前將隨機噪聲添加到準確數據來實現保護位置隱私。在現有的工作中，添加的噪聲大都呈現高斯分布。攻擊者可以通過最小二乘法來推斷分布函數的類型，并且可以通過諸如最大似然估計的統計方法來獲得參數。當獲得分布函數時，攻擊者可以通過統計方法推斷出真實位置。在基于網格的方法中，地圖被視為網格。并且一個網格中的所有位置將被相同的點(例如地標或其它重要位置)替換[9,10]。基于網格的方法的缺點之一是位置精度低，會導致基于位置的服務質量低下。最近，Embed sensors[11]和趙大鵬等[12]引入了一些新方法，但是這些技術不適用于基于第三方服務器中的位置數據。

匿名技術也已被廣泛用于保護用戶位置隱私，基于匿名方法的基本思想是在使用基于位置的服務時使用假數據。但是，攻擊者可以推斷出用戶的特征位置(如家庭，學校和公司)，然后從匿名數據中獲取用戶的身份[13]。k-anonymity模型是另一種被廣泛使用的技術，其關鍵是從真實請求中增加一些假的信息請求，使得每個信息請求在其它k-1請求中無法區分。現在最新的概念是一種基于坐標變換的k匿名位置隱私保護方法，用戶請求位置服務時，向匿名服務器發送經過變換后的坐標，匿名服務器可以在不知道用戶真實坐標的情況下形成匿名區域[14]。文獻[15]采用了真實位置信息，將一個區域偽裝成一個可以輕易識別實際用戶位置的小區域，以此解決k匿名中的區域問題。趙逢達等[16]提出了一種基于Unit的新路網模型，采用希爾伯特編碼對匿名區域進行排序。這些通過匿名區域向第三方服務器發送請求，一定程度上保護了用戶的隱私，但是也造成了位置精度的損失，無法兼顧用戶的高服務質量需求。

針對第三方服務器向LBS請求連續查詢，Hok等[17]設計了隱藏用戶軌跡的路徑混淆技術，而不是簡單地隱藏用戶身份。文獻[18]使用(k-1)歷史軌跡來滿足基于軌跡的k匿名范式。由于軌跡被分解為一系列足跡，所提出的KAT技術隱藏了k軌跡上的足跡，包括服務用戶軌跡，但是當用戶在移動時，如果該路徑上沒有其他用戶，則LBS仍然可以輕松識別用戶的實際位置。雖然用戶軌跡受k匿名保護，但這項工作并未考慮可能引起隱私問題的環境條件。文獻[19]通過考慮許多因素(例如，混合區幾何，用戶群和用戶的移動模式)來提高道路網絡的攻擊彈性。林玉香等在文獻[20]中提出了一種通過路段間最短距離計算尋找匿名用戶的方法，解決了連續查詢環境下用戶匿名的問題，盡管這些工作都在匿名方面保護了用戶位置不能被直接推測，但是它們都沒有考慮時間因素，LBS仍然可以根據所有觀察到的時間上相鄰的查詢推測可能的軌跡。

針對上述混淆和匿名中產生的問題，本文提出了一種基于半可信服務器的隱私保護方法。該方法使用了隨機函數擾動和時間混淆的技術，這可以有效防止半可信服務器和LBS服務器通過傳統的攻擊手段推測出用戶真實位置。

2 系統模型

本節將對提出的基于隨機函數混淆和時間擾動k匿名的隱私保護方案做具體說明。方便閱讀，將相關符號定義歸納為表1。

表1 相關符號及其意義

提出的保護機制使用的系統框架如圖1所示，該框架由移動終端、半可信服務器、LBS服務器組成。

如圖1給出的經過擾動再k匿名的信息查詢框架，其中的符號含義歸納如下：

(1) (O1∈O)：u1表示原始用戶的個人身份，(x,y)即是用戶的真實位置，表示用戶的坐標，s1為用戶的隱私語義(如可到達的地點，要購買的商品等)集合，O1為用戶位置和秘密的笛卡爾積列表。

(2) (O′1)：x′表示用戶真實位置的經度x在滿足用戶服務質量的前提下，經過隨機擾動函數變換后的假經度位置，同樣y′也是經過函數擾動后的假緯度位置，用戶的語義在變換過程中保持不變。

(3) (O′1,O2,…Ok)(Q)：Q表示半可信服務器在對用戶上傳的信息進行k匿名后發送給LBS服務器的k個請求，其中k匿名中使用了時間擾動方法。

圖1 基于半可信服務器的系統架構

本文運用傳統的方法對噪聲擾動進行推測攻擊，以此來評估用戶的隱私水平。如圖2所示，傳統的推測攻擊通過輸入和大量的輸出結果來推測出概率密度函數h() 和h(θ)， 通過密度函數、輸出的大量結果(x′,y′) 和已知的n，能夠推測出真實位置(x*,y*)。 (x*,y*) 和 (x,y) 的距離被用來量化推測誤差，具體推斷過程2.1節所示。

圖2 傳統噪聲攻擊推測

2.1 推測函數

將經過擾動函數f(x,y) 擾動后的位置用(x′,y′) 表示，則

(1)

(2)

(3)

P(x)=P0+P1·x+P2·x2+…+Pm-2·xm-2

(4)

我們通過以下規則產生最優多項式P(x)

P(A1)-F(A1)=+ε
P(A2)-F(A2)=-ε
……
P(Am)-F(Am)=±ε

(5)

將上述等式展開，有

(6)

(3)在得到概率密度函數h() 和h(θ) 后，能夠計算出用戶的精確定位，過程如下

(7)

(8)

(9)

因為D((x,y),(x′,y′))≤α， 得到∈[α,+α],θ∈[α,+α]。

概率密度函數用于定義隨機變量落入特定值范圍內的概率。因此，h(ai) 指定落入接近ai的特定值范圍內的概率。并且上述分析適用于bi,h(bi)。 因此，*和θ*可以被視為用于混淆真實數據的最高可能性的點。所以，使用 (x′-*,y′-θ*) 來近似精確位置 (x,y)。

在本文設計的混淆算法中，每個用戶都有一組函數，可以隨機選擇這些函數來混淆準確的位置。因此，使用 Remez 算法或通過統計方法無法獲得近似的混淆函數。所以，與傳統的基于差分隱私噪聲的工作相比，本文的隱私保護算法在隱私保護方面實現了更好的效果。

2.2 時間混淆

隨著傳統的快照查詢逐漸被連續查詢取代，即使在k匿名的情況下，LBS服務器也能根據連續請求或最大移動速度推斷出用戶的真實軌跡，因此本文采取了基于時間擾動的k匿名，提高用戶隱私水平，相關定義如下：

定義1 移動軌跡：T={lt1,lt2,…,ltn}，ltj是指在T軌跡上tj時刻的位置。

定義中的軌跡由用戶的一組位置組成，這些位置是由GPS設備跟蹤定位的。為了實現時間混淆，查詢處理器隨機選擇T上的一個ltj， 在一個隨機時間tj發出一個點查詢。換句話說，查詢處理器不會定期從順序位置發出查詢。

定義2 查詢內容m，m=(uid,ltj,k,s)， 其中uid是查詢用戶的id，ltj是指在T軌跡上tj時刻的位置，k表示k匿名，最后s是用戶查詢的語義內容。

定義查詢信息m，在m發送給LBS之前，半可信服務器通過修改uid為pid，ltj改為ctj將m擾動為查詢信息m*。

通過在半可信服務器上設置基于時間擾動的k匿名混淆方法，能有效減小LBS服務器通過連續查詢排除虛假信息，重構用戶移動軌跡的概率，提高隱私水平。

3 隱私保護策略

本節對用戶的隱私需求進行分析。通過在使用半可信服務器前，對用戶的真實位置提出了位置模糊算法。在滿足用戶服務質量的前提下，設計了生成α擾動函數算法，通過算法分析了用戶的需求和模糊策略。在半可信服務器中，本節使用了時間混淆的k匿名并對該算法進行了分析。

3.1 位置模糊算法

在實現用戶位置的隨機擾動上，通過混淆函數來生成模糊位置，提供了一種可以產生混淆函數的算法，模糊功能應該滿足以下要求：

(1)準確位置與由函數生成的假位置之間的歐幾里德距離應該是有界的。

(2)對于R中的任何實際位置，模糊位置應滿足(1)。

引入第一個要求的原因是，服務質量是由基于位置服務中的位置準確性決定的，在對用戶位置進行模糊的同時也考慮到服務質量的缺失。第二個要求即是設計的混淆函數算法應該具有普遍適用性，即滿足一切實際位置的服務質量要求。

令 (x,y) 是實際位置， (x′,y′) 是由函數f(x,y) 生成的混淆的位置。 (x,y) 和 (x′,y′) 之間的歐幾里德距離如下

(10)

D′表示所有真實位置及混淆后的位置之間的最大歐幾里德距離有

(11)

實現上述兩個要求的函數的定義如下：

定義3f(x,y) 是一個α擾動函數,考慮到用戶需要滿足自己的服務質量的情況下，擾動位置的范圍不能過大，所以設置參數α來限制D′。α是一個由用戶確定，代表了基于位置服務的數據精度要求的常數。即D′≤α。

許多函數在封閉區間內有界，如多項式函數、三角函數、指數函數和它們的復合函數等，可以用來構造R中有界的函數。然后通過設置合適的系數可以生成α擾動函數。據此本文提出了一個模糊算法生成α擾動函數。

算法1： 生成α擾動函數

(1)Input：α,A←{g(x)|?c,T∈R,?x∈[0,T],|g(x)|≤c}

(2)Output：f(x,y)

(3) 從函數集A中隨機選擇兩個函數g1(x),g2(x)

(4)While|g1(x)|≤c1and|g2(x)|≤c2

(6)f(x,y)←(xf,yf)

(8)endwhile

(9)returnf(x,y)

定理1 由算法1生成的函數是α擾動函數

因為任意x∈[0,T1] 和y∈[0,T2]， 都存在 |g1(x)|≤c1,|g2(y)|≤c2， 所以D((x,y)(xf,yf))≤

根據定理1，算法1生成的函數滿足模糊功能的要求。

3.2 需求和模糊策略

雖然每個用戶都可以從算法1獲得特殊的混淆功能，但用戶的位置隱私尚未保留。攻擊者可以收集用戶的蹤跡，然后通過2.1節的推測方法推斷混淆函數，泄露用戶的準確位置。本文指出，良好的隱私保護策略應該具有以下2個屬性：

(1)當位置被混淆時，應該限制服務質量的損失，即最大化服務質量

(12)

(2)不應通過隨機或近似方法從混淆數據推斷出準確的位置

(13)

本節提出一種實用的混淆策略，稱為隨機函數混淆策略，該策略具有上述2個屬性。策略的關鍵思想是在使用基于位置的服務時隨機選擇混淆函數。具體的步驟如下：

步驟1 為每個用戶生成α混淆函數集RF，其中α由用戶給出，本文的用戶服務質量用真實位置與混淆后位置的歐幾里得距離來衡量，即

(14)

步驟2 用戶當需要對準確的位置進行模糊處理時，從RF中隨機選擇一個函數，其中 (x*,y*) 表示推測的用戶位置

(15)

該策略通過應用混淆函數滿足要求。由于處理用戶真實位置的函數是不確定的并且隨著時間變化，用戶的可選函數集也發生變化，因此通過統計大量輸入輸出信息，運用2.1節提出的傳統推測函數方法，推斷到的函數信息是單一的，不能推測得到具體幾個函數和函數的具體形式，充分保護的用戶隱私。

3.3 時間混淆算法

半可信服務器采用以下隱私保護機制：在用戶開始行進之前，服務器根據用戶的當前位置和他們的目的地來從數據庫中選擇具有相關的歷史軌跡作為預測軌跡，如果沒有即歷史數據不存在，則使用基于Dijkstra算法來生成最短路徑軌跡。當用戶在預測的軌跡上行進時，半可信服務器通過k匿名發送k個請求，并在這些請求中使用時間混淆技術，即在不同時段發送下一刻的查詢請求以混淆LBS。具體的算法分析如算法2所示。

算法2： 時間混淆算法

(1)Input： (k,Tu)

(2)Output:QueryCell

(3) if (issueQuery(Tu)) 存在，則

(4)locu=getCur(Tu),UserQueryCell←getCellId(lu)

(5) /*否則隨機從Tu發送查詢*/

(6) if (RanIssueQuery(Tu)) 存在， 則

(7)UserQueryCell=getRandomCellId(Tu)

(8) /*發送查詢*/

(9)for(j=0ToMAX_QUERY_NUM)

(10)if (queryIndex==j)則

(11)QueryCell=UserQueryCell

(12) else

(13)QueryCell=getRandomCellId(r-Trajectory)

(14)Endfor

算法2中輸入包括兩個用戶隱私配置文件值k和用戶軌跡Tu。 當用戶開始朝目的地行走時，半可信服務器采用時間模糊技術隨機發送包括查詢時間的查詢，在該查詢時間用戶不發出查詢。執行此方法直到用戶到達他/她的目的地。第(2)-(4)行檢查用戶在當時是否發出查詢。如果是肯定的，則獲取用戶當前占用空間所在的查詢單元。否則，在第(5)-(7)行中，系統決定是否以及在何處從Tu發出查詢。

4 性能分析

為了驗證提出的位置隱私保護方案的性能，根據提出的方法，設計了一系列仿真實驗。實驗的軟硬件環境為Intel Core i5-2450M CPU，2.50 GHz，內存為8 GB，Windows 10 64位操作系統，開發工具為Visual Studio 2015和Matlab R2016a。

本節對提出的方案進行評估，比較在使用半可信服務器的情況下，傳統算法和本文的隨機函數擾動算法(RF)帶來的用戶服務質量的差別和隱私保護的效果的不同。通過合成數據集的技術現狀，報告了各種參數設置條件下的結果質量。同時，針對用戶的連續查詢，比較了在半可信服務器下傳統的k匿名和基于時間擾動的k匿名所帶來的保護效果的差別。

在對比實驗中，使用最常用的基于位置的服務算法，在精確的位置上加入高斯和均勻噪聲。

4.1 服務質量比較

為了研究不同混淆算法的服務質量，在圖3中，通過精確路徑和模糊位置之間的距離來測量結果。因為在大多數基于位置的服務中，高精確度實現了高服務質量，從圖3(a)和圖3(b)可以看出，與高斯和均勻方法相比，RF生成的模糊數據更接近真實路徑，服務質量更高。因為相比較傳統的高斯噪聲擾動和均勻噪聲擾動，本文提出的隨機函數擾動是在保證用戶服務質量的基礎上設計的，即限制了真實位置和假位置之間的距離，實現高質量服務。

圖3 比較3種不同的基于噪聲的方法

4.2 誤差推斷

為了研究3種技術在隱私保護方面的能力，本文使用傳統的推測方法從模糊的位置計算出近似路徑。在圖4中，通過隨機函數擾動算法生成的精確數據與推測位置之間的距離來衡量位置隱私，距離越大，隱私保護效果越好。

圖4 推測路徑對比實際路徑

本節實現了3種模糊方法的比較，觀察到除RF外，其它兩個方法被推測到的模糊路徑與實際路徑非常接近。也就是說，攻擊者可以通過高斯和均勻方法生成的數據中推測到接近真實位置的路徑。而在圖4(a)和圖4(b)中，RF生成的路徑是不規則的。因此，攻擊者很難收集到任何有用的信息來推斷真實的路徑。這是因為我們的隨機函數擾動算法(RF)是通過從一個函數集中，隨機選擇函數來對真實位置進行擾動，攻擊者無法通過傳統的輸入輸出來進行真實函數的推測。

在都使用R2函數集的情況下，對比圖4(a)和圖4(b)，當α值越大時，假位置與真實位置之間的距離越大，攻擊者推測的路徑也更加模糊。

4.3 隱私水平比較

本小節比較了3種隱私方法：①RFKT(隨機擾動下的時間混淆k匿名)；②RFK(隨機擾動下的傳統k匿名)；③RF(只進行隨機擾動)。為更好判斷隱私效果，本節采用同一個函數集R3進行比較，在圖5(a)中k=5，圖5(b)中k=10。

圖5 3種方法的隱私水平

可以看到在圖5(a)、圖5(b)中，本文提出的在半可信匿名服務器中使用基于時間混淆的k匿名(RFKT)獲得的隱私水平最高且隨著α的增大，真實位置與假位置之間的距離增大，用戶的隱私水平也上升。盡管基于基本k匿名(RFK)方法滿足k-anonymity范式，但是它不考慮查詢發布時間因素，因此，根據連續查詢，攻擊者可以排除掉一些虛假的軌跡信息，重構半可信服務器中用戶的真實軌跡。所以基于時間混淆的k匿名隱私水平比傳統的k匿名高。相比較RFK，不基于半可信服務器，只是通過用戶隨機擾動方法，取得的隱私水平更低，這種情況下，用戶與LBS直接通信，將個人信息展現給攻擊者，缺少了第三方服務器的k匿名包裝，攻擊推測用戶的真實信息會變得更直接，用戶的隱私水平也會最低。

在都使用同一個混淆方法的情況下，從圖5(a)和圖5(b)中可以得到，k匿名中的k值越大，隱私水平越高。其中，對比其它兩個方法，本文提出的方法隨著k變大，隱私水平變化最大，表明了我們的基于半可信服務器的時間混淆方法在連續查詢上提供了更好的隱私保護效果。

5 結束語

本文在解決第三方服務器容易引發隱私泄露問題中，提出了一種基于半可信服務器的隱私保護方法，在該方法中設計了隨機函數擾動算法和時間混淆的k匿名機制。用戶將請求發送給半可信服務器前，在保證服務質量基礎上，隨機選擇混淆函數對真實位置進行擾動，再通過半可信服務器使用基于時間混淆的k匿名。結果表明，該方法能有效地防止攻擊者通過傳統的信息統計和連續查詢，推測用戶的真實位置，實現了很好的隱私保護效果。

但是，在對服務質量要求更高的今天，如何平衡位置擾動后的隱私效果和質量需求，減小服務器處理的時延消耗依舊是個很大的挑戰，也是下一步我們的研究工作。