Provenance expressiveness benchmarking on non-deterministic executions


Sheung Chi Chan, Heriot Watt University; James Cheney, University of Edinburgh and The Alan Turing Institute; Pramod Bhatotia, Technische Universität München


Data provenance is a form of meta-data recording inputs and processes. It provides historical records and origin information of the data. Because of the rich information provided, provenance is increasingly being used as a foundation for security analysis and forensic auditing. These applications require provenance with high quality. Earlier works have proposed a provenance expressiveness benchmarking approach to automatically identify and compare the results of different provenance systems and their generated provenance. However, previous work was limited to benchmarking deterministic activities, whereas all real-world systems involve non-determinism, for example through concurrency and multiprocessing. Benchmarking non-deterministic events is challenging because the process owner has no control over the interleaving between processes or the execution order of system calls coming from different processes, leading to a rapid growth in the number of possible schedules that need to be observed. To cover these cases and provide all-around automated expressiveness benchmarking for real-world examples, we proposed an extension to the automated provenance benchmarking tool, ProvMark, to handle non-determinism.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {274845,
author = {Sheung Chi Chan and James Cheney and Pramod Bhatotia},
title = {Provenance expressiveness benchmarking on non-deterministic executions},
booktitle = {13th International Workshop on Theory and Practice of Provenance (TaPP 2021)},
year = {2021},
url = {},
publisher = {USENIX Association},
month = jul,