移动互联网服务的隐私保护机制

李晖　牛犇　李维皓

摘要：探讨了考虑背景信息的位置和查询隐私保护方案，如基于背景信息的虚假位置k-匿名方案、同时保护位置和兴趣的隐私保护方案、基于交互的隐私保护方案，还探讨了基于用户隐私链拆分的实名认证和身份隐私保护策略；认为在避免可信第三方参与，敌手能够获取到背景信息的前提下，能够实现对用户身份、位置和查询隐私的保护，达到信任机制和隐私保护的有机结合将是未来隐私保护发展的趋势。

关键词： 移动互联网；身份隐私；位置隐私；查询隐私

1 移动互联网面临隐私

保护威胁

移动互联网服务的广泛普及、大数据技术的普遍应用在为人们带来便利的同时，也对用户隐私保护带来了巨大的挑战。众多的移动互联网服务大量采用用户名-口令认证机制，为记忆方便，用户普遍对不同的应用采用相同的用户名和口令，使得一旦某个服务商数据库泄露就威胁到用户在其他服务商的信息。国家对移动互联网信息传播实名管控的需求与用户身份隐私形成矛盾，如何提高用户身份认证的安全等级，免除用户记忆口令的负担，兼顾实名管控和用户身份隐私的保护成为移动互联网用户身份管理的主要挑战。

另一方面，微信、大众点评、百度地图等移动服务要求用户的位置信息和兴趣信息，不可信的服务对这些信息的滥用或者泄露对于用户权益带来极大的损害，在享受移动互联网服务方便性的同时，保护用户的身份、位置和兴趣的隐私成为移动互联网领域亟待解决的问题。

2 移动互联网位置和查询

隐私保护的主要方法

基于位置服务中常见的安全及隐私威胁主要包括5种攻击方式：单点攻击、基于上下文的攻击、多点攻击、多点配合上下文攻击以及直接攻击可信第三方。一般而言，这几种攻击方式要求攻击者的能力依次增强，要求攻击者能够获取越来越多的用户信息，从而更高概率地获取用户隐私信息。

对于攻击者而言，他们可以通过多种途径获取多种额外的信息，例如，用户密度信息，请求发送的概率分布，地图上兴趣点的分布情况等，这些可以统称为背景信息，此类信息一般为公开信息，可以通过互联网轻易获取，亦可通过攻击相关的可信第三方来获取。例如，Google Maps的服务器上保存着历史用户的各种查询记录，分布情况等重要信息，一旦该服务器被攻击，用户的所有信息将暴露于攻击者眼前。

各种基于位置服务中的服务提供商本身其实就是潜在的攻击者或者隐私信息的泄露者。层出不穷的泄密事件说明传统上认为是可信的服务提供商完全有可能被来自内部或者外部的攻击者攻陷，从而导致用户隐私信息的泄漏，因此，如何在服务提供商不可信的前提下保证用户隐私信息不被泄露就成为了一个很严峻的问题。

针对上述问题，来自全球工业界和学术界的科研人员已经提出了许多解决方案，这些方案可以根据不同标准分为不同的类别，以下介绍两种常见的分类方法：

（1）第一种分类主要根据用户对隐私信息的类型进行分类，可分为位置隐私、查询隐私。

其中位置隐私用以保护用户当前以及历史位置信息，使得攻击者难以获取用户位置相关的信息，从而难以实现对用户的追踪等。

查询隐私旨在保护用户所查询的内容，从而不泄露用户的个人喜好等信息。然而，用户的位置与所查询的内容并不完全独立，甚至在大多数情况下两者存在一定的关系，从而使得单纯保护某一种隐私的方案难以真正保护用户的隐私，故而也需要同时保护用户的位置隐私和查询隐私。

（2）第二种分类主要是为了实现不同场景下的隐私保护问题，现将当前主流的隐私保护方案分为5类：位置偏移、混淆技术、时间和空间隐匿、添加虚假信息以及其他方案。

（a）位置偏移

