基于差分隱私的LBS用戶位置隱私保護(hù)方案

于乃文 楊少杰 陳振國 張光華

摘 要：為了兼顧共享位置數(shù)據(jù)的可用性和隱私保護(hù)需求，針對(duì)第三方收集的用戶共享位置信息，提出了一種基于差分隱私的LBS用戶位置隱私保護(hù)方案。首先，對(duì)共享位置數(shù)據(jù)集進(jìn)行預(yù)處理，使用字典查詢方式構(gòu)建位置事務(wù)數(shù)據(jù)庫，采用Trie樹結(jié)構(gòu)存儲(chǔ)位置數(shù)據(jù)和頻率，提高查詢效率，減少加噪次數(shù);其次，在Trie樹上進(jìn)行頻繁位置選取，并使用差分隱私下的拉普拉斯機(jī)制擾動(dòng)位置頻率;最后，基于向上后置處理和一致性約束后置處理2種技術(shù)對(duì)擾動(dòng)后的數(shù)據(jù)進(jìn)行優(yōu)化，并通過理論證明所提方案滿足ε-差分隱私。結(jié)果表明，與已有方法相比，差分隱私保護(hù)方案提高了數(shù)據(jù)處理效率，泛化了敏感位置同時(shí)具有較高的精確率和較低的拒真率。所提方案能夠有效保護(hù)用戶的位置隱私，同時(shí)在共享位置數(shù)據(jù)可用性方面具有一定的參考價(jià)值。

關(guān)鍵詞：數(shù)據(jù)安全與計(jì)算機(jī)安全;位置數(shù)據(jù);隱私保護(hù);差分隱私;可用性

中圖分類號(hào)：TP309.2 文獻(xiàn)標(biāo)識(shí)碼：A

doi：10.7535/hbkd.2021yx03003

Location privacy protection scheme for LBS users based on differential privacy

YU Naiwen1， YANG Shaojie1， CHEN Zhenguo2， ZHANG Guanghua1，3

（1.School of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang，Hebei 050018，China;

2.Hebei Engineering Technology Research Center for IoT Data Acquisition & Processing，North China Institute of Science and Technology，Langfang，Hebei 065201，China;

3.State Key Laboratory of Integrated Services Networks，Xidian University，Xi'an，Shaanxi 710071，China）

Abstract：In order to take into account the availability of shared location data and privacy protection requirements，aiming at the shared location information collected by the third party，a location privacy protection scheme of LBS users was proposed based on differential privacy.Firstly，the shared location data set was preprocessed，the dictionary query mode was used to build the location transaction database，and the trie tree structure was adopted to store the location data and frequency，so as to improve the query efficiency and reduce the number of noise.Secondly，frequent location selection was carried out in the Trie tree，and Laplacian mechanism under differential privacy was used to disturb the location frequency.Finally，the perturbed data was optimized based on the two techniques of upward post-processing and consistency constrained post-processing，and theoretically prove that the proposed scheme satisfies ε-differential privacy.The experimental results show that，compared with the existing methods，this scheme improves the efficiency of data processing，generalizes the sensitive locations，and has higher accuracy and lower rejection rate.This scheme has a certain reference value in user location privacy protection and shared location data availability.

Keywords：

data security and computer security;location data;privacy protection;differential privacy;availability

隨著GPS、無線通信等技術(shù)的飛速發(fā)展，基于位置服務(wù)（LBS，location-based service）[1]給人們的生活起居、外出工作和社交活動(dòng)帶來了巨大變化。用戶通過智能設(shè)備從應(yīng)用商店可以下載基于位置的應(yīng)用程序，如百度地圖、谷歌地圖等，在提交的位置信息和查詢內(nèi)容基礎(chǔ)上獲取所需的服務(wù)數(shù)據(jù)[2]。功能多樣化的LBS應(yīng)用遍及人們的日常生活，其應(yīng)用場(chǎng)景主要有導(dǎo)航服務(wù)、社交網(wǎng)絡(luò)服務(wù)、興趣點(diǎn)推薦服務(wù)。然而，位置服務(wù)給用戶帶來諸多便利的同時(shí)，各種隱私泄露問題也層出不窮[3-4]。服務(wù)器獲取了用戶所使用的位置信息，進(jìn)一步分析用戶的居住地點(diǎn)、身體狀況和日常行為規(guī)律，甚至跟蹤用戶，并將用戶信息發(fā)布給第三方[5]。相對(duì)于LBS應(yīng)用提供的便利，用戶更關(guān)注個(gè)人的隱私安全。個(gè)人隱私保護(hù)水平影響用戶使用LBS應(yīng)用的積極性，因此設(shè)計(jì)強(qiáng)有力的位置隱私保護(hù)機(jī)制顯得尤為重要。

