基于位置服务中针对动态轨迹的匿名化

魏 燊，孙广中，谢 幸

（1．中国科学技术大学 计算机科学与技术学院，合肥 230027；2．微软亚洲研究院，北京 100080）

1 引 言

随着传感器技术的发展和移动设备的普及，有越来越多基于位置服务的应用被广泛使用．这些应用在实现自身功能的时候，需要向服务器发送用户当前的位置信息．然而在传输过程中或者服务器端有可能发生信息的泄露，使得攻击者知道用户的位置信息，进而判断住址、生活习惯等．如今移动设备在不断增多，访问互联网也更加方便，使得数据的采集和收集也更加容易．虽然这些数据的使用会给人们的生活带来便利，但是泄露隐私的风险也需要被解决．

目前已经有许多保护用户数据的方法，一些方法需要在数据中添加噪声，以保护真实的数据，如差分隐私［1］，对于地理数据就是在一定范围内改变位置［2］．还有一些方法将真实的数据替换为一个取值范围［3］，对于地理数据就是将位置改变为一片区域［4］，虚假地点［5］则是使用多个地点的集合来代替真实地点，这样可以不将一片区域内的所有地点加入到集合中．本文考虑的情形为移动设备会不断地向服务器发送用户当前的地理信息，通过地理位置查询出相应的结果并返回给用户，攻击者可以了解除真实地点以外的信息．为了保证结果的准确性，本文方法并不对真实地点做修改，因此虚假地点是可行的方法．但是如何选择虚假地点，如何使需要的虚假地点更少，如何防止背景知识很多的攻击者的攻击，都是需要考虑的问题．

本文采用的保护方法如下，首先根据用户上次发送的地点判断用户当前可能到达的所有地点，将这些地点划分为不相交的集合，然后向服务器发送包含真实地点的集合．采用集合划分的原因是这样可以将多个地点对应到同一匿名化结果，攻击者即使知道保护方法和发送的地点集合也无法推测出真实地点．由于集合划分的方法并没有多项式的算法，本文将提出一个启发式算法划分地点集合，并尽可能减少需要发送的虚假地点．

δ隐私用来确保用户的隐私被保护，因为攻击者也会通过设备发送的前后地点甚至用户的行为习惯来推测当前所在位置．在用户发送当前的地点集合时，攻击者对用户可能出现的地点可以计算出一个先验概率，在用户发送过当前及以后的地点集合后，攻击者可以根据这个序列对用户出现的地点的概率进行计算，称为后验概率．而δ隐私则规定后验概率与先验概率之差不能超过δ，即攻击者并不能从用户发送的地点集合序列中获得更多的信息，δ也反应了隐私保护程度．

2 问题定义

2．1 隐私保护模型

假定用户使用的移动设备需要持续地向服务器发送用户当前位置进行查询，得到相应的结果再提供服务．移动设备会有唯一的设备编号，根据这个编号服务器可以唯一识别出用户，需要保护的是用户的地点信息．令o＝｛l0，l1，…，lT｝为用户一天内去过的地点记录序列，其中T为地点变化的总数，ln为第n个时刻所在的地点．用户希望被保护的地点被称为敏感地点，用户所有敏感地点构成的集合用S表示．为了保护用户的真实地点，需要向服务器发送虚假地点．当从t－1时刻到t时刻时，首先推测用户可以到达的地点集合，记为Ct，再对集合Ct进行划分．一个集合C的划分是C的一组非空子集，其中任意两个子集没有交集，且所有子集的并集为C，一个集合的划分记为P（C）．由于攻击者可能会了解所使用的隐私保护方法，如果对于不同的地点都选取不相同的虚假地点来发送，那么攻击者可能会通过两者间的映射关系推测出真实地点．因此在计算划分后，对于一个可行的划分P（Ct），移动设备将向服务器发送包含地点lt的子集Lt，Lt∈P（Ct）．

