武汉大学学报(理学版) 2017, Vol. 63 Issue (2): 142-150
0

文章信息

彭瑞卿, 刘行军
PENG Ruiqing, LIU Xingjun
用户的行动轨迹还原与隐私风险度量
Action Trajectory Restoration and Privacy Risk Metrics
武汉大学学报(理学版), 2017, 63(2): 142-150
Journal of Wuhan University(Natural Science Edition), 2017, 63(2): 142-150
http://dx.doi.org/10.14188/j.1671-8836.2017.02.007

文章历史

收稿日期：2016-05-31
Abstract              PDF              Figures              Tables
引用本文
彭瑞卿, 刘行军. 用户的行动轨迹还原与隐私风险度量[J]. 武汉大学学报 (理学版),2017, 63(2): 142-150.
PENG Ruiqing, LIU Xingjun. Action Trajectory Restoration and Privacy Risk Metrics[J]. Journal of Wuhan University (Natural Science Edition) , 2017, 63(2): 142-150.
用户的行动轨迹还原与隐私风险度量
彭瑞卿, 刘行军    
湖北经济学院 信息管理与统计学院，湖北 武汉 430205
收稿日期：2016-05-31
基金项目：湖北省教育厅科研计划项目 (Q20152203)
作者简介：彭瑞卿，男，讲师，现从事信息安全和隐私保护方法研究. E-mail：rqp1985@qq.com
摘要：位置隐私保护是位置服务中的关键安全问题.当前的位置发布隐私保护方法忽略了位置点之间的时空关联特性对敏感轨迹信息泄露的重要影响.本文提出了一种基于敏感轨迹点还原的风险模型，利用真实的样本轨迹数据，构造基于马尔科夫链的轨迹隐私威胁模型，基于时空上下文信息计算敏感轨迹点被还原的条件概率，还原由删除或抑制而造成的不完整轨迹数据.基于真实的轨迹数据完成实验，验证了该算法在轨迹数据还原准确性方面达到了80%以上.同时，针对行动轨迹还原中存在的隐私泄露问题，提出一种轨迹数据隐私风险度量模型，通过计算敏感状态的先验概率和后验概率之间的差值来评价轨迹还原造成的隐私泄露程度，估计轨迹点的发布对敏感位置的安全性影响，减少隐私泄露的风险.实验验证了该隐私保护算法的有效性.
关键词：位置服务     位置发布     隐私保护     轨迹还原     隐私度量    
Action Trajectory Restoration and Privacy Risk Metrics
PENG Ruiqing, LIU Xingjun    
School of Information Management and Statistics, Hubei University of Economics, Wuhan 430205, Hubei, China
Abstract: Location privacy protection is an important security issue in LBS (location based service). The current privacy protection methods ignore that the temporal and spatial correlation of location points has important impact on the leakage of sensitive information. In this work, our primary contributions include advertizing a risk model based on restoring sensitive points in the track, constructing a privacy threat model for tracks based on Markov chain, and calculating the conditional probability of restoring sensitive points in the track based on the context information of time and space. We ran an extensive set of experiments on large real-world tracks. Our results demonstrate the possibility of restoring location points with our algorithm is above 80%. Furthermore, we also propose a metric model to advertise the issue of privacy leakage. By calculating the difference value of the prior probability and the posterior probability of sensitive point, it measures the degree of privacy leakage resulting from restoring location points. We use the metric model to evaluate the influence of the issue of the track points on sensitive points. Our experiments demonstrate the effectiveness of our privacy protection method.
Key words: location based service     location publishing     privacy preservation     trajectory restoration     privacy metrics    
0 引言

随着智能移动终端和车辆导航系统的快速发展，各种类型的位置服务如路网优化和社交网络等深入到人们日常生活的各个方面[1].然而，位置信息是一种极其重要的个人隐私数据，在某种情况下分享和暴露位置信息的风险要远远超过所获得的服务[2, 3].

