不影響隱私的位置服務(wù)查詢處理模型

雷建云，姚 瑤

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

不影響隱私的位置服務(wù)查詢處理模型

雷建云，姚 瑤

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

基于位置服務(wù)的應(yīng)用中，針對(duì)沒有可信任的服務(wù)器人們的隱私信息將受到嚴(yán)重威脅的問題，提出了一個(gè)位置服務(wù)查詢處理模型.該模型是移動(dòng)和固定用戶在不顯示其位置信息的情況下使用基于位置服務(wù)的新框架.實(shí)驗(yàn)結(jié)果顯示：該模型位置匿名器采用的金字塔結(jié)構(gòu)較其它算法有一定的優(yōu)越性，用戶數(shù)可達(dá)到50000個(gè)或更多，且用戶數(shù)越多，位置匿名器的性能越高；隱私感知查詢處理器使用過(guò)濾算法可大幅減少查詢處理時(shí)間.該模型具有一定的理論價(jià)值和實(shí)用價(jià)值.

基于位置的服務(wù)；K-匿名；位置隱私

隨著移動(dòng)通信和傳感器設(shè)備等位置感知技術(shù)的快速發(fā)展，基于位置的服務(wù)(LBS)應(yīng)用越來(lái)越廣泛[1].例如，查詢興趣點(diǎn)(結(jié)合當(dāng)前位置信息查詢最近的醫(yī)院、加油站、賓館以及娛樂場(chǎng)所等)；分享社交網(wǎng)絡(luò)位置(簽到、大富翁游戲等).為了獲取準(zhǔn)確的結(jié)果，用戶需不斷地向服務(wù)器發(fā)送自己的位置信息，這些位置數(shù)據(jù)不僅直接包含用戶的隱私信息，還可以挖掘出用戶的健康狀況、社會(huì)地位等敏感信息.若位置信息被不正當(dāng)使用或被第三方惡意攻擊，會(huì)給用戶的隱私帶來(lái)嚴(yán)重的威脅.

最早Samarati P 和Sweeney L 提出 K-匿名技術(shù)[2]，并用于保護(hù)用戶的隱私.2003年，Gruteser等人[3]將K-匿名技術(shù)的思想引入到位置服務(wù)LBS 中，通過(guò)模糊用戶的空間位置信息以達(dá)到隱私保護(hù)的目的[4].2014年，王璐，孟小峰根據(jù)位置隱私的保護(hù)程度，把現(xiàn)有方法總結(jié)為基于啟發(fā)式隱私度量、概率推測(cè)和隱私信息檢索的位置大數(shù)據(jù)隱私保護(hù)技術(shù)[5].文獻(xiàn)[6]利用服務(wù)查詢結(jié)果的相似性來(lái)輔助匿名區(qū)域，提出具有較高平衡性的K-匿名位置隱私保護(hù)方法.本文提出的保護(hù)隱私模型的位置匿名器具有以下優(yōu)點(diǎn)：(1)模型為每個(gè)用戶提供可定制的隱私簡(jiǎn)檔：包括K值，最小隱藏區(qū)域Amin；(2)很好地衡量大量具有任意隱私簡(jiǎn)檔的移動(dòng)用戶；(3)不能逆向獲取關(guān)于用戶確切位置的任何信息.

1 系統(tǒng)框架

移動(dòng)用戶在注冊(cè)使用系統(tǒng)時(shí)，可通過(guò)用戶隱私簡(jiǎn)檔自定義其隱私要求.用戶隱私簡(jiǎn)檔為二元組(K,Amin)，其中K表示用戶所需的匿名數(shù)，Amin是最小匿名區(qū)域.在用戶密集區(qū)域內(nèi)Amin特別有用，因?yàn)樵诿芗瘏^(qū)域內(nèi)，即使K很大也達(dá)不到用戶的高隱私要求,此時(shí)可通過(guò)設(shè)置Amin滿足用戶需求.圖1描述的是系統(tǒng)構(gòu)架的兩個(gè)主要組件：位置匿名器和隱私感知查詢處理器.

圖1 系統(tǒng)框架圖Fig.1 The system architecture

