啞元位置隱私博弈機制

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

1(南京工業大學 計算機科學與技術學院,南京 211816)

2(南京大學 計算機軟件新技術國家重點實驗室,南京 210093)

E-mail:niuxiaolei@njtech.edu.cn

1 引 言

基于位置的服務(Location-based Service,LBS)給人們的生活帶來了極大的便利[1],但用戶在享受LBS帶來便捷服務的同時,隱私信息也存在著泄露的風險.在獲取服務的同時需要將用戶當前的位置信息提供給LBS服務器.LBS服務器獲取到用戶的各種位置信息,如果這些信息被第三方獲取,分析并加以利用,將會對用戶造成難以估計的損失.因此如何能在保證服務的同時,對用戶的隱私信息加以保護是十分重要的.

目前,很多隱私保護方案采用k匿名模型,一種是由匿名服務器[2,3]產生一個包含用戶真實位置與其余k-1個用戶位置的匿名區域,攻擊者從這k個用戶中推測出真實用戶的概率為1/k;另一種不依賴可信第三方的方案[4,5]是由移動設備產生k-1個啞元(dummy),將真實用戶位置混入其中構成匿名集發送給LBS.由于k匿名沒有考慮匿名區域內的語義信息.假設匿名區域正處于某醫院的范圍內,那么攻擊者可能推測出用戶可能是患有某種疾病或者是醫院的工作人員,攻擊者根據用戶的一些背景信息,比如某用戶經常在上下班時間出入醫院,那么這個用戶是工作人員的概率便會增大.基于模糊和泛化的用戶隱私保護也是一種常見的方法,基于模糊的位置保護方法[6-8]在用戶向LBS發起查詢請求時,通過提交非精確位置來避免信息泄露,采用的技術主要有位置偏移、位置擴張等.位置偏移指的是在用戶真實位置周圍,通過某種方法,尋找啞元來代替用戶發起位置請求;位置擴張是將用戶的真實位置擴大為一個匿名區域,然后通過加入噪聲來降低位置精度,提高推測難度.

上述方法大多忽略了攻擊者對于用戶背景知識的掌握.通過對用戶背景知識進行分析,攻擊者可以篩選掉一些用戶進而提高自己的隱私推測能力.本文提出啞元位置隱私博弈機制,該機制可以在滿足服務質量的前提下保證用戶的位置隱私,為用戶提供更好的位置服務.用戶的真實位置經改進的坐標轉換方法生成啞元,替代用戶的真實位置與其余k-1用戶位置構成匿名區域發送給LBS.考慮到掌握用戶背景知識的攻擊者可以利用匿名區域內所有用戶的數據進行更深層次的挖掘分析,并根據用戶策略來調整攻擊策略.用戶在覺察到自己的隱私信息受到威脅后調整保護策略以抵抗攻擊者的攻擊,用戶與攻擊者之間展開博弈,在隱私水平與效用代價之間找一個最佳的平衡點.本文在位置暴露概率、隱私水平和位置熵等方面進行實驗分析,證明本機制在損失一定程度的服務質量換取了更好的隱私保護效果.

本文各個章節的安排如下,第2節主要介紹常見的位置隱私保護算法;第3節提出啞元位置隱私博弈機制;第4節主要介紹實驗的設計以及相關實驗結果;第5節對文章進行總結.

2 相關工作