位置偏移示意如图1所示。黑色手机为真实用户，其请求服务半径为1英里，当他需要发送基于位置服务的服务请求时，用偏移后的位置取代其真实位置，然后构建新的服务请求信息并发送给服务运营商，从而达到保护其位置隐私的目的。此种方法算法复杂度很低，很容易在智能终端上实现，而且系统开销，尤其是通信开销基本上没有增加。然而由于所请求的服务数据和真实需要的服务数据之间存在一定的偏差，从而导致服务质量的降低。而且在此类方案中，服务质量的优劣和隐私保护效果的好坏成为了一对矛盾，服务质量越高，隐私效果越差，反之亦然。

（b）混淆

适用于位置隐私的保护和查询隐私的保护。对于位置混淆，用户可以通过对其查询半径进行模糊，例如，增大其查询半径或者刻意缩小其查询半径，甚至结合偏移的方案，通过位置偏移+查询半径变化的方案，使得攻击者更难推断其真实信息，如图2（a）所示；对于查询隐私混淆，将用户的兴趣集合进行划分，如图2（b）所示，当用户真实的查询请求为KFC的时候，为了对其查询信息进行混淆，可以用更大的一个集合“餐饮”代替，从而将自己的真实请求信息混淆于更大的集合之中，达到保护查询请求的目的。

此类解决方案的优点在于易于实现，由于只需要对相关参数进行修改，例如增大查询半径，所以很容易完成隐私保护。由于对查询半径的调整以及查询内容的混淆，会导致额外的系统开销，例如，用户需要获取一些不必要的服务信息，这样的操作也会引起服务质量的下降。

（c）时空隐匿

其核心思想在于收集/等候足够多的用户信息，通过统一提交请求，达到保护各个用户隐私信息的目的。真实用户将其请求发送至一个可信的第三方，该第三方同时收集周围其他用户的多个请求，如图3（a）收集多个用户的请求，然后将多个请求进行合并，一起发送给服务提供商，从而使得提供商难以获取各个用户的隐私信息。在图3（b）中，假设用户的真实请求发送于时间点t3，可信第三方出于时间隐匿的目的，等候一段时间以收集更多的请求信息。此处收集的信息可能来自多个用户，也可能来自该用户的多条请求信息，然后将多个请求一并发送给服务提供商，达到隐匿真实请求的目的。

一般情况下，此类方案可以达到较高的隐私保护级别，但具有较大的系统开销，以及较长的等待时延，最重要的问题在于对于可信第三方的依赖。

（d）虚假信息

包括基于虚假位置的位置隐私保护和基于虚假请求信息的查询隐私保护。其核心思想在于通过构造虚假的位置或者虚假的请求从而有效的实现k-匿名或者l-多样性的隐私保护级别。

如图4（a）所示，为了保护用户的真实位置，通过合理构造出若干个虚假的位置（例如k-1个），最终将这个k个位置构成的集合一并发送给服务提供商，其隐私保护的效果取决于攻击者是否能够有效从k个位置中区分出哪个是用户的真实位置。

类似的，图4（b）中给出了基于虚假查询请求的查询隐私保护策略，用户在向服务提供商发送请求之前，先构造若干个虚假的请求，一并发送给服务提供商，从而实现隐私保护。

在此类方案中，是否能够有效的构造虚假信息成为了隐私保护是否有效的关键，尤其是在面对拥有各种各样的背景信息的攻击者的时候，虚假信息可能会被有效过滤，从而难以达到用户期望的隐私保护效果。

基于虚假信息的隐私保护方案比较容易实现，也能够提供较高级别的隐私保护。由于需要引入额外的虚假信息，而额外的虚假位置或者虚假查询请求会带来相应的服务数据，所以随着虚假信息数目的增加，系统的性能会大幅度的降低。另外大多此类方案都没能同时保护用户的位置隐私和查询隐私，这也会使得整个系统的隐私保护效果会由于攻击者所拥有背景信息的数量增加而下降。

（e）其他

