移動互聯網服務的隱私保護機制

李暉　牛犇　李維皓

摘要：探討了考慮背景信息的位置和查詢隱私保護方案，如基于背景信息的虛假位置k-匿名方案、同時保護位置和興趣的隱私保護方案、基于交互的隱私保護方案，還探討了基于用戶隱私鏈拆分的實名認證和身份隱私保護策略；認為在避免可信第三方參與，敵手能夠獲取到背景信息的前提下，能夠實現對用戶身份、位置和查詢隱私的保護，達到信任機制和隱私保護的有機結合將是未來隱私保護發展的趨勢。

關鍵詞： 移動互聯網；身份隱私；位置隱私；查詢隱私

1 移動互聯網面臨隱私

保護威脅

移動互聯網服務的廣泛普及、大數據技術的普遍應用在為人們帶來便利的同時，也對用戶隱私保護帶來了巨大的挑戰。眾多的移動互聯網服務大量采用用戶名-口令認證機制，為記憶方便，用戶普遍對不同的應用采用相同的用戶名和口令，使得一旦某個服務商數據庫泄露就威脅到用戶在其他服務商的信息。國家對移動互聯網信息傳播實名管控的需求與用戶身份隱私形成矛盾，如何提高用戶身份認證的安全等級，免除用戶記憶口令的負擔，兼顧實名管控和用戶身份隱私的保護成為移動互聯網用戶身份管理的主要挑戰。

另一方面，微信、大眾點評、百度地圖等移動服務要求用戶的位置信息和興趣信息，不可信的服務對這些信息的濫用或者泄露對于用戶權益帶來極大的損害，在享受移動互聯網服務方便性的同時，保護用戶的身份、位置和興趣的隱私成為移動互聯網領域亟待解決的問題。

2 移動互聯網位置和查詢

隱私保護的主要方法

基于位置服務中常見的安全及隱私威脅主要包括5種攻擊方式：單點攻擊、基于上下文的攻擊、多點攻擊、多點配合上下文攻擊以及直接攻擊可信第三方。一般而言，這幾種攻擊方式要求攻擊者的能力依次增強，要求攻擊者能夠獲取越來越多的用戶信息，從而更高概率地獲取用戶隱私信息。

對于攻擊者而言，他們可以通過多種途徑獲取多種額外的信息，例如，用戶密度信息，請求發送的概率分布，地圖上興趣點的分布情況等，這些可以統稱為背景信息，此類信息一般為公開信息，可以通過互聯網輕易獲取，亦可通過攻擊相關的可信第三方來獲取。例如，Google Maps的服務器上保存著歷史用戶的各種查詢記錄，分布情況等重要信息，一旦該服務器被攻擊，用戶的所有信息將暴露于攻擊者眼前。

各種基于位置服務中的服務提供商本身其實就是潛在的攻擊者或者隱私信息的泄露者。層出不窮的泄密事件說明傳統上認為是可信的服務提供商完全有可能被來自內部或者外部的攻擊者攻陷，從而導致用戶隱私信息的泄漏，因此，如何在服務提供商不可信的前提下保證用戶隱私信息不被泄露就成為了一個很嚴峻的問題。

針對上述問題，來自全球工業界和學術界的科研人員已經提出了許多解決方案，這些方案可以根據不同標準分為不同的類別，以下介紹兩種常見的分類方法：

（1）第一種分類主要根據用戶對隱私信息的類型進行分類，可分為位置隱私、查詢隱私。

其中位置隱私用以保護用戶當前以及歷史位置信息，使得攻擊者難以獲取用戶位置相關的信息，從而難以實現對用戶的追蹤等。

查詢隱私旨在保護用戶所查詢的內容，從而不泄露用戶的個人喜好等信息。然而，用戶的位置與所查詢的內容并不完全獨立，甚至在大多數情況下兩者存在一定的關系，從而使得單純保護某一種隱私的方案難以真正保護用戶的隱私，故而也需要同時保護用戶的位置隱私和查詢隱私。

（2）第二種分類主要是為了實現不同場景下的隱私保護問題，現將當前主流的隱私保護方案分為5類：位置偏移、混淆技術、時間和空間隱匿、添加虛假信息以及其他方案。

（a）位置偏移

