基于位置推薦中的隱私保護(hù)方法研究

張海濤，汪佩佩

(1.南京郵電大學(xué) 地理與生物信息學(xué)院，江蘇 南京 210023; 2.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

近年來(lái)，隨著人們從海量信息中找到自己所需要位置信息的需求日益強(qiáng)烈，位置推薦系統(tǒng)得到了廣泛的應(yīng)用[1-3]?；谖恢玫耐扑]系統(tǒng)主要是利用用戶向服務(wù)器發(fā)送位置服務(wù)請(qǐng)求以及用戶所在的地理位置來(lái)為用戶提供個(gè)性化的服務(wù)。推薦系統(tǒng)結(jié)合用戶的興趣偏好與地理位置，對(duì)服務(wù)的內(nèi)容進(jìn)行分析，最終返回用戶所需要的服務(wù)信息[4]。在位置推薦系統(tǒng)中，服務(wù)器為給用戶提供個(gè)性化服務(wù)，會(huì)儲(chǔ)存記錄大量用戶的評(píng)價(jià)及推薦信息，并從中挖掘出隱藏的、有用的信息，從而為請(qǐng)求用戶返回有效的推薦結(jié)果[5]。但是，這些位置推薦服務(wù)，會(huì)對(duì)用戶的隱私構(gòu)成一定的威脅。

位置推薦系統(tǒng)當(dāng)前面臨著基于敏感位置和位置獨(dú)立性的隱私推理攻擊。敏感位置推理攻擊是指攻擊者結(jié)合推薦結(jié)果中的敏感位置數(shù)據(jù)及相關(guān)的背景知識(shí)，推斷出用戶的偏好信息[6-7]和社會(huì)屬性。位置獨(dú)立性推理是指攻擊者結(jié)合推薦結(jié)果中的獨(dú)立性位置數(shù)據(jù)和收集到的其他用戶信息，獲取用戶隱私信息。截止目前，已有大量的研究指出，位置推薦系統(tǒng)在為用戶提供服務(wù)時(shí)會(huì)造成用戶隱私的泄露。因此，位置推薦過(guò)程中的隱私保護(hù)成為當(dāng)前研究的熱點(diǎn)。

針對(duì)位置推薦中的隱私保護(hù)問(wèn)題，國(guó)內(nèi)外學(xué)者已提出了很多解決方法。文獻(xiàn)[8-9]中提出通過(guò)匿名的方法來(lái)對(duì)用戶的位置隱私進(jìn)行保護(hù)。文獻(xiàn)[10-11]中提出了基于差分隱私保護(hù)的位置隱私保護(hù)機(jī)制。此外，Shao等[12]提出了一種屬性加密方案。文獻(xiàn)[13-14]提出了一種以密碼學(xué)為基礎(chǔ)的方案。Zhu等[15]基于移動(dòng)端APP流行度以及用戶的隱私需求設(shè)計(jì)了個(gè)性化的具有隱私感知功能的智能APP推薦系統(tǒng)。

但是，上述方法均不能對(duì)推薦結(jié)果中的敏感位置數(shù)據(jù)和獨(dú)立性位置數(shù)據(jù)做出有效處理。基于此，文中提出了一種基于敏感位置和獨(dú)立性位置推理攻擊的隱私保護(hù)方法。

1 基于位置推薦的隱私攻擊

1.1 基本定義

定義1(位置)：將位置定義為S={p1,p2,…,pn}，其中pn表示位置點(diǎn)的特征值。

定義2(敏感位置)：對(duì)于位置S，如果其任意特征值p(p∈S)具有敏感屬性，那么S就是敏感位置。

定義3(基于敏感位置的推理攻擊)：如果推薦系統(tǒng)返回給用戶的推薦線路R(u1)={S1,S2,…,Sn}滿足Sn∈R且Sn為敏感位置，則該推薦結(jié)果會(huì)使用戶受到基于敏感位置的推理攻擊。

定義5(基于位置獨(dú)立性的推理攻擊)：如果推薦系統(tǒng)返回給用戶的推薦線路R(u1)={S1,S2,…,Sn}滿足Sn∈R且F(Sn)=1，則該推薦結(jié)果會(huì)使用戶受到基于位置獨(dú)立性的推理攻擊。

1.2 推理攻擊步驟

基于敏感位置的推理攻擊的主要步驟如下：

(1)基于用戶提出的位置請(qǐng)求服務(wù)，服務(wù)器給用戶返回推薦列表LR={R1,R2,…,Rn}。

(2)對(duì)所有Rn(Rn∈LR)，利用定義2進(jìn)行敏感位置檢測(cè)。

