Abstract:

Provenance sanitization is a technique to hide sensitive information to generate secure provenance graphs by redacting the nodes, edges or indirect dependencies in the provenance graph. Existing researches of data sanitization mainly focus on sanitizing nodes and edges, rarely on sanitizing indirect dependencies. To this end, an indirect dependency sanitization method for provenance by extending the existing strategy of “delete and repair” is proposed. Firstly, the uncertain usage edge is defined and the rationale of adopting uncertain usage edges to repair the non-sensitive indirect dependencies that are accidentally broken during hiding a sensitive indirect dependency is articulated. Secondly, a sanitization mechanism for indirect dependency based uncertain usage edges is proposed. This mechanism first disconnects the sensitive indirect dependency by deleting the appropriate usage edge in the sensitive path, and then repairs the insensitive indirect dependencies that have been accidentally broken by introducing appropriate uncertain usage edges while minimizing the sanitization cost. The experimental results show that the proposed method can generate sanitized graphs with higher utility while meeting the typical provenance structural constraints, in comparison with existed sanitization mechanisms.

Key words: provenance sanitization, indirect dependency, uncertain usage edge, provenance utility, provenance security

摘要：

起源过滤是通过改造起源图中的节点、边或间接依赖关系，隐藏起源图中的敏感信息，实现起源安全发布的新兴技术。针对现有起源过滤研究主要关注节点和边的过滤，较少研究间接依赖的过滤问题。扩展现有“删除+修复”的间接依赖过滤策略，提出了一种起源间接依赖过滤方法。形式地定义不确定的使用边，并阐明引入不确定的使用边修复被误断的间接依赖的基本原理；提出一种基于不确定使用边的间接依赖过滤机制，该机制先删除敏感路径中的恰当的使用边断开敏感间接依赖，再采用最小代价法引入恰当的不确定的使用边修复被误断的非敏感间接依赖。实验结果表明，与现有的间接依赖过滤机制相比，该方法可以在满足结构约束的同时保持过滤视图的溯源效用。

关键词: 起源过滤, 间接依赖, 不确定使用边, 溯源效用, 起源安全