基于SpaceTwist改進的位置隱私保護方法

楊曉暉，朱燁，胡倩茹

(河北大學 計算機科學與技術學院，河北 保定 071002)

?

基于SpaceTwist改進的位置隱私保護方法

楊曉暉，朱燁，胡倩茹

(河北大學 計算機科學與技術學院，河北 保定 071002)

移動互聯(lián)網(wǎng)中基于位置服務的查詢質(zhì)量與位置隱私保護二者的權衡問題是目前研究熱點之一.提出一種基于SpaceTwist方案的k匿名增量查詢位置隱私保護方法，采用客戶-服務器架構(gòu)，對用戶真實位置形成k匿名區(qū)并以供應匿名區(qū)形心作為錨點，經(jīng)匿名變換后將真實位置排除于匿名區(qū)域外，并以增量形式改變查詢范圍來返回查詢結(jié)果集.避免使用第三方服務器使其成為攻擊點，在提高查詢準確度的同時保證了用戶位置隱私的效果.

位置隱私保護；基于位置的服務；k匿名；錨點；匿名變換

移動互聯(lián)網(wǎng)的飛速發(fā)展改變了人們傳統(tǒng)的生活方式，其便攜性以及實時性使網(wǎng)絡的服務模式有了新的起點，而帶來的安全和隱私問題卻甚于傳統(tǒng)互聯(lián)網(wǎng)，包括用戶的身份信息、興趣信息、位置信息等.基于位置的服務[1](LBS，location-based service)融合了定位技術、移動通信技術、互聯(lián)網(wǎng)技術以及地理信息系統(tǒng)(GIS)技術，是移動互聯(lián)網(wǎng)中應用性最強的服務.用戶作為需求方，將自己的位置信息發(fā)送給LBS提供商(LSP，location-based service provider)來獲得相關查詢信息，如查詢“離我最近的餐廳、5 km范圍內(nèi)的加油站”等興趣點(POI，point of interest).

隨著位置服務的廣泛應用，位置隱私的安全問題已經(jīng)越來越受到用戶的重視，形勢日益嚴峻，國內(nèi)外學者對位置隱私保護問題的研究也日益增多.在用戶使用LBS的過程中，LBS必須要首先獲得準確的用戶位置信息才能夠提供相應的滿足用戶需求的服務，這其中并不是只包含單純的地理坐標信息，因為攻擊者通過對位置的觀察分析，同時能夠獲知用戶的身份信息甚至家庭住址、興趣愛好、健康狀況等一系列個人隱私信息，在充分享受位置服務提供的便利的同時，保證用戶的隱私安全是當下亟待解決的問題.

1 經(jīng)典位置隱私保護方法

現(xiàn)存的位置隱私保護方法中，提出最早的，也是最廣泛采用的是位置k匿名模型[2]，k匿名模型是基于泛化法[3]的位置隱私保護技術，主要思想是在發(fā)布用戶的位置信息時，用一個覆蓋其他k-1個用戶的匿名區(qū)域代替用戶的真實位置，使得LBS提供者無法從這k個用戶中辨別出真實用戶的位置.但大多數(shù)k匿名模型的研究都依賴于第三方服務器，為了不使自己的精確位置泄露，用戶與LSP之間的交流需要第三方服務器來維系，用戶將位置信息發(fā)送給第三方服務器，再由第三方服務器將匿名區(qū)域的k個用戶的查詢需求發(fā)送給位置服務提供商，得到結(jié)果集后，第三方服務器再對數(shù)據(jù)進行分析，把最終篩選出來的結(jié)果返回給相應的用戶.經(jīng)典的k匿名有四分法[4]，該方法通過將用戶所在區(qū)域逐一四分化來形成匿名區(qū)域以達到k匿名效果.k匿名模型采用的第三方服務器結(jié)構(gòu)在實際生活中可靠性不高，完全可靠的第三方服務器幾乎是不存在的，使第三方擔任用戶與LSP之間的通信中介會導致依賴性過強，成為攻擊熱點等問題，其掌握用戶的位置信息、身份信息和查詢信息等被惡意攻擊，后果不堪設想[5].同時第三方服務器效率也將成為LBS的瓶頸.

