  The need for countering Advanced Persistent Threat (APT) attacks has led to
the solutions that ubiquitously monitor system activities in each host, and
perform timely attack investigation over the monitoring data for analyzing
attack provenance. However, existing query systems based on relational
databases and graph databases lack language constructs to express key
properties of major attack behaviors, and often execute queries inefficiently
since their semantics-agnostic design cannot exploit the properties of system
monitoring data to speed up query execution.
  To address this problem, we propose a novel query system built on top of
existing monitoring tools and databases, which is designed with novel types of
optimizations to support timely attack investigation. Our system provides (1)
domain-specific data model and storage for scaling the storage, (2) a
domain-specific query language, Attack Investigation Query Language (AIQL) that
integrates critical primitives for attack investigation, and (3) an optimized
query engine based on the characteristics of the data and the semantics of the
queries to efficiently schedule the query execution. We deployed our system in
NEC Labs America comprising 150 hosts and evaluated it using 857 GB of real
system monitoring data (containing 2.5 billion events). Our evaluations on a
real-world APT attack and a broad set of attack behaviors show that our system
surpasses existing systems in both efficiency (124x over PostgreSQL, 157x over
Neo4j, and 16x over Greenplum) and conciseness (SQL, Neo4j Cypher, and Splunk
SPL contain at least 2.4x more constraints than AIQL).
