Structural Analysis of Whole-System Provenance Graphs

Abstract

System based provenance generates traces captured from various systems, a representation method for inferring these traces is a graph. These graphs are not well understood, and current work focuses on their extraction and processing, without a thorough characterization being in place. This paper studies the topology of such graphs. We analyze multiple Whole-system-Provenance graphs and present that they have hubs-and-authorities model of graphs as well as a power law distribution. Our observations allow for a novel understanding of the structure of Whole-system-Provenance graphs.