唐 禹 吳正華

(電子科技大學(xué)信息與軟件工程學(xué)院 成都 611731)

近年來，基于位置的服務(wù)(LBS)變得越來越普遍，LBS提供商基于用戶的位置提供例如定位、導(dǎo)航、路線規(guī)劃、興趣點(diǎn)(POI)搜索、定制化廣告等服務(wù).其可以通過用戶移動(dòng)設(shè)備的GPS定位、蜂窩移動(dòng)網(wǎng)絡(luò)信息、WiFi信息等來獲取用戶定位.一方面，豐富的LBS便利了用戶的生活，但是另一方面，LBS也竊取了用戶的隱私，F(xiàn)echner的報(bào)告[1]顯示攻擊者可能會(huì)因?yàn)槟怖哪康倪M(jìn)行一些騷擾行為.根據(jù)Busic和Filjar的調(diào)查[2]，大多數(shù)商業(yè)LBS要求我們每隔幾分鐘更新一次定位.當(dāng)用戶連續(xù)使用LBS時(shí)情況會(huì)愈發(fā)嚴(yán)重，如果用戶的軌跡被惡意使用，通過數(shù)據(jù)挖掘[3-5]可以獲取用戶的更多隱私，包括家庭住址、愛好、生活情況、健康狀況、親密關(guān)系等.因此軌跡信息的保護(hù)得到了廣泛的應(yīng)用研究，受到國內(nèi)外學(xué)者的關(guān)注.

為了保護(hù)用戶的位置隱私，目前國內(nèi)外已有很多研究.Kato等人[6]認(rèn)為，一個(gè)能夠保證用戶位置隱私的系統(tǒng)應(yīng)該滿足以下2個(gè)條件：1)它應(yīng)該是一個(gè)封閉的系統(tǒng)，即能夠在用戶的移動(dòng)設(shè)備上部署，并且不會(huì)向外部泄露用戶的位置隱私；2)它不應(yīng)破壞用戶或LBS提供商的利益.第2個(gè)要求對(duì)于使整個(gè)生態(tài)系統(tǒng)受益至關(guān)重要.否則，沒有用戶或LBS會(huì)使用該系統(tǒng)來保護(hù)隱私.但是，前人的研究基本上是基于K-匿名算法，在真實(shí)使用中，使用者往往不具備專業(yè)知識(shí)背景，他們無法為每個(gè)LBS構(gòu)建請(qǐng)求，通常是LBS應(yīng)用直接向移動(dòng)設(shè)備請(qǐng)求位置信息，這種請(qǐng)求的結(jié)果是固定的，即某一個(gè)經(jīng)緯度標(biāo)識(shí)的點(diǎn)，也就無法通過返回給應(yīng)用多個(gè)定位數(shù)據(jù)，以實(shí)現(xiàn)K-匿名算法.

應(yīng)用在LBS中的位置隱私保護(hù)系統(tǒng)架構(gòu)主要有3類[7]：集中式模型、分布式模型和獨(dú)立式模型.其中集中式模型需要有可信的第三方服務(wù)器，分布式模型需要用戶進(jìn)行分布式組網(wǎng)，都需要外部服務(wù)或設(shè)備的幫助，而獨(dú)立式模型的隱私保護(hù)皆由用戶設(shè)備完成，不干涉外部網(wǎng)絡(luò)與服務(wù)，也與本文的研究方向最為貼切.

在獨(dú)立式模型中的軌跡隱私保護(hù)算法主要分為3種：K-匿名軌跡算法、軌跡抑制算法和虛擬軌跡算法.

軌跡抑制算法是選擇性地抑制敏感位置的發(fā)布[14]，軌跡抑制法雖然實(shí)現(xiàn)簡單，但是卻容易導(dǎo)致數(shù)據(jù)丟失，降低數(shù)據(jù)可用性.Weng等人[15]提出一種基于擾動(dòng)的軌跡數(shù)據(jù)隱藏發(fā)布方法，找到出現(xiàn)頻率低的位置節(jié)點(diǎn)來替換出現(xiàn)頻率高或有隱私泄露風(fēng)險(xiǎn)的節(jié)點(diǎn).

虛擬軌跡算法是通過對(duì)真實(shí)軌跡的處理，得到1條虛擬軌跡，此軌跡在LBS等位置服務(wù)和用戶軌跡隱私中取得折中.Duckham等人[16]提出了一種通過混淆的方式在LBS與位置隱私中取得一定平衡的框架.Ardagna提出了3種混淆策略[17]：1)通過擴(kuò)大其半徑來降低定位區(qū)域精準(zhǔn)度；2)通過移動(dòng)其中心來降低定位區(qū)域精準(zhǔn)度；3)通過減小半徑來降低定位區(qū)域精準(zhǔn)度.