服务器端最终得到的是一个地点集合的序列，记为o′＝｛L0，L1，…，LT｝．若攻击者也得到了这个序列，那么可以对用户出现的真实地点进行推测，得到一个地点的后验概率，而之前也可以根据用户的历史行为得到这个地点的先验概率．δ隐私要求敏感地点的后验概率与先验概率之差不能超过δ，因此对于所有的时刻t和所有敏感地点s，需要满足

在计算集合划分的时候，需要保证对于每个划分得到的子集，它被发送至服务器时仍能满足δ隐私．

2．2 概率计算

现有的研究表明人们的行为和活动可以用一个一阶马尔科夫链进行建模［6］．马尔科夫链是一种随机过程，包含了状态和状态之间的转移，一阶表明产生当前状态的情况只与上一状态有关．这里仍使用一阶马尔科夫链的思想，当前时刻可能出现的地点只受到上一时刻所在地点的影响．在t时刻时，设备向服务器发送了地点集合Lt，在t＋1时刻，根据Lt推测用户可能到达的地点集合为Ct＋1，那么用户到达Ct＋1中一个地点i的概率可以计算为

这个概率也是在t＋1时刻到达一个地点的先验概率，用PriorPr［lt＋1＝i］表示，其中Pr［lt＋1＝i｜lt＝j］是从t时刻的地点j到t＋1时刻的地点i的转移概率．用户不同地点之间的转移概率是不断变化的，它与用户的历史记录有关，历史轨迹可以反映出用户的偏好；也与不同地点的流行程度有关，大多数用户会倾向于去更多人去过的地方．Pr［lt＝j｜Lt］是地点j被泄露的概率，它和集合Lt中每个地点的先验概率有关，而这些概率是在t－1时刻计算Ct得到的．Pr［lt＝j｜Lt］的计算公式为

在t时刻公开地点集合Lt后，此时Pr［lt＝j｜Lt］就是地点j被公开的后验概率．由于需要满足δ隐私，因此对于地点lt∈S，有

若用户还会继续上传位置信息，在t＋1时刻公开地点集合Lt＋1，那么这个集合也会影响t时刻地点出现的概率，这个也是t时刻地点最终的后验概率．t时刻的地点i的后验概率记为PosteriorPr［lt＝i］，

Pr［Lt＋1｜lt＝i］是用户从t时刻的地点i到达t＋1时刻的地点集合Lt＋1的概率．因此公式5中分子是以Lt中地点i为真实地点到达地点集合Lt＋1的概率，分母是Lt中所有地点到达地点集合Lt＋1的概率．Pr［Lt＋1｜lt＝i］的计算较为简单，

即从地点i到达Lt＋1中各地点的概率之和．为了满足δ隐私，在Lt＋1公开后Lt中的敏感地点i需要满足

最终我们需要计算的就是两个地点间的转移概率，这也是上述公式中需要计算的最基础的概率．对于用户的动态轨迹数据，用户可能会到达新的地点，在预测可能出现的地点时，除了用户的习惯和偏好，还考虑地点的流行程度．用户不仅会倾向于去以前经常去的地点，也会倾向于去没有去过但非常流行的地点．首先使用一个时间窗口W来刻画用户动态的特性，通过前W天的轨迹数据来模拟计算用户的习惯偏好．令counts（i→j）为前W天中存在用户从地点i到达地点j的天数，counts（i）为前W天中用户去过地点i的天数，那么根据历史轨迹数据统计得到的用户会从地点i到达地点j的概率为令pop（i）为前W天内地点i的人流量，那么用户从t时刻的地点i到达t＋1时刻的地点j的转移概率为

λ是用户行为习惯在地点转移概率中占的权重．如果用户对一个地方越熟悉，那么他的行动会更加按照自己的偏好，而不是其他人的影响．本文仅用线性的关系来计算权重，λ＝如果使用其他方法来计算转移概率，只需要将公式（8）修改即可，其他概率计算公式并不需要发生变化．

3 算法求解

3．1 问题转化

为了解决集合划分的问题，在每个时刻首先构造一个包含转移概率的矩阵．令m为t时刻用户发送给服务器的地点集合大小，m＝｜Lt｜．令n为t＋1时刻用户可能到达的地点集合的大小，n＝｜Ct＋1｜．那么可以构造一个m×n的矩阵M，其中每一行对应Lt中的一个地点，每一列对应Ct＋1中的一个地点，