某些应用程序通过采集GPS传感器数据，恶意收集大量的超过其正常功能所需的位置信息，实现非法的信息分享，甚至推理用户习惯和社会关系等更高层次的隐私信息，导致个人隐私的泄漏[4].

访问控制是实现隐私保护的一种重要手段[5]，可通过选择“允许”或“拒绝”应用程序对位置服务的访问来保护隐私信息.

然而，该方法在限制信息使用的同时也限制了位置服务的使用.抑制和泛化是位置发布隐私保护的重要手段[6]，通过分析用户行动轨迹特征，结合当前的运行环境，找出行动轨迹的敏感信息，并通过删除或抑制敏感轨迹点的发布来减少位置隐私的泄露[7].然而，该算法只考虑用户当前运行环境下的轨迹特征，忽略了行动轨迹的时空关联特性对轨迹隐私的威胁，当对手在一段时间内收集到大量的行动轨迹时，可根据用户的行动轨迹所处的上下文信息，准确预测被删除的敏感轨迹点，窃取用户的隐私信息.

本文利用真实的轨迹数据集，通过建立基于马尔科夫链的用户行动轨迹的特征模型，并根据当前的上下文环境，计算敏感信息被还原的条件概率，还原由删除或抑制而造成的不完整轨迹数据.同时，针对该问题，提出一种轨迹数据隐私风险度量模型，通过计算敏感状态的先验概率和后验概率之间的差值来评估轨迹还原造成的隐私泄露程度，预测轨迹点的发布对敏感位置的安全性影响，减少隐私泄露的风险.

1 研究现状

目前位置发布中防止隐私泄漏方法主要有两类，第一类是通过用户授权管理，限制某些情景下位置信息的发布；第二类是敏感信息删除，服务提供者为保护用户的隐私信息，将收集到的用户轨迹数据发布给第三方时，删除轨迹上的敏感片段.

用户授权管理的方式，主要通过用户限制应用程序对位置服务的访问，以及抑制在敏感状态下位置的发布来实现位置隐私保护.Tsai等[5]对各种隐私设置机制进行了总结：用户可以通过访问授权控制来允许或者抑制位置的发布；可以通过设置时间域来控制允许位置发布的时间段；还可以通过设置位置集合来控制允许用户对外发布的位置点.Peng等[8]提出了一种概率生成模型，对应用程序的风险进行排序，以协助用户进行“允许”或“拒绝”应用程序位置服务请求的授权决策.Nauman等[9]定义了一种策略语言，通过对当前Android库进行修改，实现策略执行框架Apex，允许用户选择性地授予应用程序获取位置的权限，同时还可以限制拥有位置访问权限的应用程序对位置的访问次数.Jeon等[10]则基于Android系统平台，提出了一种基于权限抑制的细粒度隐私保护方法，对应用权限请求进行细致的分类，通过修改应用程序的源文件来实现细粒度访问授权策略.当前存在的用户授权管理的方式，虽然在一定程度上实现了用户对位置发布的细粒度控制，但是并不能阻止攻击者根据一段时间内收集到的用户的行动轨迹所处的上下文信息来还原这些被抑制的位置点.

敏感信息删除的方式，主要通过服务提供者在发布轨迹数据库时抑制或删除轨迹当中的敏感点来实现.Terrovitis等[11]通过设定敏感阈值，根据攻击者拥有的背景知识计算每个位置点的敏感度，当敏感度超过阈值时删除该敏感位置点，最终将原始数据库转换成一个安全可发布的数据库.在轨迹模式挖掘等连续性原始数据的挖掘中，Mohammed等[12]基于MFS (maximal frequent sequences) 通常扮演信息基础的角色考虑，提出LKC隐私模型，通过设定最大长度为L的子序列出现的次数以及位置点的敏感值比例，采用全局抑制的方法，将保护重点放在MFS上.Chen等[13]为了更高地保证轨迹数据的有效性，在LKC隐私模型的基础上，进一步提出 (K, C)L-privacy模型，采用局部抑制和全局抑制相结合的方法，当局部抑制不会产生新的违背序列时，认为局部抑制是可行的，否则采用全局抑制的方法.霍峥等[14]总结并分析了当前轨迹隐私保护与数据可用性之间的挑战性问题，并指出了存在的问题和可能解决方法.王丽娜等[15]提出了基于假轨迹的时空匿名方法，综合考虑基于位置和移动方式的背景知识攻击，通过生成假轨迹来隐匿真实的轨迹信息，从而保证轨迹数据的安全性和可用性.王彩梅等[16]综合考虑不同背景知识环境，将用户轨迹用带权无向图描述，从信息熵的角度计算用户轨迹的隐私水平.

