基于空间位置的K—匿名隐私保护机制研究

摘 要：随着大数据时代的来临，大数据分析带来的隐私泄露问题日益严重。近期频发的、针对用户隐私信息泄露的安全事件中，存在用户自身对于信息安全不够重视和信息接收客户端数据处理保存程序不完善等问题。同时未经许可私下售卖交易用户隐私的灰色产业也严重威胁着信息安全。本文针对K-匿名隐私保护机制在空间位置的应用展开，从位置信息、攻击者、攻击方式出发，介绍了将K-匿名中不同思路的空间和时间相结合的方法，并对该机制的发展方向进行了阐述。

关键词：K-匿名；LBS；位置隐私保护

中图分类号：TP309 文献标识码：A 文章编号：2096-4706（2018）08-0160-02

Abstract：With the coming of the big data era，the problem of privacy leakage caused by big data analysis is becoming more and more serious. In the recent frequent security events for the disclosure of user privacy information，there are problems such as the lack of attention to the information security and the imperfect data processing and saving program of the client. At the same time，without permission，the gray industry that sells private users privacy is also a serious threat to information security. This paper based on the application of K-anonymous privacy protection mechanism in spatial location，from position information，attacker and attack mode，introduces how to combine the space and time of different ideas in K- anonymity，and expounds the development direction of the mechanism.

Keywords：K-anonymity；LBS；location privacy protection

0 引 言

全球化进程不断加速，与之伴随出现了大量电子信息，数据挖掘、大数据等数据分析技术不断进步，人们对敏感信息泄露的问题更加关注，特别是移动设备的普遍运用让位置服务（Location-Based-Service，简称LBS）越来越受到欢迎，成为具有切实应用前景的服务之一。同时因为各种GPS定位愈发精确，LBS已经被广泛应用于军事、医疗、救援、商业和建筑等领域。科技是一把双刃剑，用户在实时发送有关的位置信息时，信息中不仅包含大量数据信息，还存在一些用户自身并不想被他人所知的隐私信息，如个人住宅、交通出行和联系方式等。

1 K-匿名技术的应用

在这些情况下，人们需要一种既能继续为自身提供高质量LBS服务，又能够有效保护自身隐私的解决方案。K-匿名技术是1998年由Samarati和L.Sweeney提出的一种在数据发布时保护私有信息的重要方法[1]。这种技术最初用于保护数据安全，用户匿名。在LBS信息爆炸，用户需要匿名隐私保护之后，K-匿名技术开始应用于位置匿名。

位置匿名因存在时效性和空间性等不同于一般数据的性质，所以相较于K-匿名技术对传统数据的算法，需要做出一些改变。在妥协便利性与时效性上需要对不同的情景区别对待。例如位置K-匿名算法应用于民生领域，如医疗、救援、导航等时，因数据价值相对不高，应首先考虑位置信息的便捷性和时效性。在匿名程度上可以做出一定的取舍，这样可以显著降低成本，提高用户体验。

在另一些领域，如军事、商业等，因数据价值相对更高，一旦泄露将产生严重后果。例如，有人通过Strava（Strava是一款风靡欧美的测速应用，其主要功能是把运动爱好者们的成绩和名将们的成绩加入同一个排名中，其中包括运动时间、配速和路线等信息）发布的全球热度图成功推论出美军军事基地所在地。在阿富汗、叙利亚等中东荒凉地区，只有美军士兵会使用这种运动软件，这些地区的热度图格外引人注目，这表明有外来军队驻扎。另外，可以从跑步者经常围绕建筑物有规律的跑动推测出基地整体规模以及驻扎在当地的“跑步者”的大致人数。更糟糕的是，横穿战区地图的几条较长线条表面暴露了更为复杂的后勤数据，例如车队和巡逻路线，这可能导致部队遭受伏击。

所以在一些非常依赖于信息发送、接收和处理的领域，应同时考虑时效性和安全性。这对广泛应用于各个领域的K-匿名技术来说是一个不小的挑战。另外，在建筑方面，对于位置定位服务提出了较高的精度要求，这也是K-匿名技术研究者不得不考量的一个方面。

2 信息泄露的类型

2.1 攻击来源

探索K-匿名技术在位置信息上的应用，可以从信息攻击者的角度出发，分析匿名消息可以从被攻击的方向着手，反向推演得到较优解。衡量攻击者是否可以在单一用户位置情况下访问位置信息。一是攻击者只得到用户单个独立的位置信息，这是可以较轻松处理的情况，也是绝大多数匿名方法设计者预设的攻击方背景；二是攻击者可以持续不断地接收或是跟踪用户的实时位置信息，繼而通过这些处于更新中的信息绘制完整的运动轨迹。这些信息可以通过在用户发送给客户端的过程中截取获得，也可以通过直接攻击信息接收服务器，盗用客户端数据来实现。通常来说，信息攻击者可以从这些方面来攻击用户或是客户端得到位置隐私信息：单一位置攻击、多位置攻击、上下文链接攻击、多位置和上下文链接合并攻击[2]。

2.2 攻击类型

