融合語義信息的時空關聯位置隱私保護方法

左開中，劉 蕊，趙 俊，諶章義，陳付龍

(1.安徽師范大學 計算機與信息學院，安徽 蕪湖 241002；2.安徽師范大學 網絡與信息安全安徽省重點實驗室，安徽 蕪湖 241002)

21世紀之后，空間定位技術、無線網絡通信技術和移動互聯網絡的發展速度越來越快，手機等智能設備的計算能力、存儲能力、通信能力也有了顯著的提高，手機用戶的數量也處于不斷上升的趨勢。中國互聯網絡信息中心在2021年2月發布的《中國互聯網絡發展狀況統計報告》[1]表明：截至2020年12月，我國上網人數高達9.89億，約占全國總人口的70.4%。其中，使用手機上網的人數為9.86億，占比高達99.7%。因此，基于位置的服務(Location Based Service，LBS)得到了廣泛的應用。

但是，用戶在享受便捷服務的同時也受到了相應的威脅[2]。2017年8月，“微信發送原圖導致位置隱私泄露”的帖子迅速刷爆各大信息平臺。智能數碼設備和手機在拍照時會主動收集拍攝的精確位置信息是導致位置隱私泄露的根本原因。同時，拍攝日期、時間、手機型號等內容一覽無遺。熱心的網友經過測試還發現無論是使用微信、郵件、微博或者其他的信息傳輸工具都存在位置隱私泄露的問題。這對于喜愛游山玩水又樂于向朋友時刻分享動態的人來說，無疑是一顆重磅炸彈。

為了使用戶可以安全地使用基于位置的服務避免位置隱私泄露，國內外學者針對自由空間、路網空間等環境提出了匿名、假位置、混合區域以及加密等多種技術手段[3]。其中，基于假位置的隱私保護技術是常用位置隱私保護手段之一[4-8]。它是指通過構建假位置替代用戶真實位置發出服務查詢請求或者構建多個假位置和用戶真實位置構成匿名集發出查詢請求，以達到保護用戶實際位置的效果。從假位置方法的原理和實現兩個層面來講，它都屬于易理解、操作性強的隱私保護方法。而假軌跡方法是在假位置方法的基礎上形成假軌跡來降低攻擊者識別真實軌跡的概率。但是，在連續請求服務中，傳統的假軌跡隱私保護方法往往生成多條假軌跡混淆用戶真實軌跡，但是假軌跡中語義位置的移動不符合用戶行為規律，增加了真實軌跡暴露的概率。

如圖1所示，假設某公司職員Bob于17：30從A公司出發與朋友在L影院有約，然后途徑B超市購物后回到家庭住址C小區。因此Bob有一條從A公司→L影院→B超市→C小區的移動軌跡，通過假軌跡方法構建了一條從G銀行→F餐館→H醫院→M學校的移動軌跡。但是M學校開門時間為8：00—16：30，且攻擊者挖掘用戶Bob的軌跡信息得知該用戶從H醫院移動到M學校的概率為0，從而推測出從G銀行→F餐館→H醫院→M學校的移動軌跡為一條假軌跡，導致用戶Bob的真實軌跡很容易被攻擊者識破。

圖1 用戶真實軌跡和假軌跡

針對上述問題，筆者提出融合語義信息的時空關聯位置隱私保護方法。首先，將用戶歷史移動數據規律與用戶當前位置語義信息相結合構建用戶行為模型；然后，根據該模型構建假軌跡并充分考慮相鄰時刻位置間的時空關聯性。筆者的貢獻在于：

(1) 綜合考慮了時空關聯性、位置語義信息和用戶的行為規律，提出了時空關聯匿名集生成算法；

(2) 基于真實的數據集，將筆者提出的算法與現有的算法進行比較，表明筆者提出的算法有效地降低了隱私泄露的風險。

1 相關工作

考慮攻擊者挖掘用戶的歷史請求信息，NIU等[5]提出了最大化熵和匿名區域的多目標優化算法，使得假位置盡可能地分散來保護用戶位置隱私。夏興有等[9]設計了一種基于半可信第三方服務器的隱私保護體系結構，利用歷史查詢概率選擇假位置，同時采用博弈模型對生成的假位置候選集進行博弈，從而得到最優匿名集。

