Abstract: Provenance sanitization is a new technology that aims at producing secure provenance views by hiding or redacting sensitive nodes,edges or even indirect dependencies in a provenance graph.However,existing research works mostly focus on sanitizing nodes,rarely on sanitizing edges,not on sanitizing indirect dependencies.To this end,this paper first exemplified the motivations and analyzed the challenges of sanitizing indirect dependencies while keeping utility of provenance views,and formally defined goals and constraints of sanitizing indirect dependencies.Second,this paper proposed a novel mechanism for sanitizing indirect dependencies on the basis of the “Delete＋Repair” mechanism for direct dependency in literature.The proposed mechanism includes both deletion rules and repairing rules.Deletion rules specify what edges can be deleted for breaking all connected paths among two end nodes of a sensitive indirect depen-dency while minimizing the sanitization cost.Repairing rules specify what uncertain dependencies can be added for improving the utility of the sanitized provenance views harmed by applying deletion rules.Finally,a comprehensive sanitization algorithm for sanitizing indirect dependency was implemented and experiments was conducted upon an online open dataset.The experiments results show that the proposed approach can effectively sanitize indirect dependencies while preserving utility of the sanitized provenance view.

Key words: Data provenance, Indirect dependency, Information security, PROV-DM, Provenance sanitization