PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs

Emaad A. Manzoor, Sadegh Momeni, Venkat N. Venkatakrishnan, Leman Akoglu

arXiv:1602.04844v2cs.SI

TL;DR

StreamSpot targets real-time anomaly detection in streaming heterogeneous graphs under bounded memory, motivated by host-level APT detection. It uses shingle-based similarity, constant-space sketches, and dynamic centroid clustering; experiments report over 90% average precision while processing over 100,000 edges per second.

  • Problem

    Detect anomalous graphs in streams of typed, interleaved edges quickly while meeting bounded-memory requirements.

  • Method

    StreamSpot combines shingle-based graph similarity, fixed-memory sketches, and dynamically maintained centroid-based clustering for online anomaly scoring.

  • Results

    Over 90% average precision was obtained across the stream while processing over 100,000 edges per second under strict memory constraints.

  • Takeaways & Limitations

    The approach supports continuous edge-level processing and real-time ranking of evolving heterogeneous graphs by anomalousness.

  • Takeaways & Limitations

    SimHash cannot be applied directly in streaming settings because it requires stored projection vectors, a potentially large shingle set, and known shingle-universe size.

Abstract

from arXiv · show

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 100K 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 our proposed StreamSpot is high-performance; achieving above 95% detection accuracy with small delay, as well as competitive time and memory usage.

1. INTRODUCTION

StreamSpot addresses real-time anomaly detection in streaming heterogeneous graphs, motivated by host-level APT detection and constrained by interleaved inputs, fast processing, and bounded memory. It introduces a clustering-based approach with graph similarity, sketches, and dynamic maintenance, validated on simulated normal and attack activity.

  • Problem: Streaming heterogeneous graphs contain typed nodes and edges, with multiple graph streams potentially interleaved.The goal is to identify graphs significantly different from prior observations quickly while using bounded memory.
  • Motivation: Host-level APT detection motivates the problem because malicious information flows are assumed sufficiently different from normal system behavior.System logs are converted into typed information flow graphs whose edges represent data or control dependencies.
  • Approach: StreamSpot combines a shingling-based heterogeneous-graph similarity function, fixed-memory graph sketches, and dynamically maintained centroid-based clustering.The method scores graphs by their distance to cluster centroids and flags anomalies online.
  • System properties: StreamSpot is designed for continuous edge-level processing, fast updates, bounded memory, and real-time anomaly detection.Its contributions include incremental maintenance of graph sketches and clustering rather than snapshot-oriented processing.
  • Evaluation: Experiments use simulated normal host activity and attack scenarios with ground truth to evaluate detection, sketch approximation, and resource efficiency.The study also varies parameters such as memory size.
  • Artifacts: The implementation and simulated normal and attack datasets are slated for release as source code and data.The cited release location is the StreamSpot project website.

2. PROBLEM & OVERVIEW

The paper models simultaneously evolving information-flow graphs as streams of typed edges, using flow tags to separate graphs even when their edges interleave. StreamSpot maintains compact graph representations, dynamically clusters graphs, and scores anomalies against cluster centroids in real time.

  • Input model: Host logs capture system events such as memory accesses and system calls, which are converted into information-flow graphs.Graph edges represent control and data dependencies, and flow tags identify the graph to which each event belongs.
  • Input model: The streaming graphs are heterogeneous: edge types encode system calls, while node types include sockets, files, and memory.Examples include read, fork, and sock_wr edge types.
  • Input model: Each streamed edge records typed source and destination nodes, a timestamp, an edge type, and a flow tag.The representation includes source-id, source-type, destination-id, destination-type, timestamp, edge-type, and flow-tag fields.
  • Streaming model: Edges sharing a flow tag form one dynamically evolving graph, while edges from different graphs may arrive interleaved.Multiple information flows can therefore evolve simultaneously.
  • Detection pipeline: StreamSpot maintains small graph representations and dynamically updates clustering as graphs evolve or new graphs arrive.Anomalies are flagged in real time from the evolving clustering.
  • Detection pipeline: Graph similarity uses shingle-frequency vectors, constant-size sketches, and centroid-based clustering for real-time anomaly scoring.A graph is scored by its distance to the closest centroid, with significance quantified from distances in the corresponding cluster.