常見的位置隱私保護方法[6]還包括假位置，掩蓋技術，加密技術等，其中假位置的方法利用1個或多個錨點進行位置隱私保護，不同的需求采用不同的假名來模糊真實位置，并且假名需要不斷更新，同時保持新、舊假名的連接，使攻擊者即便截獲數(shù)據(jù)而得到用戶信息也無法精確得出用戶是誰的結(jié)論，達到保護用戶隱私的目的，但這類方法存在結(jié)果不精確或開銷過大等問題.

Yiu等[7]提出了SpaceTwist方案，主要思想是用戶隨機選取自己真實位置附近的一個點作為錨點q'，使用該錨點代替用戶的真實位置向LBS服務器發(fā)送請求，如圖1所示，查詢開始時，初始化需求空間和供應空間，需求空間是整個空間，供應空間為空，查詢過程中需求空間以用戶真實位置為圓心，供應空間以錨點為圓心.用戶向LBS服務器發(fā)送請求搜索附近POI，需求空間不斷縮小，同時供應空間不斷擴張，直到供應空間完全覆蓋需求空間才停止檢索，此時查詢結(jié)束，請求結(jié)果返回給用戶.

圖1 SpaceTwist方案Fig.1 SpaceTwist scheme

SpaceTwist方案雖然擺脫了第三方服務器，但無法達到k匿名，它忽視了一種情況：如果用戶所在地點除錨點外恰巧只有一個用戶，則攻擊者知道用戶真實位置的概率為50%，無法很好地滿足用戶位置隱私保護需求；且SpaceTwist方案選取錨點的方法隨機性太強，如果在更恰當?shù)暮侠矸秶鷥?nèi)選取合適的錨點，能夠提高查詢的精確度.針對SpaceTwist方案無法實現(xiàn)k匿名的缺陷，孟小峰等[8]提出Coprivacy來彌補不足.而Coprivacy是采用用戶之間相互協(xié)作的無中間服務器結(jié)構(gòu)的方法，雖然避免了中心服務器造成的黑客集中攻擊點以及性能瓶頸問題，但其假定了參與協(xié)作的移動用戶都是可信的，未考慮不可信用戶的情況，如遇惡意用戶，隱私泄露問題也難以解決.

肖燕芳等[9]提出了基于匿名區(qū)域變換的方法，匿名區(qū)域變換與傳統(tǒng)匿名區(qū)域生成方式不同，其特點是采用變換的方法使用戶的真實位置不包含在匿名區(qū)域中，該方案形成的匿名區(qū)域排除了用戶真實位置，降低了位置隱私泄露的概率，但錨點生成階段仍然存在隨機性較大導致查詢結(jié)果不精確的問題.

因此為了進一步提高查詢結(jié)果的精確度和位置隱私保護程度，基于SpaceTwist方案提出采用客戶-服務器系統(tǒng)架構(gòu)并結(jié)合k匿名以及匿名變換方法來實現(xiàn)LBS查詢方面的位置隱私保護，在移動客戶端中進行匿名區(qū)域生成、錨點選取以及查詢處理等工作.

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

本文方法采用客戶-服務器架構(gòu)，直接在移動客戶端進行匿名區(qū)域的生成以及用戶需求查詢處理的工作，系統(tǒng)架構(gòu)如圖2所示.

圖2 系統(tǒng)架構(gòu)Fig.2 System architecture

整個系統(tǒng)架構(gòu)包括移動客戶端和位置服務提供商，二者由通信網(wǎng)絡連接.移動客戶端包含位置匿名模塊和查詢處理模塊，位置匿名模塊的工作是生成查詢過程中的供應匿名區(qū)和需求匿名區(qū)以及選取錨點，其中匿名轉(zhuǎn)換器是利用匿名區(qū)域變換法生成供應匿名區(qū)，并把移動用戶的k近鄰查詢轉(zhuǎn)變?yōu)楣涿麉^(qū)內(nèi)所有節(jié)點的范圍查詢；查詢處理模塊的工作是在SpaceTwist方案的基礎上搜索符合條件的POI，經(jīng)過分析計算后選出最終結(jié)果.