(3)將敏感位置進(jìn)行標(biāo)注，作為對(duì)用戶隱私進(jìn)行攻擊的依據(jù)。

(4)輸出含敏感位置數(shù)據(jù)的推薦列表。

基于位置獨(dú)立性的推理攻擊的主要步驟如下：

(1)服務(wù)器返回滿足用戶需求的推薦列表LR。

(2)利用定義4對(duì)LR中的所有Rn進(jìn)行位置獨(dú)立性檢測(cè)。

(3)將獨(dú)立性位置進(jìn)行標(biāo)注，作為對(duì)用戶隱私進(jìn)行攻擊的依據(jù)。

(4)輸出含獨(dú)立性位置數(shù)據(jù)的推薦列表。

2 感知隱私推理攻擊的位置推薦算法

2.1 系統(tǒng)架構(gòu)

為應(yīng)對(duì)基于敏感位置和位置獨(dú)立性的隱私推理攻擊，設(shè)計(jì)了基于隱私保護(hù)服務(wù)器的推薦系統(tǒng)架構(gòu)。整個(gè)系統(tǒng)架構(gòu)主要由用戶、應(yīng)用服務(wù)器、隱私保護(hù)服務(wù)器三部分組成。推薦及隱私保護(hù)過(guò)程如下：

(1)用戶發(fā)送位置服務(wù)請(qǐng)求給應(yīng)用服務(wù)器，應(yīng)用服務(wù)器結(jié)合請(qǐng)求用戶和其他用戶的位置信息，找到相似度最高的用戶信息，以此為基礎(chǔ)生成推薦列表，并將其發(fā)送給隱私保護(hù)服務(wù)器。

(2)隱私保護(hù)服務(wù)器收到推薦列表后，會(huì)對(duì)列表中的數(shù)據(jù)進(jìn)行隱私檢測(cè)，然后將處理后的數(shù)據(jù)返回給應(yīng)用服務(wù)器。

(3)應(yīng)用服務(wù)器將推薦結(jié)果返回給用戶[16]。

2.2 算法實(shí)現(xiàn)

根據(jù)2.1中提到的系統(tǒng)架構(gòu)，文中設(shè)計(jì)的兩種隱私保護(hù)算法的流程描述如下：

(1)用戶提出位置服務(wù)請(qǐng)求。

(2)應(yīng)用服務(wù)器接收用戶請(qǐng)求信息，計(jì)算用戶相似度，生成推薦列表。

(3)對(duì)推薦列表中的數(shù)據(jù)進(jìn)行敏感位置檢測(cè)，若包含敏感位置數(shù)據(jù)則隱藏。

(4)對(duì)推薦結(jié)果中的數(shù)據(jù)進(jìn)行獨(dú)立性位置檢測(cè)，如果包含獨(dú)立性位置數(shù)據(jù)則進(jìn)行步驟5，否則進(jìn)行步驟6。

(5)刪除獨(dú)立性位置數(shù)據(jù)。

(6)判斷推薦結(jié)果數(shù)量是否滿足用戶需求，滿足則輸出推薦結(jié)果，不滿足則重復(fù)步驟2～6。

算法實(shí)現(xiàn)的偽代碼如下所述：

算法：RL:Privacy Protection(ML,Count,Req)

輸入：移動(dòng)終端位置(ML)、所需位置推薦數(shù)(Count)及位置請(qǐng)求(Req)

輸出：推薦列表(RL)

數(shù)據(jù)庫(kù)：用戶位置數(shù)據(jù)(DB)、敏感位置數(shù)據(jù)(SD)、獨(dú)立性位置數(shù)據(jù)(UD)

1.InsertML,Req into DB

2.While(RR.Count=Count and RR not contain SD and RR not contained)

3.{

4.RL=Reco()

5.If RL contain SD

6.RS()

7.else if RL contain SD

8.RU()

9.else return RL

10.}

函數(shù)Reco()

1.M=ALS.train(D,ε)

2.for eachε'