位置服务中还有其他相关的一些隐私保护方案，主要包括基于密码学工具的方案。通过对用户所上传的信息进行相关处理，例如加密等方法，借助于私人信息检索（PIR）等技术，从而使得用户在能够享受服务数据的同时又不将自己的查询请求泄露给服务提供商。当然，此类系统也可能借助于第三方的匿名服务器等，从而更高程度的保护用户隐私信息。

此类方案一般能够较高程度的为用户提供隐私保护效果。然而，由于匿名服务器（可信第三方的一种）的存在，使得整个系统难以承受单点失效攻击。此外，一些复杂的密码学运算仍然难以高效的应用在其上，这样会导致额外的计算负担，降低系统的可用性。

从移动用户的身份信息、位置信息以及兴趣信息三方面对隐私保护问题进行总结，分析了现有科研成果所采用的主流技术及相应的优、缺点，在此基础进行了分类。现有移动互联网中隐私保护方案分类如表1所示。

从表1提及的现有方案中可以看到，当前解决方案大都基于可信第三方，用户的身份认证一般由可信第三方或者服务提供商进行认证。CliqueCloak[1]和Casper[2]利用可信第三方实现匿名区域大小可调的k-anonymity。Footprint k-anonymity[3]利用移动用户的历史信息，通过在相遇用户之间构成一个虚拟的Mix-Zone来完成对用户兴趣信息和身份信息的混淆，从而实现k-anonymity。CacheCloak[4]引入了缓存和预测的概念，通过缓存的用户历史轨迹等信息，预测用户下一步的移动，为用户提供实时的服务。但是当用户身处全新环境时，该方案的预测准确性会大幅降低。Xu和Cai[5]提出了Feeling-based pyramid解决方案，该方案将地图进行划分，并根据用户的感兴趣程度赋予不同的权重，通过分析历史信息，用信息熵的概念实现P-popular trajectory（PPT）。该方案能够有效的保护用户的位置信息和兴趣信息，但其具有较高的计算资源消耗。Pan[6]等人提出了ICliqueCloak，虽然该方案可以在连续场景下同时保护用户的位置信息和兴趣信息，但同样的运算复杂度较高。

与此同时，有一些隐私保护技术并不依赖于第三方机构的技术（TTP），其基本思想主要集中于用户和其他用户之间交互信息，通过对等网络（P2P）或者基于相遇的解决方案实现匿名集的构造，从而保护用户隐私。Chow[7]等人提出了一种基于P2P的解决方案，通过用户的相互协作，用近距离通信标准（Wi-Fi或蓝牙技术）实现用户之间的信息交换，在考虑用户的最大移动距离基础上，实现连续场景下的k-anonymity，以保护用户的位置隐私。然而由于用户的移动模式和近距离通信的通信距离限制，使得真实用户的位置会以较大概率落在匿名集的中心区域。另外，用户仍需将自己的真实身份和兴趣信息发送给服务运营商，所以该方案难以同时保护用户的身份信息和兴趣信息。CAP[8]是一个基于四叉树和不同的网格步长的希尔伯特曲线型（VHC）的P2P解决方案，根据道路密度，CAP用一个大小可调的希尔伯特曲线对地图进行填充，用四叉树的存储结构，在有效实现k-anonymity的基础上大幅度降低系统的计算和存储开销。Pingley[9]等人提出了DUMMY-Q方案，通过在本地构建一个兴趣信息池，利用虚假兴趣信息选择算法高效的实现k-anonymity，从而有效抵御来自主动攻击者的推理攻击。但高额的兴趣信息池维护开销对手机用户而言难以负担。Shokri[10]等人提出了一种基于群组的用户隐私保护方案，当前用户通过将所需查询在群组内转发，由某一用户替代其向服务运营商发送服务请求，从而实现对当前用户身份信息，位置信息和兴趣信息的保护。但该方案的问题在于代替当前用户进行发送请求的用户没有足够的动力来进行此类操作，加之移动设备的资源受限性，该方案难以在移动互联网中广泛应用。

3 考虑背景信息的位置和

查询隐私保护方案

3.1 基于背景信息的虚假位置

k-匿名方案

