Scalable Graph Pattern Matching for Cyber Threat Hunting
Open AccessGraph data structures have seen a significant rise in popularity over the years due to their ability to represent highly interconnected data in a wide range of domains, e.g., chemical compounds, biological networks, social networks, source codes, and computer network systems. Cybersecurity data are a perfect candidate for taking advantage of graph data structure and a multitude of algorithms for extracting patterns from graphs. In this dissertation, we will discuss several graph pattern matching and mining algorithms that can be used to extract actionable insights from highly interconnected security datasets and how we tailor these algorithms to detect, analyze and reconstruct modern sophisticated targeted attacks, popularly referred to as Advanced Persistent Threats (APTs).First, we model threat detection as subgraph matching, where a query graph representing the behavior pattern of interest is searched against the data graph built on security telemetries. To support this computationally taxing NP-Complete algorithm for the size of data and query in modern threat detection problems, we make several algorithmic and system optimizations. In our framework named CECI, we address the problem of parallelizing subgraph matching using shared-memory and distributed computing hardware so that we can perform pattern matching on large datasets promptly. CECI proposes novel techniques for restructuring the graph into an intermediate data structure that enables sequential memory access and utilizes proactive cost estimation and work decomposition to achieve work balanced parallelization.In the Mnemonic system, we extend the performance improvements we have made on CECI towards building a more general-purpose, programmable subgraph matching system. Since the data graphs in many real-world applications are dynamic, we present an incremental subgraph matching system, where an update-friendly intermediate data structure is designed without compromising the access throughput. Additionally, Mnemonic exposes a set of high-level APIs and a programming paradigm that is suited for subgraph matching tasks. Modern Endpoint Detection and Response (EDR) systems continuously collect and monitor a huge amount of log data from endpoint hosts and generate thousands of alerts every day using event matching rules written by security analysts. Using the EDR-generated suspicious events and the data provenance graphs built from audit logs, we design a new system SteinerLog that automatically correlates the causal relationship among alerts to extract the subgraphs with a high likelihood of representing an attacker's activity within an enterprise host. The modeling of threat detection as alert correlation and the use of hierarchical traversal enables it to perform robust threat detection and reconstruction on a network with hundreds of hosts.Finally, in the Prov2vec system, we provide an unsupervised threat detection capability by using a representation learning system for provenance graphs. It detects abnormal behavior by comparing the provenance graph of an enterprise host at a time with its historical counterparts and that of similar hosts in the network. We present a novel graph kernel for obtaining representation vectors for provenance graphs in real-time, which are then fed to the downstream machine learning models trained with representations of normal behavior. It provides a more holistic view into the user/host behavior at any point in time and quickly pinpoints the ones acting out of the norm.Through these works, we have demonstrated the potential of graph data structure and graph pattern matching, mining, and learning algorithms for tackling critical challenges of cyber defense solutions. Moving forward, we plan to keep expanding these works to incorporate more data sources, harness the power of threat intelligence streams, scale the problem size, and improve detection and response abilities.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Bhattarai_gwu_0075A_16062.pdf | 2022-10-04 | Open Access |
|