楊松濤，孟凡波，焦 博

(佳木斯大學(xué)信息電子技術(shù)學(xué)院，黑龍江 佳木斯154007)

0 引 言

基于位置的服務(wù)(Location Based Services，LBS)是依賴于移動用戶位置的典型應(yīng)用.LBS 建立了一個機制和平臺，整合分布在人們周圍的零散數(shù)據(jù)，并在這個平臺之上實現(xiàn)了更多的應(yīng)用.例如:基于位置的物流運輸、娛樂和購物;位置感知的緊急救援、商業(yè)廣告的精確投放等.當(dāng)用戶體驗LBS的時候，必須提交三個敏感信息:位置、時間和查詢內(nèi)容.如果LBS 服務(wù)器是不可信的，這些數(shù)據(jù)可能涉及用戶敏感的隱私問題.位置隱私問題被公認為阻礙LBS 被廣泛接受和應(yīng)用的主要原因［1］.個性化位置k－匿名模型允許用戶自由調(diào)整個人隱私要求和最大時空容忍度，同時縮小了匿名集的勢.一些研究進一步分析了用戶隱私需求并提出了位置多樣性、查詢多樣性和語義多樣性等概念.位置模糊技術(shù)［8］是故意降低用戶位置的分辨率來保護用戶位置隱私，低空間分辨率位置造成了LBS 提供粗粒度的服務(wù).位置模糊技術(shù)和位置k－匿名技術(shù)是相輔相成的，近年來的一些研究方法［2］結(jié)合了位置模糊和k－匿名技術(shù)，同時保護位置隱私和查詢隱私.位置數(shù)據(jù)精度越高，依賴位置提供的服務(wù)越精確，而用戶的隱私保護程度就越低.從主次關(guān)系角度來說，保證位置數(shù)據(jù)的可用性是基于位置服務(wù)首先要考慮的.但是，在保證數(shù)據(jù)可用性的前提下，設(shè)計合理的隱私保護方法是非常必要的.本文主要關(guān)注數(shù)據(jù)可用性與隱私保護間之間矛盾，提出基于決策樹的位置匿名方法.

1 系統(tǒng)模型

中心服務(wù)器結(jié)構(gòu)在大量的隱私保護方案中得到應(yīng)用并證明了它的有效性，主要具有以下優(yōu)點:(1)切斷了查詢位置與查詢內(nèi)容之間的直接聯(lián)系;(2)減輕了移動客戶端的計算負載;(3)屏蔽查詢者的身份標(biāo)識(例如:IP 地址和MAC 地址).因此，本文設(shè)計了一個基于中心服務(wù)器結(jié)構(gòu)的位置隱私保護模型，此模型滿足查詢匿名性和位置軌跡不可追蹤性.圖1 顯示了系統(tǒng)模型中的實體及它們之間的交互.這里有4 個關(guān)鍵部件:定位系統(tǒng)服務(wù)器，移動終端(MC)、位置匿名服務(wù)器(LAS)和LBS 服務(wù)器(LBSS).

圖1 系統(tǒng)模型

圖1 所示的系統(tǒng)模型中，LBSS 在嚴(yán)格執(zhí)行協(xié)議和算法的前提下，同時使用收集到的位置信息和背景知識推斷用戶的敏感信息，為了商業(yè)目的，LBSS 可能出賣用戶的敏感信息給不友好的第3方.本文確定了4 個基本假設(shè)如下:

假設(shè)1 LAS 和MC 是完全可信的.LBSS 是半可信的，一方面為用戶提供服務(wù)，另一方面有可能直接或間接地泄露用戶的隱私信息;

假設(shè)2 攻擊者可以從公共數(shù)據(jù)庫(例如:電話黃頁，家庭住址等)獲得一些先驗知識.同時，攻擊者具備較強的統(tǒng)計分析和推理能力，可以利用查詢信息和先驗知識形成后驗知識;

假設(shè)3 MC 在LAS 上注冊為合法用戶，定期向LAS 更新其位置信息;

假設(shè)4 LAS 使用的匿名算法是公開的.

定義1 查詢匿名性.匿名的本意是指在同一匿名集(AS)內(nèi)的主體是不可區(qū)分的.相對攻擊者而言，主體沒有唯一的特征標(biāo)識.匿名不是保護某一具體的主體標(biāo)識，而是使攻擊者不能建立主體與其行為動作的聯(lián)系.匿名集的量化需要一個閾值k代表匿名度，k 在一般意義下等于匿名集的勢|AS|，k 值越大，匿名效果越好.

定義2 軌跡不可追蹤性.位置軌跡可以表示為T = {Ti，(x1，y1，t1)，(x2，y2，t2)，…，(xn，yn，tn)}，其中，Ti表示該軌跡的標(biāo)識符，(xi，yi，ti)(i=1…n)表示移動對象在時刻ti的位置為(xi，yi)，ti為采樣時間.軌跡不可追蹤性是指LBSS 通過已有的先驗、查詢?nèi)罩竞秃蜻x結(jié)果集等信息，分析出用戶位置軌跡的概率很低.

