现实环境中基于虚拟用户的LBS位置隐匿方法*

陈 思，赵 明，张锦健

(中南大学软件学院，湖南 长沙410075)

1 引言

全球定位系统GPS(Global Positioning System)精度和性能的不断提高，推动了基于位置服务LBS(Location-Based Service)应用程序的发展，给人们的生活提供了许多便利。然而，位置信息共享如果被人恶意利用，则会带来一系列的问题(比如频繁出入的场所和常规的出行路线，可能暴露用户的身份和家庭住址)，这让针对个人的跟踪及诈骗难度降低。根据Busic等[1]调查，大量商业的LBS要求用户每隔几分钟更新一次当前位置。这种收集用户位置的系统，不仅潜在地侵犯了用户位置隐私，并且存在泄露用户位置信息的巨大隐患，最终严重影响用户体验及位置服务的发展。

为了保护用户的位置隐私，众多学者针对这一问题进行研究，目前已提出了大量可行的方法。其中，基于泛化的技术[2]提供了一个很好的解决方案：通过把用户的位置与其他k个用户的位置混合，使真实用户位置被确定的概率小于或等于1/k。然而，这种方法需要一个第三方服务器来承担用户和LBS提供者之间的相互作用。实际上，部署一个绝对安全的第三方服务器难度极大，而且，如果没有足够数量的用户，这种方法也不可行。

针对车辆密度较低的区域，基于模糊的技术从很大程度上保护了个人位置隐私，尤其是替换位置对泛化位置的补充。Hong等[3]提出了利用圆形区域代替用户真实位置的模糊法。但是，这种模糊技术不能对LBS返回结果进行处理，往往产生较粗糙的LBS结果，无法满足用户需求。

基于掩盖法的技术指在特定或全部场景下，用户通过不对外发布位置来达到保护位置隐私的目的。文献[4]是最为典型的代表。但是，Mix zones位置往往相对固定，且覆盖区的大小和隐私的强弱往往很难权衡。

综合以往研究，基于虚拟用户的方法是满足上述要求的有效途径[5 - 7]。该方法不必依赖于受信任的服务器，也不必收集周边用户的位置信息，系统可以自行生成虚拟用户并将自己位置连同虚拟用户位置一并发送给LBS提供商，使LBS提供商无法确定真实用户的位置。但是，过去基于虚拟用户的保护方法并没有考虑现实环境中的物理约束，实际隐私保护的鲁棒性值得商榷。因为基于虚拟用户隐私保护方法的鲁棒性强弱程度是依靠虚拟用户的行为是否自然而决定的，如图1所示。

Figure 1 Moving trajectories of user and dummies图1 真实用户与虚拟用户的移动轨迹

在图1中，实线表示真实用户的移动轨迹(记为T)，虚线轨迹为虚拟用户(记为d1和d2)。由于真实用户通常表现出一定的社会移动行为，所以构造逼真的虚拟用户运动对保护位置隐私极为重要。如图1a所示，如果在同一时间，攻击者收集到同一用户的三条运动轨迹，真实轨迹T将被识别的概率为100%，因为d1和d2显然不符合人们日常行动规律。因此，生成难以被攻击者轻松辨别且符合现实环境的虚拟用户至关重要，如图1b所示。

另外，真实环境中，轨迹的可溯性也是一个关键性因素。假设，一个用户频繁地请求LBS，则他发送的位置数据将构造一条清晰的运动轨迹，然而这样的运动轨迹容易泄露用户的位置隐私。因为一旦用户某一时刻的位置意外地被攻击者通过特殊的手段检测到，该用户以前全部的(也可能是未来的)位置将变得明显，即用户的运动轨迹是可溯的，如图2a所示。

Figure 2 Traceability图2 可追溯性

为了降低可溯性，一个简单而有效的方法就是将虚拟用户和真实用户的轨迹进行交叉。因为交叉的轨迹让攻击者无法准确地获取用户过去的位置。如图2b所示，假设有两条轨迹，即使攻击者获取了某一时刻的一个位置，但由于轨迹的交叉，他是无法确定用户的起始位置是m1还是m2。

针对上述问题，本文提出一种Dummy-Ex方法，创新点是利用交叉来保护用户的隐私。其余部分组织如下：第2节介绍概念与动机；第3节说明方案构造；第4节就提出的方法进行实验评估；第5节进行总结以及对未来工作进行展望。

2 概念与动机

2.1 基本概念

(1)最小覆盖区：由Lu等[6]所提出，隐匿面积定义为一次LBS请求中覆盖所有用户的最小面积。位置的隐匿性与最小覆盖面积有很强的关联。比如图3a中所描述的隐匿性相对图3b更弱，因为覆盖区域过小，攻击者则不需要猜测用户的真实位置，他可以直接定位到一个非常小的区域，如某栋楼房。最小覆盖区的提出是为了限制最小的隐形覆盖区的面积，因为用户在每个快照中需构建一个覆盖其它k-1个虚拟用户的隐形区域，用于混淆LBS提供商。

