连续不确定协作用户的隐私保护方法

林玉香，王慧婷

LIN Yuxiang1,WANG Huiting2

1.南阳理工学院 软件学院，河南 南阳 473000

2.北京邮电大学 科学技术发展研究院，北京 100876

1.School of Software,Nanyang Institute of Technology,Nanyang,Henan 473000,China

2.Institute of Science and Technology Development,Beijing University of Posts and Telecommunications,Beijing 100876,China

1 引言

当前，智能手机的普及为基于位置服务技术的发展提供了便利，这种通过提交当前或连续位置，并获取查询、导航以及广告推送等便捷服务的技术深受人们喜爱。然而，人们在享受这种服务所带来的便利同时，又不可避免地要面对个人隐私泄露的问题。攻击者或不可信的位置服务提供商，可利用申请者提交的位置推测出申请者的行为特征，进而可能会造成现实生活中的麻烦甚至是人身伤害。

针对使用基于位置服务可能会泄露申请者个人隐私的问题，研究者提出了大量的隐私保护方法。这些方法可按照提供隐私保护服务的系统结构分为：集中式结构和分布式结构两类。其中，集中式结构一般假设存在一个可信的第三方服务台提供隐私保护计算处理，申请者只需将自身查询发送给该可信第三方，并由其返回查询结果。但是，人们认为这种集中式结构存在一些不足：一方面，所有申请者的个人隐私信息全部由中心服务器处理，这使得申请者的个人隐私全部保存在中心服务器中，因此中心服务器变成了攻击者攻击的焦点，一旦中心服务器出现隐私泄露情况，将造成严重的隐私泄露问题；另一方面，中心服务器需要对每一个申请者按照其所设定的要求进行隐私保护，当提出隐私服务申请的申请者数量较多时，势必会造成服务器负载过大，严重时将会降低服务处理速度，影响基于位置服务的服务质量，成为服务瓶颈。基于这两方面不足，研究者提出了基于用户移动设备的分布式系统结构。

分布式系统结构不再使用第三方提供隐私保护，而是移动用户通过彼此之间的短距离通信设备，相互协作、相互依托，以此建立彼此之间的隐私保护结构，实现不同用户的隐私保护。相对于集中式结构，分布式结构具有不依赖可信第三方，部署简单方便，可平衡隐私保护与服务质量等特点。但是，当前已有的该结构下的隐私保护方法一般基于快照服务，即对于单次查询申请的申请者具有较好的隐私保护效力。当申请者提出连续基于位置查询时，由于每次参与协作的用户彼此之间存在差异，攻击者可根据用户差异剔除参与协作的用户，进而识别出申请者，获得该用户的服务申请位置甚至连续位置轨迹，最终获得申请者的个人隐私。针对这一问题，本文提出了一种连续的不确定协作用户隐私保护方法（A continuous uncertain collaborative users privacy protection algorithm，CUPPA），使申请者可获得多跳连续移动范围内的查询结果，在满足连续基于位置查询服务请求的同时实现对申请者个人连续位置的隐私保护。

本文的主要贡献可概括如下：

提出了一种连续不确定协作用户寻找方法，解决了分布式隐私保护系统结构下，连续基于位置服务隐私保护能力不足的问题，既保障了服务质量又提供了较好的隐私保护效力。

利用信息熵作为度量标准，较好地量化了基于分布式隐私保护系统结构的隐私保护能力，更进一步证明了所提出方法的隐私保护效力。

实验验证所产生的结果进一步验证了所提出方法的隐私保护能力以及在现实环境下算法运行时的执行效率。

2 相关工作

为了保护用户在使用基于位置服务时的个人隐私，早在2003年Gruteser等人[1]就提出了基于k-匿名的位置隐私保护方法，并借助中心服务器完成了对快照服务下的位置隐私保护。之后为完善这种方案，陆续提出了语义多样性p-sentivity[2]以及查询多样性l-diversity[3]的隐私保护方法。出于对集中式结构中心服务器不足之处的考虑，Ghinita等人[4]通过用户移动设备，基于可计算PIR方法提出了一种零信息泄露的隐私信息检索方案。Chow等[5]则针对PIR方案计算量较大以及需要LBS服务器进行检索方式更改的问题，提出了一种基于用户协作，通过点对点通信建立匿名组的隐私保护方法。

