隐私保护下的组最近邻查询算法研究

刘晓乐　李　博

(河南工程学院计算机学院　河南 郑州 451191)



隐私保护下的组最近邻查询算法研究

刘晓乐李博

(河南工程学院计算机学院河南 郑州 451191)

摘要针对现有的组最近邻GNN(Group Nearest Neighbor)查询的隐私保护算法没有考虑地图匹配攻击的问题，在无可信第三方的模型下，提出基于三阶段的保护用户位置隐私的组最近邻算法SFR(Send-Filter-Refine)。发送阶段中用户向服务商发送可防御地图匹配攻击的矩形区域来代替精确位置；过滤阶段中服务商利用各区域计算所有可能成为结果的数据点并回传给用户；求精阶段为了防止发起查询的用户间的隐私泄露，通过用户间的无序交互来得到最终的查询结果,并提出多个剪枝策略来加快查询速度。基于真实路网的实验结果表明，SFR与传统方法相比，有更高的查询效率和更低的受攻击率。

关键词组最近邻隐私保护位置服务提供商

0引言

近年来，随着移动计算技术和通信技术的不断发展，随时随地获得个人精确位置成为可能，基于位置的服务LBS(Location Based Service)受到人们的普遍关注。组最近邻GNN查询[1]是最近邻NN查询[2]的一种变体，它查找的是到给定多个查询对象距离之和最小的点。GNN查询在现实生活中有广泛的应用，例如，由多个社区所组成的社交网络中，查找各个社区的领导者/核心，可以查找到该社区中各成员距离和(表示成员间的熟悉程度)最小的人；同一城市的一组用户想查询一家离他们距离之和最小的餐馆作为见面地点等。

然而，用户在享用LBS的同时，包含他们精确位置的信息被位置服务提供商LSP(Location Service Provider)所获取。LSP能够根据这些信息得到用户的生活方式、健康状况和政治背景等[3]。个人隐私泄露问题逐渐引起广大学者的关注[4-6]。

图1　用户的精确位置及相应的位置区域

为了在提供LBS的同时，保护用户的隐私，一种解决方法是利用可信的第三团体TTP(Trusted Third Party)在用户和LSP之间进行通信[7]。这种方法有一定的局限：(1)所有用户将位置信息暴露给TTP，存在单点被攻击的危险；(2)用户的隐私只在当前时刻被保护，不能保证“相关攻击”(如用户运动的历史轨迹)。另一种常用的方法是用户向LSP发送一个位置范围(通常是一个矩形)来代替精确的位置[3]，如图1所示，用矩形区域代替精确位置点。LSP返回该矩形下所有可能成为查询结果的数据点，用户再根据自己的精确位置，从这些点中直接找到最终的结果。这种无TTP参与的模型，避免了上述问题。本文采取的就是无TTP模型。

尽管无TTP模型下的NN查询相关的隐私保护技术有很多[8]。但由于GNN查询中发出查询的用户有多个，它的查询结果取决于所有查询用户的位置，单个用户无法只根据自己的精确位置信息来得到GNN结果。因此，传统用于NN查询的隐私保护技术无法直接应用到GNN查询中。文献[9]首次解决了隐私保护下的GNN查询算法，但算法使用简单的矩形区域代替用户的精确位置，容易受到地图匹配的攻击。例如，攻击者在获取地图信息后，可通过地图匹配的方法排除一些障碍区域(如湖泊等)，从而大大增加攻击的概率。此外，地图中所包含一些如医院、减肥中心等重要的语义信息，简单的矩形区域可能包含这些敏感信息，也容易泄露用户个人隐私。另外，发出GNN查询的用户虽然有可能彼此熟识，但用户之间也需要保护位置隐私，这为隐私保护下的GNN查询提出了新的挑战。