现有的方法虽然较好的折中了用户的隐私保护和数据使用的有效性，然而，这些方法仅考虑敏感轨迹当前的运行环境特征，通过删除或者抑制敏感点来保护隐私信息，而忽略了敏感轨迹的上下文信息对隐私的威胁.本文通过建立基于上下文的轨迹风险模型，通过对行动轨迹所处的上下文信息挖掘，还原被删除或者抑制的敏感轨迹点，证明轨迹隐私泄漏风险的存在.同时，基于该风险模型，提出轨迹隐私泄漏的风险度量模型，在轨迹发布之前有效的保护敏感隐私信息的泄漏.

2 行动轨迹还原 2.1 基本符号及定义

用户的行动轨迹点之间具有较强的关联特性，通过对离线轨迹中空缺数据的还原，获取完整轨迹样本中所有非空白位置节点信息，这些信息可能出于空白节点之前或之后，同时，空白节点数量在整条轨迹中所占的比例也会对离线阶段的预测精度造成影响.本文中使用的符号如表 1所示.

表1 符号定义 Table 1 The definition of symbols
名称 符号 值域
位置 l {1, 2, …, n}
位置集合
时间 t
周期
状态 Ct
初始分布 π
状态转移
矩阵集合
状态输出
矩阵集合
状态转移
矩阵		 A
状态输出
矩阵		 B
表选项

●位置：在用户所有的地理位置信息经过聚类或用户标注后得到的位置点中，所有访问次数大于n的位置点，称为对用户有意义的位置，简称为位置，用符号l来表示.设用户所有有意义位置的集合为.对于得到的每一个位置，用一个不重复的整数来表示其标签，则有.

●时间：在用户位置预测模型中，将时间进行离散化，则每一个时刻t可以用一个不重复的整数来表示.又由于人类的移动行为具有周期性，可以设周期为T，则用户的时间.

●状态：在用户的位置轨迹数据中，每一个样本节点表示在某一时刻t，用户处于某一个位置l，则用户的位置状态为在时间t上的有序序列，将序列中的每一个节点称为用户的时空状态，简称为状态，用符号Ct来表示.

●时空轨迹：在一个周期中，用户经历从C1到的状态序列，将序列称为用户的时空轨迹模型，简称为时空轨迹.

在基于位置的服务LBS中，要实现对用户位置的还原，所要解决的主要问题就是根据用户的历史时空轨迹，识别出状态之间的转移关系，并根据这种转移关系建立其相应的概率传播模型.基于建立的模型，根据在现阶段的当前状态或离线阶段的非空白状态信息，对空白状态进行还原.

2.2 时空轨迹模型

利用马尔可夫链模型表示用户的时空轨迹，首先需要将其在时间序列上进行扩展.对于用户u，设集合为所有位置信息集合.则对于用户时空轨迹序列中的每两个相邻的状态节点之间，都对应一个n节点的马尔可夫随机过程，表示状态之间的位置转移概率关系.由于用户的时空轨迹是周期为的序列，且在周期内不同时刻的转移概率并不相同，因此需要建立的马尔可夫链模型为非齐次模型.

设用户在t时刻的状态为Ct，则用户在每个周期内的初始状态为C1，终止状态为.Ct的值域为，即在t时刻，用户可能处于集合中任意一个位置，并且不同时刻可能具有相同的取值.根据一阶马尔可夫链的定义，利用转移概率矩阵将用户在相邻时刻状态之间的转移概率表示出来，进而刻画出用户的时空轨迹模型.