針對攻擊者掌握位置的語義特征信息，CHEN等[10]通過構建位置語義樹使用樹節點之間的跳數來量化語義間的距離，同時考慮了位置的語義多樣性和物理分散性。MA等[11]挖掘語義信息并引入距離公式計算語義相似度，利用可調整余弦相似度計算用戶間相似性使得攻擊者無法識別出真實用戶的同時有效地抵御語義推斷攻擊。LI等[12]為解決語義同質攻擊問題提出一種語義感知模型，并設計了一種在服務質量和隱私要求之間取得平衡的貪婪算法。

在此基礎上，王潔等[13]綜合考慮上述問題，提出了基于位置語義信息和查詢概率的假位置選擇算法，避免了攻擊者結合背景知識過濾假位置，同時保證了假位置之間語義差異性和查詢結果的精確性。

在連續請求服務的場景下，李洪濤等[2]基于路網拓撲關系對路段的敏感程度進行等級劃分，提出了差分隱私位置保護機制實現了對用戶位置隱私的保護。周長利等[14]針對連續查詢過程中面臨用戶位置隱私和查詢內容隱私的雙重問題，設計了以道路頂點為中心的興趣點結構，降低查詢次數，提高查詢準確率。鄭磊等[15]通過馬爾科夫模型對用戶位置進行預測，提出了一種基于緩存的位置匿名選擇算法來構建匿名區域，從而抵御利用背景信息造成的推斷攻擊。

針對攻擊者掌握的位置可達性背景知識，TAKBIRI等[16]針對用戶個性化的隱私需求，通過跟蹤分析用戶真實位置的時間相關性，提出與之匹配的用戶匿名和數據模糊尺度。李維皓等[17]考慮到空間和時間之間的關聯性，選取與偽位置關聯的偽查詢內容，提出了基于偽位置生成的時空關聯隱私保護方案，在保護用戶的位置隱私的同時能夠更好地保護查詢隱私。WANG等[18]基于用戶隱私要求和實時位置信息，采用貪婪策略生成安全的匿名區域，然后計算不同時間匿名用戶集的交集，利用動態假名機制更新用戶身份信息。

另外，劉海等[19-20]考慮到連續查詢請求中相鄰位置集的時空關聯性，設計了連續合理性檢查算法篩選假位置，然后從單點的隱私保護程度進行二次篩選，以確保假軌跡的真實性。周佳琪等[21]針對攻擊者掌握的時空可達、位置語義特征、用戶歷史請求特征等背景知識提出了一種基于時空關聯和位置語義的三重假位置篩選方案——位置是否可達、語義是否相近、與用戶歷史請求特征是否接近，從而降低假位置被識別的概率，提升隱私保護程度。但是上述方法中假位置構成的假軌跡不符合用戶行為規律，增加真實軌跡暴露的概率。

綜合考慮時空關聯性、位置語義信息和用戶行為規律，筆者提出了時空關聯匿名集生成算法，可有效地降低攻擊者在擁有用戶行為規律等背景知識情況下用戶真實軌跡被識別的風險。

2 預備知識

首先介紹了相關定義和系統架構，然后根據用戶歷史軌跡和地圖數據介紹如何構建用戶行為模型，最后對時空關聯性進行描述。

2.1 相關定義

定義1(查詢請求) 查詢請求是指用戶向位置服務器發送的消息內容。表示為{id，(x，y)，t，cont}，其中，id為用戶身份唯一標識，(x，y)為用戶位置信息，t為用戶查詢時間，cont為查詢內容。

定義2(隱私要求) 用戶個性化的隱私需求，表示為req(K，L)，其中，K和L分別是用戶可接受的移動用戶和路段的最小值。

定義3(匿名集) 匿名集是指滿足用戶隱私需求的基本前提下可隱蔽用戶真實位置的集合，表示為AS。

定義4(語義軌跡) 語義軌跡是指用戶在連續查詢時間段內曾到達的語義位置所組成的路徑。換句話說，語義軌跡實際上是一個按照時空序列連續采樣的語義位置的集合，表示為

T={(x0，y0，t0)，(x1，y1，t1)，…，(xn，yn，tn)} ，

其中，T[i]表示用戶在ti時刻所處語義位置的坐標，i∈(0，1，…，n)且t0

定義5(用戶行為模型) 用戶行為模型是指中心匿名服務器根據用戶歷史語義軌跡統計用戶在語義位置之間的轉移概率所創建的矩陣。表示為

其中，mij表示由第i個語義位置轉移到第j個語義位置的概率(1≤i≤n)。

2.2 系統結構

圖2 系統架構