3.{

4.if ALS.train(D,ε')優(yōu)于M

5.M=ALS.train(D,ε')

6.}

7.returnM

函數(shù)RS()

1.for eachr∈RL

2.{

3.ifrcontain SD

4.RL remover

5.}

6.return RL

函數(shù)RU()

1. for eachr∈RL

2.{

3.ifrcontain UD

4.RL remover

5.}

6.return RL

算法中第1行是將移動(dòng)終端位置及位置請(qǐng)求信息導(dǎo)入到數(shù)據(jù)庫(kù)中；第2行是一個(gè)循環(huán)推薦過(guò)程，當(dāng)推薦結(jié)果的數(shù)量滿足用戶的需求時(shí)，已刪除敏感位置數(shù)據(jù)和獨(dú)立性位置數(shù)據(jù)，就退出循環(huán)；第4行是對(duì)移動(dòng)終端的請(qǐng)求進(jìn)行位置推薦；第5～6行是隱藏敏感位置數(shù)據(jù)；第7～8行是刪除獨(dú)立性位置數(shù)據(jù);第9～10行是返回推薦結(jié)果給用戶。

函數(shù)Reco()主要是找到與請(qǐng)求用戶相似度較高的用戶信息。

函數(shù)RS()、RU()分別檢測(cè)推薦結(jié)果中有無(wú)敏感位置數(shù)據(jù)和獨(dú)立性位置數(shù)據(jù)。如果有，則將數(shù)據(jù)刪除，然后將推薦結(jié)果返回給用戶。

2.3 實(shí)例分析

下面結(jié)合一個(gè)例子，介紹算法的基本實(shí)現(xiàn)過(guò)程。用戶甲在圖1中的位置提出了景點(diǎn)推薦的請(qǐng)求，其提供的自身喜好程度由高到低排序依次為：電影院(9分)、商場(chǎng)(7分)、美食(5分)。

圖1 地圖信息

數(shù)據(jù)庫(kù)中已有的用戶信息如表1所示。

表1 數(shù)據(jù)庫(kù)用戶信息

(1)根據(jù)用戶的位置服務(wù)請(qǐng)求，將用戶與其他用戶進(jìn)行相似度計(jì)算，得到的相似度最高的3位用戶序號(hào)依次為2，4，5。

(2)將相似度最高的3位用戶2，4，5的路線作為推薦結(jié)果進(jìn)行隱私檢測(cè)，檢測(cè)結(jié)果如下：

路線A→B→H→E中不包含敏感位置和獨(dú)立性位置；

路線A→B→H→E→C中不包含敏感位置，但是包含獨(dú)立性位置；

路線K→B→I→J中不包含獨(dú)立性位置，但是包含敏感位置。

(3)刪除推薦結(jié)果中用戶4，5推薦的線路，遞補(bǔ)相似度較高的用戶6推薦的線路，并進(jìn)行隱私安全檢測(cè)，檢測(cè)結(jié)果正常。

(4)將線路A→B→H→E與A→B→H推薦給用戶甲。

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

實(shí)驗(yàn)數(shù)據(jù)主要由位置數(shù)據(jù)、樣本數(shù)據(jù)、評(píng)分?jǐn)?shù)據(jù)組成。位置數(shù)據(jù)由400個(gè)網(wǎng)格組成，樣本數(shù)據(jù)包含了發(fā)出服務(wù)請(qǐng)求的用戶信息，評(píng)分?jǐn)?shù)據(jù)包含了數(shù)據(jù)庫(kù)中所有用戶的信息。通過(guò)對(duì)評(píng)分?jǐn)?shù)據(jù)進(jìn)行統(tǒng)計(jì)，得到數(shù)據(jù)庫(kù)中的用戶數(shù)為4 382，有評(píng)分的網(wǎng)格數(shù)為385，用戶對(duì)網(wǎng)格的平均評(píng)分為5分(評(píng)分等級(jí)為1～10)，各評(píng)分等級(jí)網(wǎng)格數(shù)會(huì)隨著生成的實(shí)驗(yàn)數(shù)據(jù)的不同而有所變化。

實(shí)驗(yàn)1：對(duì)比分析基于敏感位置的隱私檢測(cè)算法對(duì)推薦結(jié)果的影響。

該實(shí)驗(yàn)將基于敏感位置的隱私檢測(cè)算法與位置推薦算法相結(jié)合，依次選取敏感等級(jí)G=6，7，8，9，10時(shí)生成的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)(當(dāng)G=6時(shí)，實(shí)驗(yàn)會(huì)對(duì)隱私等級(jí)大于等于6的推薦結(jié)果中的位置數(shù)據(jù)進(jìn)行隱私保護(hù))。將所得實(shí)驗(yàn)結(jié)果與正常推薦所得結(jié)果進(jìn)行比較，對(duì)比結(jié)果如圖2～4所示。

