基于K―匿名的轨迹隐私保护相关技术研究

摘要：如何在保证轨迹数据可用性前提下，最大程度保护敏感信息不被泄露，是位置服务中的重要问题。基于泛化模糊思想的隐私保护技术是保护位置服务中轨迹隐私信息泄露的有效方法之一。阐述了轨迹隐私保护问题的内涵，归纳了轨迹可能遭受的攻击类型，分析了常用基于K匿名技术，比较了轨迹数据质量度量方法，指出K匿名模型应用到轨迹隐私保护问题的热点研究方向。

Abstract： It is one of the important issues in the location service that how to guarantee the availability of trajectory data， at the same time sensitive information should not be leaked. In recent years， the trajectory privacy protection has gradually become an active research topic， and the privacy preserving method based on K-anonymity model is an effective method to realize the protection of trajectory privacy.The concept of trajectory privacy protection was discussed， attacking types on trajectory data were analyzed. Trajectory privacy preserving methods based on K-anonymity were concluded. At last， risks of trajectory data were pointed out.

关键词：轨迹隐私保护；K-匿名；位置服务

Key words： trajectory privacy preserving；K-anonymity；location service

中图分类号：TP311 文献标识码：A 文章编号：1006-4311（2015）35-0176-03

0 引言

移动手持设备的普及使得基于位置的服务（LBS，location based services）已经成为信息技术应用的重要趋势之一。LBS是各种网络服务平台基于用户当前位置提供的相关服务的统称，移动用户可主动获取路线导航、商业搜索等服务，也可接受附近商家提供的推送服务，服务处理得到的结果返回给用户。

由于位置服务平台搜集的用户位置和轨迹数据含有丰富的时空信息，对其分析和挖掘能够更好地辅助理解用户行为模式，有效地帮助位置服务供应商制定个性化的用户服务。然而，用户的位置和轨迹数据中含有大量隐私内容，如用户的家庭、单位地址，个人偏好及用户的反常行为，用户在享受LBS提供的便捷服务的同时，也面临着极大的隐私泄露威胁。

在位置服务中，如果位置相关数据能够很容易地被一般用户获知；或者由于轨迹数据的复杂性，行业缺少数据挖掘人才，将轨迹数据外包给其它单位进行分析；再者，轨迹数据拥有者出于各种目的交换轨迹数据，都会造成隐私的泄漏。一旦这些隐私数据被攻击者所掌握，用户的利益和安全就会受到侵犯。因此，如何兼顾用户服务质量和用户隐私安全两个方面是位置服务中需要解决的重要问题之一。

1 轨迹隐私保护的基本问题

1.1 轨迹隐私保护的内涵 文献[1]把信息隐私界定为由个体定义的不愿意被别人知道的一些个人信息，比如个人的生活习惯、健康状况、朋友圈等。

轨迹是指用户在移动状态下请求服务时的运动线路，一般来说轨迹隐私不仅仅指用户的运动线路信息，还包括由轨迹数据衍生、推理得到的其它重要相关数据（包括重要位置数据、个人身份数据等）。

从用户轨迹隐私泄漏的条件来说，轨迹隐私泄露主要来源有三个方面。

①用户移动轨迹上的重要位置数据。这一类隐私信息等同于位置服务中的位置隐私数据，是一种静态的、单个点上的敏感信息。②用户轨迹重要数据。很多数据在其独立存在于数据基本表中时，可能不是敏感信息，但是当若干独立数据综合在一起时，可能会被攻击者通过推理攻击、间接获知敏感信息。这一类隐私信息的保护一方面可以通过对具体的敏感轨迹进行保护之外；另一方面还可以通过切断轨迹中静态点之间的联系来达到轨迹隐私保护的目的。③移动轨迹推理隐私信息。通过对移动轨迹数据的推理，间接获知诸如移动速度、频率等敏感数据[2]。