（1）单一位置攻击可以用来应对较为简单的K-匿名方法，攻击者分析信息成员的位置，若成员位置全部一致，则所有信息都会泄露。这种位置攻击方法基于作为信息发送端的用户在空间为非均匀分布；（2）多位置攻击的攻击者通过跟踪和关联用户的多位置更新查询来获得所需的信息；（3）上下文链接攻击要利用不同信息之间的交错性。攻击者可使用攻击目标信息之外的背景知识来获取用户信息。可分为三种：个体上下文链接攻击、概率分布攻击和地图匹配。

这几种攻击方式仅仅是冰山一角，位置信息攻击者绝不仅仅局限于这几个可能的攻击方式，所以可以从另一个角度，从可以实现位置K-匿名的设计角度出发。

3 K-匿名方式

3.1 空间匿名

首先定义位置的匿名程度，忽略用户密度，然后通过放大暴露空间区域来使用户的精确地址被隐藏。典型的空间模糊方法通过给LS和客户端发送刻意降低过的位置信息来保护信息安全。用户发送给LS的不再是一个精确且具体的位置信息，而是一个将精确地址包含在内的圆形区域。同时这个圆形区域可以由用户自己定义模糊区域，在提供位置信息的同时保护位置隐私。

但这种方法也存在局限性，即客户端未得到精确的用户位置，在一定情况下提高了隐形成本。这就需要用户在隐私保护和信息安全之间进行权衡。于是有人提出在用户发送给LS具体位置信息时，对所发送的信息进行简单的几何变换，如平移对称旋转等，在客户端读取数据时通过反向变换还原具体位置信息，需要变换函数分配给客户端[2]。综上所述，空间匿名可以成功起到对位置消息匿名的作用。但具体到一些需要精确位置的信息时，不单单是发送消息的用户，对于接收客户端也提出了一些硬性要求。

3.2 时间匿名

在发送消息前增加一个延迟，持续等待，直到有k移动客户端访问过同一位置区域，前提是这位置区域由消息发送者发送消息时所在的位置区域，达到用户匿名防止信息泄露的作用。时间匿名的特点在于一定程度上增加了信息从发送到接收分析这一流程的时间长度，在匿名程度隐私保护上具有独特的优势，但也存在不足之处。

3.3 空间和时间匿名

将空间和时间分别定义为消息集合的成员。给用户发送到客户端的消息一个定义，用符合S表示消息的集合，用ms代表初始信息集中的一个元素，定义为：

ms∈S{uid，rno，（t，x，y），k，（lt，lx，ly），N}

（uid—用户id标识，k—最小匿名度）

在这个集合S中，uid代表发送者的标识符，同一个移动客户端发送的消息标识符是一样的，但rno存在差异，这个值用来区别同一客户端不同的消息。（t，x，y）代表一则消息的时空坐标点，参数x和y为二维坐标的空间坐标点，参数t为在空间坐标轴上的时间二维坐标。[3]

在消息中k值代表用户所需的最小位置匿名度，若k=1，该消息对位置匿名没有要求；k>1，該消息与其他至少k-1个相互之间无法区分的消息存在于同一个时空匿名区域中。综上所述，k的值与消息所需隐私程度成正比。

lx和ly代表用户可以自身指定的空间容度，这代表消息存在一个空间匿名区域，在这个空间坐标轴上不应存在任意离消息坐标（x，y）距离超过lx和ly值的点。lt为时间容度，同样应由用户指定。这个参数的确定通常需要由LBS和用户对于信息精确和信息安全之间的偏好二者共同发挥作用。例如，lx和ly的值（空间容度）越大，移动客户端发送的消息越不精确，模糊区域越大，这表示信息的质量越低。反之空间容度越小，位置信息越精确，模糊区域越小，信息质量也就越高。同样lt的值（时间容度）越大，代表这则消息在由LBS接收时收到的延迟越高，降低了用户服务的时效性。

这则公式给出了一个可以定量分析位置消息的空间、时间和匿名程度值的分析方法，能将客户端接收到的消息定性定量，为位置K-匿名技术的不断探索与研究中提供了一个方向思路。

4 结 论

随着计算机技术的不断发展和全球信息化时代的来临，信息泄露造成的后果愈发严重。K-匿名技术作为上个世纪末提出的概念，在十多年间发展延伸出各种算法，在数据安全领域有着不可或缺的重要性。现如今人们在使用LBS时应当进行位置隐私保护，绝大部分方法均利用K-匿名概念保护用户隐私，但是考虑到现在日新月异的各种可能的攻击，位置隐私保护仍然是一个很大的挑战，用户需要在享受位置信息服务的便捷和隐私信息可能被泄露之间进行权衡。

参考文献：

[1] 张毅荣.大数据背景下的K-匿名隐私保护机制研究 [J].农村经济与科技，2017，28（4）：289-290.

[2] 侯士江.基于空间k-匿名的位置隐私保护技术研究 [D].秦皇岛：燕山大学，2014.

[3] 娄绿林.基于位置服务（LBS）的隐私保护方案研究 [D].昆明：昆明理工大学，2013.

作者简介：杨升森（1996.09-），男，汉族，浙江湖州人，本科在读。研究方向：电子信息工程。