从公式（10）和（11）可以看出，当在时刻t发送地点集合Lt到服务器时，矩阵M中每一行之和是Lt中对应地点的后验概率．而矩阵每一列的和是Ct＋1中对应地点的先验概率．在对集合Ct＋1进行划分后，根据之前由δ隐私得到的约束公式（4）和（7）可以重新表示为，∀p∈P（Ct＋1），i∈S∩p，需要满足

3．2 算法框架

匿名化算法的主要框架见图1．在时刻t对地点lt进行匿名化时，首先使用上一时刻发送到服务器的地点集合Lt－1和间隔的时间估计用户的速度并得到用户在t时刻可以到达的所有地点集合Ct．然后利用公式（9）计算概率矩阵M．最后通过Compute Partition方法计算得到地点集合的划分，返回用户地点lt所在的集合即可．

图1 匿名化算法Fig．1 Anonymization algorithm

以图2为例，用户从上一时刻的地点s到达地点b，根据计算当前用户可以到达的地点为a，b，c，e，f，其中b和c是敏感地点，地点a，b，c，e，f按照先验概率由大到小排列．为了保护用户的敏感地点，将不同地点合并为地点集合，如将a，b合并为一个集合，c，d，e合并为一个集合可以满足隐私要求．在计算划分时通过进一步优化发现，仅将b，c合并为一个集合也可以满足隐私要求，而且这样做划分中最大的子集大小由3变为了2，可以发送更少的地点．因此最后匿名化算法选择包含用户地点b的集合进行发送，即地点b，c．

3．3 集合划分算法

在计算集合划分的时候，首先考虑公式（12）．对于Ct里的一个地点i，它所在的地点集合p需要满 足而函数在x＞0时是单调递增的，因此划分p需要满足的一个条件为其中m是p里对应的值最大的地点可以看作是划分需要达到的一个下界．另外考虑到划分的子集应该越小越好，优先将大的地点加入到集合中以尽快超过下界的值，具体算法见图3．首先将Ct中的地点按对应的值降序排序．之后在每次循环中先找到最大的敏感地点，并按照排序后的顺序选择其他地点与其合并为集合，当这个集合满足公式（12）和（13）的时候不再加入新的地点．然后调用Optimize方法对集合p中的元素进行一些优化和修改，将修改后的集合p加入最终的划分结果partition，并将p中的地点从Ct中移除，然后进行下一轮的循环．

图2 算法运行示例Fig．2 A running example of anonymization algorithm

图3 集合划分算法Fig．3 Set partition algorithm

有两种情况会导致循环停止，一种是当前集合Ct不包含敏感地点时，另一种是把Ct中地点都添加进p后仍没有满足隐私条件时．对于第一种情况，由于剩下的都是非敏感地点，可以直接公开，把它们直接添加进partition即可，每个地点独自表示为一个集合．对于第二种情况，由于剩下的地点无法构成满足隐私条件的地点集合，那么把其中的敏感地点加入到之前已经计算过的集合中．此时只需要判断公式（13）是否满足，因为加入剩余地点后集合仍然满足公式（12）．加入的同时也需要考虑集合的大小，尽量把地点加入到不是最大的集合中．剩下的非敏感地点则可以直接以自身为集合加入到划分结果中．

3．4 优化方法

Optimize方法对于已经产生的地点集合p做一些修改，使划分算法在后面的循环中可以得到更好的结果．它基于两个原则，即在不改变集合大小的前提下，使其包含的敏感地点尽可能的多，和使其包含的对应较大的非敏感地点尽可能少．这样在余下的地点中，需要考虑的敏感地点减少而且供它们合并的非敏感地点更多．保留对应的值大的非敏感地点也使得下一个划分对应的和更容易超过下界，从而需要合并的地点减少．如图4所示，Optimize方法中有两个循环，第一个循环中首先寻找不在p中且对应最大的敏感地点lmax，然后寻找在p中的对应最小的非敏感地点lmin，如果用lmin替换lmax后的集合p仍满足公式（12）和（13），那么p中多增加了一个敏感地点．第二个循环首先寻找p中对应最大的非敏感地点lmax，然后再寻找不在p中的非敏感地点lmin，它对应的值是在小于lmax的地点中最大的，如果用lmin替换lmax后的集合p仍满足公式（12）和（13），那么p中少使用了一个对应大的非敏感地点．方法最后将修改后的集合p返回并加入partition．

