DASS：路网上基于交换和合并的用户敏感信息保护方法

李晓燕，朴春慧，潘 晓

（石家庄铁道大学，河北 石家庄 050031）

伴随着移动互联网的蓬勃发展和智能终端的快速成熟，基于位置服务（location based services，LBS）逐渐受到人们的关注，给人们的日常生活带来了极大的便利，因而LBS的需求量在日益增长。例如，移动用户可以通过LBS查询感兴趣点（“离我最近的医院在哪里？”）、GPS导航（“去人民医院怎么走”）等。

移动用户想要获得位置服务，需要向服务提供商提供他们的查询请求以及精确的位置信息。通常基于位置服务要保护的目标有三种［4］：位置信息、用户标识和敏感信息。所谓敏感信息，即用户不希望通过查询信息推断出与用户相关的敏感信息，如推断出用户曾经患过哪种病或者提出过哪些敏感服务。

目前，研究最多的是如何保护位置信息和用户标识。为保护位置信息，使用最普遍的模型是K－匿名模型，即满足K共享特性，一个用户位置与其他K－1个用户位置无法区别。文献［3］首次将K－匿名模型应用到公路网路中，以图1为例，图中是一个公路网络，假设此为3－匿名（K＝3）模型，用户A、B、C组成匿名集，匿名服务器将匿名集发送给基于位置服务器，这样攻击者无法区别到底是哪个发送查询请求，从而达到了保护用户位置位置信息和用户标识的目的。

图1 简单公路网络

对于敏感信息，通常情况下基于位置服务中泄露主要来源于两种公开信息［4］，即位置语义与查询语义。为了防止敏感信息泄露，匿名集不仅要满足K－匿名，还要满足l－差异性模型，即在一个匿名集中，与用户相关的敏感信息应具有足够的差异，从而攻击者将此敏感信息与用户建立联系的概率小于定义的1/l。可是，即使同时满足以上两种模型，隐私泄露仍然可能会存在。例如，存在匿名集｛A，B，C｝，三个用户提出的查询内容均不同，同时还满足3－匿名和3－差异模型，从用户A看来，三个查询均属于敏感查询，而A又不愿意攻击者将自己与任何查询联系起来，这种情况称为敏感同质性攻击。对于敏感同质性攻击，研究者做了大量研究工作。

文献［5］提出了（K，L，P）－敏感匿名模型，以及匿名算法P3RN（Personalized Privacy Protection over Road Networks），来解决道路网络中的感知查询语义的敏感同质性攻击。该方法满足了路网中用户的个性化隐私需求，又保护了用户位置信息安全。然而存在缺点：算法只通过合并寻找匿名集，致使匿名集中包含过多用户，查询代价较高。本文针对文献［5］中存在问题进行了改进，在合并之前先进行满足一定条件的交换，这样既满足了K共享，又使得每组中用户个数最优，提高了匿名算法的效率。

1 系统结构

系统结构采用目前使用最多的中心服务器结构，即在移动用户和LBS服务器之间加入第三方可信匿名服务器，并由匿名服务器完成匿名化处理和查询结果求精。如图2，系统结构包括移动用户、匿名服务器和LBS服务提供商。其中匿名服务器包含有三个部件［4］：知识库、匿名引擎和查询结果求精引擎。知识库中存储着查询类别集合、敏感度以及敏感度关系，知识库的主要功能是从查询历史中建立查询类别集合。

图2 系统结构

2 预备知识

2.1 基本概念

沿用研究［5］工作中对敏感关系、个性化隐私需求等基本概念以及敏感同质性攻击模型和个性化（K，L，P）－敏感匿名模型的定义，其定义如下。

定义1 敏感关系R：设CaSet是查询类别集合，Sset是敏感度集合。令敏感关系R＝｛（a，b）｜aCaSet，bSSet且（a1，b1），（a2，b2）R，若a1＝a2，则b1＝b2｝。

