基于地理敏感度的空間模糊方法

王鑫

【摘 要】隨著基于位置的服務(wù)（location-based services，簡稱LBS）的廣泛應(yīng)用，個人位置信息的保護越來越受到人們關(guān)注。由于傳統(tǒng)的位置隱私保護方法將用戶真實位置用粗粒度位置來代替，并沒有考慮用戶所處的地理位置環(huán)境，所以很容易受到空間推理攻擊，威脅用戶位置隱私。本文通過考慮地理位置環(huán)境相關(guān)信息，提出一種基于地理敏感度的空間模糊方法，用以模糊用戶位置，并做了相關(guān)實驗來評估該方法的性能和精確性。

【關(guān)鍵詞】位置隱私 粗粒度 空間推理 地理敏感度

1 引言

近年來，基于位置的服務(wù)（location-based services，簡稱LBS[1]）不斷發(fā)展，用以實現(xiàn)物聯(lián)網(wǎng)中的實時、快速、可擴展的物體位置搜索。但是，由于用戶在使用LBS服務(wù)時，需要向LBS服務(wù)器提供自身的位置信息，而LBS服務(wù)器又不是絕對可靠的，所以基于位置的服務(wù)給用戶的位置隱私帶來了極大的威脅。為了確保位置隱私，研究者提出了很多不同的方法，大多數(shù)都是基于模糊技術(shù)，旨在隱匿用戶真實位置，向LBS服務(wù)器提供非精確的位置信息，實現(xiàn)一定程度上的位置隱私保護。k-匿名[2]技術(shù)就是其中之一，它通過確保每個用戶的位置與其他k-1個用戶的位置難以區(qū)分，來達到模糊效果。

上述方法有一個共同缺點，那就是沒有考慮用戶所處的地理位置環(huán)境，攻擊者可以根據(jù)已有的空間上下文環(huán)境，推理出用戶真實位置的精確邊界，進而進行位置推理，威脅位置隱私。上述方法的另一個大的缺點是，沒有考慮用戶對于不同位置的敏感度需求，也就是說，并不是所有位置對用戶都具有相同的敏感程度，如圖1所示地理環(huán)境。

圖1 空間地理環(huán)境

在圖1中，假設(shè)一個LBS用戶位于醫(yī)院之內(nèi)，而醫(yī)院對于這個用戶是敏感的，考慮圖1.a的地理環(huán)境：醫(yī)院H靠近湖L和居住區(qū)R，H，L和R都是多邊形區(qū)域。假設(shè)湖L是不可達的，并且攻擊者知道這一地理信息，進一步假設(shè)用戶真實位置被區(qū)域模糊了。如果位于圖1.b的位置，攻擊者可以很容易推理得知用戶位于一個敏感區(qū)域H內(nèi)；如果位于圖1.c的位置，因為用戶的位置不可能位于湖L之內(nèi)，唯一的可能位置便會是醫(yī)院H內(nèi)，模糊位置仍就是敏感的，在此種情況下攻擊者只需將用戶模糊位置同湖L不可達這一公共信息相結(jié)合，便可推理出用戶精確位置的相關(guān)信息，這就是空間位置推理。如果位于圖1.d的位置，我們可以認為模糊位置在一定程度上是敏感的。

為了解決這一問題，本文首先對區(qū)域的敏感度進行量化處理，然后提出一種可靠的體系結(jié)構(gòu)，最后提出一種基于地理敏感度的空間模糊方法，實現(xiàn)對敏感位置的空間模糊，從而達到更好的位置隱私保護效果。

2 敏感度數(shù)學(xué)模型

本文提出的數(shù)學(xué)模型主要包括四個方面：空間模型，敏感度度量，隱私屬性和模糊位置。

2.1 空間模型

我們把LBS應(yīng)用所涉及的區(qū)域稱之為參考空間，由一個二維空間的有界區(qū)域組成，位于中的幾何物體有一個包含地理空間標準[3]的空間類型。依據(jù)地理空間標準，我們用空間特征（Spatial Feature）來描述在位置隱私方面不同區(qū)域的差別，每個特征都有一個類型（Feature Type，簡稱ft），每個類型的特征在二維空間上都有一定大小的區(qū)域，本文假設(shè)不同類型特征所在的區(qū)域是不重合的。