图4 优化算法Fig．4 Optimize algorithm

在初始时刻的时候，并不存在前一时刻的地点，不能推测当前用户可到达的地点．但可以在用户真实地点周围随机选取足够多的地点作为划分的集合．在构造转移矩阵的时候，假定前一时刻存在一个虚假的非敏感地点，它到当前时刻地点的概率也根据用户的历史轨迹数据和地点流行程度计算得到，然后就可以构造出转移矩阵之后进行集合划分．

整个匿名化算法并没有找出集合划分的最优解，因为对集合划分的遍历并没有多项式时间内的方法，通过对地点按照的大小进行划分，算法的复杂度可以降低为多项式的．GetReachableLocations方法只需要遍历附近的地点即可，它的时间复杂度为O（n），n是周围的地点个数．ComputeTransitionMatrix方法需要计算上一时刻发送的地点集合到当前时刻可到达地点之间的转移概率，它的时间复杂度为是上一时刻发送的地点集合大小，是当前时刻可以到达的地点数量．从实验中可以看出并不大，因此方法需要计算的概率并不多．ComputePartition方法的时间复杂度为O（nlgn），其中n为需要划分的集合大小．

4 实 验

4．1 数据集描述

本文使用的数据来自中国科学技术大学采集的无线网络设备接入数据．使用的数据集的记录时间从2014年3月1日至2014年6月30日．在这段时间内，校园无线网的接入点有200多个，它们被放置在图书馆、活动中心、教学楼等不同的建筑中．当移动设备如手机通过这些接入点连接到校园网时，数据库会将相应信息记录下来．在无线网接入数据的数据库中共有三个表．第一个是关于校内建筑的说明，它包含了建筑名称、建筑位置的经度和建筑位置的纬度的信息．截止到2014年6月，已经部署了无线网接入点的建筑共有32栋．第二个表是关于无线网接入点的说明，其中包含的信息有接入点序列号、接入点MAC地址、接入点所在建筑、接入点具体位置描述和当前连接用户数等．接入点的序列号和MAC地址都是唯一的，可以被当作接入点的标识使用．第三个表记录了用户连入无线网的详细信息，它包含用户移动设备的MAC地址、连接的接入点的序列号、接入的时间以及断开连接的时间等．移动设备的MAC地址可以当作用户本身的标识．数据库刷新记录的频率为5分钟一次，在用户的设备最开始连接到接入点后的下一次刷新时间，数据库会在第三张表中添加一条与用户相关的记录，其中接入时间和断开时间都设为当前的时间．之后的每5分钟，如果用户依然连接在之前的接入点上，那么数据库会将断开时间更新为这次刷新的时间．如果用户已经不再连接，那么在刷新记录时这条记录的信息不会再更新，断开时间就是上一次的刷新时间．

在2014年3月至6月中，连接过校园无线网的设备有60 000多台．连接记录在30天以上的设备约有13 000个，一个设备一天内连接过3个以上接入点的比例占所有记录的50%．在表1中列出了连接时长最多的几个建筑，其中图书馆的连接时间占到了总时长的一半．对于一天中的不同时间，接入的设备数量也不尽相同，如图5所示为2014年4月8日24小时内东区图书馆和食堂的设备接入数量变化的情况．从图中可以看出食堂只有在早中晚三餐时间连接的设备数量才会增大，其余时间的数量非常小．而图书馆在非休息时间连接的设备数都很多，在早饭和午饭的时段，图书馆设备数增长的时间比食堂增长的稍晚，也符合学生吃完饭去图书馆的活动规律．这些接入的时长可以用来表示不同建筑在不同时间的流行程度．

