基于连续查询的语义位置隐私保护算法

贾媛媛　史志才　方凯

摘 要： 针对用户连续位置查询请求服务中未考虑语义信息而导致用户敏感语义泄露问题，为了实现对道路网络上客户端的查询隐私、位置隐私和语义位置隐私保护，本文提出一种离线轨迹聚类和语义位置图相结合的算法来进行隐藏用户的选择，使隐藏用户的位置具有明显的多样性和不同的语义以及多样化的服务请求，有效保护客户端的语义和位置隐私。在具有2个定义指标的真实地图上评估了该算法的有效性，整个连续查询道路网络服务的过程中，有很好的成功率和查询处理时间。同时与现有的其他可信第三方模型算法进行了对比分析，验证了本文算法的有效性。

关键词： 位置隐私保护; 连续查询; 轨迹聚类; 语义位置图; 语义位置隐私

文章编号： 2095-2163（2021）07-0156-07中图分类号：TP391文献标志码： A

Semantic location privacy protection algorithm based on continuous query

JIA Yuanyuan1， SHI Zhicai1，2 ， FANG Kai1

（1 School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China;

2 Shanghai Key Laboratory of Integrated Administration Technologies for Information Security， Shanghai 200240， China）

【Abstract】Since the user's continuous location query request service without considering semantic information ， to realize the protection of query privacy， location privacy and semantic location privacy of the client on the road network， this paper proposes an algorithm of offline trajectory clustering and semantic location map to choose hidden users， so that the hidden users' locations have obvious diversity， different semantics and diversified service requests effectively protect the semantics and location privacy of the client. The effectiveness of the algorithm is evaluated on a real map with two defined indicators， the entire process of continuously querying road network services has a very good success rate and query processing time. At the same time， compared with other trusted third-party model algorithms， the validity of this algorithm is verified.

【Key words】location privacy-preserving; continuous query; trajectory clustering algorithm; semantic location graph; semantic location privacy

0 引 言

位置大數据为人们的生活带来了巨大的改变，在给人们带来显著收益的同时，也带来了个人信息泄露的危险。2014年，iPhone用户隐私泄露事件披露出苹果公司曾私自记录每次使用LBS（基于位置的信息服务）应用时的位置信息，从而造成用户的大量位置信息泄露[1]。因此，在用户使用LBS应用时，如何保护用户的个人隐私成为一个待解决的问题。

现有的隐私保护方法扩展了查询客户端的范围，一些研究者们将k-1个其他用户也包括进来[2-4];但在这个过程中，会将具有不同移动趋势的其他请求结果移动对象包括起来，这可能是攻击的来源。2007年，Liu借鉴数据发布隐私处理中的l-差异性模型的思想，提出了位置l-差异性模型，以防止位置同质性攻击[5]。但最初提出的位置差异性模型忽略了用户的位置语义。直观上来讲，用户位置带有语义信息，如用户现在位于早餐店，说明用户可能在吃早餐;用户在医院，则该用户很大概率有某种疾病。为了保护用户的语义位置，Damiani等人[6]采用了语义位置隐藏方法，该方法允许用户定义个性化的隐私配置文件，该配置文件说明了指定的敏感场所类型和每种类型所需的隐私程度。但是这种语义位置掩盖方法仅被设计为在不受限制、不受约束的空间中工作移动;但在现实环境中，移动用户大部分在道路网络上，因此可能导致隐私泄露。Lee等人[7]提出了一种位置隐私保护技术，该技术可以保护位置语义免受对手的攻击，采用第三方可信匿名服务器，该服务器使用位置语义信息来掩盖用户的语义位置。同样，研究时只考虑了欧几里得空间，在路网限制下会导致隐私泄漏。又有一些学者提出多样化的服务请求[8]，从而满足k-匿名性和l-多样性隐私条件。然而，确定移动用户在线的语义位置是一个挑战，这使得绝对隐私保护的实现更具挑战性。

本文提出了一种保护用户语义位置隐私的连续查询道路网络服务隐私保护算法，贡献如下：

（1）提出一种离线聚类移动用户轨迹的算法，并使用在线导出的移動趋势来帮助选择匿名用户，提高客户端的隐私保护程度。