例如，存在查询类别集合CaSet＝｛急救呼叫，敏感政治信息，敏感经济账单，位置导航，购物导引，商品追踪｝，感度集合Sset＝｛top secret，more secret，secret，less secret，non－secret｝。构造一个敏感关系R＝｛（急救呼叫，more secret），（敏感政治信息，top secret），（敏感经济账单，secret），（位置导航，less secret），（购物导引，non－secret），（商品追踪，non－secret）｝。

定义2 个性化隐私需求（privacy profile）：系统中的每个用户均可以设置个性化的隐私需求，形式化的表示为一个四元组profile＝（k，ts，l，p），其中

⇨匿名度需求k，用户可接受的最小匿名度。即用户要求在匿名集中至少包含的用户个数。K值越大，匿名程度越高。

⇨查询敏感度需求ts，用户可容忍的查询敏感度最高值。若某查询的敏感度大于ts，则此查询在该用户看来属于敏感查询；反之，该查询属于非敏感查询。ts越大说明该用户对查询的敏感性容忍度越高。

⇨匿名路段l，表示匿名位置中至少包含的路段个数。l越大，用户位置匿名程度越高。

⇨集合敏感度需求p，表示用户可接受的敏感查询在匿名集合中所占的最大值。P越大说明该用户对敏感查询的可接受程度越高。

例如，某用户u的隐私需求profile＝（4，0.25，3，0.5），表示用户要求在匿名集合中至少包含4个不同用户；若查询敏感度大于0.25则该查询即为敏感查询；匿名集合中所包含的路段个数L至少为3；对于用户u，匿名集中所包含的敏感查询在所有查询中所占的比例不能超过0.5。

定义3 路网：一个简单公路网络可以用无向图G＝（V，E）来表示，其中V是网络结点组成的集合，E表示网络中所有边组成集合，图1显示的即为一个简单的路网模型，其中实心圆表示移动用户，空心圆代表路网结点，图中每条边即是一条路段。

定义4 用户提出的匿名查询：匿名服务器中待匿名的查询可以形式化地表示为（id，loc，profile，q，qs），其中

◆id表示查询标识符；

◆loc＝D（n1，u），设n1，n2为一条路段的两个顶点；

◆profile表示提出该查询用户的隐私需求（参见定义3）；

◆q表示查询内容；

匿名服务器可以通过查询内容q确定查询类别，然后通过敏感关系R得到其查询敏感度。需要指出的是，本文关注数值型查询敏感度，类别型查询敏感度作为未来的工作，数值越大说明敏感度越高。

2.2 攻击模型和隐私模型

定义5 敏感同质性攻击［5］：设CS为一匿名集，对于任意用户u∈CS，根据用户u的查询敏感度需求u.ts可获得在用户看来，CS中包含的敏感查询个数，记作Count＿SQu。若u∈CS，u.p＜Count＿SQu/｜CS｜，则称此攻击为敏感同质性攻击。其中｜CS｜表示CS中包含的用户个数。

图3 敏感同质性攻击的例子

定义6 个性化（K，L，P）－敏感匿名模型［5］：设CS是移动用户组成的集合，若CS满足以下条件：

（1）位置k匿名模型，即｜CS｜≥max（u，k），u∈CS；

（2）匿名集合中个性化路段个数S.L≥Lmax；

（3）存在u∈CS，u.p≥Count＿SQu/｜CS｜；

则称CS满足个性化（K，L，P）－敏感匿名模型。

如图4个性化（K，L，P）－敏感匿名模型例子：

图4 敏感匿名模型例子

根据定义6，由｛u1，u2，u3｝组成的匿名集合满足个性化（K，L，P）－敏感匿名模型。为了防止异常点攻击，匿名集除了满足个性化（K，L，P）－敏感匿名模型外，还需要满足k－共享。根据（K，L，P）－敏感匿名模型，当有一个移动用户u，向LBS发出一个查询请求，他的敏感隐私为（k，ts，l，p），则匿名服务器应如何为u找到一个匿名路段集S（S中包含了K’个移动对象，L’条路段），使得S不仅覆盖u的精确位置，而且还要满足S.K’＞＝Kmax，Count SQu/K’＜＝P，S.L’＞＝Lmax，此满足条件对应于定义6，同时该用户所在匿名集中的所有用户均不受查询同质性攻击。