Figure 3 Anonymous area图3 隐形覆盖区面积

(2)位置可达性：对于当前的位置在任何一条真实或虚拟的路径中，依据用户当前的最大速度，在单位时间内的下一个位置应是可到达的。例如，用户请求LBS，在一定时间后(如3 min)再次请求服务，如果两次定位距离超过20 km，那么这个用户显然是虚拟的。因此，本文采用限制条件规范虚拟用户的运动，让每个虚拟用户单位时间内的位置在一个可到达的区域。

2.2 基本思想

本文所用相关符号的含义如表1所示。

Table 1 Symbol references表1 符号引用表

Figure 4 Basic plan图4 本文基本方案

3 Dummy-Ex方案构造

3.1 虚拟用户的运动控制

用户连续请求LBS，为了达到隐私要求，需首先确定每个虚拟用户的目的地。因为，随机选择虚拟用户的路由，有可能造成图2a的位置泄露。为了降低可溯性，选择虚拟用户目的地时，本文将对真实路由与虚拟路由实施交叉，这对保持用户与虚拟用户的行为一致性来说至关重要。

在路径混淆上，本方案将对路由的交叉调用评估和选择。若虚拟用户在真实用户之后交叉，会导致真实用户位置过于突出，如图5所示。长此以往，LBS提供商将会注意到，有一个用户遥遥领先于其他用户，这将增加真实用户被识别的可能性。为了避免这种情况的发生，本文方法在构建用户路由时，分为以下两种情况：

情况1用户前面的虚拟用户数量超过总数的一半时，可随机选择虚拟用户调用交叉。

情况2用户前面的虚拟用户数量小于总数的一半，则不调用交叉。

Figure 5 Crossing after real user图5 虚拟用户在真实用户之后调用交叉

3.2 虚拟用户生成算法(DLG)

本文所提出的虚拟用户生成算法(DLG)是在用户设置的匿名区域内，生成满足用户隐私需求的虚拟用户，如图6所示。基本思想是：首先，用户根据需求定义一个最小的隐形区域Amin和参数δi。其中对应隐形区域的最小半径为：

(1)

Figure 6 Dummy locations generating algorithm图6 虚拟用户位置生成算法

(2)

|δi-1|=εi

(3)

其中，εi是一个很小的正数(如0.05或者0.1)。

3.3 虚拟路径生成算法(DPC)

DPC算法是在DLG算法的基础上，将每张快照所产生的虚拟用户集通过交叉判断，然后把合适的虚拟用户填充至虚拟路由中。实施方法如下：考虑每个虚拟用户的可达性，本文首先由DLG构建出第一张快照中的虚拟用户，其次定义一个参数来限制每个虚拟用户从当前位置到下一个位置的最大距离。计算如下：

(4)

其中，vti表示在一个时间戳为ti的快照中，用户对应的速度。

算法1DPC算法

输出:D2,D3,…,Dk。

开始：Dj=∅；

