PaperlayerView exact revision on arXiv

Source-linked AI summary

SAQL: A Stream-based Query System for Real-Time Abnormal System Behavior Detection

Peng Gao, Xusheng Xiao, Ding Li, Zhichun Li, Kangkook Jee, Zhenyu Wu, Chung Hwan Kim, Sanjeev R. Kulkarni, Prateek Mittal

arXiv:1806.09339v1cs.CRcs.DB

TL;DR

Advanced attacks and large-scale monitoring streams make timely detection of diverse anomalies and incorporation of expert knowledge challenging. SAQL provides a stream-based query engine and language for specifying anomaly models; its evaluation reports low latency, high throughput, and more efficient memory use than Siddhi.

  • Problem

    System-monitoring approaches face challenges combining timely detection of multiple anomaly types with expert knowledge over large volumes of data.

    Source: §1 · pp. 1, 3

  • Method

    SAQL uses a real-time event-feed query engine and domain-specific language for expressing rule-based, time-series, invariant-based, and outlier-based anomaly models.

    Source: §1 · p. 2

  • Results

    Across 1.1TB of data containing 3.3 billion events, SAQL reported <2s alert latency, 110,000 events/s for a representative query, scaling to ~4000 hosts, and 30% average memory saving versus Siddhi.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The system supports analyst-specified anomaly models over real-time event feeds aggregated from multiple enterprise hosts.

    Source: §1 · p. 2, §9 · p. 15

    The current data model covers files, processes, and network connections, with inter-process communications and finer-grained monitoring left for future work.

    Source: §7 · p. 13

Abstract

from arXiv · show

Recently, advanced cyber attacks, which consist of a sequence of steps that involve many vulnerabilities and hosts, compromise the security of many well-protected businesses. This has led to the solutions that ubiquitously monitor system activities in each host (big data) as a series of events, and search for anomalies (abnormal behaviors) for triaging risky events. Since fighting against these attacks is a time-critical mission to prevent further damage, these solutions face challenges in incorporating expert knowledge to perform timely anomaly detection over the large-scale provenance data. To address these challenges, we propose a novel stream-based query system that takes as input, a real-time event feed aggregated from multiple hosts in an enterprise, and provides an anomaly query engine that queries the event feed to identify abnormal behaviors based on the specified anomalies. To facilitate the task of expressing anomalies based on expert knowledge, our system provides a domain-specific query language, SAQL, which allows analysts to express models for (1) rule-based anomalies, (2) time-series anomalies, (3) invariant-based anomalies, and (4) outlier-based anomalies. We deployed our system in NEC Labs America comprising 150 hosts and evaluated it using 1.1TB of real system monitoring data (containing 3.3 billion events). Our evaluations on a broad set of attack behaviors and micro-benchmarks show that our system has a low detection latency (<2s) and a high system throughput (110,000 events/s; supporting ~4000 hosts), and is more efficient in memory utilization than the existing stream-based complex event processing systems.

1 Introduction

Advanced attacks and massive system-monitoring streams make timely detection of multiple anomaly types and incorporation of expert knowledge difficult. SAQL combines a real-time anomaly query engine with a domain-specific language and shared-stream query execution.

1 Introduction

  • Advanced persistent threats span hosts and vulnerabilities, while timely detection, expert-knowledge integration, and large-scale log analysis remain challenges for monitoring-based anomaly detection.Existing stream and anomaly systems focus on specific anomalies and provide limited support for expert-specified models.Source: §1 · pp. 1–2
  • SAQL accepts event patterns and stateful sliding-window computations to let analysts specify rule-based, time-series, invariant-based, and outlier-based anomaly models.The models are checked continuously against unbounded system-monitoring streams.Source: §1 · p. 2
  • Rule-based SAQL patterns express activities as subject-operation-object events and can represent suspicious sequences such as rapid access to multiple command logs.The example is framed as possible probing of commands used by legitimate users.Source: §1 · p. 2
  • Sliding-window states and historical state access support time-series comparisons, learned invariants, and peer-based outlier detection.SAQL provides aggregation functions and past-window access for time-series models, learns invariants under normal operation, and supports clustering to identify outliers.Source: §1 · p. 2
  • A master-dependent-query scheme groups compatible queries by temporal and spatial properties so dependent queries can reuse a master query's intermediate results instead of copying the stream per query.Compatibility considers sliding windows, host machines, and event attributes.Source: §1 · p. 3