个性化（K，L，P）－匿名模型的匿名集可以保护用户标识、位置和敏感信息。定义1中的第一条说明匿名集满足位置K匿名模型，可防止用户标识和用户位置信息泄露；第二个条件满足l差异性，保护用户的位置信息；第三个条件可以防止用户敏感信息泄露。

3 划分匿名路段集算法DASS

3.1 构造最初匿名路段集

构造初始匿名路段集的基本思想是：利用文献［3］中无向图中深度优先搜索的方法找到最初匿名路段集。具体来讲，从用户所在路段开始，采用深度优先遍历，给边标号。然后利用边的顺序给边上所有的用户进行编号。将编号后的用户分为B＝｜U｜/Kmax组，除最后一组外每一组包含Kmax个用户，其中｜U｜是所有用户的个数，Kmax是用户最大的匿名度需求。判断初始的Kmax个用户组成的候选匿名集是否满足个性化（K，L，P）－敏感匿名模型。若不满足，则通过交换和和并使其满足要求。

以图5为例，用户个数｜U｜＝7，假设用户u2发出一个查询请求，K＝3。则将结果分成2组，b1＝｛u1，u2，u3｝，b2＝｛u4，u5，u6，u7｝。用户u2属于b1，可知u2所在的匿名路段集为编号为2、3、4的路段。

图5 图的深度优先遍历

3.2 交换

交换部分的基本思想是：首先交换存在不满足隐私需求的用户所在组中的不安全用户。交换准则为：留在原组中的用户是原本隐私需求就得到满足的安全用户，进行交互的用户是在交换后至少一个用户由非安全用户转为了安全用户。

交换前，把所有分组按照不安全用户数进行升序排序，包含不安全用户数小的用户组先进行交换。下面分别从仅包含一个不安全用户和包含多个不安全用户两种情况进行说明。

（1）组中只有一个问题用户（即不满足要求用户）

交换原则1：设u1所在用户组为group1，u2所在组为group2。u1和u2是原组中的问题用户。如果u1可以与u2进行交换，则u1需要满足同时满足以下两个条件：

其中条件2满足其中之一即可，qi为交换来用户与原组剩余用户查询敏感度的升序排列后第i个值，这里k＝｜group2｜为Kmax即该组中用户的个数。

上面的第一个条件，即满足u1.q＜＝u2.q这一条件可以保证原来满足要求的用户仍然满足要求，而判断一个用户u是否存在敏感同质性攻击条件是敏感查询个数与匿名集总个数的比值是否大于该用户的集合匿名度需求P，而u2存在情况下已经使得原组其他用户不存在敏感同质攻击，由于u1.q小不会增加敏感查询个数，故可以保证原来满足要求的用户仍然满足要求。第二个条件即保证换进来的用户u1是安全的。若用户u的一个查询是敏感查询则u.ts＜u’.q（u’为匿名集中任意一个用户），敏感查询的个数可以为x＝｛0，1，2，3…k｝，将u.ts与u’.q排序，u.ts的大小决定了敏感查询的个数，而判断是否存在敏感同质性攻击还要看敏感查询个数与匿名集总个数的比值于P的大小，若满足要求，则应保证u1.p＞（k－x）/k。条件2的三种情况可以实现。

（2）当一组中含有多个非安全用户时，按照非安全用户提出查询的查询敏感度降序排序。依次选出当前查询敏感度最大的用户，利用规则1进行交换，但是优先选择u1.q＜＝min（u2’.tsmin，u2.q），其中u2’为不包含换出用户的其他用户，u2为换出的问题用户若不存在这样用户则按（1）方式交换。这样做使得其他问题用户也有可能得到满足。具体算法参见算法1。