如圖2所示，采用由可信的中心匿名服務器來連接移動終端和基于位置的服務器的中心匿名服務器架構。中心匿名服務器結構由移動終端、中心匿名服務器和基于位置的服務器組成[22]。它是移動終端和基于位置的服務器之間傳遞消息的加工者。正是由于中心匿名服務器的可信性，用戶不用擔心其位置資料的泄露。其主要工作流程如下：

步驟1 中心匿名服務器初始化路網數據庫、語義位置數據庫、用戶歷史語義軌跡數據庫，統計用戶在語義位置之間的轉移次數以構建用戶出行模型；

步驟2 移動終端將用戶隱私需求和查詢請求發送至中心匿名服務器，其根據用戶隱私需求、時空關聯匿名集生成算法生成假軌跡點構建匿名集，并判斷相鄰時刻匿名集是否滿足時空關聯性；若滿足，則直接將匿名請求發送給基于位置的服務器；若不滿足，則計算延遲發送時刻，將匿名請求延遲發送給基于位置的服務器；

步驟3 基于位置的服務器對匿名請求進行查詢操作，然后將候選結果集全部返回給中心匿名服務器；

步驟4 中心匿名服務器利用查詢結果求精處理器對候選結果集進行處理，得到精確結果后發送至移動終端。

2.3 用戶行為模型

充分考慮用戶歷史語義軌跡中包含的用戶行為規律信息，構建用戶行為模型。使用中心匿名服務器統計用戶歷史移動數據構建融合語義信息的用戶出行模型，即中心匿名服務器分析用戶從一個語義位置轉移到另外一個語義位置的頻率。使用一個矩陣N來記錄用戶從一個語義位置loci到另一語義位置locj的次數Qij，則Qij=N[i][j]。

表1是用戶出行統計表。表格的第1列代表出發地，第1行代表目的地。例如，用戶從商場出發的軌跡條數為200條，其中到達商場10次，學校40次，住宅20次，公園30次，醫院60次，公司40次。

表1 用戶出行統計表 次

根據這些數據創建語義位置轉移矩陣N，表示為

P(i|j)=Qij/∑Qij，表示用戶從語義位置loci到達語義位置locj的概率。例如用戶從商場到達學校的轉移概率為P(商場|學校)=40/200=0.2。因此，基于語義位置轉移矩陣N，可以分析出用戶出行概率矩陣M，表示為

2.4 時空關聯性

連續查詢場景下，用戶相鄰時刻的查詢請求具有時空關聯性，即用戶需在請求時間內到達下一位置點。

圖3為描述時空關聯性的實例。ASi-1={A，B，C，D}，為用戶A在ti-1時刻提交的匿名集，而用戶在ti時刻提交的匿名集為ASi={A′，B′，C′，D′}。其中A→A′為用戶真實移動軌跡。攻擊者根據用戶進行查詢請求的時間間隔Δt=ti-ti-1和用戶最大移動速度推測出軌跡D→D′為虛假移動軌跡，因此用戶真實位置和真實軌跡被推測出的概率明顯增加。

圖3 時空關聯性的實例圖

Max(Dis(ASi-1，ASi))/vmin≤Δt，

(1)

其中，Max(Dis(ASi-1，ASi))表示某條移動軌跡的最大移動距離，vmin為用戶最小移動速度，Δt為查詢時間間隔即Δt=ti-ti-1。

如果不滿足式(1)的要求則延遲發送查詢請求，延遲發送的的時間為

ti=Max(Dis(ASi，ASi-1))/vmin+ti-1。

(2)

3 融合語義信息的時空關聯位置隱私保護算法

詳細介紹融合語義信息的時空關聯位置隱私保護算法(Spatiotemporal Correlation Location Privacy Protection algorithm with semantic information，SCLPP)，即時空關聯匿名集生成算法和連續時刻匿名集生成算法。

算法1為時空關聯匿名集生成算法，主要解決如何根據用戶查詢狀態構建匿名集的問題。

在該算法中如果用戶是首次發出連續查詢請求(②)，根據用戶隱私偏好L找到用戶所在路段的L-1條相鄰路段(③～⑦)，在這L條路段上找到K-1個不同的語義位置并在其附近生成假位置作為假軌跡的起點，即產生匿名位置集AS0(⑧～)；否則，根據用戶位置坐標、路網、用戶出行模型調用算法2構建匿名位置集ASi()。

算法1時空關聯匿名集生成算法。

輸入：用戶坐標(x，y)，隱私需求req(K，L)，路網G。

輸出：ASi 。

① AdjecentEdgeset=?；ASi=?；S_loc=?；

② ifti=t0then