由圖2可以看出，進(jìn)行隱私保護(hù)時(shí)，敏感位置數(shù)會(huì)隨著隱私等級(jí)的升高而減少。不進(jìn)行隱私保護(hù)時(shí)，敏感位置數(shù)不受隱私等級(jí)的影響，數(shù)量一直為0。由圖3可以看出，進(jìn)行隱私保護(hù)時(shí)，推薦給用戶的位置數(shù)會(huì)隨著隱私等級(jí)的升高而增加，而不進(jìn)行隱私保護(hù)時(shí)，推薦給用戶的位置數(shù)不受隱私等級(jí)變化的影響，并且一直高于進(jìn)行隱私保護(hù)時(shí)系統(tǒng)推薦給用戶的位置數(shù)量。由圖4可以看出，進(jìn)行隱私保護(hù)時(shí)對(duì)推薦結(jié)果的平均檢測(cè)時(shí)間始終高于未進(jìn)行隱私保護(hù)時(shí)的平均檢測(cè)時(shí)間，但是差值不大。結(jié)果表明：基于敏感位置的隱私保護(hù)方法能有效找到推薦結(jié)果中的敏感位置數(shù)據(jù)，并且檢測(cè)到的敏感位置數(shù)、推薦給用戶的位置數(shù)以及平均推薦用時(shí)均隨敏感等級(jí)的增加呈線性變化，而不是指數(shù)型變化，變化范圍波動(dòng)不大;提出的算法具有代價(jià)小、速度快、可用性強(qiáng)的優(yōu)點(diǎn)，對(duì)用戶的隱私保護(hù)具有一定的意義。

圖2 進(jìn)行隱私保護(hù)與不進(jìn)行隱私保護(hù)檢測(cè)到的敏感位置平均數(shù)對(duì)比

圖3 進(jìn)行隱私保護(hù)與不進(jìn)行隱私保護(hù)推薦給用戶的位置平均數(shù)對(duì)比

圖4 進(jìn)行隱私保護(hù)與不進(jìn)行隱私保護(hù)的平均檢測(cè)時(shí)間對(duì)比

原因分析：進(jìn)行隱私保護(hù)時(shí)，隱私保護(hù)服務(wù)器會(huì)對(duì)推薦結(jié)果中的數(shù)據(jù)進(jìn)行敏感位置的檢測(cè)。在敏感范圍內(nèi)，隨著等級(jí)的升高，算法可檢測(cè)的范圍會(huì)變小，檢測(cè)到的敏感位置數(shù)就會(huì)降低，能推薦給用戶的位置數(shù)就隨之升高。而未進(jìn)行隱私保護(hù)時(shí)，應(yīng)用服務(wù)器不會(huì)將生成的推薦列表發(fā)送給隱私保護(hù)服務(wù)器進(jìn)行隱私檢測(cè)，而是將生成的推薦列表直接返回給用戶。因此，不管隱私等級(jí)如何變化，推薦結(jié)果中檢測(cè)到的敏感位置數(shù)都是0，推薦給用戶的位置數(shù)也一直保持不變，并且始終高于進(jìn)行隱私保護(hù)時(shí)推薦給用戶的位置數(shù)。

實(shí)驗(yàn)2：對(duì)比分析基于位置獨(dú)立性的隱私檢測(cè)算法對(duì)推薦結(jié)果的影響。

該實(shí)驗(yàn)將基于位置獨(dú)立性的隱私檢測(cè)算法與位置推薦算法相結(jié)合，依次選取5組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)(實(shí)驗(yàn)數(shù)據(jù)與敏感等級(jí)無(wú)關(guān))。表2是基于位置獨(dú)立性的檢測(cè)結(jié)果。

表2 基于位置獨(dú)立性的檢測(cè)結(jié)果

進(jìn)行獨(dú)立性檢測(cè)的推薦結(jié)果與正常推薦結(jié)果的對(duì)比如下：

(1)進(jìn)行獨(dú)立性檢測(cè)的推薦和正常推薦中推薦系統(tǒng)返回位置的平均數(shù)量均是26。

(2)進(jìn)行獨(dú)立性檢測(cè)的推薦中檢測(cè)到的具有獨(dú)立性位置的平均數(shù)是3，而正常推薦中沒(méi)有檢測(cè)到獨(dú)立性位置數(shù)據(jù)。

結(jié)果分析：由獨(dú)立性檢測(cè)結(jié)果對(duì)比可以看出，在正常的推薦結(jié)果中，具有獨(dú)立性特征的數(shù)據(jù)所占的比重達(dá)到了0.116。這樣的推薦結(jié)果會(huì)造成用戶隱私的泄露。因此，對(duì)推薦結(jié)果進(jìn)行獨(dú)立性位置檢測(cè)有很大的必要性；在性能方面，包含獨(dú)立性檢測(cè)的位置推薦與正常的位置推薦耗時(shí)平均相差143 ms，差值很小，可以忽略不計(jì)。實(shí)驗(yàn)結(jié)果表明：文中提出的算法不僅能有效降低用戶隱私泄露的風(fēng)險(xiǎn)，而且不會(huì)對(duì)生成推薦列表的時(shí)間帶來(lái)太大的影響，具有較高的可用性。