位置偏移示意如圖1所示。黑色手機為真實用戶，其請求服務半徑為1英里，當他需要發送基于位置服務的服務請求時，用偏移后的位置取代其真實位置，然后構建新的服務請求信息并發送給服務運營商，從而達到保護其位置隱私的目的。此種方法算法復雜度很低，很容易在智能終端上實現，而且系統開銷，尤其是通信開銷基本上沒有增加。然而由于所請求的服務數據和真實需要的服務數據之間存在一定的偏差，從而導致服務質量的降低。而且在此類方案中，服務質量的優劣和隱私保護效果的好壞成為了一對矛盾，服務質量越高，隱私效果越差，反之亦然。

（b）混淆

適用于位置隱私的保護和查詢隱私的保護。對于位置混淆，用戶可以通過對其查詢半徑進行模糊，例如，增大其查詢半徑或者刻意縮小其查詢半徑，甚至結合偏移的方案，通過位置偏移+查詢半徑變化的方案，使得攻擊者更難推斷其真實信息，如圖2（a）所示；對于查詢隱私混淆，將用戶的興趣集合進行劃分，如圖2（b）所示，當用戶真實的查詢請求為KFC的時候，為了對其查詢信息進行混淆，可以用更大的一個集合“餐飲”代替，從而將自己的真實請求信息混淆于更大的集合之中，達到保護查詢請求的目的。

此類解決方案的優點在于易于實現，由于只需要對相關參數進行修改，例如增大查詢半徑，所以很容易完成隱私保護。由于對查詢半徑的調整以及查詢內容的混淆，會導致額外的系統開銷，例如，用戶需要獲取一些不必要的服務信息，這樣的操作也會引起服務質量的下降。

（c）時空隱匿

其核心思想在于收集/等候足夠多的用戶信息，通過統一提交請求，達到保護各個用戶隱私信息的目的。真實用戶將其請求發送至一個可信的第三方，該第三方同時收集周圍其他用戶的多個請求，如圖3（a）收集多個用戶的請求，然后將多個請求進行合并，一起發送給服務提供商，從而使得提供商難以獲取各個用戶的隱私信息。在圖3（b）中，假設用戶的真實請求發送于時間點t3，可信第三方出于時間隱匿的目的，等候一段時間以收集更多的請求信息。此處收集的信息可能來自多個用戶，也可能來自該用戶的多條請求信息，然后將多個請求一并發送給服務提供商，達到隱匿真實請求的目的。

一般情況下，此類方案可以達到較高的隱私保護級別，但具有較大的系統開銷，以及較長的等待時延，最重要的問題在于對于可信第三方的依賴。

（d）虛假信息

包括基于虛假位置的位置隱私保護和基于虛假請求信息的查詢隱私保護。其核心思想在于通過構造虛假的位置或者虛假的請求從而有效的實現k-匿名或者l-多樣性的隱私保護級別。

如圖4（a）所示，為了保護用戶的真實位置，通過合理構造出若干個虛假的位置（例如k-1個），最終將這個k個位置構成的集合一并發送給服務提供商，其隱私保護的效果取決于攻擊者是否能夠有效從k個位置中區分出哪個是用戶的真實位置。

類似的，圖4（b）中給出了基于虛假查詢請求的查詢隱私保護策略，用戶在向服務提供商發送請求之前，先構造若干個虛假的請求，一并發送給服務提供商，從而實現隱私保護。

在此類方案中，是否能夠有效的構造虛假信息成為了隱私保護是否有效的關鍵，尤其是在面對擁有各種各樣的背景信息的攻擊者的時候，虛假信息可能會被有效過濾，從而難以達到用戶期望的隱私保護效果。

基于虛假信息的隱私保護方案比較容易實現，也能夠提供較高級別的隱私保護。由于需要引入額外的虛假信息，而額外的虛假位置或者虛假查詢請求會帶來相應的服務數據，所以隨著虛假信息數目的增加，系統的性能會大幅度的降低。另外大多此類方案都沒能同時保護用戶的位置隱私和查詢隱私，這也會使得整個系統的隱私保護效果會由于攻擊者所擁有背景信息的數量增加而下降。

（e）其他