随着基于位置服务逐渐从快照查询变换为连续基于位置查询，基于快照查询所制定的隐私保护方法大多很难适应。因此，基于中心服务器，Hwang等[6]提出了利用历史信息，提供位置及轨迹匿名的连续位置隐私保护方法。Zhang等[7]则根据用户连续位置表现出的属性信息可关联成轨迹的问题，提出了相似属性寻找的隐私保护方法。同样出于对集中式结构的不信任，Schlegel等[8]利用加密方法实现协作用户与不可信中心服务器之间的信息检索与交换。Gao等[9]假设所有协作用户具有相同的移动方向，实现用户的轨迹匿名。

但是已有的隐私保护方法尚未能有效地解决攻击者通过识别匿名用户，进而降低申请者隐私保护级别的攻击方法。这种攻击方法使得当前已有的集中式和分布式隐私保护方法都无法实现全面的用户隐私保护，尤其在申请者申请连续基于位置服务的查询时。针对这一问题，基于保障基于位置服务效率和提供有效隐私保护能力的考虑，本文基于用户协作的隐私保护方法，针对这种方法在连续位置隐私保护方面的不足，提出了CUPPA算法，并通过安全性分析与实验验证证明了所提出算法的优越性。

图1 连续协作匿名示意图

3 预备知识

3.1 攻击模式

利用分布式系统架构进行连续基于位置服务的隐私保护可得到如图1所说的连续泛化集合。在该图中可以看到，申请者A申请四次连续基于位置查询服务，每次查询都找到其他3个协作用户参与匿名，以期将自己位置泛化。然后，由于在连续基于位置查询的移动过程中，协作用户很难在每次查询申请时都在申请者A的周围，因此建立的匿名组中包含的协作用户存在一定的变化。这使得攻击者能够获得如图1所示的连续位置泛化结果。通过该结果，攻击者可对提出连续服务的用户进行筛选，由于B、C、D、E、F等用户均未能包含在每次位置泛化的匿名集合中，使得攻击者可将申请者A四次查询的位置进行关联，在获得A的位置轨迹隐私的情况下，更可获得每次查询的具体位置，进而可推测分析出A潜在的个人隐私。

本文假设攻击者为不可信的LBS服务器，由于该服务器可获得申请者提供的所有位置信息以便获取服务结果，这使得该服务器可获得最大的申请者信息量，一旦被商业利益所诱惑或者被其他攻击者攻破，便可转换为具备最大背景知识的攻击者。

3.2 隐私保护基本思想

为防止申请者在使用分布式系统架构进行隐私保护时，攻击者可利用匿名用户的差异识别申请者，最好的方法是所有协作用户都具有与申请者相同的移动方向，能够在整个连续基于位置查询的过程中参与每次快照查询匿名。然而，这显然在现实中是不可能实现的，所有参与匿名的协作用户其移动方向和移动速度显然与申请者不同，这就必然导致每次快照查询参与的匿名用户存在差异。针对这个问题，本文利用协作用户位置获取查询结果的方法，通过选择在连续移动范围内协作用户的位置，获取基于这些位置的查询结果。在移动到这些区域所处的位置时，不在重复连续的基于位置查询申请，而是使用协作用户已获得并保存的查询结果，降低与LBS服务器之间的信息交互。同时，利用首次查询存在的大量匿名用户泛化真实位置，进而实现在连续基于位置查询服务下申请者的位置隐私保护。

4 CUPPA算法

CUPPA算法需要保障在连续基于位置服务过程中，每个协作用户位于申请查询所处的位置区域，以此获得连续基于位置查询所需要的结果。基于这一目的，本文将申请者所在区域划分为网格，连续移动所经过的区域可表示为当前网格范围内的一组连续单元格。但是，连续的规则单元格又可能会泄露申请者所经过的位置区域，使得攻击者可利用轨迹校正的方法获得申请者轨迹。为保护申请者的位置隐私，这种连续的单元格又需要进行不确定扩张处理。这使得CUPPA算法需要包含单元格不确定性扩张和协作用户寻找两部分。