位置匿名器不斷地獲取用戶更新的位置信息，模糊更新的位置信息并隱藏在滿足用戶隱私簡(jiǎn)檔(K,Amin)的匿名區(qū)域內(nèi)，發(fā)送匿名區(qū)域給基于位置的數(shù)據(jù)庫(kù)服務(wù)器.隱私感知查詢處理器嵌入在基于位置的數(shù)據(jù)庫(kù)服務(wù)器內(nèi)，以匿名方式查詢處理用戶需求并將結(jié)果返回候選列表，用戶根據(jù)自己的實(shí)際情況選擇滿意的結(jié)果.候選列表的大小很大程度上是由用戶設(shè)置的隱私簡(jiǎn)檔(K,Amin)決定的，一個(gè)嚴(yán)格的隱私簡(jiǎn)檔會(huì)得出一個(gè)很長(zhǎng)的候選列表.用戶可以通過(guò)權(quán)衡基于位置的服務(wù)質(zhì)量和其隱私要求設(shè)置隱私簡(jiǎn)檔(K,Amin).

2 位置匿名器

如圖1所示，位置匿名器將每個(gè)移動(dòng)用戶的精確點(diǎn)位置信息p模糊到空間區(qū)域R以滿足每個(gè)用戶隱私簡(jiǎn)檔要求.新模型的位置匿名器將滿足以下4個(gè)目標(biāo).

(1)準(zhǔn)確度.匿名區(qū)域R應(yīng)屬于區(qū)域AR，并包含滿足和接近的KR用戶(即KR≥K，AR≥Amin)；

(2) 質(zhì)量.攻擊者只知道用戶在匿名區(qū)域R內(nèi)，無(wú)法獲知其具體位置；

(3)效率.匿名算法在計(jì)算上有效且可擴(kuò)展.能夠應(yīng)對(duì)大量的持續(xù)運(yùn)動(dòng)的移動(dòng)用戶和時(shí)空查詢的實(shí)時(shí)要求；

(4)靈活性.每個(gè)注冊(cè)用戶均有指定其隱私要求和隨時(shí)改變要求的能力.

2.1 數(shù)據(jù)結(jié)構(gòu)

圖2描述了基本位置匿名器的數(shù)據(jù)結(jié)構(gòu).主要思想是采用基于網(wǎng)格的完整金字塔數(shù)據(jù)結(jié)構(gòu)[7],將層次空間分解為H級(jí)，其中高度h的級(jí)別有4h個(gè)網(wǎng)格單元.每個(gè)金字塔單元表示為(cid，N),其中cid是單元標(biāo)識(shí)符，N是單元格邊界內(nèi)移動(dòng)用戶的數(shù)量.動(dòng)態(tài)的維護(hù)金字塔結(jié)構(gòu)用以追蹤每個(gè)單元內(nèi)當(dāng)前移動(dòng)用戶的數(shù)量.另外，追蹤一個(gè)哈希表.每個(gè)注冊(cè)用戶都有一個(gè)格式為(uid,profile,cid)的條目，其中uid是移動(dòng)用戶標(biāo)識(shí)符，profile是用戶的隱私簡(jiǎn)檔，cid是移動(dòng)用戶所在的單元標(biāo)識(shí)符.cid總是在金字塔的最低級(jí)別，如圖2的陰影層所示.

圖2 基本位置匿名器Fig.2 The basic location anonymizer

2.2 維護(hù)

基于位置的應(yīng)用程序，其高動(dòng)態(tài)環(huán)境必然使它采用的數(shù)據(jù)結(jié)構(gòu)需要持續(xù)頻繁地更新.位置更新以(uid，x，y)的形式發(fā)送給位置匿名器，其中uid是用戶標(biāo)識(shí)符，x和y是用戶新的位置坐標(biāo).一旦位置匿名器接收到更新，散列函數(shù)h(x，y)可以在最底層的網(wǎng)格層獲取用戶新的標(biāo)識(shí)符cidnew.檢查哈希表中的用戶條目以獲得其原始單元標(biāo)識(shí)符cidold.若舊單元格標(biāo)識(shí)符與新單元格標(biāo)識(shí)符相同(cidold=cidnew)，則不需要做任何處理；若有變化(cidold≠cidnew)，則執(zhí)行：

(1)更新哈希表中新的單元格標(biāo)識(shí)符；

(2)更新新、舊金字塔網(wǎng)格單元格中的計(jì)數(shù)器N；