本文解决了GNN查询的隐私保护问题，所提出的基于三阶段的查询算法SFR。不仅可有效防御地图匹配攻击，还能保护发起查询的各个用户间的位置隐私。在发送阶段，用户结合地图中的语义信息向LSP发送各自的位置区域来代替精确位置，避免用户位置隐私的泄露并防御地图匹配攻击；在过滤阶段，提出了针对位置区域的GNN查询算法，所提的剪枝策略能够有效过滤掉那些一定不是结果的数据点；最后在求精阶段计算出最终精确的GNN结果，用户间进行的无序交互，避免了用户间的隐私泄露，并最终得到正确的查询结果。

最后，基于真实城市路网，对本文所提算法SFR与文献[9]所提的算法IPPF进行了性能比较和验证。实验结果表明，与IPPF相比，SFR有更高的查询效率和更低的受攻击率。

1问题定义

本文假设用户和LSP通过网络(移动网络或因特网)互相连接，查询集合Q由n个用户u1,u2, …,un组成，它们相应的位置用l1,l2, …,ln来表示，被查询的数据点集合用P表示。下面列出了传统针对点的GNN查询以及隐私保护下针对区域的GNN查询的形式化定义。

隐私保护下的GNN查询中，LSP只知道各用户的位置区域，所有用户到数据点的距离之和是一个范围，而不是一个值，因此无法直接得到精确的GNN结果。算法SFR先执行针对这些区域的GNN查询，来得到所有可能成为结果的数据点，放在候选集合Scnd中。Scnd中的对象都是可能成为最终GNN结果的点，所有可能成为GNN结果的点也一定在Scnd中。本文在下一节中对如何快速得到Scnd，以及如何利用Scnd进一步得到最终的GNN结果进行了详细的介绍。

2隐私保护下的GNN查询算法SFR

SFR采用无TTP模型，即不存在任何中心节点参与查询运算，但由于GNN查询结果取决于所有发出查询用户的精确位置，单个用户无法直接根据自己的位置计算出结果，这给无TTP模型下的GNN查询带来了难度和挑战。

本文提出了由协调者参与的查询算法框架，在进行GNN查询之前，系统随机选取一个协调者，用来协助系统完成隐私保护下的GNN查询。该协调者可以是发出GNN查询的其中一个用户，也可以是系统中不参与查询的其他用户。它与中心节点的不同之处在于，不同的GNN查询，系统所选取的协调者是不同的，从而消除了单个节点被攻击的危险。此外，协调者只能获得用户的ID以及它所发出的查询类型，而不知道用户所在的位置，进而保护了用户与协调者之间的位置隐私。本节将对基于三阶段的SFR算法进行详细介绍。

2.1发送阶段

发出GNN查询的组内每个用户首先向协调者注册自己的ID(如IP地址、电话号码等)，并从协调者处获得一个查询ID(QID)。再结合地图中的语义信息，生成自己的安全位置区域，把该区域和QID发送给LSP，在因特网中发送时可采用假名服务[10]的方法，在无线个人区域网络(如蓝牙或802.11)中发送时可采用随机选取节点[8]的方法。这些技术能够向LSP隐藏用户的ID信息。最后，协调者只把与GNN查询有关的信息(QID、组查询用户个数)发送给LSP。

生成用户的安全位置区域首先要考虑地图匹配攻击，这是因为攻击者在获取地图信息后，可通过地图匹配的方法排除一些行人车辆无法到达的障碍区域(如湖泊等)，从而增加攻击的概率；其次还要考虑地图中包含的重要语义信息的泄露，这是因为地图文件不仅包含位置坐标等信息，还包含着更重要的语义信息，如医院、减肥中心和军事要地等。攻击者可根据一些敏感的语义信息来获取用户生活方式、健康状况和政治背景等个人隐私。

针对重要语义信息的保护问题，系统先在地图上定义了几个类型的重点保护区域(如医院、减肥中心、心理诊所等)，先离线预计算出这些区域对应的一些安全区域，使得安全区域要么不包括重要区域，要么包含k种重要区域。若用户处在这些重点保护区域内，直接为其生成安全区域。当用户所要保护的语义类型不在系统的预计算列表中时，系统再为用户在线构建安全的位置区域。发送阶段的安全区域生成算法见算法1。

