嚴(yán)少均，王子馳，張新鵬

上海大學(xué)通信與信息工程學(xué)院，上海200444

隨著移動(dòng)設(shè)備的普及，用戶可以享受的位置服務(wù)越來(lái)越豐富.然而用戶在享受快捷服務(wù)的同時(shí)也面臨隱私泄露的問(wèn)題.2018年4月28日，全球領(lǐng)先的新經(jīng)濟(jì)行業(yè)數(shù)據(jù)挖掘和分析機(jī)構(gòu)iiMedia Research（艾媒咨詢）權(quán)威發(fā)布《2018 中國(guó)手機(jī)APP 隱私權(quán)限測(cè)評(píng)報(bào)告》指出，移動(dòng)社交及網(wǎng)購(gòu)類APP 調(diào)用定位權(quán)限占比高達(dá)96.7%.當(dāng)攻擊者掌握用戶的位置隱私后，攻擊者可以向用戶推送廣告來(lái)獲益或者推送片面信息引導(dǎo)輿論，更有甚者可以通過(guò)用戶的位置以及軌跡信息推斷出用戶的身份信息，以致對(duì)人身安全造成影響.因此，保護(hù)位置信息意義重大[1-3].

目前保護(hù)位置信息的系統(tǒng)架構(gòu)主要分為分布式架構(gòu)[4-5]和中心式架構(gòu)[6-7].其中分布式架構(gòu)中包括用戶群和服務(wù)器，如圖1所示，用戶在發(fā)起查詢請(qǐng)求前先在P2P（點(diǎn)對(duì)點(diǎn)）群內(nèi)自行構(gòu)建匿名區(qū)域（如匿名矩形區(qū)域或匿名圓形區(qū)域）來(lái)代替區(qū)域內(nèi)的若干個(gè)用戶.組內(nèi)的所有用戶共同分擔(dān)查詢?nèi)蝿?wù)并共享查詢結(jié)果.但該架構(gòu)所需通信帶寬大，對(duì)用戶終端計(jì)算能力依賴強(qiáng)，且當(dāng)用戶群中出現(xiàn)惡意攻擊者時(shí)無(wú)法采取防范措施.此外，由于在用戶端對(duì)位置信息進(jìn)行了模糊處理，服務(wù)質(zhì)量也會(huì)降低.與分布式架構(gòu)不同，中心式架構(gòu)通過(guò)引入一個(gè)可信第三方來(lái)對(duì)用戶的信息進(jìn)行預(yù)處理.如圖2所示，引入可信第三方后，用戶不需要對(duì)自己的位置坐標(biāo)進(jìn)行處理，而是直接把定位信息發(fā)送給可信第三方.可信第三方將地理位置上聚集的用戶群構(gòu)建出匿名區(qū)域后向服務(wù)器發(fā)起匿名請(qǐng)求，之后對(duì)返回的結(jié)果進(jìn)行過(guò)濾后分別分配給不同ID 的用戶.該架構(gòu)在保證安全性的前提下有效地提升了用戶的服務(wù)質(zhì)量.

圖1 分布式架構(gòu)Figure1 Distributed architecture

圖2 中心式架構(gòu)Figure2 Central architecture

