Towards provenance-based access control with feasible overhead

Provenance is a directed graph that explains how a data item became what it is. It is recently proposed to use provenance to enable the so-called provenance-based access control (PBAC) in provenance-aware systems. Evaluating a PBAC policy usually involves one or more queries against provenance store. However, directly reusing existing provenance query engines in a PBAC enforcement framework may introduce unacceptable performance overhead because provenance store might grow to immense size. This paper argues that feasible performance overhead for evaluating a PBAC policy must be under a nearly fixed threshold that is tolerable for users no matter how big the provenance store is. This paper designs several tactics, in particular a PBAC-specific tactic-adding shortcuts in a provenance graph, to partially satisfy this requirement. Finally, we analyze several open questions with respect to adopting these tactics.