设用户u的时空轨迹模型为，则-1, π).其中为状态转移矩阵集合.其中，At为由Ct到Ct+1的状态转移概率矩阵.对于每一个At，第i行j列的ai, jt表示从Ct到Ct+1是由位置i转移到位置j概率.其中，或者.π为初始状态C1中不同位置的概率分布.

图 1为一个具有三个状态C1、C2、C3的基于一阶马尔可夫链的时空轨迹模型.位置集合={1, 2, 3, 4}.通过对采集的历史轨迹数据的学习，我们掌握了该用户u在t=1时刻的状态只有1与2两种可能，并且通过统计方法可以得到这两种可能性的概率分别为0.3和0.7.这样便可以得到初始状态C1的概率分布π为：

图 1 基于一阶马尔科夫链的时空轨迹模型 Figure 1 Spatial-Temporavy trajectory model based on single-order Markov chain
图选项

π=[0.3 0.7 0 0]

图 1中相邻状态之间的有向边表示从前一个状态所处的某一个位置会以一定的概率转移到后一个状态的某一个位置，边上的权值表示这一转移概率，因此我们可以得到由C1到C2的状态转移概率矩阵A1以及C2到C3的状态转移概率矩阵A2分别为：

其中At中第i行第j列的值表示Ct从位置i转移到Ct+1的位置j的概率值.

2.3 轨迹还原

对于一条长度为的用户时空轨迹样本S={C1, C2, …, }，Ci∈S且Ci=，则称Ci为空白状态节点.根据S中的非空白状态节点以及用户的时空轨迹模型对空白位置进行基于概率的还原，称为轨迹还原.根据轨迹还原的定义，即对所有的{Ct|Ct∈S且Ct=}，计算其条件概率P(Ct=l | S).其预测结果l*=arg maxlP(Ct=l|S).

设Ctb为Ct之前，距离Ct最近非空白状态节点，Cte为Ct之后，距离Ct最近非空白位置状态.根据贝叶斯公式有：

(1)

上式的分母部分为常量，不受l变化的影响，因此只需要求得使分子部分最大的变量l*即可，则有：

(2)

其中, 事件Ctb=ctb为实际观测到的状态节点，即其概率为1，则上式可化为：

(3)

其中，ectb表示从tb到t的概率传播，ei表示从t到te的概率传播，.上述公式所描述的方法在还原空白状态节点的位置时，不仅考虑了空白节点前面最近的已知节点，也考虑了之后最近的已知节点.若只考虑之前的节点，则可能会导致求得的对应最大概率的节点无法生成后续的已知节点.

如图 2所示，为某离线样本S中空白状态节点Ct，以及距离其最近的两个非空白状态节点Ct-1与Ct+1.每个节点的位置取值有0和1两种选择，节点之间的有向边表示转移概率.假设已观测到Ct-1=0且Ct+1=1，若只考虑Ct-1对Ct的影响，则根据最大概率原则，求得的Ct的位置取值为0，但如图中的模型所描述，由Ct=0到Ct+1=1之间的转移概率为0，说明该预测结果不正确.因此，应该综合考虑之前与之后已知状态节点的影响，计算：P(Ct=0|Ct-1=0)P(Ct+1=1|Ct=0) 和P(Ct=1|Ct-1=0)P(Ct+1=1|Ct=1)，分别为0和0.2，因此预测的结果应为Ct=1.

图 2 离线样本S Figure 2 Offline sample S
图选项

攻击者根据还原的轨迹样本对用户的行动模式进行分析和预测，轨迹还原的准确率越高则相应的预测精度也越高，对用户造成的隐私威胁也越大.轨迹预测的算法1如下：

其中，参数为包含状态转移概率矩阵集合的用户时空轨迹特征模型，S为包含若干空白位置状态的用户时空轨迹样本，t为要进行离线预测的时刻，可知.tb为t之前最近的非空白位置状态出现的时刻，te为t之后最近的非空白位置状态出现的时刻.