本文致力于在無第三方可信服務(wù)器的情況下獨(dú)立保護(hù)用戶的位置隱私，同時(shí)為使用者提供可用的LBS.本文的方法著重于維護(hù)可用LBS和用戶位置隱私之間的平衡，通過一定的混淆策略降低用戶的位置信息質(zhì)量，以達(dá)到保護(hù)用戶位置隱私的目的.同時(shí)考慮到真實(shí)軌跡中存在的停頓現(xiàn)象及工作、住宅等地的固定點(diǎn)存在，在普通混淆策略的基礎(chǔ)上增加了停頓處理和固定點(diǎn)映射策略，使得本文的方法在擬真方面更加優(yōu)秀.在降低定位精度方面，本文創(chuàng)新性地提出了通過時(shí)延來獲取混淆區(qū)域中心，在降低定位精準(zhǔn)度的同時(shí)保證了軌跡的擬真性.

1 本文的隱私保護(hù)模型

1.1 條件假設(shè)

1.2 度量標(biāo)準(zhǔn)

為了明確在使用混淆算法前后用戶獲得的LBS差異，本文提出通過命中率AR來度量模型對(duì)于用戶獲取LBS的影響.命中率AR表示為

(1)

其中，Lr表示真實(shí)定位，Lf表示此真實(shí)定位對(duì)應(yīng)的虛擬定位，POI(L)表示在定位L處所獲得的LBS興趣點(diǎn)集合，故AR可以用通過虛假軌跡獲取到的興趣點(diǎn)集合中命中真實(shí)定位獲取到的興趣點(diǎn)集合的數(shù)量與真實(shí)定位獲取到的興趣點(diǎn)數(shù)量的比值來表示.

為表示所生成軌跡的真實(shí)性，本文提出通過判正率CR來度量生成的假軌跡被判斷為真實(shí)軌跡的概率.即所有生成軌跡中，被定性判斷為真實(shí)軌跡的軌跡條數(shù)占生成的所有軌跡條數(shù)的比例.

1.3 軌跡生成策略

本文提出的虛擬軌跡生成策略通過延遲使用，暫停處理和固定點(diǎn)映射的方法達(dá)到保護(hù)用戶軌跡隱私的目的.當(dāng)用戶使用提供LBS服務(wù)的應(yīng)用時(shí)，應(yīng)用將會(huì)通過系統(tǒng)API調(diào)用獲取當(dāng)前的定位，本策略在這一環(huán)節(jié)通過修改系統(tǒng)API返回的數(shù)據(jù)，以達(dá)到返回虛假定位、保護(hù)用戶隱私的目的，并使得此算法具有普適性，可以為無相關(guān)背景知識(shí)的用戶所使用.

1.4 延遲使用

常規(guī)的虛擬軌跡生成策略通過當(dāng)前位置生成虛擬節(jié)點(diǎn)“啞元”(dummies)，由啞元生成半徑r控制定位精準(zhǔn)度，r越大則定位精準(zhǔn)度越低，用戶隱私保護(hù)程度越高.然而一方面單一的增減r會(huì)使得軌跡無序性隨r增大而增大，即生成的虛假軌跡更容易被識(shí)別；另一方面此策略在某些情況下極易暴露用戶真實(shí)位置，如高速路出口處等位置，此時(shí)即使啞元并不在出口處，但是攻擊者也可以輕易結(jié)合時(shí)間信息推斷被攻擊者的位置.故本文的生成策略考慮到Ardagna等人[17]的研究，通過移動(dòng)區(qū)域中心的方法，降低定位精準(zhǔn)度的同時(shí)更大程度地保護(hù)用戶位置隱私.為了使虛假軌跡更加擬真(如圖1所示)，生成虛假定位的區(qū)域中心選擇一定延遲時(shí)間D之前的真實(shí)定位.

圖1 控制生成定位精準(zhǔn)度的方式

1.5 停頓處理

用戶并非一直在行走，如果用戶在某個(gè)地方停下來如觀看風(fēng)景或短暫休息，此時(shí)在以往的匿名軌跡生成算法中將會(huì)繼續(xù)在當(dāng)前節(jié)點(diǎn)周圍生成啞元，然而停留時(shí)間越長，生成的啞越有可能暴露真實(shí)定位所在.如圖2所示，在同一真實(shí)定位附近，分別生成5，20，100個(gè)虛擬定位，真實(shí)定位越來越接近所有定位的中心.故本策略擁有停頓處理功能，當(dāng)使用者停頓后，其相應(yīng)的啞元也會(huì)停頓，避免隱私泄露的風(fēng)險(xiǎn).

