We are witnessing a rapid escalation in targeted cyber-attacks, often called "Advanced and Persistent Threats" (APTs), carried out by skilled adversaries. By combining social engineering (e.g.,spear-phishing) with advanced exploit techniques, these adversaries routinely bypass widely-deployed software protections such as address space randomization. Consequently, enterprises have come to rely on second-line defenses such as security information and event management (SIEM) tools. While generally useful, these tools generate vast quantities of information, making it difficult for a security analyst to distinguish attacks from background noise. Moreover, analysts lack the tools to "connect the dots" to piece together fragments of an attack campaign that spans multiple applications, hosts, and time periods. It is no wonder that many APT campaigns go undetected for weeks to months.Researchers have proposed the use of causal dependencies, also called provenance, to bring more automation to cyber attack detection. Provenance provides additional context to prune away false positives, and can link together disparate attack steps. However, a straight-forward application of provenance leads to campaign summaries that are many orders of magnitude larger than what can be visualized or understood by a cyber analyst. Moreover, provenance data consists of billions of events, posing major challenges for real-time analysis.In this thesis, we first propose novel techniques that achieve two orders of magnitude reduction in the size of dependence graphs, while provably preserving analysis results. This makes it feasible to analyze scenarios consisting of tens of billions of events in main memory, where graph traversals can be implemented efficiently. To speed up detection and scenario reconstruction, we observed that these techniques typically compute and use global context at each graph node. We introduced the notion of tags to compactly summarize global context, and propagate these tags efficiently from ancestor nodes to descendant nodes using local computations. We have introduced several novel tags and propagation semantics, each offering different trade-offs in terms of efficiency and accuracy. Our experimental evaluation, carried out through several DARPA-sponsored red team exercises, demonstrates that our techniques are (a) effective in identifying stealthy attack campaigns, (b) reduce false alarm rates by more than an order of magnitude, and (c) yield compact attack scenarios consisting of tens to hundreds of events while sifting through event logs with tens to hundreds of millions of events.
展开▼