算法1安全区域生成算法

输入：N个用户的精确位置(*ax, *ay), 障碍阈值δ;

输出：N个用户的安全区域(*lx, *ly, *hx, *hy);

1.for(i =1toN)

2.if(该点处在预计算的重点保护区域内)

3.return相应的(lx[i], ly[i], hx[i], hy[i]);

4.else

5.生成一个包含点(ax[i], ay[i])、长宽各为

1000的矩形(lx[i], ly[i], hx[i], hy[i]);

6.Swhole= 1000000;

7.计算该矩形内障碍空间的面积Sobstacle;

9.改变矩形或增加长和宽;

10. 重新计算Swhole；

11.return满足阀值的lx[i],ly[i],hx[i],hy[i];

2.2过滤阶段

LSP接到GNN查询请求后，执行RGNN查询。由于用户的位置是一个区域，数据点与查询用户间的距离是一个范围而不是一个固定值，许多数据点都可能成为最终的结果。过滤阶段的目的就是如何快速得到RGNN定义中的候选集合Scnd，使得Scnd中的对象都是可能成为最终GNN结果的点，而所有可能成为GNN结果的点也一定在Scnd中。本文改进传统最佳优先BF(Best-First)[11]查找算法，提出了MBF(ModifiedBest-First)算法来执行RGNN查询。

MBF算法与BF算法的执行过程类似，但由于MBF处理的是多个区域(矩形)，元素到多个矩形的距离之和是一个范围，因此查找过程以及算法结束条件更加复杂。算法的思想就是按照ds值由小到大来处理R*树中的结点，直到找到某结点。若其ds值大于当前所处理过的结点中最小的dl值，剩下结点中的数据点就可以被过滤掉。具体见算法2。

算法2过滤算法MBF (Modified Best-First)

输入：N个用户的位置区域(*lx,*ly,*hx,*hy),R*树;

输出：可能成为结果的候选集合Scnd;

1.Scnd初始化为空;

2.优先队列PQ初始化为R*树的根结点root;

3.全局变量minmaxdist= root.dl;

4.while (PQ不为空) do

5.从PQ中取一个结点pc;

6.if (pc.ds>minmaxdist) returnScnd;

7.minmaxdist= min{minmaxdist,pc.dl};

8.if (pc是中间结点)

9.计算每个孩子的ds值并按升序插到PQ中;

10.else

11.将pc插入到集合Scnd中;

12.returnScnd;

初始时把根结点(root)放入优先队列PQ中，优先队列中的元素(中间结点MBR或者是叶子结点存储的数据点)按照其ds进行升序排列。算法不断地从队列中取出有最小ds的元素进行处理。记录和更新全局变量minmaxdist使它始终是所有被处理过的数据点的dl的最小值(行3和7)。这样，当从优先队列中取出的元素pc的ds大于minmaxdist时，pc以及优先队列中的其他元素就可被剪枝掉(行6)，在pc之前被处理的数据点则被放入候选集合中(行11)。下面给出MBF算法的正确性证明。

定理1假设minmaxdist是某数据点p到各查询矩形最大距离之和，pc是从当前从优先队列中取出的元素，若ds(pc)>minmaxdist，则pc以及优先队列中的剩余元素不可能是最终的GNN查询结果。

证明：反证法。假设最终的GNN结果是pc或优先队列中剩余元素中的其中一个，记作pr。根据RGNN的定义可知，无论发出查询的n个用户处在查询矩形的哪个位置，pr到这n个用户的距离之和都要小于其他数据点。根据已知条件pc.ds>minmaxdist，且优先队列是按照各元素的ds值进行升序排列，因此pr.ds>pc.ds>minmaxdist。也就是说，无论发出查询的n个用户处在查询矩形的哪个位置，p到这n个用户的距离之和都要小于pr。与假设相矛盾，定理成立，证毕。