首先，現(xiàn)有的LBS用戶位置隱私保護(hù)機(jī)制大都通過K匿名模型[6]的擴(kuò)展達(dá)到保護(hù)位置隱私的目的。然而匿名是從外部保護(hù)用戶的身份而非用戶位置信息本身，所以在背景知識(shí)攻擊下會(huì)造成用戶個(gè)人隱私的泄露[7]。差分隱私[8]給出了一種嚴(yán)格可證明的數(shù)據(jù)隱私保護(hù)模型，其并不關(guān)心攻擊者擁有的背景知識(shí)，而是通過對(duì)輸出結(jié)果進(jìn)行隨機(jī)擾動(dòng)在保護(hù)數(shù)據(jù)隱私安全的同時(shí)，又可兼顧數(shù)據(jù)的可用性。其次，用戶使用位置服務(wù)時(shí)需授權(quán)LBS應(yīng)用以獲取位置信息，這些被收集的用戶位置信息經(jīng)過第三方處理并發(fā)布用于數(shù)據(jù)分析[9]。常用的處理方法是匿名或使用擴(kuò)展技術(shù)對(duì)位置數(shù)據(jù)集進(jìn)行處理，然而此類技術(shù)難以抵御背景知識(shí)的攻擊，從而造成用戶隱私泄露[10]。DWORK[11]最早提出了差分隱私概念，其優(yōu)勢(shì)在于不受背景知識(shí)和某條數(shù)據(jù)變化的影響。此外，將差分隱私運(yùn)用到位置隱私保護(hù)場(chǎng)景中，可通過隱私預(yù)算控制添加噪聲的大小[12]。再次，待發(fā)布的共享位置數(shù)據(jù)集為LBS用戶的頻繁位置數(shù)據(jù)集。對(duì)于此類頻繁模式數(shù)據(jù)挖掘問題，采用差分隱私技術(shù)合理分配隱私預(yù)算來兼顧頻繁數(shù)據(jù)的可用性和隱私保護(hù)[13]。文獻(xiàn)[14]基于廣義差分隱私技術(shù)添加噪聲以擾動(dòng)用戶的位置信息，實(shí)現(xiàn)了用戶敏感漸進(jìn)不可區(qū)分。文獻(xiàn)[15]和文獻(xiàn)[16]提出了一個(gè)2階段的隱私預(yù)算分配策略保護(hù)頻繁數(shù)據(jù)的隱私。此類方案單獨(dú)處理數(shù)據(jù)效率過低，且破壞了事務(wù)數(shù)據(jù)間的聯(lián)系，而頻繁位置數(shù)據(jù)的項(xiàng)集之間存在獨(dú)立且相聯(lián)的數(shù)據(jù)特性。最后，頻繁模式樹[17]、Trie樹[18]等數(shù)據(jù)結(jié)構(gòu)在處理頻繁數(shù)據(jù)挖掘中，能有效維持?jǐn)?shù)據(jù)項(xiàng)間的關(guān)系，常用于頻繁數(shù)據(jù)挖掘。文獻(xiàn)[19]使用Trie樹存儲(chǔ)事務(wù)數(shù)據(jù)，基于壓縮感知技術(shù)對(duì)事務(wù)數(shù)據(jù)的支持度計(jì)數(shù)添加滿足差分隱私約束的噪聲。文獻(xiàn)[20]在文獻(xiàn)[19]的基礎(chǔ)上運(yùn)用差分隱私設(shè)計(jì)了工業(yè)物聯(lián)網(wǎng)中位置大數(shù)據(jù)的隱私保護(hù)方案。文獻(xiàn)[21]將差分隱私引入興趣點(diǎn)推薦系統(tǒng)，保護(hù)用戶位置隱私的同時(shí)，又提供了較好的興趣點(diǎn)推薦效果。上述方案雖然能夠兼顧位置數(shù)據(jù)的隱私保護(hù)和可用性，但均存在一個(gè)問題，即沒有對(duì)擾動(dòng)后的位置數(shù)據(jù)支持度計(jì)數(shù)進(jìn)行后置處理，而第三方發(fā)布的LBS用戶共享位置數(shù)據(jù)集中位置數(shù)據(jù)的支持度計(jì)數(shù)應(yīng)為整數(shù)。

綜上所述，第三方發(fā)布的共享位置數(shù)據(jù)集，經(jīng)差分隱私后能夠兼顧LBS用戶位置數(shù)據(jù)的可用性和隱私保護(hù)，但未考慮頻繁位置數(shù)據(jù)的項(xiàng)集之間存在獨(dú)立且相聯(lián)的數(shù)據(jù)特性。目前，雖然已有將Trie樹結(jié)構(gòu)引入隱私保護(hù)以維持事務(wù)數(shù)據(jù)獨(dú)立且相聯(lián)的特性，但在位置隱私保護(hù)方案中構(gòu)建位置搜索樹的效率不高，且因未對(duì)擾動(dòng)后的位置數(shù)據(jù)支持度計(jì)數(shù)進(jìn)行后置處理使得可用性降低。本方案引入Trie樹結(jié)構(gòu)存儲(chǔ)位置數(shù)據(jù)和頻率，基于字典的查詢方式提高處理位置數(shù)據(jù)的效率?；谝恢滦约s束后置處理對(duì)擾動(dòng)后的數(shù)據(jù)進(jìn)行優(yōu)化，提高位置數(shù)據(jù)的可用性，使得共享位置數(shù)據(jù)更加安全。

1 基于差分隱私的位置保護(hù)方案

1.1 總體框架