（2）提出一个生成语义位置图的算法，以帮助确定在线用户的语义位置，利用导出的离线轨迹聚类算法与语义位置图相结合来保护用户在路网下连续查询的语义位置隐私。

1 系统架构及相关知识

1.1 系统架构

为了避免客户端计算量过大，本文采用由移动客户端（MC）、匿名服务器（AS）和基于位置的服务器（LBS）组成的可信第三方体系结构[9]。蜂窝服务提供商为匿名服务器提供了用户的初始轨迹和服务请求（查询内容）数据库。位置和服务请求数据库可以通过客户端定期电话呼叫和LBS查询服务进行获取，如果没有初始数据，匿名服务器会收集几天的位置服务请求数据，在移动用户请求LBS的过程中，将从用户那里获得更多的位置数据。同时允许MC使用隐私配置文件k，即期望匿名的用户数。

系统的核心是AS，AS由隐藏存储库（CR）和离线轨迹聚类引擎（TCE）组成。系统的功能可以定义为：

（1）隐藏存储库保存一些以前隐藏的结果，并使用其来生成新的隐藏区域。

（2）轨迹聚类引擎对移动用户的轨迹数据库进行聚类，结构如图1所示。

1.2 路网模型

道路网由一个有向图G=（V，E）表示，由交叉点V=（n0，n1，...，nn）和定向边E=（（Sid，ninj）| ni，nj∈V）表示。Edge =（Sid，w0，w1，con，ninj）∈e表示连接实际道路网络中2个交叉点ni和nj的路段，其属性包括路段标识符Sid、路段分类w0、交通密度w1和服务请求类型con（sr1，sr2，…，srn∈con，其中每个sr是一个服务请求）。研究中将根据路段的速度限制对其进行分类。路段分为主要路段（限速<40 km/hr）、普通路段（40 km/hr≤限速<70 km/hr）、公路（70 km/hr≤限速<100 km/hr）、高速公路（限速≥100 km/hr），分别用p、a、h、ex表示。因此，路段分类w0可用p、a、h或ex表示。例如，w0=ex表示快速路分类。将用户在时间戳为t和坐标为（x，y）的路段S上的位置表示为l =（Sid，x，y，t）

定义1 轨迹 由TR={tid，l0，l1，…，ln}表示的轨迹，是道路网络上用户随时间变化的位置l0，l1，…，ln的时间顺序序列，由轨迹标识符tid唯一标识。对于一个移动用户来说，对应的行程与起始位置和目的地位置形成一条轨迹。

定义2 语义位置 语义位置是一个区域，在该区域中聚集的用户具有相似的情景信息，如年龄、性别、活动等。学校、医院、公司等都可以是语义位置[10]。

定义3 类簇 对于给定的轨迹集T={TR1，...，TRn}在道路网络上，类簇cw0是在具有相似段分类w0的所有段中的所有段簇csid的集合。因此，类簇是cp、ca、ch、cex，其中每个类簇通常可以表示为cw0。

定义4 集群 对于给定的轨迹集T={TR1，...，TRn}在道路网络上，集群C是所有类簇的集合，即C={cp，ca，ch，cex}。因此，C表示具有段分类w0的所有类簇。

2 轨迹聚类算法及语义位置图

2.1 轨迹聚类算法

聚类算法将数据库对象分组为一组有意义的子类，所以根据用户在同一路段上的相似运动特征，离线将其轨迹聚类成子类[11]。在一个网段内的用户可以被认为是网络接近的，因此在移动中将显示一组子类特征，这些特征将反映该路段上任何在线移动对象的特征。因此，可以从离线特性中估计该对象的加入是否会在将用户伪装成在线特性之前保护客户端的隐私。根据路段id、服务请求、流向、速度、时间、路段长度及其速度限制，将离线移动用户的轨迹聚类成沿路段的子类。利用这一先验信息，提出了一种基于用户轨迹的轨迹聚类算法。考虑一组由T={TR1，...，TRn}表示的一组轨迹在TCE中，检查从第一个位置l0到最后一个位置ln的单个轨迹TRi={tid，l0，l1，…，ln}。取轨迹中每两个连续点，例如li  and  li+1，并使用地图匹配方法检查以获得与2个路段相交的道路交叉点[12]。将获得的连接节点作为新点插入正在检查的轨迹中的li和li+1之间。在检查给定轨迹TRi中的每个点之后，TRi中添加的连接节点序列将作为轨迹分割点，用于沿段将轨迹分割为轨迹碎片（tf）。例如，在图2中，轨迹C具有沿段2和段3断裂的2个轨迹碎片。分析单个轨迹碎片所经过的时间段，并将其分为一天中的不同时间段（tb）。对T中的所有轨迹集重复此过程。