通过巧妙的设计虚假位置生成算法，在充分考虑攻击者可能拥有的背景信息的基础上有效实现k-匿名。同时，此方案能够有效的提供较大的隐匿区域，而且可以避免真实用户落在所提交k个位置中处于最中间区域的问题。

基于背景信息的虚假位置k-匿名如图所示。将本地地图划分为若干个网格，不同的网格形状框代表了不同的历史请求概率，也就是用户历史上在该网格内发送基于位置服务请求的概率。蓝色小人儿代表真实用户，空心儿小人儿代表最后参与k-匿名的虚假用户位置。我们的思路包括两部分，第一部分见图5（a）、图5（b），其主要目的在于通过比对每个网格与当前用户所处网格的历史请求概率，旨在选择出一组潜在的网格去分配虚假用户，从而保证攻击者难以通过此类背景信息对最终提交的k个位置进行有效过滤。图5（c）、图5（d）代表了两种极端，在图5（c）中，真实用户与虚假用户相距较近，这样攻击者甚至无需猜测，便能获取真实用户的大体位置，使得真实用户的位置隐私难以有效保证，显然这是不可取的。图5（d）给出了一种相对比较优良的选择结果，即最终参与匿名的几个位置（包括了一个真的和两个假的用户位置），两两之间相距足够远，且具备相等或者近似的服务请求概率，从而大大降低攻击者猜测出用户真实位置的概率，大幅度提高用户的位置隐私级别。

我们对所提出方案的有效性和安全性进行了验证，具体细节[11]可参看，同时对于背景信息的进一步利用可参考[12]。

3.2 同时保护位置和兴趣的隐私

保护方案

同时保护位置和兴趣的隐私保护方案[13]用于同时保护用户的位置隐私和查询隐私，并提供个性化的隐匿区域大小选择。该方案通过对传统的背景信息进行细分，在选择虚假位置的时候，不但考虑选择k-1个查询概率相似的位置，同时兼顾查询隐私的保护，通过合理选择l-1个相似的查询内容，来确保位置隐私到达k-匿名级别的保护，和查询隐私的l-多样性级别的隐私保护。另外，本方案由于在设计初期就允许用户对隐匿区域的大小进行选择，并通过隐匿区域的随机偏移保证真实用户的位置可能落在该区域内的任何位置，从而有效的避免真实位置位于隐匿区域中心部分的攻击。

由于隐匿区域的大小往往决定了系统开销的大小，故而本方案首先赋予用户自主的隐匿区域大小调节能力，从而让用户根据自己的需求合理调节该区域的大小，进而调节可以忍受的系统开销。

具体而言，用户设定合适的隐匿区域，如图6（b）中的红色虚线框，故而需要在该隐匿区域内进行虚假位置分布。然而考虑到上文提到的“用户处于中心区域的攻击”，我们首先对该虚线框进行一个随机偏移，偏移至图中红色实线框处，然后进行相关虚假用户分布工作。在具体分布时，根据需要达到的位置k-匿名中的参数k，首先用四分法对该区域进行划分，如图6（b）所示，k=3，故而将该区域划分为4部分，除了真实用户所处的区域外，随机选取其他3个区域中的2个作为备选，最后开始着手考虑对查询请求内容的l-多样性需求。具体的方法如图7所示，图中每种颜色的符号代表不同的历史查询请求，例如附近的酒店信息，附近的医院信息等，我们在每个细分后的区域内对各类查询请求进行统计，遵循相似的规律来构造剩下的l-1个查询内容，即所选择的l-1个请求内容需要与当前用户的真实请求内容的查询概率接近，从而确保l-多样性的效果。通过以上步骤，最大限度的实现本文所设定的目标。

3.3 基于交互的隐私保护机制

