基于K近鄰的隱式位置訪問(wèn)隱私保護(hù)方法

2022-07-20 02:16:00王宏志

計(jì)算機(jī)仿真 2022年6期

王勇，王宏志

(1. 吉林建筑科技學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林長(zhǎng)春 130114 ；2. 長(zhǎng)春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林長(zhǎng)春 130012 )

1 引言

信息化時(shí)代的到來(lái)，以及智能終端的涌現(xiàn)，促進(jìn)了移動(dòng)互聯(lián)網(wǎng)的發(fā)展。移動(dòng)互聯(lián)網(wǎng)與傳統(tǒng)互聯(lián)網(wǎng)不同，在于其具有較強(qiáng)的身份鎖定功能，能夠不受時(shí)間與地點(diǎn)的限制，使用各類(lèi)傳輸方式完成信息傳輸。雖然為人們的生活提供一些便利，但同樣也會(huì)泄露個(gè)人隱私。攻擊者可根據(jù)個(gè)人位置訪問(wèn)數(shù)據(jù)獲取其住址、生活行為方式等敏感信息。這些信息一旦泄露就會(huì)對(duì)用戶隱私造成威脅。為此，需隱藏用戶的真實(shí)訪問(wèn)位置，但此種做法卻無(wú)法滿足用戶對(duì)高精度定位服務(wù)的需求。單一的隱私保護(hù)方式不能兼顧以上兩種需求，基于此，有關(guān)學(xué)者提出下述隱私保護(hù)策略。

文獻(xiàn)[1]提出群智感知網(wǎng)絡(luò)個(gè)性化位置隱私保護(hù)方法。結(jié)合用戶歷史訪問(wèn)軌跡，獲取用戶對(duì)不同位置的訪問(wèn)時(shí)間、頻率與規(guī)律性完成用戶社會(huì)屬性預(yù)測(cè)；結(jié)合位置具有的自然屬性，預(yù)測(cè)敏感等級(jí)，按照不同位置安全需求，設(shè)置隱私保護(hù)策略。文獻(xiàn)[2]研究一種基于位置服務(wù)隱私自相關(guān)的保護(hù)方法。綜合分析用戶自身與服務(wù)商緩存的查詢記錄，防止攻擊者通過(guò)歷史記錄對(duì)隱私信息進(jìn)行攻擊；在用戶隱私自關(guān)聯(lián)前提下，將簡(jiǎn)易隱私自關(guān)聯(lián)保護(hù)方法與擴(kuò)展隱私自關(guān)聯(lián)保護(hù)方法相結(jié)合，從時(shí)間與查詢范圍雙重維度下實(shí)現(xiàn)算法的擴(kuò)展，全方位保護(hù)用戶隱私信息。

但上述兩種算法會(huì)造成通信代價(jià)較高，用戶搜索效率降低的后果。為此，本文提出基于K近鄰的隱式位置訪問(wèn)隱私保護(hù)方法。隱式位置訪問(wèn)隱私保護(hù)的關(guān)鍵思想在于：結(jié)合當(dāng)前研究得出的隱私泄露方式，針對(duì)推測(cè)與條件軌跡集合，使用位置替換方式完成軌跡匿名化，此時(shí)兩個(gè)集合的大小會(huì)產(chǎn)生變化，使泄露模式的置信度降低到能被允許的閾值范圍內(nèi)。根據(jù)這一思想本文利用K近鄰方式進(jìn)行隱私保護(hù)。該方法是一種非常重要的查詢方法，其核心內(nèi)容是在固定集合內(nèi)查詢與興趣點(diǎn)最近的目標(biāo)。結(jié)合服務(wù)相似性、背景知識(shí)與信息熵等因素，構(gòu)建敏感位置推理模型，在情境感知基礎(chǔ)上實(shí)現(xiàn)隱式位置訪問(wèn)隱私保護(hù)。

2 隱式位置訪問(wèn)面臨的攻擊分析

要想實(shí)現(xiàn)隱私的全方位保護(hù)，必須了解所有威脅位置訪問(wèn)的事件類(lèi)型，本文從下述幾點(diǎn)探討了隱私保護(hù)技術(shù)面臨的攻擊種類(lèi)。

1)偽裝用戶威脅

