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

王鑫

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

【關鍵詞】位置隱私 粗粒度 空間推理 地理敏感度

1 引言

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

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

圖1 空間地理環境

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

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

2 敏感度數學模型

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

2.1 空間模型

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

定義函數表示所有特征類型所在區域的并集，FT表示特征類型集。特征類型可以分為敏感的和非敏感的，定義，其中表示敏感特征類型集，當區域r滿足條件時，我們認定區域r是敏感的。

2.2 敏感度度量

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

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

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

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

圖2 敏感區域示例圖

2.3 隱私屬性

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

2.4 模糊位置

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

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

3 模糊處理體系結構

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

圖3 模糊處理體系結構

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

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

4.1 模糊策略

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

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

4.2 模糊方法

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

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

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

4.3 實例分析

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

圖4 模糊位置形成過程

5 仿真實驗與結果分析

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

5.1 空間精確性

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

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

由圖5可以看出，當敏感特征類型大小為1×1時，SPyr方法和SHil方法所產生的模糊區域平均大小相同，隨著特征類型所包含網格數的不斷擴大，兩個方法所產生的模糊區域平均大小都有顯著提升，并且敏感特征類型越大，兩個方法的差別越明顯。可以得出如下結論：當敏感特征類型較小時，SPyr方法和SHil方法的空間精確性差別不大；當敏感特征類型較大時，SHil方法比SPyr方法更精確。

5.2 模糊時間

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

圖6 模糊時間對比示意圖

由圖6可以看出，當敏感實體數目為5、10、20、30時，SPyr方法和SHil方法產生模糊區域所需的時間幾乎相同，當敏感實體數目為50時，二者的模糊時間開始有明顯的差別，并且隨著敏感實體數目增多，兩種方法產生模糊區域所需的時間都有大幅提升，但是同等條件下，SPyr方法所需模糊時間更多。可以得出如下結論：當敏感實體數目較少時，SPyr方法和SHil方法的模糊時間差別不大；當敏感實體數目較多時，同等條件下，SHil方法比SPyr方法所需的模糊時間少，可見SHil方法有更好的性能。

6 結語

本文依據地理空間環境，首先對區域的敏感度進行量化處理，建立了一個基于地理敏感度的數學模型，然后在模糊處理體系結構的基礎上，提出一種基于地理敏感度的空間模糊方法——SHil，該方法依據用戶的隱私屬性，對空間敏感特征類型進行模糊，得到有效模糊位置，從而保護實體位置隱私免遭空間推理攻擊，具有一定實用價值。最后通過仿真實驗，將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.