3. SKETCHING TYPED GRAPHS

StreamSpot represents typed, timestamped graphs through ordered local shingles and compares their shingle-frequency vectors using cosine similarity. This representation supports online updates while avoiding storage of the potentially enormous shingle universe.

  • Requirements: The representation must capture temporal edge order, support efficient online updates, and consume bounded space over an infinite edge stream.These requirements motivate the proposed graph-similarity construction.
  • Requirements: Existing methods are unsuitable because some require node correspondence, fixed substructure spaces, or global metrics that cannot accommodate streaming edge order.The cited limitations prevent direct application to this setting.
  • Shingling: A k-shingle is a string produced by an ordered k-hop breadth-first traversal that starts with a node type and appends traversed edge and destination-node types.Outgoing edges are traversed in timestamp order.
  • Shingling: OkBFT constructs a directed k-hop neighborhood by performing the ordered breadth-first traversal used in shingle construction.The traversal abbreviation is Ordered k-hop Breadth First Traversal.
  • Vector representation: A graph’s shingle-frequency vector stores the frequency of every shingle in the universe S.Its dimension is |S|, with one entry for each shingle.
  • Illustration: Figure 2 illustrates two graphs, their k = 1 shingles, and the resulting shingle-frequency vectors.The figure connects local graph patterns with their vectorized frequency representation.
  • Similarity: Graph similarity is defined as cosine similarity between the corresponding shingle-frequency vectors.The vector representation captures local structure and edge order, while k trades expressiveness against update cost.

3.2 Graph Sketches by Hashing

The shingle universe can grow combinatorially, so StreamSpot uses locality-sensitive hashing to replace high-dimensional shingle vectors with constant-space sketches while preserving similarity. SimHash projects vectors using random Gaussian directions and records binary hash values.

  • Motivation: Heterogeneous graphs can have a combinatorially large shingle universe, making full shingle-frequency vectors infeasible to store.The paper therefore introduces a constant-space sketch approximation.
  • LSH: Locality-sensitive hashing projects high-dimensional vectors into lower-dimensional representations while preserving their similarity.MinHash and SimHash are cited as examples for Jaccard and cosine similarity, respectively.
  • SimHash: SimHash samples L projection vectors uniformly from a d-dimensional Gaussian distribution for input vectors in R^d.Each projection vector defines one hash function.
  • SimHash: Each SimHash value is +1 when z · r_l ≥ 0 and −1 when z · r_l < 0.Equivalently, the hash is sign(z · r_l).
  • Similarity preservation: The probability that two vectors hash to the same value is proportional to their cosine similarity.This property allows hash values to approximate similarity between graph representations.
  • Sketches: A d-dimensional shingle vector can be replaced by an L-dimensional sketch containing its LSH values.Similarity computation then requires only the sketch hash values.

BpEoD 1

StreamHash replaces explicit high-dimensional random projections with hash functions, producing compact sketches that preserve graph similarity and support streaming updates without knowing the complete shingle universe.

  • Sketching: Graphs are represented by L-bit sketches that estimate similarity from the proportion of agreeing sketch bits.The sketches replace |S|-dimensional shingle vectors with a target dimension L much smaller than |S|.
  • Limitations of SimHash: SimHash is unsuitable for streaming because it requires explicit projection vectors, potentially huge shingle dimensions, and prior knowledge of the complete shingle universe.New node and edge types can continuously create new shingles, leaving the universe unknown.
  • StreamHash: StreamHash uses L uniformly random hash functions that deterministically map shingles to +1 or −1.Its hash family is required to provide uniformity over shingles and functions, plus pairwise independence.
  • StreamHash: The projection vector stores signed shingle-count contributions, and the sketch is obtained by taking the sign of each projection entry.Each projection entry subtracts counts hashed to −1 from counts hashed to +1.
  • Streaming representation: StreamHash avoids storing explicit shingle vectors or the complete shingle universe, enabling incremental sketch construction and maintenance.Hash functions can be implemented using fixed random numbers for the maximum shingle length, with Θ(|s|) hashing time per shingle.
  • Merging sketches: Sketches of graph unions can be computed by summing projection vectors before applying the sign function.This supports merging graphs and constructing cluster-centroid sketches from unions.