位置服務中還有其他相關的一些隱私保護方案，主要包括基于密碼學工具的方案。通過對用戶所上傳的信息進行相關處理，例如加密等方法，借助于私人信息檢索（PIR）等技術，從而使得用戶在能夠享受服務數據的同時又不將自己的查詢請求泄露給服務提供商。當然，此類系統也可能借助于第三方的匿名服務器等，從而更高程度的保護用戶隱私信息。

此類方案一般能夠較高程度的為用戶提供隱私保護效果。然而，由于匿名服務器（可信第三方的一種）的存在，使得整個系統難以承受單點失效攻擊。此外，一些復雜的密碼學運算仍然難以高效的應用在其上，這樣會導致額外的計算負擔，降低系統的可用性。

從移動用戶的身份信息、位置信息以及興趣信息三方面對隱私保護問題進行總結，分析了現有科研成果所采用的主流技術及相應的優、缺點，在此基礎進行了分類。現有移動互聯網中隱私保護方案分類如表1所示。

從表1提及的現有方案中可以看到，當前解決方案大都基于可信第三方，用戶的身份認證一般由可信第三方或者服務提供商進行認證。CliqueCloak[1]和Casper[2]利用可信第三方實現匿名區域大小可調的k-anonymity。Footprint k-anonymity[3]利用移動用戶的歷史信息，通過在相遇用戶之間構成一個虛擬的Mix-Zone來完成對用戶興趣信息和身份信息的混淆，從而實現k-anonymity。CacheCloak[4]引入了緩存和預測的概念，通過緩存的用戶歷史軌跡等信息，預測用戶下一步的移動，為用戶提供實時的服務。但是當用戶身處全新環境時，該方案的預測準確性會大幅降低。Xu和Cai[5]提出了Feeling-based pyramid解決方案，該方案將地圖進行劃分，并根據用戶的感興趣程度賦予不同的權重，通過分析歷史信息，用信息熵的概念實現P-popular trajectory（PPT）。該方案能夠有效的保護用戶的位置信息和興趣信息，但其具有較高的計算資源消耗。Pan[6]等人提出了ICliqueCloak，雖然該方案可以在連續場景下同時保護用戶的位置信息和興趣信息，但同樣的運算復雜度較高。

與此同時，有一些隱私保護技術并不依賴于第三方機構的技術（TTP），其基本思想主要集中于用戶和其他用戶之間交互信息，通過對等網絡（P2P）或者基于相遇的解決方案實現匿名集的構造，從而保護用戶隱私。Chow[7]等人提出了一種基于P2P的解決方案，通過用戶的相互協作，用近距離通信標準（Wi-Fi或藍牙技術）實現用戶之間的信息交換，在考慮用戶的最大移動距離基礎上，實現連續場景下的k-anonymity，以保護用戶的位置隱私。然而由于用戶的移動模式和近距離通信的通信距離限制，使得真實用戶的位置會以較大概率落在匿名集的中心區域。另外，用戶仍需將自己的真實身份和興趣信息發送給服務運營商，所以該方案難以同時保護用戶的身份信息和興趣信息。CAP[8]是一個基于四叉樹和不同的網格步長的希爾伯特曲線型（VHC）的P2P解決方案，根據道路密度，CAP用一個大小可調的希爾伯特曲線對地圖進行填充，用四叉樹的存儲結構，在有效實現k-anonymity的基礎上大幅度降低系統的計算和存儲開銷。Pingley[9]等人提出了DUMMY-Q方案，通過在本地構建一個興趣信息池，利用虛假興趣信息選擇算法高效的實現k-anonymity，從而有效抵御來自主動攻擊者的推理攻擊。但高額的興趣信息池維護開銷對手機用戶而言難以負擔。Shokri[10]等人提出了一種基于群組的用戶隱私保護方案，當前用戶通過將所需查詢在群組內轉發，由某一用戶替代其向服務運營商發送服務請求，從而實現對當前用戶身份信息，位置信息和興趣信息的保護。但該方案的問題在于代替當前用戶進行發送請求的用戶沒有足夠的動力來進行此類操作，加之移動設備的資源受限性，該方案難以在移動互聯網中廣泛應用。

3 考慮背景信息的位置和

查詢隱私保護方案