1.2 轨迹隐私保护常用方法 轨迹隐私保护的常用措施有：①通过用户身份不确定性的提高，使得攻击者无法关联用户身份和敏感信息；②通过增加位置信息的模糊性，使攻击者无法获知足够精确的位置信息；③通过数据库结构等技术手段切断用户身份和轨迹数据之间的关联性。

1.3 位置轨迹隐私保护的挑战 LBS中实现轨迹隐私保护存在一定的难度[2]：①LBS中存在很多泄露用户位置隐私的方式；②轨迹隐私保护和基于位置服务是一对矛盾体，基于位置的服务质量越高，用户的位轨迹隐私往往就越容易泄露；③不同用户对隐私保护强度的要求是不一样的；④互联网设备带宽等资源往往有限，需要轻量级的隐私保护机制。这些都对研究和设计位置隐私保护机制提出了挑战。

1.4 轨迹隐私保护的要求 现有研究中相对成熟的位置隐私保护技术并不能直接应用到轨迹隐私保护问题[3]。

通常轨迹信息和位置信息的数据存储方式有了较大变化，数据结构也不相同。随着时间的增长，轨迹数据库的数据量会不断增加，若利用简单的快照数据模型会带来数据的线性增长，对于需长时间保存轨迹数据的数据库并不可行，所以需要采取新的存储方式。另外轨迹数据含有连续的时间信息，也使得位置隐私保护技术不再适合于轨迹隐私保护问题。

由于轨迹隐私保护不仅要保护轨迹中的位置信息、保护轨迹中个人敏感信息，还要保护轨迹本身暗示的信息。所以传统的基于匿名思想的位置隐私保护方法不能直接应用于轨迹隐私保护问题。

2 隐私风险的度量

通过对隐私可能面临的攻击方式的分析，可以将轨迹隐私泄露分为四种形式。

①直接风险。这是一类最简单、最直接的隐私泄露风险，指敏感信息被非法用户或非授权用户直接获知，而造成的隐私信息泄露[4]。②关联风险（Rr）。位置服务中，只有当轨迹数据包含的敏感位置、用户个人身份信息对应起来时才有可能造成敏感信息泄露[5]，而单独考察敏感位置信息或者个人身份信息，则不能称为隐私信息。针对此类隐私泄露风险，隐私保护策略一般通过切断个人身份与敏感位置信息之间的对应关系来实现。③质量风险（Rq）。现在研究成果中，基于模糊思想的隐私保护策略具有较好的隐私保护效果。这一些隐私保护策略中，存在一对关键的矛盾，即隐私保护强度与数据使用质量[6]。一般来说，隐私保护强度越强，数据模糊程度就越高，因而数据质量就越低；反之，隐私保护程度越弱，则数据越精确、质量越高。④数量风险（Rm）。此类风险一般存在于统计攻击[7]中，当单个个体的相关信息遭泄露时，不会造成隐私泄露；但是当足够多的个体相关信息被攻击者匹敌时，攻击者可能会通过统计分析推理得到统计敏感信息。

3 位置服务LBS中位置隐私的攻击类型

位置隐私攻击一般分为主动攻击和被动攻击两种类型。

3.1 主动式攻击 在主动式攻击类型中，恶意攻击者利用公共平台获知的轨迹信息、不断向服务平台攻击信息，达到干扰隐私保护系统运行、识别用户真实位置的目的。

①诱探位置信息攻击。攻击者多次发送恶意攻击服务请求，通过分析移动服务平台返回的服务结果推理用户位置或轨迹相关敏感信息。②洪水信息攻击。类似于拒绝服务攻击，攻击者通过发送大量服务请求达到干扰服务平台正常动作的目的。

3.2 被动式攻击 这种攻击类型中，攻击者并不会主动服务请求信息、通过分析超过合法用户应该获知的合理信息量，推理位置、轨迹等敏感信息。而是通过合法获知的用户信息，利用隐私保护系统、背景知识等推理获知用户位置等隐私信息的一种攻击行为。常见的被动攻击有区域中心攻击、社会关系攻击等。