4.1 单元格不确定性扩张

单元格不确定性扩张主要是为了解决在当前范围内寻找足够的连续位置的协作用户，同时防止协作用户位于规则的连续单元格内，造成攻击者通过轨迹校正获取申请者真实轨迹的问题。其扩张过程可概括为：为每一个潜在位置进行满足k-匿名的单元格扩张。例如：假设申请者制定如图2（a）所示的当前位置网格，其连续基于位置查询所经过的网格如箭头所示。当申请者需要获取满足4-匿名要求下的连续位置隐私保护时，申请者首先基于起始位置(xu,yu)沿着随机方向寻找下一单元格，同时基于下一单元格再次沿着随机方向寻找单元格，直到满足4个单元格为止。完成后可得到如图2（b）阴影部分所示的匿名单元格。在此之后，以每一个连续基于位置查询所处的位置单元格为起点，重复以上随机查找，可得到如图2（c）阴影部分所示的不确定扩张后的选定单元格集合。

经过不确定性扩张获得选定单元格之后，申请者需要在选定的单元格中寻找协作用户，并通过协作用户完成隐私保护。

4.2 协作用户寻找

基于分布式系统架构的隐私保护方法需要寻找足够的协作用户来完成隐私保护，而申请者移动设备的短距离通信功能很难满足在连续的位置范围内寻找到足够的协作用户。因此，本文所提出的CUPPA使用了一种协作用户传递的方法来寻找连续服务位置单元格上的协作用户。这种寻找方法的处理过程为：在一跳通信范围内，申请者首先根据不确定性扩张建立的匿名单元格，选择向当前位置所在单元格发送协作请求；当协作用户收到请求时，首先确定是否参与协作，若是则根据自身位置向LBS服务器发起针对当前单元格与发起者相同的兴趣点查询申请，同时在发起者提供的单元格集合中选择最近单元格发送协作请求，否则发送不参与协作标识，由发起者重新发起协作请求。若用来连续移动所在单元格内无协作用户参与，则算法执行失败，若在匿名单元格内无协作用户，可重新设定匿名单元格，并在重新设定的单元格内寻找协作用户。算法1详细表述了协作用户处理隐私保护申请所进行的信息处理流程。

图2 单元格不确定性扩张

算法1协作用户处理隐私保护申请

输入：收到的信息。

1.协作用户收到协作申请信息E；

2.if该用户不参与协作

3.将信息E返回；

4.else

5.将信息E发送给周围的其他用户；

6.将查询信息发送给LBS服务器；

7.保存从LBS服务器返回的查询结果；

8.在其他用户经过时使用保存的结果提供服务；

9.end

输出：查询结果。

经过单元格不确定性扩张与协作用户寻找，发起者可以在连续基于位置查询的过程中，从协作用户保存的查询结果中获取所需的内容，在整个过程中发起者与LBS服务器之间不存在任何的信息交互，整个查询结果均由协作用户获得并提供给查询发起者，这使得查询发起者能够最大限度地保护自己的位置隐私。

4.3 安全性分析

CUPPA算法的安全性可以从攻击者猜测真实连续位置轨迹和申请者某一时刻所处位置两个方面加以考虑。在连续基于位置服务的过程中，申请者会产生一个基于每个查询位置的位置轨迹，在这个轨迹中包含大量的时空关联信息，这些信息有助于攻击者获取申请者个人隐私。在本文所提出的方法中，经过不确定性单元格扩张，申请者的连续位置被扩张后的单元格所模糊，这使得攻击者即使获得申请者连续基于位置查询的次数也很难在当前单元格集合中确定申请者的单元格轨迹。另外，由于申请者是在协作用户处获取查询结果，整个基于位置的连续基于位置查询过程中，申请者与LBS服务器之间不存在信息交互，这更增加了攻击难度。假设申请者进行连续n次查询，则按照CUPPA算法的不确定单元格扩张规则，在最好的情况下可产生n×k个连续单元格；在最坏的情况下可产生n个单元格，但是这种情况是不会出现的，因为申请者可放弃当前扩张结果，重新进行一次新的扩张计算获得满足要求的泛化单元格集合。因此，产生的平均单元格数量可由申请者设定为n×k/2到n×k之间，也就是经过不规则性扩张可产生至少n×k!/2个连续的单元格组合。因此，攻击者很难通过扩张后的不确定单元格集合判断得出申请者的真实轨迹。