2.3求精阶段

求精阶段是保护用户与LSP之间以及用户彼此间隐私的关键，该阶段的目的是在不泄露用户隐私的前提下，对Scnd中的数据点进行求精计算，进而得到最终正确的GNN结果。

假设发出GNN查询的用户有4个，过滤阶段得到的候选集中有5个数据点。用户与各数据点间的距离如表1所示。为保护用户与LSP间的隐私，用户不会把位置信息发送给LSP，而是通过用户间的交互，把最终的距离和发送给LSP。如表2所示，u1把其到p1的距离2发送给u2，u2再用其到p1的距离更新当前和，即得到11，并发送给u3。最后，u4计算出全部和24，发送给LSP。以此类推，计算出所有点的距离和，和最小的点就是最终结果，即p4。

表1　用户与Scnd中各数据点的精确距离

表2　用户更新与Scnd中各数据点的距离和

以上方法在用户之间进行距离传递时，可能会在彼此间泄露隐私。例如u1总是把自己到其他数据点的距离传递给u2，u2就可以根据u1到任意两个数据点的距离来得到u1的精确位置。为了保护用户间的隐私，SFR在更新距离和时，对Scnd中不同的数据点，用户的交互(更新)顺序随机产生。当GNN查询只有2个用户时，先更新距离的第一个用户会把自己的位置信息暴露给第二个用户。这种情况下，协调者需要充当第三个用户参与交互。由于用户只向协调者发送QID以及更新后的距离信息，并不会暴露自己的ID和位置信息，从而保护了用户的隐私。

此外，为了提高计算效率，本文还提出了剪枝算法来优化求精过程。SFR用一个全局变量SUM记录当前已计算的距离和的最小值用来剪枝。若某用户更新后的距离和大于SUM，则该数据点就可被剪枝掉，无需再计算其他用户到该点的距离，从而减少了计算代价。具体算法见算法3。

算法3优化求精算法

输入：用户个数N, 候选集合Scnd以及候选对象个数M;

输出：查询结果rst;

1.全局变量SUM= ∞; *sum=0;

2.for (i= 1 toM)

3.随机产生用户的一个更新顺序list;

4.for (j= 1 toN)

5.计算用户list[j]到对象Scnd[i]的距离dist；

6.sum[i] =sum[i] +dist;

7.if (sum[i] >SUM)

8.break;

