呂志陽 趙炯 Ahmed M.A.Alsayadi

清華信息科學與技術國家實驗室(籌) 北京 100086

0 引言

本文提出的方法甚至可以在連續(xù)的精確查詢情況下對時間相關性很強的LBS的用戶提供實時位置隱私。該方法在匿名策略基礎上，通過對用戶的行進方向上的位置點的信息的提前查詢并緩存，來使得追蹤者失去對用戶即時位置的了解，讓用戶總是處于一個不確定區(qū)域內(nèi)，這樣即使用戶在某一標示點上已經(jīng)被識別出來，也能夠保護用戶隱私不繼續(xù)被泄露，防止用戶繼續(xù)被追蹤。同時通過對預先查詢的時機把握，來使得用戶的行進速度也得到保護，防止追蹤者從這個信息上對用戶進行追蹤。用戶的不確定區(qū)域也可擴大在交叉路口時的產(chǎn)生共同區(qū)域的機會。共同區(qū)域(Mix Zones)，是指當采用了匿名策略后，當兩個用戶相遇后，對于追蹤者來說他們就會變得不可識別，這時相遇點就稱為共同區(qū)域，當這兩個用戶分開后，追蹤者就不能區(qū)分哪一個方向的用戶是自己先前追蹤的。達到隱私保護的目的。

1 熵模型

LBS由于擁有用戶所有的查詢記錄,可能會濫用這些記錄，因而需要針對惡意的LBS建立隱私保護策略。在本文中，惡意LBS被看作追蹤者，試圖從用戶匿名的一系列查詢請求中追蹤到用戶的所在。

我們因此提出了一種熵模型來衡量追蹤者的追蹤結(jié)果，也是對隱私保護算法的一個評價模型。熵值表示追蹤者了解到的用戶位置的不確定性。對追蹤結(jié)果的熵值作了分析，分析出了兩種熵值：

(1) 對被追蹤對象與其他對象的混淆導致的熵值，此處稱為個體熵。

(2) 追蹤者所能確定被追蹤對象實際所處匿名區(qū)域的大小，稱為位置熵。

個體熵指的是追蹤過程中由于被追蹤用戶與其它用戶不可區(qū)分而生成的匿名集導致的熵值。Mix Zones策略增加的就是這種熵值。

位置熵指的是被追蹤的每個用戶實時位置的不確定程度。位置匿名策略通過產(chǎn)生這種熵值來保護用戶位置隱私。

圖 1中每個陰影區(qū)域指的是每個單獨被追蹤用戶的不確定區(qū)域，面積越大，說明該用戶當前位置熵越大。圓點則是代表實際用戶所在，紅點是原始追蹤目標。三塊陰影區(qū)域表示當前追蹤者已經(jīng)不能從這三個匿名區(qū)域分辨出用戶所在。需要注意的是 B區(qū)域雖然包含兩個用戶，但是它們此時處于同一個匿名區(qū)域，所以匿名集中用戶數(shù)量為3，而不是4。

圖1 熵模型

這兩種熵值可以綜合在一起得到一個總的熵值：

S指的是每個匿名區(qū)域的用戶可能所處位置的數(shù)量，我們給單個用戶規(guī)定了一個區(qū)域面積閾值MIN_AREA，當一個用戶的不確定區(qū)域面積小于MIN_AREA，那么我們認為該用戶已經(jīng)被精確定位了，而 S指的是匿名區(qū)域中 MIN_AREA的個數(shù)，由匿名區(qū)域面積除以MIN_AREA得到。

P指的是當前匿名區(qū)域內(nèi)包含追蹤對象的概率。

H則是最終的熵值，表明了追蹤者的追蹤結(jié)果的好壞。

在追蹤模型中，每個匿名區(qū)域都有個概率值來表示其中包含最初追蹤的用戶的概率。最初被追蹤用戶的匿名區(qū)域概率值為1，然后在交叉路口遇到另外一個用戶的話，形成Mix Zone，之后這兩個用戶各自的匿名區(qū)域的概率為 0.5，但如果是在直道上相向相遇的情況，那么與原運動方向一致的用戶的匿名區(qū)域概率為p，反向運動的匿名區(qū)域概率為1-p，一般情況下，p遠遠大于0.5，具體數(shù)值需要從交通數(shù)據(jù)中統(tǒng)計得到。所以直道上相遇造成的個體熵不及岔道口。

本文在cachecloak方法基礎上做了以下改進：

修改了預測算法，原本的預測算法把整個LBS服務區(qū)域分成小塊，按照以往用戶路徑數(shù)據(jù)分析出每個小塊中用戶的下一個行進方向。該方法實施起來太過復雜，需要收集以往該區(qū)域的用戶移動路徑數(shù)據(jù)，并且由于是細粒度預測，預測路徑計算起來會非常復雜。對于單個用戶來說，他的實際移動路徑和統(tǒng)計方法得出的移動路徑不一定相符，復雜的計算并不能保證預測結(jié)果的準確性。