在Trajectory-Prediction函数内，首先将变量Max_Index和变量Max_Value初始化为0，这两个变量分别记录能够使被预测位置条件概率最大的位置以及概率值.首先计算从tb到t的概率传播pb，再计算从t到te的概率传播pe.若条件概率[pb]i*[pe]cte>Max_Value，则更新最大概率以及产生最大概率的位置，最终将该最大概率值以及相应的位置标记返回.

3 位置隐私保护 3.1 隐私威胁模型

考虑离线应用场景如图 3所示，为某用户的一条经过隐私处理的局部时空轨迹数据.其中l3为敏感位置信息，其他为非敏感位置信息，l2和l4为t+1时刻的备选位置，即可能出现的位置.假设该轨迹在处理的过程中抑制了t+1时刻的l3的发布，而将t时刻和t+2时刻的非敏感位置信息l1和l5进行了正常发布.根据三个时间节点之间的状态转移概率分布，关于t+1时刻的l3的信息同样有很高的概率被还原出来.

图 3 离线阶段局部时空轨迹模型 Figure 3 The local Spatio-temporal trajectory model in offline phase
图选项

因此，必须将用户不同时刻之间状态转移概率对敏感位置暴露的影响纳入考虑，对非敏感位置节点的发布进行控制.

为了描述带有传统位置隐私保护功能的用户时空轨迹特征模型，可以通过隐马尔可夫链来表示其结构.根据隐马尔可夫链的定义，对于t时刻的状态Ct，其状态本身是无法获知的.从观测者的角度来看，所能观察到的变量只有每个时刻的状态输出变量Ot，即存在映射Ct→Ot服从某个概率分布.

为了表现状态和输出之间的不确定性，在原有的马尔可夫链模型中引入状态输出概率矩阵Bt，其中bi, jt表示t时刻的状态Ct为i时，对应的输出Ot为j的概率.则扩展后的模型为，其中为在扩展模型中引入的状态输出概率矩阵集合.

由于采用的传统位置隐私保护方法的不同，可用不同的方法来构造概率矩阵B.为了表示不同位置的敏感程度，首先区分敏感位置和非敏感位置.在实际应用中，位置信息的敏感程度很大程度上会随着时间的变化而变化，即同一位置在不同的时间节点可能处于不同的敏感级别.因此可以将位置与时间二者结合考虑，定义用户的敏感时空状态为：

设用户u为t时刻处于某位置l为用户的时空状态，则用户的敏感时空状态集合为，其中表示用户在ti时处于位置li为敏感时空状态，简称敏感状态.

为了测量还原模型对用户位置隐私的影响，必须能够量化用户位置预测造成的隐私泄露程度.这种潜在的隐私泄露是由于被观测状态的出现消除了被预测状态的一部分不确定性，增大了其被预测的概率，而这部分额外的概率，可以采用敏感状态的后验概率与先验概率之间的差值来表示.根据模型的定义，在未观测到任何前驱时间节点时，对于所代表的事件“Cti的位置取值为li”，其发生的概率为，此为该敏感状态的先验概率.当观测到某前驱事件“Ctj的位置为lj”时 (该状态必为非敏感状态)，该事件的发生很可能对未来事件A的发生概率产生了影响，产生的敏感状态的后验概率为, 则后验概率与先验概率的差值为隐私泄露程度.

通过对隐私泄露程度的测定，可以定量地表示出非敏感位置的发布对敏感位置暴露概率的影响.用户在使用LBS应用的同时，建立自己的时空轨迹模型，并根据模型在对非敏感状态发布之前，预先判断其发布对敏感状态的影响.用户根据不同的应用场景以及隐私需求，来设定其容忍的隐私暴露程度阈值δ.若检测到的隐私暴露程度高于δ，则称这种发布会导致敏感状态的隐私泄露程度超过阈值的非敏感状态为半敏感状态，并对其进行相应处理.

3.2 位置隐私度量

