Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2017, Vol. 57 Issue (6): 561-568    DOI: 10.16511/j.cnki.qhdxxb.2017.26.019
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
基于语法推导的溯源依赖关系路径模式挖掘算法
裴继升, 叶晓俊
清华大学 软件学院, 信息系统与工程研究所, 北京 100084
Provenance dependency path pattern mining algorithm based on grammar induction
PEI Jisheng, YE Xiaojun
Institute of Information System & Engineering, School of Software, Tsinghua University, Beijing 100084, China
全文: PDF(1205 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 溯源依赖关系路径模式是基于溯源数据的云数据服务安全策略的重要基础。该文阐述了依赖关系路径模式挖掘的重要意义,提出一种对数据溯源图进行预处理的线性排序算法,使利用自动机模型对溯源数据进行语法推导及解析成为可能;给出了基于自动机语法推导及解析的依赖关系路径间相似度的定义和计算方法;提出一种通用的依赖关系路径模式挖掘算法,在降低领域先验知识要求的前提下,支持溯源规则的自动学习。通过实例研究,验证了该算法在现实应用中的可行性。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
裴继升
叶晓俊
关键词 数据溯源依赖关系路径模式自动机聚类溯源规则学习    
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.
Key wordsdata provenance    dependency path pattern    automata    clustering    provenance based rule mining
收稿日期: 2016-07-01      出版日期: 2017-06-15
ZTFLH:  TP309.2  
通讯作者: 叶晓俊,教授,E-mail:yexj@tsinghua.edu.cn     E-mail: yexj@tsinghua.edu.cn
引用本文:   
裴继升, 叶晓俊. 基于语法推导的溯源依赖关系路径模式挖掘算法[J]. 清华大学学报(自然科学版), 2017, 57(6): 561-568.
PEI Jisheng, YE Xiaojun. Provenance dependency path pattern mining algorithm based on grammar induction. Journal of Tsinghua University(Science and Technology), 2017, 57(6): 561-568.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2017.26.019  或          http://jst.tsinghuajournals.com/CN/Y2017/V57/I6/561
  表1 基本概念定义
  图1 溯源依赖关系路径模式挖掘算法基本流程
  图2 溯源数据线性排列算法
  图3 溯源数据语法推导与解析
  图4 溯源数据语法推导及语法解析算法
  图5 溯源依赖关系路径模式挖掘算法
  图6 目标系统对应自动机模型推导结果
  表2 挖掘得到的溯源依赖关系路径模式
  表3 溯源规则学习决策表
[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.
[1] 肖熙, 徐晨. 基于声学状态似然值得分模型及监督状态模型的语音识别特征融合算法[J]. 清华大学学报(自然科学版), 2019, 59(6): 476-481.
[2] 张继文, 宋立滨, 许君杰, 石循磊, 刘莉. 仿人足球机器人的非预定义足球检测算法[J]. 清华大学学报(自然科学版), 2019, 59(4): 298-305.
[3] 骆歆远, 陈欣, 寿黎但, 陈珂, 吴妍静. 面向室内空间的语义轨迹提取框架[J]. 清华大学学报(自然科学版), 2019, 59(3): 186-193.
[4] 李子浩, 田向亮, 黎忠文, 周炜, 周志杰, 钟茂华. 基于客流规律的地铁车站客流风险分析[J]. 清华大学学报(自然科学版), 2019, 59(10): 854-860.
[5] 马锐, 高浩然, 窦伯文, 王夏菁, 胡昌振. 基于改进GN算法的程序控制流图划分方法[J]. 清华大学学报(自然科学版), 2019, 59(1): 15-22.
[6] 索明亮, 周鼎, 安若铭, 李顺利. 邻域密度网格聚类算法及应用[J]. 清华大学学报(自然科学版), 2018, 58(8): 732-739.
[7] 陈晓方, 钱荧灿, 王雅琳, 阳春华. 基于主元导数特征聚类的加氢裂化动态调整区间识别[J]. 清华大学学报(自然科学版), 2018, 58(1): 81-86.
[8] 肖熙, 周路. 基于k均值和基于归一化类内方差的语音识别自适应聚类特征提取算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 857-861.
[9] 韩东红, 宋明, 张宏亮, 王佳茜, 王嘉兴, 王国仁. 基于密度的不确定数据流聚类算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 884-891.
[10] 方勇, 刘道胜, 黄诚. 基于层次聚类的虚假用户检测[J]. 清华大学学报(自然科学版), 2017, 57(6): 620-624.
[11] 刘书明, 吴以朋, 王晓婷, 刘友飞, 李佳杰. 应用聚类算法识别供水管网爆管事故[J]. 清华大学学报(自然科学版), 2017, 57(10): 1096-1101.
[12] 李煦, 屠明, 吴超, 国雁萌, 纳跃跃, 付强, 颜永红. 基于NMF和FCRF的单通道语音分离[J]. 清华大学学报(自然科学版), 2017, 57(1): 84-88.
[13] 刘杰, 王生进. 融合聚类与排序的图像显著区域检测[J]. 清华大学学报(自然科学版), 2016, 56(9): 913-919.
[14] 谭金华, 石京. 浓雾下高速公路双车道间断放行措施[J]. 清华大学学报(自然科学版), 2016, 56(9): 985-990.
[15] 王志如, 苏国锋, 梁作论. 基于信息传递效率的地铁网络小世界特性评价[J]. 清华大学学报(自然科学版), 2016, 56(4): 411-416.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn