基于K近邻的隐式位置访问隐私保护方法

王 勇，王宏志

(1. 吉林建筑科技学院计算机科学与工程学院，吉林 长春 130114 ；2. 长春工业大学计算机科学与工程学院，吉林 长春 130012 )

1 引言

信息化时代的到来，以及智能终端的涌现，促进了移动互联网的发展。移动互联网与传统互联网不同，在于其具有较强的身份锁定功能，能够不受时间与地点的限制，使用各类传输方式完成信息传输。虽然为人们的生活提供一些便利，但同样也会泄露个人隐私。攻击者可根据个人位置访问数据获取其住址、生活行为方式等敏感信息。这些信息一旦泄露就会对用户隐私造成威胁。为此，需隐藏用户的真实访问位置，但此种做法却无法满足用户对高精度定位服务的需求。单一的隐私保护方式不能兼顾以上两种需求，基于此，有关学者提出下述隐私保护策略。

文献[1]提出群智感知网络个性化位置隐私保护方法。结合用户历史访问轨迹，获取用户对不同位置的访问时间、频率与规律性完成用户社会属性预测；结合位置具有的自然属性，预测敏感等级，按照不同位置安全需求，设置隐私保护策略。文献[2]研究一种基于位置服务隐私自相关的保护方法。综合分析用户自身与服务商缓存的查询记录，防止攻击者通过历史记录对隐私信息进行攻击；在用户隐私自关联前提下，将简易隐私自关联保护方法与扩展隐私自关联保护方法相结合，从时间与查询范围双重维度下实现算法的扩展，全方位保护用户隐私信息。

但上述两种算法会造成通信代价较高，用户搜索效率降低的后果。为此，本文提出基于K近邻的隐式位置访问隐私保护方法。隐式位置访问隐私保护的关键思想在于：结合当前研究得出的隐私泄露方式，针对推测与条件轨迹集合，使用位置替换方式完成轨迹匿名化，此时两个集合的大小会产生变化，使泄露模式的置信度降低到能被允许的阈值范围内。根据这一思想本文利用K近邻方式进行隐私保护。该方法是一种非常重要的查询方法，其核心内容是在固定集合内查询与兴趣点最近的目标。结合服务相似性、背景知识与信息熵等因素，构建敏感位置推理模型，在情境感知基础上实现隐式位置访问隐私保护。

2 隐式位置访问面临的攻击分析

要想实现隐私的全方位保护，必须了解所有威胁位置访问的事件类型，本文从下述几点探讨了隐私保护技术面临的攻击种类。

1)伪装用户威胁

伪装用户代表攻击者假扮成普通用户，通过逻辑推理或监听用户信息等手段，对用户隐私造成威胁。按照攻击形式差异，此种威胁分为下述三种：

被动监听：攻击者假扮成一般用户或直接对这些用户进行有效控制，利用隐私保护框架中用户必须信任的原则，通过共享信息漏洞采集用户真实访问位置。

三点定位：此种攻击方式重点针对网络中近邻发现服务。攻击者假扮为用户，散布虚拟位置消息，观察附近是否存在目标，经长时间探测后，利用三点测量法获取用户实际方位位置信息。

诱探位置：该攻击行为是指攻击者主动向攻击对象发送诱探位置信息，由于受到这些位置信息影响，某些用户匿名区域会出现改变。此种状况下，攻击者可根据匿名区域预测出用户精准的位置数据。假设目标与攻击者之间距离较大，结合匿名算法特性，用户会调节匿名区域边界，同时靠向探测区域。此时，攻击者更加容易推测出用户与诱探区域的位置，降低隐私保护程度。

2)基于用户访问速度的威胁

基于用户访问速度的攻击一般针对连续型访问，此攻击可根据地域背景相关信息推测出用户的实际位置。假设

C

与

C

是相同用户使用泛化法，分别在时间点

t

与

t

形成匿名区域。如果攻击者具备网络允许的最快访问速度

v

，则可结合匿名区域

C

与最大访问速度

v

增量重新形成用户在

t

时间点能够到达的区域

C

，此时将匿名区的范围缩小到

C

和

C

的重合部分。

3)基于用户背景信息的威胁

攻击者事先了解用户背景信息，例如社交关系、兴趣等，结合这些信息推测出用户经常访问的位置。假设用户的匿名区域中含有酒吧、书店与饭店三个语义词语，如果攻击者已经确定用户的身份为学生，则可推断出该用户访问与书店相关的信息概率会更大。