近年來，互聯(lián)網(wǎng)和通信技術(shù)的飛速發(fā)展，使得LBS普遍應(yīng)用于人們的日常生活中。用戶在使用這些應(yīng)用時(shí)產(chǎn)生的位置信息被LBS應(yīng)用收集，用于數(shù)據(jù)分析，如頻繁位置挖掘、出行規(guī)律分析等，甚至發(fā)布給第三方獲取額外收益。本研究基于差分隱私設(shè)計(jì)了一種LBS用戶位置隱私保護(hù)方案，實(shí)現(xiàn)用戶敏感位置保護(hù)。

所提方案中，定義用戶被收集的地理位置信息為共享位置數(shù)據(jù)，方案總體框架如圖1所示。首先，對(duì)用戶共享位置數(shù)據(jù)集進(jìn)行預(yù)處理，匿去用戶身份、查詢內(nèi)容等信息，將位置信息進(jìn)行編號(hào)并構(gòu)建位置事務(wù)數(shù)據(jù)庫。位置事務(wù)數(shù)據(jù)庫是包含標(biāo)志符、位置項(xiàng)集和頻繁次數(shù)共3列的表格形式，行表示不同位置屬性的集合。其次，基于位置事務(wù)數(shù)據(jù)庫建立Trie樹，并完成頻繁位置的選取，其中頻繁位置表示用戶此階段經(jīng)常使用的位置信息，包含用戶的敏感位置。再次，采用差分隱私下的拉普拉斯機(jī)制對(duì)頻繁位置的支持度進(jìn)行擾動(dòng)，泛化用戶的敏感位置達(dá)到隱私保護(hù)的效果。最后，對(duì)擾動(dòng)后的數(shù)據(jù)進(jìn)行后置處理以提高位置數(shù)據(jù)的可用性，并返回處理后的數(shù)據(jù)進(jìn)行查詢分析。

1.2 方案設(shè)計(jì)

設(shè)計(jì)一種基于差分隱私的LBS用戶位置隱私保護(hù)方案，在保護(hù)共享位置數(shù)據(jù)隱私安全的同時(shí)較好地維持了數(shù)據(jù)可用性。將位置數(shù)據(jù)預(yù)處理后構(gòu)建Trie位置樹，并使用指數(shù)機(jī)制進(jìn)行頻繁位置選取;對(duì)選取的頻繁位置采用拉普拉斯機(jī)制，擾動(dòng)其真實(shí)支持度，泛化敏感位置信息;對(duì)擾動(dòng)后的數(shù)據(jù)進(jìn)行后置處理，增強(qiáng)數(shù)據(jù)的可用性。

1.2.1 基于指數(shù)機(jī)制的頻繁位置選取共享位置數(shù)據(jù)集包含用戶的身份、訪問時(shí)間、當(dāng)前位置信息、經(jīng)緯度和查詢條件等內(nèi)容，LBS應(yīng)用在用戶授權(quán)下對(duì)位置信息進(jìn)行分析處理或向第三方發(fā)布，需要考慮用戶的隱私安全和位置數(shù)據(jù)的可用性。本方案兼顧隱私保護(hù)和位置數(shù)據(jù)可用性，首先對(duì)共享位置數(shù)據(jù)集進(jìn)行預(yù)處理，為集合中的位置數(shù)據(jù)分配編號(hào)，將共享位置數(shù)據(jù)集轉(zhuǎn)化為只包含編號(hào)和位置數(shù)據(jù)的集合。將此集合內(nèi)容轉(zhuǎn)化為位置事務(wù)數(shù)據(jù)庫，并用Trie數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)位置事務(wù)數(shù)據(jù)庫的內(nèi)容，位置事務(wù)數(shù)據(jù)庫如表1示。

當(dāng)用戶的位置處于字典中時(shí)，其頻繁次數(shù)上升一次;

當(dāng)字典中查找不到該位置時(shí)，將該位置添加進(jìn)字典中，并令該位置頻繁次數(shù)取值為1。之后，只需掃描一次即可構(gòu)建位置事務(wù)數(shù)據(jù)庫，避免了在原有數(shù)據(jù)庫中對(duì)位置信息的多次查找，提高了處理效率?；诒?構(gòu)建位置數(shù)據(jù)的Trie樹如圖2示。

