ABSTRACT: Intrusive multi-step attacks, such as Advanced Persistent Threat (APT) attacks, have plagued many well-protected businesses with significant financial losses. These advanced attacks are sophisticated and stealthy, and can remain undetected for years as individual attack steps may not be suspicious enough. To counter these advanced attacks, a recent trend is to leverage ubiquitous system monitoring for collecting the attack provenance for a long period of time and perform attack investigation for identifying risky system behaviors.