(3)如果需要，把單元格計(jì)數(shù)器N的變化發(fā)送到金字塔頂層.若有新的注冊(cè)用戶，在哈希表中創(chuàng)建一個(gè)新條目，并將金字塔結(jié)構(gòu)中所有受影響的網(wǎng)格單元的計(jì)數(shù)器加1.類似地，若有用戶退出，將其條目從哈希表中刪除，并將所有受影響的網(wǎng)格單元的計(jì)數(shù)器減1.

2.3 匿名算法

算法1描述了一種基于網(wǎng)格的金字塔結(jié)構(gòu)的自下而上的匿名算法.具體算法如下：

輸入：用戶隱私簡(jiǎn)檔(K,Amin)和用戶當(dāng)前處于網(wǎng)格單元的標(biāo)識(shí)符cid

輸出：滿足用戶要求的單元格區(qū)域Area(cid)

算法1 Bottom-up cloaking algorithm

FunctionBOTTOM-UPCLOAKING(K,Amin,cid)

ifcid.N≥Kandcid.Area≥Aminthen

returnArea(cid);//if the initial area is satisfied, then initial area is returned.

end if

cidV← The vertical neighbor cell ofcid.

cidH← The horizontal neighbor cell ofcid.

NV=cid.N+cidV.N,NH=cid.N+cidH.N

if (NV≥KorNH≥K) and 2cid.Area≥Aminthen

if(NV≥KandNH≥KandNH≤NV) orNV

returnArea(cid) ∪Area(cidH);

else

returnArea(cid) ∪Area(cidV);

end if

//return the more satisfiedK

else

BOTTOM-UPCLOAKING(K,Amin,PARENT(cid)); //if the neighbor cells are not satisfied, use the father node ofcidto do the recursion.

end if

3 隱私感知查詢處理器

如圖1所示，隱私感知查詢處理器嵌入在基于位置的數(shù)據(jù)庫(kù)服務(wù)器內(nèi)，其主要目標(biāo)是提供高效、準(zhǔn)確的服務(wù).存儲(chǔ)在基于隱私的位置數(shù)據(jù)庫(kù)服務(wù)器上的數(shù)據(jù)類型主要有：公共數(shù)據(jù)和私有數(shù)據(jù).公共數(shù)據(jù)包括固定物體，如醫(yī)院、餐館和加油站等.私人數(shù)據(jù)主要包含個(gè)人資料，具有非零K或非零Amin的隱私簡(jiǎn)檔的移動(dòng)或固定用戶的信息.這些數(shù)據(jù)被位置匿名器隱藏在匿名區(qū)域內(nèi).基于存儲(chǔ)數(shù)據(jù)，通過(guò)其隱私感知查詢處理器識(shí)別新模型支持的3種查詢類型.

1) 私人查詢公共數(shù)據(jù).例如一個(gè)人(私人查詢)詢問關(guān)于離他最近的加油站(公共資料).隱私感知查詢處理器沒有發(fā)出用戶的確切位置，而加油站的確切位置是已知的.

2) 公共查詢私人數(shù)據(jù).例如管理員(公共查詢)詢問移動(dòng)用戶的數(shù)量(私人數(shù)據(jù)).隱私感知查詢處理器知道查詢的確切信息，但不知道移動(dòng)用戶的確切位置.

3) 私人查詢私人數(shù)據(jù).例如一個(gè)人(私人查詢)詢問離他最近的朋友(私人資料).用戶和他好友的確切位置在隱私感知查詢處理器上均不可用.

最近鄰查詢的主要思想是計(jì)算出要發(fā)送給客戶端的結(jié)果候選列表.然后，客戶在候選列表中本地評(píng)估他的查詢，以獲得查詢結(jié)果.通過(guò)實(shí)驗(yàn)證明該方法是高效、可擴(kuò)展的，通過(guò)計(jì)算證明候選列表是可包容性的，即包含確切答案的最小表.

算法的主要思想是初始化選擇一組可用于整個(gè)目標(biāo)對(duì)象集上搜索的過(guò)濾目標(biāo)對(duì)象.不管匿名區(qū)域A中用戶的確切位置，使用過(guò)濾目標(biāo)，識(shí)別空間搜索可能覆蓋最近鄰查詢潛在答案的區(qū)域AEXT.最后，將AEXT內(nèi)的所有目標(biāo)對(duì)象都作為候選名單返回給用戶.算法2給出了私人對(duì)公共數(shù)據(jù)進(jìn)行最近鄰查詢的具體算法.

