張海濤，汪佩佩

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

0 引 言

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

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

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

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

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

1.1 基本定義

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

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

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

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

1.2 推理攻擊步驟

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

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

(2)對所有Rn(Rn∈LR)，利用定義2進行敏感位置檢測。

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

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

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

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

(2)利用定義4對LR中的所有Rn進行位置獨立性檢測。

(3)將獨立性位置進行標注，作為對用戶隱私進行攻擊的依據(jù)。

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

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

2.1 系統(tǒng)架構

為應對基于敏感位置和位置獨立性的隱私推理攻擊，設計了基于隱私保護服務器的推薦系統(tǒng)架構。整個系統(tǒng)架構主要由用戶、應用服務器、隱私保護服務器三部分組成。推薦及隱私保護過程如下：

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

(2)隱私保護服務器收到推薦列表后，會對列表中的數(shù)據(jù)進行隱私檢測，然后將處理后的數(shù)據(jù)返回給應用服務器。

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

2.2 算法實現(xiàn)

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

(1)用戶提出位置服務請求。

(2)應用服務器接收用戶請求信息，計算用戶相似度，生成推薦列表。

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

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

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

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

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

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

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

輸出：推薦列表(RL)

數(shù)據(jù)庫：用戶位置數(shù)據(jù)(DB)、敏感位置數(shù)據(jù)(SD)、獨立性位置數(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行是將移動終端位置及位置請求信息導入到數(shù)據(jù)庫中；第2行是一個循環(huán)推薦過程，當推薦結(jié)果的數(shù)量滿足用戶的需求時，已刪除敏感位置數(shù)據(jù)和獨立性位置數(shù)據(jù)，就退出循環(huán)；第4行是對移動終端的請求進行位置推薦；第5～6行是隱藏敏感位置數(shù)據(jù)；第7～8行是刪除獨立性位置數(shù)據(jù);第9～10行是返回推薦結(jié)果給用戶。

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

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

2.3 實例分析

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

圖1 地圖信息

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

實驗1：對比分析基于敏感位置的隱私檢測算法對推薦結(jié)果的影響。

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

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

圖2 進行隱私保護與不進行隱私保護檢測到的敏感位置平均數(shù)對比

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

圖4 進行隱私保護與不進行隱私保護的平均檢測時間對比

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

實驗2：對比分析基于位置獨立性的隱私檢測算法對推薦結(jié)果的影響。

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

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

進行獨立性檢測的推薦結(jié)果與正常推薦結(jié)果的對比如下：

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

(2)進行獨立性檢測的推薦中檢測到的具有獨立性位置的平均數(shù)是3，而正常推薦中沒有檢測到獨立性位置數(shù)據(jù)。

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

4 結(jié)束語

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

參考文獻：

[1] 涂金龍.基于tag的個性化推薦技術研究[D].重慶：重慶大學,2013.

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

[3] 孫冬婷.協(xié)同過濾推薦系統(tǒng)中的冷啟動問題研究[D].長沙：國防科學技術大學,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] 王付強,彭甫镕,丁小煥,等.基于位置的非對稱相似性度量的協(xié)同過濾推薦算法[J].計算機應用,2016,36(1):171-174.

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

[7] 李 青,尹四清.結(jié)合用戶偏好和相似性的網(wǎng)絡結(jié)構推薦算法[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] 鞠 娜.移動互聯(lián)網(wǎng)的大數(shù)據(jù)處理關鍵技術[J].信息與電腦,2015(23):38.