在上述兩種架構(gòu)中，保護(hù)的隱私信息主要分為單次查詢的點(diǎn)位置坐標(biāo)信息[8]與連續(xù)查詢的軌跡信息[9].針對(duì)單次查詢中點(diǎn)位置信息的保護(hù)，主要是采用k-匿名的方法，其目的是無(wú)法讓服務(wù)器無(wú)法在k個(gè)用戶中區(qū)分出真實(shí)用戶，從而達(dá)到保護(hù)用戶的目的.但對(duì)于同樣的單點(diǎn)用戶k-匿名方法應(yīng)用到軌跡保護(hù)中則效果不理想.主要原因是軌跡信息不但包含點(diǎn)位置坐標(biāo)，而且軌跡位置坐標(biāo)之間還包含了時(shí)序信息.攻擊者可以根據(jù)軌跡在時(shí)間上的趨勢(shì)還原出用戶的軌跡信息，從而推斷出用戶的敏感屬性.如圖3所示，用戶（黑色五角星）在連續(xù)3 個(gè)時(shí)刻都滿足k=4 的匿名要求，但是匿名區(qū)域中心所連接出來(lái)的軌跡（藍(lán)色軌跡線條）和原軌跡（紅色軌跡線條）是類似的，隨著連續(xù)請(qǐng)求的密度逐漸增大這個(gè)現(xiàn)象會(huì)更加明顯.在此基礎(chǔ)上進(jìn)行改進(jìn)的方法有軌跡的k-匿名法[10]，該方法要求有k條難以互相區(qū)分的軌跡.但是在城市路網(wǎng)環(huán)境中，當(dāng)攻擊者知道城市地圖時(shí)，其實(shí)很多條偽軌跡不可能存在，如城市中的湖泊、單行道等.此外其余k ?1 條軌跡所帶來(lái)的計(jì)算負(fù)擔(dān)會(huì)很大，影響時(shí)效性.文獻(xiàn)[11]利用周圍伙伴一跳內(nèi)的位置數(shù)據(jù)共享來(lái)將服務(wù)器端的連續(xù)軌跡斷開(kāi)，從而使攻擊者無(wú)法在兩個(gè)時(shí)間間隔較大的點(diǎn)內(nèi)判斷出軌跡.但是該方法不能保證用戶下一跳的位置點(diǎn)剛好被伙伴緩存，所以有一定概率使得軌跡斷點(diǎn)失效，此外為了下一跳的緩存數(shù)據(jù)需要周圍一跳內(nèi)的所有用戶一起加入請(qǐng)求，可見(jiàn)所耗費(fèi)的資源以及通信代價(jià)過(guò)高.

圖3 連續(xù)查詢的k-匿名圖示Figure3 K-anonymous for continuous query

上述工作有效解決了單次查詢中的隱私保護(hù)問(wèn)題，但對(duì)連續(xù)查詢中軌跡隱私的保護(hù)方法并不完善.軌跡隱私中的保護(hù)方法浪費(fèi)了大量的通信帶寬，故不能在實(shí)用性和安全性上取得一個(gè)較好的權(quán)衡.針對(duì)軌跡保護(hù)方法[11]中緩存利用率低以及匿名區(qū)域不合理的問(wèn)題，本文在系統(tǒng)中引入了改進(jìn)的長(zhǎng)短期記憶(long short-term memory,LSTM)網(wǎng)絡(luò).本網(wǎng)絡(luò)利用用戶軌跡的時(shí)序信息有效提高軌跡的預(yù)測(cè)準(zhǔn)確率.在此基礎(chǔ)上，將預(yù)測(cè)位置放入當(dāng)前時(shí)刻進(jìn)行匿名區(qū)域的構(gòu)造，從而使得匿名區(qū)域更加合理，達(dá)到了隱私保護(hù)的效果.文中所提出的軌跡隱私保護(hù)方法能有效地提升緩存命中率，減少服務(wù)器有效請(qǐng)求次數(shù)，從而在保證軌跡服務(wù)質(zhì)量的同時(shí)防止服務(wù)器推斷出用戶的隱私信息.

1 基于LSTM 網(wǎng)絡(luò)的位置預(yù)測(cè)與基于時(shí)序匿名的軌跡保護(hù)