Deployment and Evaluation

  • 110,000 events/s for a representative rule-based query, <2s alert latency for all evaluated queries, and 30% average memory saving versus Siddhi were reported across the evaluation.The deployment comprised 150 hosts; the system scaled to ~4000 hosts on the deployed server and used 1.1TB of data containing 3.3 billion events.Source: §1 · p. 3

2 Background and Examples

System monitoring represents host activity as events that can reveal attack footprints, while SAQL examples illustrate how its query constructs express several anomaly models. These examples demonstrate language capabilities rather than assess model quality.

2 Background and Examples

  • The section presents SAQL query examples to demonstrate anomaly-model language constructs, not to assess the models’ quality.The examples cover rule-based, time-series, invariant-based, and outlier-based anomalies.Source: §2 · p. 3, §2.2 · p. 4

2.1 System Monitoring

  • System monitoring models interactions among files, processes, and network connections as events represented by subject, operation, and object.Events are categorized by the type of their object entity.Source: §2.1 · p. 3

2.2 SAQL Queries for Anomalies

  • A rule-based query links ordered events to describe an attack sequence involving external access, a downloaded cracking tool, and its execution.The example’s events are reading an external network, downloading gsecdump.exe, and executing it to obtain database credentials.Source: §2.2 · p. 4
  • A time-series query tracks per-process network usage in sliding windows and alerts on spikes using a moving-average comparison.The example uses a 10-minute window and compares the current state with two past-window states.Source: §2.2 · p. 4
  • An invariant-based query learns Apache child-process names from ten windows, then alerts when a new child-process name appears.The example uses 10-second windows and an offline training stage.Source: §2.2 · p. 4, §A.1 · p. 18
  • An outlier-based query uses DBSCAN to compare per-IP data sent by sqlservr.exe and identify a suspicious outlier.SAQL can also specify IQR- or 3-sigma-based outlier rules, or alert on top sorted results.Source: §2.2 · pp. 4–5

3 System Overview and Threat Model

SAQL collects system-monitoring events from enterprise hosts into a central stream, parses user queries, and executes them to report alerts. Its threat model assumes kernel trust and untampered kernel-collected data.

3 System Overview

  • Monitoring agents collect kernel system-call data across servers, desktops, and laptops and send it to a central server as an event stream.Collection uses ETW on Windows, Linux Audit Framework on Linux, and DTrace on Mac OS.Source: §3 · p. 5
  • The parser analyzes submitted SAQL queries and creates an anomaly model context, which the execution engine uses to monitor the event stream and report alerts.The parser is implemented with ANTLR 4, and the execution engine is built upon Siddhi.Source: §3 · p. 5

3 Threat Model

  • The threat model assumes kernel trust and untampered kernel-collected monitoring data, excluding kernel-level attacks that compromise security auditing.Attackers may know the queries and models and attempt evasion through seemingly normal activity or peer-mimicking behavior.Source: §3 · p. 5

4 SAQL Language Design

SAQL is designed to help experts express anomaly models through event patterns and stateful computation. Its language covers event relationships, windowed state and invariants, peer clustering, alert conditions, and result filtering.

4 SAQL Language Design

  • SAQL combines event and stateful constructs to express rule-based, time-series, invariant-based, and outlier-based anomalies using expert domain knowledge.The grammar presents representative language rules and omits terminal symbols.Source: §4 · pp. 5–6