4 基于k匿名的轨迹隐私保护技术

文献[8]将k-匿名模型[1，9]引入位置隐私保护中，采用区域代替位置点的方法以达到模糊敏感位置信息的目的，并且要求区域至少能够覆盖当前用户及其周边K-1个用户。在此基础上，相关学者提出轨迹K-匿名的隐私保护模型[10，11]。轨迹K-匿名要求每条移动轨迹至少与其他K-1条轨迹不可区分，以保护轨迹信息的隐私安全。基于匿名的轨迹隐私保护方案如图2所示。

一般而言，通过轨迹聚类算法得到轨迹聚类集和中，每个轨迹聚类集合就具备了代表性，可以直接。此种方法有一定的隐私保护作用，但容易受到了解聚类算法流程攻击者的推理攻击。如图3所示，假设轨迹L1L2L3是属于经过K-means轨迹聚类后的一个轨迹聚类集合M1。通过聚类算法或者直接计算M1中各条轨迹对应采样时间点的均值，可以得到具有该区域特征的轨迹L′（蓝色），也就是该聚类集合的聚类中心，将L′直接就是轨迹特征。而若想将M1进行泛化处理，可以将该轨集合中采样点坐标的最大值连接起来形成区域，图中ABCD四个点构成的四边形区域就是对该轨迹集合的一种泛化方式。

轨迹匿名方法的最大难点是如何在保证轨迹隐私安全和数据质量的前提下，构建轨迹匿名集合。目前，主要通过聚类、泛化方法实现轨迹匿名隐私保护[12]。基于泛化的轨迹匿名方法[13]首先将轨迹集合中的轨迹泛化到多个K-匿名集中，然后通过在K-匿名集中重新构建K条轨迹，以实现轨迹信息的隐私保护。基于聚类的轨迹匿名方法[13]需要进行轨迹预处理、轨迹聚集和空间转换3个步骤。其中，轨迹预处理阶段需将轨迹同步化处理并生成轨迹等价类，轨迹聚集阶段将符合一定条件的轨迹聚集在一起生成轨迹K-匿名集，最后空间转换阶段将每个K-匿名集中的轨迹以聚集中心的形式。然而，以上方法在实现轨迹匿名保护时并未限制轨迹K-匿名集的空间规模和轨迹间的关系，的匿名轨迹数据可用性较低。随着研究的不断深入，轨迹K-匿名集构建的优化方法引起了学者们的重视。

位置隐私保护中使用比较多的是位置K-匿名技术，但数据领域的隐私[1]与位置服务中的位置隐私[3]有较大的区别。Samarati（2002）[14，15]和Gehrke（2006）[8]等研究了如何使用K-匿名方法对位置隐私进行保护。Buttyan（2007）[8]和Du（2007）[10]等通过把空间位置信息泛化为位置集合或区域实现隐私保护目的，其中对位置进行泛化和模糊化处理的过程都是在中心匿名服务器中进行。Chow[10，11]提出了另一种基于K-匿名的位置隐私保护方法。文献[16]提出使用假的位置信息来隐藏用户的轨迹。Serjantov和Danezis[17]在隐私保护度量方面引入香农信息理论[18]。针对隐私保护强度与数据可用程度的协调问题，Tobyxu等人[19]也引入概率分布、信息熵理论，提出plain和advanced两种构建匿名区域代替位置点的方法，使得选用的替代区域既满足隐私保护要求、同时数据效用也满足特定应用领域需求。

5 小结

目前，已有轨迹隐私保护方法大多忽略了敏感信息的个性化需求问题，而现实生活中的不同轨迹所需的隐私保护程度不同，为所有轨迹设置严格的隐私保护会造成大量的信息损失，而为所有轨迹数据设定统一的隐私保护需求则不满足不同用户、不同应用场景下的具体隐私保护需求。下一步将针对不同的知识背景与攻击模式研究个性化轨迹隐私保护方法。

参考文献：