輸入：偽匿名區(qū)域A

輸出：結(jié)果候選列表

算法2 PrivateNNQueries over Public Data

FunctionPRIVATENNPUBLICDATA(CloakedAreaA)

AEXTis an extened area and initially set toA

for each vertexviin regionAdo

ti← is the nearest target object tovi

end for

for each edgeeij=vivjof regionAdo

ifti=tjthen

mij← NULL

else

Lijis a line connectingtiandtj

Pijis a line that divides and is orthogonal toLij

mijis a intersection point ofPijandeij

end if

dm←Distance(ti,mij) =Distance(tj,mij)

di←Distance(vi,ti)

dj←Distance(vj,tj)

maxd←MAX(dm,di,dj)

ExpandAEXTby distancemaxdinvivjdirection

end for

candidate_list← All target objects insideAEXT

return candidate_list

4 實(shí)驗(yàn)結(jié)果

通過(guò)實(shí)驗(yàn)評(píng)估新模型的兩個(gè)主要組件(位置匿名器和隱私感知查詢處理器)的性能來(lái)評(píng)價(jià)其框架性能.

4.1 位置匿名器

對(duì)基本位置匿名器和自適應(yīng)匿名器在匿名時(shí)間、維護(hù)成本、準(zhǔn)確性和可擴(kuò)展性方面進(jìn)行比較.實(shí)驗(yàn)使用50000個(gè)注冊(cè)用戶的9級(jí)金字塔結(jié)構(gòu).每個(gè)用戶生成一個(gè)隨機(jī)隱私簡(jiǎn)檔，其中K和Amin分別在[1-50]個(gè)用戶和[0.005%，0.01%]的范圍內(nèi)均勻分配.

圖3給出了金字塔高度對(duì)基本和自適應(yīng)位置匿名器性能的影響.圖3(a)給出了金字塔高度對(duì)每個(gè)用戶請(qǐng)求平均隱藏時(shí)間的影響(算法1).圖3(b)給出了每個(gè)位置更新所需的平均更新次數(shù)對(duì)金字塔高度的影響.圖3(c)和3(d)分別給出了關(guān)于K和Amin的金字塔高度對(duì)匿名區(qū)域精度的影響.基本和自適應(yīng)方法都產(chǎn)生與算法1相同的匿名區(qū)域精度.圖3(c)中，測(cè)量精度為K′/K，其中K′是包括在匿名區(qū)域內(nèi)用戶的數(shù)量，而K是用戶的確切需求.較低的金字塔水平給予要求寬松的用戶非常不準(zhǔn)確的答案.然而，即使對(duì)于要求寬松的用戶，更高的金字塔級(jí)別可以給出非常接近于最佳情況的準(zhǔn)確匿名區(qū)域.類似地如圖3(d)中所示，測(cè)量精度為A′/Amin，其中A′是計(jì)算的匿名空間區(qū)域，Amin是所需的空間區(qū)域.此外，對(duì)具有各種Amin要求的幾組用戶進(jìn)行實(shí)驗(yàn)，同時(shí)將K設(shè)置為1.

圖3 金字塔高度Fig.3 The height of the pyramid structure

圖4給出了將注冊(cè)用戶數(shù)量從1000改為50000時(shí)基本和自適應(yīng)位置匿名器的可擴(kuò)展性.對(duì)于隱藏時(shí)間(圖4(a))，隨著用戶數(shù)量的增加，基本位置匿名器的性能大大提高.主要思想是，通過(guò)增加用戶數(shù)量，移動(dòng)用戶的隱私要求將很可能在較低的金字塔級(jí)別中得到滿足，即對(duì)算法1的遞歸調(diào)用較少.自適應(yīng)位置匿名器的情況不同，大量的用戶增加了維護(hù)網(wǎng)格單元的數(shù)量，以適應(yīng)具有各種需求的用戶.然而，適應(yīng)性方法的隱藏時(shí)間總是小于基本方法的時(shí)間.對(duì)于更新成本(圖4(b))，隨著用戶數(shù)量的增加，由于維護(hù)單元數(shù)量較少，自適應(yīng)方法的性能總是優(yōu)于基本方法.

4.2 隱私感知查詢處理器

以下研究隱私感知查詢處理器對(duì)返回候選列表的大小和查詢處理時(shí)間的效率和可擴(kuò)展性.