圖2包含了位置事務(wù)數(shù)據(jù)庫的全部項(xiàng)集，節(jié)點(diǎn)表示位置數(shù)據(jù)，節(jié)點(diǎn)中的支持度表示頻繁位置次數(shù)。位置Trie樹維持了事務(wù)數(shù)據(jù)的相聯(lián)特性，在Trie樹上進(jìn)行頻繁位置選取效率更高。此外，拉普拉斯機(jī)制擾動(dòng)的是節(jié)點(diǎn)的頻繁次數(shù)而非共享數(shù)據(jù)集中的單個(gè)位置數(shù)據(jù)，可有效降低拉普拉斯加噪的頻率并提高數(shù)據(jù)的處理效率。在頻繁位置選取中，以頻繁次數(shù)劃分用戶的敏感位置。實(shí)際應(yīng)用中可融入多個(gè)參數(shù)，如使用當(dāng)前位置的時(shí)間按照用戶敏感時(shí)間段分配不同的權(quán)值，從而更好地區(qū)分敏感位置?；诓罘蛛[私指數(shù)機(jī)制的頻繁位置選取過程如下。

令按層遍歷選出的頻繁次數(shù)不小于m的位置數(shù)據(jù)為N個(gè)，其構(gòu)成頻繁位置集S={FL1，F(xiàn)L2，…，F(xiàn)LN}。差分隱私下的指數(shù)機(jī)制隱私預(yù)算為ε1，則前k個(gè)頻繁位置中每次選取所分配的隱私預(yù)算為ε1/k。本方案中，影響位置敏感性的因素僅由位置頻繁次數(shù)決定，故指數(shù)機(jī)制中打分函數(shù)可定義為位置頻繁次數(shù)，如式（1）所示：

u（S，F(xiàn)Li）=CLi（FLi）。（1）

式中：u（S，F(xiàn)Li）為指數(shù)機(jī)制的打分函數(shù);CLi（FLi）表示位置FLi的頻繁次數(shù)。

打分函數(shù)u（S，F(xiàn)Li）的敏感度Δu為1。而每次選取所分配的隱私預(yù)算為ε1/k，指數(shù)機(jī)制如式（2）所示：

Pr（FLi）∝exp（εu（S，F(xiàn)Li）2Δu）=exp（ε1u（S，F(xiàn)Li）2k）。（2）

根據(jù)式（2）計(jì)算位置數(shù)據(jù)的歸一化概率，如式（3）所示：

Pr（FLi）=exp（ε1u（S，F(xiàn)Li）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k），（3）

式（3）是位置數(shù)據(jù)歸一化后的指數(shù)機(jī)制輸出概率值，該值與位置頻繁次數(shù)成正比，通過指數(shù)機(jī)制選取前k個(gè)位置數(shù)據(jù)可有效保護(hù)位置的頻繁次數(shù)，不被數(shù)據(jù)分析人員獲取。

1.2.2 基于拉普拉斯機(jī)制的加噪處理

運(yùn)用差分隱私下的指數(shù)機(jī)制思想選取前k個(gè)頻繁位置數(shù)據(jù)，有效保護(hù)了頻繁位置選取過程中的頻繁次數(shù)隱私安全。然而，指數(shù)機(jī)制只用于頻繁項(xiàng)選取，并未對(duì)位置數(shù)據(jù)進(jìn)行擾動(dòng)，若作為最終結(jié)果輸出會(huì)造成嚴(yán)重的用戶隱私泄露問題。因此，在頻繁位置選取后，仍需采用拉普拉斯機(jī)制對(duì)選出的前k個(gè)頻繁位置加噪，擾動(dòng)其真實(shí)頻繁次數(shù)，從而保護(hù)用戶的隱私安全。拉普拉斯函數(shù)的概率密度如式（4）所示：

Pr（x，b）=12bexp（-xb）。（4）

令拉普拉斯機(jī)制加噪所分配的隱私預(yù)算為ε2，則對(duì)選取的k個(gè)頻繁位置次數(shù)加噪，每次所分配的隱私預(yù)算為ε2/k。查詢函數(shù)Q（FL）的敏感度為ΔQ，當(dāng)用Q（FL）表示位置頻繁次數(shù)時(shí)，ΔQ的值為1。定義b=ΔQ/（ε2/k）=k/ε2。則在式（4）的基礎(chǔ)上，拉普拉斯噪聲的定義如式（5）所示：

Lap（kε2）=ε22kexp（-ε2xk）。（5）

每次加噪擾動(dòng)后的查詢函數(shù)Q（FLi）如式（6）所示：

Q（FLi）=Q（FLi）+Lap（kε2）。（6）

通過拉普拉斯機(jī)制對(duì)k個(gè)頻繁位置的次數(shù)進(jìn)行擾動(dòng)，泛化了用戶敏感位置，從而保護(hù)了用戶的隱私安全。然而，加噪后的頻繁位置次數(shù)可能不為整數(shù)，若直接覆蓋原位置數(shù)據(jù)會(huì)降低數(shù)據(jù)的可用性。因此，需要對(duì)其進(jìn)行后置處理，以提高數(shù)據(jù)的可用性。

1.2.3 后置處理

采用一致性對(duì)數(shù)據(jù)進(jìn)行后置處理，以提高數(shù)據(jù)的可用性。一致性約束將后置處理轉(zhuǎn)化為一個(gè)保序回歸問題，不妨令CL（FL）={CL1（FL1），CL2（FL2），…，CLk（FLk）}表示擾動(dòng)后的位置頻繁次數(shù)集合，同時(shí)令CL（FΔL）={CL1（FΔL1），CL2（FΔL2），…，CLk（FΔLk）}表示一致性約束處理后位置頻繁次數(shù)集合。即在CLi（FΔLi）≥CLi+1（FΔLi+1）條件下，對(duì)式（7）進(jìn)行求解

min∑ki=1（CL（FL）-CL（FΔL））2。（7）

定理1 令Lk=minj∈[t，k]maxi∈[1，j]M[i，j]，Ut=maxi∈[1，t]mini∈[i，k]M[i，j]，則在式（7）和其一致性條件約束下的解為CL（FDL）={L1，L2，…，Lk}={U1，U2，…，Uk}。其中，M[i，j]=∑jt=iCLt（FΔLt）/（j-i+1）。

基于定理1[20]求解出一致性約束處理后的位置頻繁次數(shù)集合，再對(duì)其進(jìn)行向上取整處理，以滿足頻繁位置次數(shù)為整數(shù)的性質(zhì)。例如，擾動(dòng)后的位置頻繁次數(shù)集合為CL（FL）={14.8，12.5，13.3}，經(jīng)過一致性約束處理后位置頻繁次數(shù)集合為CL（FΔL）={14.8，12.9，12.9}，采用向上取整處理后位置頻繁次數(shù)集合為{15，13，13}。將后置處理的結(jié)果更新到共享位置數(shù)據(jù)集中進(jìn)行發(fā)布，保護(hù)敏感位置的同時(shí)具有較好的位置數(shù)據(jù)可用性。

2 安全性分析

對(duì)方案的安全可行性進(jìn)行分析，證明其滿足ε-差分隱私[11]。首先對(duì)指數(shù)機(jī)制進(jìn)行差分隱私分析，證明其滿足ε1-差分隱私;其次對(duì)拉普拉斯機(jī)制進(jìn)行差分隱私分析，證明其滿足ε2-差分隱私。綜合以上2點(diǎn)，本方案滿足ε-差分隱私。

定理2 令S={FL1，F(xiàn)L2，…，F(xiàn)LN}為頻繁位置集合，差分隱私下的指數(shù)機(jī)制隱私預(yù)算為ε1，采用均勻分配每次選取所分配的隱私預(yù)算為ε1/k。指數(shù)機(jī)制的打分函數(shù)為u（S，F(xiàn)Li），打分函數(shù)u（S，F(xiàn)Li）的敏感度Δu為1。則指數(shù)機(jī)制滿足ε1-差分隱私。

證明 令M（S，i）（1≤i≤k）表示第i次從頻繁位置集合S中選取頻繁位置FLi;S表示集合S的相鄰數(shù)據(jù)集。則指數(shù)機(jī)制的概率比值如式（8）所示：

Pr[M（S，i）=FLi]Pr[M（S，i）=FLi]=exp（ε1u（S，F(xiàn)Li）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）exp（ε1u（S，F(xiàn)Li）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）= exp（ε1（u（S，F(xiàn)Li）-u（S，F(xiàn)Li））2k）×∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）≤exp（ε12k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）。（8）

由敏感度定義對(duì)式（8）化簡(jiǎn)，結(jié)果如式（9）所示：

Pr[M（S，i）=FLi]Pr[M（S，i）=FLi]≤exp（ε12k）×∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）≤ exp（ε12k）×∑Ni=1exp（ε1（u（S，F(xiàn)Li）+1）2k）∑Ni=1exp（ε1u（S，F(xiàn)Li）2k）=exp（ε12k）×exp（ε12k）=exp（ε1k）。（9）

即每一次頻繁位置選取均滿足ε1/k-差分隱私。由差分隱私的串行性質(zhì)可知，本指數(shù)機(jī)制滿足ε1-差分隱私。

定理3 令S={FL1，F(xiàn)L2，…，F(xiàn)LN}表示頻繁位置集合，差分隱私下的拉普拉斯機(jī)制隱私預(yù)算為ε2，采用均勻分配每次添加拉普拉斯噪聲所分配的隱私預(yù)算為ε2/k。則添加噪聲的過程滿足ε2-差分隱私。

證明：不妨令擾動(dòng)后的位置頻繁次數(shù)集合為CL（FL）={CL1（FL1），CL2（FL2），…，CLk（FLk）}。同時(shí)，不妨令擾動(dòng)前的頻繁次數(shù)集合為CL（FL）={CL1（FL1），CL2（FL2），…，CLk（FLk）}。S表示集合S的相鄰數(shù)據(jù)集，Q（FL）表示查詢函數(shù)。對(duì)于每一次向FLi的頻繁次數(shù)CL1（FLi）添加噪聲擾動(dòng)而言，拉普拉斯機(jī)制的概率比值如式（10）所示：

Pr[Q（S，F(xiàn)Li）=CL（FLi）]Pr[Q（S，F(xiàn)Li）=CL（FLi）]=exp（-ε2|CL（FLi）S-CL（FLi）|k）exp（-ε2|CL（FLi）S-CL（FLi）|k）= exp（ε2k×（|CL（FLi）S-CL（FLi）|-|CL（FLi）S-CL（FLi）|））≤ exp（ε2k×|CL（FLi）S-CL（FLi）S|）≤exp（ε2k）。（10）

綜上所述，每一次加噪均滿足ε2/k-差分隱私。由差分隱私的串行性質(zhì)可知，拉普拉斯加噪過程滿足ε2-差分隱私。故從整體上而言，滿足ε-差分隱私。

3 仿真實(shí)驗(yàn)及結(jié)果分析

在Intel（R） Core（TM） i5-4210U CPU @ 1.70 GHz2.40 GHz處理器、4 GB內(nèi)存、Windows 10操作系統(tǒng)下進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)代碼采用Python 3.7編寫，并于PyCharm上運(yùn)行，所用的數(shù)據(jù)集為Foursquare dataset[22]，該數(shù)據(jù)集經(jīng)過處理后，包含24 941個(gè)用戶，28 593個(gè)位置興趣點(diǎn)和1 196 248個(gè)用戶的位置簽到數(shù)據(jù)。以下從時(shí)間和效用性2個(gè)方面分析討論方案的敏感隱私保護(hù)和數(shù)據(jù)可用性。