对于申请者某一时刻所处位置的安全性：首先CUPPA算法仅由协作用户与LBS服务器进行一次基于位置查询的服务申请，且提供一个位置单元格集合，因此不存在LBS服务器获得申请者连续基于位置查询时间的可能；其次，申请者连续基于位置查询过程中的查询结果均从参与协作的协作用户处获得，这使得申请者与LBS服务器之间不存在任何信息交互，更让LBS服务无法或者其在某一时刻所处的位置；最后，由于申请者获取的是一个位置单元格集合，这使得LBS即使想要获得最初的申请者位置，都需要在至少n×k/2个位置单元格中准确猜测出真实位置，其猜测的成功率为2/n×k，显然很难获得申请者在初始时刻的真实位置。由此，可认为申请者在申请连续基于位置服务的过程中，攻击者很难获得该用户的真实位置以及位置轨迹，CUPPA算法可有效地保护申请者的位置隐私。

5 实验验证

为验证本文所提出的CUPPA算法在隐私保护能力和算法执行效率方面的优势，本文采用BerlinMOD Data Set提供的真实位置数据为基础，在该数据集上通过用户位置所占用的空间面积实现不确定性的位置区域扩张。实验与同样基于用户协作的随机行走方法R-cloak[10]、查询信息传递方法QFPIR[11]和信息分块传递算法random-QBE[12]比较快照服务下的隐私保护能力，与基于用户cache的连续隐私保护方法MobiCrowd[13]、假设所有用户行进方向相同的LTPPM[9]和基于轮廓泛化的IRDA[7]算法比较连续基于位置查询服务下的隐私保护能力。最后，通过算法执行时间和隐私保护成功率来验证算法的执行效率。

5.1 验证标准

对于本文所提出算法的优越性，可以从隐私保护能力和算法执行效率两个方面加以验证。其中，算法隐私保护能力通过快照查询下的位置信息熵以及连续基于位置查询下的连续两个位置的成对熵均方差加以度量；算法的执行效率从算法运行时间和隐私保护成功率两方面加以验证。

通常情况下，攻击者对当前快照查询下申请者的位置猜测的不确定性可用信息熵来表示，设攻击者成功猜测的概率为 p(i)，则位置信息熵可表示为：

式中，H(i)取值越大表示当前攻击者的不确定性越高，则攻击者更难在当前的位置集合中准确识别申请者的真实位置。

在进行连续基于位置查询时，利用每两次快照查询位置的成对熵之和可计算整个连续基于位置查询过程中的平均信息熵，设连续基于位置查询的次数为n，则平均信息熵可表示为：

根据平均信息熵，可以很容易地计算得出成对熵均方差，由此可得到成对熵均方差的表示公式：

显然，由于在不同快照查询下的不同位置熵的不确定性，使得σ2的取值越小，表明当前的隐私保护级别越高。

算法的执行时间是主要指协作用户或中心服务器处理申请者信息并完成隐私保护所需要的平均时间，对于n次连续基于位置查询的执行时间可表示为：

隐私保护成功率是指在实现连续位置查询服务的过程中，申请者成功实现隐私保护的概率，表现为连续基于位置查询中的每次查询都可成功实现隐私保护。若n次查询中有一次未能完成隐私保护，则隐私保护失败。该成功率受协作用户是否参与隐私保护影响较大，当协作用户未参与匿名时，隐私保护成功率较低。设当前申请隐私保护的用户数为U，成功完成隐私保护的用户数为Us，由此可得到连续基于位置查询下的隐私保护成功率：

根据以上实验验证标准对参与比较的算法进行实验验证可得到如下实验结果。

5.2 实验结果