3.1 基于背景信息的虛假位置

k-匿名方案

通過巧妙的設計虛假位置生成算法，在充分考慮攻擊者可能擁有的背景信息的基礎上有效實現k-匿名。同時，此方案能夠有效的提供較大的隱匿區域，而且可以避免真實用戶落在所提交k個位置中處于最中間區域的問題。

基于背景信息的虛假位置k-匿名如圖所示。將本地地圖劃分為若干個網格，不同的網格形狀框代表了不同的歷史請求概率，也就是用戶歷史上在該網格內發送基于位置服務請求的概率。藍色小人兒代表真實用戶，空心兒小人兒代表最后參與k-匿名的虛假用戶位置。我們的思路包括兩部分，第一部分見圖5（a）、圖5（b），其主要目的在于通過比對每個網格與當前用戶所處網格的歷史請求概率，旨在選擇出一組潛在的網格去分配虛假用戶，從而保證攻擊者難以通過此類背景信息對最終提交的k個位置進行有效過濾。圖5（c）、圖5（d）代表了兩種極端，在圖5（c）中，真實用戶與虛假用戶相距較近，這樣攻擊者甚至無需猜測，便能獲取真實用戶的大體位置，使得真實用戶的位置隱私難以有效保證，顯然這是不可取的。圖5（d）給出了一種相對比較優良的選擇結果，即最終參與匿名的幾個位置（包括了一個真的和兩個假的用戶位置），兩兩之間相距足夠遠，且具備相等或者近似的服務請求概率，從而大大降低攻擊者猜測出用戶真實位置的概率，大幅度提高用戶的位置隱私級別。

我們對所提出方案的有效性和安全性進行了驗證，具體細節[11]可參看，同時對于背景信息的進一步利用可參考[12]。

3.2 同時保護位置和興趣的隱私

保護方案

同時保護位置和興趣的隱私保護方案[13]用于同時保護用戶的位置隱私和查詢隱私，并提供個性化的隱匿區域大小選擇。該方案通過對傳統的背景信息進行細分，在選擇虛假位置的時候，不但考慮選擇k-1個查詢概率相似的位置，同時兼顧查詢隱私的保護，通過合理選擇l-1個相似的查詢內容，來確保位置隱私到達k-匿名級別的保護，和查詢隱私的l-多樣性級別的隱私保護。另外，本方案由于在設計初期就允許用戶對隱匿區域的大小進行選擇，并通過隱匿區域的隨機偏移保證真實用戶的位置可能落在該區域內的任何位置，從而有效的避免真實位置位于隱匿區域中心部分的攻擊。

由于隱匿區域的大小往往決定了系統開銷的大小，故而本方案首先賦予用戶自主的隱匿區域大小調節能力，從而讓用戶根據自己的需求合理調節該區域的大小，進而調節可以忍受的系統開銷。

具體而言，用戶設定合適的隱匿區域，如圖6（b）中的紅色虛線框，故而需要在該隱匿區域內進行虛假位置分布。然而考慮到上文提到的“用戶處于中心區域的攻擊”，我們首先對該虛線框進行一個隨機偏移，偏移至圖中紅色實線框處，然后進行相關虛假用戶分布工作。在具體分布時，根據需要達到的位置k-匿名中的參數k，首先用四分法對該區域進行劃分，如圖6（b）所示，k=3，故而將該區域劃分為4部分，除了真實用戶所處的區域外，隨機選取其他3個區域中的2個作為備選，最后開始著手考慮對查詢請求內容的l-多樣性需求。具體的方法如圖7所示，圖中每種顏色的符號代表不同的歷史查詢請求，例如附近的酒店信息，附近的醫院信息等，我們在每個細分后的區域內對各類查詢請求進行統計，遵循相似的規律來構造剩下的l-1個查詢內容，即所選擇的l-1個請求內容需要與當前用戶的真實請求內容的查詢概率接近，從而確保l-多樣性的效果。通過以上步驟，最大限度的實現本文所設定的目標。

3.3 基于交互的隱私保護機制