4 結(jié)束語(yǔ)

位置推薦系統(tǒng)中用戶位置數(shù)據(jù)的泄露嚴(yán)重影響著用戶的隱私安全，而現(xiàn)有的基于位置推薦中的隱私保護(hù)方法不能有效應(yīng)對(duì)基于敏感位置和位置獨(dú)立性的推理攻擊。為此，文中設(shè)計(jì)了一種基于敏感位置和獨(dú)立性位置的隱私保護(hù)方法。通過(guò)實(shí)驗(yàn)對(duì)比分析正常推薦結(jié)果和進(jìn)行敏感位置及獨(dú)立性位置檢測(cè)后的推薦結(jié)果。結(jié)果表明，該方法不會(huì)對(duì)生成推薦列表的時(shí)間帶來(lái)太大的影響，并且能實(shí)現(xiàn)敏感位置數(shù)據(jù)和獨(dú)立性位置數(shù)據(jù)的快速隱藏，具有較高的可用性。

參考文獻(xiàn)：

[1] 涂金龍.基于tag的個(gè)性化推薦技術(shù)研究[D].重慶：重慶大學(xué),2013.

[2] 藺 川.基于LBS移動(dòng)終端信息推薦系統(tǒng)的研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué),2016.

[3] 孫冬婷.協(xié)同過(guò)濾推薦系統(tǒng)中的冷啟動(dòng)問(wèn)題研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué),2010.

[4] MCNEE S M,RIEDL J,KONSTAN J A.Making recommendations better:an analytic model for human-recommender interaction[C]/Extended abstracts on human factors in computing systems.Montréal,Québec,Canada:ACM,2006:1103-1108.

[5] 王付強(qiáng),彭甫镕,丁小煥,等.基于位置的非對(duì)稱相似性度量的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用,2016,36(1):171-174.

[6] 付達(dá)杰,張小波.基于用戶興趣與隱私保護(hù)的網(wǎng)絡(luò)信息資源個(gè)性化推薦技術(shù)[J].景德鎮(zhèn)高專學(xué)報(bào),2015,30(6):42-45.

[7] 李 青,尹四清.結(jié)合用戶偏好和相似性的網(wǎng)絡(luò)結(jié)構(gòu)推薦算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(3):814-818.

[8] GAO Sheng,MA Jianfeng,SHI Weisong,et al.TrPF:A trajectory privacy-preserving framework for participatory sensing[J].IEEE Transactions on Information Forensics and Security,2013,8(6):874-887.

[9] NIU Ben,LI Qinghua,ZHU Xiaoyan,et al.Enhanceing privacy through caching in location-based services[C]//Proceedings of the IEEE conference on computer communications.Kowloon,Hong Kong,China:IEEE,2015:1017-1025.

[10] XIAO Yonghui,XIONG Li.Protecting locations with differential privacy under temporal correlations[C]//Proceedings of the 22nd ACM SIGSAC conference on computer and communications security.Denver,Colorado,USA:ACM,2015:1298-1309.

[11] TO H,GHINITA G,SHAHABI C.A framework for protecting worker location privacy in spatial crowd-sourcing[J].Proceedings of the VLDB Endowment,2014,7(10):919-930.

[12] SHAO Jun,LU Rongxing,LIN Xiaodong.FINE:A fine-grained privacy-preserving location-based services framework for mobiles devices[C]//Proceedings of the IEEE conference on computer communications.Toronto,ON,Canada:IEEE,2014:244-252.

[13] SAMANTHULA B K,CEN Lei,JIANG Wei,et al.Privacy-preserving and efficient friend recommendation in online social networks[J].Transactions on Data Privacy,2015,8(2):141-171.

[14] GONG Yanmin,GUO Yuanxiong,FANG Yuguang.A privacy-preserving task recommendation framework for mobile crowdsourcing[C]//Proceedings of the IEEE global communications conference.Austin,TX,USA:IEEE,2014:588-593.

[15] ZHU Hengshu,XIONG Hui,GE Yong,et al.Mobile app recommendations with security and privacy awareness[C]//Proceedings of the 20th SIGKDD international conference on knowledge discovery and data mining.New York,NY,USA:ACM,2014:951-960.

[16] 鞠 娜.移動(dòng)互聯(lián)網(wǎng)的大數(shù)據(jù)處理關(guān)鍵技術(shù)[J].信息與電腦,2015(23):38.