位置服務中的查詢隱私度量框架研究

張學軍，桂小林，馮志超，田豐，余思，趙建強

（1.西安交通大學電子與信息工程學院，710049，西安；2.蘭州交通大學電子與信息工程學院，730070，蘭州）

智能移動設備（例如智能手機、PDA等）的廣泛使用促進了位置服務（location-based service，LBS）的快速發展。據美國ABI Research最新預測，LBS全球總收入將由2009年的26億美元上升到2014年的140多億美元［1］。雖然LBS為用戶提供了極大的方便，但也造成了嚴重的隱私關注。惡意攻擊者可以將包含位置信息的LBS查詢與用戶關聯起來，推斷出其生活習慣、興趣愛好、健康狀況等個人敏感信息。研究者就如何允許用戶在享受LBS的同時限制其隱私泄露提出了許多查詢隱私保護機制［1-5］，但是，對這些保護機制的評價通常忽略了攻擊者可能具有的背景知識和推理能力，而這些背景知識和推理能力可以幫助攻擊者減少其對用戶真實位置的不確定性［4］。因此，已有的查詢隱私度量方法過高地評價了給定保護系統提供的隱私保護水平。而且，目前的LBS隱私保護研究主要集中在保護技術研發上，對隱私保護系統可信性及隱私保護機制有效性的評估還不夠成熟和完善，明顯缺乏一個形式化的框架來說明和度量各種查詢隱私保護機制。

本文針對上述問題，設計了一個融合攻擊者背景知識和推理能力的形式化查詢隱私度量框架。該框架綜合考慮LBS系統中影響用戶查詢隱私的各種因素，能正確度量各種查詢隱私保護機制的有效性。

1 相關工作

在查詢隱私中，位置k匿名［5］是最常使用的度量指標，k是匿名集的大小，k越大，查詢的隱私性越高。林欣等指出，當匿名集中各個用戶發送查詢的概率不相等時，匿名集的大小就不能反映每個用戶的真正匿名性［6］。Shokri等分析了位置k匿名在攻擊者具有用戶實時位置信息、統計信息和無信息時保護隱私的有效性，得出k匿名對查詢隱私有效，對位置隱私無效，并指出攻擊者可以利用k匿名的缺陷推斷出用戶的當前位置［7］。為此，他們提出了一種基于扭曲的隱私度量指標，通過比較攻擊者跟蹤用戶獲得的軌跡和用戶真實軌跡之間的差異來反映用戶的隱私保護水平［8］。最近，Shokri等設計了一個位置隱私量化工具，假定攻擊者可以利用從用戶軌跡采樣中抽取的用戶移動模型、LBS訪問模式等推斷其截獲的軌跡的真正制造者，并使用攻擊者的期望估計誤差作為隱私度量指標［9］，它在思想上和我們的工作很接近。通過對以上工作的研究發現：①已有的查詢隱私度量方法大都忽略了攻擊者的背景知識和推理能力，而這些信息和隱私度量密切相關。②已有的查詢隱私度量方法大都針對某個特定的隱私保護技術，缺乏一個泛化的度量框架來量化各種隱私保護機制，因此建立融合攻擊者背景知識和推理能力的查詢隱私框架就顯得非常必要。

2 查詢隱私度量框架

為了正確度量各種查詢隱私保護機制在不同攻擊模型下的有效性，需要綜合考慮LBS系統中影響用戶查詢隱私的各種因素和它們之間的關系，例如用戶的時空狀態和需求、攻擊者的背景知識和推理能力、隱私保護機制實現算法、隱私指標等。本文將這些高度相關的因素放在一起，針對匿名和泛隱私保護機制，設計了一個形式化查詢隱私度量框架，如圖1所示。

圖1 查詢隱私度量框架

定義該框架為六元組＜U，Q，PPM，，Aattacker，Mmetric＞，其中U是用戶u的集合。Q為用戶u在t時刻l位置上發出的LBS查詢集合。PPM是隱私保護機制，它對查詢q（q∈Q）進行扭曲處理并產生泛化查詢是攻擊者可以觀察的泛化查詢的集合。Aattacker是攻擊者，指能夠通過LBS訪問用戶位置和查詢的任何實體。Aattacker能夠利用他對PPM、用戶資料的背景知識和，通過執行推理攻擊推斷出q的真正請求者。Mmetric是查詢隱私度量指標，用于度量攻擊者的攻擊性能。攻擊者的推理是統計意義上的，他利用獲得的用戶資料抽取每個用戶發送q的先驗概率，形成概率矩陣M=（mij），進而利用M嘗試重構泛化區域內每個用戶發送的后驗概率。

