王鑫

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

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

1 引言

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

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

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

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

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

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

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

2.1 空間模型

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

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

2.2 敏感度度量

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

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

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

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

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

2.3 隱私屬性

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

2.4 模糊位置

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

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

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

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

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

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

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

4.1 模糊策略

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

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

4.2 模糊方法

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

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

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

4.3 實(shí)例分析

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

圖4 模糊位置形成過(guò)程

5 仿真實(shí)驗(yàn)與結(jié)果分析

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

5.1 空間精確性

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

圖5 空間精確性對(duì)比示意圖

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

5.2 模糊時(shí)間

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

圖6 模糊時(shí)間對(duì)比示意圖

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

6 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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.