圖2 生成不同個(gè)數(shù)虛假定位時(shí)真實(shí)定位所在位置

1.6 固定映射

在前人的研究中很少考慮到固定的映射策略，但是固定點(diǎn)映射在反惡意檢測中有很大的作用，如果從攻擊者的角度出發(fā)，大部分使用者都會(huì)有常駐點(diǎn)，如家或工作地點(diǎn)等，可以通過判斷一段時(shí)間內(nèi)用戶有沒有常駐點(diǎn)來表明此軌跡是否是虛假軌跡，所以常駐點(diǎn)映射是十分必要的，例如當(dāng)用戶回到家之后，相應(yīng)的啞元也會(huì)最終到達(dá)一個(gè)固定點(diǎn)停留，防止攻擊者的虛假軌跡識(shí)別.而從用戶的角度出發(fā)，一段路徑中的某些點(diǎn)可能是必須暴露的，此時(shí)固定點(diǎn)映射也可以暴露出用戶指定的點(diǎn)，達(dá)到定制化的效果.

1.7 算法思路

首先得到真實(shí)軌跡集合RT，由于用戶設(shè)備本身存在定位誤差，所以需要先對(duì)真實(shí)軌跡進(jìn)行預(yù)處理，把誤差范圍內(nèi)的定位處理為同一定位，解決用戶停頓后因?yàn)槎ㄎ徽`差帶來的前后定位不一致問題.同時(shí)為了方便后續(xù)依據(jù)時(shí)延t獲取混淆區(qū)域半徑，在前t個(gè)時(shí)間內(nèi)重復(fù)第1個(gè)定位節(jié)點(diǎn).

隨后進(jìn)行啞元生成，根據(jù)處理好的真實(shí)軌跡集合中的每一個(gè)定位，在混淆半徑r內(nèi)取出1個(gè)滿足可達(dá)性的點(diǎn).即前一個(gè)啞元能夠在單位時(shí)間內(nèi)到達(dá)此啞元.在此過程中如有遇到在固定點(diǎn)映射集合M中的點(diǎn)，則啞元不必自己生成，而是從M中取得.

最后將所有啞元合并就得到了用戶的虛假軌跡，使用者可以根據(jù)需求從中提取數(shù)據(jù).

1.8 軌跡預(yù)處理

為了使延遲使用和暫停處理的算法策略更好地發(fā)揮作用，需要對(duì)用戶真實(shí)軌跡RT進(jìn)行處理，將相似定位處理為同一定位，解決移動(dòng)設(shè)備本身定位精度問題帶來的誤差，同時(shí)依據(jù)時(shí)延時(shí)間t在真實(shí)軌跡開始處不斷填充相同的起始節(jié)點(diǎn).

算法1.真實(shí)軌跡預(yù)處理算法.

步驟1.將PRT置為空集；

步驟2.重復(fù)t次；

步驟4.結(jié)束重復(fù)；

步驟8.結(jié)束遍歷；

步驟9.返回PRT.

1.9 生成虛假軌跡

在之前經(jīng)過預(yù)處理的軌跡PRT的基礎(chǔ)上，通過混淆策略和固定點(diǎn)映射策略生成虛假軌跡FT.

算法2.虛假軌跡生成算法.

步驟1.將FT置為空集；/*生成與PRT中定位數(shù)對(duì)應(yīng)的FT*/

步驟7.結(jié)束遍歷；

步驟8.返回FT.

2 實(shí)驗(yàn)與數(shù)據(jù)分析

本文使用微軟亞洲研究院收集的軌跡數(shù)據(jù)集Geolife[18-20]，使用了其182個(gè)用戶在2007-04—2012-08期間記錄的24 876 978個(gè)點(diǎn)表示的GPS軌跡的數(shù)據(jù)，本實(shí)驗(yàn)代碼由Python3.8.3編寫，實(shí)驗(yàn)環(huán)境為macOS 10.15.7操作系統(tǒng).實(shí)驗(yàn)中的POI(L)即定位L處的周圍興趣點(diǎn)通過調(diào)用高德地圖開放平臺(tái)接口獲取，平均距離s指混淆區(qū)域中心與原定位的平均歐氏距離.

2.1 時(shí)延t對(duì)命中率AR的影響

由于不同用戶對(duì)于POI(興趣點(diǎn))搜索的需求范圍不同，我們使用了3種搜索范圍，分別是300 m，1 000 m和3 000 m，即在這3種POI搜索范圍中探究時(shí)延t與命中率AR的關(guān)系：命中率1表示在搜索附近300 m時(shí)POI的命中率；命中率2表示在搜索附近1 000 m時(shí)POI的命中率；命中率3表示在搜索附近3 000 m時(shí)POI的命中率.實(shí)驗(yàn)表明，當(dāng)用戶對(duì)POI搜索距離較大時(shí)，延遲對(duì)命中率影響較小，在3 000 m時(shí)POI搜索范圍的情況下，即使時(shí)延300 s也可以達(dá)到超過94%的命中率.

2.2 混淆區(qū)域半徑r對(duì)命中率AR的影響

在POI查詢距離分別為300 m時(shí)，時(shí)延對(duì)命中率的影響如圖4所示，當(dāng)POI的查詢范圍為3 000 m時(shí)，時(shí)延對(duì)命中率的影響如圖5所示，此時(shí)時(shí)延對(duì)命中率的影響非常小，同時(shí)從圖3可以看出，時(shí)延越長，時(shí)延后的節(jié)點(diǎn)與原節(jié)點(diǎn)歐氏距離越遠(yuǎn)，即混淆效果越好，但當(dāng)POI范圍較近時(shí)，時(shí)延對(duì)命中率的影響較大.

圖3 時(shí)延t對(duì)命中率的影響

圖4 POI查詢范圍為300 m時(shí)混淆半徑對(duì)命中率的影響

圖5 POI查詢范圍為3 000 m時(shí)混淆半徑對(duì)命中率的影響

2.3 與以往方案對(duì)比

此次實(shí)驗(yàn)位置采樣設(shè)置為每5秒1次，混淆半徑為10 m，分別對(duì)比了隨機(jī)法、軌跡旋轉(zhuǎn)法和本文的方法所生成軌跡的判正率CR和命中率方差A(yù)RV.

在以往關(guān)于虛擬軌跡算法的研究中，并沒有對(duì)軌跡的擬真性提出量化標(biāo)準(zhǔn)，本文實(shí)驗(yàn)通過判正率這一判斷指標(biāo)對(duì)各方法進(jìn)行定性比較.

由圖6可知，隨著平均距離的增大，通過隨機(jī)法生成的軌跡迅速失去真實(shí)性，極易被判斷為假軌跡，而本文的策略與軌跡旋轉(zhuǎn)法生成的軌跡則基本不受平均距離的影響，具有較高的真實(shí)性.

圖6 不同方法的判正率

如圖7所示，本文的策略在POI命中率的方差上與隨機(jī)法是一個(gè)量級(jí)，遠(yuǎn)低于軌跡旋轉(zhuǎn)法，保證了LBS的穩(wěn)定可用.

圖7 不同方法的命中率方差

3 結(jié)束語

目前基于LBS的位置隱私保護(hù)主要集中在K-匿名算法等模型上，然而此類模型要求使用者具有相應(yīng)的背景知識(shí)，不適宜作為普適的解決方案，對(duì)于沒有背景知識(shí)的普通使用者來說，在位置隱私保護(hù)和LBS中取折中的混淆算法無疑是更佳的選擇.本文在以往研究的基礎(chǔ)上，采用了延時(shí)處理、停頓處理、固定點(diǎn)映射等策略，提出了一種更優(yōu)的保護(hù)使用者位置隱私的混淆策略.相比于以往的混淆策略，通過隨機(jī)法生成的軌跡隨著混淆中心的位移長度增加，軌跡呈現(xiàn)混沌的趨勢(shì)，與真實(shí)軌跡不符，通過軌跡旋轉(zhuǎn)法生成的虛假軌跡雖然具有較高的真實(shí)性，但是在POI命中率上容易出現(xiàn)極端情況，本文的策略則表現(xiàn)出了更好的擬真性與穩(wěn)定性.

下一步的研究工作主要包含：

1)本文所采用的數(shù)據(jù)集主要分布在北京市，建筑密集，POI集中，而對(duì)于人口稀疏、POI較少的地區(qū)的處理有待進(jìn)一步研究；

2)本文主要關(guān)注的步行軌跡，針對(duì)騎行、公共交通或駕車等速度更快的情況缺乏探討，基于時(shí)延等策略的混淆是否有效還需要驗(yàn)證，適用于這些情況的更好的混淆策略也還需進(jìn)一步研究.