3 匿名區(qū)域增量查詢位置隱私保護方法

3.1 基于k匿名的錨點選取過程

結(jié)合k匿名的思想，將用戶真實位置q所在區(qū)域通過四分法選取單元格后形成需求匿名區(qū)，需求匿名區(qū)即匿名變換之前形成的包含用戶真實位置信息的匿名區(qū).將該單元格形心作為錨點，如圖3所示，圖中實心圓為除用戶真實位置以及錨點以外的其他用戶.具體步驟如下：

1)用戶端定位出用戶真實位置q的地理位置坐標；

2)用戶端根據(jù)經(jīng)緯度，確定用戶所在城市，記為G；

3)用戶向LBS服務器發(fā)出請求，LBS返回該區(qū)域的分割結(jié)果；

4)LBS服務器采用四分法對整個G區(qū)域分割成正方形塊區(qū)域，逐一遞推縮減正方形塊的大小，其中每個正方形的邊長根據(jù)需求擬定參數(shù)λ，使數(shù)值不大于λ.每個正方形塊作為一個單元格.每個單元格對應一個節(jié)點.每個節(jié)點中存儲相應的單元格信息(包括用戶ID，中心點O，單元格內(nèi)的用戶數(shù)量x)，單元格信息實時更新.

5)對于給定的匿名度k，每劃分一次單元格后都要比較x與k的大小關系，當x>k時，則繼續(xù)分割單元格，重復此過程；當x

6)用戶端將真實位置所在單元格的形心作為錨點q'.

該過程基于SpaceTwist方案選取錨點的思想提出了在實現(xiàn)k匿名后的需求匿名區(qū)的形心作為錨點，而不是隨機選取，可以提高用戶查詢結(jié)果的準確性，同時結(jié)合k匿名的思想，保證了用戶附近有其他k-1個用戶，這將對攻擊者產(chǎn)生混淆，保證了用戶的位置隱私.

3.2 基于匿名變換的匿名區(qū)域生成過程

將用戶所在位置設置為原點，運用上文中提到的匿名區(qū)域變換法生成供應匿名區(qū).如圖4所示，q為用戶真實位置，q'為錨點，圖4中實心圓為POI點.步驟如下：

1)以用戶真實位置q為圓心，建立x-y直角坐標系

2)連接qq'，做過q'的直線垂直于qq'，與y軸相交于點N，以q'為中點的線段NF作為正方形的邊長，此正方形即為供應匿名區(qū)，在坐標系的第一象限形成.

該過程利用匿名變換形成的匿名區(qū)域排除了用戶真實位置，相比較傳統(tǒng)k匿名模型來說大大降低了位置隱私泄露的概率.

圖3 錨點選取Fig.3 Anchor selection

圖4 匿名區(qū)域變換Fig.4 Anonymous area transformations

3.3 基于SpaceTwist的增量查詢過程

圖5 增量查詢Fig.5 Incremental query

為了使用戶享受LBS所帶來的便利的同時，又不必擔心隱私信息泄露給LSP，就要權衡服務質(zhì)量與隱私保護程度這2個問題.用戶發(fā)出LBS請求的過程從根本上說就是一個用戶和服務端共享位置信息并獲取查詢結(jié)果的過程.根據(jù)位置服務中查詢結(jié)果的不同可分為2種查詢模型[10]，即范圍查詢和K近鄰(KNN)查詢.典型的范圍查詢語言為“距我R范圍內(nèi)所有的電影院”，是以查詢距離R作為標準以獲得結(jié)果.典型的K近鄰查詢語言為“距我最近的K個電影院”，是以POI數(shù)量K作為標準獲得結(jié)果.基于SpaceTwist的增量查詢過程是用戶端以供應匿名區(qū)作為用戶的位置向服務提供商發(fā)送查詢請求.

