基于语法推导的溯源依赖关系路径模式挖掘算法

裴继升; 叶晓俊

doi:10.16511/j.cnki.qhdxxb.2017.26.019

PDF(1205 KB)

清华大学学报（自然科学版） ›› 2017, Vol. 57 ›› Issue (6) : 561-568. DOI: 10.16511/j.cnki.qhdxxb.2017.26.019

计算机科学与技术

基于语法推导的溯源依赖关系路径模式挖掘算法

裴继升, 叶晓俊

作者信息 +

Provenance dependency path pattern mining algorithm based on grammar induction

PEI Jisheng, YE Xiaojun

Author information +

文章历史 +

摘要

溯源依赖关系路径模式是基于溯源数据的云数据服务安全策略的重要基础。该文阐述了依赖关系路径模式挖掘的重要意义，提出一种对数据溯源图进行预处理的线性排序算法，使利用自动机模型对溯源数据进行语法推导及解析成为可能；给出了基于自动机语法推导及解析的依赖关系路径间相似度的定义和计算方法；提出一种通用的依赖关系路径模式挖掘算法，在降低领域先验知识要求的前提下，支持溯源规则的自动学习。通过实例研究，验证了该算法在现实应用中的可行性。

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.

导出引用

裴继升, 叶晓俊. 基于语法推导的溯源依赖关系路径模式挖掘算法[J]. 清华大学学报（自然科学版）. 2017, 57(6): 561-568 https://doi.org/10.16511/j.cnki.qhdxxb.2017.26.019

PEI Jisheng, YE Xiaojun. Provenance dependency path pattern mining algorithm based on grammar induction[J]. Journal of Tsinghua University(Science and Technology). 2017, 57(6): 561-568 https://doi.org/10.16511/j.cnki.qhdxxb.2017.26.019

中图分类号： TP309.2

参考文献

[1] Park J, Nguyen D, Sandhu R. A provenance-based access control model[C]//Privacy, Security and Trust (PST), 2012 Tenth Annual International Conference on. Paris, France:IEEE, 2012:137-144. [2] Sun L, Park J, Sandhu R. Engineering access control policies for provenance-aware systems[C]//Proceedings of the 3rd ACM conference on data and application security and privacy. San Antonio, CA USA:ACM, 2013:285-292. [3] Nguyen D, Park J, Sandhu R. Dependency path patterns as the foundation of access control in provenance-aware systems[C]//4th USENIX Workshop on the Theory and Practice of Provenance. Boston, MA USA:USENIX Association, 2012:4. [4] Nguyen D, Park J, Sandhu R. A provenance-based access control model for dynamic separation of duties[C]//Privacy, Security and Trust (PST), 2013 Eleventh Annual International Conference on. Tarragona, Spain:IEEE, 2013:247-256. [5] 李斌, 王艺霏, 裴继升, 等. 基于溯源数据的业务流程合规性检测[J]. 清华大学学报(自然科学版), 2013, 53(12):1768-1776. LI Bin, WANG Yifei, PEI Jisheng, et al. Business process compliance checking based on provenance data[J]. J Tsinghua Univ (Sci & Tech), 2013, 53(12):1768-1776. (in Chinese) [6] Muniswamy-Reddy K K, Macko P, Seltzer M I. Provenance for the cloud[C]//8th USENIX Conference on File and Storage Technologies. San Jose, CA USA:USENIX Association, 2010:14-15. [7] Groth P, Moreau L. PROV-Overview:An Overview of The PROV Family of Documents[R]. Southampton, UK:W3C, 2013. [8] 叶先一, 张福基. 偏序集上的一种拓扑排序[J]. 数学研究, 2005, 28(4):440-443. YE Xianyi, ZHANG Fuji. A topological sorting in partial order set[J]. Journal of Mathematical Study, 2005, 28(4):440-443. (in Chinese) [9] Carrasco R C, Oncina J. Learning stochastic regular grammars by means of a state merging method[M]//Grammatical Inference and Applications. Berlin Heidelberg:Springer, 1994:139-152. [10] Bergmann R, Müller G, Wittkowsky D. Workflow clustering using semantic similarity measures[M]//KI 2013:Advances in Artificial Intelligence. Berlin Heidelberg:Springer, 2013:13-24. [11] Margo D W, Smogor R. Using provenance to extract semantic file attributes[C]//4th USENIX Workshop on the Theory and Practice of Provenance. San Jose, CA, USA:USENIX Association, 2010:7-7. [12] Chen P, Plale B, Aktas M S. Temporal representation for mining scientific data provenance[J]. Future Generation Computer Systems, 2014, 36:363-378.

PDF(1205 KB)

Accesses

Citation

Detail

段落导航

收稿日期	出版日期
2016-07-01	2017-06-15
发布日期
2017-06-15

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

访问统计

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

访问统计