近年來,基于扭曲法的LBS隱私保護技術受到了研究者的關注.它是對LBS查詢中用戶的原始數據進行必要的擾動,以避免攻擊者獲得用戶的真實信息數據,同時保證不影響用戶獲得LBS服務.采用的技術主要有假名(刪除或者用一個臨時標志來替代用戶)、隨機化(添加啞元)、模糊化(泛化用戶查詢過程中的時空信息)和隱蔽化(隱蔽用戶的整個查詢).在文獻[9]中將LBS查詢中的用戶位置用一個臨時的假名代替以打破用戶身份與查詢之間的聯系.但僅僅采用假名并不能充分保護查詢隱私,為了增強假名的有效性,文獻[10]結合了一些復雜的加密方法與假名技術配合使用來保護用戶隱私.隨機化指在LBS查詢中加入隨機啞元,并將啞元和真實查詢一起發送給LBS提供商.考慮到隨意的隨機化并不能很好的保護隱私獻,文獻[11]在使用隨機化技術的同時,考慮了普適、擁擠、均勻等指標和與用戶真實移動模式相近的啞元位置,使其看起來更為真實.但是由啞元位置組成的數據中可能與真實數據有很大的差別,甚至產生一些無效的位置(如在湖中),很容易被攻擊者識別.在文獻[12]中提交給LBS服務器的是一個包含k個位置的匿名區域而非精確的位置,服務器需要在該區域選擇參考位置來得到準確的結果,這無疑增加了服務器的負載、響應時間等,降低了服務質量,需要在隱私與服務質量之間進行權衡.文獻[13]中提出隱蔽化的方法,擁有一些具體信息的用戶可以將這些信息傳遞給附近用戶,用戶請求不是向LBS發起查詢,而是由附近的用戶來請求查詢信息,實現對LBS隱蔽查詢.

在匿名隱私保護算法的研究中,信息熵作為信息度量的有效工具,廣泛用于位置隱私保護領域.Chen等[14]人針對LBS查詢隱私進行了度量,將隨機變量的概率表現為攻擊者在無背景知識和有背景知識兩種情況下判斷用戶的真實位置,并使用互信息量來度量隱私水平.文獻[15,16]也均采用信息熵來度量LBS系統的隱私水平.Peng等[17]人基于Shannon信息論提出來幾種隱私保護信息熵模型,并且初步考慮了含隱私信息主觀感受的信息熵模型.

以上方法對攻擊者可能掌握用戶的背景知識研究有些許不足,攻擊者利用收集到的數據對用戶的位置信息進行推測分析,進而可以排除某些用戶.Shokri[18]提出了基于Stackelberg博弈的保護策略,該策略假設攻擊者掌握用戶的背景知識,讓用戶與攻擊者輪流進行博弈.用戶在確保服務質量損失小于給定閾值的情況下最大化隱私保護水平,而攻擊者根據先驗知識和偏移位置保證最小化隱私保護水平.通過博弈,該策略可以在最優化隱私保護水平的同時確保服務質量損失小于給定閾值,最后通過解最優化問題,得到用戶的最優位置隱私保護策略和攻擊者的最優攻擊策略.

基于扭曲法的隱私保護技術可以在服務質量與隱私保護上取得較好的平衡,但容易受到掌握用戶背景知識攻擊者的隱私攻擊.基于Stackelberg博弈的保護策略采用不依賴可信第三方的系統結構,但是受移動設備性能的限制且無法獲取用戶全局信息(如所有用戶的歷史服務請求分布).針對上述問題,本文采用基于第三方服務器的隱私保護系統結構,并在此基礎上設計啞元位置隱私博弈機制,在用戶發起請求時將自己真實位置信息轉換為啞元位置后,才發送給匿名服務器,即使第三方服務器被攻陷,攻擊者也只能獲得用戶的啞元位置,對自己的真實位置進行了隱藏.

3 啞元的位置隱私博弈機制

在本節中,首先簡單介紹本機制的隱私保護結構,然后對于位置隱私保護中的一些度量進行介紹,然后介紹位置隱私攻擊算法,最后介紹用戶的最佳保護策略、攻擊者的最佳攻擊者策略以及它們之間的最佳平衡問題.

本文采用基于第三方服務器的隱私保護結構,如圖1所示,主要由以下3個部分組成:

·用戶:需要LBS服務時發起位置服務請求,并將真實位置信息轉換為啞元.

·位置匿名服務器(Location Anonymization Server,LAS):負責將用戶的啞元位置轉換為匿名區域,并在LBS提供商返回查詢結果后,返回對應的服務結果.