轨迹还原中的隐私检测主要用于计算被抑制位置信息的还原概率，以度量轨迹的隐私风险程度并控制轨迹的发布.在实际应用场景中，用户的历史轨迹数据可以被服务提供者面向第三方进行发布，用于改善和优化服务功能以及进行相关调查.在对外发布之前，需要对每条历史轨迹数据进行离线隐私检测，以确定其不存在隐私泄露风险.

采用了传统位置隐私保护方法处理的离线数据，其中部分敏感位置已经被抑制为空白位置.扩展后的模型可以用加入了状态输出概率矩阵集合的隐马尔可夫链来表示.其中bi, jt表示当状态Ct的位置取值为i时，对外发布的位置为j的概率.

在实际应用中，根据用户的选择，会以一定的概率对敏感位置作出发布或抑制处理，则有：

(4)

该式表示对Ct节点的可能敏感备选位置i，有pit的概率被抑制发布，即用户在t时刻有pit的概率不想被外界知道自己处于i位置, 有1-pit的概率向外发布.

基于上述假设，对于集合中的每条样本，其中的空白位置节点即为该节点的处于被抑制状态的位置节点.这样就可以获得整个中各状态与其输出之间的概率矩阵.离线预测阶段隐私检测的最终目的是对所有的样本S，测量其中所有的的节点被还原出敏感位置信息的概率，即通过观测整条样本，对该节点造成的敏感位置隐私泄露程度进行考察.

在隐马尔可夫链中，通过对输出变量的观测来预测状态变量的主要采用前-后向算法，描述如下：

设观测向量o为一条长度为T的历史样本的输出，o=(o1, o2, …, oT)，且满足.则通过观测向量o来预测某时刻t被抑制的位置状态为i的概率为：

利用前向算法因子α和后向算法β来分别计算各部分概率值：

其递归终止的条件为，对于所有的j，初始化αj(1)=πj.

其递归终止的条件为，对于所有的j，初始化.

综合前向算法因子α和后向算法β，则得：

完整的前-后向算法如算法2.

首先对样本S中每个空白采样点C，枚举其处于可能的敏感位置的先验概率和后验概率.其中计算先验概率的算法与在线阶段的Get-Prior () 函数相同，计算后验概率方法为前-后向算法，其中α(i, t) 为前向算法因子，β(i, t) 为后向算法因子.对求得的每一对后验概率以及先验概率计算其差值，若差值大于用户定义的阈值δ, 则返回false表示样本的观测序列可能导致当前节点敏感位置信息过度暴露.若对于所有的空白位置都满足隐私暴露度小于阈值δ，则最终返回true表示样本观测序列符合隐私要求，不会造成被隐藏位置过度暴露.

4 仿真实验 4.1 仿真实验环境 4.1.1 实验数据

本次实验所有数据来自Crawdad数据社区[17].该数据集通过在韩国首尔地区对参与实验的用户进行超过两个月的细粒度位置数据收集，采集到用户的精确位置信息以及用户对位置信息的定义.由于位置节点的聚类已有实验用户在采集过程中交互完成，因此采用该数据集进行实验可以省去位置聚类的过程.

4.1.2 样本数据分析

实验中将50%的数据用于建立用户时空轨迹模型 (以下称为学习样本)，25%的数据用于测试位置预测 (以下称为预测样本)，另外25%用于隐私检测 (以下称为隐私样本).为了建立用户模型，首先需要将学习样本中的有意义位置进行采集，并分别对数据集中所有位置信息出现的次数以及位置停留时间的分布进行统计，如图 4和图 5所示.

图 4 位置出现频率分布 Figure 4 Position frequency distribution
图选项
图 5 位置停留时间分布 Figure 5 Position residence time distribution
图选项

从图 4中可以看到，全体样本中的绝大部分位置出现的次数都极低，这部分低频率位置对应了用户在移动过程中采集到的无意义位置点.样本中的少部分位置信息重复出现了多次，对应了样本数据中对于用户有实际意义的停留位置.因此，根据位置出现频率的分布以及用户对位置信息的标记，并综合考虑生成的位置取值空间的大小，对于出现次数在15次以下的位置数据点进行剔除，将其所处时间段的位置信息置为空白.