9.if (j==N&&sum[i]

10.SUM=sum[i];

11.rst=Scnd[i];

12.returnrst;

根据算法3，表3给出了优化后的求精算法的一个测试用例。根据表1中用户与数据点的实际距离可知，p2经过各用户的更新，所得到的SUM值13是当前最小的距离和(行9-11)。对于p3，在u4更新完距离和后，当前距离和16大于13，因此p3可直接被剪枝，u1到p3的距离无需计算(行7-8)。同理，计算p5时，也减少了两个用户的距离计算。最终的结果rst就是p4。

表3优化后的求精过程

3实验结果

为验证本文所提算法SFR的有效性，本节在真实城市路网上生成数据集对算法SFR以及文献[9]所提的算法IPPF从查询效率和受攻击率两个角度进行了对比实验。两个算法的区别之一是SFR在生成安全区域时考虑了地图匹配攻击，产生的区域可能比算法IPPF要大，但可以减少受攻击的次数。区别之二是在用户更新时，SFR考虑了用户间的隐私泄露问题，并提出了优化的求精算法。

3.1实验环境

本文使用Oldenburg(德国城市)真实的道路网络，并基于该路网定义了一些障碍空间(每10条街道产生一个100×100的障碍区域)以及一些包含语义信息的点(每条街道平均产生五个语义点，代表超市、餐厅、商场、医院等)。假设攻击者了解地图的这些信息，当用户发出一个矩形区域时，攻击者先根据地图信息去掉该矩形区域内的障碍空间，再从剩余区域内随机选择一个语义点作为攻击，如果与该用户的实际位置一致，则认为用户隐私泄露。

查询算法的响应时间是衡量算法性能最重要的标准之一。当被查询数据点的个数、发出查询的用户个数以及用户发送给LSP的位置区域面积这三个因素的规模增大时，算法响应时间的增加速度能够反映算法的可扩展性。因此，本文实验中分别考察了这三个因素对查询算法响应时间的影响，从而验证算法的可扩展性。对于隐私保护下的查询算法来说，除了算法的响应时间，其受攻击率是另外一个重要的衡量标准。显然，用户发送给LSP的位置区域面积与受攻击率之间的关系较为密切，因此，本文在实验中还考察了该因素对查询算法受攻击率的影响。其中数据点个数从5000增加到20 000，20 000是默认值。用户个数从4到1024以4的倍数增长，默认值是64。位置区域大小则从2002增加到10002，默认值是6002。在研究一种参数对算法效率的影响时，其他参数设置为默认值。每组实验中，执行100次GNN查询，再取平均值用来分析。

本文所有算法都使用标准C++在Windows 7操作系统下实现，电脑配置为：Intel Core2 CPU, 2.20 GHz,2 GB内存，500 GB硬盘。

3.2结果分析

图2列出了被查询的数据点个数对SFR和IPPF算法响应时间的影响。可以看出，随着数据点个数的增加，两个算法的响应时间都有所增加。这是因为被查询点越多，需要进行的距离计算越多。另外，可能成为用户组最近邻结果的对象数目也会增加，从而导致过滤阶段得到的候选结果增多，求精阶段用户所需要更新的距离也随之增加。从图中还可以看出，SFR查询效率略微高于IPPF。这是由于SFR算法在求精阶段利用保存的全局变量对候选结果进行剪枝，减少了用户到候选结果之间距离的计算代价，从而提高了整体的查询效率。

图2　数据点个数对算法响应时间的影响

图3给出了两种算法响应时间随着同一查询集合内用户个数增加的变化趋势。用户个数增多，所需的距离计算增多，用户与LSP交互过程中需要传输的数据也增多。另外传送给LSP的矩形增多，也会使可能成为组最近邻的候选对象增多，增加了后续剪枝和交互的计算代价，因此两个算法的响应时间都有所增加。与IPPF相比，SFR算法响应时间增加得比较缓慢，表现出了良好的扩展性。

图3　用户个数对算法响应时间的影响

图4和图5分别列出了用户向LSP发送的位置区域的大小对SFR和IPPF算法在查询响应时间和受攻击率两方面的影响。对于算法IPPF来说，横坐标的值就代表用户发出的位置区域的边长；而对SFR来说，由于考虑地图匹配攻击，算法会在默认区域的基础上，通过调整位置或大小来满足指定的障碍阈值δ，因此一般会比原区域略大一些。从图4可以看出，随着区域的增大，两种算法的响应时间都增加了。主要原因就是区域的增加使得LSP计算的可能成为组最近邻结果的对象变多，增加了求精阶段的计算代价。与IPPF相比，SFR查询时间的变化较小，这是因为SFR在位置区域默认较小时，考虑到地图匹配攻击，也会将大的区域发送给LSP，因此响应时间变化不明显。

从图5可以看出，区域的增大，使得IPPF的受攻击率有所下降。这是因为区域增大，攻击者能够猜到用户真实位置的概率会下降，因此受到攻击的次数变少。而对SFR来说，受攻击率并没有受区域大小的变化有太大的影响，始终都保持在一个较低的受攻击率，这是由于无论默认的区域是多大，SFR在发送阶段都考虑了可能遭受的地图匹配攻击，因此能够一直保持较高的隐私保护能力。

图4　位置区域大小对算法响应时间的影响

图5　位置区域大小对算法受攻击率的影响

4结语

本文基于无TTP模型，提出了隐私保护下的基于三阶段的GNN查询算法SFR。首先用户向LSP只发送能有效防御地图匹配攻击的位置区域来隐藏各自的真实位置信息；其次，基于这些位置区域，LSP利用剪枝策略过滤掉那些不可能成为查询结果的数据点，快速得到候选集合；最后通过用户之间的交互，从候选集中查找最终的结果，在交互过程中不仅充分考虑了用户间的隐私保护问题，还提出了剪枝算法来优化计算过程。基于真实城市路网下的实验结果表明，SFR与传统方法相比，有较高的查询效率和较低的受攻击率。

参考文献

[1] Deng K, Sadiq S, Zhou X F, et al. On group nearest neighbor query processing[J].IEEE Transactions on Knowledge and Data Engineering (TKDE), 2012,24(2):295-308.

[2] Chatzimlioudis G, Zeinalipour-Yazti D, Lee W Q, et al. Continuous all k-nearest-neighbor querying in smartphone networks[C]//Proceedings of the 13th International Conference on Mobile Data Management，MDM’12, 2012:79-88.

[3] Shin K G, Ju X, Chen Z, et al. Privacy protection for users of location-based services[J].Wireless Communications,2012,19(1): 30-39.

[4] 朱青, 赵桐, 王珊. 面向查询服务的数据隐私保护算法[J].计算机学报, 2010,33(8):1315-1323.

[5] 李玮, 杨庚. 保护隐私性与完整性的低能耗数据融合算法[J].计算机应用,2013,33(9):2505-2510, 2515.

[6] 崔丽群，张明杰.车载网络中隐私保护方法[J]. 计算机应用, 2013, 33(9):2516-2519, 2524.

[7] Wernke M, Skvortsov P, Durr F, et al. A classification of location privacy attacks and approaches[J].Personal and ubiquitous computing, 2014,18(1):163-175.

[8] Wernke M, Durr F, Rothermel K. PShare: Ensuring location privacy in non-trusted systems through multi-secret sharing[J]. Pervasive and Mobile Computing, 2013,9(3):339-352.

[9] Hashem T, Kulik L, Zhang R. Privacy preserving group nearest neighbor queries[C]//In EDBT, 2010:489-500.

[10] Vu K, Zheng R, Gao J. Efficient algorithms for k-anonymous location privacy in participatory sensing[C]//Proceedings of the 2012 International Conference on INFOCOM, 2012:2399-2407.

[11] Hjaltason G R, Samet H. Distance browsing in spatial databases[J].Acm Transactions on Database System,1999,24(2):265-318.

[12] Beckmann N, Kriegel H P, Schneider R, et al. The R*tree: an efficient and robust access method for points and rectangles[J].Acm Sigmod Record,1990,19(2):322-331.

ON GROUP NEAREST NEIGHBOUR QUERY ALGORITHM FOR PRIVACY-PRESERVING

Liu XiaoleLi Bo

(SchoolofComputer,HenanInstituteofEngineering,Zhengzhou451191,Henan,China)

AbstractExisting private-preserving algorithm for group nearest neighbour (GNN) query ignores map matching attacks. To avoid this problem, we proposed a GNN algorithm for preserving the privacy of users location, which is based on three phases of send-filter-refine (SFR), in the model of no-trusted third party. In sending phase, users send the rectangular regions capable of defending map matching attacks instead of accurate locations to location service provider (LSP). In filtering phase, LSP utilises these regions to calculate all the points possibly being the GNN results and returns them to users. And in refining phase, in order to prevent revealing the privacies among those users initiating queries, the final query result is obtained by unordered interactions between users, and we proposed a couple of pruning strategies to speed up the query. Result of the experiment based on real road network showed that SFR had higher query efficiency and lower rate of being attacked than the traditional algorithm.

KeywordsGroup nearest neighbourPrivacy-preservingLocation service provider

收稿日期：2014-09-02。国家自然科学基金项目(61301232)；河南省科技厅基础与前沿技术研究计划项目(142300410131)。刘晓乐，讲师，主研领域：计算机应用，网络信息安全。李博，讲师。

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.075