本方案目的在于设计一个通过用户交互来实现信息混淆的隐私信息保护方法，思路相对较简单。每个用户维护一个本地缓冲区，用以随机记录其所处位置和所发送请求，当遇到其他用户时，随机从缓冲区内抽取一条信息进行交换，如此往复，使得每个用户的缓冲区内的信息足够混乱。在真正需要向服务提供商发送请求时，可以从本地缓冲区内随机搭配出若干个组合，结合真实的位置和请求内容一起发送给服务提供商，以达到k-匿名的保护效果。系统架构如图8所示，智能终端利用位置混淆部件、伪兴趣生成部件以及缓冲区对信息进行处理，将处理后的请求信息发送给定位业务系统（LBS）服务器以便获取服务[14]。

4 基于用户隐私链拆分的

实名认证和身份隐私

保护策略

Zhu[15]等人提出通过将用户与证书之间的注册链条打断，并将各部分交由不同的实体进行管理的方案来实现对用户的身份信息的保护，进而实现用户个人信息的安全、有效更新，防止来自用户和服务运营商双方的欺骗和共谋等攻击。主要思想是打断用户查询/发布数据资源时提供的“用户真实身份-用户数据”对应关系，通过引入“假名”（或者多个假名的假名集）的方法实现基于用户隐私链拆分的实名认证和身份隐私保护策略。通过构造相应的“假名集”，将用户隐私链分为“用户真实身份-假名集-用户数据”，可信认证服务器是一个权威的第三方认证服务器，其和各种不同的服务提供商分别管理用户隐私链的一部分。其中，可信认证服务器维护“用户真实身份-假名集”，服务提供商维护“假名集-用户数据”，从而实现实名认证和用户身份隐私的保护。

服务提供商对用户的认证过程可基于移动终端进行。在移动终端上保存假名证书和假名对应的密钥，安装认证模块，该模块可以是应用（APP）程序，也可以是手机用户识别模块（SIM）卡或者手机内部拥有的硬件安全模块。图9是我们基于SIM卡实现的一种兼顾实名与用户身份隐私的互联网服务认证方案。SIM卡中实现有数字签名模块和认证用户识别应用发展工具（STK）应用，可信认证服务方可使用公安部eID服务，具体步骤如下：

·用户向可信认证服务器提供真实身份，申请“全局证书”，该证书包含可信认证服务器对用户的真实身份的签名，用作用户向可信用户申请假名证书时认证的凭证。

·凭借“全局证书”，用户可向可信认证服务器申请多个假名证书，构建假名集合。

·用户在向不同服务提供商系统注册时，可以使用不同的假名证书证实自己的身份。这样，服务提供商系统维护假名-用户数据。并利用假名证书实现服务提供商系统的登录认证，保证了不同的服务使用不同的假名。

服务提供商对用户的认证过程如下：

·用户提交注册或登录请求。

·服务提供商通过短消息向用户SIM卡发送认证挑战。

·SIM卡上的认证STK应用会截获并处理认证挑战短消息，并通过STK功能将相关注册或交易请求信息显示在手机屏幕上。

·用户确认信息无误后，认证STK应用对认证挑战进行数字签名生成相应的认证信息，并将此信息发回服务提供商。

·服务提供商用户假名证书验证签名的正确性。

这一方案服务提供商不存储用户的真实身份信息，而且不同的服务提供商使用不同的假名，支付等关键交易采用数字签名认证，提高了安全级别。如有需要，通过假名证书，可信认证服务可追踪用户真实身份。

5 结束语

本文分析了现有移动互联网位置、兴趣和身份隐私保护方案，介绍了几个基于分布式架构的位置和查询隐私保护机制，并给出了一个兼顾实名和身份隐私保护的身份认证方案，但是这个方案需要可信认证服务提供方。未来在下面几个方面还有许多问题需要解决。

第一，考虑到智能终端的大规模使用，传统的基于可信第三方的方案无论从性能角度还是安全性角度来讲都有比较大的局限性，所以应该尽可能的避免可信第三方的使用。另外由于智能终端的资源受限性，例如较低的计算能力，有限的存储空间以及相对较弱的通信能力，故而应该尽可能的降低所涉及隐私保护方案的复杂度，并提高已有资源的利用率。