本方案目的在于設計一個通過用戶交互來實現信息混淆的隱私信息保護方法，思路相對較簡單。每個用戶維護一個本地緩沖區，用以隨機記錄其所處位置和所發送請求，當遇到其他用戶時，隨機從緩沖區內抽取一條信息進行交換，如此往復，使得每個用戶的緩沖區內的信息足夠混亂。在真正需要向服務提供商發送請求時，可以從本地緩沖區內隨機搭配出若干個組合，結合真實的位置和請求內容一起發送給服務提供商，以達到k-匿名的保護效果。系統架構如圖8所示，智能終端利用位置混淆部件、偽興趣生成部件以及緩沖區對信息進行處理，將處理后的請求信息發送給定位業務系統（LBS）服務器以便獲取服務[14]。

4 基于用戶隱私鏈拆分的

實名認證和身份隱私

保護策略

Zhu[15]等人提出通過將用戶與證書之間的注冊鏈條打斷，并將各部分交由不同的實體進行管理的方案來實現對用戶的身份信息的保護，進而實現用戶個人信息的安全、有效更新，防止來自用戶和服務運營商雙方的欺騙和共謀等攻擊。主要思想是打斷用戶查詢/發布數據資源時提供的“用戶真實身份-用戶數據”對應關系，通過引入“假名”（或者多個假名的假名集）的方法實現基于用戶隱私鏈拆分的實名認證和身份隱私保護策略。通過構造相應的“假名集”，將用戶隱私鏈分為“用戶真實身份-假名集-用戶數據”，可信認證服務器是一個權威的第三方認證服務器，其和各種不同的服務提供商分別管理用戶隱私鏈的一部分。其中，可信認證服務器維護“用戶真實身份-假名集”，服務提供商維護“假名集-用戶數據”，從而實現實名認證和用戶身份隱私的保護。

服務提供商對用戶的認證過程可基于移動終端進行。在移動終端上保存假名證書和假名對應的密鑰，安裝認證模塊，該模塊可以是應用（APP）程序，也可以是手機用戶識別模塊（SIM）卡或者手機內部擁有的硬件安全模塊。圖9是我們基于SIM卡實現的一種兼顧實名與用戶身份隱私的互聯網服務認證方案。SIM卡中實現有數字簽名模塊和認證用戶識別應用發展工具（STK）應用，可信認證服務方可使用公安部eID服務，具體步驟如下：

·用戶向可信認證服務器提供真實身份，申請“全局證書”，該證書包含可信認證服務器對用戶的真實身份的簽名，用作用戶向可信用戶申請假名證書時認證的憑證。

·憑借“全局證書”，用戶可向可信認證服務器申請多個假名證書，構建假名集合。

·用戶在向不同服務提供商系統注冊時，可以使用不同的假名證書證實自己的身份。這樣，服務提供商系統維護假名-用戶數據。并利用假名證書實現服務提供商系統的登錄認證，保證了不同的服務使用不同的假名。

服務提供商對用戶的認證過程如下：

·用戶提交注冊或登錄請求。

·服務提供商通過短消息向用戶SIM卡發送認證挑戰。

·SIM卡上的認證STK應用會截獲并處理認證挑戰短消息，并通過STK功能將相關注冊或交易請求信息顯示在手機屏幕上。

·用戶確認信息無誤后，認證STK應用對認證挑戰進行數字簽名生成相應的認證信息，并將此信息發回服務提供商。

·服務提供商用戶假名證書驗證簽名的正確性。

這一方案服務提供商不存儲用戶的真實身份信息，而且不同的服務提供商使用不同的假名，支付等關鍵交易采用數字簽名認證，提高了安全級別。如有需要，通過假名證書，可信認證服務可追蹤用戶真實身份。

5 結束語

本文分析了現有移動互聯網位置、興趣和身份隱私保護方案，介紹了幾個基于分布式架構的位置和查詢隱私保護機制，并給出了一個兼顧實名和身份隱私保護的身份認證方案，但是這個方案需要可信認證服務提供方。未來在下面幾個方面還有許多問題需要解決。

第一，考慮到智能終端的大規模使用，傳統的基于可信第三方的方案無論從性能角度還是安全性角度來講都有比較大的局限性，所以應該盡可能的避免可信第三方的使用。另外由于智能終端的資源受限性，例如較低的計算能力，有限的存儲空間以及相對較弱的通信能力，故而應該盡可能的降低所涉及隱私保護方案的復雜度，并提高已有資源的利用率。