如圖5所示，POI點記為p1,p2,p3,…,pn，具體增量查詢請求過程如下：

1)初始化供應空間和需求空間.供應空間是以錨點q'為圓心的圓形區(qū)域，需求空間是以真實位置q為圓心的圓形區(qū)域.查詢開始，供應空間為空，需求空間為整個空間.

2)匿名區(qū)域中的n個節(jié)點以增量形式發(fā)起n次近鄰查詢請求，LSP不斷返回近鄰查詢結(jié)果集，直到供應空間完全覆蓋需求空間；

3)用戶端檢索返回的查詢結(jié)果，將LSP返回的結(jié)果集進行篩選，根據(jù)用戶隱私需求定義一個參數(shù)m，當dist(q,p)>m時，剔除掉該點，將恰當?shù)腜OI作為最終結(jié)果.

需要說明的是，當用戶發(fā)出KNN查詢請求，返回的POI數(shù)量小于K時，則擴大正方形匿名區(qū)域邊長，繼續(xù)發(fā)送匿名區(qū)域內(nèi)n個節(jié)點的查詢請求，直到滿足K為止.

4 仿真實驗

仿真實驗主要關注LBS服務查詢過程中用戶位置安全性、查詢精準率、響應時間等指標的變化情況，在模擬數(shù)據(jù)集上進行，通過與經(jīng)典位置隱私保護方法進行對比來體現(xiàn)本方法的性能.

算法采用Java語言實現(xiàn)，在window 7系統(tǒng)上運行，硬件環(huán)境為3.2 GHz Intel Core i5處理器、4 GB內(nèi)存.模擬數(shù)據(jù)集來自Thomas Brinkhoff[11]路網(wǎng)數(shù)據(jù)生成器，并以城市Oldenburg的交通路網(wǎng)作為輸入生成移動對象數(shù)據(jù).實驗數(shù)據(jù)參數(shù)如表1所示.

表1 實驗參數(shù)Tab.1 Experimental parameters

隨機選擇1 000個用戶作為查詢用戶的位置，匿名需求參數(shù)k∈[5,25],區(qū)域內(nèi)隨機生成.本文相對SpaceTwist方案錨點的選取過程取消了隨機方式，為了檢驗其精準性，實驗使用Oldenburg生成的移動對象數(shù)據(jù)，對比了二者的查詢近鄰結(jié)果數(shù)量，即匿名區(qū)域中用戶向LSP請求得到的近鄰結(jié)果總數(shù)，如圖6所示.可見相對SpaceTwist方案來說，實驗效果有顯著改善，查詢結(jié)果數(shù)量較少，精準率高于SpaceTwist方案.

相對傳統(tǒng)匿名方法，采用了客戶-服務器結(jié)構(gòu)，不使用第三方服務器，并加入了匿名轉(zhuǎn)換器，即把真實位置放置于匿名區(qū)域外.文獻[12]中提出的PrivacyGrid方案是一種典型的采用中心服務器結(jié)構(gòu)的位置隱私保護方法，通過匿名成功率來檢驗其性能，匿名成功率指匿名區(qū)域內(nèi)的用戶(即匿名區(qū)內(nèi)用戶個數(shù)滿足匿名度k)占系統(tǒng)中全部用戶的比例.而不同用戶對k的隱私需求不同，涉及到個性偏好問題[13]，暫時不做深入研究.如圖7所示，隨著匿名度k的增加，本文方法的匿名成功率相對PrivacyGrid來說略低，這是因為經(jīng)匿名變換后供應匿名區(qū)和需求匿名區(qū)的范圍稍有出入，但影響并不大，此匿名方法的隱私保護程度更高.

圖6 本文方法與SpaceTwist方案查詢精準性對比Fig.6 Query accuracy of this method compared with SpaceTwist

圖7 本文方法與PrivacyGrid方案匿名成功率對比Fig.7 Anonymous success rate of this method compared with PrivacyGrid