定義函數(shù)表示所有特征類型所在區(qū)域的并集，F(xiàn)T表示特征類型集。特征類型可以分為敏感的和非敏感的，定義，其中表示敏感特征類型集，當區(qū)域r滿足條件時，我們認定區(qū)域r是敏感的。

2.2 敏感度度量

定義函數(shù)表示實體空間位置的概率密度函數(shù)，表示用戶處于區(qū)域r內(nèi)的概率，對于參考空間來說，，。如果區(qū)域r不可達，那么，如果區(qū)域r可達，存在子區(qū)域，使得。

我們用上述概率模型來定義區(qū)域的敏感度，區(qū)域敏感度是一個[0，1]的值，用來描述一個區(qū)域到底有多敏感，對于特征類型，定義為區(qū)域r關(guān)于的敏感度，表述如下：

當區(qū)域r不可達時，敏感度為0；當區(qū)域r被完全覆蓋時，敏感度為1。根據(jù)概率密度函數(shù)，可以將 表示如下：

在圖2情況下計算。區(qū)域r與類型為Hospital的兩個特征H1、H2有重疊的部分，而Hospital是敏感特征類型，H1與部分重合，H2與完全重合，并且區(qū)域包含湖。假設(shè)是不可達的，用戶位置在空間上等可能分布，那么區(qū)域r關(guān)于Hospital的敏感度計算如下：

圖2 敏感區(qū)域示例圖

2.3 隱私屬性

用戶隱私屬性主要指用戶隱私需求，可以用序?qū)Ρ硎?，表示用戶定義的敏感特征類型集，表示特征類型對應(yīng)的閾值集，對于，定義閾值函數(shù)，，表示的敏感度閾值，表示特征類型根本不敏感，這種情況沒有研究意義。表示特征類型絕對敏感，絕對敏感只有當沒有實例的時候才存在，沒有研究意義。本文中，區(qū)域r的敏感度需滿足。

2.4 模糊位置

基于以上理論，我們可以定義模糊位置如下：對于含有隱私屬性的區(qū)域r，如果r是敏感的，并且滿足，那么認為r就是一個模糊位置。

本質(zhì)上來說，模糊位置就是一個包含空間敏感部分的模糊區(qū)域，模糊位置可以為任意形狀，任意大小，甚至可以覆蓋整個空間，但是為了在模糊的基礎(chǔ)上保證一定的服務(wù)質(zhì)量，模糊位置需要用一個較小的空間表示。對于模糊位置集合，我們用區(qū)域平均大小來定義的空間精確度，表示如下：

3 模糊處理體系結(jié)構(gòu)

由于需要對敏感位置進行模糊處理，所以本文提出的體系結(jié)構(gòu)必須包含一個模糊引擎，由客戶端、模糊引擎和LBS服務(wù)器所組成的模糊處理體系結(jié)構(gòu)如圖3所示。

圖3 模糊處理體系結(jié)構(gòu)

該結(jié)構(gòu)中模糊處理過程分為如下三個階段：（1）用戶通過客戶端中的屬性編輯器來指定自己的隱私屬性，例如選擇敏感特征類型。（2）基于輸出的隱私屬性，用戶可以請求模糊引擎產(chǎn)生模糊位置，模糊引擎可以在第三方服務(wù)上運行，如web應(yīng)用，筆記本，甚至是移動終端[4]。（3）對于一個服務(wù)請求，位置執(zhí)行模塊檢查用戶位置，如果用戶落在模糊位置之內(nèi)，那么用模糊位置代替用戶真實位置，并將模糊位置傳送給LBS服務(wù)器，否則向LBS服務(wù)器傳送用戶真實位置。

4 基于地理敏感度的空間模糊方法

4.1 模糊策略

