雷建云，姚 瑤

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

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

雷建云，姚 瑤

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

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

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

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

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

1 系統(tǒng)框架

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

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

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

2 位置匿名器

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

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

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

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

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

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

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

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

2.2 維護

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

(1)更新哈希表中新的單元格標識符；

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

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

2.3 匿名算法

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

輸入：用戶隱私簡檔(K,Amin)和用戶當前處于網(wǎng)格單元的標識符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ù)庫服務(wù)器內(nèi)，其主要目標是提供高效、準確的服務(wù).存儲在基于隱私的位置數(shù)據(jù)庫服務(wù)器上的數(shù)據(jù)類型主要有：公共數(shù)據(jù)和私有數(shù)據(jù).公共數(shù)據(jù)包括固定物體，如醫(yī)院、餐館和加油站等.私人數(shù)據(jù)主要包含個人資料，具有非零K或非零Amin的隱私簡檔的移動或固定用戶的信息.這些數(shù)據(jù)被位置匿名器隱藏在匿名區(qū)域內(nèi).基于存儲數(shù)據(jù)，通過其隱私感知查詢處理器識別新模型支持的3種查詢類型.

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

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

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

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

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

輸入：偽匿名區(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 實驗結(jié)果

通過實驗評估新模型的兩個主要組件(位置匿名器和隱私感知查詢處理器)的性能來評價其框架性能.

4.1 位置匿名器

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

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

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

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

4.2 隱私感知查詢處理器

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

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

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

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

5 結(jié)語

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

[1] 雷建云，張鐳鐘.基于LBS的連續(xù)查詢位置隱私保護模型的動態(tài)規(guī)劃算法[J].中南民族大學(xué)學(xué)報(自然科學(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隱私保護方法的研究[J].小型微型計算機系統(tǒng),2014, 35(9):2088-2093.

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

[6] 葉阿勇，李亞成，馬建峰，等.基于服務(wù)相似性的K-匿名位置隱私保護方法[J].通信學(xué)報,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é)基金資助項目(2014CFB445)

TP393

A

1672-4321(2017)04-0121-05