3.1 時(shí)間分析

時(shí)間是衡量算法效率的因素之一，從建立Trie樹的時(shí)間和挑選出前k個(gè)頻繁位置的時(shí)間2個(gè)角度進(jìn)行計(jì)算分析，并與LPT-DP-K[20]的算法進(jìn)行對(duì)比分析。先對(duì)原數(shù)據(jù)集進(jìn)行預(yù)處理，使預(yù)處理后的數(shù)據(jù)集僅包含位置編號(hào)和位置信息。從預(yù)處理后的數(shù)據(jù)集中選取100，200，500，1 000行數(shù)據(jù)，本方案（Trie）和LPT-DP-K方案（ergod）建立Trie樹的時(shí)間如圖3所示。

從圖3可看出，本方案和LPT-DP-K方案建立Trie樹的時(shí)間效率都很高，且本方案優(yōu)于LPT-DP-K方案。通過新建字典的方式構(gòu)建位置數(shù)據(jù)庫，當(dāng)數(shù)據(jù)集位置在字典中，則位置頻繁次數(shù)加1，否則添加位置進(jìn)字典中，位置頻繁次數(shù)值取1。通過查詢字典，只需遍歷一次數(shù)據(jù)集。而LPT-DP-K方案通過先選出數(shù)據(jù)集中不同的項(xiàng)集N，再對(duì)每一個(gè)項(xiàng)集遍歷數(shù)據(jù)集統(tǒng)計(jì)每一項(xiàng)的頻率次數(shù)。

