随着开放环境下云服务数据量的不断增大、用户类型的不断多样化以及相关业务流程的日渐复杂，传统的静态访问控制规则显现出灵活性方面的不足。基于近年来快速发展并获得普遍认可的数据溯源技术，文[1-4]广泛研究并阐述了溯源数据及溯源规则在访问控制领域和业务合规领域^[5]方面的应用。然而面对庞大的数据用户规模及复杂的安全控制需求^[6]，溯源规则中所包含的溯源依赖关系路径模式引用及约束条件日趋复杂。溯源依赖关系模式及相关约束若完全依靠人工设计，则不仅工作量及成本巨大，还容易出现错漏，因此迫切地需要从历史溯源数据中自动学习提取出溯源规则的方法。

溯源依赖关系路径模式是溯源规则的基本组成部分，决定了溯源规则的描述能力。在溯源规则学习的过程中，溯源依赖关系路径模式的粒度和语义直接影响规则学习的正确性及全面性。为降低对领域相关知识及领域专家参与的依赖，迫切需要一种对应用领域先验知识要求尽可能低的方法，来挖掘溯源数据中具有代表性的溯源依赖关系路径模式。

本文主要研究无人监督情况下溯源依赖关系路径模式的挖掘与生成的问题，并采用有限状态自动机推导技术，建立溯源依赖关系路径与目标系统各运行状态之间的映射关系，从而根据各溯源路径在系统状态语义上的异同自动进行模式挖掘。该方法将有利于提高基于溯源依赖关系路径的多种安全技术在云服务环境中的应用潜力与可扩展性。

为便于理解，本节对溯源数据、依赖关系路径模式、溯源规则以及溯源规则学习等基本概念进行介绍，并给出溯源依赖关系路径模式挖掘的问题描述。

溯源数据是记录云数据服务中数据衍生过程、相关业务流程发生过程以及所涉及人员信息的历史信息，其中不仅包括所发生数据业务流程中数据、人员、过程等各对象自身的属性信息，还包括对象之间的因果依赖关系如使用、产生、控制等。本文基于由国际万维网联盟(W3C)提出的、获普遍认可的溯源数据模型^[7]，将溯源数据直观地表示成有向无环图的的形式。溯源模型定义如表 1所示，其中溯源图的顶点包括实体(entity)、活动(activity)和参与者(agent)等基本节点类型，溯源图中的有向边表示溯源数据中的各对象之间的依赖关系，并以不同的边标注来刻画不同的依赖关系，包括使用、被产生以及被控制等基本依赖关系。

溯源图中相邻节点之间的有向边所对应的依赖关系称为简单依赖关系或基本依赖关系。通过把代表基本依赖关系的有向边联接成路径的形式，可以得到依赖关系路径(dependency paths)^{[1, 3]}，用于表示节点之间更为多样化的复合依赖关系。

由基本依赖关系组成的正则路径表达式所表示的依赖关系路径集合，可以描述路径的起始节点与满足该路径表达式的终结节点之间的一类因果依赖关系，故称为溯源依赖关系路径模式^[3]。然而，溯源依赖关系路径模式的描述目前完全由业务人员手工设计，费时费力，缺乏通用的自动获取方法。

溯源规则是针对溯源数据中特定部分的值之间相互关系的限定和约束，在云数据服务安全中有着广泛的应用，如文[1-4]提出的基于溯源数据的访问控制规则、文[5]提出的基于溯源数据的合规性检验规则等。溯源规则表达式由操作数和运算符2种元素组成，其中操作数为利用溯源起始节点及溯源依赖关系路径模式表示的溯源数据实例以及其他必要的数据常量。针对所获取的溯源数据，从起始节点出发，按照溯源依赖关系路径模式进行追溯，查找满足其正则路径表达式的溯源节点，即可获取与该规则相关的溯源数据实例集，并通过集合运算符、逻辑运算符等来表示对相关溯源数据的基数约束、包含关系约束、时间顺序约束和数据值约束等约束条件。

溯源规则学习是通过挖掘历史溯源数据及相应安全控制历史记录，发现溯源数据中特定部分的值及其相互关系对安全需求的影响，从而得到用于保证安全需求的溯源规则。其中需要对溯源起始节点、溯源依赖关系路径模式以及安全需求所对应的约束条件等对象进行自动挖掘。