3 基于K近邻的隐式位置访问隐私保护

3.1 位置访问系统模型

本文建立的系统模型是利用集中隐式保护框架，也就是通过某较为可信的第三方来执行隐私保护机制，第三方的处理性能有助于用户快速完成隐私保护。系统架构如图1所示。位置服务器具备全部地图数据与用户的历史访问信息，所以它能够按照相似性定义，事先给出相似地图，并传输到第三方。相似地图中包括服务相似度，能帮助第三方生成

K

近邻的匿名候选区域。当第三方获取用户访问请求后，结合隐私保护方法实现对用户请求的匿名处理，生成扰动位置传输到位置服务器进行处理，并将处理结果通过第三方反馈给用户，实现查询服务。

图1 系统模型图

在该系统中主要存在感知群体、用户与服务提供商三个参与角色，下述分别从功能、安全性等方面对其介绍。

1)感知群体：是用户位置访问数据的采集者也是使用者。比如，某查询酒店的应用，其中酒店位置、价格等即为此应用中认证用户上传的，可将这些用户作为感知群体。安全性假设为：仅有合法的、通过系统认证的用户才有上传数据的资格，上传者上传的数据必须真实可靠。

2)查询用户：属于数据的真实消费者，可以向提供商发出

K

近邻的查询请求，比如查找与其较近的饭店、书店等。为保证所有查询用户的隐私安全，用户可向服务商直接提交请求。

3)服务提供商：是服务的唯一提供者，主要完成信息采集、整理等任务。并对数据做加密处理，再外包给云平台，降低自身成本。其安全假设为：服务商提供的信息是安全可靠的，但会对用户隐私数据感兴趣，以及对采集的用户信息进行分析。

3.2 敏感区域确定

要想确定用户位置访问的敏感区域，需结合服务相似性、背景知识与信息熵等因素，利用这些信息生成标签相似地图，确定敏感区域。

1)服务相似性

假设用户

U

与

U

分别处于

A

与

B

两处，在访问和自己最近的饭店，若获取的访问结果相同，则表明两个位置存在较强的服务相似性。结合访问结果的相似程度判断两个位置的服务相似性

ρ

ρ

=

s

(

A

，

B

)=

s

((

x

，

y

)，(

x

，

y

))

(1)

式中，

s

代表相似度计算函数，

F

(

x

，

y

)为对位置坐标访问结果排序后获得的前

w

个结果集合，

w

是访问结果数量，0≤

ρ

≤1。

2)背景知识

为便于处理，将地图分割成

n

×

n

的网格，任意一个网格均表示位置单元。其中，各单元均存在与其相对的历史查询几率，表达式如下

(2)

3)信息熵

信息熵可以衡量隐私保护程度，该值越大，被攻击者识别出可能性就越高。计算公式如下

(3)

式中，

p

是匿名集合内位置查询概率，其表达式如下

式中，

P

代表第

j

个位置的查询概率。

4)标签相似地图生成

为便于处理，将地图分割为

n

×

n

的网格地图

M

，且

M

={

m

|

i

，

j

=1，2，3，…，

n

}。位置服务器结合查询函数

F

与已知用户兴趣点位置数据获取所有位置单元的查询结果，确定距离用户最近的前

w

个兴趣点，利用式(1)计算获取全部单元的服务相似度

ρ

，同时将

ρ

=1的单元合并在一起，并给予相同标签。因此，将地图

M

当作包含各类分区的标签相似地图，表示为

T

T

={

z

，

z

，

z

，…，

z

}

(4)

则形成包括近邻查询数量的

T

过程如下：

步骤一：形成近邻查询结果表，如表1所示。

表1 近邻查询结果表

步骤二：结合表1近邻查询结果利用式(1)计算两个位置之间的服务相似度。

步骤三：生成T，获取具有不同分区的T。

步骤四：结合表1查询结果获取不同分区的服务相似度，将相似度较高的位置区域当作敏感区域。

3.3 位置访问隐私保护

在确定敏感位置后，通过情景感知的方式完成隐私保护。假设用户U的隐私保护需求表示为

PR

(

k

)=〈(

r

，

l

，

s

)，…，(

r

，

l

，

s

)，…，(

r

，

l

，

s

)〉

(5)

第三方结合敏感位置能够获取用户的敏感区域点集合

LS

(

k

)={

l

，…，

l

，…，

l

}

(6)

当第三方获得用户的访问请求u(l，t，f)后，需评估该请求是否满足隐私设定要求。