·LBS提供商(Location Based Service Provider,LBSP):負責根據位置查詢請求,返回對應的查詢結果.

圖1 基于第三方服務器的隱私保護結構

3.1 隱私度量

定義1.位置暴露概率P.表示匿名區域內啞元被攻擊者成功預測的概率,如公式(1)所示:

(1)

其中,k為匿名區域的用戶數,k′表示攻擊者根據用戶背景信息可以過濾掉的用戶數.攻擊者過濾掉的用戶數量越多,P越小,真實用戶暴露出來的概率越大,真實用戶被推測出來的概率越大.由公式(1)可知,0≤P≤1.

(2)

定義3.服務質量損失Qloss.表示真實用戶ui與匿名區域o內所有用戶之間距離的數學期望,如公式(3)所示:

(3)

(4)

結合公式(4),可得:

(5)

(6)

(7)

證明:由公式(7)可知:

(8)

3.2 位置隱私攻擊算法

攻擊者掌握的用戶的背景信息包括用戶所在地域的實際環境、用戶的移動模式及其用戶的歷史查詢請求等,攻擊者可以利用這些信息來對用戶進行推測分析,可以更加準確的推測出用戶的真實位置.

假設P(B|A)表示在B事件發生情況下A事件發生的概率,那貝葉斯法則可表示為：

(9)

(10)

攻擊者可以在貝葉斯攻擊的過程中根據自己掌握的用戶背景信息對用戶的位置信息進行更為準確的推測.

(11)

其中Z表示攻擊者掌握的用戶背景知識(用戶所在區域真實環境、用戶的移動模式等).

對掌握用戶背景知識與無用戶背景知識的攻擊者的攻擊能力進行比較,如公式(12)所示.

(12)

用戶掌握自己的背景知識,因此用戶的保護策略在有背景知識的情況下選擇對自己最佳的匿名區域,則A≥C.相反地,掌握用戶背景知識的攻擊者會選擇最佳的攻擊策略,所以B≤D,因此

(13)

3.3 最佳攻擊策略

(14)

其中,q是攻擊者針對常見的位置隱私方法結合用戶的背景知識進行的推斷.

3.4 用戶的最佳保護策略

啞元位置隱私博弈機制主要分為啞元的生成與匿名區域的構建過程和Stackelberg博弈優化過程.用戶的真實位置轉換為啞元,將該啞元與其余k-1個用戶位置組成匿名區域后,才將匿名區域發送給服務器.LBS服務器接受到匿名區域后,將相應的應答反饋給用戶終端,終端接收到反饋之后會從其中找到自己需要的隱私信息.掌握用戶背景知識的攻擊者可以根據自己掌握的背景知識對用戶進行隱私攻擊,用戶在覺察到自己的位置信息受到威脅后,適當擴大匿名區域來與攻擊者展開博弈.

3.4.1 啞元生成與匿名區域構建

啞元替代用戶真實位置參與匿名區域的構建.攻擊者想要推測出用戶的真實位置,不僅需要推測啞元,還需要推測出坐標轉換參數,由于坐標轉換參數是由用戶的個人終端隨機產生,只有用戶才能反向計算出用戶真實位置,提高了保護隱私的能力.然而攻擊者可以根據掌握的用戶的背景知識推測出坐標轉換方法的參數,然后對用戶的位置信息進行推測.在本節中,首先是將用戶的真實位置經坐標轉換方法轉換為啞元,然后將啞元與其余k-1個用戶位置經k匿名處理構建匿名區域后,才發送給LBS服務器.