为尽可能减少对领域先验知识的要求，本文考虑在仅给定原始溯源数据及基本依赖关系信息的情况下，如何在原始溯源数据中挖掘得到具有代表性语义的溯源依赖关系路径模式。为此需要建立溯源依赖关系路径与目标系统状态变化之间的映射关系，利用其反映的各依赖关系路径语义的异同进行路径模式挖掘。

溯源依赖关系路径模式挖掘首先将具有相同或相似语义的路径实例归为一组，再对每组实例进行正则路径语法归纳，抽象出对应的溯源依赖关系路径模式。因此，对路径实例语义的理解及分类粒度的选择尤为关键。

在实际业务系统中，语义相同的依赖关系路径可能呈现多种流程结构，流程结构本身难以反映出用户操作的行为语义，因此一些基于流程结构特征的传统溯源数据聚类算法及分类器学习算法难以给出合适的语义分组。为解决这一问题，在缺乏领域相关先验知识的情况下实现合理的语义比较以及分组，本算法采用由原始溯源数据推导而得的有限状态自动机对目标系统状态进行描述，通过自动机语法解析，将溯源依赖关系路径映射到与之对应的目标系统各状态上，从而达到刻画各依赖关系路径所蕴含的语义，并对其按语义进行分组与模式归纳的目的。如图 1所示，算法的大致步骤如下。

图 1 溯源依赖关系路径模式挖掘算法基本流程

图选项

步骤1 溯源数据预处理：为使用原始溯源数据作为样本推导目标系统的有限状态自动机模型以及支持后续的语法解析，首先要基于基本依赖关系对溯源数据进行线性化和符号化(仅使用基本依赖关系作为输入)，得到符号序列。

步骤2 自动机语法推导：将线性化及符号化后得到的符号序列作为样本数据，选用自动机语法推导算法学习得到描述目标系统行为模式的有限状态自动机模型。

步骤3 溯源符号序列语法解析：使用所得到的描述目标系统行为的自动机模型，对溯源数据实例对应的符号序列进行语法解析，从而得到溯源数据实例中各基本依赖关系边上的系统状态语义标注。

步骤4 溯源依赖关系路径模式挖掘：将具有相同系统状态语义标注的溯源依赖关系路径实例归为一组，利用语法推导得到对应的基于正则路径表达式的溯源依赖关系路径模式。

步骤5 挖掘结果应用及验证：将挖掘得到的溯源依赖关系路径模式应用于候选溯源规则的生成，进行溯源规则学习，验证所挖掘模式在规则学习中的应用效果。

溯源数据一般以有向无环图形式存在，为使其能够通过有限状态自动机解析，需要进行线性化，将其转化为序列数据。而为了提取具有一定语义特征的溯源路径模式，在预处理时应将溯源信息中具体数据内容、人员属性等细节略去，只保留溯源边上的基本依赖关系类型标签，降低数据维度，使其适于模式挖掘，进而将各溯源边按其时序进行排列，形成线性的溯源边序列，便于自动机相关处理。

为使线性化后的基本依赖关系序列尽可能保留系统运行过程的原始特征，排列的过程中须遵循一定的原则。在具体介绍前，首先引入以下定义。

定义1 溯源边线性序列：对某溯源数据实例PD= <V, E, D>，及序列S=(e₁, e₂, …, e_n)，n ≥1，若有∀e_i=(v_i1, v_i2, d_i)∈S, e∈E，则S称为PD的一个溯源边线性序列，记边e在序列S中的序号为pos_S(e)，并记S中各边依赖关系类型所生成的线性序列为π_d(S)=(d₁, d₂, …, d_n)。

定义2 活动依赖性：对溯源数据中任意2个活动a₁, a₂∈A，若存在边e₁, e₂∈E及数据对象o∈O，满足e₁=(o, a₁, g), e₂=(a₂, o, u), 其中u∈U，g∈G，则称活动a₂依赖于活动a₁。

定义3 节点入度集合：对任意溯源节点v，称α(v)={e=(w, v, d)∈ E | d ∈ D}为溯源节点的入度集合。

定义4 节点出度集合：对任意溯源节点v，称β(v)={e=(v, w, d)∈E | d ∈D}为溯源节点的出度集合。