③ assign the edge where userulocated toe；

④ AdjecentEdgeset=AdjecentEdgeset∪e

⑤ if |AdjecentEdgesset|

⑥ edge=FindEdge(e)；//隨機查找e的一條相鄰路段

⑦ AdjecentEdgeset=AdjecentEdgeset∪edge

⑧ end if

⑨ put the semantic location where user u located to AS0

⑩ if |AS0|

算法2為連續時刻匿名集生成算法，主要解決為非首次查詢用戶如何構建匿名集的問題。

首先得到用戶前一時刻的匿名位置集Asi-1(①)，根據用戶隱私偏好L找到用戶所在路段的L-1條相鄰路段(②)，當位置匿名集中位置個數小于L時，將L條路段上的語義位置分別存放在L個集合中，同時構建一個Total_set集合存放前面所述的L個集合，即Total_set={set1，set2，…，setL}(③～⑧)。

然后，從用戶出行模型中將前一時刻匿名位置集Asi-1[i]轉移到Total_set集合中所有位置的轉移概率放在集合Moveset中，并在轉移概率最大的語義位置附近產生假位置作為當前時刻的第i個假位置，將Moveset置空，同時將該位置從所屬集合seti中刪除，然后將seti從Total_set集合中刪除(⑨～)。但是，當位置匿名集中位置個數大于L時，將set1，set2，…，setL中剩余的位置從新組成一個集合Movenew，然后依次找出ti-1時刻剩余假位置到Movenew中轉移概率最大的K-L個語義位置并在附近產生假位置(～)。

最后，利用式(1)檢查相鄰時刻匿名位置集是否滿足利用連續查詢的時空關聯性()，否則，利用式(2)計算延遲發送匿名集的時間(～)。該算法的偽代碼如下。

算法2連續時刻匿名位置集生成算法。

輸入：用戶坐標(x，y)，隱私需求req(K，L)，路網G，用戶出行模型user_matrix 。

輸出：ASi。

① get Asi-1

② 重復算法1的③～⑧

③ put the semantic location where user located to ASi

④ if |ASi|<=req.Lthen

⑤ fori=1：Ldo

⑥ put the semantic location in AdjecentEdgeset[i]into seti；//將位于同一路段上的語義位置放在同一集合中

⑦ Total_set={seti}

⑧ end for

⑨ fori=1：L-1 do

⑩ put transition proability from Asi-1[i]to Total_set use user_matrix into Moveset

4 實驗及結果分析

4.1 實驗設置

