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

王鑫（內蒙古伊泰集團有限公司，內蒙古鄂爾多斯 017000）

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

王鑫
（內蒙古伊泰集團有限公司，內蒙古鄂爾多斯 017000）

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

位置隱私 粗粒度 空間推理 地理敏感度

1　引言

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

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

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

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

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

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

圖4　模糊位置形成過程

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

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

2.1空間模型

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

2.2敏感度度量

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

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

2.3隱私屬性

用戶隱私屬性主要指用戶隱私需求，可以用序對 ＜FTs，T＞表示，F(xiàn)Ts表示用戶定義的敏感特征類型集，T表示特征類型對應的閾值集，對于 ft∈FTs，定義閾值函數(shù) Γ（ft）=v，v∈（0，1），v表示 ft的敏感度閾值，Γ（ft）=1表示特征類型 ft根本不敏感，這種情況沒有研究意義。 Γ（ft）=0表示特征類型 ft絕對敏感，絕對敏感只有當ft沒有實例的時候才存在，沒有研究意義。本文中，區(qū)域r的敏感度需滿足 Psens（ft，r）≤v。

基于上述描述，隱私屬性序對 ＜FTs，T＞可以進一步描述為：FTs=｛ft1，...，ftn｝，T=｛Γ（ft1），...，Γ（ftn）｝。舉例如下：

FTs=｛Hospital，ReligiousBuilding｝，

T=｛Γ（Hospital）=0.4，Γ（ReligiousBuilding）=0.1｝，

可以看出特征類型Religious Building比Hospital具有更低的閾值，也就是需要更強的位置隱私保護。

2.4模糊位置

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

3　模糊處理體系結構

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

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

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

4.1模糊策略

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

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

4.2模糊方法

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

本文將二維空間網(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ū)域（line6），如此往復，直到每一個網(wǎng)格都被檢查完畢，最終返回模糊位置集合，最壞的情況是返回整個區(qū)域作為模糊位置。

4.3實例分析

圖4舉例說明了SHil方法的每個執(zhí)行步驟，初始參考空間標記為‘START’，模糊后的空間標記為‘RESULT’，在圖4中有兩個相同類型的敏感特征，設定敏感度閾值為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í)行完畢，模糊位置形成。

5　仿真實驗與結果分析

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

5.1空間精確性

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

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

5.2模糊時間

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

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

6　結語

本文依據(jù)地理空間環(huán)境，首先對區(qū)域的敏感度進行量化處理，建立了一個基于地理敏感度的數(shù)學模型，然后在模糊處理體系結構的基礎上，提出一種基于地理敏感度的空間模糊方法——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，F(xiàn)uzziness 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. ofthe 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.

王鑫（1990—），男，內蒙古鄂爾多斯人，工學碩士，畢業(yè)于哈爾濱工業(yè)大學，現(xiàn)就職于內蒙古伊泰集團有限公司信息管理中心，研究方向：網(wǎng)絡與信息安全。