定义2可直观理解为假如某活动a₂使用了由另一活动a₁产生的数据对象，则称活动a₂依赖于活动a₁。基于上述定义，为使溯源数据线性化结果能尽可能反映原有溯源图中的依赖关系信息，本文提出溯源边线性排列S所须满足的基本性质如下。

1) 局部依赖保序性：对于任意a₁∈A，则对任意e_i∈α(a₁)，e_j∈β(a₁)，应有pos_S(e_i) < pos_S(e_j)，且对于任意e_x, e_y∈α(a₁)∪β(a₁)有|pos_S(e_x)-pos_S(e_y)|≤α(a₁)∪β(a₁)(在排序结果中构成一连续区间)；

2) 整体依赖保序性：对于任意a₁, a₂∈A，若a₁≺a₂，则对任意e₁∈α(a₁)，e₂∈β(a₁)，e₃∈α(a₂)，e₄∈β(a₂)应满足pos_S(e₁) < pos_S(e₂) < pos_S(e₃) < pos_S(e₄)。

依据上述性质可以证明，符合要求的线性排列集合{S}是溯源图边集E的所有可能拓扑排序方案的一个子集。其中性质1保证了同一活动节点的各入度和各出度前后邻接进入线性排列。结合性质1含义可知，性质2实际上保证了活动节点之间的先后顺序必须满足定义在活动节点集A上的偏序关系“≺”所导出的拓扑排序顺序。由于可能同时存在多种可行的活动节点的排序方案，因此面临如何选取一个更趋于合理的排序方案的问题^[8]。为保持线性排列的一致性，本文通过引入效用函数的方式选取一个确定的排序方案，并根据上述基本性质给出溯源数据线性排列算法1(见图 2)。

图 2 溯源数据线性排列算法

图选项

算法1中序列追加操作append函数的定义为

即得出将某元素追加在原序列后形成的新序列。

算法1第11行所使用的效用函数定义为

该函数为用户自定义的效用函数，表示在满足排序性质2(整体依赖保序性)的情况下，活动a′出现于当前活动序列S_A后的合理性，越接近1的值表示将a′追加于S后越合理。效用函数μ的设计依据目标系统业务流程的特点及语法推导的需要而定，其目的是在各种可能方案中选择更为符合系统运行特征的排序结果。如函数

其中dist(a_n, a′)表示原序列尾部的边与新加入边之间的最短距离(假设边长度均为1)。进行排序时，该效用函数将鼓励优先加入与刚刚加入的溯源边相邻或接近的边，因而线性化结果将集中反映系统中连续工作流的运行特征。再如

其中I_a′=an为指示函数，当a′=a_n时为1，否则为0。该函数能在特定的情况下鼓励加入并行执行的具有相同依赖关系的溯源边，从而反映系统并行执行相同过程的相关特征。面对具体问题，可进行不同效用函数的具体设计及配合使用。

为实现性质2，算法1在排序过程中将已进入排序序列的溯源节点标为“已就绪”，并不断选取入度节点均已就绪的活动节点(表示其依赖的活动均已处理完)相关的溯源边放入线性排序序列。算法1首先将入度为0的节点设为已就绪(第4-6行)，并找出所有入度端点均已就绪的活动节点，初始化就绪活动节点集T(第7-9行)，再根据效用函数从T中取出效用值最大的活动节点加入S_A序列(第10-12行)，并将其相关依赖关系边加入序列，并实现了定义1(第13-19行)，同时将新增的数据对象节点标记为已就绪(第18行)，第20-24行根据新增就绪节点的情况更新就绪活动节点集T，并循环执行，直至所有活动节点均完成处理。

如图 3所示，在本步骤中，通过语法推导，可将溯源数据实例集作为样本，推导自动机中的各状态及状态之间的迁移规则。根据所获得的描述目标系统行为特征的自动机，将左边溯源数据中的各溯源边赋予状态语义。

图 3 溯源数据语法推导与解析

图选项

溯源数据一般通过记录系统实际运行过程得到，难以获得反例样本，因此作为本研究的起始工作，本文选择相关研究较为充分、与正则语言有对应关系的有限状态机模型来刻画目标系统特征，并使用通过正例样本推导有限状态自动机模型的推导算法。符合这一需求的推导算法有很多，各具特点和优势。本文在案例研究中使用的是Carrasco等^[9]提出的较为直观的经典算法(Alergia算法)，基于相似状态合并的思想进行语法推导。