所以本文使用了電子地圖，預測路徑是直接沿著用戶所在道路向用戶前進方向延伸直到交叉路口停止。這種預測方法計算復雜度低，對于移動用戶路徑的預測準確率高。并且一個地區(qū)的地點地圖的獲取要比用戶移動數(shù)據(jù)的獲取容易得多。

對預測路徑上預查詢算法進行了修改，cachecloak是路徑預測完畢后，按照用戶請求的頻繁程度直接獲取路徑上所有的查詢點，然后一起交給LBS進行查詢。該算法并沒有考慮到查詢路徑上不同查詢的過期時間點的不同，而且密集查詢很容易被追蹤者發(fā)現(xiàn)。本文提出了一種預查詢模型，基于它可以更加有效的調(diào)整查詢時機，來擺脫追蹤，該模型同時也支持解決用戶相交的情況。

由此本文提出了一個新的算法，并且使用之前的熵模型進行評價。

2 算法模型

預測算法采用了電子地圖來預測用戶未來路徑，需要考慮到用戶行進方向，并且按照用戶實際速度，沿著道路行進直到交叉路口。當然該預測算法決定了本方法只適用于公路交通，而不適用于鄉(xiāng)村道路。

2.1 預查詢算法

預查詢即是指當預測了用戶未來的行進路徑之后，提前獲取行進路徑上的查詢結(jié)果。預查詢有以下四點目標：

讓實際查詢 LBS時間與用戶請求時間分開，這樣 LBS就不能獲得用戶實時位置，可以產(chǎn)生一個不確定區(qū)域，形成位置熵。這里預先查詢需要預測算法的支持。

通過控制預測路徑上各點的查詢時間，來使得用戶移動速度不被追蹤者識別，防止追蹤者通過用戶速度來追蹤。

由于每個用戶都因為預查詢產(chǎn)生了匿名區(qū)域，只要該匿名區(qū)域相交，就可以認為產(chǎn)生了Mix Zone，同樣會產(chǎn)生個體熵。如圖 2，兩個用戶雖然沒有在交叉路口相遇，但是他們的匿名區(qū)域相交，導致產(chǎn)生了個體熵。

圖2 十字路口個體熵示意

需要在產(chǎn)生盡可能多熵的情況下保證LBS的可用性，也就是保證預查詢結(jié)果最終可被用戶使用而不是過期。

預查詢模型有如下一些假設：

LBS查詢過期時間為T，并且在沒過期之前，查詢結(jié)果也會隨著時間逐漸失去精確性。

用戶速度在一段時間內(nèi)是恒定的，設為v。

在遇到岔道前，忽略掉道路的寬度與形狀，以用戶某一時刻的位置為原點的話，前進方向設定為正方向，那么就可以用預測路徑上預測點與原點之間的路程距離來表示預測點的位置，這樣每個查詢都可以表示為(s,t)的二元組，s為查詢點位置，t為查詢時間。岔道口的處理會在dummu user部分說明。

由以上假設可以得到下面的結(jié)論：

(1) 在t＞s/v時，查詢的時候查詢點位置早已經(jīng)被用戶經(jīng)過，該查詢結(jié)果已經(jīng)無用。

(2) 當s/v-t＞T時，查詢點時間太早，用戶到達前查詢結(jié)果已經(jīng)過期。

所以(s,t)必須滿足 s/v-T＜t＜s/v，這樣的查詢點才是可用的查詢點，也就是一個位置點必須在用戶經(jīng)過它之前的T時間內(nèi)進行預查詢。

我們使用圖3來表示查詢點，查詢點組成了查詢路徑。

圖3 不確定性時空

以用戶的當前所在位置與當前時間作為原點，橫軸表示預查詢的時間點，縱軸表示預查詢的位置，過原點的斜線表示用戶的 s-t線，由之前討論可知有效查詢點必須位于兩條平行的斜線之間。

在這個模型下，我們討論一下可能的各種預查詢方法所采用的預查詢路徑。

如圖4，紅線表示預查詢路徑，這是在cachecloak中采用的預查詢方法，每當用戶查詢時，緩存中沒有的話，就會對用戶路線進行預測，并且一次取回路線上所有查詢結(jié)果。這種方法雖然簡單，產(chǎn)生的位置熵最大，但是在每次觸發(fā)對LBS查詢的時候，用戶的具體位置暴露無疑，位置熵為0，并且這種密集的查詢也很容易泄露查詢之間的相關性以及用戶的前進速度。同時由于每次查詢時最遠處的查詢結(jié)果總是在快過期時被用戶使用，導致精確性不好。

圖4 cachecloak預查詢時空模型

圖 5表示的是另外一個極端，預查詢路徑與用戶的 s-t線重合。此時查詢并沒有任何提前，用戶是被完全追蹤的，用戶的位置，速度等信息都泄露，位置熵完全消失。

圖5 即時查詢時空模型