3.3 Maintaining Sketches Incrementally

StreamHash maintains graph sketches incrementally as each edge changes only a local set of shingles, updating projection entries through signed hash contributions rather than explicit shingle vectors.

  • Shingle updates: Each arriving edge creates outgoing shingles to remove and incoming shingles to add, constructed through OkBFT traversals.Only nodes that can reach the edge destination within k hops require shingle updates.
  • State maintenance: The method maintains a length-L projection vector and derives the graph sketch from it, initializing empty graphs with zero projections.The shingle vector itself is not maintained explicitly.
  • Projection updates: For an incoming shingle, each projection entry increases by its hash value; for an outgoing shingle, it decreases by that value.The corresponding sketch bit changes when the updated projection entry changes sign.
  • Update optimization: Combining duplicate incoming and outgoing shingles across updated nodes reduces redundant projection and sketch updates.An incoming shingle for one node may be an outgoing shingle for another.

3.4 Time and Space Complexity

StreamSpot’s update costs depend on sketch size and shingle locality, while configurable edge retention bounds total memory for graph storage and sketch-based state.

  • Sketch updates: O(L+|s|^2_max) time is required per edge for sketch updates.L is constant, while |s|max depends on the k-hop parameter k, allowing per-edge running time to be controlled.
  • Graph storage: O(cL + N) total space is achieved by retaining at most N edges and maintaining constant-size sketches.N is chosen according to available memory, while L controls approximation quality.

4. ANOMALY DETECTION

StreamSpot bootstraps benign graph clusters, assigns incoming graphs to nearby centroids, updates cluster summaries dynamically, and flags graphs whose distance exceeds a cluster-specific threshold.

  • Bootstrap Clusters: Bootstrap clusters are formed from benign flow-graphs using K-medoids, with K selected to maximize the silhouette coefficient.Each cluster threshold is set at three standard deviations above its mean within-cluster distance.
  • Bootstrap Clusters: Cluster centroids are represented by averaged projection vectors, corresponding to average shingle-count graphs, and their sketches are constructed before bootstrap graphs are discarded.This preserves compact centroid state after initialization.
  • Streaming Cluster Maintenance: Each arriving edge updates a graph’s sketch and projection vector, after which the graph is compared with every cluster centroid to find the nearest cluster.The nearest cluster is denoted Q and provides the threshold used for assignment.
  • Streaming Cluster Maintenance: Graphs within threshold are assigned or reassigned while cluster sizes and projection vectors are updated; graphs beyond threshold are assigned to the attack class.Previously assigned graphs can remain in, move between, or be removed from clusters as their distances change.
  • Anomaly Scoring: Anomaly scores are computed as distances to the updated nearest-cluster centroid.The score is calculated after the centroid has incorporated the graph when appropriate.
  • Time and Space Complexity: O(KL) time is required per edge for clustering and anomaly detection, with O(c + KL) space for assignments, scores, centroids, and projection vectors.Nearest-cluster search dominates the per-edge clustering cost.

5. EVALUATION