Li等[19]引入了一種坐標轉換機制對用戶真實位置進行處理.從用戶的角度來看坐標轉換,圖2(a)中正方形的4個頂點都有可能成為u′(x′,y′),用戶只有4個可選擇的位置點.如果用戶身處環境較差此方法效果較差甚至失效,比如對用戶的真實位置進行坐標轉換后的位置處于湖中,那么這個位置肯定是無效的.從攻擊者的角度來看坐標轉換,u′(x′,y′)是經坐標轉換公式轉換后的啞元,在圖2(b)中位于圓邊界上的是用戶真實位置轉換后的位置u′(x′,y′),其實線圓內任一位置點都可能是用戶的真實位置.掌握用戶背景知識的攻擊者可以根據用戶的移動模式等信息對用戶進行分析,可以更為準確的推測出用戶的真實位置.

圖2 坐標轉換方法

傳統的坐標轉換方法中用戶的真實位置經坐標轉換后的位置點有4個,然而這4個位置點中可能是無效的.在此基礎上,本文分別從用戶的角度和攻擊者的角度對傳統的坐標轉換方法進行改進.1)從用戶的角度來看,增加一個坐標轉換參數λ,使得攻擊者更加難以推測出坐標轉換參數,推測出用戶真實位置概率降低,所需要的代價提高.從圖2(a)中可以看出,改進后的算法使得用戶經坐標轉換后的位置點變得更為復雜,出傳統算法中的4個位置點外,矩形的兩條對角線均可選擇;2)從攻擊者的角度來看,攻擊者對坐標轉換的推測具有概率性,由圖2(b)可以看出,如果攻擊者對于λ的值進行了錯誤的估計,那么對于攻擊者而言者更為致命.

改進后的坐標轉換公式如公式(15)所示.

(15)

其中x,y分別代表用戶的真實位置橫縱坐標,x′,y′分別代表轉換后的橫縱坐標.α、b和λ是個人終端隨機產生的坐標轉換參數,其中0<λ≤1,λ是隨機生成的.當用戶接收到LAS的查詢結果后,可以由其坐標逆轉換公式得到用戶的真實位置,其坐標逆轉換公式為:

(16)

從用戶的角度出發,圖2(a)中除4個頂點外,正方形區域的兩條對角線都可能成為u′(x′,y′),極大提高了用戶的可選擇性,用戶可以選擇更好位置點來替代用戶的真實位置.在保證LBS服務質量的同時,保護自己的位置隱私.從攻擊者的角度來看坐標轉換,攻擊者對于坐標轉換參數的推測是有概率的.如果攻擊者對于λ的值進行了錯誤估計,那么會對攻擊者的攻擊造成更大的阻礙.如圖2(b)所示,真實坐標轉換參數λ值為1,然而攻擊者錯誤的將其預測為0.5(虛線圓),恰好其真實用戶u(x,y)位于虛線圓外側,那么攻擊者則永遠不會推測出用戶的真實位置.只要知道α、λ、b參數,攻擊者就可以得到用戶的真實坐標,因此對于用戶來說,想要真實位置不被發現,其經過坐標轉換后的啞元也要盡量保證不被攻擊者獲知,若攻擊者多次推測出用戶經過坐標轉換后的位置,那么攻擊者也更容易推測出坐標轉換參數.

用戶的真實位置在經改進的坐標轉換方法轉換為啞元之后,與其余k-1 個用戶位置構成匿名區域被發送給LBS服務器,此過程中匿名區域內必須包含用戶的真實位置,但是實際上用戶真實位置并不參與匿名.在用戶第一次發起查詢并且構成匿名區域時,匿名區域恰好將用戶真實位置包含在內即可,此時用戶的真實位置處于匿名區域的邊界.當攻擊者準確預測出坐標轉換后的位置后,那么攻擊者只需要推測位于邊界的用戶位置即可.盡管這樣也可以保護用戶的位置隱私,但是本文的目的是盡量提高用戶的隱私水平,即當用戶的隱私信息可能被攻擊者推測的情況下,允許適當增大匿名區域.

3.4.2 最佳匿名區域隱私保護策略

用戶的真實位置ui被泛化為匿名區域o,攻擊者觀測到o且了解用戶的隱私保護方法和用戶的概率分布函數Ω.攻擊者可以得到后驗分布,如公式(17)所示.