LSTM 網(wǎng)絡(luò)是一種時(shí)間遞歸神經(jīng)網(wǎng)絡(luò)，適合處理和預(yù)測(cè)時(shí)間序列中間隔和延遲非常長(zhǎng)的重要事件，是一種非線性模型，可以用來(lái)構(gòu)造一些大型的深度神經(jīng)網(wǎng)絡(luò).不同于傳統(tǒng)的循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network,RNN)，LSTM 可以記憶不定時(shí)間長(zhǎng)度的數(shù)值，其內(nèi)部有一個(gè)門模塊能夠決定輸入是否需要被長(zhǎng)時(shí)間記住以及是否需要輸出.時(shí)序匿名是一種從時(shí)間維度上進(jìn)行匿名的方法，原始的匿名方案將不同時(shí)間點(diǎn)的用戶單獨(dú)考慮，存在匿名者參與不夠?qū)е履涿麉^(qū)域不合理的狀態(tài)；時(shí)序匿名將前后時(shí)間點(diǎn)的用戶放入同一個(gè)匿名區(qū)中，既可以完善本次請(qǐng)求的匿名合理性，又可以預(yù)測(cè)將來(lái)時(shí)刻的請(qǐng)求.本文將LSTM 網(wǎng)絡(luò)應(yīng)用于城市軌跡隱私保護(hù)中，可信第三方利用該LSTM 模型預(yù)測(cè)出用戶在將來(lái)時(shí)刻的位置點(diǎn)信息.之后可信第三方通過(guò)提前發(fā)起未來(lái)的請(qǐng)求來(lái)擾亂服務(wù)器端用戶的軌跡信息.這一做法使得軌跡的時(shí)序信息被打亂，一方面使得匿名區(qū)域的構(gòu)建更加合理，另一方面由于將來(lái)時(shí)刻的請(qǐng)求結(jié)果被提前緩存以供后續(xù)進(jìn)行請(qǐng)求應(yīng)答，保證了后續(xù)請(qǐng)求的服務(wù)質(zhì)量.此時(shí)在攻擊者看來(lái)，用戶的軌跡產(chǎn)生了多種可能性，達(dá)到了軌跡隱私和服務(wù)質(zhì)量之間權(quán)衡的目的.

1.1 系統(tǒng)描述

考慮到LSTM 模型在弱計(jì)算能力的終端運(yùn)行可能會(huì)影響時(shí)效性，本文采用的系統(tǒng)為改進(jìn)的中心式架構(gòu).該系統(tǒng)包含了用戶、可信第三方和服務(wù)器3 部分，其工作過(guò)程如圖4所示.

圖4 本文系統(tǒng)工作過(guò)程Figure4 Working process of the proposed system

首先，用戶會(huì)在本地生成當(dāng)前時(shí)刻的請(qǐng)求信息MSGT:{ID,Loc,T,Q,V}.其中：ID 表示用戶的唯一身份標(biāo)識(shí)，如IP 地址等；Loc 表示用戶的經(jīng)緯度定位信息；Q表示用戶的查詢內(nèi)容，T表示此次發(fā)起請(qǐng)求的時(shí)刻點(diǎn)；V表示用戶的速度.

之后可信第三方收集各個(gè)用戶的請(qǐng)求信息，根據(jù)不同用戶的MSGT分別預(yù)測(cè)出將來(lái)若干個(gè)時(shí)序的位置點(diǎn)信息MSGT+1,MSGT+2,···,MSGT+n.然后，第三方先拷貝一份存取到本地?cái)?shù)據(jù)庫(kù)中以供后續(xù)的ID匹配，之后將請(qǐng)求信息去ID后根據(jù)用戶隱私預(yù)算k，將用戶的位置信息劃分成多個(gè)匿名區(qū)域，此時(shí)得到的信息為，其中為匿名區(qū)域，為Q的集合，可以參考圖3中的矩形部分(隱私預(yù)算為k=4).因?yàn)榇颂幈疚目紤]的背景是用戶的連續(xù)請(qǐng)求，所以在該時(shí)間段內(nèi)用戶的請(qǐng)求內(nèi)容保持不變.為該匿名區(qū)域內(nèi)不同ID 的用戶所發(fā)起的請(qǐng)求內(nèi)容Q的集合.

服務(wù)器得到此信息后在數(shù)據(jù)庫(kù)進(jìn)行服務(wù)請(qǐng)求查找，此時(shí)由于地理位置經(jīng)過(guò)了匿名化處理，服務(wù)器只能獲知用戶位置的一個(gè)范圍而無(wú)法確定具體位置.服務(wù)器根據(jù)同一匿名區(qū)域中不同的，返回該請(qǐng)求結(jié)果POIs(興趣點(diǎn)集合)，POIs 包含了集合中所有請(qǐng)求的結(jié)果值.匿名者收到POIs 后根據(jù)之前在本地拷貝的數(shù)據(jù)集進(jìn)行一一匹配，之后根據(jù)該時(shí)刻不同用戶的請(qǐng)求將POI 信息返回給用戶.因?yàn)榇藭r(shí)已經(jīng)緩存了后續(xù)若干個(gè)時(shí)刻的用戶POI結(jié)果，所以當(dāng)用戶在下一個(gè)預(yù)測(cè)點(diǎn)附近發(fā)起請(qǐng)求時(shí)，可信第三方不會(huì)將當(dāng)前準(zhǔn)確位置發(fā)送給服務(wù)器發(fā)起查詢，而是隨機(jī)產(chǎn)生一個(gè)偏離準(zhǔn)確位置的假位置來(lái)混淆服務(wù)器，同時(shí)直接利用服務(wù)器上次的緩存信息返回匿名組的查詢信息.

