Modern cyber attackers use advanced zero-day exploits, highly targeted spear phishing, and other social engineering techniques to gain access, and also use evasion techniques to maintain a prolonged presence within the victim network while working gradually towards the objective. To minimize damage, detecting these Advanced Persistent Threats as early in the campaign as possible is crucial. This paper proposes, Prov2vec, a system for the continuous monitoring of enterprise host’s behavior to detect attackers’ activities. It leverages the data provenance graph built using system event logs to get complete visibility into the execution state of an enterprise host and the causal relationship between system entities. It proposes a novel provenance graph kernel to obtain the canonical representation of the system behavior, which is compared against its historical behaviors and that of other hosts to detect the deviation from the norm. These representations are used in several machine learning models to evaluate their ability to capture the underlying behavior of an endpoint host. We have empirically demonstrated that the provenance graph kernel produces a much more compact representation compared to existing methods while improving prediction ability.

Advanced cyberattacks are carried out in multiple stages, where each stage performs a specific task corresponding to the campaign. While these steps are designed to blend in with benign activities, they leave their activity footprints across multiple logs on the machines inside the victim environment. The majority of these footprints when looked at in isolation seem benign to the activity monitors. Existing threat hunting systems require a significant amount of human effort to correlate these events in order to detect and reconstruct an attack campaign. This paper introduces SteinerLog, an end-to-end system to automate the task of correlating the alerts to detect ongoing attack campaigns within an enterprise network. SteinerLog takes the alerts generated by mature intelligence-based and anomaly-based alerting systems and uses causal analysis to extract the group of events that are most likely to represent the attackers' activities. It performs hierarchical graph traversal to perform cross-host attacker activity correlation, which includes detecting the compromised entities, reconstructing the attackers' steps, and abstracting them into easy-to-understand attack graphs. The experiments show that it is able to detect APT campaigns in real-time and scale to an enterprise system with hundreds of workstations.

Finding patterns in large highly connected datasets is critical for value discovery in business development and scientific research. This work focuses on the problem of subgraph matching on streaming graphs, which provides utility in a myriad of real-world applications ranging from social network analysis to cybersecurity. Each application poses a different set of control parameters, including the restrictions for a match, type of data stream, and search granularity. The problem-driven design of existing subgraph matching systems makes them challenging to apply for different problem domains. This paper presents Mnemonic, a programmable system that provides a high-level API and democratizes the development of a wide variety of subgraph matching solutions. Importantly, Mnemonic also delivers key data management capabilities and optimizations to support real-time processing on long-running, high-velocity multi-relational graph streams. The experiments demonstrate the versatility of Mnemonic, as it outperforms several state-of-the-art systems by up to two orders of magnitude.

Subgraph matching finds all distinct isomorphic embeddings of a query graph on a data graph. For large graphs, current solutions face the scalability challenge due to expensive joins, excessive false candidates, and workload imbalance. In this paper, we propose a novel framework for subgraph listing based on Compact Embedding Cluster Index (\idx), which divides the data graph into multiple embedding clusters for parallel processing. The \sub has three unique techniques: utilizing the BFS-based filtering and reverse-BFS-based refinement to prune the unpromising candidates early on, replacing the edge verification with set intersection to speed up the candidate verification, and using search cardinality based cost estimation for detecting and dividing large embedding clusters in advance. The experiments performed on several real and synthetic datasets show that the \sub outperforms state-of-the-art solutions on average by 20.4× for listing all embeddings and by 2.6× for enumerating the first 1,024 embeddings.