Provenance is the representation of a system execution as a directed acyclic graph. Those graphs, representing the execution of an entire system from initialization to shut down, can be comprised of millions of graph elements. After a general introduction to the field of data provenance, it will present my recent work on the development of a provenance-based intrusion detection system. The system spans the entire software stack from the kernel-level capture mechanism to the algorithm used to perform intrusion detection. This talk is based on papers published at ACM CCS, NDSS and USENIX Security. I will be available after the talk for further technical discussions.