表1 无线网接入数据中连接时长最多的几个建筑及所占比例Tab．1 Proportion of some buildings with the longest connection time in the Wi－Fi dataset

图5 2014年4月8日图书馆和食堂每个小时的无线网接入设备数量Fig．5 Number of devices connected to Wi－Fi every hour at library and canteen on April 8th，2014

图6中展示了一天内接入设备总量的规律性，图中统计了2014年4月每一天内设备连接的总数量．可以看出接入数量会有周期性的下降，其中2014年4月5日为星期六，即在周末连接无线网的人数会比工作日少．另外由于4月5日是清明节，是法定节假日，所以有三天时间连接无线网的设备比较少，且设备总数比其他周末的时候要更少．

图6 2014年4月中每一天连接无线网的设备数量Fig．6 Number of devices connected to Wi－Fi every day in April 2014

4．2 实验结果

用户的设备在一天内不同时间会连接到不同的接入点上，将设备与人对应，接入点与地点对应，这样就构成了一天内的轨迹．在实验中我们将不同的接入点视为不同的地点，对于用户每次连接的接入点，匿名化后转变为接入点的集合．

在评估算法的时候，我们只使用连接天数在60天以上的设备记录．W被设置为21天．实验中首先测试集合划分算法的效果，在改变敏感地点比例的情况下，计算划分后子集的平均大小，以及划分中最大集合的大小．再测试不同的δ和不同比例的敏感地点对匿名化算法的影响，以发送的地点集合的平均大小作为标准．

首先测试集合划分算法的效果，令δ为0．2，敏感地点占划分集合的比例从10%升到90%，每次增加10%，然后计算划分的子集中最大集合的大小以及所有集合的平均大小．如图7所示，随着敏感地点所占比例的增加，最大的划分子集大小并没有很大变化，保持在8到10之间．如果对所有集合大小求平均，那么集合大小在开始会随着敏感地点比例的增大而增大，之后趋于平稳，保持在4的左右．出现这种情况的原因是当敏感地点多于一定比例时，集合划分已经可以不发生改变．根据划分算法每个集合都是根据其中一个对应值最大的敏感地点而计算得到的，这个地点决定了集合中之和的下界．当敏感地点增多到一定程度时，这些下界会保持稳定，其他非敏感地点变为敏感地点时也不会这个下界造成很大影响．

图7 敏感地点占集合比例不同时对应的划分子集大小Fig．7 Average size of the subset in partitions under different scale of sensitive locations

然后测试用户需要向服务器发送的地点集合大小，用户真实地点所在的集合并不一定是划分中最大的集合，得出的结果应该低于最大集合的大小．图8显示了敏感地点占的比例不同时用户发送的集合大小的均值．δ被设置为0．2，比例依然是从10%增长到90%，每次增长10%．从图中可以看出随着敏感地点的增多，发送的地点数也会增多，从4个地点增长到9个，而没有平稳的趋势．

图9中显示了在设置不同的δ时用户发送的集合大小的均值，其中敏感地点比例固定为30%，δ取值从0．1到0．7．从图中可以看出δ也会影响集合划分的结果，δ越大的时候，划分出子集的大小会越小，发送的地点数也越少，从7个地点减少到2个地点．

5 相关工作

对于地点轨迹的隐私保护按照保护的对象分可以分为两类，对单个地点的隐私保护以及对轨迹的隐私保护［7］，两者使用的匿名化方法中也有一些相同之处．对地点的隐私保护使用的方法主要有虚假地点、空间变换、区域隐藏三类．虚假地点就是在向服务器发送真实地点的时候，也发送其他地点给服务器，降低真实地点泄露的概率［5］．空间变换是将地点信息变换到另一个空间中，再根据新空间内地点的关系进行运算［8］．区域隐藏是将用户的地点转化为范围更大的区域，这片区域内也存在其他用户，这样攻击者就无法确定是区域内的哪个用户［4］．一般区域隐藏都使选定的区域可以满足k匿名［9］，即区域内至少有k个用户，通常需要第三方的可信服务器来进行匿名化操作．