根据上述分析，给出如图 4所示的溯源数据语法推导及语法解析算法2。该算法首先调用算法1，将溯源数据集中的各溯源数据实例进行线性化，并将得到的线性溯源边序列(S_Ei)所对应的基本依赖关系序列(S_di)作为输入符号语料加入到语料库W中(第1-7行)，进行自动机推导，得到的有限状态机模型记为(Σ, S, s₀, δ, F)(第8行)。其中Σ为字母表，S为状态集合，s₀为起始状态，δ为状态转移函数，F为结束状态集合。注意到字母表由溯源数据中的依赖关系集D组成。得到推导结果后，即根据所得有限状态机模型对各原始溯源边序列进行语法解析，将各基本依赖关系输入之前及之后的系统状态，作为该溯源边中基本依赖关系及其逆关系的语义描述信息，加入到带语义扩展的溯源边集及逆边集中(第12-14行)，并更新当前状态(第15行)。加入状态信息后的溯源边集(E_S)及逆边集(E_S^-1)将带有状态语义标签，见定义5。而由此所得的对应溯源数据也因此称为带语义标签的溯源数据，记为PD_S= < V, E_S, E_S^-1, D>，并加入到最终要返回的带状态语义标签的溯源数据集Ω_S中(第16行)。

图 4 溯源数据语法推导及语法解析算法

图选项

定义5 带语义标签的溯源边集及其逆边集：

其中S为所得有限状态机的状态集。

基于上述带状态语义标签的溯源数据集Ω_S，可以得到溯源边间在状态语义上的相似性，从而给出依赖关系路径实例之间的相似性度量，支持模式聚类挖掘。首先，任意两条带状态语义标签的溯源边e₁(w₁, v₁, d₁, s₁), e₂(w₂, v₂, d₂, s₂)∈E_S∪E_S^-1之间的相似性定义如下：

其中sim_S(s₁, s₂)为其对应自动机状态之间的相似性，由各状态在接受输入符号及状态迁出上的相似性决定，定义为

其中A₁及A₂分别是状态s₁, s₂所能接受的符号(基本依赖关系类型)的集合。

根据溯源依赖关系路径的定义，由溯源边前后相连组成的溯源依赖关系路径实例可表示为

其中：e_pi=(v_pi, v_pi+1, d_pi, s_pi)∈E_P且E_P⊆E_S∪E_S^-1, v_pn+1∉A, 1≤i≤n，并称E_P为路径P的边集，注意到v_pn+1∉A即序列必须以非活动溯源节点结束。对于2条溯源依赖关系路径实例P, Q，借鉴文[10]中方法，将二者间的相似度化约为其各溯源边之间的相似度计算，通过引入定义在两者边集间的单射m: E_P→E_Q将P中的边(记为e_pi)映射到Q中对应的边(m(e_pi))进行比较，即计算sim_E(e_pi, m(e_pi))。给定映射m，为整体比较P与Q的相似性将各sim_E(e_pi, m(e_pi))的值进行加权求和(要求归一化条件)，即可得到关于映射m的溯源依赖关系路径相似度，记为sim_m(P, Q)。选取使sim_m(P, Q)最大的映射m，并确定相似度值，即：

由于sim(P, Q)的非对称性，最终用于聚类分析时，通过下式将相似度转化为对称的P、Q间距离：

图 5总结并描述了溯源依赖关系路径模式挖掘的流程。第1-10行按照上述相似性定义给出溯源依赖关系路径实例之间的相似性度量及距离度量，并进行聚类分析(具体聚类算法可根据实际情况及效果选择)。得到溯源数据实例按其语义分组的结果后，提取出每组中各溯源路径实例，将其对应的基本依赖关系序列加入语料库(第13-16行)，并对每组的语料库进行语法推导(第17行)，生成相应的依赖关系路径模式。

图 5 溯源依赖关系路径模式挖掘算法

图选项

在算法1中，为快速检验节点入度数，可构建并维护一个入度数组，构建入度数组的复杂度为O(e)，e为图的边数；算法执行时，每条边产生一次加入序列S_E的操作，复杂度亦为O(e)，同时每个活动节点产生一次进入节点集T的操作和移出节点集T的操作，其中每次发生进入操作时需要维护节点集T中各μ(S_A, a)的最小值，若用最小堆实现则复杂度为O(log₂|T|)=O(log₂|A|)，故算法复杂度为