StreamSpot was evaluated on simulated benign browsing and attack flow-graphs in static and streaming settings. It achieved strong anomaly-ranking performance while maintaining small detection delay, bounded-memory robustness, and high per-edge throughput.

  • Datasets: The evaluation uses flow-graphs from five benign browsing scenarios and one drive-by-download attack scenario, with automated traces providing ground truth.The scenarios include YouTube, file downloads, CNN, Gmail, and video-game activity; each scenario was executed for 100 tasks.
  • Evaluation settings: StreamSpot is tested both offline with full graph representations and online by processing test graphs one edge at a time under memory constraints.In streaming evaluation, graph sketches, cluster assignments, and anomaly scores are updated for every arriving edge, with snapshots retained every 10,000 edges.
  • Parameter selection: Chunk length controls the balance between graph structure and node-type frequency, and the selected safe-region settings produce near-ideal average precision that is robust to cluster count.The chosen settings are C = 25, 100, 50 and K = 5, 5, 10 for YDC, GFC, and ALL, respectively.
  • Static evaluation: AP exceeds 0.9 and AUC is near-ideal in the static setting, even when only 25% of the data is used for training.These results are averaged over 10 independent random samples and concern ranking attack graphs among the test graphs.
  • Streaming evaluation: Streaming performance recovers quickly after new graph groups arrive, yielding near-ideal attack ranking with small anomaly-detection delay.Performance dips when new graphs are only partially observed, then rises as the graphs grow; similar results hold for B = 50.
  • Memory efficiency: Reducing sketch size to L = 100 preserves comparable performance, while performance remains reasonable at L = 10 and degrades only slightly under memory constraints.Memory constraints increase detection or recovery delay, but StreamSpot remains robust across sketch sizes and memory limits.
  • Memory usage: Memory measurements separate stored graph edges from projection and sketch vectors, with graph-edge memory growing proportionally to the edge limit N.Projection vectors use 32 times the sketch memory because they are integer vectors of the same length.

6. RELATED WORK

Prior work spans graph similarity, typed-graph anomaly detection, streaming graph analysis, and compact graph representations, but existing methods do not directly address streaming heterogeneous graphs.

  • Graph similarity: Graph similarity methods requiring node correspondence or global graph metrics are unsuitable for streams with evolving, temporally ordered edges.Global metrics also cannot account for temporal edge ordering.
  • Graph similarity: Graph-edit distance offers a general dissimilarity measure, but its minimum-cost inexact matching is NP-hard and heuristics provide no error bound.This limits its direct use in scalable streaming settings.
  • Graph similarity: Graph kernels compare shared local substructures but require a fixed universe of substructures, unavailable when graphs arrive continuously.Their similarity is based on the number of substructures common to two graphs.
  • Heterogeneous/typed graphs: Typed-graph methods have focused on static databases, frequent substructures, anomalous subgraphs, or graph-edit deviations rather than evolving heterogeneous streams.These approaches commonly discover or use normative structures offline.
  • Streaming graphs: Streaming-graph methods address clustering, connectivity anomalies, attributes, unlikely edges, or approximate graph-edit distance, primarily for untyped or differently summarized graphs.Examples include centroid clustering, structural reservoir sampling, and distributed GED approximation.
  • Streaming graphs: Other streaming approaches detect community evolution, global structural changes, or temporal evolution rules, while graph-sketching work targets compact solutions to specific graph problems.These lines of work do not directly provide the paper’s heterogeneous streaming anomaly-detection formulation.

7. CONCLUSION

StreamSpot clusters and ranks anomalous heterogeneous graphs from evolving streams of typed edges using online sketches and centroid-based detection. It sustains bounded memory and high throughput while extending to other typed-graph streaming applications.

  • 7. CONCLUSION: StreamSpot represents heterogeneous ordered graphs by shingling and maintains their summaries online with StreamHash.The summaries support constant-time updates and bounded memory consumption.
  • 7. CONCLUSION: Over 90% average precision is obtained across the stream while processing over 100,000 edges per second under strict memory constraints.These are the reported course-of-stream anomaly-ranking and throughput results.
  • 7. CONCLUSION: Beyond host-level APT detection, StreamSpot applies to typed graphs from syntax-tree event streams and biochemical structures.The conclusion identifies social-media event detection and biochemical anomaly detection as example scenarios.
Loading 1602.04844v2…