圖2 Voronoi 圖GV

2 決策樹匿名

本文將LBS 服務(wù)空間映射為Voronoi 圖GV，GV中的每個單元格cell 覆蓋一個語義位置，同時每個cell 對應(yīng)一個語義位置編號No.如圖2 所示，查詢用戶的當(dāng)前cell 是指包含用戶當(dāng)前位置的語義位置，設(shè)移動用戶u 當(dāng)前位置為l，則該用戶的當(dāng)前cell 被定義為current－C(l)=Ni.LAS 和LBSS 共享GV的信息.LAS 通過GV構(gòu)建匿名決策樹，實現(xiàn)位置k－匿名和位置l－多樣性.

定義3 匿名查詢請求(Q)，查詢用戶發(fā)出的LBS 匿名查詢請求可以形式化為:

式中:I 代表用戶的身份標(biāo)識;loc代表用戶當(dāng)前位置;c 代表查詢內(nèi)容;t 代表查詢時間;k 代表匿名度;l 代表位置的多樣性;Rmin和Rmax分別代表最小和最大容忍區(qū)域;Δt 代表查詢?nèi)萑虝r間.在查詢過程中，用戶通過共享loc和c 來獲得相應(yīng)的服務(wù)，k，l保障了用戶的隱私安全，Rmin，Rmax和Δt 保證了服務(wù)質(zhì)量.

圖3 匿名決策樹

定義4 語義位置(Semantic location，S)，語義位置是一個位置范圍的描述，形式化為:

新世紀(jì)以來，中國政府在扶貧領(lǐng)域進一步加強了與全球減貧的“互動”交流。2004年5月，首次“全球扶貧大會”在我國上海召開，來自120余個國家和地區(qū)的代表在此次大會上交流扶貧經(jīng)驗，并共同簽署了《上海減貧議程》，這進一步增強了國際社會的減貧共識。2005年5月，中國國際扶貧中心成立，這一機構(gòu)架起了我國與國際組織扶貧合作與交流的重要平臺。2015年9月，在聯(lián)合國發(fā)展峰會上通過了一份關(guān)于全球減貧的新計劃——《2015年后發(fā)展議程》。

式中:No代表語義位置編號;Na代表語義位置的名稱;Rel代表與該語義位置相鄰的其他位置集合;Pro代表該語義位置的幾何物理特性的集合，包括形狀、大小、面積等信息.

為了便于表示決策樹規(guī)則，本文使用H ={S1，S2，…，Sn}代表語義位置的集合，UH代表當(dāng)前語義位置集合內(nèi)的移動用戶數(shù)量，RH代表該語義位置集合所圍成的區(qū)域面積，TH代表該位置語義集合的平均查詢時間.圖3 描述了匿名決策樹，該決策樹從位置l－多樣性、位置k－匿名、查詢?nèi)萑虆^(qū)域、查詢?nèi)萑虝r間4 個方面來決定匿名是否成功.

圖4 平均匿名時間

基于決策樹的位置匿名在LAS 內(nèi)完成，具體過程如下:

(1)從Q 中提取參數(shù)loc，k，l，Rmin，Rmax，Δt;

(2)計算current－C(loc)=No，并將No加入H;

(3)判斷是否滿足位置l－多樣性要求，如果|H|＞=l，則執(zhí)行下一步，否則，從No臨近的語義位置中隨機選擇l－1 個語義位置加入H;

(4)判斷H 所在區(qū)域內(nèi)是否存在大于k 個用戶，如果UH＞=k，則執(zhí)行下一步，否則，從No的臨近位置中選擇1 個語義位置增加到H 中，重復(fù)執(zhí)行(4);

(5)判斷RH是否符合容忍區(qū)域要求，如果Rmin=＜RH＜=Rmax，則執(zhí)行下一步，否則，匿名失敗;

(6)判斷TH是否符合容忍時間要求，如果TH＜=Δt，則匿名成功，否則，匿名失敗.

查詢內(nèi)容語義的相似性有利于提高LBSS 的檢索效率，但是，單一的查詢內(nèi)容可能導(dǎo)致查詢同質(zhì)攻擊，即LBSS 雖然不能確定查詢的發(fā)出者，但是，其根據(jù)查詢候選結(jié)果集可以斷定查詢用戶所關(guān)注的興趣點(Points of Interest，POIs).本文為了滿足查詢語義的q－多樣性，LAS 隨機產(chǎn)生q－1 個不同的查詢內(nèi)容，連同原始查詢內(nèi)容構(gòu)成查詢內(nèi)容集合.