圖5給出了將公共目標(biāo)數(shù)量從1000增加到10000時(shí)，隱私感知查詢處理器的可擴(kuò)展性.對(duì)于1000目標(biāo)時(shí)，使用更多的過(guò)濾器候選列表會(huì)大大減少(圖5(a))；對(duì)于10000目標(biāo)時(shí)，使用4個(gè)過(guò)濾器導(dǎo)致候選列表大約只有一個(gè)過(guò)濾器返回列表的一半.關(guān)于查詢處理時(shí)間(圖5(b)),4個(gè)過(guò)濾器的計(jì)算開銷是通過(guò)在搜索空間中的巨大修剪來(lái)獲得候選名單，所以使用4個(gè)濾波器總能實(shí)現(xiàn)更好的性能.

圖4 用戶數(shù)量Fig.4 Number of users

圖5 公共目標(biāo)數(shù)量Fig.5 Number of public target objects

5 結(jié)語(yǔ)

本文提出了一個(gè)新框架,移動(dòng)用戶無(wú)需泄漏其私人位置即可獲取基于位置的服務(wù)，由位置匿名器和隱私感知查詢處理器兩部分組成.該位置匿名器充當(dāng)可信任的第三方，將每個(gè)用戶的確切位置信息模糊隱藏在與用戶隱私配置文件匹配的空間區(qū)域內(nèi).位置匿名器具有高準(zhǔn)確性、高質(zhì)量、高效率和高靈活性等特性.隱私感知查詢處理器是嵌入到傳統(tǒng)的基于位置的數(shù)據(jù)庫(kù)服務(wù)器中，使其成為隱私感知具有隱藏的空間區(qū)域而不是精確的點(diǎn)位置信息.此模型支持3種查詢類型：私人查詢公共數(shù)據(jù)、公共查詢私有數(shù)據(jù)和私人查詢私有數(shù)據(jù).模型為處理這些查詢提供一個(gè)框架，其返回候選列表，而不是確切的答案.通過(guò)實(shí)驗(yàn)證明候選列表包含最小范圍確切的答案.通過(guò)實(shí)驗(yàn)評(píng)估研究了其組件，并顯示在大量的移動(dòng)用戶和各種隱私要求下的效率、準(zhǔn)確性和可擴(kuò)展性.

[1] 雷建云，張鐳鐘.基于LBS的連續(xù)查詢位置隱私保護(hù)模型的動(dòng)態(tài)規(guī)劃算法[J].中南民族大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，34(3)：83-87.

[2] Samarati P. Protecting respondents identities in micro data release[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(6): 1010-1027.

[3] Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//ACM. International Conference on Mobile Systems Applications and Services. San Francisco: ACM, 2003: 163-168.

[4] 韓建民，林 瑜，于 娟，等. 基于位置K-匿名的LBS隱私保護(hù)方法的研究[J].小型微型計(jì)算機(jī)系統(tǒng),2014, 35(9):2088-2093.

[5] 王 璐，孟小峰.位置大數(shù)據(jù)隱私保護(hù)研究綜述[J].軟件學(xué)報(bào)，2014，25(4)：693-712.

[6] 葉阿勇，李亞成，馬建峰，等.基于服務(wù)相似性的K-匿名位置隱私保護(hù)方法[J].通信學(xué)報(bào),2014,35(11):162-169.

[7] Brinkhoff T. Framework for generating network-based moving objects[J]. GeoInformatica, 2002, 6(2):153-180.

QueryProcessingModelforLocationServiceswithoutPrivacyCompromising

LeiJianyun，YaoYao

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

In location based service applications, people′s privacy may be compromised without trusted servers. To address this problem, a new model with a framework in which mobile and stationary users can use location-based services without revealing their location information is presented. The experimental results indicate that the model using pyramid structure can contain an amount of users more than 50000, and more users brings better performance, privacy query processor uses filter algorithms to drastically reduce query processing time. The new model has certain theoretical value and practical value.

location-based service; K-anonymity; location privacy

2017-07-26

雷建云(1972-)，男，教授，研究方向：信息安全，E-mail：leijianyun@mail.scuec.edu.cn

湖北省自然科學(xué)基金資助項(xiàng)目(2014CFB445)

TP393

A

1672-4321(2017)04-0121-05