第二，需要充分考虑攻击者可能拥有的各类背景信息。我们的实验结果证明，现有大多方案的隐私保护效果在攻击者拥有背景信息的前提下都会大幅下降，即使少部分方案已经将背景信息考虑进算法设计过程中，然而由于对于背景信息分析的不全面性，导致攻击者仍然能够通过将各类相关背景信息进行融合，如采用数据挖掘等技术，从而增大获取用户隐私信息概率的目的。因此，在未来的研究方向中，需要考虑更加符合用户现实生活的各类背景信息。

第三，目前仍然没有一种行之有效的隐私保护效果衡量方法。由于用户需求的多样性，例如，身份隐私，位置隐私，查询隐私，轨迹隐私，数据隐私等，以及用户在不同应用中对于各类隐私信息的个性化设置等因素，导致对隐私保护效果的衡量工作难以统一的进行，这也使得很难去评价当前已有算法的效果。因此，设计统一的隐私度量方案或者度量平台显得尤为重要。

第四，将信任机制与隐私保护有机结合。如果有足够高的信任，可以降低隐私泄露的风险，提高服务质量，降低系统开销。如何确立最佳的平衡点和建立大规模用户的信任评估模型和系统还亟待开展研究。

参考文献

[1] GEDIK B， LIU L. Protecting Location Privacy With Personalized k-Anonymity： Architecture and Algorithms [J]. IEEE Trans. Mobile Computing， 2008，7（1）：1-18

[2] MOKBEL M F， CHOW C-Y， AREF W G. The New Casper： Query Processing for Location Services Without Compromising Privacy [C]//Proceedings of the VLDB， 2006：763-774

[3] XU T， CAI Y. Exploring Historical Location Data for Anonymity Preservation in Location-Based Services [C]//Proceedings of the INFOCOM， 2008：547-555

[4] MEYEROWITZ J， CHOUDHURY R R. Hiding Stars with Fireworks： Location Privacy Through Camouflage [C]//Proceedings of the MobiCom， 2009： 345-356

[5] XU T， CAI Y. Feeling-Based Location Privacy Protection for Location-Based Services [C]//Proceedings of the CCS， 2009：348-357

[6] PAN X， XU J， MENG X. Protecting Location Privacy against Location-Dependent Attack in Mobile Services [J]. IEEE Trans. Knowledge and Data Engineering， 2012，24（2）： 1506-1519

[7] CHOW C-Y， MOKBEL M F， LIU X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service [C]//Proceedings of the GIS， 2006：171-178

[8] PINGLEY A. Cap： A context-Aware Privacy Protection System for Location-Based Services [C]//Proceedings of the ICDCS， 2009：49-57

[9] PINGLEY A. Protection of Query Privacy for Continuous Location Based Services [C]//Proceedings of the INFOCOM， 2011：1710-1718

[10] SHOKRI R， PAPADIMITRATOS P， THEODORAKOPOULOS G， HUBAUX J P. Collaborative Location Privacy [C]//Proceedings of the IEEE MASS， 2011：500-509

[11] NIU B， LI Q， ZHU X， CAO G， LI H. Achieving k-anonymity in Privacy-Aware Location-Based Services [C]//Proceedings of the INFOCOM， 2014： 1805-1819

[12] NIU B， LI Q， ZHU X， CAO G， LI H. Enhancing Privacy through Caching in Location-Based Services [C]//Proceedings of the INFOCOM， 2015： 1309-1321

[13] NIU B， ZHU X， LI W， LI H， WANG Q， LU Z. A Personalized Two-Tier Cloaking Scheme for Privacy-Aware Location-Based Services [C]//Proceedings of the ICNC， 2015： 2301-2316

[14] NIU B， ZHU X， LEI X， ZHANG W， LI H. EPS： Encounter-Based Privacy-Preserving Scheme for Location-Based Services [C]//Proceedings of the GLOBECOM， 2013： 1106-1117

[15] ZHU Z， CAO G. APPLAUS： A Privacy-Preserving Location Proof Updating System for Location-based Services [C]//Proceedings of the IEEE INFOCOM， 2011：1889-1897