假设l代表用户在t时间点上发布的兴趣点，第三方需利用下述公式获取两次访问请求的时间间隔

Δ

t

=

t

-

t

-1

(7)

若

Δ

t，则说明在两次访问请求之间，此用户没有访问过其它兴趣点。反之，用户在两次请求之间访问过其它兴趣点l的机率p(l|l，l，u)可利用下述贝叶斯公式获取：

(8)

将下述三种不同种类的兴趣点添加到用户接下来可能访问的位置兴趣点集合L中：距离用户最近的k个兴趣点；当前兴趣点访问后，其他用户接下来最有可能访问的k个兴趣点；具有最高评分的k个兴趣点。

通过位置服务器对这些兴趣点进行评估，如果置信度较高，则不存在隐私泄露现象；反之，有隐私泄露危险，应及时停止对兴趣点的访问，并将泄露信息反馈给用户，达到保护隐私的目的。

4 仿真数据分析与研究

为验证所提隐式位置访问隐私保护算法性能，所处实验的硬件环境为：操作系统为64位

Windows

7惠普台式计算机，配置是

CPU

为

Intel

i

7-4790，内存是8

GB

；软件环境为：

Python

3

.

6，

Spyder

3

.

2

.

6。实验数据集合的相关信息如表2所示。实验中的用户以某市为例，地域空间限定在10

km

×10

km

的正方形区域内，该区域被划分为100×100的网格。任意网格中的先验查询概率根据此网格中全部兴趣点的评论数量获取。

表2 数据集合参数表

首先在上述仿真环境下，测试兴趣点密度与

k

对用户分区数量的影响。分别在高密度、中密度与低密度三种情况下通过不断改变

k

值，来观察用户分区数量的变化情况，如图2所示。

图2 k对分区位置集合数量的影响

由图2可知，实验初始阶段，分区位置集合数量随

k

值的增加逐渐增加，当

k

值高于兴趣点总数量的二分之一时，分区数量逐渐下降。这是因为

k

值较小时，每个网格内查询结果一致的概率较低，当

k

达到一定量时，查询结果相同的机率升高。此外，兴趣点越稀疏，分区位置集合数量越小，分区面积越大，因此，用户位置访问的隐私需求就越容易被满足。此外，又考虑了

k

值对通信代价产生的影响，为方便分析，假定仿真中设置的用户隐私需求都为5，即分区位置数量集合的信息熵等于5。利用文献[1]与文献[2]方法与本文方法进行对比，当

k

逐渐增加时，用户通信代价情况如图3所示。

图3 通信代价对比图

由图3可看出，随着

k

值的不断增加，大体上的通信代价随之增加，这是因为分区数量随着

k

值的增加而扩大，造成每个分区面积较小。此时，为确保用户隐私保护水平，必须加入大量混淆兴趣点。本文方法无论在哪种分区密度下，通信代价均较为平稳，并没有随着

k

值的增加出现大幅度增长趋势，表明该方法通信代价较小。为进一步证明本文方法对近邻搜索的性能，假设

l

代表匿名点，

l

为真实点，以上述两点为中心进行近邻查询，查询内容为用户提交的申请，通过准确率

P

判断服务质量，计算公式如下

(9)

式中，

S

(

l

)与

S

(

l

)分别表示将匿名位置、实际位置当作中心的近邻查询结果集合。

隐私保护质量取决于匿名点与真实点之间的距离，因此有必要分析不同距离对服务质量造成的影响。

图4 近邻查询性能实验结果图

由图4显示，当近邻数量一致时，随着匿名点与实际点数量的增加，查询准确率随之下降。但是下降幅度并不大，且当查询数量为16时，准确率均会达到80%以上。这是因为对大众行为与用户个人特征进行了准确分析，提高了近邻搜索性能，使隐私保护的服务质量得到增强。

5 结论

隐私保护始终是互联网领域研究的热点话题，针对隐式位置访问信息中存在的隐私保护问题，本文利用K近邻搜索方式确定敏感位置区域，再通过情景感知的方式评估隐私保护器是否会泄露用户隐私，避免用户在危险节点处进行访问。仿真结果表明，通过设置合理的用户兴趣点数量，可提高隐私保护服务质量，且该算法通信代价较低。但该算法依然存在改进之处，例如文中所提的隐式位置访问隐私保护均是针对离线数据的处理，这些数据的应用具有一定局限性。为实现实用性需求，在今后研究中需采用用户发布的实时数据完成进一步研究。