基于假位置選擇的位置隱私脫敏算法

摘 要： 傳統位置隱私脫敏技術容易遭受背景知識攻擊和單點攻擊，造成用戶位置隱私泄露，危及其生命財產安全。針對此問題，提出了一種基于假位置選擇的位置隱私脫敏算法DLPD（dummy location privacy desensitization）。首先，通過衡量位置敏感程度、實行偏移優化、過濾位置查詢概率來構造假位置候選集；其次，改善位置分布篩選假位置；最終，構造安全匿名集實現位置隱私脫敏。實驗證明，該算法增強了隱私保護強度，提高了隱私保護的有效性，同時，降低了開銷，具有實用性。

關鍵詞： 假位置； 位置隱私； 隱私保護； 脫敏

中圖分類號： TP309"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-046-1551-06

doi：10.19734/j.issn.1001-3695.2021.10.0477

Location privacy desensitization algorithm based on dummy location selection

Zhang Ai， Li Xiaohui， Li Bo

（School of Electronics amp; Information Engineering， Liaoning University of Technology， Jinzhou Liaoning 121000， China）

Abstract： Traditional location privacy desensitization algorithms are susceptible to background knowledge attack and single point attack， which causes users’ location privacy to be leaked and endangers their life and property safety. In order to solve the problem， this paper proposed a location privacy desensitization algorithm based on dummy location selection， called DLPD. Initially， it constructed a dummy location candidate set by measuring location sensitivity， implementing offset optimization and filtering location query probability. Furthermore， it improved the location distribution to filter dummy locations. Eventually， it constructed a secure anonymous set to achieve location privacy desensitization. Experiments demonstrate that the proposed algorithm enhances the privacy protection strength and improves the effectiveness of privacy protection. Meanwhile， it reduces the overhead and has practicality.

Key words： dummy location; location privacy; privacy protection; desensitization

0 引言

大數據時代，移動通信得到普及，傳感設備不斷推陳出新，位置感知技術蓬勃發展，人和事務的地理位置以數據化形式存在，通過直接或間接的形式收集移動對象的位置數據之后，用戶可以進行與位置相關的查詢［1］，即基于位置的服務（location-based services，LBS）。基于位置的服務實則是將移動設備的位置信息與其他信息進行整合［2］，為用戶提供增值服務。比如生活中常用的百度地圖、餓了么、微博等軟件，這些都是LBS的應用實例，LBS已經全方位地滲透到人們的日常生活中，為用戶帶來了巨大的收益［3］。但是這些服務系統經常在用戶不知情的情況下收集用戶的位置信息，進而分析和挖掘用戶的個人信息，如家庭住址、健康狀況、工作地點、興趣愛好等敏感信息，威脅用戶的人身和財產安全，存在著隱私信息泄露的危害［4］。因此，實現位置隱私保護至關重要。

近年來，國內外研究者提出了多種位置隱私脫敏技術， 可以大致劃分為三類［5］：a）數據加密技術［6］，實現較高的隱私保護強度，服務可用性較強，但是計算量和運行開銷較大［7］；b）抑制發布技術［8］，容易受到背景知識攻擊，隱私保護程度較低；c）數據失真技術，用戶提交不真實的查詢內容，使攻擊者無法獲取用戶的真實位置信息，以此來保護用戶的位置隱私，包括K-匿名［9］、假位置干擾等。