快照查询下的位置信息熵主要表现攻击者对申请者真实位置猜测的准确程度，当前存在的几种主流方法均能有效地泛化攻击者获得申请者的真实位置，取得申请者设定匿名值所能得到的最大熵。从图3中可以看到，CUPPA算法与其他主流方法R-cloak、QFPIR、random-QBE等方法相似，都能在快照查询的情况下取得当前申请者位置经过泛化后的最大熵值。因此，可以说在针对快照查询情况下的用户位置，CUPPA算法能够提供最好的隐私保护效果。

图3 快照查询下的位置信息熵取值

在图4（a）中，可以看到除CUPPA算法外，其他的基于快照查询产生的隐私保护算法都可在两个位置成对熵的均方差上获得取值，这说明以上方法可能会通过当前位置与其他连续的经过隐私保护后的位置之间产生一定的关联关系，能够通过当前位置与其他位置相关联，进而识别潜在的匿名位置，识别出申请者的真实位置。所以，这些方法在连续基于位置服务的情况下是很难保护申请者的位置隐私的。在图4（b）中，可以看到MobiCrowd以及LTPPM两种算法也存在潜在的可关联情况，这是由于MobiCrowd在周围协作用户不具备申请者所需要的查询结果的情况下，申请者需要向LBS服务器直接提交查询以便获得服务器结果，这使得攻击者能够较为轻易地获得当前位置，进而关联位置集合并通过轨迹校正[14]的方式获得申请者的轨迹隐私。而LTPPM算法由于假设所有协作用户均具有与申请者相同的移动方向，但是移动速度是存在变化的，仍可能造成部分位置之间匿名协作用户之间的差异，进而使得攻击者可通过这种差异识别申请者真实位置的情况。最后，CUPPA算法和IRDA算法一个从协作用户处获得整个连续基于位置查询过程中的所有查询结果，另一个通过可信第三方泛化了所有可能产生关联的用户属性轮廓信息，使得攻击者很难进行位置关联，因此能够在连续的基于位置查询服务中取得较小的σ2取值，即申请者的个人隐私能够获得比其他两种主流隐私保护方法更好的隐私保护效果。

图4 不同隐私保护方法产生成对熵均方差

从图5中可以看到不同的针对连续基于位置查询的隐私保护方法的运行时间。从该图中可以看到IRDA方法所需的执行时间最高，这是由于该方法需要可信第三方计算所有参与匿名用户的可能产生关联的属性轮廓信息，并找到与申请者最为相似的匿名用户参与匿名，中心服务器的计算负载较大，因此其执行时间最长。其次，MobiCrowd方法的运行时间也相对较高，这是由于申请者需要在周围的协作用户中寻找能够提供当前所需要查询内容结果的协作用户，其时间消耗主要用于对这样协作用户的寻找上，同时由于申请者短距离通信范围的限定，使得这种方法可能需要更多的移动时间去需要合适的协作用户。再次，LTPPM与MobiCrowd方法运行时间较长的原因相似，这种方法需要找到与申请者具有相同移动方向的协作用户，虽然这种协作用户在数量上要高于具有相同查询结果的协作用户，但同样需要较长的算法运行时间来完成。最后，CUPPA算法的执行时间要低于其他算法，这是因为该算法首先无需在连续基于位置查询的每次快照查询中逐次寻找协作用户，其次该算法能够保障协作用户保存有申请者所需的查询结果，最后该算法因为申请者不存在与LBS服务器之间的信息交互，整个服务过程中无需考虑协作用户的属性信息关联问题，这使得在寻找协作用户所消耗的时间上远低于其他算法。

图5 不同连续隐私保护方法的平均运行时间

从图6中可以看到各种算法在提供连续隐私保护时的算法隐私保护成功率。在该图中，LTPPM算法的隐私保护成功率要低于其他几种算法，这是由于该算法首先很难找到具有相同移动方向的协作用户，同时又由于协作用户移动速度差异造成部分协作用户无法参与到当前匿名中。MobiCrowd算法的隐私保护成功率稍好，这主要是因为该算法只需找到能够提供查询结果的协作用户，不需要寻找至少k个协作用户参与匿名，其协作用户查找数量不受限制，因此其隐私保护成功率稍高。IRDA由于利用可信第三方进行匿名用户的选择，提高了查找匿名用户的能力与查找范围，使得其隐私保护的成功率要高于其他两种算法。最后，CUPPA算法可通过协作用户传递的方式实现多跳短距离通信范围内的协作用户查找，同时该算法只需在连续基于位置查询中进行一次查询即可获得连续基于位置查询结果，提高了查询结果的利用率，因此其隐私保护的成功率最高。