偽裝用戶代表攻擊者假扮成普通用戶，通過(guò)邏輯推理或監(jiān)聽(tīng)用戶信息等手段，對(duì)用戶隱私造成威脅。按照攻擊形式差異，此種威脅分為下述三種：

被動(dòng)監(jiān)聽(tīng)：攻擊者假扮成一般用戶或直接對(duì)這些用戶進(jìn)行有效控制，利用隱私保護(hù)框架中用戶必須信任的原則，通過(guò)共享信息漏洞采集用戶真實(shí)訪問(wèn)位置。

三點(diǎn)定位：此種攻擊方式重點(diǎn)針對(duì)網(wǎng)絡(luò)中近鄰發(fā)現(xiàn)服務(wù)。攻擊者假扮為用戶，散布虛擬位置消息，觀察附近是否存在目標(biāo)，經(jīng)長(zhǎng)時(shí)間探測(cè)后，利用三點(diǎn)測(cè)量法獲取用戶實(shí)際方位位置信息。

誘探位置：該攻擊行為是指攻擊者主動(dòng)向攻擊對(duì)象發(fā)送誘探位置信息，由于受到這些位置信息影響，某些用戶匿名區(qū)域會(huì)出現(xiàn)改變。此種狀況下，攻擊者可根據(jù)匿名區(qū)域預(yù)測(cè)出用戶精準(zhǔn)的位置數(shù)據(jù)。假設(shè)目標(biāo)與攻擊者之間距離較大，結(jié)合匿名算法特性，用戶會(huì)調(diào)節(jié)匿名區(qū)域邊界，同時(shí)靠向探測(cè)區(qū)域。此時(shí)，攻擊者更加容易推測(cè)出用戶與誘探區(qū)域的位置，降低隱私保護(hù)程度。

2)基于用戶訪問(wèn)速度的威脅

基于用戶訪問(wèn)速度的攻擊一般針對(duì)連續(xù)型訪問(wèn)，此攻擊可根據(jù)地域背景相關(guān)信息推測(cè)出用戶的實(shí)際位置。假設(shè)

與

是相同用戶使用泛化法，分別在時(shí)間點(diǎn)

與

形成匿名區(qū)域。如果攻擊者具備網(wǎng)絡(luò)允許的最快訪問(wèn)速度

，則可結(jié)合匿名區(qū)域

與最大訪問(wèn)速度

增量重新形成用戶在

時(shí)間點(diǎn)能夠到達(dá)的區(qū)域

，此時(shí)將匿名區(qū)的范圍縮小到

和

的重合部分。

3)基于用戶背景信息的威脅

攻擊者事先了解用戶背景信息，例如社交關(guān)系、興趣等，結(jié)合這些信息推測(cè)出用戶經(jīng)常訪問(wèn)的位置。假設(shè)用戶的匿名區(qū)域中含有酒吧、書(shū)店與飯店三個(gè)語(yǔ)義詞語(yǔ)，如果攻擊者已經(jīng)確定用戶的身份為學(xué)生，則可推斷出該用戶訪問(wèn)與書(shū)店相關(guān)的信息概率會(huì)更大。

3 基于K近鄰的隱式位置訪問(wèn)隱私保護(hù)

3.1 位置訪問(wèn)系統(tǒng)模型

本文建立的系統(tǒng)模型是利用集中隱式保護(hù)框架，也就是通過(guò)某較為可信的第三方來(lái)執(zhí)行隱私保護(hù)機(jī)制，第三方的處理性能有助于用戶快速完成隱私保護(hù)。系統(tǒng)架構(gòu)如圖1所示。位置服務(wù)器具備全部地圖數(shù)據(jù)與用戶的歷史訪問(wèn)信息，所以它能夠按照相似性定義，事先給出相似地圖，并傳輸?shù)降谌健Ｏ嗨频貓D中包括服務(wù)相似度，能幫助第三方生成

近鄰的匿名候選區(qū)域。當(dāng)?shù)谌将@取用戶訪問(wèn)請(qǐng)求后，結(jié)合隱私保護(hù)方法實(shí)現(xiàn)對(duì)用戶請(qǐng)求的匿名處理，生成擾動(dòng)位置傳輸?shù)轿恢梅?wù)器進(jìn)行處理，并將處理結(jié)果通過(guò)第三方反饋給用戶，實(shí)現(xiàn)查詢服務(wù)。