4.1 Multievent Pattern Matching

  • Event patterns describe subject-operation-object activity, while global constraints and temporal or attribute relationships link patterns into behavioral rules.A global constraint can require patterns to occur on the same host; temporal relationships can specify ordering and time spans.Source: §4.1 · p. 6

4.2 Stateful Computation

  • Windowed state fields support aggregates and sets, past-window comparisons, learned invariants, and peer clusters defined by points, distance metrics, and clustering methods.SAQL supports common metrics and clustering algorithms, with extensibility for additional algorithms and metrics.Source: §4.2 · p. 7

4.3 Alert Condition Checking

  • Alert conditions use boolean expressions to trigger time-series, invariant-based, or outlier-based detection, including moving-average, 3-sigma, and IQR rules.The cited examples specify 3-sigma and IQR thresholds for outlier detection.Source: §4.3 · p. 7

4.4 Return and Filters

  • Return, grouping, sorting, and top constructs select or filter query results, including threshold-based queries such as returning processes with IP frequency above 100 in a one-minute window.The example reports each process’s IP frequency.Source: §4.4 · p. 7

5 SAQL Execution Engine

The SAQL execution engine parses anomaly queries, schedules their execution, and reports alerts. Its master-dependent-query scheme lets compatible queries share stream data and intermediate results.

5 SAQL Execution Engine

  • The master-dependent-query scheme groups compatible queries so they share one copy of stream data, significantly reducing data copies.Only master queries access the stream directly; dependent queries reuse their masters’ intermediate results.Source: §5 · p. 8, §5.2 · p. 8

5.1 Query Execution Pipeline

  • The pipeline uses Siddhi for stream processing, parses queries into anomaly contexts, retrieves matched events, maintains state when needed, and generates alerts when conditions are met.The scheduler optimizes concurrent query execution; the multievent solver issues Siddhi queries, and the state maintainer uses intermediate results.Source: §5.1 · p. 8

5.2 Concurrent Query Scheduler

  • A semantic cover requires compatible single-event-pattern queries with matching event, operation, and window types; it can combine attributes, agent IDs, window lengths, and state fields.The cover uses attribute and agent-ID unions, the window-length GCD, and—when applicable—the union of state fields.Source: §5.2 · p. 9
  • Dependent queries reuse a master’s state aggregates when both define states with equal window lengths; otherwise they reuse matched events, then apply filters and continue execution.The scheduler seeks compatible queries because copying stream data for separate execution incurs high memory usage and limits scalability.Source: §5.2 · pp. 8–9

6 Deployment and Evaluation

The evaluation deployed SAQL on 150 hosts and used 1.1TB of monitoring data containing 3.3 billion system events, testing attack behaviors and concurrent-query performance.

6.1 Evaluation Setup

  • The evaluation ran on a server receiving data from 150 deployed hosts; a stream replayer reproduced attack scenarios for the concurrent-query tests.The host deployment comprised 10 servers and 140 employee stations, generating around 3750 events/s.Source: §6 · p. 9, §6.1 · p. 9

6.2 Attack Cases Study

  • The case study covered APT, SQL injection, Bash Shellshock, and suspicious system behaviors using queries built for known exploits and analyst-defined suspicious activity.The evaluation used four major attack-behavior categories.Source: §6 · p. 9, §6.2 · p. 9, §6.2.1 · p. 10

6.2.1 Attack Behaviors

  • The APT case used rule-based queries for attack steps and additional invariant-, time-series-, and outlier-based queries for suspicious behavior.The advanced queries detect unseen child processes, unusually high network transfer against historical behavior, and peer outliers; their construction assumes no knowledge of detailed attack steps.Source: §6.2.1 · pp. 9–10

6.2.2 Query Execution Statistics

  • <2s alert detection latency for all 17 attack queries, with latency ≤10ms for most and <10% CPU and <2.7GB memory use across 150 hosts.The SQL-injection query had somewhat higher latency because it used DBSCAN clustering.Source: §6.2.2 · p. 10, Table 3 · p. 11