图6 不同连续隐私保护方法的隐私保护成功率

综上所述，可以看出本文所提出的CUPPA算法既可保障在快照服务下的用户位置隐私，又可保障在连续基于位置查询下的用户位置以及位置轨迹隐私。同时该算法在算法执行时间和隐私保护成功率上又好于其他算法。因此可认为该算法相比于其他算法具有更大的优势。

6 结论

本文针对现有的基于用户协作的隐私保护方法在连续基于位置查询隐私保护方面的不足，提出了一种连续不确定协作用户寻找方法CUPPA。该方法通过单元格不确定性扩张和协作用户寻找，实现了基于协作用户的连续基于位置查询下的位置隐私保护。最后通过安全性分析和实验验证进一步证明了所提出的CUPPA算法的隐私保护能力和算法的执行效率，较好地解决了隐私保护和基于位置服务之间的平衡问题。但是，由于申请者不再提交自身的真实位置，使得由LBS服务器反馈回来的基于位置服务结果与申请者真实位置之间存在偏差，进而造成服务反馈后的结果稍低于真实位置反馈回的结果，今后的工作将在如何提高反馈结果的精确度方面展开。

参考文献：

[1]Gruteser M，Grunwald D.Anonymous usage of locationbased services through spatial and temporal cloaking[C]//Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，San Francisco，California，2003：31-42.

[2]Xiao Z，Xu J，Meng X.p-Sensitivity：A semantic privacyprotection model for location-based services[C]//Proceedings of the International Conference on Mobile Data Management Workshops，2008：47-54.

[3]Fuyu L，Hua K A，Ying C.Query l-diversity in locationbased services[C]//Proceedings of the Tenth International Conference on Mobile Data Management：Systems，Services and Middleware（MDM’09），2009：436-442.

[4]Ghinita G，Kalnis P，Khoshgozaran A，et al.Private queries in location based services：Anonymizers are not necessary[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，Vancouver，Canada，2008：121-132.

[5]Chow C Y，Mokbel M F，Liu X.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems，Arlington，Virginia，USA，2006：171-178.

[6]Hwang R H，Hsueh Y L，Chung H W.A novel timeobfuscated algorithm for trajectory privacy protection[J].IEEE Transactions on Services Computing，2014，7（2）：126-139.

[7]Zhang Lei，Ma Chunguang，Yang Songtao，et al.Location privacy protection model and algorithm based on profiles generalization[J].Systems Engineering and Electronics，2016，38（12）：2894-2900.

[8]Schlegel R，Chow C Y，Huang Q，et al.User-defined privacy grid system for continuous location-based services[J].IEEE Transactions on Mobile Computing，2015，14（10）：2158-2172.

[9]Gao S，Ma J F，Shi W S，et al.LTPPM：A location and trajectory privacy protection mechanism in participatory sensing[J].Wireless Communications&Mobile Computing，2015，15（1）：155-169.

[10]Niu B，Zhu X Y，Li Q H，et al.A novel attack to spatial cloaking schemes in location-based services[J].Future Generation Computer Systems，2015，49：125-132.

[11]Rebollo-Monedero D，Forne J，Solanas A，et al.Private location-based information retrieval through user collaboration[J].Computer Communications，2010，33（6）：762-774.

[12]Ma C，Zhang L，Yang S，et al.Achieve personalized anonymity through query blocks exchanging[J].China Communications，2016，13（11）：106-118.

[13]Shokri R，Theodorakopoulos G，Papadimitratos P，et al.Hiding in the mobile crowd：Location privacy through collaboration[J].IEEE Transactions on Dependable and Secure Computing，2014，11（3）：266-279.

[14]Su H，Zheng K，Wang H，et al.Calibrating trajectory data for similarity-based analysis[C]//Proceedings of the Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data，2013：833-844.