一般的預查詢路徑如圖 6，預查詢路徑的斜率是追蹤者看到的用戶的速度，所以需要隨機改變曲線斜率，而且事實上雖然圖中查詢路徑是到了邊界然后改變方向，實際卻可以超出邊界查詢(作為假查詢)，也可以隨時轉(zhuǎn)向，這些都是可以隨機設置的。這樣位置熵就會產(chǎn)生，同時用戶真實速度也得到了保護。

圖6 擾亂的預查詢時空模型

這里預查詢路徑的產(chǎn)生是隨機的，算法主要決定斜率和轉(zhuǎn)折點。

用戶相交時情況如圖7表示同向用戶相遇，圖8表示不同向用戶相遇。圖中，陰影區(qū)域的查詢可以被兩個用戶共用，紅線表示最長的公用查詢路線。用戶相遇可以產(chǎn)生個體熵。但是相對于叉路口，兩用戶在直道上反向相遇并不能產(chǎn)生1bit的熵值，根據(jù)統(tǒng)計規(guī)律，兩個用戶相遇然后同時反向的概率很小，所以此處產(chǎn)生的個體熵遠遠小于在叉路口產(chǎn)生的個體熵，這點前面熵模型時已經(jīng)分析過。但是通過假查詢，以及設計好各個用戶的預查詢路徑，是可以一定程度提高個體熵的產(chǎn)生值的。

圖7 同向相遇不確定時空模型

圖8 不同向相遇不確定時空模型

設計預查詢路徑的目的在于：

(1) 使得用戶和其他用戶相遇時造成有效數(shù)量的個體熵；

(2) 保護用戶的速度信息。

預查詢路徑確定之后，然后需要按照用戶查詢頻繁程度來確定具體查詢點，用戶實際使用查詢數(shù)據(jù)時需要在距當前距離 MIN_AREA范圍內(nèi)搜索最接近的查詢點，如果在MIN_AREA內(nèi)找不到查詢點的話，那就需要觸發(fā)預查詢了。但是由于本模型的每個預查詢點都是包含觸發(fā)時間的，不需要額外的觸發(fā)條件。

2.2 Dummy方法

之前的預測路徑只考慮了直道，在岔道口需要采用假用戶的方法來產(chǎn)生個體熵。在岔路口相遇的用戶會形成 Mix Zone，隨之產(chǎn)生個體熵，但是在稀疏環(huán)境下這種相遇的機會很少，所以我們需要產(chǎn)生假用戶來迷惑追蹤者，這里實現(xiàn)方式如下：

(1) 在直道預測路徑遇到叉路口時，繼續(xù)沿所有可能的方向進行預查詢；

(2) 在用戶到達岔路口時，在沒有與其他用戶的匿名區(qū)域相交的方向上都產(chǎn)生一個dummy user，沿著各條路徑繼續(xù)運動下去。

Dummy user的預查詢路徑也是完全隨機產(chǎn)生，它的消亡條件如下：

(1) 遇到其他用戶；

(2) 查詢數(shù)超過閾值；

(3) 到了下一個岔路口。

這樣就可以最大限度的利用岔路口的優(yōu)勢來增加熵值。

對于稀疏應用來說，假請求也不會給服務器帶來很大負擔，并且在用戶逐漸多起來之后，假請求也會越來越少，這是一個良性發(fā)展的解決辦法。Dummy方法需要一個衡量標準，也就是假查詢的數(shù)量與熵值增加的比。

3 結(jié)論

本文針對城市交通中用戶頻繁查詢不可信的時間相關性很強的LBS時的隱私保護問題，在cachecloak方法的基礎上進行了改進，使得用戶得到的查詢結(jié)果更加準確，同時也增加了追蹤者的追蹤難度。

先對追蹤者進行了分析，提出了兩種熵的概念以及計算公式，分析了以往隱私保護算法中對兩種熵值的影響。然后提出了預查詢模型，很好的表現(xiàn)了用戶查詢之間的時空相關性，同時也通過分析預查詢模型來產(chǎn)生預查詢路徑，用來提高熵值。dummy user的使用讓稀疏的應用也可以在岔路口增加熵值。

在實際中我們可以根據(jù)應用本身的特點如即時性需求和位置精確度要求，來根據(jù)熵模型選擇合適的預查詢策略，來達到隱私保護的目的。

[1]MOKBEL, C.C.F.Casper*： Query processing for location services without compromising privacy[J].ACM Trans Database Syst 34,2009.

[2]Meyerowitz, J.& Roy Choudhury, R.Hiding stars with fireworks： location privacy through camouflage.Proceedings of the 15th annual international conference on Mobile computing and networking 345-356 (2009).

[3]Meyerowitz, J.& Choudhury, R.Realtime location privacy via mobility prediction： creating confusion at crossroads.HotMobile 1-6 (2009).

[4]L.Sweeney.k-anonymity： a model for protecting privacy.International Journal on Uncertainty,Fuzziness and Knowledgebased Systems.2002.

[5]Pan Xiao, Hao Xing, Meng Xiaofeng.Privacy Preserving towards Continuous Query in Location-based Services.JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT