一种连续查询事件中基于语义的轨迹k-匿名方法

何远德 黄奎峰

1(西南民族大学语言实验教学中心 四川 成都 610041)2(重庆三峡医药高等专科学校 重庆 404120)

0 引 言

轨迹匿名隐私保护技术是近年来网络空间安全领域研究的热点问题之一[1-3]，常用的轨迹匿名技术主要是基于泛化方法的k-匿名查询技术[4]，该技术要求在发布数据中任一当前轨迹在以半径为δ的圆柱范围内，至少包含其他k-1条轨迹，生成一个泛化后的数据包，向客户端提交虚假轨迹组，从而降低当前查询轨迹的辨识率。然而当用户在多个不同时刻k-匿名区域时，例如3个连续查询事件，轨迹T1={P1、P2、P3、P4}，轨迹T2={P3、P4、P6、P7}，轨迹T3={P3、P8、P9、P10}，攻击者比较容易推断发出查询事件请求的为P3用户。

针对传统的k-匿名轨迹隐私保护方法不能直接应用于连续查询，学者们提出了不同的研究思路和观点。文献[5]将真实轨迹位置进行模糊处理，根据历史数据生成虚假用户，并提出了虚假轨迹的距离约束和相似性约束。文献[6]通过匿名框的泛化方法将最初在框中的轨迹继续保留在接下来多个连续查询匿名框中，以避免攻击者对数据信息的推断和识别。文献[7]针对关联查询攻击和运动模式推断攻击问题，利用路网顶点作为锚点提出一种路网兴趣点连续KNN查询隐私保护方法。以上三种方法都采用了匿名框或路网的方式进行隐私保护，但仅考虑轨迹位置与攻击点的匹配程度，忽略了背景知识的语义信息。通过空间关联因素推断并结合特定的领域背景知识，可以将查询条件作为关联最初匿名框的接口，从而对轨迹数据进行攻击，在语义背景下降低了k-匿名的效果。文献[8]针对语义位置攻击和最大运行速度攻击，将语义轨迹隐私问题定义为k-CS匿名问题，实现基于图上顶点聚类的近似算法，进而对图上顶点进行匿名。但这种方法缺少对位置节点语义解释，缺少一个知识库模型，攻击者可以将查询兴趣点所在特定轨迹片段结构作为背景知识进行隐私攻击，构造出至少相同结构和属性的轨迹作为攻击候选集，使目标轨迹导致隐私泄露的概率大于1/k，从而泄露与目标相关的信息[9]。

针对现有轨迹匿名模型难以防范以连续查询为背景知识的攻击问题，利用事件本体对轨迹连续查询进行形式化表示的优点，提出一种连续查询事件攻击中基于语义的轨迹匿名方法。该方法引入OWL[10](Ontology Web Language)对轨迹的身份隐私、地理信息和敏感查询事件进行形式化表示，构建基于事件本体的轨迹匿名模型，利用轨迹综合相似性和Jena推理引擎，给出基于k-匿名的轨迹聚类方法，实现关于当前轨迹的虚假匿名组，最后用实验验证本文方法的有效性和可扩展性。

1 问题定义与模型

1.1 连续查询事件

定义2结构相似查询：存在一条轨迹T映射F，对于轨迹结构的每一个属性，诸如采样点序列、速度、形状、转角、加速等，攻击者通过对轨迹T的相似结构发现隐私数据。从结构相似性带来的轨迹攻击表示为：

其中：εSi强度由结构向量集合Si一致性等因素决定，Contex包含攻击者通过结构属性获取轨迹知识，结构属性的一致性越高，攻击者构造出F的可能性越高。

1.2 事件本体[13]

事件本体技术能够描述某个事件行为的概念及概念之间的关系，形式化表示事件行为的语义逻辑，共享、集成、推理的性能，形成相互连接的无环超图。事件本体在特定的领域本体内，对某个特定时间或环境下发生的表现出的动作特征的形式化描述。通常用表示，ECS表示事件类集合，包含动作(Action)、对象(Objects)、时间(Time)、地点(Place)、内部状态(Status)和语言表现(Expression)6 个要素的知识单元。R表示事件关系集合，Rules采用描述逻辑语言表示事件之间的规则集合。本文针对用户在连续查询事件中存在被攻击者通过内容关联、结构特性和连续查询获取隐私问题，构建基于事件的本体模型E-Ontology，用于抵御攻击者对轨迹数据的隐私窃取。

