A core calculus for provenance

DOI10.1007/978-3-642-28641-4_22zbMATH Open1353.68027DBLPconf/post/AcarACP12arXiv1310.6299OpenAlexW2119479592WikidataQ60142679 ScholiaQ60142679MaRDI QIDQ2894337FDOQ2894337

Authors: Umut A. Acar, Amal Ahmed, James Cheney, Roly Perera 

Publication date: 29 June 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Provenance is an increasing concern due to the ongoing revolution in sharing and processing scientific data on the Web and in other computer systems. It is proposed that many computer systems will need to become provenance-aware in order to provide satisfactory accountability, reproducibility, and trust for scientific or other high-value data. To date, there is not a consensus concerning appropriate formal models or security properties for provenance. In previous work, we introduced a formal framework for provenance security and proposed formal definitions of properties called disclosure and obfuscation. In this article, we study refined notions of positive and negative disclosure and obfuscation in a concrete setting, that of a general-purpose programing language. Previous models of provenance have focused on special-purpose languages such as workflows and database queries. We consider a higher-order, functional language with sums, products, and recursive types and functions, and equip it with a tracing semantics in which traces themselves can be replayed as computations. We present an annotation-propagation framework that supports many provenance views over traces, including standard forms of provenance studied previously. We investigate some relationships among provenance views and develop some partial solutions to the disclosure and obfuscation problems, including correct algorithms for disclosure and positive obfuscation based on trace slicing.

Full work available at URL: https://arxiv.org/abs/1310.6299

Recommendations

• Toward a theory of self-explaining computation
• Causality and the semantics of provenance
• Provenance as dependency analysis
• Tracing where and who provenance in linked data: a calculus
• Provenance and privacy

Mathematics Subject Classification ID

Theory of programming languages (68N15) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Authentication, digital signatures and secret sharing (94A62)

Cited In (10)

• Provenance and privacy
• Adaptable Traces for Program Explanations
• Principles of Distributed Systems
• A framework for provenance-preserving history distribution and incremental reduction
• Title not available (Why is that?)
• Provenance propagation in complex queries
• Toward a theory of self-explaining computation
• Tracing where and who provenance in linked data: a calculus
• On the Chase for All Provenance Paths with Existential Rules
• Causality and the semantics of provenance

This page was built for publication: A core calculus for provenance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894337)