(17)

(18)

為了表述方便,用x對公式(18)進行了相應的簡化,x的定義如公式(19)所示.

(19)

因此,SPMD是尋找最優匿名區域o的過程,如公式(20)所示.

(20)

該公式的含義是,在所有的攻擊者策略中,找到一個匿名區域o,使得用戶的收益最大化.因此可將公式(19)變為一個約束條件,如公式(21)所示.

(21)

綜上所述,可以得出用戶的最佳保護策略如公式(22)所示.

(22)

Subject to

(23)

(24)

其中,公式(23)用來讓用戶收益最大化;公式(24)用來限制最大可容忍位置服務質量損失.

用戶的最大隱私期望就是在公式(22)中的約束條件下對目標函數進行求解,得到最優的匿名區域,在滿足服務質量的條件下讓隱私水平最大化.

3.5 最佳平衡點搜索

如圖3所示,a表示用戶的真實位置,a′表示其t+1時刻的位置,實線圓表示用戶匿名區域,虛線圓為其圓心用戶最大移動范圍.在t+1時刻,b′為a′在t+1時刻經過坐標轉換后的位置,此時a′與以b′為圓心的圓相切(實線),b′出現在b用戶的最大移動范圍之外,而e用戶也不可能參與t+1時刻的匿名過程(不在其最大移動范圍內),因此攻擊者可以排除掉b用戶與e用戶,用戶位置暴露概率由原來的1/4增加到1/2,保護能力下降.如果我們適當擴大其隱匿范圍(虛線)與e用戶最大移動范圍重疊,此時攻擊者不能將e用戶排除,用戶位置暴露概率增加到1/3(假設c、d一直在其匿名區域且不能被攻擊者排除),提高了用戶的隱私保護水平.

圖3 用戶與攻擊者博弈過程

(25)

其中Amax、Amin表示用戶的最大匿名區域和最小匿名區域,這兩個區域可以由用戶自行設定.當攻擊者的攻擊能力大時,用戶的匿名區域半徑增大幅度較大.反之,當攻擊者的攻擊能力小時,用戶的匿名區域半徑增大幅度較小.盡管用戶的隱私得到保護,但是代價也隨之增大,因此我們要在隱私與代價之間找到一個平衡點,在最小化代價的同時,保證服務質量.假如用戶位置暴露概率至少為70%,在經過攻擊者隱私攻擊之后,如果隱私水平低于70%,那么用戶會適當擴大自己的匿名范圍,直到滿足70%.

4 實驗分析

4.1 實驗設計

本實驗主要采用matlab工具實現.實驗使用滴滴打車的訂單數據(1)http://research.xiaojukeji.com/competition/detail.actioncompetitionId=DiTech2016(由滴滴大數據比賽發布)進行算法驗證.數據集中給出了M市2016年連續三周的900萬條數據信息:訂單數據包括訂單ID、區域ID、司機ID、乘客ID,價格以及訂單時間,還有一些天氣、POI和路況信息.

圖4 最大服務質量損失與服務質量損失、隱私水平對比

本文設定隱私需求k、生成的匿名區域為圓形,其面積是160 000 m2,之后將面積劃分網格形式,網格中的每個單元格都代表位置,單元格的大小與位置粒度有關.假設在任意時間點都可以發布位置服務請求,該請求過程可以看作是泊松過程.為了驗證機制的有效性,首先采用DLPG與標準的Stackelberg博弈隱私保護算法SG[14]以及PPMD進行對比,其中PPMD為DLPG中不加Stackelberg博弈的過程,即基于啞元的隱私保護(Position Privacy Mechanism based on Dummy,PPMD).之后對DLPG、PPMD和SG中不同k值情況下位置暴露概率、隱私水平、服務質量損失以及位置熵之間的關系進行比較分析.最后分析攻擊者是否掌握用戶背景知識下,DLPG與SG匿名區域內用戶數量k與隱私水平L以及服務質量損失Qloss之間的關系.因為在啞元的選取上具有隨機性,因此本文采用多次實驗取平均值的方法進行驗證,保證效果的一致性與合理性.