為了達到較好的模糊效果，本文用基于網(wǎng)格的空間表示方法[5]將參考空間進行離散化處理，假設(shè)空間被劃分為規(guī)則的網(wǎng)格，并且網(wǎng)格需要足夠小來覆蓋特征類型，一個特征類型可以包含一個或者多個網(wǎng)格，但是一個網(wǎng)格不允許跨越兩個特征類型，否則需要進一步劃分網(wǎng)格，如果網(wǎng)格是敏感特征類型的一部分，那么認定網(wǎng)格是敏感的，在這種情況下網(wǎng)格c的敏感度記為：，由于敏感度超過了敏感閾值，我們認為網(wǎng)格c是過度敏感的。

本文的模糊策略是通過聚集鄰近的網(wǎng)格，將每一個過度敏感的網(wǎng)格c進行模糊處理，方法是通過漸進地擴大包含網(wǎng)格c的區(qū)域，直到產(chǎn)生一個滿足用戶隱私屬性的模糊位置。

4.2 模糊方法

上述聚集方法對單個網(wǎng)格進行處理，每次只聚集一個網(wǎng)格，而不是對整個敏感特征類型進行直接處理，這樣獲得的模糊位置會小于直接模糊整個區(qū)域所得的結(jié)果。

本文將二維空間網(wǎng)格映射到Hilbert空間填充曲線[6]上，然后基于Hilbert空間曲線對網(wǎng)格進行聚集，Hilbert空間曲線是一維曲線，可以訪問二位離散空間中的每一個網(wǎng)格?；诖?，本文提出一種基于地理敏感度的空間模糊方法——SHil，來產(chǎn)生模糊位置。SHil方法描述如下：

SHil方法掃描整個網(wǎng)格序列，每當遇到過度敏感的網(wǎng)格，SHil從當前網(wǎng)格產(chǎn)生一個模糊區(qū)域（line 6），如此往復(fù)，直到每一個網(wǎng)格都被檢查完畢，最終返回模糊位置集合，最壞的情況是返回整個區(qū)域作為模糊位置。

4.3 實例分析

圖4舉例說明了SHil方法的每個執(zhí)行步驟，初始參考空間標記為‘START，模糊后的空間標記為‘RESULT，在圖4中有兩個相同類型的敏感特征，設(shè)定敏感度閾值為25%，‘START初始空間被劃分為4×4網(wǎng)格，包含16個單元格，所有單元格被希爾伯特空間曲線所貫穿，標記為‘GRID。接下來依據(jù)隱私屬性來檢查每一個網(wǎng)格，用‘OK或者‘NO來標記已檢查過的網(wǎng)格，‘OK表示網(wǎng)格不敏感，‘NO表示網(wǎng)格過度敏感，需要聚集近鄰網(wǎng)格，直到滿足用戶隱私屬性。步驟1—16為整個模糊過程，當最后一個網(wǎng)格被檢查完畢，SHil方法執(zhí)行完畢，模糊位置形成。

圖4 模糊位置形成過程

5 仿真實驗與結(jié)果分析

本文用已有的SPyr方法[7]與SHil方法進行對比，SPyr方法基于金字塔數(shù)據(jù)結(jié)構(gòu)進行空間模糊，該結(jié)構(gòu)表與Casper系統(tǒng)中的空間k-匿名結(jié)構(gòu)[8]類似，SPyr方法利用樹的形式表示金字塔，樹中結(jié)點表示空間區(qū)域，根結(jié)點表示整個參考空間。用象限遞歸劃分空間區(qū)域，保證樹中每一個中間結(jié)點都有四個孩子，分別與每個象限相對應(yīng)，對于每一個過度敏感的葉子結(jié)點，用該節(jié)點對應(yīng)的象限進行模糊，直到滿足條件。

5.1 空間精確性

本文用模糊區(qū)域平均大小來衡量空間精確性，假設(shè)參考空間大小為128×128網(wǎng)格，每個網(wǎng)格都足夠小來覆蓋特征類型。假設(shè)有100個實體，每個實體都是自身的敏感特征類型，敏感特征類型大小從1×1網(wǎng)格到32×32網(wǎng)格均勻變化，設(shè)定。SPyr方法與SHil方法的空間精確性對比如圖5所示。