圖1 系統(tǒng)模型圖

在該系統(tǒng)中主要存在感知群體、用戶與服務(wù)提供商三個(gè)參與角色，下述分別從功能、安全性等方面對(duì)其介紹。

1)感知群體：是用戶位置訪問(wèn)數(shù)據(jù)的采集者也是使用者。比如，某查詢酒店的應(yīng)用，其中酒店位置、價(jià)格等即為此應(yīng)用中認(rèn)證用戶上傳的，可將這些用戶作為感知群體。安全性假設(shè)為：僅有合法的、通過(guò)系統(tǒng)認(rèn)證的用戶才有上傳數(shù)據(jù)的資格，上傳者上傳的數(shù)據(jù)必須真實(shí)可靠。

2)查詢用戶：屬于數(shù)據(jù)的真實(shí)消費(fèi)者，可以向提供商發(fā)出

近鄰的查詢請(qǐng)求，比如查找與其較近的飯店、書(shū)店等。為保證所有查詢用戶的隱私安全，用戶可向服務(wù)商直接提交請(qǐng)求。

3)服務(wù)提供商：是服務(wù)的唯一提供者，主要完成信息采集、整理等任務(wù)。并對(duì)數(shù)據(jù)做加密處理，再外包給云平臺(tái)，降低自身成本。其安全假設(shè)為：服務(wù)商提供的信息是安全可靠的，但會(huì)對(duì)用戶隱私數(shù)據(jù)感興趣，以及對(duì)采集的用戶信息進(jìn)行分析。

3.2 敏感區(qū)域確定

要想確定用戶位置訪問(wèn)的敏感區(qū)域，需結(jié)合服務(wù)相似性、背景知識(shí)與信息熵等因素，利用這些信息生成標(biāo)簽相似地圖，確定敏感區(qū)域。

1)服務(wù)相似性

假設(shè)用戶

與

分別處于

與

兩處，在訪問(wèn)和自己最近的飯店，若獲取的訪問(wèn)結(jié)果相同，則表明兩個(gè)位置存在較強(qiáng)的服務(wù)相似性。結(jié)合訪問(wèn)結(jié)果的相似程度判斷兩個(gè)位置的服務(wù)相似性

(

，

((

，

)，(

，

))

(1)

式中，

代表相似度計(jì)算函數(shù)，

(

，

)為對(duì)位置坐標(biāo)訪問(wèn)結(jié)果排序后獲得的前

個(gè)結(jié)果集合，

是訪問(wèn)結(jié)果數(shù)量，0≤

≤1。

2)背景知識(shí)

為便于處理，將地圖分割成

的網(wǎng)格，任意一個(gè)網(wǎng)格均表示位置單元。其中，各單元均存在與其相對(duì)的歷史查詢幾率，表達(dá)式如下

(2)

3)信息熵

信息熵可以衡量隱私保護(hù)程度，該值越大，被攻擊者識(shí)別出可能性就越高。計(jì)算公式如下

(3)

式中，

是匿名集合內(nèi)位置查詢概率，其表達(dá)式如下

式中，

代表第

個(gè)位置的查詢概率。

4)標(biāo)簽相似地圖生成

為便于處理，將地圖分割為

的網(wǎng)格地圖

，且

，

=1，2，3，…，

}。位置服務(wù)器結(jié)合查詢函數(shù)

與已知用戶興趣點(diǎn)位置數(shù)據(jù)獲取所有位置單元的查詢結(jié)果，確定距離用戶最近的前

個(gè)興趣點(diǎn)，利用式(1)計(jì)算獲取全部單元的服務(wù)相似度

，同時(shí)將

=1的單元合并在一起，并給予相同標(biāo)簽。因此，將地圖

當(dāng)作包含各類(lèi)分區(qū)的標(biāo)簽相似地圖，表示為

，

，…，

}

(4)

則形成包括近鄰查詢數(shù)量的

過(guò)程如下：

步驟一：形成近鄰查詢結(jié)果表，如表1所示。

表1 近鄰查詢結(jié)果表

步驟二：結(jié)合表1近鄰查詢結(jié)果利用式(1)計(jì)算兩個(gè)位置之間的服務(wù)相似度。

步驟三：生成T，獲取具有不同分區(qū)的T。

步驟四：結(jié)合表1查詢結(jié)果獲取不同分區(qū)的服務(wù)相似度，將相似度較高的位置區(qū)域當(dāng)作敏感區(qū)域。

3.3 位置訪問(wèn)隱私保護(hù)

在確定敏感位置后，通過(guò)情景感知的方式完成隱私保護(hù)。假設(shè)用戶U的隱私保護(hù)需求表示為

(

)=〈(

，

)，…，(

，

)，…，(

，

)〉

(5)

第三方結(jié)合敏感位置能夠獲取用戶的敏感區(qū)域點(diǎn)集合

(

)={

，…，

}

(6)

當(dāng)?shù)谌将@得用戶的訪問(wèn)請(qǐng)求u(l，t，f)后，需評(píng)估該請(qǐng)求是否滿足隱私設(shè)定要求。

假設(shè)l代表用戶在t時(shí)間點(diǎn)上發(fā)布的興趣點(diǎn)，第三方需利用下述公式獲取兩次訪問(wèn)請(qǐng)求的時(shí)間間隔

-1

(7)

若

t，則說(shuō)明在兩次訪問(wèn)請(qǐng)求之間，此用戶沒(méi)有訪問(wèn)過(guò)其它興趣點(diǎn)。反之，用戶在兩次請(qǐng)求之間訪問(wèn)過(guò)其它興趣點(diǎn)l的機(jī)率p(l|l，l，u)可利用下述貝葉斯公式獲取：

(8)

將下述三種不同種類(lèi)的興趣點(diǎn)添加到用戶接下來(lái)可能訪問(wèn)的位置興趣點(diǎn)集合L中：距離用戶最近的k個(gè)興趣點(diǎn)；當(dāng)前興趣點(diǎn)訪問(wèn)后，其他用戶接下來(lái)最有可能訪問(wèn)的k個(gè)興趣點(diǎn)；具有最高評(píng)分的k個(gè)興趣點(diǎn)。

通過(guò)位置服務(wù)器對(duì)這些興趣點(diǎn)進(jìn)行評(píng)估，如果置信度較高，則不存在隱私泄露現(xiàn)象；反之，有隱私泄露危險(xiǎn)，應(yīng)及時(shí)停止對(duì)興趣點(diǎn)的訪問(wèn)，并將泄露信息反饋給用戶，達(dá)到保護(hù)隱私的目的。

4 仿真數(shù)據(jù)分析與研究

為驗(yàn)證所提隱式位置訪問(wèn)隱私保護(hù)算法性能，所處實(shí)驗(yàn)的硬件環(huán)境為：操作系統(tǒng)為64位

Windows

7惠普臺(tái)式計(jì)算機(jī)，配置是

CPU

為

Intel

7-4790，內(nèi)存是8

；軟件環(huán)境為：

Python

6，

Spyder

6。實(shí)驗(yàn)數(shù)據(jù)集合的相關(guān)信息如表2所示。實(shí)驗(yàn)中的用戶以某市為例，地域空間限定在10

×10

的正方形區(qū)域內(nèi)，該區(qū)域被劃分為100×100的網(wǎng)格。任意網(wǎng)格中的先驗(yàn)查詢概率根據(jù)此網(wǎng)格中全部興趣點(diǎn)的評(píng)論數(shù)量獲取。

表2 數(shù)據(jù)集合參數(shù)表

首先在上述仿真環(huán)境下，測(cè)試興趣點(diǎn)密度與

對(duì)用戶分區(qū)數(shù)量的影響。分別在高密度、中密度與低密度三種情況下通過(guò)不斷改變

值，來(lái)觀察用戶分區(qū)數(shù)量的變化情況，如圖2所示。

圖2 k對(duì)分區(qū)位置集合數(shù)量的影響

由圖2可知，實(shí)驗(yàn)初始階段，分區(qū)位置集合數(shù)量隨

值的增加逐漸增加，當(dāng)

值高于興趣點(diǎn)總數(shù)量的二分之一時(shí)，分區(qū)數(shù)量逐漸下降。這是因?yàn)?p>k