本方法通過(guò)減少真實(shí)軌跡信息與服務(wù)器的通信次數(shù)來(lái)保證隱私免受泄露，通過(guò)緩存的POIs 信息同樣由第三方進(jìn)行一一匹配后返回給用戶來(lái)保證請(qǐng)求結(jié)果的準(zhǔn)確性.

1.2 基于LSTM 的位置預(yù)測(cè)

LSTM 是一種RNN 的特殊類型.區(qū)別于傳統(tǒng)RNN，LSTM 在算法中加入了模擬生物細(xì)胞的結(jié)構(gòu)單元(cell)，用于判斷處理信息是否有用.一個(gè)cell 中包含了3 個(gè)門：輸入門、遺忘門和輸出門.當(dāng)信息進(jìn)入LSTM 網(wǎng)絡(luò)當(dāng)中時(shí)，可以根據(jù)算法的規(guī)則來(lái)判斷是否有用，決定是保留還是遺忘該信息，從而有效解決傳統(tǒng)RNN 所帶來(lái)的梯度消失以及梯度爆炸問(wèn)題.LSTM 適用于處理和預(yù)測(cè)基于時(shí)間序列的相關(guān)事件，目前已應(yīng)用于眾多領(lǐng)域[12]，包括自然語(yǔ)言處理以及語(yǔ)音識(shí)別[13-14]等，但將此技術(shù)應(yīng)用于隱私保護(hù)領(lǐng)域的文獻(xiàn)較少.本文將LSTM 網(wǎng)絡(luò)應(yīng)用于城市軌跡預(yù)測(cè)中，依靠準(zhǔn)確的預(yù)測(cè)結(jié)果來(lái)保護(hù)用戶的軌跡隱私.

圖5展示了本文所采用的網(wǎng)絡(luò)結(jié)構(gòu)，考慮到用戶軌跡會(huì)因?yàn)榻煌ǚ绞降牟煌瑢?duì)軌跡產(chǎn)生速度和方向上的影響，本文提取每一段軌跡數(shù)據(jù)的交通方式作為模型的一個(gè)輸入，并以此特征數(shù)據(jù)作為模型的旁路分支來(lái)優(yōu)化模型結(jié)果，再將分段篩選清理后的軌跡數(shù)據(jù)送入模型中訓(xùn)練，根據(jù)梯度下降和反向傳播算法進(jìn)行參數(shù)修正.

圖5 LSTM 網(wǎng)絡(luò)結(jié)構(gòu)圖Figure5 Network structure diagram of LSTM

1.3 基于時(shí)序匿名的軌跡保護(hù)

如圖6所示，不同顏色的幾何圖形表示不同ID 的設(shè)備(可以是不同交通方式，且這些方式在發(fā)起連續(xù)請(qǐng)求時(shí)的時(shí)間間隔和運(yùn)行速度范圍都有所不同)，未填充幾何圖形表示將來(lái)時(shí)刻預(yù)測(cè)的點(diǎn)位置信息，數(shù)字表示將來(lái)第n時(shí)刻的位置，虛線表示匿名區(qū)域.

傳統(tǒng)匿名區(qū)域的形成都是同一時(shí)刻的點(diǎn)位置信息，本方法利用一時(shí)間段內(nèi)的連續(xù)時(shí)序點(diǎn)來(lái)構(gòu)造匿名區(qū)域.使用本方法后，在一定程度上將時(shí)序強(qiáng)相關(guān)性的軌跡查詢轉(zhuǎn)換為時(shí)序弱相關(guān)性的點(diǎn)位置查詢，同時(shí)利用連續(xù)時(shí)序的用戶點(diǎn)位置信息來(lái)構(gòu)造匿名區(qū)域可以有效解決匿名位置數(shù)量不足的問(wèn)題.因?yàn)榇藭r(shí)匿名集合中的位置都是之后時(shí)序可能出現(xiàn)的，所以本方法可在減少無(wú)用虛擬位置的基礎(chǔ)上提高緩存利用率.同時(shí)利用了緩存作為之后時(shí)刻的應(yīng)答資源，減少了用戶對(duì)服務(wù)器的有效查詢請(qǐng)求，這樣服務(wù)器端得到的用戶軌跡會(huì)更模糊，從而在不影響連續(xù)請(qǐng)求服務(wù)質(zhì)量的前提下保護(hù)了軌跡隱私.