第二，需要充分考慮攻擊者可能擁有的各類背景信息。我們的實驗結果證明，現有大多方案的隱私保護效果在攻擊者擁有背景信息的前提下都會大幅下降，即使少部分方案已經將背景信息考慮進算法設計過程中，然而由于對于背景信息分析的不全面性，導致攻擊者仍然能夠通過將各類相關背景信息進行融合，如采用數據挖掘等技術，從而增大獲取用戶隱私信息概率的目的。因此，在未來的研究方向中，需要考慮更加符合用戶現實生活的各類背景信息。

第三，目前仍然沒有一種行之有效的隱私保護效果衡量方法。由于用戶需求的多樣性，例如，身份隱私，位置隱私，查詢隱私，軌跡隱私，數據隱私等，以及用戶在不同應用中對于各類隱私信息的個性化設置等因素，導致對隱私保護效果的衡量工作難以統一的進行，這也使得很難去評價當前已有算法的效果。因此，設計統一的隱私度量方案或者度量平臺顯得尤為重要。

第四，將信任機制與隱私保護有機結合。如果有足夠高的信任，可以降低隱私泄露的風險，提高服務質量，降低系統開銷。如何確立最佳的平衡點和建立大規模用戶的信任評估模型和系統還亟待開展研究。

參考文獻

[1] GEDIK B， LIU L. Protecting Location Privacy With Personalized k-Anonymity： Architecture and Algorithms [J]. IEEE Trans. Mobile Computing， 2008，7（1）：1-18

[2] MOKBEL M F， CHOW C-Y， AREF W G. The New Casper： Query Processing for Location Services Without Compromising Privacy [C]//Proceedings of the VLDB， 2006：763-774

[3] XU T， CAI Y. Exploring Historical Location Data for Anonymity Preservation in Location-Based Services [C]//Proceedings of the INFOCOM， 2008：547-555

[4] MEYEROWITZ J， CHOUDHURY R R. Hiding Stars with Fireworks： Location Privacy Through Camouflage [C]//Proceedings of the MobiCom， 2009： 345-356

[5] XU T， CAI Y. Feeling-Based Location Privacy Protection for Location-Based Services [C]//Proceedings of the CCS， 2009：348-357

[6] PAN X， XU J， MENG X. Protecting Location Privacy against Location-Dependent Attack in Mobile Services [J]. IEEE Trans. Knowledge and Data Engineering， 2012，24（2）： 1506-1519

[7] CHOW C-Y， MOKBEL M F， LIU X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service [C]//Proceedings of the GIS， 2006：171-178

[8] PINGLEY A. Cap： A context-Aware Privacy Protection System for Location-Based Services [C]//Proceedings of the ICDCS， 2009：49-57

[9] PINGLEY A. Protection of Query Privacy for Continuous Location Based Services [C]//Proceedings of the INFOCOM， 2011：1710-1718

[10] SHOKRI R， PAPADIMITRATOS P， THEODORAKOPOULOS G， HUBAUX J P. Collaborative Location Privacy [C]//Proceedings of the IEEE MASS， 2011：500-509

[11] NIU B， LI Q， ZHU X， CAO G， LI H. Achieving k-anonymity in Privacy-Aware Location-Based Services [C]//Proceedings of the INFOCOM， 2014： 1805-1819

[12] NIU B， LI Q， ZHU X， CAO G， LI H. Enhancing Privacy through Caching in Location-Based Services [C]//Proceedings of the INFOCOM， 2015： 1309-1321

[13] NIU B， ZHU X， LI W， LI H， WANG Q， LU Z. A Personalized Two-Tier Cloaking Scheme for Privacy-Aware Location-Based Services [C]//Proceedings of the ICNC， 2015： 2301-2316

[14] NIU B， ZHU X， LEI X， ZHANG W， LI H. EPS： Encounter-Based Privacy-Preserving Scheme for Location-Based Services [C]//Proceedings of the GLOBECOM， 2013： 1106-1117

[15] ZHU Z， CAO G. APPLAUS： A Privacy-Preserving Location Proof Updating System for Location-based Services [C]//Proceedings of the IEEE INFOCOM， 2011：1889-1897