基于语法推导的溯源依赖关系路径模式挖掘算法
Provenance dependency path pattern mining algorithm based on grammar induction

溯源依赖关系路径模式是基于溯源数据的云数据服务安全策略的重要基础。该文阐述了依赖关系路径模式挖掘的重要意义，提出一种对数据溯源图进行预处理的线性排序算法，使利用自动机模型对溯源数据进行语法推导及解析成为可能；给出了基于自动机语法推导及解析的依赖关系路径间相似度的定义和计算方法；提出一种通用的依赖关系路径模式挖掘算法，在降低领域先验知识要求的前提下，支持溯源规则的自动学习。通过实例研究，验证了该算法在现实应用中的可行性。
Abstract：Provenance dependency path patterns are the foundations of many provenance based cloud data security measures. This article analyzes the importance of provenance dependency path pattern mining in provenance based security system with a linearization algorithm for provenance graphs that enables grammar induction and parsing of provenance data using automata models. A similarity measurement method is given for dependency paths based on grammar parsing with a dependency path pattern mining algorithm to reduce reliance on the domain knowledge and support automatic provenance rule learning. The feasibility and effectiveness of the approach are demonstrated by experiments.