3 分析與驗證

3.1 隱私性分析

特定的隱私保護模型僅在特定的場景下成立，當(dāng)攻擊者具有足夠多的先驗知識的情況下，隱私可能泄露.查詢匿名性、位置軌跡不可追蹤性是度量隱私保護水平的主要指標(biāo)，相關(guān)的研究工作主要是圍繞這2 個指標(biāo)來探討LBS 隱私保護技術(shù)的隱私保護能力.本文從這2 個指標(biāo)角度分析所提出方法的抗攻擊能力.

圖5 平均通信量

(1)從查詢匿名性分析.位置k－匿名是最流行的查詢隱私度量方式，給定集合U={u1，u2，…，uk}是k 個移動用戶的集合，?ui∈U 的位置坐標(biāo)位于匿名區(qū)域(Anonymous Spatial Region，ASR)內(nèi).如果攻擊者確定查詢q 由ui發(fā)出的概率為1/k，則稱ui實現(xiàn)了位置k－匿名.本文方法中的H 內(nèi)至少包含k 個用戶，符合位置k－匿名的定義，因此本文方法具有匿名性，進而不會遭受受限空間識別攻擊和觀察識別攻擊.同時，本文方法不僅實現(xiàn)了k－匿名，而且保證了查詢內(nèi)容的q－多樣性，查詢者與查詢內(nèi)容是多對多的關(guān)系，進而不會遭受查詢同質(zhì)攻擊和關(guān)聯(lián)攻擊.

(2)從位置軌跡不可追蹤性分析.位置k－匿名混淆了匿名查詢和位置隱私的概念，k－匿名可以切斷查詢和用戶身份的關(guān)聯(lián)，但是無法保證用戶的位置隱私和軌跡隱私.k 值的大小不依賴于k－ASR，在用戶密集區(qū)域，k－ASR 可能匯聚成一點(例如:一個酒吧)，在稀疏區(qū)域，k－ASR 可能很大.所以，唯一的k 值無法度量位置隱私和軌跡隱私.本文提出的匿名方法同時滿足了位置k－匿名性和位置l－多樣性.攻擊者的最小推斷區(qū)域是多個語義位置的并集，進而不會遭受位置同質(zhì)攻擊和推理攻擊.

3.2 實驗驗證

本文算法采用C#實現(xiàn)，在Intel(R)Core(TM)i3－2310M CPU 2.10GHz 處理器、4GB 內(nèi)存的Windows 7 平臺上運行.模擬數(shù)據(jù)集由業(yè)界認可的Thomas Brinkhoff 路網(wǎng)數(shù)據(jù)生成器生成，以城市Oldenburg 的交通路網(wǎng)作為輸入，生成模擬的移動用戶數(shù)據(jù)集.我們在模擬數(shù)據(jù)集上對本文方法的平均匿名時間、平均通信量進行實驗.

平均匿名時間主要受到語義位置劃分的精細程度、匿名度k 和移動用戶數(shù)量的影響，圖4(a)顯示語義位置數(shù)量影響匿名時間，語義位置數(shù)量越多越容易滿足位置l－多樣性要求，匿名時間越短.圖4(b)顯示移動用戶數(shù)量與匿名時間成反比，移動用戶數(shù)量越多越容易實現(xiàn)k－匿名，匿名時間越短.同時，從圖4(b)可以看出，匿名度k 與匿名時間成反比，即k 越大，則匿名時間越長.

平均通信量主要受到位置l－多樣性和查詢q－多樣性的影響.我們假設(shè)查詢語義的q－多樣性數(shù)量在1 到2* |H|內(nèi)隨機選取，每個POIs 消息是100kB.圖5 顯示用戶隱私要求越高，平均通信量越大.

4 結(jié)束語

大量的位置隱私研究工作基于“零和博弈”的觀點，提出了權(quán)衡服務(wù)質(zhì)量和隱私保護的方法，其中位置k－匿名、位置模糊是位置隱私研究的主流技術(shù).綜合考慮個性化匿名查詢中的各種影響因素，提出了基于決策樹的匿名方法，實現(xiàn)了個性化匿名查詢.隱私性分析表明方法具有查詢匿名性和位置軌跡不可追蹤性，并且具有一定的抗攻擊能力.實驗結(jié)果驗證了方法的平均匿名時間和平均通信量較低，可以滿足LBS 即時服務(wù)的要求.但是，隨著用戶隱私要求的提高，匿名成功率下降明顯，有待于在后續(xù)研究中進一步完善.

［1］ 王璐，孟小峰.位置大數(shù)據(jù)隱私保護研究綜述［J］.軟件學(xué)報，2014，25(4):693－712.

［2］ 楊松濤，馬春光.隨機匿名的位置隱私保護方法［J］.哈爾濱工程大學(xué)學(xué)報，2015，36(3):1－5.