2 连续查询事件本体建模

2.1 连续查询事件本体模型

事件本体能够对轨迹连续查询进行可共享的明确的形式化规范化说明，本文根据事件本体定义，结合实际研究需求，扩展模型，将其逻辑结构定义为一个五元组E-Ontology={Contexts, Events, Relations, Rules}，其中：

(1) Contexts是查询事件本体中的背景知识与概念分类集合，每个Context表示一个背景概念分类，包括轨迹位置信息、地理环境信息、用户身份和社交关系信息等，所有Context构成一个查询事件背景知识的树形分类结构。

(2) Events是查询攻击事件行为本体分类集合，存储各类攻击事件行为的实例及其属性。本文所述查询攻击事件行为包含内容集、对象集、时间段集、内部状态集和语言描述集等5个要素，其中，内部状态集包括触发条件集和结果集。

(3) Relations表示概念与概念之间的关系集合，不同的事件之间通过关系，形成具有图结构的事件类网络。关系集合包括包含关系(is_a)、组成关系(isComposed of)、因果关系(causal)、并发关系(concurrence)、跟随关系(follow)。

(4) Rules是由逻辑描述语言表示的规则集合，可以通过Contexts、Events、Relations的分类形成推理规则。

2.2 E-Ontology构建

如图1所示，采用OWL对查询事件本体进行构建，OWL具有较强的语义性和知识表达能力，可较好地支持Jena推理引擎。具体构建步骤如下：

(1) 定义基础信息类：基础信息类包括背景知识类和环境信息类，背景知识类(Contexts Class)为一定区域内的地理信息，包含路网顶点、区域、路段、标识、结构等要素，环境信息类包含气象环境(降水数据、能见度)和物理环境(压强、磁场)等要素，这些要素作为基础数据导入本体结构中形成离线的本体结构。从事件本体中自上而下抽象基本类及其层次关系，class表示类中的本体概念，SubClass表示子类，instance表示查询事件的实例，例如Channel是Line的子类，Position1是Channel的实例。

(2) 定义事件类：不同的本体存在不同的抽象类，从多个事件类中抽取事件要素和事件关系，表示事件当前的状态信息和行为特征。例如“Move”是当前查询事件中轨迹的一个状态，它包括从当前路网顶点移出和移入的行为特征，用“InMove”和“OutMove”表示。当多次查询一条轨迹上的路网顶点(P1,P2,P3，…)时，触发事件本体类中各项子类，遍历P1,P2,P3,…在事件类中位置，若存在当前查询轨迹在k个匿名范围实例内的轨迹结构关系或关联因果关系，则进行报警请求。

(3) 设置事件实例：事件实例作为事件类和事件要素的扩充，包含事件发生的具体内容和属性，包含类型、关联强度、因素及约束条件阈值，用Datatype Property表示，细化查询事件内容。当连续查询某个轨迹上的路网顶点时，将这些查询事件存入匿名集，并不断扩展事件实例库。

(4) 定义事件关系：① 包含关系，存在事件类EC1={E1,C1A,C1O,C1T,C1P,C1S,C1E}和EC2={E2,C2A,C2O,C2T,C2P,C2S,C2E}，存在EC1∈EC2，当且仅当C1F∧C2F∧C1I∈C2I∧C1A∧C2A。包含关系存在于事件类之间，如查询路网线段事件与查询路网顶点事件属于包含关系，通常用Ris_a表示；② 组成关系，轨迹事件行为类EC1中的一个实例由事件行为类EC2中的某个实例组成时，则该事件行为类EC1由事件类EC2组成，如“敏感位置查询”由“身份信息查询事件”、“停留查询事件”、“离开查询事件”等组成。组成关系形式化为Rcomp。③ 因果关系，事件类EC1的实例事件发生以一定的概率导致了事件类EC2的实例事件发生，如果发生的概率大于某一阈值，则该两类事件类存在因果关系，形式化为Rcause。例如恶意者攻击发现一条轨迹T上的某个位置P在连续查询事件出现，用户位置P的泄露导致身份隐私被获取，则该事件发生的实例为因果关系。④ 跟随关系，随着数据流的时间推移，事件类EQ1实例和EQ2实例先后发生，则为该两类事件存在跟随关系，形式化表示为Rfollow。例如查询轨迹中位置P1的事件实例EQ1后，进而查询位置P1的事件实例用户出入信息动态EQ2。⑤ 并发关系，在一定时间段内，存在两个攻击事件同时发生或攻击事件发生重合，形式化为Rconcurrence。