針對假位置技術，最早是由Kido等人［10］于2005年提出的，基本思想是將用戶真實位置加入到假位置中一同發給LBS服務器，混淆用戶位置的真實性，使其無法區分用戶的真實位置，由此實現用戶位置隱私脫敏。Lu等人［11］提出基于虛擬方格的GridDummy算法和基于虛擬圓的CirDummy算法，這兩種算法解決了零散的假位置容易被攻擊者過濾的隱患，降低了匿名區域過小導致用戶位置隱私泄露的風險，但是忽略了攻擊者可能依據背景知識或邊信息等排除部分位于無人區、河流、高山等的位置，進而分析出用戶的真實位置。Niu等人［12］考慮了背景知識，提出了DLS方案，計算歷史位置查詢概率，根據位置熵對隱私保護程度進行度量，但是攻擊者運用聚類、數據挖掘等技術，通過概率攻擊竊取用戶的真實位置信息，所以僅考慮概率因素還不足以有效地實現位置隱私保護。李暢等人［13］綜合考慮了歷史查詢概率、速度、行駛方向等多種因素，提出選取與用戶位置相似度較高的假位置構造匿名區域的基于用戶偏好選擇的假位置生成方案，但未考慮位置語義信息，無法應對語義背景知識的攻擊。Hara［14］注意了位置語義，滿足了用戶需求，提升了服務質量，但是卻忽略了生成假位置的離散度，存在著位置同質性攻擊的危險。王潔等人［15］提出了一種基于位置語義和查詢概率的最大最小假位置選擇算法，該算法綜合了位置語義和查詢概率兩個主要因素，同時考慮了離散度，通過計算的方式量化位置語義，但是衡量語義差異性的方式較為粗糙，不夠準確，語義適用范圍不夠廣泛，存在不足。

綜上所述，這些技術在面對背景知識攻擊、邊信息攻擊、位置同質性攻擊等方面存在局限性，同時沒有實現綜合因素的考量，衡量方式不夠準確，用戶位置隱私保護強度不夠高。因此，本文提出一種改進的基于假位置選擇的位置隱私脫敏算法DLPD。該算法全面考慮了位置語義、偏移優化、查詢概率、離散程度、匿名等級多種因素，生成更具有合理性和不可區分性的假位置;同時衡量方式相對準確，基于WordNet結構計算語義相似度，通過海倫公式準確量化假位置之間的密集程度，實現位置隱私保護的有效性，同時降低了開銷，增強了實用性。

2.3 假位置篩選

通過算法2得到假位置候選集合C，對集合C的離散度進行處理，改善假位置的分布，最終篩選出假位置集合，如算法3所示。

算法3 DLF算法

輸入：假位置候選集C。

輸出：假位置集合D。

n←|C|

for i=1 to n do

if （i==1） //尋找第1個加入D的假位置

return dis（U，Ci） "http://計算C中假位置到偏移位置的歐氏距離

E1←max dis（U，Ci）" /*歐氏距離最大值對應的位置作為第1個加入到假位置集D中的假位置E1* /

insert E1 into D

else"" "http:// 從尋找第2個假位置開始，依次往后尋找

