针对轨迹数据的攻击性推理可能导致个人隐私信息泄露的问题，提出了一个基于动态时间归整（DTW）交换查询的轨迹隐私保护方案.通过对基于位置的服务（LBS）请求的用户及候选者身份进行匿名化处理，利用DTW算法依次计算出所有候选者与发起者在一定时间间隔内的轨迹相似值，从中选出最优相似轨迹的候选者替代真实用户请求LBS服务，从而实现用户身份与位置的隐私保护.经过安全性分析，所提方案不仅满足匿名性和不可伪造性等安全特性，而且能够抵抗窃听攻击和连续查询服务追踪攻击.仿真实验结果表明，所选候选者轨迹的相似度有明显提高.
In order to solve the problem of personal privacy information disclosure caused by aggressive reasoning of the trajectory data, based on dynamic time warping (DTW) exchange query, a trajectory privacy protection scheme is proposed. Through anonymizing the identities of user and candidates who request location-based service (LBS), and calculating the trajectory similarity between all candidates and the initiator within acertain period of time by using the DTW algorithm, then choosing the candidate with the optimal trajectory similarity to replace real user in requesting LBS, the real user privacy information about identity and location is effectively protected. Security analyses prove that this scheme not only satisfies the security characteristics such as privacy, anonymity, and unforgeability, but also can resist query service tracking attack. Simulation experiments show that the optimal trajectory similarity is significantly improved.
随着无线通信、全球定位系统和智能移动终端的迅猛发展，用户能够随时随地享受基于位置的服务(LBS，location based services)[1-3]带来的各种便利.然而，在传统LBS请求中，移动终端用户请求信息若被攻击者窃听，相关隐私信息[4-5]将会泄露.当前，尽管一些学者针对用户位置隐私问题做了一些研究[6-8]，但深入研究发现，仅防止位置信息泄露已不能满足用户的需求.因此，在保护用户位置隐私的基础上，如何防止攻击者根据位置时空的关联性推断用户隐私信息成为亟待解决的问题[9-10].针对该问题，本文提出了一个基于动态时间归整(DTW，dynamic time warping)交换查询的轨迹隐私保护方案.该方案在匿名LBS请求用户及候选者身份基础上，采用DTW算法，计算所有候选者与发起者一定时间间隔内的轨迹相似值，并由相似度最高的最优候选者替代真实用户请求LBS服务.
1 相关工作近年来，一些学者在移动终端用户轨迹隐私保护方面做了大量的研究工作. Gruteser和Liu[11]根据区域内对象多少将其划分为敏感区域和非敏感区域，通过对敏感区域内的用户进行抑制或延迟位置更新的方法来保护其轨迹隐私. Terrovitis和Mamoulis[12]通过迭代抑制的方法从轨迹中选择满足隐私约束的位置，由于轨迹被抑制造成信息大量受损，导致服务质量下降. Chen等[13]通过向敏感轨迹数据集中添加假数据或局部抑制的方法，提出一种基于轨迹频率抑制的隐私保护方案.随后，Dai和Hua[15]提出一种基于分段假弹道的虚拟轨迹生成方案.以上方案均基于虚拟轨迹模糊和抑制思想，尽管实现简单，效率较高，但隐私级别相对较低.针对此问题，学者们又提出了一些基于轨迹匿名的方案. Chow和Mokbel [16]提出一个k-匿名区域共享方案，通过包含其他k-1个相同用户连续查询，LBS服务器无法辨别真实用户. Kato等[17]以用户移动特征信息预知为前提，提出一种虚拟匿名化轨迹隐私保护方案，但轨迹相似度有待进一步提高. 2014年，Hwang等[18]提出一种基于用户隐私信息的综合弹道隐私方案，通过预处理一组类似轨迹来模糊用户的真实轨迹，同时引入时间模糊技术，由于每次预处理计算量较大，导致效率偏低. Schlegel等[19]提出一个用户自定义的隐私网格系统，满足了快照和持续LBS查询隐私保护的基本要求，但需要一个第三方辅助实现.李凤华等[20]提出一种高效的轨迹隐私保护方案，基于地图背景信息、轨迹相似性以及用户行动模式等特征来构建k-1条虚假轨迹，以致攻击者无法分辨出其真实轨迹，进而保证终端轨迹隐私安全. Peng等[21]提出一个基于连续查询的协作轨迹隐私保护方案.但以上三个方案均未考虑通信保密问题.
2 预备知识 2.1 轨迹隐私保护系统模型如图 1所示，轨迹隐私保护系统模型主要由移动终端、可信匿名服务器和LBS服务器三部分实体组成.每部分实体的功能如下：
|
图 1 轨迹隐私保护系统模型 |
1) 移动终端.移动终端具有两个功能：一是向可信匿名服务器发送匿名化请求并验证匿名的有效性；二是发送LBS请求，并接收服务查询的结果.
2) 可信匿名服务器.在匿名位置隐私保护中，通常需配置一个可信匿名服务器.可信匿名服务器保存用户属性矩阵信息，并处理移动终端请求，为移动终端寻找最优候选者，发布系统参数等.
3) LBS服务器. LBS服务器是轨迹隐私保护系统的核心部分，负责处理来自移动终端的匿名化查询，并将查询结果反馈给移动终端.
2.2 轨迹数据集对于一个运动对象A，其运动轨迹TA是一组在采样时间内的离散位置，而轨迹数据集T是所有用户轨迹序列的集合，表示为：T={Tk}，k=1, 2, ….其中，Tk为用户i的运动轨迹.每个用户k的运动轨迹Tk是由n个不同时刻ti的位置序列组成，表示为:Tk={IDk, (x1, y1, t1), (x2, y2, t2), …, (xn, yn, tn)}.其中，t1＜t2＜…＜tn, IDi表示用户的匿名身份，(xi, yi)为对象在ti时刻的位置，ti为采样时的时间.
2.3 动态时间归整算法DTW算法是针对传统算法对采样过于苛刻的问题而设计的，通过采用重复之前的记录点填补对应空缺的方式，求出最小距离作为轨迹的相似性度量.设序列L={l1, l2, …, lm}和序列H={h1, h2, …, hn}分别表示两条轨迹的空间域离散采样，其中，m>1, n>1.为了对齐L和H内的元素，需要构造一个m×n的矩阵，矩阵元素(i, j)分别表示li和hj两点的欧氏距离Dist(li, hj)，即欧几里得距离. 2条轨迹间的相似度表示为：DTW(L, H)=D(m, n).其中D(i, j)满足：D(i, j)=Dist(i, j)+min{D(i-1, j), D(i-1, j), D(i-1, j-1)}，D(i, j)表示序列L与H之间的规整路径距离.
3 轨迹隐私保护方案 3.1 系统初始化系统初始化阶段主要生成系统参数，具体步骤如下：
第1步 G1，G2分别为两个阶为素数q的加法循环群和乘法循环群，P是为G1的生成元. e:G1×G1→G2表示一个双线性映射. Zq*表示模q的整数乘法群.
第2步 定义2个安全哈希函数：H1:{0, 1}*→G1*, H2:{0, 1}*→{0, 1}k.其中，{0, 1}*表示任意长度的二进制串，k为一个整数.
第3步 可信匿名服务器选取系统主密钥s∈Zq*，计算其公钥为：PKanon=sP.
第4步 可信匿名服务器保存系统主密钥s，公开系统参数：{G1, G2, e, k, n, P, PKanon, H1, H2}.
3.2 注册注册阶段主要实现身份匿名化，具体步骤如下：
第1步 移动终端将其真实身份ID作为注册请求消息发送给可信匿名服务器.
第2步 可信匿名服务器随机生成一个m×n矩阵Z(2≤m＜n)和一个m维的列向量p，满足R(Z)=R(Z)，且R(Z)＜n.
第3步 可信匿名服务器为每个用户生成一个唯一n维列向量di，且满足Zdi=p；并随机选取一个n维列向量D，计算用户u的假身份PIDu=DTdi，参数Qu=H1(PIDu)和Xu=sQu，然后将{PIDu, Xu, di}通过安全信道返回给用户.
第4步 用户u收到消息后，计算
设
第1步 根据点间的欧氏距离，生成序列距离矩阵Mn×m，其中行对应Lu，列对应Hc，矩阵元素为对应Lu和Hc中对应点的欧氏距离.
第2步 根据Mm×n计算损失矩阵Mc，Mc第一行第一列元素为矩阵Mm×n第一行第一列的元素.其余位置元素的计算方法为：Mc(i, j)=min{Mc(i-1, j), Mc(i-1, j-1), Mc(i, j-1)}+M(i, j).元素Mc(m, n)为Lu与Hc的轨迹相似度.
第3步 利用同样方法分别求出真实轨迹与其他候选轨迹相同时间间隔Δt内轨迹相似度.
3.4 查询交换的位置服务请求查询交换的位置服务请求阶段主要挑出最优候选者，由候选者替代用户请求LBS服务.具体步骤如下：
第1步 终端用户u发起广播，获取一定范围内候选用户匿名身份{PIDn1, PIDn2, PIDn3, …, PIDnk}，计算MEGuoN={EPKanon(PIDu, PIDn1, PIDn2, …, PIDnk), EPKS(Locu, Qu, Ks)}并发送给可信匿名服务器.其中，Ek()为加密函数，PKs为LBS服务器公钥，Locu、Qu、Ks分别表示位置、请求内容、用户与LBS服务器的会话秘钥.
第2步 可信匿名服务器接收到请求后，随机选择i∈Zq*，计算I=iZ和r=ip，并将消息{t1, I, H2(r‖IDTu‖t1‖t2)}发送给终端用户u，其中IDTu为可信匿名服务器的身份标识，t1表示时间戳.
第3步 用户u接收到消息后，计算R=Idi，验证等式H2(R‖IDTu‖t1)
第4步 可信匿名服务器接收到消息后，验证等式H2(R‖IDTu‖t1‖t2)
第5步 B收到消息后通过解密获取PIDu，并计算MEGBoS={EPKS(PIDB), EPKS(Locu, Qu, Ks)}，然后将MEGBoS发送给LBS服务器.
第6步 LBS服务器收到数据包后解密MEGBoS，获取查询请求内容，并计算MEGSoB={EPKB(PIDB), EnKS(MEG)}，其中EnKS()表示对称加密函数；然后将MEGSoB发送给B.
第7步 B收到消息后，计算MEGBou={EPKu(EnKS(MEG))}，其中PKu表示用户u的公钥，然后将MEGBou发送给u.
第8步 用户u接收到信息后解密MEGBou获取查询结果MEG.
4 安全性分析 4.1 匿名性定义1 匿名游戏.
第1步 攻击者发起询问获取系统公共参数：{G1, G2, e, k, n, P, PKanon, H1, H2}和必要的参数信息.
第2步 攻击者选取两个完全不同的LBS服务请求加密信息m0和m1.
第3步 选取随机位b∈{0, 1}，并将mb和m1-b随机发送给两个最优候选者B1和B2，b对于攻击者是保密的.
第4步 LBS服务器分别为B1和B2查询所请求的信息结果MEGb与MEG1-b.
第5步 如果B1与B2输出两个加密的查询结果MEGb与MEG1-b分别与加密信息m0与m1所请求的内容相对应，然后将MEGb与MEG1-b按照随机顺序发送给攻击者，否则，返回⊥给攻击者.
第6步 攻击者对MEGb进行解密输出真正发出LBS服务请求的用户信息，则攻击者赢得这场游戏.
定理1 假设在轨迹隐私保护方案中攻击者A在匿名游戏中以可以忽略的概率赢得游戏，则该方案满足匿名性.
证明 攻击者A作为定义1中匿名游戏的攻击者，如果在第5步中收到是⊥，则表明攻击者A不能获取任何有用的信息.考虑另一种情况，假设攻击者A获取了2个加密后的请求查询结果：
| $ \begin{array}{l} {\rm{ME}}{{\rm{G}}_{{\rm{So}}{{\rm{B}}_1}}} = \left\{ {{E_{{\rm{P}}{{\rm{K}}_{{B_1}}}}}\left( {{\rm{PI}}{{\rm{D}}_{{B_1}}}} \right), {{{\mathop{\rm En}\nolimits} }_{{K_S}}}\left( {{\rm{ME}}{{\rm{G}}_b}} \right)} \right\}\\ {\rm{ME}}{{\rm{G}}_{{\rm{So}}{{\rm{B}}_2}}} = \left\{ {{E_{{\rm{P}}{{\rm{K}}_{{B_2}}}}}\left( {{\rm{PI}}{{\rm{D}}_{{B_2}}}} \right), {{{\mathop{\rm En}\nolimits} }_{{K_S}}}\left( {{\rm{ME}}{{\rm{G}}_{1 - b}}} \right)} \right\} \end{array} $ |
由于本文方案中所有参与者之间的通信进行了加密处理.若攻击者A预通过解密数据包MEGSoB1来获取用户的身份信息，需要通过计算XB1=sQB1和SKB1=rB1XB1得到其解密密钥SKB1，而该计算过程将面临求解椭圆曲线离散对数难题.即攻击者A通过解密方式获取请求结果信息等价于破解椭圆曲线离散对数难题，其在计算上是不可行，故攻击者A赢得游戏的概率：Adv(A)=|Pr [A]|是可以忽略不计的.因此攻击者A在匿名游戏中以可忽略的概率赢得游戏.方案中每次LBS请求均由不同的最优的候选者替代，隐藏了发起者的身份信息，因此进一步提高方案的匿名性.
4.2 不可伪造性用户注册阶段，可信匿名服务器为用户的真实身份进行匿名化，生成可验证性的假身份PIDu，注册用户获取信息{PIDu, Xu, di}后，用户计算
用户和LBS服务器之间的无线通信容易被攻击者监视和窃听，本文方案通过加密方式来解决窃听攻击.当最优的候选者与LBS进行通信时，最优候选者B的PIDB和发起者u的请求信息(Locu, Qu, Ks)使用LBS服务器的公钥PKS加密，确保请求信息和会话秘钥Ks的保密性.当LBS返回查询结果时，使用会话秘钥Ks对查询结果加密，并使用LBS服务器的公钥PKS对最优候选者B的PIDB进行加密处理，确保用户的信息和身份不被泄露.
4.4 抵抗查询追踪攻击查询追踪攻击也称为连续查询攻击.本文方案通过最优候选者替代发起者请求LBS服务，发起者的身份完全由候选者的身份替代.在LBS服务器的查询记录信息中，仅记载了最优候选者的身份信息；同时，用户移动轨迹上不同时间间隔内代替其发出LBS服务请求的最优候选者是不固定，攻击者无法通过查询用户交集推断其关联性.设用户在移动轨迹上连续查询的次数为k次，每次参入请求的候选者个数为ni，其中1≤i≤k，由于每次查询过程中最优候选者不同，即不同的匿名区域候选者相互独立.设攻击者截获用户u和候选者之间的通信并解密消息的概率为Pr(E)，根据PIDu求解di的概率为Pr (ID)，假设攻击者获取移动终端用户向匿名服务器注册请求消息，那么连续查询过程中实现用户追踪的概率为
本文仿真实验在Intel i5 CPU处理器、8 GB内存、Windows7 64位操作系统、MATLAB仿真软件和移动对象生成器Thomas Brinkhoff环境下进行.假设具备一个理想的网络环境，Thomas Brinkhoff首先生成大量的移动对象的轨迹数据，然后随机选取某一移动对象作为发起者，通过DTW相似轨迹求解算法和交换查询算法来实现用户轨迹的混淆，进而保护用户的轨迹隐私.为了确保实验结果的真实性，以下所有的实验结果均为1 000次运行的平均值.如图 2所示，在候选者一定的情况下，处理时间开销随着用户和轨迹段点数的增加而增加.例如，当候选者K=5时，轨迹段的点数N从2增加到10，算法的处理时间从18 ms增加到41 ms，这表明处理时间与轨迹段上的点的数量成正比关系.在轨迹段点数一定的情况下，处理时间随着候选者个数的增加而增加，如当N=3时，候选者个数为5、10和15所需要的处理时间分别为21 ms、25 ms和31 ms.由于增加用户的候选者个数或者轨迹段内点数，用户需要匹配一定范围内的更多的候选者用户，导致增加一定的时间开销.需要注意，本文方案在实际应用场景中需要满足候选用户个数K≥2和轨迹段上的点数N≥2.如果请求用户所在环境过于稀疏，如K=0，周围无候选者；若K=1，无需调用DTW算法，直接替代用户请求服务，攻击者可以通过候选者的连续查询进行跟踪.如果轨迹段上的采样点数N=1，那么该轨迹段由该采样点来替代，显然，一个点无法确定轨迹段的相似性.
|
图 2 候选者个数和轨迹段的点数与时间的关系 |
实验结果如图 3所示，三个方案中，候选者个数K对最优轨迹相似度影响均不大.在候选者个数K相同的情况下，随机选择方案的相似度效果最差，文献[17]次之，本文方案相似程度最高.因为随机方案不考虑用户的行动模式和趋势等因素，仅随机的生成虚假轨迹；文献[17]在生成虚假轨迹时考虑了用户在每一次停顿后继续行进的方向和可达性等因素，使得所生成虚假轨迹与用户真实的轨迹的相似度有所提高；本文方案通过轨迹采样，然后根据DTW算法选择最优相似轨迹，该算法采用重复之前的记录点填补对应空缺位置的方式来计算两条轨迹间的相似度，参与计算的两条轨迹的采样点不需在时间间隔和采样点数一一对应，避开了传统的基于欧式距离轨迹相似度算法，同时，由于该方案采样时间间隔较短，采样点数较多，因此，所选最优候选者轨迹相对于方案[17]更接近用户的真实轨迹.
|
图 3 最优轨迹相似度比较 |
本文针对攻击者根据用户运动轨迹数据进行逻辑性推理可能造成个人隐私信息泄露的问题，提出了一个基于DTW交换查询的轨迹隐私保护方案.通过对LBS服务请求的用户及候选者身份进行匿名化处理，并采用DTW算法挑选最优相似轨迹候选者替代真实用户进行LBS服务请求，从而解决用户的身份和位置隐私问题.通过安全性分析，本文方案不仅满足匿名性和不可伪造性等安全特性，而且还能抵抗窃听攻击和连续查询攻击.对本文方案候选者个数和轨迹段的点数对算法所需时间以及不同方案相似度进行仿真实验，结果表明，本文方案所选最优候选者与真实用户在一定时间间隔内轨迹相似程度明显优于其他方案.因此，本文方案在移动用户隐私保护环境中有着重要的理论意义和应用价值.
| [1] |
Gartner G, Huang Haosheng. Progress in location-based services 2014[M]. Berlin: Springer International Publishing, 2015.
|
| [2] |
Sun Yanming, Chen Min, Hu Long, et al. ASA:against statistical attacks for privacy-aware users in location based service[J]. Future Generation Computer Systems-the International Journal of eScience, 2017(70): 48-58. |
| [3] |
Li Xinghua, Miao Meixia, Liu Hai, et al. An incentive mechanism for K-anonymity in LBS privacy protection based on credit mechanism[J]. Soft Computing, 2017, 21(14): 3907-3917. DOI:10.1007/s00500-016-2040-2 |
| [4] |
Huo Zheng, Meng Xiaofeng. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830. DOI:10.3724/SP.J.1016.2011.01820 |
| [5] |
He Wen. Research on LBS privacy protection technology in mobile social networks[C]//IEEE Advanced Information Technology, Electronic and Automation Control Conference. New York: IEEE Press, 2017: 73-76.
|
| [6] |
Khoshgozaran A, Shahabi C, Shirani-Mehr H. Location privacy:going beyond K-anonymity, cloaking and anonymizers[J]. Knowledge and Information Systems, 2011, 26(3): 435-465. DOI:10.1007/s10115-010-0286-z |
| [7] |
Zhang Yuan, Chen Qingjun, Zhong Sheng. Privacy-preserving data aggregation in mobile phone sensing[J]. IEEE Transactions on Information Forensics and Security, 2016, 11(5): 980-992. DOI:10.1109/TIFS.2016.2515513 |
| [8] |
万盛, 李凤华, 牛犇, 等. 位置隐私保护技术研究进展[J]. 通信学报, 2016, 37(12): 124-141. Wan Sheng, Li Fenghua, Niu Ben, et al. Research progress on location privacy-preserving techniques[J]. Journal on Communications, 2016, 37(12): 124-141. DOI:10.11959/j.issn.1000-436x.2016279 |
| [9] |
Lee K C K, Zheng Baihua, Chen C, et al. Efficient index-based approaches for skyline queries in location-based applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(11): 2507-2520. DOI:10.1109/TKDE.2012.216 |
| [10] |
Tai F Y, Song Jiankai, Tsai Y C, et al. Cloaking sensitive patterns Td preserve location privacy for LBS applications[C]//IEEE International Conference on Consumer Electronics-Taiwan. New York: IEEE Press, 2016: 1-2.
|
| [11] |
Gruteser M, Liu Xuan. Protecting privacy in continuous location-tracking applications[J]. IEEE Security and Privacy, 2004, 2(2): 28-34. DOI:10.1109/MSECP.2004.1281242 |
| [12] |
Terrovitis M, Mamoulis N. Privacy preservation in the publication of trajectories[C]//International Conference on Mobile Data Management. New York: IEEE Press, 2008: 65-72.
|
| [13] |
Chen Rui, Fung B C M, Mohammed N, et al. Privacy-preserving trajectory data publishing by local suppression[J]. Information Sciences, 2013(231): 83-97. |
| [14] |
赵婧, 张渊, 李兴华, 等. 基于轨迹频率抑制的轨迹隐私保护方法[J]. 计算机学报, 2014, 37(10): 2096-2106. Zhao Jing, Zhang Yuan, Li Xinghua, et al. A trajectory privacy protection approach via trajectory frequency suppression[J]. Chinese Journal of Computers, 2014, 37(10): 2096-2106. |
| [15] |
Dai Jiazhu, Hua Liang. A method for the trajectory privacy protection based on the segmented fake trajectory under road networks[C]//International Conference on Information Science and Control Engineering. New York: IEEE Press, 2015: 13-17.
|
| [16] |
Chow C Y, Mokbel M F. Enabling private continuous queries for revealed user locations[C]//International Symposium on Advances in Spatial and Temporal Databases. Berlin: Springer, 2007: 258-275.
|
| [17] |
Kato R, Iwata M, Hara T, et al. A dummy-based anonymization method based on user trajectory with pauses[C]//International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 249-258.
|
| [18] |
Hwang R H, Hsueh Y L, Chung H W. A novel time-obfuscated algorithm for trajectory privacy protection[J]. IEEE Transactions on Services Computing, 2014, 7(2): 126-139. DOI:10.1109/TSC.4629386 |
| [19] |
Schlegel R, Chow C Y, Huang Qiong, et al. User-defined privacy grid system for continuous location-based services[J]. IEEE Transactions on Mobile Computing, 2015, 14(10): 2158-2172. DOI:10.1109/TMC.2015.2388488 |
| [20] |
李凤华, 张翠, 牛犇, 等. 高效的轨迹隐私保护方案[J]. 通信学报, 2015, 36(12): 114-123. Li Fenghua, Zhang Cui, Niu Ben, et al. Efficient trajectory privacy protection scheme[J]. Journal of Communications, 2015, 36(12): 114-123. DOI:10.11959/j.issn.1000-436x.2015320 |
| [21] |
Peng Tao, Liu Qin, Meng Dacheng, et al. Collaborative trajectory privacy preserving scheme in location-based services[J]. Information Sciences, 2017(387): 165-179. |