根据路段id、流向、速度（v）、路段长度、行程时间（tb）和该路段的速度限制vL对轨迹碎片进行分组，形成一组基簇。然后，计算出一个段中每个基簇上产生的交通密度w1作为轨迹碎片的数量。交通密度给出一天中给定时间段内具有特定特征用户的可能数量。例如，在图2中，如果所有轨迹片段具有相似的特性，那么段2将具有3的交通密度，而段1具有2的密度。同一段id下的一组基簇构成一个段簇csid。该算法根据b=（Sid，w0，sr，v，w1，tb，ninj）的段id输出一个基本簇，作为tb时该段上的用户特征组。最后，将相似道路分类w0下的所有路段簇抽象表示为cp、ca、ch、cex∈C的类簇，根据路段分类进行抽象，将有助于隐藏具有不同位置语义的用户。一组类簇构成一个C簇，具体描述如算法1所示。

算法1 轨迹聚类算法

输入 <有向图G>， ，

0输出 <集群C = cp，ca，ch，cex>

1：有向图G 由节点 V（ni，nj∈V） 和边E （e∈ E）组成;

2： for TRi，i=1...n do

3：檢查每个li和 li+1以获得路口节点ni;

4：将获得的节点作为新点插入li和li+1之间;

5：使用新的节点将TR分解为tf;

6：为每个e分配唯一标识Sid;

7：将所有tf的tb进行分类;

8：根据Sid， v ， vL， tb， ninj和|ninj|将所有tf 沿着e分组成b;

9： end for

10：在每个b中评估w1;

11：将每个e中的所有b分组为csid;

12：对所有csid 分组 w0和cw0相同;

13：将所有cw0输出为C

2.2 语义位置图

本节中，建立一种语义位置图的算法，以帮助选择要隐藏的用户，从而保护语义位置隐私。将语义位置隐私定义为不同时间点用户访问量，采用用户到访时间作为定义语义位置的标准。例如晚上十点，用户可能访问酒吧、但是不可能访问早餐店，这里可以采用一个时间点来标识一个语义位置。但是晚上九点，用户可能访问娱乐场所、医院等等，仅仅采用一个时间点的用户访问量是不够的，因此采用一个24维的向量来表示语义位置[13]。一个语义位置即如式（1）所示：

其中，L0，L1，...，L23分别表示某一个小时内某个语义位置的用户访问数，其中u是在L0，L1，...，L23提供的服务类别，例如，将诊所、卫生站、医院、牙科诊所等归为“健康”类别，其中“健康”是指提供的服务类别，进行分类是为了避免用类似的服务隐藏用户位置，以增强其语义位置的l-多样性。每个语义位置都有一个特定的区域，比如学校有对应的区域，不在这个区域的位置，就属于别的语义位置，利用语义位置集SL，采用地图匹配的方法在路网模型的各个路段上精确定位相关的位置。然后，生成一个语义位置图G来描述各种语义位置及其提供的服务。语义位置算法如算法2所示。

算法2 语义位置图算法

输入 <有向图G >，

输出 <语义位置图G′>和< SLu>

1：有向图G 由节点 V（ni，nj∈V） 和边E （e∈ E）组成;

2： for Li，i=1，...，n do

3：根据u进行标记L0， L1， L2，.....，L23

4：使得同一组L0， L1， L2，.....，L23在相同u下

5：将每个组输出为SLu

6： end for

7： for Li，i=1...n do

8：插入到G

9：返回G

10： end for

