王鑫

【摘 要】随着基于位置的服务（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.