6.3 Pressure Test

  • 110000 events/s maximum throughput: the authors estimate the server could support ∼4000 hosts from the deployed environment’s event rate.The pressure test used a 12-core server; temporal dependencies and concurrent queries may limit the maximum supported hosts.Source: Figure 4 · p. 11, §6.3 · p. 11

6.4 Performance Evaluation of Concurrent Query Execution

  • The 64-query micro-benchmark varied event attributes, sliding-window duration, agent IDs, and state aggregations, comparing SAQL with equivalent Siddhi queries.Siddhi lacks native stateful computation, so its state-category queries monitored matching event patterns without that computation.Source: §6.4 · pp. 11–13
  • 30% average memory saving at four concurrent queries: SAQL used less memory than Siddhi across all evaluation settings.The authors attribute the difference to sharing intermediate results; Siddhi copies stream data. Figures 5–8 report the settings, while replaying data raises absolute memory use without affecting the relative improvement.Source: Figure 5 · p. 12, Figure 6 · p. 12, Figure 7 · p. 12

7 Discussion

The discussion identifies limits in SAQL's deployment scale, monitored entities, query sharing, anomaly-model coverage, and alert fusion. It describes these as areas for future work or adaptation.

Scalability

  • SAQL executes over one holistic stream centrally; distributed query execution is not enabled in this work.The authors identify adapting the master-dependent-query scheme to more complex distributed scenarios as an open research direction.Source: §7 · p. 13

System Entities and Data Reduction

  • The current data model covers files, processes, and network connections, with pipes and finer-grained activity left for future expansion.The authors note that adding such monitoring would increase system pressure and call for further data-reduction research.Source: §7 · p. 13

Master-Dependent Query

  • The master-dependent-query optimization shares pattern-matching and stateful-computation results, but not alerts or results reported by alerts.Broader sharing is left for future work.Source: §7 · p. 13

Anomaly Models

  • SAQL supports major anomaly models found in common attacks, while specialized attacks may require additional models.The authors plan to extend model support through interfaces to models written in other languages.Source: §7 · pp. 13–14

Alert Fusion

  • Alert fusion is beyond this work's scope, and richer temporal relationships among alerts would require further design.The authors describe possible syntax for temporal alert relationships and modular chaining of queries.Source: §7 · p. 14

8 Related Work

The related work positions SAQL as an interface for querying abnormal behaviors in streaming system logs, distinct from historical-log forensics and general stream-processing platforms.

Audit Logging and Forensics

  • System-level provenance tools focus on historical logs and forensic analysis, while SAQL queries abnormal behaviors from log streams and can interoperate with those tools for causality analysis.The discussion cites work on attack causality, graph filtering, and storage reduction.Source: §8 · p. 14
  • AIQL queries historical audit logs in databases, and the authors propose using it to investigate anomalies detected by SAQL in streams.The authors suggest the two systems can be used together for defense against advanced cyber attacks.Source: §8 · p. 14

Security-Related Languages

  • Unlike security-specific languages for other domains, SAQL focuses on expressing anomaly models as queries and executing them over system-monitoring data.The related work describes other domain-specific languages for cryptography, overlay networks, intrusions, and obfuscation.Source: §8 · p. 14

Security Anomaly Detection

  • Existing anomaly-detection techniques target settings such as malware, intrusion, insider threats, and attack prediction, while SAQL offers a unified interface for expert-defined anomalies.The discussion contrasts rule-based and outlier-based techniques with SAQL's query interface.Source: §8 · p. 14

Complex Event Processing Platforms & Data Stream Management Systems

  • CEP platforms manage event patterns and sliding windows, but lack the stateful sliding-window computation needed to express SAQL's anomaly models.The authors present CEP systems as possible management infrastructure for their approach.Source: §8 · p. 14

