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. In this talk, I will give an overview of my work on the development of a provenance-based intrusion detection system. I will discuss the development of the 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.