響應時間是指用戶端發(fā)送近鄰查詢請求至LSP，LSP返回查詢結(jié)果并滿足用戶需求整個過程的所需的時間[14]，其與SpaceTwist方案對比結(jié)果如圖8所示，可以看出錨點與用戶位置距離越大，響應時間越長，這是因為隨著二者距離的增加，圓形供應區(qū)域半徑隨之增加，查詢區(qū)域會因此變大，LSP返回的結(jié)果集也會越來越大，從而導致響應時間變長.本文方法較SpaceTwist方案增加了四分法選取錨點過程和匿名變換過程，因此當錨點距離用戶真實位置較近時響應時間較SpaceTwist方案略長，隨著距離的增大，響應時間較SpaceTwist方案都變小，同時增大幅度較小.響應時間較SpaceTwist方案有所改善，但并未達到預期效果.

圖8 本文方法與SpaceTwist方案響應時間對比Fig.8 Response time of this method compared with SpaceTwist

5 結(jié)束語

結(jié)合客戶-服務器架構(gòu)和SpaceTwist方案的增量近鄰查詢處理方法的優(yōu)點，本文工作主要包括以下幾個方面：

1)提出了一種采用客戶-服務器架構(gòu)的位置隱私保護方法，不使用第三方服務器，避免出現(xiàn)第三方服務器成為攻擊中心的問題.

2)基于SpaceTwist方案來選取一個錨點代替用戶真實位置向LSP發(fā)送請求，同時采用四分法生成需求匿名區(qū)，將需求匿名區(qū)中心作為錨點，相對提高了查詢結(jié)果的精準率.

3)采用匿名變換法生成供應匿名區(qū)，將用戶真實位置放在匿名區(qū)外，相對加大了位置隱私保護的強度.

最后在模擬數(shù)據(jù)集上進行了實驗，證明了其優(yōu)點，但由于工作量較大，導致響應時間未達到預期效果，未來工作可以在減少響應時間方面進一步開展.

[1] MOKBEL M F.Privacy in location based services:start of the art and research directions[J].2013 IEEE 14th International Conference on Mobile Data Management,Mannheim,2007.DOI:10.1109/MDM.2007.45.

[2] GRUTESER M,GRUNWALD D.Anonymous usage of location-based services through spatial and temporal cloaking[Z].The 1st International Conference on Mobile Systems,Applications and Service,San Frncisco, CO,USA,2003.DOI:10.1145/1066116.1189037.

[3] 王宇航,張宏莉,余翔湛.移動互聯(lián)網(wǎng)中的位置隱私保護研究[J].通信學報,2015,36(9):230-243.DOI:10.1195/j.issn.1000-436x.2015167. WANG Y H,ZHANG H L,YU X Z.Research on location privacy in mobile internet[J].Journal on Communications,2015,36(9):230-243.DOI:10.11959/j.issn.1000-436x.2015167.

[4] MOKBEL M F,CHOW C Y,AREF W G.The new casper query processing for location services without compromising privacy[Z].The 32nd International Conference on Very Large Data Bases,Seoul,South Korea,2006.

[5] WERNKE M,SKVORTSOV P,DURR F K,et al.A classification of location privacy attacks and approaches[J].Personal and Ubiquitous Computing,2014,18(1):163-175.DOI:10.1007/s00779-012-0633-z.

[6] 李暉,李鳳華,曹進,等.移動互聯(lián)服務與隱私保護的研究進展[J].通信學報,2014,35(11):1-11.DOI:10.3969/j.issn.1000-436x.2014.11.001. LI H,LI F H,CAO J,et al.Survey on security and privacy preserving for mobile internet service[J].Journal on Communications,2014,35(11):1-11.DOI:10.3969/j.issn.1000-436x.2014.11.001.

[7] YIU M L,JENSEN C S,HUANG X,et al.SpaceTwist:managing the trade-offs among location privacy,query performance,and query accuracy in mobile services[C].Data Engineering,ICDE 2008,IEEE 24th Intenational Conference,Cancun,Mexico,2008:366-375.DOI:10.1109/ICDE.2008.4497445.