2.1 移動用戶

在移動無線網絡環境中，用戶是在一定的時空狀態下執行LBS查詢，時空特性不僅包含它的實際狀態，也包含來自觀察者角度的狀態。

記U=｛u1，u2，…，uN｝為在區域L 內移動的N個用戶的集合，L=｛l1，l2，…，lM｝為 M 個不同位置的集合，時間T=｛1，2，3，…，T｝是離散的，為可記錄時間實例的集合。由于用戶是移動的，其位置隨時間發生變化，所以記函數whereis：U×T→L為用戶在任意時刻的真實位置。用戶u在時刻t的位置分布定義為集合S（t）=｛（u，whereis（u，t））｜u∈U｝。

定義1（初始查詢Q） 設Qu為LBS支持的所有查詢qu的集合，則定義用戶u的初始查詢q為一個四元組＜u，t，whereis（u，t），qu＞，其中u∈U 為用戶標識，t∈T 為查詢q發生的時間戳，whereis（u，t）∈L是用戶u在t時刻與查詢q相關聯的位置，qu∈Qu是查詢體。用戶U在時刻T所有可能的初始查詢的集合為Q?U×T×L×Qu。初始查詢Q代表了用戶在真實環境中的實際狀態。

2.2 隱私保護機制

LBS系統中，攻擊者能夠利用其可用的背景知識從初始查詢Q中推理出用戶的隱私信息或定位其位置。為了防止這種威脅，需要在LBS服務器得到用戶查詢之前，對其進行扭曲處理產生泛化查詢。隱私保護機制就是實現這種扭曲處理的。

定義3（隱私保護機制PPM） 設Q是初始查詢，泛化查詢，則定義隱私保護機制為映射函數f：Q→。例如，有f（q）=。轉換函數f實現初始查詢到泛化查詢的映射，攻擊者的目標就是通過觀察到的泛化查詢的子集，盡力重構出查詢Q。

2.3 攻擊者

為了正確評估隱私保護機制的有效性，必須對攻擊模型進行建模。攻擊模型可通過攻擊者的背景知識和推理能力來刻畫。對每種隱私保護機制，攻擊者所擁有的背景知識和推理能力直接影響攻擊這種保護技術的難易程度。攻擊者得到的有用背景知識越多，推理能力越強，就越有可能推斷出用戶的隱私。所以，只有將攻擊者的背景知識和推理能力融入到隱私度量中，才能正確度量用戶的隱私保護水平。

2.3.1 攻擊者背景知識和推理能力假設 在隱私度量中融入攻擊者的背景知識，就需要知道攻擊者可能擁有多少或哪些背景知識，這在實際中是不可行的。因此，一般會對攻擊者所擁有的背景知識和推理能力做出各種假設。本文做如下假設［10］：①攻擊者具有用戶實時位置分布的全局知識；②攻擊者可獲取匿名服務器轉發給LBS服務器的任何泛化查詢，匿名服務器可信且用戶和匿名服務器之間的通信是安全的；③匿名服務器使用的隱私保護方法是公開的，即對匿名集中的每個用戶，攻擊者通過隱私保護方法得到的匿名區域和其他人進行計算得到的匿名區域一樣；④攻擊者可利用獲得的用戶資料得到關于用戶的先驗知識；⑤攻擊者不具備用戶隱私需求的決策過程，但在獲得匿名服務器轉發的泛化查詢后，可以了解用戶的隱私需求；⑥攻擊者不能關聯同一用戶的任意兩個查詢。