4.2 結果分析

圖5 k與位置暴露概率、隱私水平、服務質量損失以及位置熵

2)匿名區域內用戶數量k與位置暴露概率P、隱私水平L、服務質量損失Qloss以及位置熵H之間的關系.

圖6 有、無背景知識下k與隱私水平以及服務質量損失對比

由圖5(a)可以看出,隨著k的增大,DLPG、PPMD和SG的位置暴露率均有明顯的提高,且DLPG優于PPMD、SG.這是因為PPMD只是單純的匿名過程,無Stackelberg博弈優化過程,一旦k值確定,其匿名區域也就固定;而在DLPG中若用戶的位置隱私受到威脅后,便會適當增大匿名區域,使得攻擊者更加難以準確推測出用戶的真實位置.SG算法中添加Stackelberg博弈優化過程,其位置暴露概率要高于PPMD,但SG本身只提供偏移位置,沒有考慮假位置匿名,而DLPG中使用啞元來替代用戶真實位置,攻擊者必先推測出啞元位置才能對用戶的真實位置進行預測,這兩個過程只要一個過程出錯,攻擊者便不會推測出用戶的精確位置.在本文中,位置暴露概率越高,其隱私保護效果越好,因此其隱私水平也高,用戶與用戶之間相似度越高,位置熵也越大,因此圖5(b)與圖5(d)一樣,與圖5(a)呈現相同的趨勢.DLPG和SG均需要通過攻擊者與用戶的博弈過程來提高用戶的隱私水平,而PPMD無博弈過程.因此圖5(c)可以看出,相同k值情況下,DLPG和SG服務質量損失高于PPMD,且隨著k值的增大趨勢更加明顯.DLPG中使用啞元來替代用戶真實位置,因此生成啞元的過程導致了DLPG服務質量損失要大于 SG.

3)攻擊者是否掌握用戶背景知識下,匿名區域內用戶數量k與隱私水平L以及服務質量損失Qloss之間的關系.

圖6為不同k值情況且攻擊者是否掌握用戶背景知識情況下,DLPG與SG的隱私水平以及服務質量損失.由實驗可以得出,攻擊者掌握用戶背景知識下,DLPG隱私保護效果好于SG,但其服務質量損失高于SG,這是因為用戶損失一定的服務質量來提高自己隱私的安全.在攻擊者不掌握掌握用戶背景知識下,DLPG中使用啞元來替代用戶真實位置,攻擊者需要先推測出啞元位置,才能利用啞元與真實位置之間的關系推測用戶真實位置,因此DLPG隱私保護效果更好,意味著服務質量損失更高.

綜上所述,DLPG在位置暴露率、隱私水平和位置熵等方面有著良好的表現,增大的匿名區域可以對用戶進行隱匿,增加了攻擊者對用戶真實位置的推測難度,同時將服務質量損失限制在可控范圍內,在損失一定的服務質量的同時換取更高的隱私保護效果.

5 小 結

本文提出啞元位置隱私博弈機制,解決了服務質量與隱私保護之間權衡問題,將服務質量損失限制在可控范圍內,在損失一定的服務質量的同時換取更高的隱私保護效果.該機制首先將用戶的真實位置轉換為啞元后與其余k-1個用戶位置構成匿名區域后,發送給LBS服務器.考慮到掌握用戶背景知識的攻擊者會根據用戶的保護策略調整攻擊策略來獲得用戶的位置信息,該機制基于Stackelberg博弈對匿名結果進行優化來對抗攻擊者的推測攻擊,盡可能保護用戶的位置隱私.本文通過真實數據集進行實驗,證明該機制在位置暴露率、隱私水平和位置熵方面表現良好,且在損失一定的服務質量的同時換取更高的隱私保護效果.