[8] 黃毅,霍崢,孟小峰.CoPrivacy:一種用戶協(xié)作無匿名區(qū)域的位置隱私保護方法[J].計算機學報,2011,34(10):1976-1985.DOI:10.3724/SP.J.1016.2011.01976. HUANG Y,HUO Z,MENG X F.CoPrivacy:a collaborative location privacy preserving method without cloaking region[J].Chinese Journal of Computers,2011,34(10):1976-1985.DOI:10.3724/SP.J.1016.2011.01976.

[9] 肖燕芳.基于匿名區(qū)域變換的位置隱私保護模型與算法研究[D].廣州:華南理工大學,2012. XIAO Y F.Research on location privacy protection model and algorithm based on anonymous area scaling[D].Guangzhou:South China University of Technology,2012.

[10] 賈金營,張鳳荔.位置隱私保護技術綜述[J].計算機應用研究,2013,30(3):641-646.DOI:10.3969/j.issn.1001-3695.2013.03.001. JIA J Y,ZHANG F L.Overview of location privacy protection technology[J].Application Research of Computers,2013,30(3):641-646.DOI:10.3969/j.issn.1001-3695.2013.03.001.

[11] Brinkhoff T.A framework for fenerating network based moving objects[J].GeoInformatica,2002,6(2)153-180.DOI:10.1023/A:1015231126594.

[12] BAMBA B,LIU L,PESTI P,et al.Supporting anonymous location queries in mobile environments with privacygrid[Z].The 17th International Conference on World Wide Web,Beijing,2008.DOI:10.1145/1367497.1367531.

[13] 倪巍偉,陳蕭.保護位置隱私近鄰查詢中隱私偏好問題研究[J].軟件學報,2016,27(7):1805-1821.DOI:10.13328/j.cnki.jos.005053. NI W W,CHEN X.User privacy preference support in location privacy-preserving Nearest Neighb-orQuery[J].Journal of Software,2016,27(7):1805-1821.DOI:10.13328/j.cnki.jos.005053.

[14] 周長利,馬春光,楊松濤.基于敏感位置多樣性的LBS位置隱私保護方法研究[J].通信學報,2015,36(4):125-136.DOI:10.11959/j.issn.1000.436x.2015160. ZHOU C L,MA C G,YANG S T.Research of LBS privacy preserving based on sensitive location diversity[J].Journal on Conmmunications,2015,36(4):125-136.DOI:10.11959/j.issn.1000.436x.2015160.

(責任編輯：孟素蘭)

Improved location privacy protection method based on SpaceTwist

YANG Xiaohui，ZHU Ye，HU Qianru
(College of Computer Science and Technology,Hebei University,Baoding 071002,China)

The trade-off between location-based query quality and location privacy protection in mobile internet is one of the current research hotspots.This paper proposes an anonymous incremental query location privacy protection method based on the SpaceTwist scheme.The client-server architecture is used in this paper.Thekanonymous area is formed and the centroid of the anonymous area is used as the anchor point.After anonymous transformation,the real location is excluded in the anonymous area.It changes the query range in the form of incremental and returns the query result set.It avoids using a third-party server or it will become a point of attack,and it improves the accuracy of the query while ensuring the user's location privacy effect.

location privacy protection;location-based service;kanonymous;anchor;anonymous transformation

2017-02-27

國家科技支撐計劃項目(2013BAK07B04)；河北省自然科學基金資助項目(F2014201152)

楊曉暉(1975—)，男，河北邢臺人，河北大學教授，博士，主要從事分布計算與信息安全等方向研究. E-mail:yxh@hbu.edu.cn

胡倩茹(1979—)，女，河北靈壽人，河北大學講師，主要從事大數(shù)據(jù)和數(shù)據(jù)挖掘方向研究.E-mail:huqr@hbu.edu.cn

10.3969/j.issn.1000-1565.2017.03.011

TP391

A

1000-1565(2017)03-0287-07