图1 基于事件本体的轨迹匿名模型

3 基于k-匿名查询的轨迹聚类方法

由于构建的事件本体模型E-Ontology，在知识推理与服务方面建立在描述逻辑基础上，对动态事件特征的知识无法应用推理，而基于原子动作的动态描述逻辑推理对本体事件要素的概念、关系、实例和公理的可满足性推理没有相关的系统框架可参照。因此，本文提出了一种基于k-匿名查询的轨迹聚类算法，在计算轨迹片段相似度基础上，利用KNN在获取邻近轨迹的优点以及Jena引擎的推理能力，将与当前轨迹相似的k条轨迹进行聚类，从而形成关于当前轨迹的虚假轨迹匿名组。

3.1 轨迹片段相似度计算

(1) 内容关联强度计算：当前查询轨迹内容与E-Ontology中属性及实例之间的近似度。取当前查询轨迹T={(Tv1,Tv2),(Tv2,Tv3),…,(Tvi,Tvj)}，针对集合中的每个路网位置节点Tvi名称对应的本体与E-Ontology中实体名称的文本相似性(Jaccard相似性[14])，并选择文本相似性最大的实体作为该位置节点匹配的实体，记内容关联强度为ε，扩充到当前轨迹片段记为：

(1)

(2) 结构相似度计算：当前攻击查询轨迹结构属性及其实例与E-Ontology中属性及实例的相似程度。取当前查询轨迹T={(Tv1,Tv2),(Tv2,Tv3),…,(Tvi,Tvj)}，遍历E-Ontology，当内容关联命中E-Ontology实体名称时，进一步向子节点属性扩展同时获取叶节点的实例描述，在E-Ontology中选择与当轨迹片段实例最相似的文本作为学习节点，并记为η：

扩展到当前轨迹片段则计算为：

(3)

定义3(综合相似度) 为结构相似度和内容关联度的权重求和，记为：

Sim(vi,Tvj)=θ×A+(1-θ)×S

(4)

按上述方法，对于任意轨迹的综合相似度，构成一个k阶相似度矩阵RSim=(ri,j)k×k。

3.2 基于k-匿名聚类的轨迹查询事件服务

为实现当前查询的轨迹与E-Ontology实例相似度最高的k-1条轨迹，形成一个关于当前轨迹的匿名组，本节在语义本体模型和轨迹相似度的基础上，实现轨迹的k-匿名。算法的基本思路是：在以半径为δ的区域内，截取当前查询轨迹片段，采用综合相似度计算当前轨迹片段与E-Ontology实体、属性和实例，选取最大的k-1条轨迹，并遍历整条轨迹，生成关于当前轨迹的虚假轨迹组。最后将学习到的知识更新到语义本体库中，作为新的相似匿名实例，从而增强轨迹匿名的语义性。如算法1所示。

算法1基于k-匿名聚类的轨迹查询事件服务

输入：当前查询轨迹Tq，轨迹位置节点V(Tq)，参数k表示k条轨迹，参数θ表示相似权重，Tont表示E-Ontology

输出： 匿名轨迹组Tp

步骤：

1. Initθ=0.5,V(Tq),Vi,Tont,i=0;

2. OntModelTont=ReasonerFactory.CreateReasoner()

//通过Jena推理引擎获取E-Ontology实体

3. For EachV(Tq)0

Vi++={V(Tq)}

//通过参数Vi进行增量存储

//当前轨迹位置节点V(Tq)

Rsim=calculating(Vi,Tont,θ)

//计算当前查询轨迹片段

//与E-Ontology形成的k阶矩阵

min=MinDistance(Rsim)

//取输入轨迹点距离最小间隔的轨迹

Vij=∅,j=0

//初始化k阶矩阵的列j

For |Rsim|<=kandj

Vij+=max(Tont.Reasoner(Vi),min)

//通过Jena的Reasoner API获取相似度最大的轨迹

Tp[]=Vij

//最终结果存入Tp[]

End For

End For

ReturnTp