從預(yù)處理后的數(shù)據(jù)集中選取前1 000行位置數(shù)據(jù)建立Trie樹，使用無放回取最大值的思想和指數(shù)機(jī)制頻繁位置選取2種方法分別從Trie樹上選取前k=[10，20，50，100]個(gè)頻繁位置。2種方法選擇前k個(gè)頻繁位置的時(shí)間如圖4所示。

從圖4可看出，使用無放回取最大值的時(shí)間效率優(yōu)于指數(shù)機(jī)制頻繁位置選取。第1種是基于無放回取最大值的思想，取k次后即可獲取前k個(gè)頻繁位置數(shù)據(jù);第2種是基于差分隱私下的指數(shù)機(jī)制思想，先按層遍歷選出頻繁次數(shù)不小于m的位置數(shù)據(jù)，再運(yùn)用指數(shù)機(jī)制進(jìn)行篩選獲取前k個(gè)頻繁位置數(shù)據(jù)。第1種方法獲取前k個(gè)頻繁位置數(shù)據(jù)時(shí)間效率高，第2種方法可在選取前k個(gè)頻繁位置數(shù)據(jù)時(shí)保護(hù)位置的頻繁次數(shù)不被數(shù)據(jù)分析人員獲取。

3.2 效用性分析

效用性可用來衡量算法的隱私保護(hù)有效性和位置數(shù)據(jù)的可用性。

3.2.1 有效性分析

對(duì)有效性而言，對(duì)隱私保護(hù)前后的敏感位置進(jìn)行分析。從預(yù)處理后的數(shù)據(jù)集中選取前1 000行位置數(shù)據(jù)，取k頻繁位置分別為10，20，50和100時(shí)對(duì)隱私保護(hù)前后的敏感位置進(jìn)行對(duì)比分析，從而驗(yàn)證位置隱私保護(hù)方案的有效性。算法中定義訪問頻率h劃分敏感位置和非敏感位置。當(dāng)位置的頻繁次數(shù)值不小于h時(shí)，則將此位置劃分為敏感位置;否則，則將此位置劃分為非敏感位置。通過實(shí)驗(yàn)可得無差分隱私[9]和差分隱私后的敏感位置對(duì)比如表2所示。

為了更直觀地對(duì)比分析，基于表2的數(shù)據(jù)繪制隱私保護(hù)前后的敏感位置對(duì)比圖，如圖5所示。由圖5可知，采用差分隱私對(duì)頻繁位置進(jìn)行保護(hù)后敏感位置變多了，從而對(duì)原敏感位置進(jìn)行泛化。當(dāng)k為10時(shí)，敏感位置從2個(gè)變?yōu)?個(gè);當(dāng)k為20時(shí)，敏感位置從4個(gè)變?yōu)?個(gè);當(dāng)k為50時(shí)，敏感位置從11個(gè)變?yōu)?3個(gè);當(dāng)k為100時(shí)，敏感位置從21個(gè)變?yōu)?1個(gè)。

圖6更為直觀地顯示了50個(gè)模式隱私保護(hù)前后的敏感位置數(shù)量，其中藍(lán)點(diǎn)表示非敏感位置，紅點(diǎn)表示敏感位置。可見，采用拉普拉斯機(jī)制對(duì)頻繁位置的次數(shù)加噪后，使得部分非敏感位置轉(zhuǎn)變成敏感位置，泛化了最初的敏感位置，從而保護(hù)了用戶的位置隱私。此外，經(jīng)過泛化后的敏感位置集合仍包含用戶敏感位置，使得第三方對(duì)位置數(shù)據(jù)集的分析依然有著較高的可用性。

3.2.2 可用性分析