3.3 合并

定义7 敏感查询余额：匿名集中用户在满足隐私需求的情况下还可以填充的敏感查询的个数。例如，一个匿名集中有3个用户，对于用户u来说敏感查询个数为1，而u的集合敏感度需求u.p＝0.8，在满足定义6中u.p≥Count＿SQu/｜CS｜条件下还可以添加一个敏感查询，故u的敏感查询余额是1。

在文献［5］中定义了保守用户，其要求其他组中用户u.q≤group.tsmin，实际上，本文通过敏感查询余额放松了保守用户的定义。

算法1交换

定义8 非严格保守用户：设匿名集中敏感查询余额为零的用户为su，若存在用户u满足u.q＜＝su.tsmin，则称这样的用户为保守用户。

合并的基本思想是优先选择从较容易满足要求的组中找较难满足要求组的非严格保守用户然后插入到较难满足要求的组中。其中，定义敏感查询个数多的为较难满足隐私需求组，若敏感查询个数相同，则根据用户隐私需求参数具体判断难易程度。先处理较难满足的匿名集，这样剩下的问题用户比较容易处理。若满足要求的组存在多个，则从选择位置最近组进行合并。合并算法参见算法2。

算法2合并

4 实例分析

根据上述算法介绍，用一段真实路网详细分析算法的可行性和实用性。以图6路网为例，介绍算法的实现过程，表1列出了各个用户的匿名需求。

图6 路网实例

表1 用户匿名需求

首先通过图的深度优先遍历，K＝3，得到最初的匿名路段集，分组为：1组｛u1，u2，u3｝；2组｛u4，u5，u6｝；3组｛u7，u8，u9｝；4组｛u10，u11，u12｝；5组｛u13，u14，u15｝；6组｛u16，u17，u18｝。根据3.2节中定义5判断出不满足要求的用户有：1组u2；3组u7；5组u15；6组u17，u18；则可知不满足要求组有：1组；3组；5组；6组。

根据4.2节交换算法对表1中用户进行交换：1、3组问题用户交换，两组均不能满足隐私需求，故交换不成立；5、6组中u15与u17交换使得6组满足要求，而5组仍不满足要求，此时，5组变为｛u13，u14，u17｝，6组变为｛u15，u16，u18｝；不满足要求用户有：1组u2；3组u7；5组u13，u17，不满足组有：1组，3组，5组。

由合并算法判断1组的保守用户为满足q＜＝0.4的用户即3组的u7，5组的u13；3组的保守用户为满足q＜＝0.25的用户即u3，u13；5组的保守用户为q＜＝0.3的用户即u1，u3，u8。将3组中u8插入到1组，经判断1组满足要求；此时，1组变为｛u1，u2，u3，u8｝；3组变为｛u7，u9｝。发现最后依然存在3组、5组中的用户不能匿名成功，这里通过添加假数据的方法提高匿名成功率。

5 结论

研究了基于位置服务器中敏感同质性攻击的个性化隐私保护问题，提出了划分匿名路段集（DASS）算法，并用实例验证了算法的可行性。本文研究仅涉及到匿名化部分，今后还有待对其他部分做进一步的研究。

［1］潘晓，肖珍，孟小峰.位置隐私研究综述［J］.计算机科学与探索.2007，1（3）：268－281.

［2］薛娇，刘向宇，杨晓春，王斌.一种面向公路网络的位置隐私保护方法［J］.计算机学报.2011，34（5）：865－878.

［3］Kyriakos Mouratidis，Man Lung Yiu.Anonymous query processing in road network［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22（1）：2－15.

［4］吴雷，潘晓，朴春慧，李占平.防止敏感同质性攻击的个性化隐私保护技术研究.

［5］Xiao Pan，Lei Wu，Chunhui Piao，et al：P3RN：Personalized Privacy Protection using Query Semantics over Road Networks.In procedings of Waim 2014，2014.