如图 5所示，用户的停留时间同样符合长尾分布.其中用户的最短停留时间为7 min，最长为16 h.因此，综合考虑采样精度以及生成的模型周期长度，将采样时间间隔设为30 min.实验中仅对原始数据中从每天8:00开始，到当天24:00结束的位置数据进行采样，因此可得到采样周期为33 min.

4.1.3 实验平台

Intel (R) Core (TM) i5-2450M CPU 2.50GHz双核, Windows 7 8 GB内存的64位台式机.使用C++语言实现本文的算法.

4.2 位置还原与预测 4.2.1 预测准确性

测试样本在离线阶段预测的局部准确性分布如图 6所示，其中横轴为按照准确性排序之后的预测样本，纵轴为其对应的局部准确性，分别将空白状态节点比例设为0.1至0.5，可以看到，随着空白状态节点的比例的增大，样本的个体以及整体的局部准确性都出现了相应的减小.

图 6 不同比例的空白节点预测准确性 Figure 6 The forecast accuracy when the blank node ratio is different
图选项

如图 7所示为所有预测样本的全局准确性，即整体预测准确性随空白状态节点比例的上升所发生的变化.随着空白节点比例的上升，离线预测的整体预测精度呈现下降趋势，当空白节点比例为0.5时，其得到的预测准确性高于0.4所对应的预测准确性，但仍低于比例为0.3时的预测准确性.实验结果表明，当空白节点比例不高于50%时，离线预测可以以高于80%的概率对离线样本中的空白位置信息进行还原.

图 7 预测精度随空白节点比例的变化 Figure 7 The prediction accuracy varies with the percentage of blank nodes
图选项
4.2.2 隐私度量

图 8表示了在离线阶段，对所有经过传统位置隐私保护处理的离线样本进行还原，所导致的敏感位置信息暴露程度，其中模型输出矩阵B中，敏感位置信息对应的输出概率为随机生成.由于前-后向算法的最坏时间复杂度为，完全按照递归终止条件进行计算，则不可能在有限的时间内求得结果，因此实验中只进行有限深度的前-后向算法，其递归深度为2.

图 8 隐私暴露程度 Figure 8 Privacy exposure level
图选项

根据图中的分布，其最小隐私暴露程度为0.006，最大隐私暴露程度为0.989，平均隐私暴露程度为0.714.可见，通过对离线样中非敏感位置的观测，综合状态转移模型以及状态输出模型，会对敏感位置信息的暴露额外造成0.714的概率.

5 结论

本文提出了一种基于敏感轨迹点还原的风险模型，通过构造基于马尔科夫链的轨迹隐私威胁模型，以及基于时空上下文信息计算敏感轨迹点被还原的条件概率，还原由删除或抑制而造成的不完整轨迹数据.同时，针对行动轨迹还原中存在的隐私泄露问题，提出一种轨迹数据隐私风险度量模型，通过计算敏感状态的先验概率和后验概率之间的差值来评价轨迹还原造成的隐私泄露程度，估计轨迹点的发布对敏感位置的安全性影响，减少隐私泄露的风险.实验验证了该隐私保护算法的有效性.将理论模型与实际用户轨迹数在空白节点比例不大于50%时，预测准确性可达到80%以上.隐私暴露实验的结果表明，在只采用了传统位置隐私保护方法的模型中，位置预测会造成潜在的位置隐私暴露，因此采取相应的检测与控制手段是十分必要的.