for j=1 to n-1 do" "/*從除去第1個作為假位置的假位置候選集C中，依次往后尋找新的加入D中的假位置* /

return dis（Ei，Cj）

Ei←Smax （Heron’s formula） /* 根據海倫公式計算能與U和E1…j組成最大面積的位置作為第i個假位置Ei * /

insert Ei into D

（n-1）--

end for

end if

n--

end for

return D

算法3輸入對象是假位置候選集合C，目的是依據海倫公式的思想過濾出離散度較高的假位置組成假位置集合，優化位置分布。 首先，按照式（3）計算假位置候選集C中各位置到偏移位置U的歐氏距離，挑選出最大值，選定其對應的位置作為第1個假位置E1加入到假位置集合D中；然后，計算假位置候選集C中除去E1以外的其余位置到E1的歐氏距離，利用式（5）計算與U和E1組成最大面積的位置作為第2個假位置E2加入到假位置集合D中；接著計算集合C中除去E1 和E2以外的假位置到E2的歐氏距離，按照海倫公式的推論選出與U、E1、E2圍成最大面積的位置作為第3個假位置E3加入到假位置集合D中。依次重復上述步驟，直到假位置候選集C中沒有符合要求的假位置后才結束循環，最后返回假位置集合D。該算法實現了假位置在離散度方面的篩選，其篩選結果最后再依據設定的匿名等級，結合偏移位置一同構造成安全匿名集。

2.4 算法性能分析

2.4.1 安全性分析

a）DLPD算法利用歷史位置信息生成假位置，成功避免了攻擊者利用地理知識進行邊信息攻擊。當攻擊者獲取一定的知識背景時，可以篩除類似于高山、湖泊、沙漠等不可達位置，對縮小匿名度的位置加以分析，很可能推斷出用戶的真實位置，造成隱私泄露。歷史信息的應用無論是位置點稠密還是稀疏的情況都可以保證假位置的數量，確保匿名度，實現位置隱私保護。

b）實現語義多樣化和提高概率相似性增強了假位置與用戶真實位置的不可區分性。首先，針對與用戶敏感位置語義相同的位置，一旦定位，將向攻擊者傳遞有用信息，暴露用戶真實位置，最先進行敏感語義位置的刪除，保證了各位置之間語義的差異性，避免了語義同質性攻擊；其次，篩選與用戶位置查詢概率相似的假位置，可以增強假位置的真實性，增大被識別的難度，提高隱私保護強度。

c）實行偏移優化避免攻擊者單點攻擊。改變傳統的假位置算法應用用戶真實位置構造匿名集的思想，利用與用戶距離較近的偏移位置完全替代用戶的真實位置加入到安全匿名集中，完全掩蓋了用戶的真實位置信息，具有真實性和不易區分性，實現用戶隱私脫敏。

d）改善位置分布，避免攻擊者進行位置同質攻擊。安全匿名集相對較小的情況下假位置分布過于集中，攻擊者可以利用位置聚類的手段過濾假位置，提高推測出用戶真實位置的概率，威脅用戶的位置隱私安全。所以改善位置分布，篩選出分散的假位置，擴大安全匿名集的覆蓋范圍，切斷了攻擊者進行同質分析的機會，保障了用戶的位置隱私安全。

2.4.2 實用性分析

a）量化衡量標準，提高準確性。首先，改進傳統位置語義較為粗糙的計算方法，選擇適用范圍廣泛，計算結果準確的WordNet結構計算語義相似度，同時考慮語義的屬性，利用sense標記一個位置可能有多種語義的情況，精準分析與用戶敏感位置語義是否相同，衡量效果更可靠，更符合實際；其次，利用海倫公式、歐氏距離等方式量化假位置的離散程度，既方便又精準地實現位置隱私數據脫敏，提高了實用性。

b）合理部署算法流程，提高效率，降低通信量。算法的通信主要是發生在用戶、可信匿名服務器、LBS服務器之間。由于這些通信僅包括簡單的查詢請求和少量數據的傳輸，所以通信量為常數級，記為O（C）。首先，用戶與可信匿名服務器之間主要傳輸位置服務請求和安全匿名集，位置服務請求通信量為O（C），安全匿名集傳輸取決于匿名度K記為O（KC）；其次，可信匿名服務器和LBS服務器之間主要是假位置信息的傳遞為O（C），同時可知最先進行與用戶敏感語義相同位置的刪除，免于計算其查詢概率以及是否為偏移位置等的操作，進一步減少了位置信息的傳遞量，降低了通信開銷；最后，綜合分析，該算法的整體通信量復雜度不會超過O（KC），通信開銷較低，因此具有較高的可用性。

2.4.3 時間復雜度分析

算法主要分為兩個階段順序執行。第一階段假位置構造、語義相似度和查詢概率的計算以及偏移位置的選取均體現在通過遍歷位置實現相關操作，時間復雜度均為O（n），故第一階段時間復雜度為O（n）。第二階段假位置篩選，海倫公式嵌套循環，準確度量假位置離散度，時間復雜度為O（n2）。所以總體上算法的時間復雜度為O（n2），時間開銷相對較小。

3 實驗分析

3.1 實驗環境及數據集

3.1.1 實驗環境

實驗采用PyCharm 2019.3.1的開發平臺，通過Python編程實現算法。實驗運行的硬件環境是Intel Core i7 3.40 GHz處理器，16 GB內存的Windows 10操作系統。

3.1.2 實驗數據集

實驗數據是由Brinkhoff［19］提出并實現的基于網絡的移動對象生成器（network-based generator of moving objects）產生。該生成器以德國城市Oldenberg（面積約為16 km×16 km）的交通路線圖作為輸入，通過設置移動對象個數、移動速度和運行時間段，模擬出移動對象在地圖上的運動軌跡，輸出標記為（對象，時間，位置坐標）的位置信息，使用這些信息作為用戶的歷史位置點信息。實驗選取地圖中心面積為3 km×3 km的部分作為實驗區域，將其劃分為900個網格，每個網格的面積為100 m×100 m。實驗模擬在生成器默認設置的移動速度下，100個用戶在500個時間單位內的移動，隨機生成3 571條軌跡，包含15 283個位置點信息，以此作為實驗的數據集。實驗參數配置情況如表1所示。

3.2 實驗結果

在驗證DLPD算法隱私保護有效性方面，本文與未考慮位置語義的DLP算法［20］、忽略假位置離散度的HARA 算法［14］和MMDS算法［15］從匿名成功率、假位置分散度、位置熵、算法運行時間四個方面進行實驗對比，權衡在不同匿名等級K下各算法的隱私保護強度。

3.2.1 匿名成功率

首先創設相同的實驗環境，使各算法運行在同一數據集并且參數設置保持一致的范圍內對匿名成功率［21］進行合理的比較。此處應用典型的具有背景知識攻擊模式的貝葉斯（Bayesian）機制［22］。實驗結果如圖5所示。實驗結果表明，首先，在相同的背景知識攻擊下，四種算法的匿名成功率都有所下降，這是因為隨著匿名等級的提高，滿足要求的假位置數目相應減少，安全匿名集的構建難度增大，隱私保護效果下降；其次，綜合考慮位置語義、查詢概率、偏移位置等多種因素的DLPD算法匿名成功率最高，有效抵抗背景知識攻擊，具有良好的隱私保護效果。MMDS算法匿名成功率僅次于DLPD，其在語義和離散度衡量方法的選擇上不夠恰當。HARA算法匿名成功率低于MMDS，DLP算法匿名成功率最低，這說明單獨考慮位置語義或者離散度，假位置之間關聯性增強，更容易遭受背景知識攻擊，位置隱私隱匿程度降低，隱私保護效果較差。

為了對比考慮位置語義信息對位置隱私脫敏的優勢，此處采用語義攻擊［23］，以直觀的形式表現位置語義因素對位置隱私保護有效性的影響程度。實驗對比如圖6所示。

實驗結果表明，隨著匿名等級K逐漸增大，不同算法匿名成功率逐漸減小，由于K增大導致假位置之間語義差異性逐漸縮小，更容易受到語義攻擊，使匿名成功率降低。DLP算法忽略了位置語義因素，所以隱私保護強度較低，匿名成功率低于另外三種算法；盡管MMDS和HARA算法均考慮了位置語義因素，但是MMDS算法對語義差異性的計算方式較為粗糙，衡量結果不夠精確；HARA算法在位置語義和歷史位置對應性方面存在不足，所以DLPD算法的匿名成功率最高。

3.2.2 假位置分散度

假位置分散度通過式（2）最小距離來衡量。最小距離越大說明假位置分布越分散，受到攻擊者位置同質性攻擊的概率越低，位置隱私保護越有效，隱私保護強度越強。實驗對比結果如圖7所示。通過實驗對比可以看出，匿名等級K越大，四種算法假位置之間最小距離越小，假位置分布越集中，隱私保護強度越低。HARA算法沒有考慮離散度，假位置分布最集中；DLP和MMDS算法雖然都考慮了假位置離散度，但是DLP衡量方式較為單一，合理性較差，所以假位置分散度要低于MMDS算法;DLPD算法假位置分布最分散，其利用海倫公式改善位置分布，計算方式優化準確，有效地擴大了匿名區域面積，減少位置同質性攻擊，隱私保護最有效。

3.2.3 位置熵

應用文獻［17］中的位置熵衡量隱私保護強度，度量位置隱私保護的有效性。不同匿名等級下的實驗對比如圖8所示。

通過圖8可知，隨著匿名等級K增大，位置熵值呈現整體增大的趨勢，位置隱私保護強度增大。但是DLPD算法的位置熵要明顯大于另外三種算法。這是因為DLPD算法綜合考慮了位置語義、離散度、偏移位置等多種因素，增強了用戶真實位置的不確定性，可以更有效地保護用戶的位置隱私，實現位置隱私脫敏效果最佳。

3.2.4 算法運行時間

DLPD算法的時間開銷主要體現在刪除與用戶敏感語義相同的位置、選擇偏移位置、語義相似度計算、歷史位置查詢概率計算以及離散度的衡量。通過設置匿名等級K的大小，觀察四種算法運行時間的變化，如圖9所示。

實驗結果表明，隨著匿名等級K的增加，四種算法的運行時間都會變大。DLP算法沒有考慮位置語義，運算量較少，所以運行時間最小。對比HARA和MMDS算法，DLPD算法最開始先進行敏感語義位置的刪除，歷史位置數量相應減少，運行時間較小，但利用海倫公式進行假位置篩選的時間開銷較大，運行時間一定程度上高于MMDS，隨著匿名等級K的增大，DLPD算法時間開銷增長幅度相對緩慢，逐漸小于MMDS算法。總體來說，DLPD算法在時間開銷方面更具有優勢，效率更高，實用性更強。

通過歸納總結以上的對比實驗，DLPD 算法在實行偏移優化的同時還兼顧語義差異性和假位置的分散性，具有較高的位置熵值和假位置生成效率，能提高隱私保護強度，實現位置隱私保護的有效性。

4 結束語

針對傳統技術的不足，以及有效避免攻擊者進行背景知識攻擊、利用邊信息攻擊和位置同質攻擊，提出了一種改進的假位置選擇算法DLPD算法。該算法綜合位置語義敏感程度、偏移位置替代、查詢概率相似性、位置分布離散化和符合匿名等級五個方面實現位置隱私脫敏。該算法核心思想分為假位置構造和假位置篩選兩部分。首先按照位置語義多樣化、偏移位置替代優化、查詢概率相似性三個原則實現假位置構造；其次按照假位置離散度高的約束條件利用海倫公式篩選假位置，最終構造出更具合理性和不可區分性的假位置，增強位置隱私保護強度，實現了位置隱私保護的有效性。實驗分析根據匿名成功率、假位置分散度、位置熵、算法運行時間四個指標將DLPD與HARA、DLP、MMDS算法進行對比。實驗結果表明，DLPD算法平衡了安全性和實用性，不僅綜合考慮了多種因素，降低了攻擊者利用背景知識攻擊和單點攻擊竊取用戶位置隱私的風險程度，實現了位置隱私脫敏，而且時間開銷較小，運行效率高，保證了服務質量，具有良好的實際應用價值。

今后，筆者將從以下方向進行研究：

a）降低對可信第三方服務器的依賴。第三方服務器聲稱不會泄露用戶位置隱私，但無法保證用戶位置信息的絕對安全，存在著被攻擊者識別并竊取位置隱私信息的風險，所以要優化系統架構，擺脫對可信第三方服務器的依賴。

b）研究連續位置的隱私脫敏技術。在實際應用中，用戶位置在有效時間內是不斷更新的，行蹤大多以軌跡形式存在。因此，綜合衡量時間維度，研究用戶軌跡隱私脫敏也具有重要意義。

參考文獻：

[1]Yang Xudong， Gao Ling， Zheng Jie， et al. Location privacy preservation mechanism for location-based service with incomplete location data［J］.IEEE Access，2020，8：95843-95854.

［2]Wang Shengling， Hu Qin， Sun Yunchuan， et al. Privacy preservation in location-based services［J］.IEEE Communications Magazine，2018，56（3）：134-140.

［3]Wu Zongda， Wang Ruiqin， Li Qi， et al. A location privacy-preserving system based on query range cover-up or location-based services［J］.IEEE Trans on Vehicular Technology，2020，69（5）：5244-5254.

［4]He Xiaofan， Jin Richeng， Dai Huaiyu. Leveraging spatial diversity for privacy-aware location-based services in mobile networks［J］.IEEE Trans on Information Forensics and Security，2018，13（6）：1524-1534.

［5]張青云，張興，李萬杰，等.基于LBS系統的位置軌跡隱私保護技術綜述［J］.計算機應用研究，2020，37（12）：3534-3544.（Zhang Qingyun， Zhang Xing， Li Wanjie， et al. Overview of location trajectory privacy protection technology based on LBS system［J］.Application Research of Computers，2020，37（12）：3534-3544.）

［6]李幸昌，王斌，王超，等.基于加密分割的位置隱私保護方法［J］.計算機應用研究，2021，38（10）：3153-3156.（Li Xingchang， Wang Bin， Wang Chao， et al. Location privacy protection method based encryption and segmentation［J］.Application Research of Compu-ters，2021，38（10）：3153-3156.）

［7]Chen Guanhua， Zhao Jianyang， Jin Ying， et al. Certificateless deniable authenticated encryption for location-based privacy protection［J］.IEEE Access，2019，7：101704-101717.

［8]萬盛，李鳳華，牛犇，等.位置隱私保護技術研究進展［J］.通信學報，2016，37（12）：124-141.（Wan Sheng， Li Fenghua， Niu Ben， et al. Research progress on location privacy-preserving techniques［J］.Journal on Communications，2016，37（12）：124-141.）

［9]Song Fagen， Ma Tinghuai， Tian Yuan， et al. A new method of privacy protection： random k-anonymous［J］.IEEE Access，2019，7：75434-75445.

［10]Kido H， Yanagisawa Y， Satoh T. Protection of location privacy using dummies for location-based services［C］//Proc of the 21st International Conference on Data Engineering Workshops.Piscataway，NJ：IEEE Press，2005.

［11]Lu Hua， Jensen C S， Yiu M L. Pad： privacy-area aware， dummy-based location privacy in mobile services［C］//Proc of the 7th ACM International Workshop on Data Engineering for Wireless and Mobile Access.New York：ACM Press，2008：16-23.

［12]Niu Ben， Li Qinghua， Zhu Xiaoyan， et al. Achieving k-anonymity in privacy-aware location-based services［C］//Proc of IEEE Internatio-nal Conference on Computer Communications.Piscataway，NJ：IEEE Press，2014：754-762.

［13]李暢，張興，顏飛，等.基于用戶偏好選擇的假位置生成方案［J］.計算機工程與設計，2019，40（4）：914-919，1195.（Li Chang， Zhang Xing， Yan Fei， et al. False location generation scheme based" """"on user preference selection［J］.Computer Engineering and Design，2019，40（4）：914-919，1195.）

［14]Hara T. Dummy-based location anonymization for controlling observable user preferences［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2019：1-7.

［15]王潔，王春茹，馬建峰，等.基于位置語義和查詢概率的假位置選擇算法［J］.通信學報，2020，41（3）：53-61.（Wang Jie， Wang Chunru， Ma Jianfeng， et al. Dummy location selection algorithm based on location semantics and query probability［J］.Journal on Communications，2020，41（3）：53-61.）

［16]Li Fei， Liao Lejian， Zhang Lanfang， et al. An efficient approach for measuring semantic similarity combining WordNet and Wikipedia［J］.IEEE Access，2020，8：184318-184338.

［17]Niu Ben， Li Qinghua， Zhu Xiaoyan， et al. Enhancing privacy through caching in location-based services［C］//Proc of the 34th IEEE International Conference on Computer Communications.Pisca-taway，NJ：IEEE Press，2015：1017-1025.

［18]Chen Jing， He Kun， Yuan Quan， et al. Blind filtering at third parties： an efficient privacy-preserving framework for location-based services［J］.IEEE Trans on Mobile Computing，2018，17（11）：2524-2535.

［19]Brinkhoff T. A framework for generating network-based moving objects［J］.Geo Informatica，2002，6 （2）：153-180.

［20]Sun Gang， Chang V， Ramachandran M， et al. Efficient location privacy algorithm for Internet of Things （IoT） services and applications［J］.Journal of Network and Computer Applications，2017，89：3-13.

［21]王輝，朱國宇，申自浩，等.基于用戶偏好和位置分布的假位置生成方法［J］.計算機科學，2021，48（7）：164-171.（Wang Hui， Zhu Guoyu， Shen Zihao， et al. Dummy location generation method based on user preference and location distribution［J］.Computer Science，2021，48（7）：164-171.）

［22]Shokri R， Theodorakopoulos G， Troncoso C， et al. Protecting location privacy： optimal strategy against localization attacks［C］//Proc of the 19th ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2012：617-627.

［23]Tu Zhen， Zhao Kai， Xu Fengli， et al. Protecting trajectory from semantic attack considering k-anonymity， l-diversity and t-closeness［J］.IEEE Trans on Network and Service Management，2019，16（1）：264-278.