從空間數據庫(http：//www.cs.utah.edu/～lifeifei/SpatialDataset.htm)中下載加利福尼亞州的城市道路網絡和語義位置作為實驗數據。使用移動對象生成器[23]模擬移動對象在加利福尼亞州的地圖進行活動，共計生成100 000個移動對象，并為每個移動對象設置50個位置點作為用戶歷史移動數據。同時，從中隨機選取20 000個用戶的25個位置點模擬發出連續查詢請求。

為了驗證SCLPP算法的有效性，選擇Enhanced-DLS算法[5]、TTcloak算法[24]為連續發送查詢請求的用戶生成假位置集合從而構建假軌跡。上述算法是假位置技術中比較經典的算法，考慮查詢概率等輔助信息，避免用戶生成如位于湖泊中心或位于十字馬路中心等不合理的假位置。同時，為了驗證現有面向路網環境的快照查詢隱私保護算法無法直接遷移到連續查詢中，選擇LSBASC算法[25]進行對比。上述算法均采用JAVA語言編程，在Microsoft Windows 10 Professional的Intel(R)Core(TM)i5-9400 CPU @ 2.90 GHz和16 GB主內存的電腦上運行。

4.2 實驗結果分析

4.2.1 時空關聯性分析

圖4 時空關聯性通過比例

連續查詢場景下，用戶相鄰時刻的查詢請求具有時空關聯性。基于時空關聯性對所有算法生成的假位置進行檢驗，統計假位置能夠通過篩查的比例。由圖4可知，SCLPP算法通過篩查的比例為100%，這是因為它在生成匿名集時已經充分考慮了時空關聯性。而Enhanced-DLS算法、LSBASC算法、TTcloak算法未考慮時空關聯性，導致產生的匿名集中通過篩選的平均比例分別為25%、28%、27%。Enhanced-DLS算法在K=4時通過篩查的比例最高為32%，但也有78%的位置點被識別出來。LSBASC算法在K=5時通過篩查的比例最高為39%，但也有61%的位置點被識別出來。TTcloak算法在K=4時通過篩查的比例最高為30%，但也有70%的位置點被識別出來。因此可以得出這樣一個結論：時空關聯性是極為重要的考慮條件。

4.2.2 軌跡相似度分析

軌跡相似度與軌跡暴露風險是一種相反的數量關系，即軌跡相似度越高說明軌跡暴露風險越小，反之，則軌跡相似度越低導致軌跡暴露風險越高。由圖5可知，SCLPP算法的軌跡相似度最高，暴露風險最低，LSBASC次之，Enhance-DLS算法暴路風險較大，TTcloak算法暴路風險最大。與其他算法相比，SCLPP算法的軌跡暴露概率平均降低了17.6%。這是因為SCLPP匿名算法與LSBASC算法在單個時刻生成匿名集時總是優先考慮相鄰路段上的語義位置點，所以軌跡相似度偏高。而Enhance-DLS算法與TTcloak算法都是通過查詢概率選擇位置集合，所以軌跡相似度較低。

4.2.3 系統開銷分析

使用匿名位置集構成的匿名區域的平均大小來度量系統開銷，平均匿名區域面積越大，查詢時間消耗越大，系統開銷也越大。由圖6可知，SCLPP算法的系統開銷最小，LSBASC次之，TTcloak算法較小，Enhance-DLS算法最大。這是因為SCLPP匿名算法與LSBASC算法在構成匿名集時通過考慮相鄰路段上的語義位置點使得匿名區域面積較小。而TTcloak算法設定了匿名區域大小使得平均匿名區域面積比Enhance-DLS算法要低。

圖5 軌跡相似度

圖6 系統開銷

5 安全性分析

攻擊者挖掘背景知識(用戶行為規律、移動數據等)可對用戶行為軌跡中包含的語義信息進行推斷攻擊，導致用戶習慣、宗教信仰等信息的泄露。針對該問題，筆者方案利用用戶行為模型提出一種融合語義信息的時空關聯位置隱私保護算法。首先根據用戶隱私偏好L找到用戶所在路段的L-1條相鄰路段，將L條路段上的語義位置分別存放在L個集合中，同時構建一個Total_set集合存放前面所述的L個集合，即Total_set={set1，set2，…，setL}。然后，從用戶出行模型中將前一時刻匿名位置集Asi-1[i]轉移到Total_set集合中所有位置的轉移概率放在集合Moveset中，并在轉移概率最大的語義位置附近產生假位置作為當前時刻的第i個假位置，將Moveset置空，同時將該位置從所屬集合seti中刪除，然后將seti從Total_set集合中刪除。但是，當位置匿名集中位置個數等于L時，將set1，set2，…，setL中剩余的位置重新組成一個集合Movenew，然后依次找出ti-1時刻剩余假位置到Movenew中轉移概率最大的K-L個語義位置并在附近產生假位置。該算法生成的假軌跡中單個時刻位置點之間的轉移概率大于真實軌跡中單個時刻位置點之間的轉移概率，實現了保護真實移動軌跡的目的。因此，可抵御推斷攻擊。

攻擊者分析相鄰時刻匿名位置集能否在用戶正常移動速度內達到，排除不能按時到達的假軌跡，增加真實軌跡的泄露概率。針對時空可達性攻擊，筆者提出的方案計算相鄰時刻匿名位置集之間所需的最大移動時間，判斷是否延遲發送匿名查詢請求，從而實現時空關聯性。假設用戶在ti-1時刻和ti時刻上傳的匿名位置集分別為ASi-1和ASi，判斷它們滿足時空可達性條件Max(Dis(ASi-1，ASi))/vmin≤Δt，則正常發送查詢請求，否則延遲發送匿名請求的時間為ti=Max(Dis(ASi，ASi-1))/vmin+ti-1。因此，可抵御時空可達性攻擊。

6 結束語

針對連續查詢中攻擊者利用背景信息對用戶軌跡進行攻擊的問題，筆者提出了一種融合語義信息的時空關聯位置隱私保護方法。該方法不僅生成假軌跡增加用戶真實軌跡的保護力度，并且單個時刻的位置隱私保護也隨之增加。生成的假軌跡中單個時刻位置點之間的轉移概率甚至大于真實軌跡中單個時刻位置點之間的轉移概率，而且判斷相鄰時刻匿名集之間時空可達性，若不可達則延遲發送用戶匿名請求，真正的實現了保護真實移動軌跡的目的。最后通過模擬實驗驗證算法的有效性。