2.3.2 攻擊者背景知識的表達與量化 在查詢隱私中，攻擊者的目標是通過觀察到的的子集，利用相關的背景知識盡可能正確地重新識別出q的真正發送者u。攻擊者觀察到泛化查詢子集的范圍取決于它的能力。對全局攻擊者，它觀察到泛化查詢的子集等于。攻擊者識別出的真正發送者越正確，用戶隱私泄露的可能性就越大。因此，可以將u和初始查詢q以及u和泛化查詢之間的關聯描述為條件概率p（u｜q）和p（u｜）。將所有p（u｜q）和p（u｜）都看作變量，而將背景知識表達為這些變量的約束。

本文中，假定攻擊者具有用戶資料的背景知識。用戶資料可描述為與用戶相關的一組屬性的集合，分為描述信息（例如國家、種族等）、聯系信息（例如姓名，地址等）和偏好信息（例如移動模型等）［11］。攻擊者還可以通過對用戶的觀察截取到一些服務請求的背景知識，例如用戶的假名、查詢內容、位置等。攻擊者將具有的背景知識和觀察到的信息進行關聯攻擊，得到p（u｜q）和p（u｜），這就將背景知識表達成了變量p（u｜q）和p（u｜）的約束。

2.3.3 先驗知識的獲取 用戶資料的每個屬性都有一定的取值范圍，其取值可離散化為明確的形式。例如，性別的取值可表示為“男”、“女”等。這樣，每個屬性的取值都是有限的。設A=｛a1，a2，…，an｝是要考慮的n個屬性，則每個用戶的資料可表示為Φu=｛a1：v1，a2：v2，…，an：vn｝，其中vi是用戶u 的屬性ai的取值，ai的取值可以為空。

給定一個屬性ai，先將其值離散化。如果是數字型，則把連續數據空間劃分為不相交且互斥的間隔區域，離散后的每個屬性用二進制串表示。于是用戶的資料可以用一個向量Pu=＜l1，l2，…，ln＞表示，其中li是一個二進制數字序列，該序列的長度等于ai的所有可能離散值的個數。如果vi滿足相應離散值，則相應二進制位取為1，否則為0。如性別所有可能的值是“男”和“女”，可用兩位二進制表示：“男”對應的位取1，為“10”，“女”對應的位取1，為“01”；

對每個查詢q，都有一個相關屬性的子集用于推理該查詢的真正請求者。由于用戶資料中的每個屬性對攻擊者識別查詢q的重要性不同，所以相關屬性的每個值都應有一個權重以確定該屬性值識別查詢q的重要程度。例如奢侈品的查詢，相關的屬性應包括工作、月薪和年齡。在這3個屬性中，月薪比年齡重要，而且月薪超過10 000元比月薪低于1 000元對該查詢更重要。因此，引入相關向量W（q）=＜w1，w2，…，wn＞表示屬性值和查詢q之間的關系，其中n為屬性的個數。對于任意用戶u∈U 和表示用戶u的資料和查詢q的相關程度。于是，用戶u發送查詢q的概率為

2.4 隱私度量

為了客觀評價查詢隱私保護機制的實際效果，需要建立一些評價指標來度量用戶的查詢隱私。

2.4.1 位置k匿名

定義4（位置k匿名） 設q=＜u，t，whereis（u，t），qu＞∈Q是一個初始查詢=＜i，r，t，qu＞∈是其對應的泛化查詢。如果匿名集中的所有用戶u滿足則稱用戶u是位置k匿名。

2.4.2 β熵匿名 在查詢隱私保護中，如果用戶和查詢關聯的不確定性越大，攻擊者越難推斷出查詢的真正發送者，因此可以借鑒信息論中的熵理論，用攻擊者識別泛化查詢的不確定性來度量用戶的查詢隱私。

從攻擊者的角度看，當它沒有任何背景知識時，匿名區域內每個用戶發送查詢的可能性相同，匿名區域的熵最大，用戶的查詢隱私保護水平最高。

定義5（β熵匿名） 設β＞0，q=＜u，t，whereis（u，t），qu＞∈Q 是初始查詢=＜i，r，t，qu＞∈是其對應的泛化查詢，如果對于所有的用戶u∈ul（r，t），滿足則稱用戶u是β熵匿名。