Other Stream and System Analysis Systems

  • Stream-computation systems generally support stateless metrics, while log-search and system-query languages lack support for anomaly detection or stateful sliding-window computation.The related work distinguishes those tools from SAQL's support for expressing anomaly models.Source: §8 · pp. 14–15

9 Conclusion

The paper presents SAQL as a real-time stream-query system for expert-defined anomaly detection. Its evaluation reports low latency, high throughput, and more efficient memory use than existing stream-processing systems.

9 Conclusion

  • SAQL checks event streams aggregated from monitored hosts against analyst queries to detect anomalies in real time.The system provides a stream-based query engine for those submitted queries.Source: §9 · p. 15
  • SAQL combines event patterns with stateful computations over sliding windows to express rule-based, time-series, invariant-based, and outlier-based anomaly models.The language is designed to help analysts express anomalies using domain knowledge.Source: §9 · p. 15
  • Evaluation on 17 attack queries and 64 micro-benchmark queries found low alert-detection latency, high throughput, and more efficient memory use than existing stream-processing systems.The conclusion reports these outcomes without giving numerical latency or throughput values in this passage.Source: §9 · p. 15

A SAQL Queries in Attack Cases Study

The appendix presents 17 SAQL queries from a case study covering four major types of attack behavior; IP addresses and agent IDs are anonymized.

A SAQL Queries in Attack Cases Study

A.1 APT Attack

The APT examples encode attack activity as linked event sequences, from network connections and malware execution to credential or database theft and outbound connections.

A.1 APT Attack

  • A mail-focused pattern links SMTP, IMAP, and Outlook network events and returns their process, IP, agent, and event-time fields.The sequence links three events; the passages identify SMTP traffic, IMAP traffic, and Outlook reading email data.Source: §A.1 · p. 17
  • A separate process chain tracks Outlook starting Excel, Excel starting Java malware, and that malware starting Notepad before a connection to the attacker host.The returned fields include process and network entities and event start times.Source: §A.1 · p. 17
  • A psexec connection to a domain controller is followed by transferring and executing gsecdump.exe to dump administrator credentials.The query links the connection, gsecdump file write, and process execution.Source: §A.1 · p. 17
  • An SQL-server attack sequence connects with database-administrator credentials, writes malware, and has the malware connect back to the attacker host.The query links the connection, cmd.exe activity, file writes, and sbblv.exe network connection.Source: §A.1 · p. 17
  • An osql.exe execution is followed by a database dump that malware reads and transfers to the attacker.The query tracks creation of backup1.dmp, malware reading the file, and a network transfer.Source: §A.1 · p. 18

A.2 SQL Injection Attack

The section gives SAQL query examples for SQL-injection and Shellshock attacks, alongside signatures for suspicious system behaviors.

A.2 SQL Injection Attack

  • 10-minute SQL Server network windows are grouped by destination IP, clustered with DBSCAN, and flagged when an outlier amount exceeds 1,000,000.The query uses all points and the stated edit-distance setting for DBSCAN.Source: §A.2 · p. 18

A.3 Bash Shellshock Command Injection Attack

  • Within 10-second Apache process-start windows, the offline invariant alerts when |ss.set_proc diff a| > 0 and returns p1 and set_proc.The query groups by p1 and specifies invariant[10][offline].Source: §A.3 · p. 18, §A.1 · p. 18

A.4 Suspicious System Behaviors

  • Suspicious-behavior signatures include Dropbox process network starts, access to SSH keys, and reads or writes involving USB files.The queries return process, file, agent, and event-time fields where specified.Source: §A.4 · p. 18
  • Other signatures flag more than 100 process-to-network starts per minute and track reads of command histories or /etc/passwd and writes to wtmp or lastlog.The command-history query names several shell and application history files.Source: §A.4 · p. 18

Related papers

Loading 1806.09339v1…