3 隐私保护算法

在这一部分中，使用轨迹聚类算法和语义位置图来开发隐私保护算法。移动客户端（MC）以q=（qid，l，ti，tf，k，sr）的形式发送新的查询q，其中l是位置坐标，ti是查询启动时间，tf是过期时间。服务请求是sr，隐私配置文件k，qid是客户端id。当接收到新的查询q时，AS确定了q的时间，并使用该位置来查找将其发出的段、段的分类、与G中的q相关联的语义位置L以及其所属的服务提供的SLU的类别。

定义一个交通密度阈值σ，低于这个阈值就不适合执行在线隐藏。w1≥σ意味着会在tb时间段找到足够的移动用户。交通密度阈值σ由AS根据历史确定。

为了在线查找匿名MC的用户，TCE搜索除包含MC的类簇cw0以外的所有类簇，随机查找k-1个其他类簇，并从所选类簇中选择一个时间tb满足q时间的基簇。选择的基簇必须满足设计的隐藏条件，以帮助实现采用随机段采样方法的绝对隐私保护。隐藏C条件：全部选定的基簇必须满足以下几方面：

（1）数量是k-1。

（2）第（k-1）个选择的基簇bk-1时间段tbk-1必须满足查询q的时间t和第一个选择的基本簇b1的时间tb1，即t∈tb1;t∈tbk-1。

（3）任何选定的基簇交通密度满足w1（b） ≥σ， w1（b1）≥σ， w1（bk-1）≥σ。

（4）所选基簇sr（bk-1）的服务请求sr（bk-1）不能与q和第一个所选基簇b1的服务请求相同，sr（b1）≠sr（bk-1） ≠sr（q）。

（5）第（k-1）个所选基簇中，由所选段上语义位置L服务提供SLU（bk-1）的类别不应与q和第一个所选基簇b1的类别相同，即SLU（b1）≠SLU（bk-1）≠SLU（q）。

（6）第（k-1）个选择的基簇的段分类cw0（bk-1）不应与q和第一个选定的基簇b1相同，即cw0（bk-1） ≠ cw0 （b1） ≠ cw0（q）。

当满足隐藏条件时，AS将k-1个其他在线用户q'伪装成具有k-1个选定基本簇的特征，这些特征从其各自的段转移到q个隐藏区域，如果不满足这些条件那么所有查询都将被抑制。用户id被删除，并替换为准id，然后将其放入隐藏区域Ri中，其中i代表具有隐藏区域标识Rid的第i个快照。然后将包含k个用户的隐藏区域Ri转发到LBS。

对于连续查询LBS，查询将由AS在周期内（tf-ti）周期性地发出。如果用户请求连续服务，则AS将请求第一个快照的连续服务的用户隐藏起来，以便在整个查询期间保持相同的隐藏用户，从而始终确保隐藏条件。此外，保留一个存储库，其中包含已隐藏的用户请求，以便在以后与同一段相关时使用。满足隐藏条件匿名集的数目用n表示。隐私保护算法如算法3所述。

算法3 隐私保护算法

输入 <查询q = qid， l， k ， ti， tf， sr>， <类簇cw0= （cp，ca，ch，cex） >， < G>， < SLU>

输出 <隐藏区域>

1： for q在t=ti=i发布;

2：确定q的ti， e， cw0， L和SLU;

3：在cw0（b1）≠cw0（q）和ti∈ tb1的e中随机输出基簇 （b1）;

4：确保w1（b1）≥σ， SLU（b1）≠SLU（q）且sr（b1）≠sr（q）;

5：转到10行;

6：for k >2 do

7：使得w1（bk-1）≥σ;cw0（bk-1）≠cw0（b1）≠cw0（q）;sr（b1）≠sr（bk-1）≠sr（q）;SLU（b1）≠SLU（bk-1）≠SLU（q）;

8： end for;

9： if满足7行条件then

10：在各自的e上选择特征为b1到bk-1的在线q';

11：用k-1个其他q'将q隐藏到匿名区Ri中;

12：用准id替换qid;

13：分配区域标识Rid;

14：否则禁止查询;

15： end if

16：将Ri转发到LBS;