2.4.3 δ互信息匿名 互信息可用于度量兩個隨機變量之間的相關性。在查詢隱私中，可以用互信息度量泛化查詢被攻擊者截取后查詢不確定性的減少程度。攻擊者在截取到泛化查詢之前，僅知道q是由用戶U以概率p（U｜q）發送，其不確定性可描述為E（U｜q）。攻擊者截取到泛化查詢后，其不確定性可以表示為E（U｜）。于是，攻擊者截取到泛化查詢前后不確定性的增益為

定義6（δ互信息匿名） 設δ＞0，q=＜u，t，whereis（u，t），qu＞∈Q是初始查詢=＜i，r，t，qu＞∈是其對應的泛化查詢，如果對所有用戶u∈ul（r，t），滿足I（U｜q；）≤δ∧f（q）=，則稱查詢發送者u是δ互信息匿名。

3 實驗分析

利用框架對dichotomicPoints［10］隱私保護算法的有效性進行度量。實驗在產生用戶位置坐標和LBS請求時，采用業界認可的Thomas Brinkhoff路網數據生成器［12］模擬生成用戶在Oldenburg市區（面積為23.57km×26.92km）交通路網內的運動軌跡，隨機產生10 000個用戶，用戶的移動速度采用默認設置。攻擊者關于用戶資料的背景知識可用UCI機器學習中的Adult數據集，利用2.3節的方法求出。因為本文主要關注框架對隱私保護機制有效性的度量，所以在實驗中采用隨機產生用戶先驗知識的方法。模擬算法在Windows7平臺下使用Java實現，測試機器的基本參數為3.51GHz Intel Core（TM）i5處理器、4GB內存。實驗結果取算法執行100次仿真的平均值。

圖2 位置k匿名度量

3.1 位置k匿名度量

圖2給出了攻擊者有、無背景知識時，利用位置k匿名度量查詢隱私保護機制的情況。無背景知識時，在攻擊者看來，由dichotomicPoints算法產生的匿名區域內每個用戶發送查詢的可能性相同。當觀察到泛化查詢時，攻擊者只能推斷出匿名區域內用戶發送的概率為該匿名區域內用戶數目的倒數，即圖中“無背景知識”對應的曲線。有背景知識時，從攻擊者的角度看，匿名區域內每個用戶發送查詢的概率不再相等，攻擊者使用攻擊算法找出最有可能發送查詢的用戶，即圖中“有背景知識”對應的曲線。首先用戶的后驗概率隨著k值的增加而減小，這是因為k越大，隱私保護機制產生匿名區域的用戶數就越多。其次，給定一個k值，攻擊者沒有背景知識時，發送用戶的后驗概率均小于1／k，即攻擊者不能以大于1／k的概率識別出查詢發送者，k的大小能反映用戶的隱私水平；攻擊者有背景知識時，發送用戶的后驗概率大于1／k，即攻擊者能以大于1／k的概率識別出查詢發送者，用戶的隱私有可能暴露，匿名集的大小已不能正確反映用戶的隱私水平。因此，在查詢隱私度量中考慮攻擊者背景知識是必不可少的，同時也表明查詢隱私的度量結果應該包括用戶查詢隱私水平值和攻擊者背景知識的假設，這可幫助用戶理解他們隱私受保護的程度以及攻擊者背景知識對用戶隱私保護的重要性。

3.2 β熵匿名和δ互信息匿名度量

β熵匿名和δ互信息匿名指標用于度量攻擊者對查詢的不確定性，反映了用戶的查詢隱私水平。

圖3 β熵匿名度量

圖4 β熵匿名區域面積

一個滿足β熵匿名的匿名區域可以確保該匿名區域的熵值大于β，而滿足δ互信息匿名的匿名區域可確保攻擊者對查詢不確定性的減少小于δ。圖3和圖5描述了不同β和δ對應的熵和互信息，可以看出，由dichotomicPoints算法產生匿名區域的所有用戶都滿足β熵匿名和δ互信息匿名的定義，且當β和δ分別接近整數時，熵值和互信息值的變化比較急速，這是由熵的本質所確定的。圖4和圖6給出了匿名區域平均面積占數據空間的比率隨β和δ分別變化的情況，圖4中匿名區域的面積隨β增大而增大，這是因為β越大，匿名區域的熵越大，匿名區域內包含的用戶越多，匿名區域的面積就越大，用戶的隱私保護水平也越高，但服務質量越低。如圖6所示，匿名區域的面積隨著δ的增大而減小，因為δ越大，攻擊者的不確性越小，匿名區域內包含的用戶數越少，滿足隱私需求的匿名區域就越小，用戶的隱私保護水平也越低，但服務質量越高。因此，β熵匿名和δ互信息匿名指標能夠正確反映攻擊者具有背景知識時，查詢隱私保護機制提供的用戶隱私保護水平，可以幫助用戶確定隱私需求和服務質量之間的平衡。