算法1中，步骤1有关参数选取：给定当前查询轨迹Tq，选取相似权重θ=0.5，主要是平衡结构相似度和内容关联度的权重，参数k表示从当前区域内获取的k条轨迹，V(Tq)表示轨迹的位置节点编码，初始化为0，通过参数Vi进行增量存储，并可以调用Rsim求出k阶相似度矩阵，时间复杂度为O(n2)；步骤2通过Jena推理引擎生成E-Ontology模型库；步骤3先计算当前查询轨迹片段与E-Ontology形成的k阶矩阵，然后实时泛化当前轨迹结点的k匿名数据，将相似度最大的k条轨迹存入当前匿名组，形成关于当前轨迹的虚假轨迹。算法根据轨迹片段相似度将当前查询轨迹片段将和E-Ontology的实体、属性和实例相似的轨迹片段进行聚类，进而扩充到整条轨迹。

4 实验结果分析

4.1 实验数据

为了验证本文方法的有效性，考虑经典匿名聚类算法NWA[15]和(k,δ)-anonymity[15]在信息损失、近邻查询准确度、执行效率三个方面与本文方法的可比性，由此进行实验对比分析。实验数据采用Thomas Brinkhoff基于路网的移动对象生成器和和AIS信息服务平台共同合成的上海近岸地区移动对象的数据集生成的网络，包括查询范围δ、对象数、轨迹点和数据量，如图2所示。

图2 系统中生成的数据集网络

实验环境在Intel Core 2 Quad 2.4 GHz Windows 10 系统上运行，服务器架构在IBM 3650xm 上，采用Linux Asia 3x 版本，系统数据库为IBM DB2，算法采用Java语言和Jena推理包实现。考虑算法在随机选取轨迹初始节点会导致匿名结果的差别，实验重复不少于5次，结果取平均值。

4.2 性能分析

本次实验从信息损失、查询准确率和执行效率三个方面与不同的k-匿名方法进行性能比较，通过实验讨论算法的性能。

(1) 信息损失比较。本文方法构成的信息损失来自查询事件轨迹位置节点的匿名聚类造成的内容泛化和结构隐匿的信息损失。因此，采用用户错误访问子空间轨迹片段数与当前轨迹片段数之比作为度量轨迹信息损失的标准。

图3给出了不同方法随着k值的增加信息损失量的变化，实验表明：与NWA和(k,δ)-anonymity相比，在k值为8～10时本文方法降低了15%～20%，因为本文方法构建了基于事件本体的匿名模型，针对轨迹信息的语义知识不足进行扩展改进，对输入轨迹动态判断，采用Jena推理引擎将当前轨迹与历史轨迹存储与一个匿名组保证匿名信息的相对完整性。

图3 随着k值增大，三种方法的信息损失率

(2) 查询精准率。在使轨迹数据匿名隐私保护的同时，又保证用户查询的精准性。以基于k-匿名查询的轨迹聚类方法生成的匿名组Tp与当前真实查询轨迹Tq为中心进行近邻查询，查询内容为用户提交的LBS轨迹位置节点请求；Tp和Tq为结果集数量，使用查询准确率POI来衡量服务质量，其计算方式如下所示：

如图4所示，随着k值的增加，在半径δ为100～600 m的范围内查询精准率保持在65%以上，实验表明：本文方法通过Jena引擎将当前轨迹与E-Ontology匹配，使得在轨迹距离上的划分粒度更为精细，因此在当前匿名轨迹与实际轨迹的距离较小，误差在半径范围较大时保持平衡。

图4 不同距离下近邻查询精准率

(3) 执行效率。为考察本文算法的执行效率，采用运行时间作为执行效率的度量标准。图5给出了随着k的增大，相对于NWA和(k,δ)-anonymity，本文方法的运行时间相对减少并且平均低于20秒。实验表明：本文对内容和结构独立计算且只进行一次就生成了k阶矩阵，而基于事件本体的匿名模型的计算深度通过Jena API直接调用，效率较高，因此开销时间较小。

图5 随着k值增大，执行时间的变化

5 结 语

本文采用OWL形式化表示轨迹数据及查询事件，提出一种连续查询事件中基于语义的轨迹k-匿名方法，构建事件本体模型，并结合轨迹片段相似度计算和Jena推理引擎，提出基于k-匿名查询的轨迹聚类方法。该方法可以防止攻击者窃取用户轨迹数据，维护公共安全。然而数据规模扩大伴随着k值的增大，轨迹数据的不确定性可能影响推理的准确性，后续工作将在原始数据采集和提高匿名质量及匿名算法方面做深入研究。