其中n为顶点总数(注意到|A|=O(n))。

算法2对每一个溯源数据实例调用算法1，因此其复杂度为

其中n_m、e_m分别为各溯源数据实例所包含节点数及边数的最大值。算法2第8行语法推导的复杂度则因溯源数据规模及语法模型推导算法而异，而在之后的执行过程中，每一条简单依赖关系边均引起两次基本依赖关系插入操作，因此复杂度为

在算法3中，任意两个状态间之间相似度计算(第2-4行)复杂度为O(|S|²)，而依赖关系路径间相似度计算(第6-9行)复杂度为O(c|Γ|²)，其中，计算每对依赖关系路径相似度的开销在假定依赖关系路径的长度相对稳定的情况下可设为一常数c。而后续的聚类分析过程复杂度则与采用的具体方法有关。在最后的正则语法推导过程中，若假设依赖关系路径的长度相对稳定，则其复杂度为O(k|{C_i}|)，其中k对应每次执行正则语法推导的时间开销。可见，除自动机语法推导与聚类分析的复杂度存在变化之外，各算法其余部分的复杂度增长相对于溯源数据规模而言均控制在线性或多项式时间内，总体而言具有较高的效率。

为将得到的溯源依赖关系路径模式用于溯源知识学习，对训练集中的溯源数据采取以下4个步骤：1) 选择溯源规则相关的溯源起始节点；2) 进行溯源依赖关系路径模式挖掘；3) 利用路径模式生成候选约束条件；4) 测试候选约束条件，生成溯源规则。

步骤1中通过选择合理的起始节点，可减少依赖关系路径模式数量及规则学习开销。例如在基于溯源的访问控制中^[11]，选择访问请求的目标对象为起始节点；在基于溯源的合规性检验中，选择合规性要求所对应的业务控制点^[5]中各起始节点。步骤3中即如节1.3所述，将挖掘所得模式与集合运算符、逻辑运算符、关系运算符等结合，表示对相关溯源数据的各种约束。步骤4则通过前期采集的训练数据，将访问行为合法性、业务合规性等信息作为分类标签，训练出最终的分类规则，从而得到相应的溯源规则表达式。

以文[2]中作业评改系统访问控制场景为例，合成了用于测试的溯源数据集，针对其中“grade”操作，根据文[12]中的对应规则，对所合成溯源数据集中各实例附上访问行为是否合法(valid/invalid)的先验知识标签。对所合成的测试溯源数据集，调用算法1进行溯源线性化，并调用算法2对算法1得到的各线性序列进行自动机推导，得到如图 6所示的有限状态机模型。基于该自动机模型调用算法3进行溯源依赖关系路径模式聚类后，限定以“grade”操作所使用的数据对象作为溯源起点，获得的路径模式(去冗余后)见表 2。利用这些溯源依赖关系路径模式，生成候选约束条件，并利用分类器基于训练溯源数据对各约束条件进行筛选，输出决策表，见表 3。

图 6 目标系统对应自动机模型推导结果

图选项

根据表 3，可知对某作业进行“grade”操作的合法性成立的约束条件是该作业曾至少得到过两份意见, 而对应的基于溯源访问控制规则为

限于篇幅，本例涉及的溯源起点和溯源规则较为单一，但同样的思路可以扩展运用于多规则、多溯源起点的场景，可开展更多实例的分析及算法调优讨论。

本文提出了一种领域无关的溯源依赖关系路径模式挖掘算法，该算法以线性化排序、自动机语法推导及语法解析对溯源数据进行处理，获取语义信息，给出了溯源路径语义的相似性定义，从而实现了基于相似性聚类分析的路径模式挖掘。实验研究展示了算法的可行性及有效性。与现有的溯源数据挖掘技术相比，通过自动机推导及语法解析能够获取并利用系统状态变化的特征信息，具有在特征语义上的优越性。该方法将为大数据云服务环境下安全溯源规则自动学习的相关研究提供重要基础。下一步将研究模式挖掘结果在现实系统溯源规则学习中的更多应用、不同自动机模型及聚类算法的应用效果对比等。