  System level provenance is of widespread interest for applications such as
security enforcement and information protection. However, testing the
correctness or completeness of provenance capture tools is challenging and
currently done manually. In some cases there is not even a clear consensus
about what behavior is correct. We present an automated tool, ProvMark, that
uses an existing provenance system as a black box and reliably identifies the
provenance graph structure recorded for a given activity, by a reduction to
subgraph isomorphism problems handled by an external solver. ProvMark is a
beginning step in the much needed area of testing and comparing the
expressiveness of provenance systems. We demonstrate ProvMark's usefuless in
comparing three capture systems with different architectures and distinct
design philosophies.