圖5 δ互信息匿名度量

圖6 δ互信息匿名區域面積

4 結 論

本文提出了一個形式化的查詢隱私度量框架。該框架綜合考慮了LBS系統中影響用戶查詢隱私的各種因素，定義了攻擊者可用背景知識和推理能力的假設及隱私度量指標。實驗結果驗證了該框架的有效性。同時，對實驗結果的分析表明，考慮攻擊者的背景知識和推理能力對LBS查詢隱私保護的度量是必不可少的，在設計隱私保護機制時需要對攻擊者的知識和其目標的一致性進行建模，才能設計出更適合實際的查詢隱私保護機制。后續工作中，將考慮把位置服務應用集成到框架中，分析隱私保護機制對于這些應用的有效性。另外，對攻擊者具有用戶移動模型和查詢歷史等背景知識進行合理的建模也是將要進行的重點工作之一。

［1］ PAN Xiao，XU Jianliang，MENG Xiaofeng.Protection location privacy against location-dependent attacks in mobile services［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（8）：1506-1519.

［2］ XU T，CAI Ying.Exploring historical location data for anonymity preservation in location-based services［C］∥Proceedings of the 27th IEEE International Conference on Computer Communications.Piscataway，NJ，USA：IEEE，2008：1220-1228.

［3］ PING A，ZHANG Nan，FU Xinwen，et al.Protection of query privacy for continuous location based services［C］∥Proceedings of the 30th IEEE International Conference on Computer Communications.Piscataway，NJ，USA：IEEE，2011：1710-1718.

［4］ SHOKRI R，THEODORAKOPOULOS G， TRONCOSO C，et al.Protecting location privacy：optimal strategy against localization attacks［C］∥Proceedings of the 19th ACM Conference on Computer and Communication Security.New York，USA：ACM，2012：617-626.

［5］ GRUTESER M，GRUNWALD D.Anonymous usage of location-based services through spatial and temporal cloaking［C］∥Proceedings of the First International Conference on Mobile Systems， Application，and Services.New York，USA：ACM，2003：31-42.

［6］ 林欣，李善平，楊朝會.LBS中連續查詢攻擊算法及匿名性度量 ［J］.軟件學報，2009，20（4）：1058-1068.LIN Xin，LI Shanping，YANG Zhaohui.Attacking algorithms against continuous queries in LBS and anonymity measurement［J］.Journal of Software，2009，20（4）：1058-1068.

［7］ SHOKRI R，TRONCOSO C，DIAZ C.Unraveling an old cloak：k-anonymity for location privacy［C］∥Proceedings of the 2010ACM Workshop on Privacy in the Electronic Society.New York，USA：ACM，2012：115-118.

［8］ SHOKRI R，FREUDIGER J，JADLIWALA M，et al.A distortion-based metric for location privacy ［C］∥Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society.New York，USA：ACM，2009：21-30.

［9］ SHOKRI R，THEODORAKOPOUS G，BOUDEC J-Y L，et al.Quantifying location privacy ［C］∥Proceedings of the 32nd IEEE Symposium on Security and Privacy.Piscataway，NJ，USA：IEEE，2011：247-262.

［10］CHEN Xihui，PANG Jun.Measuring query privacy in location-based services［C］∥Proceedings of the Second ACM Conference on Data and Application Security and Privacy.New York，USA：ACM，2012：49-60.

［11］SHIN H，ATLURI V，VAIDYA J.A profile anonymization model for privacy in a personalized location base service environment［C］∥Proceedings of the 9th International Conference on Mobile Data Management.Piscataway，NJ，USA：IEEE，2008：73-80.

［12］BRINKHOFF T.A framework for generating networkbased moving objects ［J］.GeoInformatica，2002，6（2）：153-180.