17： for t>ti=i do

18：重复执行 2-17;

19： end for

4 安全性分析

本文使用轨迹聚类和语义位置图的算法能够抵御查询同质性攻击、位置同质性攻击。查询同质性攻击指的是攻击者通过当前匿名集发起的相同查询语义来推断出用户的敏感信息。为了避免查询同质性攻击，由于本文算法避免相同服务的2个用户在同一个匿名集中，所以攻击者推出用户的概率为1/k。对于位置相似攻击，本文算法使用不同的分类来隐藏不同位置的用户，保证客户端语义位置链接到用户的概率为1/k。

5 实验及结果分析

5.1 实验数据

本节主要通过实验验证用户在连续查询时与LBS服务器的交互情况、在相关参数变化下对本文算法性能的影响以及与Kamenyi等人[14]提出一种隐私保护算法VD-DCA（Authenticated Velocity-Distance based Dynamic Cloaking Algorithm）方法进行仿真实验比较。

本文实验算法均采用 JAVA 实现，硬件平台为 Intel （R）Core （TM） i5-8265U CPU 1.80 GHz，8 GB内存，操作系统为Microsoft Windows10。实验数据采用真实数据：上海市的公路网络数据[15]，共包括 106 867 个顶点（结点），213 734条道路（边）并从地图上提取20 148个POI，其中包括上海市50个不同类别的服务，作为语义位置。每隔5 s记录了100个快照。实验设置了10 000个发出查询请求的用户，并在上海地图上以不同的速度移动，对其分配了不同的服务请求。根据本文的分类和路段id，对所有路段进行速度限制。

5.2 实验结果分析

本文从成功率、查询处理时间对算法的性能进行评估。对此拟做研究分述如下。

（1）成功率。 定义为活动查询期间内成功隐藏快照的数量n与所有隐藏区域数之比。成功率是衡量一个位置隐私保护算法的有效性的指标，成功率越大，说明隐私保护度越好[16]。其数学公式可写为：

（2）查询处理时间。查询处理时间是算法查找k-1其他用户所需的时间。对于由n个快照组成的活动周期的连续查询，平均隐藏时间T avg可以计算为;

平均隐藏时间越短，说明算法越高效。其中，TRi是查询在区域R中的隐藏时间。

5.2.1 参数变化对性能的影响

通过对k个用户和l个不同段（k-l）值的隐藏区域的快照查询，研究了本文的定义度量效果。快照数与查询处理时间如图3所示。从图3可以看出，第一个快照的处理时间很长，这是因为处理需要很多时间来满足初始隐藏条件。从最初的快照到前十个快照，查询处理时间急剧减少，减少原因可能是隐藏用户在初始查询时请求连续服务，因为会涉及相同的用户，所需时间则会较少。从第10个快照到第20个快照的处理时间略有增加，这可能是由于用户更改了路段，因此需要进行一些处理。此后，处理时间缓慢减少，这种趋势可能是由于引入了存储库查询，从而减少了处理时间。一般来说，即使k-l值增加，查询处理时间也会随着快照的增加而减少。

快照数与成功率的关系曲线如图4所示。从图4可以看出，前10个快照的匿名化成功率几乎保持不变，这是因为用户在ti时查询一直隐藏，因此大多数快照都符合隐藏原则。在第10个快照到第20个快照之间，成功率急剧下降，这是由于移动对象改变了具有不同分类和不同语义位置的片段，因此大多数快照无法满足隐藏条件。此后，由于逐渐引入存储库查询，成功率稳步提高，因此大多数查询都满足隐藏条件。当k-l增加时，也出现类似的趋势。一般情况下，本文算法在评估的100个快照中，每个快照的平均成功率高达为87.8%。

5.2.2 匿名器的性能對比

本节主要从匿名的查询处理时间和匿名成功率两方面将本文方法与 Kamenyi等人[14]提出的隐私保护算法VD-DCA方法进行仿真实验比较，移动客户端将其隐私配置文件设置为k-l=3。

