Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs

By Emaad Manzoor, Sadegh Momeni, Venkat N. Venkatakrishnan, Leman Akoglu. Knowledge Discovery and Data Mining, 2016

348 citations recorded by the source corpus.

Given a stream of heterogeneous graphs containing different types of nodes and edges, how can we spot anomalous ones in real-time while consuming bounded memory? This problem is motivated by and generalizes from its application in security to host-level advanced persistent threat (APT) detection. We propose StreamSpot, a clustering based anomaly detection approach that addresses challenges in two key fronts: (1) heterogeneity, and (2) streaming nature. We introduce a new similarity function for heterogeneous graphs that compares two graphs based on their relative frequency of local substructures, represented as short strings. This function lends itself to a vector representation of a graph, which is (a) fast to compute, and (b) amenable to a sketched version with bounded size that preserves similarity. StreamSpot exhibits desirable properties that a streaming application requires: it is (i) fully-streaming; processing the stream one edge at a time as it arrives, (ii) memory-efficient; requiring constant space for the sketches and the clustering, (iii) fast; taking constant time to update the graph sketches and the cluster summaries that can process over 100,000 edges per second, and (iv) online; scoring and flagging anomalies in real time. Experiments on datasets containing simulated system-call flow graphs from normal browser activity and various attack scenarios (ground truth) show that StreamSpot is high-performance; achieving above 95% detection accuracy with small delay, as well as competitive time and memory usage.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/87f42406de084e60d2365adac8a159ed3e455856

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Log2vec: A Heterogeneous Graph Embedding Based Approach for Detecting Cyber Threats within Enterprise (2019, background): “STREAMSPOT is an advanced approach to detect malicious information flows [31].”
UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, methodology): “Provenancebased anomaly detection systems rely on graph neighborhood exploration to understand normal behavior through either static [53] or dynamic [83] models.”
NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks (2018, methodology): “Many methods have been proposed in the past decade to solve this problem [3, 18, 23, 32, 40].”
HOLMES: Real-Time APT Detection through Correlation of Suspicious Information Flows (2018, background): “Host-based intrusion detection approaches fall under three classes: (1) misuse-based [32], [47], which detect behavior associated with known attacks; (2) anomaly-based [13], [16], [17], [31], [35], [40], [49], [51], which learn a model of benign behavior and detect deviations from it; and (3) specif”
Generative Adversarial Active Learning for Unsupervised Outlier Detection (2018, methodology): “Spe-ciﬁc methods include the statistical-based models [11], [12], regression-based models [13], cluster-based models [14], and reconstruction-based models [15], [16], which make different assumptions about the generating mechanism of Xiangnan He is the corresponding author.”
Robust Anomaly Detection for Multivariate Time Series through Stochastic Recurrent Neural Network (2019, background): “1 INTRODUCTION Anomaly detection has been an active research topic in SIGKDD community with applications in graph [3, 12], log messages [15, 23], time series [6, 9, 14, 22], etc.”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, methodology): “This problem is commonly approached by: 1) measuring the pairwise proximities of graphs using graph kernels [139]; 2) detecting the appearance of anomalous graph signals created by abnormal groups of nodes [140]; or 3) encoding graphs using frequent motifs [63].”