图8 敏感地点占集合比例不同时发送的地点数Fig．8 Average number of uploading locations under different scale of sensitive locations

图9 δ不同时发送的地点数Fig．9 Average number of uploading locations under differentδ

轨迹的隐私保护相对于单个地点的隐私保护需要有更多的考虑，因为轨迹中包含了前后地点间时空的关联．轨迹的隐私保护使用的方法有区域隐藏、混合地区和虚假轨迹等．这里区域隐藏的方法与地点隐私保护中的类似，但是需要考虑用户的当前的轨迹和历史轨迹等信息．如果选择的区域不能由上一时刻的地点到达，那么这块区域就起不到保护当前地点信息的作用，会使保护的效果降低．由于本文假设不改变数据传输的格式，这种方法并不适用．混合地区通过修改用户的标识来保护轨迹隐私．当用户进入混合地区的时候，他们不能将当前的地点信息发送给服务器．这样当用户更换新的标识从混合地区中出来的时候，攻击者不能将他们与之前的轨迹联系起来．使用这种方法也能满足k匿名，但本文假设用户标识是可以被攻击者了解的信息．虚假轨迹通过构造不真实的轨迹来保护轨迹隐私．对于用户的真实轨迹及已经构造的虚假轨迹，在构造新的虚假轨迹时可以使其与之前的轨迹有较多的交点，这样在相交点时增大了攻击者判断真实轨迹走向的难度［10］．本文不同之处在于在计算虚假地点时考虑到地点间不同的转移概率，将真实轨迹转化为一条以地点集合为元素的轨迹．

6 结 论

本文介绍了一种对用户动态轨迹进行匿名化的方法，方法中使用δ隐私作为隐私标准．将集合划分的方法和虚假地点的方法相结合，通过向服务器发送多个地点进行查询来保护用户的真实地点．对用户每次可以到达的地点集合，使用用户历史数据和地点流行度计算出转移概率，然后进行集合划分，使得每一个划分子集都满足δ隐私．最后在无线网接入数据上进行实验，从实验中可以看出匿名化后需要发送的地点集合并不大．

［1］DWORK C．Differential privacy［M］／／VAN TILBORG H，JAJODIA S．Encyclopedia of Cryptography and Security．New York：Springer，2011：338－340．

［2］XIAO Y H，LI X．Dynamic differential privacy for location based applications［EB／OL］．［2015－08－12］．http：／／arxiv．org／abs／1410．5919．

［3］SWEENEY L．Achieving k－anonymity privacy protection using generalization and suppression［J］．International Journal of Uncertainty，Fuzziness and Knowledge－Based Systems，2002，10（5）：571－588．

［4］PAN X，XU J L，MENG X F．Protecting location privacy against location－dependent attacks in mobile services［J］．IEEE Transactions on Knowledge and Data Engineering，2012，24（8）：1506－1519．

［5］KIDO H，YANAGISAWA Y，SATOH T．An anonymous communication technique using dummies for locationbased services［C］／／Proceedings of International Conference on Pervasive Services．IEEE，2005，88－97．

［6］GÖTZ M，NATH S，GEHRKE J．et al．Privately releasing user context streams for personalized mobile applications［C］／／Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data．ACM，2012：289－300．

［7］CHOW C Y，MOKBEL M F．Trajectory privacy in location－based services and data publication［J］．ACM SIGKDD Explorations Newsletter，2011，13（1）：19－29．

［8］GHINITA G，KALNIS P，KHOSHGOZARAN A，et al．Private queries in location based services：Anonymizers are not necessary［C］／／Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data．ACM，2008：121－132．

［9］SWEENEY L．k－anonymity：A model for protecting privacy［J］．International Journal of Uncertainty，Fuzziness and Knowledge－Based Systems，2002，10（5）：557－570．

［10］HARA T，ARASE Y，YAMAMOTO A，et al．Location anonymization using real car trace data for location based services［C］／／Proceedings of the 8th International Conference on Ubiquitous Information Management and Communication．ACM，2014：34．