對(duì)于可用性而言，采用精確率和拒真率作為本方案的評(píng)價(jià)標(biāo)準(zhǔn)。設(shè)A為選取的原前k個(gè)頻繁位置的集合，B為拉普拉斯加噪后的前k個(gè)頻繁位置的集合。精確率定義為算法輸出的頻繁位置出現(xiàn)在集合A和集合B中的數(shù)量與集合B中的數(shù)量的比值，如式（11）所示。拒真率定義為算法輸出的頻繁位置出現(xiàn)在集合A中卻未在集合B中的比值，如式（12）所示：

精確率=A∩BB，（11）

拒真率=A∪B-BK。（12）

采用向上后置處理和一致性約束后置處理2種手段對(duì)加噪的位置頻率進(jìn)行處理。將從精確率和拒真率2個(gè)評(píng)價(jià)指標(biāo)對(duì)無后置處理[19-20]、向上后置處理[21]和一致性約束后置處理3種方法進(jìn)行對(duì)比分析。通過給定確切ε的值和變化k的取值計(jì)算3種方法的精確率和拒真率。實(shí)驗(yàn)中設(shè)ε=1，參數(shù)k的取值分別為20，40，60，80，100。則參數(shù)k值變化時(shí)，3種方法的精確率和拒真率分別如圖7和圖8所示。

從圖7可看出，隨著k值的增加，3種后置處理方案的準(zhǔn)確率均有所下降。使用向上后置處理和一致性約束后置處理后的準(zhǔn)確率明顯優(yōu)于無后置處理的準(zhǔn)確率。此外，隨著k值的增加，經(jīng)過一致性約束后置處理后的數(shù)據(jù)準(zhǔn)確率的變化曲線較為平緩。當(dāng)k取值為100時(shí)，一致性約束后置處理后的準(zhǔn)確率依然在80%左右，從另一方面驗(yàn)證了對(duì)加噪數(shù)據(jù)采用后置處理，可提高數(shù)據(jù)的可用性。從圖8可看出，隨著k值的增加，3種后置處理方案的拒真率均有所提升。拒真率用來衡量算法的效用性，拒真率越小，效用性越高。使用向上后置處理和一致性約束后置處理的數(shù)據(jù)拒真率較低，具有很好的效用性。

通過給定確切的k值和變化ε取值范圍計(jì)算3種方法的精確率和拒真率。實(shí)驗(yàn)中設(shè)k=200，參數(shù)ε的取值為0.05，0.10，0.50，0.75，1.00，1.50。則參數(shù)ε值變化時(shí)3種方法的精確率和拒真率分別如圖9和圖10所示。從圖9可看出，隨著ε值的增加，3種后置處理方案的精確率均有所上升。使用向上后置處理和一致性約束后置處理后的精確率明顯優(yōu)于無后置處理的精確率。隨著隱私預(yù)算的增加，數(shù)據(jù)可用性越高，但隱私保護(hù)力度降低。此外，當(dāng)ε取值為1時(shí)，一致性約束后置處理后的準(zhǔn)確率在85%左右，從另一方面驗(yàn)證了對(duì)加噪數(shù)據(jù)采用后置處理，可提高數(shù)據(jù)的可用性。從圖10可看出，隨著ε值的增加，3種后置處理方案的拒真率有所下降。拒真率用來衡量算法的效用性，拒真率越小，效用性越高。從圖10可發(fā)現(xiàn)，固定k值和改變?chǔ)湃≈禃r(shí)，使用向上后置處理和一致性約束后置處理的數(shù)據(jù)拒真率較低，具有很好的效用性。因此，本方案能有效保護(hù)用戶的隱私安全，并具有較好的數(shù)據(jù)可用性。

4 結(jié) 語

為了解決共享位置數(shù)據(jù)的隱私保護(hù)和可用性不足的問題，提出了一種基于差分隱私的位置隱私保護(hù)方案。首先，采用Trie數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)位置數(shù)據(jù)和其支持度，保持了頻繁位置數(shù)據(jù)特性，提高了位置數(shù)據(jù)處理效率。其次，使用差分隱私下的拉普拉斯機(jī)制擾動(dòng)頻繁位置支持度，保護(hù)了用戶的敏感位置。最后，對(duì)擾動(dòng)后的數(shù)據(jù)進(jìn)行后置處理，并通過不同的后置處理方法進(jìn)行對(duì)比，提高了數(shù)據(jù)的可用性。

未來工作將圍繞快速建立Trie樹提高算法效率和考慮多因素篩選敏感位置2個(gè)方面開展研究，首先使用hash表完成位置事務(wù)數(shù)據(jù)庫的統(tǒng)計(jì)構(gòu)建，基于堆結(jié)構(gòu)進(jìn)行查找并完成頻繁位置指數(shù)機(jī)制選取;其次綜合考慮頻繁次數(shù)和時(shí)間等多個(gè)位置因素，通過不同的權(quán)重，從可信計(jì)算的角度更為準(zhǔn)確地篩選敏感位置，設(shè)計(jì)出更適用于LBS用戶的位置隱私保護(hù)方案。

參考文獻(xiàn)/References：

[1] WANG Jinbao，CAI Zhipeng，LI Yingshu，et al.Protecting query privacy with differentially private k-anonymity in location-based services[J].Personal and Ubiquitous Computing，2018，22（3）：453-469.