步骤1for(i=2;i

步骤2for(j=2;i

end

end

步骤5

随机选择虚拟用户调用交叉；

不调用交叉;

end

将对应位置dm加入到虚拟路径Dj;

end

4 实验评估

在实验中，本文用定量的方法来评估Dummy-Ex方法的鲁棒性。首先利用Ultra GPS Logger记录了5条在长沙运动的真实GPS轨迹。然后用MobiREAL网络模拟器模拟真实用户和虚拟用户的运动。

4.1 参数设置

表2中的参数和值将用于本文的实验评估。真实用户和虚拟用户的移动速度将基于常规的平均速度1.30(m/s)，方差为0.22[(m/s)2]。本文选取15 000×15 000 m2的区域，并将之分为150×150的单元格来收集信息。

虚拟用户的数量在本文的方法中是一个非常重要的参数。因为大量的虚拟用户可以降低可溯性，但是也将增大通信的开销。所以，一般情况下，在保证隐私的情况下，用户会尽可能地降低虚拟用

Table 2 Experimental parameters表2 实验参数

户的数量。本文将使用不同数量的虚拟用户进行实验。

4.2 实验方法与结果

在实验中，本文引用CaSDA和V-circle两种方法(见表3)，在相同条件下进行对比实验。

Table 3 Methods for comparing experiments表3 用于对比实验的方法

4.2.1 虚拟用户对隐私的影响

本文首先评估不同虚拟用户数量k对真实路由暴露率的影响。从图7中可以看出，Dummy-Ex方法在虚拟用户数量相同的情况下，隐匿性非常强，且随着虚拟用户数量k的增加，真实用户曝光几率越来越小。

相对而言，CaDSA虽然隐匿性也随着虚拟用户数量k的增加变得越来越强，但它需要一个受信任的第三方来缓存用户的LBS请求，并通过筛选缓存中的历史足迹形成虚拟用户，虽然在隐匿性上基本达到了用户需求，但由于第三方的建立，无形中增加了真实用户曝光的可能性。V-circle也有较好的隐匿性，在虚拟用户的选择上充分考虑了现实环境的影响，但由于未考虑轨迹的可溯性，虽然每条虚拟轨迹看起来更真实，但在隐匿性上还不能达到理想状态。

Figure 7 Number of virtual users vs exposure probability图7 虚拟用户数量k与曝露概率

4.2.2 平均混乱时间MTC

在实验中，为了测试可追溯性，本文引用文献[11]中的指标“MTC(Mean Time to Confusion)”。MTC定义用户的真实位置被LBS提供商意外泄后到重新隐匿的平均时间。每当一个服务请求发出后，则需要计算每个位置可能是真实用户的熵值，计算公式如下：

(5)

对于所有的虚拟用户数量来说(N=16，25，32)，他们的MTC所显示的特征基本上相同，因此实验中用32个虚拟用户进行讨论。当用户数量(真实和虚拟用户数量)为32个时，对于不同匿名面积所产生的MTC值，如图8所示。由图8可以看出，在匿名面积很小的情况下，如300内，三种方法所需要的时间差不多，这是因为在大多数情况下，虚拟用户就分布在真实用户周围，如图3a所示，基本上不需要对虚拟用户过多处理。

Figure 8 Virtual path generation time图8 虚拟路径生成时间

当匿名区域面积较大时，Dummy-Ex方法明显比其他两个方法的MTC值要小得多。这表明本文方法在降低可溯性方面非常出色。但是，随着匿名区域大于1 500 m2后，用户重新隐匿将花费越来越多的时间，因为虚拟用户的密度变得很小，虚拟路线的选择将花费更多的时间。但是，总体上Dummy-Ex还是保持着很大的优势。CaDSA在降低可溯性方面和本文所提方法相差较小，但由于是利用中间件缓存的用户LBS请求数据，虽然响应时间较短，可没有考虑现实环境约束，所以在降低可溯性方面表现一般。V-circle考虑了现实环境的约束，但没有对虚拟用户进行运动控制，有时会造成真实用户的意外泄露，且随着最小覆盖区面积的增加,MTC增长较快。

5 结束语

考虑现有混淆、模糊和掩盖等方法的不足，本文充分考虑现实环境和最小匿名区域大小等因素对位置隐私的影响，提出了一种有效的方法Dummy-Ex。该方法在每个路由快照中生成逼真的虚拟用户，并基于用户与虚拟用户位置关系采用调用交叉来创建路由，实现对位置隐私的保护。实验结果表明，本文方法在保护位置隐私方面卓有成效。

虽然构建虚拟用户是当前常用的隐私保护技术，有利于个体用户隐私保护，但是随着大数据的发展，面对大数据资源的持续公开，隐私管理将面临新型的隐私攻击。在以后的研究中，如何预防资源数据融合带来的隐私威胁将是一个重要的研究方向。

参考文献:

[1] Busic L,Filjar R.The role of position reporting frequency in LBS QoS establishment mechanisms for location privacy[C]∥Proc of SoftCOM,2006:209-213.

[2] Gruteser M,Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C]∥Proc of the 1st International Conference on Mobile Systems,Applications and Services (MOBISYS 2003),2003:31-42.

[3] Hong J I,Landay J A.An architecture for privacy-sensitive ubiquitous computing[C]∥Proc of the 2nd International Conference on Mobile Systems,Applications,and Services(MOBISYS 2004),2004:177-189.

[4] Beresford A R, Stajano F.Mix zones:User privacy in location-aware services[C]∥Proc of the 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops,2004:127-131.

[5] Kido H,Yanagisawa Y, Satoh T.An anonymous communication technique using dummies for location-based services[C]∥Proc of International Conference on Pervasive Services,2005:88-97.

[6] Lu H,Jensen C S.Privacy-area aware dummy-based location privacy in mobile services[C]∥Proc of the 7th ACM International Workshop on Data Engineering,2008:16-23.

[7] Yanagisawa Y,Kido H.Location traceability of users in location-based services[C]∥Proc of International Conference on Mobile Ubiquitous System,2006:1-8.

[8] Gruteser M,Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C]∥Proc of the 1st International Conference on Mobile Systems,Applications an Services(MOBISYS 2003),2003:31-42.

[9] Niu B,Li Q,Zhu X.Enhancing privacy through caching in location-based services[C]∥Proc of the 34th IEEE Conference on Computer Communications,2015:1017-1025.

[10] Niu B, Zhang Z, Li X, et al.Privacy-area aware dummy generation algorithms for location-based services[C]∥Proc of IEEE International Conference on Communications,2014:957-962.

[11] Shokri R,Freudiger J, Jadiwala M, et al.A distortion-based metric for location privacy[C]∥Proc of ACM WPES’09,2009:21-30.