取t1、t2、t3這3 個(gè)時(shí)刻的4 個(gè)用戶為例，當(dāng)隱私預(yù)算k=4時(shí)，傳統(tǒng)方法和本文方法中查詢單元的分布如圖7所示，其中3 種由淺到深的顏色表示連續(xù)增長(zhǎng)的t1、t2、t3這3 個(gè)時(shí)刻.其上半部分說(shuō)明了傳統(tǒng)k-匿名方法對(duì)于軌跡查詢的無(wú)效性，并與圖3對(duì)應(yīng).可以發(fā)現(xiàn)雖然每一時(shí)刻都進(jìn)行了位置匿名，但是軌跡的連續(xù)性導(dǎo)致隱私依然泄露.圖7的下半部分是應(yīng)用了本文提出的預(yù)測(cè)模型后進(jìn)行的軌跡查詢，相較于傳統(tǒng)方法，因?yàn)檫M(jìn)行了軌跡預(yù)測(cè)，所以同一匿名區(qū)域內(nèi)存在不同時(shí)刻的同一用戶，匿名區(qū)域的構(gòu)造不再局限于時(shí)間維度.本方法增加了軌跡點(diǎn)之間的混亂程度，使得用戶真實(shí)軌跡與服務(wù)器根據(jù)用戶請(qǐng)求時(shí)間恢復(fù)出來(lái)的軌跡存在差異，從而使攻擊者無(wú)法準(zhǔn)確判斷用戶軌跡，保護(hù)了軌跡隱私.

圖6 匿名區(qū)域Figure6 Anonymous area

圖7 查詢單元的分布Figure7 Distribution of the query cell

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)條件

Thomas Brinkhoff[15]是常用的基于互聯(lián)網(wǎng)絡(luò)的移動(dòng)對(duì)象生成器，采用了德國(guó)奧爾登堡的地圖作為實(shí)驗(yàn)背景.下面的實(shí)驗(yàn)數(shù)據(jù)都是由該生成器生成的.本文所用的數(shù)據(jù)集包含57 260 個(gè)點(diǎn)位置信息，我們將數(shù)據(jù)集按占比劃分為10%和90%兩組，利用90%的數(shù)據(jù)集來(lái)進(jìn)行模型訓(xùn)練，其余的數(shù)據(jù)進(jìn)行模型驗(yàn)證.

已知真實(shí)軌跡Tt={T1,T2,T3,···,Ti}和預(yù)測(cè)軌跡Tp={Tp1,Tp2,Tp3,···,Tpi}，D(t,p)表示空間中t和p兩點(diǎn)間的歐氏距離，η表示閾值，當(dāng)D(t,p)<η時(shí)表示預(yù)測(cè)位置準(zhǔn)確，定義軌跡點(diǎn)的預(yù)測(cè)準(zhǔn)確度為

本文通過(guò)預(yù)測(cè)準(zhǔn)確率來(lái)衡量模型的預(yù)測(cè)效果，預(yù)測(cè)準(zhǔn)確率為

式中，LT p為預(yù)測(cè)的軌跡序列Tp的長(zhǎng)度.

2.2 軌跡預(yù)測(cè)及服務(wù)質(zhì)量

根據(jù)預(yù)測(cè)前已知位置序列的長(zhǎng)度不同來(lái)預(yù)測(cè)接下來(lái)某幾個(gè)時(shí)刻點(diǎn)的位置信息，如A(3→1)字段表示根據(jù)3 個(gè)連續(xù)時(shí)刻的軌跡點(diǎn)信息，預(yù)測(cè)將來(lái)一個(gè)時(shí)刻的位置信息.表1展示了不同閾值下本文方法與基準(zhǔn)算法[15]進(jìn)行位置預(yù)測(cè)的準(zhǔn)確率.