[2] DARGAHI T，AMBROSIN M，CONTI M，et al.ABAKA：A novel attribute-based k-anonymous collaborative solution for LBSs[J].Computer Communications，2016，85（1）：1-13.

[3] 劉海，李興華，雒彬，等.基于區(qū)塊鏈的分布式K匿名位置隱私保護(hù)方案[J].計(jì)算機(jī)學(xué)報(bào)，2019，42（5）：942-960.

LIU Hai，LI Xinghua，LUO Bin，et al.Distributed K-anonymous location privacy protection scheme based on blockchain[J].Chinese Journal of Computers，2019，42（5）：942-960.

[4] WANG Shengling， HU Qin，SUN Yunchuan，et al.Privacy preservation in location-based services[J].IEEE Communications Magazine，2018，56（3）：134-140.

[5] 萬盛，李鳳華，牛犇，等.位置隱私保護(hù)技術(shù)研究進(jìn)展[J].通信學(xué)報(bào)，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.

[6] SWEENEY L.K-anonymity：A model for protecting privacy[J].International Journal of Uncertainty Fuzziness & Knowledge Based Systems，2002，10 （5）：557-570.

[7] 張嘯劍，孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（4）：927-949.

ZHANG Xiaojian，MENG Xiaofeng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers，2014，37（4）：927-949.

[8] WANG Yue，YANG Lin，CHEN Xiaoyun，et al.Enhancing social network privacy with accumulated non-zero prior knowledge[J].Information Sciences，2018，445/446：6-21.

[9] ZHANG P，DURRESI M，DURRESI A.Internet network location privacy protection with multi-access edge computing[J].Computing，2021，103：473-490.

[10]付鈺，俞藝涵，吳曉平.大數(shù)據(jù)環(huán)境下差分隱私保護(hù)技術(shù)及應(yīng)用[J].通信學(xué)報(bào)，2019，40（10）：157-168.

FU Yu，YU Yihan，WU Xiaoping.Differential privacy protection technology and its application in big data environment[J].Journal on Communications，2019，40（10）：157-168.

[11]DWORK C.Differential privacy[C]// Proceedings of the 33rd International Conference on Automata，Languages and Programming （ICALP 2006）.Berlin：Springer，2006：1-12.

[12]GENG Q，VISWANATH P.The optimal noise-adding mechanism in differential privacy[J].IEEE Transactions on Information Theory，2016，62（2）：925-951.

[13]丁麗萍，盧國慶.面向頻繁模式挖掘的差分隱私保護(hù)研究綜述[J].通信學(xué)報(bào)，2014，35（10）：200-209.

DING Liping，LU Guoqing.Survey of differential privacy in frequent pattern mining[J].Journal on Communications，2014，35（10）：200-209.

[14]王斌，張磊，張國印.敏感漸進(jìn)不可區(qū)分的位置隱私保護(hù)[J].計(jì)算機(jī)研究與發(fā)展，2020，57（3）：616-630.

WANG Bin，ZHANG Lei，ZHANG Guoyin.A gradual sensitive indistinguishable based location privacy protection scheme[J].Journal of Computer Research and Development，2020，57（3）：616-630.

[15]盧國慶，張嘯劍，丁麗萍，等.差分隱私下的一種頻繁序列模式 挖掘方法[J].計(jì)算機(jī)研究與發(fā)展，2015，52（12）：2789-2801.

LU Guoqing，ZHANG Xiaojian，DING Liping，et al.Frequent sequential pattern mining under differential privacy[J].Journal of Computer Research and Development，2015，52（12）：2789-2801.

[16]張嘯劍，王淼，孟小峰.差分隱私保護(hù)下一種精確挖掘top-k頻繁模式方法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（1）：104-114.

ZHANG Xiaojian，WANG Miao，MENG Xiaofeng.An accurate method for mining top-k frequent pattern under differential privacy[J].Journal of Computer Research and Development，2014，51（1）：104-114.

[17]BODON F.A fast apriori implementation[J].Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations，2003，90：654-667.

[18]LE P，VO B，HONG P，et al.Incremental mining frequent itemsets based on the trie structure and the pre-large itemsets[C]// IEEE International Conference on Granular Computing.Taiwan：IEEE，2012：369-373.

[19]歐陽佳，印鑒，劉少鵬，等.一種有效的差分隱私事務(wù)數(shù)據(jù)發(fā)布策略[J].計(jì)算機(jī)研究與發(fā)展，2014，51（10）：2195-2205.

OUYANG Jia，YIN Jian，LIU Shaopeng，et al.An effective differential privacy transaction data publication strategy[J].Journal of Computer Research and Development，2014，51（10）：2195-2205.

[20]LI C，PALANISAMY B，JOSHI J.Differentially private trajectory analysis for points-of-interest recommendation[C]// 2017 IEEE International Congress on Big Data （BigData Congress）.Honolulu：IEEE，2017：49-56.

[21]YIN Chunyong，XI Jinwen，SUN Ruxia，et al.Location privacy protection based on differential privacy strategy for big data in industrial internet of things[J].IEEE Transactions on Industrial Informatics，2018，14（8）：3628-3636.

[22]LI Huayu，GE Yong，HONG R，et al.Point-of-interest recommendations：Learning potential check-ins from friends[C]//The 22nd ACM SIGKDD International Conference.[S.l]：ACM，2016：975-984.