圖5 空間精確性對比示意圖

由圖5可以看出，當敏感特征類型大小為1×1時，SPyr方法和SHil方法所產(chǎn)生的模糊區(qū)域平均大小相同，隨著特征類型所包含網(wǎng)格數(shù)的不斷擴大，兩個方法所產(chǎn)生的模糊區(qū)域平均大小都有顯著提升，并且敏感特征類型越大，兩個方法的差別越明顯?？梢缘贸鋈缦陆Y(jié)論：當敏感特征類型較小時，SPyr方法和SHil方法的空間精確性差別不大；當敏感特征類型較大時，SHil方法比SPyr方法更精確。

5.2 模糊時間

本文用產(chǎn)生模糊區(qū)域所需時間來衡量模糊時間，假設(shè)參考空間大小為128×128網(wǎng)格，每個網(wǎng)格都足夠小來覆蓋特征類型。設(shè)定兩個敏感特征類型，大小為4×4網(wǎng)格，假設(shè)具有這樣敏感特征類型的實體數(shù)目從10到100均勻變化，設(shè)定。SPyr方法與SHil方法的模糊時間對比如圖6所示。

圖6 模糊時間對比示意圖

由圖6可以看出，當敏感實體數(shù)目為5、10、20、30時，SPyr方法和SHil方法產(chǎn)生模糊區(qū)域所需的時間幾乎相同，當敏感實體數(shù)目為50時，二者的模糊時間開始有明顯的差別，并且隨著敏感實體數(shù)目增多，兩種方法產(chǎn)生模糊區(qū)域所需的時間都有大幅提升，但是同等條件下，SPyr方法所需模糊時間更多?？梢缘贸鋈缦陆Y(jié)論：當敏感實體數(shù)目較少時，SPyr方法和SHil方法的模糊時間差別不大；當敏感實體數(shù)目較多時，同等條件下，SHil方法比SPyr方法所需的模糊時間少，可見SHil方法有更好的性能。

6 結(jié)語

本文依據(jù)地理空間環(huán)境，首先對區(qū)域的敏感度進行量化處理，建立了一個基于地理敏感度的數(shù)學(xué)模型，然后在模糊處理體系結(jié)構(gòu)的基礎(chǔ)上，提出一種基于地理敏感度的空間模糊方法——SHil，該方法依據(jù)用戶的隱私屬性，對空間敏感特征類型進行模糊，得到有效模糊位置，從而保護實體位置隱私免遭空間推理攻擊，具有一定實用價值。最后通過仿真實驗，將SHil方法與SPyr方法進行對比，分析了SHil方法的性能和精確性。

參考文獻：

[1] Kevin Ashton. That ‘Internet of Things Thing[C]. RFID Journal. Juli 2009.

[2] Samarati P， Sweeney L. Protecting privacy when disclosing information：k- anonymity and its enforcement through generalization and suppression[J]. International Journal on Uncertainty， Fuzziness and Knowledge-based Systems，2002，

10（5）：557～570.

[3] Open GIS Consortium. Open GIS simple features specification for SQL， 1999. Revision 1.1.

[4] G. Ghinita，M.Damiani， E. Bertino and C. Silvestri. Interactive Location Cloaking with the PROBE Obfuscator. In Proc. of the Tenth International Conference on Mobile Data Management： Systems， Services and Middleware， 2009.

[5] M.Atallah and K. Frikken. Privacy-preserving location-dependent query processing. In ACS/IEEE Intl. Conf. on Pervasive Services （ICPS）， 2004.

[6] H. Samet. Foundations of Multidimensional and Metric data Structures. Morgan Kaufmann， 2006.

[7] M. L. Damiani， E. Bertino， and C. Silvestri. PROBE： an obfuscation system for the protection of sensitive location information in lbs. CERIAS Technical Report， Purdue University， 2008.

[8] M. F. Mokbel， C.-Y. Chow， and W. G. Aref. The new Casper： query processing for location services without compromising privacy. In Proc. VLDB， pages 763-774， 2006.