表1 不同閾值下本文方法與基準(zhǔn)算法進(jìn)行位置預(yù)測(cè)的準(zhǔn)確性Table1 Accuracy of location prediction based on the proposed method and benchmark algorithm under different thresholds

相較于基準(zhǔn)算法，本文所提出的模型就預(yù)測(cè)的準(zhǔn)確率而言有了較大的提升，用戶根據(jù)預(yù)測(cè)軌跡值能夠較好地保護(hù)軌跡信息.考慮到極端情況下需要預(yù)測(cè)連續(xù)時(shí)刻的位置精度，從表1的數(shù)據(jù)中發(fā)現(xiàn)本文方法的準(zhǔn)確率還是高于基準(zhǔn)算法的準(zhǔn)確率，當(dāng)η<50 時(shí)，A(3→2)，A(4→2)，A(4→3)的預(yù)測(cè)值都處于40%～50%之間，且發(fā)現(xiàn)已知軌跡點(diǎn)信息數(shù)和預(yù)測(cè)軌跡點(diǎn)準(zhǔn)確率是正相關(guān)的，即說(shuō)明了軌跡之間的時(shí)間相關(guān)性.其中當(dāng)我們僅根據(jù)當(dāng)前值預(yù)測(cè)未來(lái)值時(shí)，準(zhǔn)確率反而低于基準(zhǔn)算法，這恰好說(shuō)明因?yàn)橛脩糗壽E具有隨機(jī)性，所以在不利用時(shí)序信息的前提下很難提高預(yù)測(cè)準(zhǔn)確率.

為了進(jìn)一步說(shuō)明本文方法的有效性，本文對(duì)相同數(shù)據(jù)集是否采用該模型分別進(jìn)行對(duì)比分析.從圖8中可以看出，采用該方法(即當(dāng)前時(shí)刻+預(yù)測(cè)時(shí)刻)所構(gòu)建的匿名區(qū)域更加合理，從根本上減少了通信帶寬.此外，本文在數(shù)據(jù)集的地理位置中隨機(jī)加入1 000 個(gè)興趣點(diǎn)，根據(jù)不同用戶的請(qǐng)求分別統(tǒng)計(jì)了各自返回的興趣點(diǎn)數(shù)量.對(duì)興趣點(diǎn)數(shù)量的求和，結(jié)果見(jiàn)圖9，采用該模型的方法所獲取的興趣點(diǎn)少于未采用該模型的方法所獲取的興趣點(diǎn)，這意味著服務(wù)質(zhì)量更精確，能進(jìn)一步減少篩選興趣點(diǎn)的資源損耗.興趣點(diǎn)的總數(shù)能夠衡量所采用的方法是否有助于提升系統(tǒng)服務(wù)質(zhì)量，是衡量系統(tǒng)實(shí)用性的一個(gè)指標(biāo).

圖8 模型對(duì)匿名區(qū)域面積的影響Figure8 Impact of the model on the anonymous area

圖9 模型對(duì)返回興趣點(diǎn)的影響Figure9 Impact of the model on the returned POIs

3 結(jié) 語(yǔ)

本文采用了改進(jìn)的LSTM，在預(yù)測(cè)精度上取得了明顯的提升.系統(tǒng)在保證服務(wù)質(zhì)量的同時(shí)減少了用戶與服務(wù)器之間的有效訪問(wèn)次數(shù)，模糊了服務(wù)器端用戶的軌跡信息，從而提升了隱私保護(hù)效果.此外，本文比較了是否采用該方法的系統(tǒng)對(duì)用戶服務(wù)質(zhì)量的影響.實(shí)驗(yàn)結(jié)果表明，本方法不但混淆了軌跡的時(shí)序性，而且使匿名區(qū)域的構(gòu)造更加合理.另外利用預(yù)測(cè)的緩存應(yīng)答資源也能有效保證服務(wù)質(zhì)量.下一步的工作一方面可以通過(guò)改善模型來(lái)提高預(yù)測(cè)精度，另一方面可以考慮能否在第三方不可信的情況下完成整個(gè)服務(wù)流程，使得用戶隱私的安全性得到進(jìn)一步提升.