参考文献
[1] 刘经南, 郭迟, 彭瑞卿. 移动互联网时代的位置服务[J]. 中国计算机学会通讯, 2011, 7(12) : 40–50. LIU J N, GUO C, PENG R Q. The location services in the era of mobile Internet[J]. Communications of the China Computer Federation, 2011, 7(12) : 40–50(Ch).
[2] XUE M H, LIU Y, ROSS KW, et al. Thwarting location privacy protection in location-based social discovery services[J]. Security & Communication Networks, 2016, 24(8) : 1506–1519.
[3] NIU B, GAO S, LI F, et al.Protection of location privacy in continuous LBSs against adversaries with background information[C]//2016 International Conference on Computing, Networking and Communications (ICNC).New York:IEEE Press, 2016:1-6.
[4] SCHLEGEL R, CHOW C Y, HUANG Q, et al. Privacy-preserving location sharing services for social networks[J]. IEEE Transactions on Services Computing, 2016, 9(1) : 1–14.
[5] TSAI J, KELLEY P, CRANOR L, et al.Location-sharing Technologies:Privacy Risks and Controls[DB/OL].[2016-02-02].http://cups.cs.cmu.edu/LBSprivacy/files/TsaiKelleyCranorSadeh_2009.pdf.
[6] PERVAIZ Z, AREF W G, GHAFOOR A, et al. Accuracy-constrained privacy-preserving access control mechanism for relational data[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(4) : 795–807. DOI:10.1109/TKDE.2013.71
[7] MICHAELA G, SUMAN N, JOHANNES G.MaskIt:Privately releasing user context streams for personalized mobile applications[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.New York:ACM Press, 2012:289-300.
[8] PENG H, GATES C, SARMA B.Using probabilistic generative models for ranking risks of android apps[C]//Proceedings of the 2012 ACM Conference on Computer and Communications Security.New York:ACM Press, 2012:241-252.
[9] NAUMAN M, KHAN S, ZHANG X.Apex:Extending android permission model and enforcement with user-defined runtime constraints[C]//Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security.New York:ACM Press, 2012:328-332.
[10] JEON J, MICNSKI K K, VAUGHAN J A, et al.Dr.Android and Mr.Hide:Fine-grained permissions in android applications categories and subject descriptors[C]//SPSM'12 Proceedings of the Second ACM Workshop on Security and Privacy in Smartphones and Mobile Devices.New York:ACM Press, 2012:3-14.
[11] TERROVITIS M, MAMOULIS N.Privacy preservation in the publication of trajectories[C]//Proceedings of the The Ninth International Conference on Mobile Data Management.New York:IEEE Press, 2008:65-72.
[12] MOHAMMED N, FUNG B C M, DEBBABI M.Walking in the crowd:Anonymizing trajectory data for pattern analysis[C]//Proceedings of the 18th ACM conference on Information and knowledge management.New York:ACM Press, 2009:1441-1444.
[13] CHEN R, FUNG B C M, MOHAMMED N, et al. Privacy-preserving trajectory data publishing by local suppression[J]. Information Sciences, 2013, 231(1) : 83–97.
[14] 霍峥, 孟小峰. 轨迹隐私保护技术研究[J]. 计算机学报, 2011, 34(10) : 1820–1830. HUO Z, MENG X F. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10) : 1820–1830(Ch). DOI:10.3724/SP.J.1016.2011.01820
[15] 王丽娜, 彭瑞卿, 赵雨辰, 等. 个人移动数据收集中的多维轨迹匿名方法[J]. 电子学报, 2013, 41(8) : 1653–1659. WANG L N, PENG R Q, ZHAO Y C, et al. Multi-dimensional trajectory anonymity in collecting personal mobility data[J]. Acta Electronicas Sinica, 2013, 41(8) : 1653–1659(Ch).
[16] 王彩梅, 郭亚军, 郭艳华. 位置服务中的用户轨迹的隐私度量[J]. 软件学报, 2012, 23(2) : 352–360. WANG C M, GUO Y J, GUO Y H. Privacy metric for user's trajectory in location-based services[J]. Journal of Software, 2012, 23(2) : 352–360(Ch). DOI:10.3724/SP.J.1001.2012.03946
[17] KOTZ D, HENDERSON T. Crawdad:A community resource for archiving wireless data at Dartmouth[J]. Pervasive Computing IEEE, 2005, 4(4) : 12–14. DOI:10.1109/MPRV.2005.75