值較小時(shí)，每個(gè)網(wǎng)格內(nèi)查詢結(jié)果一致的概率較低，當(dāng)

達(dá)到一定量時(shí)，查詢結(jié)果相同的機(jī)率升高。此外，興趣點(diǎn)越稀疏，分區(qū)位置集合數(shù)量越小，分區(qū)面積越大，因此，用戶位置訪問(wèn)的隱私需求就越容易被滿足。此外，又考慮了

值對(duì)通信代價(jià)產(chǎn)生的影響，為方便分析，假定仿真中設(shè)置的用戶隱私需求都為5，即分區(qū)位置數(shù)量集合的信息熵等于5。利用文獻(xiàn)[1]與文獻(xiàn)[2]方法與本文方法進(jìn)行對(duì)比，當(dāng)

逐漸增加時(shí)，用戶通信代價(jià)情況如圖3所示。

圖3 通信代價(jià)對(duì)比圖

由圖3可看出，隨著

值的不斷增加，大體上的通信代價(jià)隨之增加，這是因?yàn)榉謪^(qū)數(shù)量隨著

值的增加而擴(kuò)大，造成每個(gè)分區(qū)面積較小。此時(shí)，為確保用戶隱私保護(hù)水平，必須加入大量混淆興趣點(diǎn)。本文方法無(wú)論在哪種分區(qū)密度下，通信代價(jià)均較為平穩(wěn)，并沒(méi)有隨著

值的增加出現(xiàn)大幅度增長(zhǎng)趨勢(shì)，表明該方法通信代價(jià)較小。為進(jìn)一步證明本文方法對(duì)近鄰搜索的性能，假設(shè)

代表匿名點(diǎn)，

為真實(shí)點(diǎn)，以上述兩點(diǎn)為中心進(jìn)行近鄰查詢，查詢內(nèi)容為用戶提交的申請(qǐng)，通過(guò)準(zhǔn)確率

判斷服務(wù)質(zhì)量，計(jì)算公式如下

(9)

式中，

(

)與

(

)分別表示將匿名位置、實(shí)際位置當(dāng)作中心的近鄰查詢結(jié)果集合。

隱私保護(hù)質(zhì)量取決于匿名點(diǎn)與真實(shí)點(diǎn)之間的距離，因此有必要分析不同距離對(duì)服務(wù)質(zhì)量造成的影響。

圖4 近鄰查詢性能實(shí)驗(yàn)結(jié)果圖

由圖4顯示，當(dāng)近鄰數(shù)量一致時(shí)，隨著匿名點(diǎn)與實(shí)際點(diǎn)數(shù)量的增加，查詢準(zhǔn)確率隨之下降。但是下降幅度并不大，且當(dāng)查詢數(shù)量為16時(shí)，準(zhǔn)確率均會(huì)達(dá)到80%以上。這是因?yàn)閷?duì)大眾行為與用戶個(gè)人特征進(jìn)行了準(zhǔn)確分析，提高了近鄰搜索性能，使隱私保護(hù)的服務(wù)質(zhì)量得到增強(qiáng)。

5 結(jié)論

隱私保護(hù)始終是互聯(lián)網(wǎng)領(lǐng)域研究的熱點(diǎn)話題，針對(duì)隱式位置訪問(wèn)信息中存在的隱私保護(hù)問(wèn)題，本文利用K近鄰搜索方式確定敏感位置區(qū)域，再通過(guò)情景感知的方式評(píng)估隱私保護(hù)器是否會(huì)泄露用戶隱私，避免用戶在危險(xiǎn)節(jié)點(diǎn)處進(jìn)行訪問(wèn)。仿真結(jié)果表明，通過(guò)設(shè)置合理的用戶興趣點(diǎn)數(shù)量，可提高隱私保護(hù)服務(wù)質(zhì)量，且該算法通信代價(jià)較低。但該算法依然存在改進(jìn)之處，例如文中所提的隱式位置訪問(wèn)隱私保護(hù)均是針對(duì)離線數(shù)據(jù)的處理，這些數(shù)據(jù)的應(yīng)用具有一定局限性。為實(shí)現(xiàn)實(shí)用性需求，在今后研究中需采用用戶發(fā)布的實(shí)時(shí)數(shù)據(jù)完成進(jìn)一步研究。