匿名器的性能对比如图5所示。由图5可知，在匿名器的查询处理时间和匿名成功率上，随着快照数增大，本文算法在所有快照值下的性能都优于VD-DCA。因为VD-DCA算法是基于用户的安全特性、速度上的相似性以及采用基于最小生成树的掩蔽机制保护用户隐私。然而，采用基于最小生成树的掩蔽机制会增加掩蔽时间，从而影响系统性能。所以在单个匿名器的查询处理时间和成功率上，本文方法相对于Kamenyi等人[14]的VD-DCA方法有很大优势。

6 结束语

本文通过离线轨迹聚类算法和语义位置图来保护用户当前绝对隐私，同时在真实地图上评估算法的有效性，在整个连续查询道路网络服务的过程中，一定查询处理时间内取得较高的匿名成功率。然而，为了确保这些技术开发能够有效地工作，必须制定有利于保护用户隐私的政策。政策发展与技术考虑同样重要，以便做出必要改变适应技术进步，因此在下一步工作中将会考虑制定隐私保护政策。

参考文献

[1]李志鹏. 位置隐私保护技术的研究[D]. 哈尔滨：哈尔滨理工大学，2018.

[2]PINGLEY A， ZHANG Nan， FU Xinwen， et al. Protection of query privacy for continuous location based services[C]//2011 Proceedings IEEE INFOCOM. Shanghai， China：IEEE， 2011： 1710-1718.

[3]穆良，程良伦. 基于k-匿名位置隐私保护的自适应学习模型[J]. 计算机工程与应用，2017，53（18）：89-94，101.

[4]TRIPATHY B K，MITRA A. An algorithm to achieve k-anonymity and l-diversity anonymisation in social networks[C]//2012 Fourth International Conference on Computational Aspects of Social Networks. Sao Carlos， Brazil：IEEE，2012：126-131.

[5]PAN Xiao， CHEN Weihang， WU Lei， et al. Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services[J]. Frontiers of Computer Science，2016， 10（2）： 370-386.

[6]DAMIANI M L ， SILVESTRI C， BERTINO E.Fine-grained cloaking of sensitive positions in location-sharing applications[J]. IEEE Pervasive Computing， 2011， 10（4）：64-72.

[7]LEE B， OH J， YU H， et al. Protecting location privacy using location semantics[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego， California， USA：ACM，2011： 1289-1297.

[8]曹敏姿， 张琳琳， 毕雪华，等. 个性化（[WT6BZ]α[WT6B1]，l）-多样性k-匿名隐私保护模型[J]. 计算机科学， 2018， 45（11）：180-186.

[9]XIAO P， XING H， XIAOFENG M. Privacy preserving towards continuous query in location-based services[J]. Journal of computer research and development， 2010， 1： 18.

[10]XUE M， KALNIS P， PUNG H K. Location diversity： Enhanced privacy protection in location based services[C]//International Symposium on Location-and Context-Awareness. Berlin/ Heidelberg：Springer， 2009： 70-87.

[11]HAN B， LIU L ， OMIECINSKI E . Road-network aware trajectory clustering： Integrating locality， flow， and density[J]. Mobile Computing， IEEE Transactions on， 2015， 14（2）：416-429.

[12]GUSTAV Y H ， WANG Y ， KAMENYI D M，et al. Query privacy preservation in location based services on road networks[J]. Journalof Computational Information Systems， 2014，10（12）：5255-5263.

[13]黎孟. 基于语义多样性的位置隐私保护算法研究[D]. 长沙：湖南大学，2018.

[14]Figshare.[2018-12-06]. https：//figshare.com/articles/Urban_Road_Network_Data/2061897.

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

[16]KAMENYI D M， WANG Yong， ZHANG Fengli， et al. Authenticated privacy preserving for continuous query in location based services[J]. Journal of Computational Information Systems， 2013， 9（24）：9857-9864.

基金項目： 上海市信息安全综合管理技术研究重点实验室开放研究课题基金（AGK2019004）。

作者简介： 贾媛媛（1995-），女，硕士研究生，主要研究方向：隐私保护、网络信息安全; 史志才（1964-），男，博士，教授，CCF高级会员（No.06601S），主要研究方向：计算机网络与信息安全、隐私保护。

收稿日期： 2021-04-06