A core calculus for provenance inspection

ABSTRACT

Recent research has been devoting increasing attention to provenance, or information describing the origin, derivation, and history of data, due to its relevance to critical issues including transparency, privacy, and security. Engineering a software system to make it provenance-aware by means of ad-hoc instrumentation requires a substantial effort: the development of general-purpose infrastructure is thus very important to achieve the goal of making provenance widely available. In this article we describe a core functional language equipped with a provenance-aware semantics that is sufficiently generic to accomodate many notions of provenance proposed in the literature. While existing proposals typically treat provenance views and provenance extraction as second-class, extralinguistic mechanisms, in our work provenance views are expressed as standard programs and provenance data can be reflected into the language, allowing for programs that inspect their own provenance.

References

1. U. A. Acar, A. Ahmed, J. Cheney, and R. Perera. 2013. A core calculus for provenance. Journal of Computer Security 21 (2013), 919--969.
2. F. Bavera and E. Bonelli. 2015. Justification logic and audited computation. Journal of Logic and Computation (2015). Published online, June 19, 2015.
3. David A. Bearman. 1985. The Power of the Principle of Provenance. Archivaria 21 (1985), 14âĂŞ27.
4. Deepavali Bhagwat, Laura Chiticariu, Wang-Chiew Tan, and Gaurav Vijayvargiya. 2005. An annotation management system for relational databases. VLDB Journal 14, 4 (2005), 373--396.
5. Rajendra Bose and James Frew. 2005. Lineage retrieval for scientific data processing: a survey. ACM Comput. Surv. 37, 1 (2005), 1--28.
6. Uri Braun, Avraham Shinnar, and Margo I. Seltzer. 2008. Securing Provenance. In HotSec.
7. Peter Buneman, James Cheney, and Stijn Vansummeren. 2008. On the expressiveness of implicit provenance in query and update languages. ACM Transactions on Database Systems 33, 4 (November 2008), 28.
8. Peter Buneman, Sanjeev Khanna, and Wang-Chiew Tan. 2001. Why and Where: A Characterization of Data Provenance. In ICDT (LNCS). 316--330.
9. J. Cheney. 2011. A formal framework for provenance security. In Proceedings of the 24th IEEE Computer Security Foundations Symposium (CSF). IEEE, 281--293.
10. James Cheney, Amal Ahmed, and Umut a. Acar. 2011. Provenance As Dependency Analysis. Mathematical. Structures in Comp. Sci. 21, 6 (Dec. 2011), 1301--1337.
11. Yingwei Cui, Jennifer Widom, and Janet L. Wiener. 2000. Tracing the lineage of view data in a warehousing environment. ACM Trans. Database Syst. 25, 2 (2000), 179--227.
12. Susan B. Davidson and Juliana Freire. 2008. Provenance and Scientific Workflows: Challenges and Opportunities. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD '08). ACM, New York, NY, USA, 1345--1350.
13. Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy, and Sarah Cohen Boulakia. 2010. Privacy Issues in Scientific Workflow Provenance. In Proceedings of the 1st International Workshop on Workflow Approaches to New Data-centric Science (Wands '10). ACM, New York, NY, USA, Article 3, 6 pages.
14. Boris Glavic and Gustavo Alonso. 2009. Provenance for Nested Subqueries. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '09). ACM, New York, NY, USA, 982--993.
15. Boris Glavic, Renée J. Miller, and Gustavo Alonso. 2013. Using SQL for Efficient Generation and Querying of Provenance Information. In In Search of Elegance in the Theory and Practice of Computation. 291--320.
16. Kwan Hee Han, Seock Kyu Yoo, and Bohyun Kim. 2009. Qualitative and Quantitative Analysis of Workflows Based on the UML Activity Diagram and Petri Net. WSEAS Trans. Info. Sci. and App. 6, 7 (July 2009), 1249--1258. http://dl.acm.org/citation.cfm?id=1639420.1639437
17. Ragib Hasan, Radu Sion, and Marianne Winslett. 2007. Introducing Secure Provenance: Problems and Challenges. In Proceedings of the 2007 ACM Workshop on Storage Security and Survivability (StorageSS '07). ACM, New York, NY, USA, 13--18.
18. Zachary Hensley, Jibonananda Sanyal, and Joshua New. 2013. Provenance in Sensor Data Management. Queue 11, 12, Article 50 (Dec. 2013), 14 pages.
19. Jan Hidders, Natalia Kwasnikowska, Jacek Sroka, Jerzy Tyszkiewicz, and Jan Van den Bussche. 2007. A Formal Model of Dataflow Repositories. In Proceedings of the 4th International Conference on Data Integration in the Life Sciences (DILS'07). Springer-Verlag, Berlin, Heidelberg, 105--121. http://dl.acm.org/citation.cfm?id=1768933.1768947
20. Wilmer Ricciotti and James Cheney. 2017. Strongly Normalizing Audited Computation. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Valentin Goranko and Mads Dam (Eds.), Vol. 82. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 36:1--36:21.
21. Wilmer Ricciotti, Jan Stolarek, Roly Perera, and James Cheney. 2017. Imperative functional programs that explain their work. In ICFP 2017. In press.
22. T. R. Schellenberg. 1965. The Principle of Provenance and Modern Records in the United States. The American Archivist 28, 1 (1965), 39--41.
23. Yogesh Simmhan, Beth Plale, and Dennis Gannon. 2005. A survey of data provenance in e-science. SIGMOD Record 34, 3 (2005), 31--36.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

      • Semantics

    • General programming languages

      • Language types

        • Functional languages

• Theory of computation

  • Formal languages and automata theory

    • Formalisms

      • Rewrite systems