\section{Dependency Parsing Example}
\label{app:sec:dependency}

\section{Design of \textsc{Zebra}\xspace}
\label{sec:approach}

In this section, we present the design details of \textsc{Zebra}\xspace.
Specifically, \cref{subsec:auditing} describes how \textsc{Zebra}\xspace collects system audit logs.
\cref{subsec:storage} describes how \textsc{Zebra}\xspace stores the collected data.
\cref{subsec:tracking} describes the underlying mechanism of \textsc{Zebra}\xspace's dependency tracking capability.
\cref{subsec:language} describes the syntax of \textsc{Zebra}\xspace's DSL, \textsc{Tstl}\xspace.
\cref{subsec:execution} describes how \textsc{Zebra}\xspace executes a \textsc{Tstl}\xspace query.

\subsection{Data Model and Data Collection}
\label{subsec:auditing}

\input{tables/syscalls.tex}
\input{tables/system-entities.tex}
\input{tables/system-events.tex}

System audit logging data records the interactions among system entities as system events.
As shown in prior studies on system auditing~\cite{backtracking,ma2016protracer,liu2018priotracker,hassan2019nodoze,ji2017rain,gao2018aiql,gao2018saql,shu2018threat}, on mainstream operating systems, system entities in most cases are files, processes, and network sockets, and the monitored system calls are mapped to three major types of system events: file access, processes creation and destruction, and network access.
Hence, in \textsc{Zebra}\xspace, we consider system entities as \emph{files}, \emph{processes}, and \emph{network sockets}.
We consider a system event as the interaction between two entities represented as $\langle$subject\_entity, operation\_type, object\_entity$\rangle$, which consists of the initiator of the interaction, the type of the interaction, and the target of the interaction.
Subjects are processes originating from software applications (e.g.,\xspace firefox) and objects can be files, processes, and network sockets.
We categorize system events into three types according to the types of their object entities: \emph{file events}, \emph{process events}, and \emph{network events}.

\textsc{Zebra}\xspace leverages mature system auditing frameworks \cite{auditd,etw,sysdig} in its monitoring agents to collect system audit logs of system calls.
\textsc{Zebra}\xspace then parses the collected audit logs into a sequence of system events among system entities, and extracts a set of attributes that are crucial for security analysis.
\cref{tab:syscalls} shows representative system calls (in Linux) processed by \textsc{Zebra}\xspace.
Failed system calls are filtered out as processing them will cause false dependencies among events.
\cref{tab:entity-attributes,tab:event-attributes} show representative attributes of system entities and system events extracted by \textsc{Zebra}\xspace.
Following the existing works~\cite{liu2018priotracker,ma2016protracer,gao2018aiql}, to uniquely identify system entities, for a process entity, \textsc{Zebra}\xspace uses the process executable name and PID as its unique identifier.
For a file entity, \textsc{Zebra}\xspace uses the absolute path as its unique identifier.
For a network socket entity,
\textsc{Zebra}\xspace uses the 5-tuple $\langle$srcip, srcport, dstip, dstport, protocol$\rangle$ as its unique identifier.
Failing to distinguish different system entities will cause problems in relating system events to system entities and tracking dependencies among system events.

\subsection{Data Storage}
\label{subsec:storage}

\textsc{Zebra}\xspace stores the parsed system entities and system events in the database, so that the collected system audit logging data can be persisted.
Prior works have modeled system audit logging data as either relational tables~\cite{gao2018aiql} or provenance graphs~\cite{liu2018priotracker}.
Inspired by such designs, \textsc{Zebra}\xspace supports both types of database models for its storage component: relational model and graph model.
At the moment, \textsc{Zebra}\xspace adopts PostgreSQL~\cite{postgresql} as its relational storage and Neo4j~\cite{neo4j} as its graph storage.
For PostgreSQL, \textsc{Zebra}\xspace stores the parsed system entities and system events in separate tables (i.e.,\xspace three entity tables and three event tables),
and stores their attributes in table columns.
For Neo4j, \textsc{Zebra}\xspace stores system entities as nodes and system events as edges.
Every entity and every event has an ID attribute in both databases, and entities can be related to events via matching the entity ID with the subject/object ID attributes of events.
Indexes are created on key attributes (e.g.,\xspace file name, process executable name, source/destination IP) for both databases to speed up the query execution.

Generally speaking, relational databases come with mature indexing mechanisms and are suitable for queries that involve many joins and constraints.
Graph databases represent data as nodes and edges, which are suitable for queries that involve graph traversal.
Hence, relational databases are good for \textsc{Tstl}\xspace search queries that specify a subgraph pattern for search, in which multiple entities and events are joined together and multiple constraints are used to specify the subgraph attributes and structure.
On the other hand, graph databases are good for \textsc{Tstl}\xspace tracking queries that need to iteratively expand the connected events of an entity to build the dependency graph.
As we will discuss in \cref{subsec:execution}, both PostgreSQL and Neo4j database backends are fully supported in the \textsc{Tstl}\xspace execution engine at the moment, which can execute the full set of features of both \textsc{Tstl}\xspace search queries and \textsc{Tstl}\xspace tracking queries.
Users (e.g.,\xspace security analysts) of \textsc{Zebra}\xspace can consider the tradeoff and have the flexibility to configure which database backend to use.

\myparatight{Data Reduction}
\textsc{Zebra}\xspace further reduces the data size before storing it in the database, so that the search can be done more efficiently while the critical information about attack behaviors is still preserved.
System audit logging data often has many excessive events between the same entity pair~\cite{reduction}.
The reason is that OS typically finishes a read/write task (e.g.,\xspace file read/write) by distributing the data proportionally to multiple system calls and each system call processes only a portion of data.
Inspired by the prior work on Causality Preserved Reduction~\cite{reduction},
\textsc{Zebra}\xspace merges the events between two entities using the following criteria:
(1) two events $e_1(u_1, v_1)$ and $e_2(u_2, v_2)$ ($u_1$, $u_2$ are subjects and $v_1$, $v_2$ are objects; suppose $e_1$ occurs before $e_2$) can be merged if: $u_1 = u_2$ \&\& $v_1 = v_2$ \&\& $e_1.operationType = e_2.operationType$ \&\& $0 \leq e_2.startTime - e_1.endTime \leq threshold$ \&\& all other attributes except dataAmount of $e_1$ and $e_2$ are the same;
(2) the attributes of the merged event $e_{m}$ are: $e_{m}.startTime = e_1.startTime$, $e_{m}.endTime = e_2.endTime$, $e_{m}.dataAmount = e_1.dataAmount + e_2.dataAmount$.
The merge process is done iteratively on all events between the paired entities until none can be further merged.
We experimented with different merge time thresholds and chose 1 second, as it has reasonable reduction performance in merging system events for file manipulations, file transfers, and network communications, with no false events generated, which is consistent with~\cite{reduction}.

\subsection{Causal Dependency Tracking}
\label{subsec:tracking}

Causal dependency tracking analyzes system events to infer their dependencies and present the dependencies as a directed system dependency graph.
In the dependency graph $G(V, E)$, a node $v\in V$ denotes a system entity (e.g.,\xspace process, file, or network socket).
An edge $e(u,v)\in E$ denotes a system event that involves two entities $u$ and $v$ (e.g.,\xspace process creation, file read or write, and network access).
The direction of the edge (from the source node $u$ to the sink node $v$) indicates the direction of the \emph{information flow } (i.e.,\xspace control flow and data flow).
For example, for a read system call between a process and a file, the file is the source and the process is the sink.
On the other hand, for a write system call between the process and the file, the process is the source and the file is the sink.
For more details on how \textsc{Zebra}\xspace infers the edge direction for other system calls, we refer the readers to the original backward tracking paper~\cite{backtracking}.
Each edge (event) $e(u, v)$ is associated with a time window, $[ts(e), te(e)]$, where $ts(e)$ and $te(e)$ denote the start time and the end time of the event $e$ respectively.
Our definition of causal dependency between two events follows the prior works~\cite{backtracking,liu2018priotracker}.
Formally, in the dependency graph, for two events $e_1(u_1, v_1)$ and $e_2(u_2, v_2)$ (suppose $e_1$ occurs earlier than $e_2$), there exists causal dependency between $e_1$ and $e_2$ if $v_1 = u_2$ and $ts(e_1) < te(e_2)$.

Causal dependency tracking enables two important security analyses that are crucial for attack investigation: (1) \emph{backward tracking} that identifies entry points of an attack, and (2) \emph{forward tracking} that investigates ramifications of an attack~\cite{backtracking}.
Given a POI event $e_{poi}(u,v)$, a backward tracking traces back from the source node $u$ to find all events that have causal dependencies on $u$,
and a forward tracking traces forward from the sink node $v$ to find all events on which $v$ has causal dependencies.
The output of backward/forward tracking is a backward/forward system dependency graph.

At the moment, \textsc{Zebra}\xspace fully supports both backward tracking and forward tracking capabilities as part of the \textsc{Tstl}\xspace execution engine for executing \textsc{Tstl}\xspace tracking queries.
Taking backward tracking for an example.
Starting from an empty queue $Q$ and an empty dependency graph $G$, \textsc{Zebra}\xspace first adds the POI event $e_{poi}(u,v)$ to $Q$ and $G$.
\textsc{Zebra}\xspace then iteratively removes an event from $Q$, finds other events that have causal dependencies on $u$, and adds these events to $Q$ and $G$.
\textsc{Zebra}\xspace repeats this process and stops until $Q$ becomes empty, and the final graph $G$ will be output.

\subsection{Threat Search and Tracking Language (\textsc{Tstl}\xspace)}
\label{subsec:language}

\input{grammar.tex}

\textsc{Zebra}\xspace provides a DSL, \emph{Threat Search and Tracking Language (\textsc{Tstl}\xspace)}, that uniquely integrates a collection of specialized language constructs for various types of fine-grained control and integration of attack pattern search and causal dependency tracking.
\cref{fig:query} shows a series of \textsc{Tstl}\xspace search and tracking queries for progressively investigating the data leakage attack depicted in \cref{fig:demo}.
\cref{bnf:grammar} shows the BNF grammar of \textsc{Tstl}\xspace.
We describe some of the key language features in detail next.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/query.pdf}
    \caption{A series of \textsc{Tstl}\xspace queries for investigating the data leakage attack in \cref{fig:demo}}
    \label{fig:query}
\end{figure}

\subsubsection{Attack Pattern Search in \textsc{Tstl}\xspace}
For the \textsc{Tstl}\xspace search query, \textsc{Tstl}\xspace provides an intuitive syntax to specify attribute constraints of entities and events, as well as relationship constraints among events.
Rule $\langle search\_stmt\rangle$ gives the overall rule of the search query syntax.
With this syntax, security analysts can easily specify multi-event attack subgraph patterns with certain event dependencies.

Let's take Query \circled{1} in \cref{fig:query} as an example to illustrate the syntax.
First, we specify a database (e.g.,\xspace \incode{db(host1)}) as the data source of the search (i.e.,\xspace Rule $\langle data\_source\rangle$).
Note that to facilitate progressive manipulation and refinement of intermediate results, a graph variable that has been bound to the in-memory results of the previous query execution can also be specified as the data source (e.g.,\xspace \incode{g2} in Query \circled{3}).
Then, we specify three system entities with constraints on their types and attributes (e.g.,\xspace \incode{e1\{name="curl", type=process\}}) according to Rule $\langle search\_node\rangle$.
Then, we specify two system events using the three entities (e.g.,\xspace \incode{e2[read]->e1}; the arrow indicates the direction of information flow) according to Rule $\langle search\_rel\_expr \rangle$.
In addition to the \emph{structural relationship} that two events are connected by the same entity \incode{e1}, we further specify their \emph{temporal relationship}: the two events should occur together within one second (e.g.,\xspace \incode{&&[<1s]}).
These three entities and two events altogether specify a subgraph pattern, which depicts the attack behavior that ``the attacker uses \incode{curl} to transfer a sensitive \incode{tar} file to an IP'' (the ``transfer'' action is achieved by first reading data from the file and then writing the data to the socket).
After specifying the subgraph pattern, we can specify how we want to process the query execution results.
In Query \circled{1}, we assign the results to a graph variable (e.g.,\xspace \incode{poi1}) and maintain the results in memory, which can be used by subsequent queries (e.g.,\xspace Query \circled{2}).
We can also directly return the results (e.g.,\xspace \incode{return *} in Query \circled{3}), which will be displayed on the console/GUI.

\subsubsection{Causal Dependency Tracking in \textsc{Tstl}\xspace}
For the \textsc{Tstl}\xspace tracking query, \textsc{Tstl}\xspace provides a novel syntax that provides various types of fine-grained control of the tracking process, including the flexible customization of tracking direction, POI, data source, tracking depth, and constraint expressions on entities and events for prioritizing or excluding certain entities and events.
Rule $\langle track\_stmt\rangle$ gives the overall rule of the tracking query syntax.
With this syntax, security analysts can easily control the tracking process and mitigate the dependency explosion problem by prioritizing attack-relevant parts and excluding attack-irrelevant parts.

Let's take Query \circled{2} in \cref{fig:query} as an example.
A backward tracking query (i.e.,\xspace Rule $\langle track\_direction\rangle$) is specified with the database (e.g.,\xspace \incode{db(host1)}) as the data source (i.e.,\xspace Rule $\langle data\_source\rangle$).
Same as the search query, a graph variable bound to in-memory execution results can also be specified as the data source (e.g.,\xspace \incode{g4} in Query \circled{6}).
Besides, the tracking starts from the execution results of the previous query: \incode{poi1} is specified as the start entities of the tracking (i.e.,\xspace Rule $\langle track\_poi\rangle$), which is declared and assigned in the previous search query Query \circled{1} as its execution results.
In addition to the graph variable, constraint expression on entities can also be specified as start entities (e.g.,\xspace \incode{curl} processes in Query \circled{4}).
To constrain the tracking process, entities with names as \incode{vscode} are excluded (i.e.,\xspace Rule $\langle track\_filter\rangle$) as they are most likely benign.
Since a full tracking won't stop until all eligible events are found, it can take a long time to execute.
To facilitate quick result inspection at the current stage, a tracking depth limit (i.e.,\xspace Rule $\langle track\_limit\rangle$) is specified (e.g.,\xspace \incode{limit step 2}) to constrain the tracking scope.
The execution results of the tracking query \circled{2} are a backward dependency graph, which is bound to the graph variable \incode{g2} for display and passed to subsequent queries for further investigation.

\subsubsection{Integrating Search and Tracking for Progressive Investigation}
As described previously, both \textsc{Tstl}\xspace search queries and \textsc{Tstl}\xspace tracking queries return a subgraph of system events as the execution results (dependency graph returned by tracking is a special type of subgraph).
To integrate search and tracking for progressive investigation, \textsc{Zebra}\xspace supports managing query results in memory and binding the results to explicit \emph{graph variables} for further access.
Security analysts can then manipulate the intermediate results through operators between these variables, and pass these results to subsequent queries via specifying the variable as the data source.

More specifically, in Query \circled{2}, variable \incode{g2} is declared and bound to the dependency graph produced by the tracking.
Then, in Query \circled{3}, \incode{g2} is specified as the data source of this subsequent search, meaning that the search directly operates over the same dependency graph maintained in memory.
This way, subgraphs generated by the previous query can be progressively refined by subsequent queries.

To further empower security analysts to progressively analyze and manipulate the results, \textsc{Tstl}\xspace supports combining the subgraphs generated by different queries through graph operators between the bound variables and binding the resulting subgraph to a new variable (i.e.,\xspace Rule $\langle graph\_op\_stmt\rangle$).
For example, in Query \circled{6}, a union operation is taken between \incode{g2} and \incode{g3} (to combine the previously identified parts of attack sequence) and the resulting new subgraph is bound to \incode{g4}.
Prior work~\cite{fang2022backpropagating} has pointed out that taking the graph intersection/difference between the dependency graphs generated by backward and forward tracking from different POIs helps reveal the attack sequence.
Thus, \textsc{Tstl}\xspace also supports the intersection and difference operations.
To facilitate the result inspection, \textsc{Tstl}\xspace supports displaying the subgraph on the console/GUI (i.e.,\xspace Rule $\langle display\_stmt\rangle$) or exporting it to a file (i.e.,\xspace Rule $\langle export\_stmt\rangle$).

The design of \textsc{Tstl}\xspace facilitates progressively finding damaging needles in a very large haystack.
To ease the query construction and the result inspection, we built a web GUI that follows a Jupyter Notebook style with code cells.
Users can specify search queries, tracking queries, and query results operation statements in a code cell, and execute the cell to display the resulting subgraph.
Users can also keep the query statements in the executed cells and the query results in the GUI to keep track of the investigation process.
The expressive support for search and tracking and the capabilities in synergistically integrating queries for progressive investigation \emph{distinguish} \textsc{Tstl}\xspace significantly from existing DSLs~\cite{gao2018aiql,shu2018threat} and general-purpose query languages like SQL~\cite{sql} or Cypher~\cite{cypher}.

\subsection{\textsc{Tstl}\xspace Execution Engine}
\label{subsec:execution}

As described previously, depending on the data source specified in a \textsc{Tstl}\xspace search or tracking query, the query can be executed over either the database or the in-memory subgraph resulting from the previous query execution.
Thus, the \textsc{Tstl}\xspace execution engine employs specialized domain-specific optimizations for these two scenarios.

\subsubsection{Optimizing \textsc{Tstl}\xspace Queries Over the Database}
To execute a \textsc{Tstl}\xspace query over the database, a \emph{straightforward but naive} execution plan would be: compiling the \textsc{Tstl}\xspace query into a semantically equivalent SQL query or Cypher query, and then executing the compiled query over the corresponding database backend (i.e.,\xspace PostgreSQL for SQL query, Neo4j for Cypher query) to leverage the execution plan and optimizations provided by the DBMS.
For example, a \textsc{Tstl}\xspace search query can be compiled into a SQL or Cypher query with joins and constraints, and a \textsc{Tstl}\xspace tracking query can be compiled into a SQL query using the recursive WITH clause or a Cypher query using the path matching clause.

However, as we will show in \cref{subsec:eval-results}, this execution plan is very \emph{inefficient}.
The primary reason is that these general-purpose query languages are designed for general data querying.
Thus, these languages
lack visibility into our particular system audit logging data domain and their optimizations are not tailored to our particular analyses.
For example, for the search analysis, as the attack pattern typically consists of multiple connected steps, the compiled SQL query and Cypher query could be giant with many joins and constraints weaved together, which often leads to slow performance.
For the tracking analysis, the compiled recursive SQL query also requires costly full table scans and many joins, and the compiled Cypher query requires matching all available paths first (the path length is determined by the tracking scope) and then does the filtering, which is very inefficient.

\myparatight{Component-Based Scheduling Algorithm}
To efficiently execute a \textsc{Tstl}\xspace query, our key idea is as follows:
instead of compiling its entirety into a giant SQL query or Cypher query, we can \emph{decompose the \textsc{Tstl}\xspace query into components}, compiles each component into a semantically equivalent database query (SQL or Cypher), and then schedules the execution of these database queries leveraging domain-specific optimizations.
This way, we can avoid weaving joins and constraints together in giant queries, while still benefiting from the indexing mechanisms and optimizations provided by the underlying DBMS when executing each database query.

We now describe our \emph{component-based scheduling algorithm}, which schedules the execution of database queries based on their
estimated pruning power and semantic dependencies.

For a \textsc{Tstl}\xspace search query, for each event pattern specified (e.g.,\xspace \incode{e2[read]->e1}, \incode{e1[write]->e3} in \cref{fig:query} are two event patterns), \textsc{Zebra}\xspace compiles it into a SQL or Cypher database query.
The SQL query joins two entity tables and one event table with filters in the WHERE clause.
The Cypher query matches two entity nodes and one event edge with filters in the WHERE clause.
Then, for each event pattern, \textsc{Zebra}\xspace computes a \emph{pruning score} by counting the number of constraints declared; more constraints lead to a higher score.
Then, when scheduling the execution of database queries for all event patterns, \textsc{Zebra}\xspace considers both the pruning scores and the event pattern dependencies: if two event patterns have dependencies (e.g.,\xspace connected by the same entity), \textsc{Zebra}\xspace will first execute the database query whose associated event pattern has a higher pruning score, and then use the execution results to prune the search space of the other database query (by adding additional filters in the WHERE clause).
This way, complex \textsc{Tstl}\xspace search queries with multiple event patterns can be efficiently executed.

For a \textsc{Tstl}\xspace tracking query, we can follow the dependency tracking procedure and naturally decomposes the query into individual dependency retrieval steps: for each event popped from the queue, we retrieve all events that are causally dependent on the event (see \cref{subsec:tracking}).
Thus, for each dependency retrieval step, \textsc{Zebra}\xspace compiles the causal dependency conditions into a small (non-recursive) SQL query or Cypher query (without multi-hop paths).
In addition to the typical dependency conditions like the information flow and time stamps described in \cref{subsec:tracking}, constraints on entities and events specified in the Rule $\langle track\_filter\rangle$ in \cref{bnf:grammar} are also compiled into filters in the SQL/Cypher WHERE clause.
\textsc{Zebra}\xspace can then follow the events popped from the queue to execute the corresponding database queries.
This way, \textsc{Zebra}\xspace can perform constrained dependency tracking with filters on the fly, as opposed to fetching all paths first and then applying filters.

\subsubsection{Optimizing \textsc{Tstl}\xspace Queries Over the In-Memory Graph}
As described in \cref{subsec:language}, users of \textsc{Tstl}\xspace can bind query execution results to a graph variable, and then use the variable as the data source for the subsequent query execution.
Users can also make operations between multiple graph variables to manipulate the execution results.
The underlying mechanism supporting all these language features is the \emph{in-memory buffering and management} of query execution results.
For queries of which the results are bound to variables, \textsc{Zebra}\xspace manages the retrieved subgraph in memory.
Then, when a variable is used as the data source, the same graph instance will be accessed, which will provide a restricted set of events and entities for the subsequent search or tracking.
The presence of such in-memory execution mode helps avoid the large communication cost of re-executing similar queries over the database.
For example, if the security analyst wants to apply extra constraints to a query that was previously executed to further prune unnecessary information, the new query can be directly applied to the maintained in-memory results of the previous query to prune the subgraph, which significantly facilitates progressive investigation.

\section{Motivating Example}
\label{sec:background}

\cref{fig:demo} shows an example multi-stage data leakage attack across three hosts (one attacker host, two victim hosts Host 1 and 2).
We constructed this attack based on Cyber Kill Chain framework~\cite{killchain} and CVE~\cite{cve}.
The attacker (\incode{20.69.152.188}) identifies a victim Host 1 (\incode{13.66.254.172}) in an enterprise network that is vulnerable to the \incode{lighttpd} Shellshock~\cite{shellshock} exploit.
To steal valuable assets from the victim Host 1, the attacker launches a series of attack steps that are divided into four stages:

\begin{itemize}[topsep=0pt, partopsep=0pt, listparindent=\parindent, leftmargin=*, itemsep=1pt]
    \item Stage 1: The attacker leverages Shellshock vulnerability in the \incode{lighttpd} web server on Host 1 to penetrate into Host 1 from the attacker host.

    \item Stage 2: The attacker discovers all the reachable hosts of Host 1 and connects to the discovered host, Host 2, using \incode{ssh}.

    \item Stage 3: The attacker uses \incode{tar} to pack the sensitive files (e.g.,\xspace \incode{/etc/passwd}, \incode{/etc/shadow}) of Host 2 as \incode{sensitive\_data.tar}.

    \item Stage 4: The attacker uses \incode{scp} on Host 1 to fetch the sensitive data \incode{sensitive\_data.tar} from Host 2.
    The attacker then uses \incode{curl} on Host 1 to send the sensitive data to the attacker host.
\end{itemize}

\myparatight{Investigation Procedure Using \textsc{Tstl}\xspace}
From \cref{fig:demo}, we can observe that attack investigation is a process of ``finding a needle in a haystack'': a small number of attack-relevant edges ($20$) are buried in an overwhelmingly large number ($154$K) of irrelevant edges.
The same imbalance observation holds for attack-relevant nodes ($20$ vs. $101$K).
\textsc{Zebra}\xspace tackles this challenging problem via progressively revealing the attack sequence using its DSL, \textsc{Tstl}\xspace.
\cref{fig:query} shows a series of \textsc{Tstl}\xspace queries for progressively investigating the attack on Host 1.
Next, we describe the investigation procedure in detail.

\begin{itemize}[topsep=0pt, partopsep=0pt, listparindent=\parindent, leftmargin=*, itemsep=1pt]

\item Query \circled{1}: Security analyst receives an intrusion alert and uses a \textsc{Tstl}\xspace search query to verify the corresponding malicious pattern on Host 1: a sensitive \incode{tar} file is transferred to an unknown IP.

\item Query \circled{2}: Security analyst tracks the backward dependencies of the \incode{tar} file and finds its creation process \incode{scp}.
The tracking results are bound to an in-memory graph variable \incode{g2}, which will be passed to the subsequent query for further investigation.

\item Query \circled{3}: Security analyst searches the related events of \incode{scp} in the local in-memory graph \incode{g2} and finds that \incode{scp} reads from the socket on Host 2, which verifies the origin of the \incode{tar} file.

\item Query \circled{4}: To further investigate the attack's entry point on Host 1, security analyst tracks the backward dependencies of the malicious \incode{curl} process and binds the tracking results to \incode{g3}.

\item Query \circled{5}: Considering that the attacker is likely on a remote server and using the same IP (i.e.,\xspace \incode{20.69.152.188} revealed in \circled{1}), security analyst searches this IP and relevant processes in \incode{g3}, and reveals the \incode{lighttpd} process.
This indicates that the attack's entry point is the vulnerability in the \incode{lighttpd} web server.

\item Query \circled{6}: Security analyst finally tracks the forward dependencies from the identified entry point, binds the final investigation results to \incode{g5}, and displays the results through \incode{g5}.

\end{itemize}

The final resulting graph \incode{g5} after a series of 6 \textsc{Tstl}\xspace queries is shown in dark black color in \cref{fig:demo}.
As we can see, by using \textsc{Tstl}\xspace to progressively refine the results, most irrelevant nodes and edges are filtered out in \incode{g5} and the entire attack sequence is clearly revealed.
This example demonstrates the effectiveness of user-guided, progressive investigation in revealing the attack sequence from massive system audit logging data and how \textsc{Tstl}\xspace enables this.
\section{Conclusion}

We have presented \textsc{Zebra}\xspace, a system that enables
efficient
attack investigation via
synergistically integrating search and tracking over system audit logs through a domain-specific language, \textsc{Tstl}\xspace.
\section{Discussion}
\label{sec:discussion}

\myparatight{Limitations}
\textsc{Zebra}\xspace relies on the system audit logs captured by system auditing frameworks and parses and stores the collected system audit logging data in databases.
As mentioned in \cref{sec:overview}, attacks on OS kernels, system auditing frameworks, databases, and attacks that are not captured by system auditing are not considered by \textsc{Zebra}\xspace.
Besides, the currently data model of \textsc{Zebra}\xspace considers files, processes, network sockets, and their interaction events.
Certain system entities, like registry locations for Windows, cannot be natively expressed by the underlying model of \textsc{Zebra}\xspace.
When parsing the logs from the DARPA TC cases, we treat registry locations as file entity nodes and edits as file-write event edges.
In addition, the query optimizations employed by \textsc{Zebra}\xspace are restrained to a per-query basis.
This means that locally available information of system dependency graphs assigned to variables aren't considered when querying from remote databases unless the local graph query is explicitly stated (as shown in the rule \emph{$\langle$source\_expr$\rangle$}).
However, by performing semantic analysis across the queries, it is possible to leverage the design of \textsc{Tstl}\xspace to avoid redoing part of queries.
In future work, we plan to add support for additional entities like registries to the language syntax and add cross-query optimizations.
We also plan to improve the level of automation of query construction by exploring approaches like query synthesis~\cite{xu2017sqlnet}.

\myparatight{Forensics of Real-World Attacks}
Advanced Persistent Threats (APT) and other real-world attacks are sophisticated (multi-step attacks exploiting various vulnerabilities) and stealthy (staying dormant for long period).
Due to the advances of log compression techniques~\cite{reduction,reduction2}
and continuing decreases of storage costs, storing system audit logs for months even years becomes affordable.
Furthermore, recent distributed database solutions~\cite{cassandra, hbase} show promising results to improve the analysis performance of the logs.
By operating together with these solutions, \textsc{Zebra}\xspace can be efficiently applied to long-period log data for investigation.

\section{Evaluation}
\label{sec:eval}

\input{implementation.tex}

We deployed \textsc{Zebra}\xspace on a physical testbed to collect real system audit logs and evaluated \textsc{Zebra}\xspace comprehensively on a broad set of attack cases.
In total, the system audit logs used in our evaluations contain $6,808,436$ system entities and $244,749,762$ system events.
Our evaluations aim to answer the following research questions:
\begin{itemize}[topsep=0pt, partopsep=0pt, listparindent=\parindent, leftmargin=*, itemsep=1pt]
    \item \textbf{RQ1:} How effective is \textsc{Zebra}\xspace    in revealing the attack sequence and reducing the size of the system dependency graph?

    \item \textbf{RQ2:} How efficient is \textsc{Zebra}\xspace in executing \textsc{Tstl}\xspace search queries over the big system audit logging data?

    \item \textbf{RQ3:} How efficient is \textsc{Zebra}\xspace in executing \textsc{Tstl}\xspace tracking queries over the big system audit logging data?

    \item \textbf{RQ4:} How concise is \textsc{Tstl}\xspace in specifying search and tracking analyses compared to general-purpose query languages?
\end{itemize}

RQ1 aims to evaluate the overall effectiveness of \textsc{Zebra}\xspace in mitigating the dependency explosion and revealing the attack sequence.
RQ2 and RQ3 aim to evaluate the efficiency of \textsc{Zebra}\xspace in \textsc{Tstl}\xspace query execution, and measure the performance speedup achieved by the \textsc{Tstl}\xspace query scheduler.
RQ4 aims to evaluate the conciseness of \textsc{Tstl}\xspace in expressing complex attack patterns and tracking conditions.

\subsection{Evaluation Setup}
\label{subsec:eval-setup}

The deployed server has an AMD(R) EPYC(R) 7352 (2.30 GHz) CPU and 32GB of RAM running 64-bit Ubuntu 20.04 OS.
To evaluate \textsc{Zebra}\xspace, we constructed an evaluation benchmark of \emph{$28$ attack cases} from four sources:
$8$ multi-host multi-step intrusive attacks based on the Cyber Kill Chain framework~\cite{killchain} and CVE~\cite{cve} (for Linux and Windows hosts),
$10$ attacks based on commonly used exploits in prior studies~\cite{gao2018aiql,liu2018priotracker,hassan2019nodoze} (for Linux hosts),
$5$ malware samples selected from VirusSign (for Windows hosts),
and $5$ cases from the DARPA TC dataset~\cite{tc}.
Except for the DARPA TC cases, we performed the rest $23$ cases on our own hosts ($1$ Windows host and $8$ Linux hosts)
to collect system audit logs.
The deployed server and hosts are frequently used by more than ten active users to perform various daily tasks, including file manipulation, text editing, and software development.
When we perform the attacks and conduct the evaluations, the server and hosts continue to serve other users.
This setup ensures that enough noise of benign background traffic is collected in together with malicious activities, representing the real-world deployment.
The total monitoring length is $10$ days for the $5$ DARPA TC cases and 12 days for our $23$ attack cases.
\cref{tab:case-name} shows the list of all attack cases, which cover various OSs, vulnerabilities (e.g.,\xspace Firefox backdoor, shellshock), and exploits (e.g.,\xspace Drakon APT).

\input{tables/case-name}

\subsubsection{Attacks Based on Commonly Used Exploits}
\label{subsec:common}

We constructed 10 attacks based on commonly used exploits~\cite{gao2018aiql,liu2018priotracker,hassan2019nodoze}:

\emph{(1) Wget Executable (Case malicious\_wget):} The attacker uses \incode{wget} to download an executable script
and executes it.
\emph{(2) Illegal Storage (Case malicious\_illegal\_store):}
A server administrator uses \incode{wget} to download suspicious files to other user's home directory.
\emph{(3) Hide File (Case malicious\_hide\_file):} The attacker downloads a malicious file and hides it by changing its file name and location.
\emph{(4) Backdoor Download (Case malicious\_backdoor\_dl):}
A malicious insider
uses \incode{wget} to download the backdoor malware from a compromised server and hides it among normal files.
\emph{(5) Annoying Server User (Case malicious\_server\_usr):}
The annoying user logs into other user’s home directories on a vulnerable server and downloads a script to write some garbage data.
\emph{(6) Password-Free Theft (Case malicious\_ssh\_theft):}
The attacker logs into other user’s server via \incode{ssh} and appends her public key to the \incode{\~/.ssh/authorized_keys} file to leave a persistent backdoor.
\emph{(7) Wget-GCC-Crash (Case malicious\_gcc\_crash):}
The attacker logs into other's server via \incode{ssh}, uses \incode{wget} to download a C source code file, and uses \incode{GCC} to compile it.
The attacker then executes this malicious executable file to exhaust the memory and crash the system.
\emph{(8) Scan and Login (Case malicious\_scan\_login):}
The attacker uses \incode{Nmap} to explore the accessible servers whose port $22$ is open for SSH connection.
The attacker then uses a script to automatically test if there exists a password-less login with SSH keys to the discovered servers.
\emph{(9) Password Reuse (Case malicious\_pwd\_reuse):}
An administrator decodes the \incode{/etc/shadow} file with the John the Ripper password cracker~\cite{john}, and uses the cracked password to login as another user.
\emph{(10) Cheating Student (Case malicious\_student):}
A cheating student hacks into her school's Apache server and downloads midterm scores.

\subsubsection{Multi-Host Multi-Step Intrusive Attacks}
\label{subsec:multi}

We constructed $8$ multi-host multi-step intrusive attacks based on the Cyber Kill Chain~\cite{killchain} framework and CVE~\cite{cve}.
In these attackers, the attacker used an external host (Command \& Control (C2) server) to perform initial penetration, distribute malware, and exfiltrate data.
The first host compromised by the attacker is named as Host 1, which is a starting point to perform lateral movement and other malicious actions to compromise more hosts inside the network.

\emph{(11) Shellshock Penetration (Case multistep\_penetration):}
The attacker exploits the Shellshock vulnerability~\cite{shellshock} to execute arbitrary code from environment variables on Host 1.

\emph{(12) Password Crack (Case multistep\_password\_crack):}
After the initial penetration on Host 1 in the previous attack, the attacker connects to
Dropbox and downloads an image where C2 server’s IP address is encoded in the image.
This behavior is a common practice shared by APT attacks~\cite{hammertoss,vpnfilter} to evade the detection.
Based on the IP, the attacker downloads a malware from the C2 server to Host 1.
When the malware is executed, it scans the SSH configuration file to locate other reachable hosts in the network.
After this discovery phase, the malware downloads another script from the C2 server and sends it to these discovered hosts to steal password from them.

\emph{(13) Data Leakage (Case multistep\_data\_leakage):}
After compromising the discovered hosts in the previous attack, the attacker steals sensitive data files, by scanning the file system, putting files into a
compressed file, and transferring it back to the C2 server.

\emph{(14) Command-Line Injection (Case multistep\_cmd\_injection):}
The victim host
runs Kodi Mediaplayer,
which exports remote control API as a web service.
One of its input sanitizations has an error that fails to filter invalid input from the outside, which in turn allows the attacker to inject arbitrary command blended in one of its requests.
This attack is inspired by the Jeep-Cherokee attack case~\cite{jeepcherokee} where the attacker gains control over the vehicle from remote.

\emph{(15) Supply Chain Attack (Case multistep\_supply\_chain):}
The attacker discovers that the GNU Wget version that runs on a victim server
is vulnerable to writing arbitrary files by deceptively redirecting requests from HTTP to a compromised FTP server (CVE-2016-4971~\cite{cve3}).
The attacker then embeds a common remote access trojan (RAT) into a Ubuntu package and compromises one of the Ubuntu repositories.
In this way, when the victim server uses \incode{wget} to download Ubuntu packages, the requests are
redirected to the attacker's FTP server, and the downloaded package contains the RAT.
When the victim installs the downloaded packages on the victim server, the RAT is triggered, establishing a C2 channel.

\emph{(16) Phishing Email (Case multistep\_phishing\_email):}
A malicious Trojan is downloaded as an Email attachment and the enclosed macro is triggered by Microsoft Word.
This allows the attacker to run arbitrary code in the context of the current user
(CVE-2017-11882~\cite{cve4}).
After the initial penetration via the phishing email, the attacker steals sensitive data files from the compromised host.

\emph{(17) Netcat Backdoor (Case multistep\_netcat\_backdor):}
A malicious Trojan is downloaded by a victim user from a compromised HTTP server via a deceptive URL (CVE-2018-14574~\cite{cve5}).
The attacker penetrates into the victim host through the Trojan backdoor, and
uses the netcat utility to maintain a persistent Netcat backdoor.

\emph{(18) WannaCry (Case multistep\_wannacry):}
An attacker exploits the EternalBlue vulnerability (CVE-2017-0146~\cite{cve6}) in network to gain access to the machines, and then encrypts data.

\subsubsection{Real-World Malware Cases}
\label{subsubsec:malware}

We obtained a dataset of free Windows malware samples from VirusSign~\cite{virussign}.
We focused on $5$ largest
categories (i.e.,\xspace Trojan.Autorun, Trojan.Danger, Virus.Hijack, Virus.Infector, Virus.Sysbot), and we randomly selected $1$ malware sample for each category
(\emph{Cases malware\_autorun, malware\_danger, malware\_hijack, malware\_infector, and malware\_sysbot}).

\subsubsection{DARPA TC Attack Cases}
\label{subsec:tc}

We selected $5$ attack cases from the DARPA Transparent Computing (TC) Engagement \#5
data release~\cite{darpatc}.
Specifically, the dataset consists of the captured system audit logs of six performer systems (i.e.,\xspace ClearScope, FiveDirections, THEIA, TRACE, CADETS, and MARPLE)
under the attack of the red team using different attack strategies.
The audit logs include both benign system activities and attack activities.
The dataset also includes a ground-truth report with attack descriptions and setups for the cases.
We first retrieved the logs for the five performers with desktop OS's (excluding ClearScope that runs Android).
After examining the logs, we found that the logs for CADETS lack key attributes (e.g.,\xspace file name), making us unable to confirm the attack ground truth to conduct evaluations.
Thus, we do not consider CADETS cases.
Nevertheless, similar attacks were already performed for other performer systems and their logs are covered.
For the other four performer systems, the attack cases for the same performer system are largely similar, and thus we selected at least one attack case from each system to include in our evaluation benchmark.
To use the logs for evaluation, we developed a tool to parse the released logs and loaded the parsed system entities and system events into \textsc{Zebra}\xspace's databases.
Our 5 cases are: \emph{tc\_fivedirections_1}, \emph{tc\_fivedirections_2}, \emph{tc\_marple}, \emph{tc\_theia}, and \emph{tc\_trace}

\subsection{Evaluation Results}
\label{subsec:eval-results}

\subsubsection{RQ1: Effectiveness of \textsc{Zebra}\xspace}
\label{subsubsec:eval-rq1}

\input{tables/query-size}

\myparatight{Effectiveness in Reveal the Attack Sequence}
To evaluate the effectiveness of \textsc{Zebra}\xspace in revealing the attack sequence, for each attack case, we construct a series of \textsc{Tstl}\xspace search and tracking queries for progressively investigating the case.
Specifically, we set the key system events as starting events according to the ground truth, and construct \textsc{Tstl}\xspace queries to reveal the entire attack sequence.
In practice, such information can easily be obtained as detection alerts from intrusion detection systems~\cite{paxson1999bro}.
For example, in the \emph{tc\_theia} case, the ground truth gives ``sshdlog'' as a file written by the attacker to the disk, so we construct a search query with the file writing event as the POI event.
Then, we construct a \textsc{Tstl}\xspace tracking query to track the dependencies of the POI event.
Once we have the first query, we execute it, and then inspect the execution results to construct the next query.
When constructing the queries, we assume no knowledge of the ground truth except for the starting events.

Our evaluation results are as follows: \emph{for all $28$ attack cases, we are able to successfully identify all key attack-relevant entities and events and reveal the entire attack sequences, using $\leq 5$ \textsc{Tstl}\xspace search and tracking queries.}
The investigation results have been verified against the ground truth after the investigation is done.

\myparatight{Effectiveness in Mitigating the Dependency Explosion}
We further evaluate the effectiveness of \textsc{Zebra}\xspace in mitigating the dependency explosion problem, by measuring how much the system dependency graphs can be reduced with fine-grained control of the dependency tracking process provided by \textsc{Tstl}\xspace.
As we have already verified that the attack sequences are preserved in the final graphs, an approach that has higher reduction rate is more powerful in filtering out attack-irrelevant parts.
For the comparison baseline, we select the original
dependency tracking algorithm proposed in \cite{backtracking}.
There also exist approaches that extend over \cite{backtracking} and attempt to refine causal dependencies.
However, these approaches either rely on intrusive system changes~\cite{ma2016protracer,ji2017rain} such as binary instrumentation and kernel customization, or execution profiles~\cite{liu2018priotracker} that are costly to obtain, making their practical adoption still questionable.
It is important to note that the goal of \textsc{Zebra}\xspace is orthogonal to these approaches.
Rather than trying to refine the causal dependencies, \textsc{Zebra}\xspace aims to enable fine-grained control of the tracking and search processes by incorporating user knowledge with a DSL.
Nevertheless, \textsc{Zebra}\xspace can seamlessly integrate with these approaches, by changing the dependency tracking algorithm described in \cref{subsec:tracking}.
Thus, we do not compare with these approaches.

Specifically, for each case, we measure the number of entities and events in the dependency graphs produced by \textsc{Tstl}\xspace tracking queries and the baseline dependency tracking counterparts.
We only include the \textsc{Tstl}\xspace tracking queries with constraints specified, as for the unconstrained tracking, our approach is equivalent to the baseline approach.
\cref{tab:query-size} shows the results.
We observe \emph{a $16.56$x reduction in the number of entities and a $18.46$x reduction in the number of events} across all tracking queries for all cases.
These results demonstrate the effectiveness of human-in-the-loop control in mitigating the dependency explosion.

\subsubsection{RQ2: Efficiency of \textsc{Tstl}\xspace Search Query Execution}
\label{subsubsec:eval-rq2}

\input{tables/aggregated-table}

We measure the runtime performance of \textsc{Zebra}\xspace in executing \textsc{Tstl}\xspace search queries, particularly the performance speedup provided by the \textsc{Tstl}\xspace query scheduler (i.e.,\xspace component-based scheduling described in \cref{subsec:execution}) over the execution plans provided by the relational DBMS PostgreSQL and the graph DBMS Neo4j.
For baseline comparisons, for each \textsc{Tstl}\xspace search query, we construct a semantically equivalent SQL query (using CROSS JOIN) and Cypher query, which specify the same subgraph pattern with the same set of constraints.
To perform the measurement, for each \textsc{Tstl}\xspace search query, we execute it over both the PostgreSQL backend and the Neo4j backend.
The difference lies in which database query will be compiled into once the \textsc{Tstl}\xspace execution engine decomposes the original \textsc{Tstl}\xspace query into components, as described in \cref{subsec:execution}.
Then, we execute the baseline SQL queries on the PostgreSQL backend and the baseline Cypher queries on the Neo4j backend.
Note that having the same storage backend enables us to compare the performance differences between the scheduling plans provided by \textsc{Zebra}\xspace and by the DBMS.

The left part of \cref{tab:aggregated} shows the execution time of the search queries aggregated over $20$ rounds.
The standard deviation is several magnitudes smaller than the mean value, which means that the mean values are reliable.
The large size (more than 220K nodes and 23 million edges) of the DARPA TC attack cases exposes the inefficiency of importing data into Neo4j.
This is because when we import the data into Neo4j, a complete graph needs to be built, which takes a lot of time.
Such a time-consuming data importing process is very costly ($\sim$20 days each case),
so we omit the evaluation of DARPA cases on the Neo4j database (marked with "-").

To further evaluate the performance of different optimization mechanisms, we analyze the execution time of local (i.e.,\xspace over the in-memory graph) and remote (i.e.,\xspace over the database) search queries separately.
To be fair, we make sure that the results of local and remote searches are the same.
\cref{tab:local-remote-search} shows the results.
Note that we only evaluated the cases that didn't raise timeout errors.

\input{tables/local-remote-search}

From \cref{tab:aggregated,tab:local-remote-search}, we have the following observations:
(1) \emph{For \textsc{Tstl}\xspace search queries, \textsc{Tstl}\xspace query scheduler is more efficient than the execution plans provided by PostgreSQL and Neo4j.}
For non-timeout cases, our scheduler is $11.54$x faster than PostgreSQL but only $1.06$x faster than Neo4j on average, other queries are either timeout or out-of-memory (both marked with ``Timeout'').
That is because our optimization mechanisms on search execution work better on reducing workloads for SQL CROSS JOIN clause.
Cypher is designed to search for relationships within small steps, so the execution times of \textsc{Tstl}\xspace(N) and Cypher on non-timeout cases are similar;
(2) \textsc{Tstl}\xspace search queries executed over the PostgreSQL backend are more efficient than the ones over the Neo4j backend.
That is because Neo4j has to load the whole graph into memory before it can execute queries \cite{li2021threat}, which is inefficient.
(3) Both the local in-memory buffering and remote execution scheduling optimization mechanisms contribute to the high efficiency of \textsc{Tstl}\xspace's search execution on the PostgreSQL backend, while only local buffering optimization
contributes to the Neo4j backend.
The reason is analyzed in (1).

\subsubsection{RQ3: Efficiency of \textsc{Tstl}\xspace Tracking Query Execution}
\label{subsubsec:eval-rq3}

We measure the runtime performance of \textsc{Zebra}\xspace in executing \textsc{Tstl}\xspace tracking queries.
For each \textsc{Tstl}\xspace tracking query, we construct a semantically equivalent standalone recursive query in SQL using the recursive WITH clause.
Similarly, we construct a semantically equivalent Cypher query using the path matching clause.
For example, \incode{MATCH\ (start:\{id:123\})-[*1..5]->(end)} matches all the paths (i.e.,\xspace a series of relationships) ranging from 1 hop to 5 hops that start from the $start$ node.
Unfortunately, these clauses lack fine-grained constraints on each hop.
So we have to match all the paths first, then filter out paths that do not satisfy the causal dependencies and our specified constraints (see \cref{subsec:language}).

The right part of \cref{tab:aggregated} shows the average execution time of the tracking queries aggregated over $20$ rounds (with small standard deviation).
Similar to RQ2, we omit the evaluation of DARPA cases on the Neo4j database (marked with "-").
In addition, even if the path matching supports unlimited hops theoretically, the unlimited hop matching hardly stops and often incurs OutofMemory exceptions even on a small graph ($\sim$1K edges).
Taking into account the resulting coverage (compared to unbounded query results) and the number of valid cases (i.e.,\xspace neither timeout nor out-of-memory), we bound the maximum hops of path matching in Cypher queries to 3.

From \cref{tab:aggregated}, we have the following observations:
(1) \emph{For \textsc{Tstl}\xspace tracking queries, \textsc{Tstl}\xspace query scheduler is more efficient than the execution plans provided by PostgreSQL and Neo4j.}
For non-timeout cases, our scheduler is $27.72$x faster than PostgreSQL and $281.38$x faster than Neo4j on average, while other queries are either timeout or out-of-memory;
(2) As the size of the input grows, \textsc{Tstl}\xspace executes much more efficiently than SQL and Cypher queries.
For instance, in the \emph{tc\_fivedirections\_1} case with $225,416$ nodes and $23,051,514$ edges, the SQL query times out after 30 minutes.
(3) \textsc{Tstl}\xspace tracking queries executed over the PostgreSQL backend are more efficient than the ones over the Neo4j backend.

\subsubsection{RQ4: Conciseness of \textsc{Tstl}\xspace}
\label{subsubsec:eval-rq4}

We further compare the conciseness of \textsc{Tstl}\xspace queries with the SQL and Cypher queries mentioned in RQ2 and RQ3, by measuring the number of words excluding comments.
\cref{tab:aggregated} shows the results.
We observe that \textsc{Tstl}\xspace is more concise than SQL and Cypher for all cases.
Specifically, \textsc{Tstl}\xspace is $11.58$x and $21.54$x more concise than SQL for search and tracking queries,
and \textsc{Tstl}\xspace is $1.63$x and $9.10$x more concise than Cypher for search and tracking queries (excluding DARPA TC cases).
This is because compared to SQL and Cypher, \textsc{Tstl}\xspace directly models the high-level, domain-specific concepts (system entities and events) instead of the low-level database concept details.

\section{Introduction}
\label{sec:intro}

Sophisticated cyber attacks, such as Advanced Persistent Threats, have plagued many well-protected businesses~\cite{breach21}.
These attacks exploit multiple types of vulnerabilities to infiltrate into the target system in multiple stages, posing challenges for effective countermeasures.
To counter these attacks, ubiquitous system auditing has emerged as an important approach for monitoring system activities.
System auditing collects system-level auditing events about system calls from OS kernel as system audit logs.
The collected audit logs provide the system-level provenance of all interactions between different system entities (e.g.,\xspace processes, files, network sockets), which further enable approaches to investigate the attacks.

The goal of attack investigation is to reveal the sequence of steps involved in an attack (i.e.,\xspace attack sequence).
It is performed after the attacker compromised the system and is a considerably time-sensitive task.
A timely and thorough investigation helps pinpoint the vulnerable components of the system and protect the system from future attacks of the same type.
By leveraging the system-level provenance, research has proposed to search for attack patterns~\cite{gao2018aiql,shu2018threat} or track the causal dependencies of system events~\cite{backtracking,ma2016protracer,liu2018priotracker,ji2017rain} to reveal the attack sequence.

However, existing approaches have significant limitations for a timely and thorough investigation.
Search-based approaches~\cite{gao2018aiql,shu2018threat} leverage domain-specific query languages (DSLs) to search for subgraph patterns of system events that may indicate malicious behaviors.
However, a key limitation is that their DSLs can only search for events that are located within a close subgraph neighborhood.
Thus, these approaches cannot efficiently reveal faraway events on a long-range attack sequence, which is observed in many of the attacks these days due to their sophisticated, multi-stage nature~\cite{milajerdi2019holmes}.
Tracking-based approaches assume causal dependencies between system entities that are involved in the same system event (e.g.,\xspace a process reading a file)~\cite{backtracking,ma2016protracer,liu2018priotracker,ji2017rain}.
Based on this assumption, these approaches track the dependencies from a Point of Interest (POI) event (e.g.,\xspace an alert event like the creation of a suspicious file) and construct a system dependency graph, in which nodes represent system entities and edges represent system events.
By inspecting the dependency graph, security analysts can reveal the attack sequence by reconstructing the chain of events that lead to the POI event.
However, due to the dependency explosion problem~\cite{reduction}, the dependency graph could be gigantic (containing $>$100K edges) and many of the edges are not relevant to the attack (e.g.,\xspace events that perform irrelevant system activities like loading system libraries).
As a result, it is difficult for security analysts to efficiently reason the graph and identify attack-relevant parts.

\myparatight{Key Insights and Challenges}
In this work, we aim to design and build a system that enables efficient investigation of long-range attack sequences.
Our idea is to \emph{synergistically integrate attack pattern search and causal dependency tracking} to leverage the best of both worlds.
Specifically, we have two key insights:
(1) \emph{User-guided investigation:}
Inspired by the query-based search, we can enable security analysts to leverage their domain knowledge via a DSL to actively guide the tracking process.
This way, we can mitigate the dependency explosion problem by prioritizing the attack-relevant parts and filtering out attack-irrelevant parts.
On the other hand, causal dependency tracking helps reveal the long-range attack sequence, which complements the attack pattern search.
(2) \emph{Progressive investigation:} Attack investigation, in practice, is an iterative process that involves multiple rounds of exploration.
Security analysts can alternate between search and tracking to progressively refine the intermediate investigation results and reveal the attack sequence.
For example, security analysts can first search for some malicious event patterns, and then track the dependencies from the searched events to expand the investigation scope, and then search for specific attack-relevant events to further refine the tracking results.

Synergistically integrating search and tracking is \emph{non-trivial and quite challenging} due to their disparate nature.
First, tracking-based approaches do not have a DSL for user control, and the DSLs of search-based approaches do not have tracking capability.
To seamlessly integrate search and tracking, we need a new flexible and expressive DSL that provides specialized constructs for various types of fine-grained control of tracking and search (e.g.,\xspace prioritizing tracking certain events).
The DSL also needs to provide a unified syntax and is concise and easy to use.
Second, to enable progressive, iterative investigation, the DSL needs to allow users to easily inspect and manipulate intermediate investigation results, and pass the results to subsequent search/tracking analyses.
Third, system auditing produces a huge amount of daily logs (0.5GB $\sim$ 1GB for 1 enterprise host~\cite{reduction}), and hence attack investigation is a procedure of ``finding a needle in a haystack''.
Such big data poses further challenges for the solution to store and query the data efficiently to meet the requirement of a timely investigation

\myparatight{Contributions}
We propose \textsc{Zebra}\xspace ($\sim$15K lines of code), a system that synergistically integrates attack pattern search and causal dependency tracking for efficient attack investigation.
\textsc{Zebra}\xspace was built upon mature system auditing frameworks~\cite{auditd,etw,sysdig} for system audit logging data collection and databases~\cite{postgresql,neo4j} for data storage. This enables \textsc{Zebra}\xspace to leverage the services provided by these mature infrastructures, such as data management, indexing mechanism, and recovery.
In particular, to facilitate a timely user-guided, progressive investigation, \textsc{Zebra}\xspace has two key designs:

(1) \emph{Expressive and Concise Domain-Specific Language:}
To facilitate user-guided investigation, \textsc{Zebra}\xspace provides a novel, expressive, and concise DSL, \emph{Threat Search and Tracking Language (\textsc{Tstl}\xspace)}.
\textsc{Tstl}\xspace treats system entities and system events as first-class citizens to effectively model the domain of system audit logging data, and provides language constructs for specifying different entity types, event types, and entity and event attributes.
Upon these, \textsc{Tstl}\xspace uniquely integrates a collection of language constructs for expressing various types of fine-grained control of search and tracking processes in its search queries and tracking queries.
For example, \textsc{Tstl}\xspace supports tracking with depth and attribute constraints on the tracking paths to effectively constrain the scope of tracking and prioritizing certain system entities and system events.

In addition, to further facilitate progressive investigation, \textsc{Tstl}\xspace supports binding intermediate search and tracking results (i.e.,\xspace subgraphs of system events) to graph variables.
Security analysts can inspect the results through these variables, manipulate these variables to refine the results, and pass these variables to subsequent search/tracking queries to continue the investigation.

\textsc{Tstl}\xspace is expressive, concise, efficient, and intuitive to use.
Compared to the DSLs proposed in existing search-based approaches~\cite{gao2018aiql,shu2018threat,gao2021enabling} that can only search for subgraph patterns, \textsc{Tstl}\xspace provides a novel syntax for fine-grained causal dependency tracking and seamless integration of tracking and search for progressive investigation.
These features distinguish \textsc{Tstl}\xspace from prior DSLs.
Compared to general-purpose query languages (e.g.,\xspace SQL~\cite{sql}, Cypher~\cite{cypher}) that are low-level and verbose, \textsc{Tstl}\xspace is specially designed for investigating system audit logging data and its syntax is high-level and much more intuitive.
Though it is possible to use SQL or Cypher to specify search or tracking queries, as we show in the comparison experiments in \cref{subsec:eval-results}, queries specified in \textsc{Tstl}\xspace are much more efficient and concise.
Moreover, it is hard to use SQL or Cypher to pass intermediate results between queries to progressively refine the investigation results.
All of these make \textsc{Tstl}\xspace a better tool for efficient attack investigation than general-purpose query languages.

(2) \emph{Efficient Language Execution Engine:}
To query the big data efficiently, \textsc{Zebra}\xspace employs specialized optimizations for data storage and \textsc{Tstl}\xspace execution engine.
Specifically, \textsc{Zebra}\xspace employs log reduction techniques to merge excessive system events while preserving adequate information.
To execute a \textsc{Tstl}\xspace query efficiently over the database, \textsc{Zebra}\xspace employs a \emph{component-based scheduling algorithm}.
Specifically, \textsc{Zebra}\xspace decomposes the \textsc{Tstl}\xspace query into components, compiles each component into a semantically equivalent database query, and schedules the execution of these database queries based on their semantics and dependencies.
This scheduling algorithm handles the execution of both search queries and tracking queries over the database.
Compared to the naive execution plan that compiles the \textsc{Tstl}\xspace query into a single large SQL or Cypher query to execute, our scheduling algorithm avoids the weaving of many joins and constraints together (which leads to slow performance) and leverages query semantics to speed up the execution.

Executing queries from the database often serve as an initial step of investigation.
To facilitate the follow-up progressive investigation, \textsc{Zebra}\xspace also supports executing a \textsc{Tstl}\xspace query directly from the previous query execution results.
Specifically, for the intermediate results that have been bound to variables in \textsc{Tstl}\xspace, \textsc{Zebra}\xspace maintains the results as in-memory graphs of system events.
These in-memory graphs can be combined and manipulated via the bound variables, and passed to subsequent queries as their data source for further refinement.
Queries executing in this mode do not need to communicate with the database, and hence the execution time is much faster, facilitating efficient investigation.

\begin{figure*}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/demo.pdf}
    \caption{Partial system dependency graphs of an example multi-stage multi-host data leakage attack case.
    The complete system dependency graphs for the two victim hosts (Host 1, Host 2) contain $100,524$ nodes and $154,353$ edges in total.
    The attack-relevant nodes and edges identified by \textsc{Zebra}\xspace are colored in dark black ($20$ nodes, $20$ edges).
    }
    \label{fig:demo}
\end{figure*}

\myparatight{Evaluation}
We deployed \textsc{Zebra}\xspace on a physical testbed and performed a broad set of attacks to evaluate it.
Our evaluation benchmark consists of $28$ attack cases leveraging various vulnerabilities and exploits, and we collected $245$ million system events in total for evaluation.
The evaluation results demonstrate that:
(1) \textsc{Zebra}\xspace is able to effectively reveal the attack sequences in all attacks.
Compared to baseline causal dependency tracking, \textsc{Zebra}\xspace can significantly reduce the dependency graphs (16.56x in \#nodes, 18.46x in \#edges) thanks to its \textsc{Tstl}\xspace.
(2) \textsc{Tstl}\xspace is much more suitable for a timely, progressive investigation compared to general-purpose query languages.
Specifically, compared to SQL and Cypher, \textsc{Tstl}\xspace queries are much more efficient (for search: 11.54x over SQL, 1.06x over Cypher; for tracking: 27.72x over SQL, 281.38x over Cypher) and concise (for search: 11.58x over SQL, 1.63x over Cypher; for tracking: 21.54x over SQL, 9.10x over Cypher).

To the best of our knowledge, \textsc{Zebra}\xspace is \emph{the first system that provides a DSL for synergistically integrating attack pattern search and causal dependency tracking capabilities for progressive and efficient attack investigation.}
A system demo video is available at~\cite{raptor-demo}.

\section{Related Work}
\label{sec:literature}

\myparatight{Data Provenance}
Data provenance is originally proposed to trace the historical records and origins of data in database system \cite{buneman2001and, woodruff1997supporting}.
This information can help determine the validity and confidence of data.
Data provenance has been widely used in various scenarios, such as fault injection \cite{naughton2009fault}, reproducibility \cite{miles2007requirements}, and so on \cite{simmhan2005survey, freire2008provenance, zafar2017trustworthy, herschel2017survey}.
This paper mainly focuses on the provenance information of system-level entities and events.

\myparatight{Forensic Analysis via System Audit Logs}
Causal dependency tracking based on system auditing data plays a critical role for forensic analysis.
King et al.~\cite{backtracking,backtracking2}
proposed a backward causality tracking\xspace technique by automatically reconstructing a series of events that are dependent on a user-specified POI event.
Recent efforts have been made to mitigate the dependency explosion problem by performing fine-grained dependency tracking~\cite{ma2016protracer,kwon2018mci,ji2017rain,ji2018enabling},
prioritizing dependencies~\cite{liu2018priotracker,hassan2019nodoze},
customizing kernel~\cite{trustkernel},
and optimizing storage~\cite{reduction,reduction2}.
However, these techniques suffer from adoption limitations as they mainly rely on heuristic rules that cause loss of information~\cite{backtracking}, intrusive system changes such as binary instrumentation~\cite{ma2016protracer,kwon2018mci},
or execution profiles that have limited generalizations~\cite{liu2018priotracker,hassan2019nodoze}.
Besides causality tracking\xspace, research has been proposed to search system audit logs for attack investigation, anomaly detection, and threat hunting~\cite{gao2018aiql,gao2018saql,pasquier2018runtime,gao2021enabling}.
The scope of \textsc{Zebra}\xspace is different from all these works, as none of these works proposed to integrate the search and tracking operations via a domain-specific language to facilitate progressive investigation.

\myparatight{Database Query Languages}
Relational databases based on SQL~\cite{sql}
provide language constructs for joins, facilitating the specification of subgraph patterns for search.
However, these languages lack explicit constructs for easily chaining constraints between relations (i.e.,\xspace tables) for tracking dependencies between high-level system events.
Graph databases~\cite{neo4j} provide semantic query languages (e.g.,\xspace Cypher) for chaining constraints among nodes in graphs.
For instance, the path matching clause of Cypher could match variable-length paths.
But it can only specify the same constraints (e.g.,\xspace operation type is ``write'') for all relations rather than fine-grained constraints (e.g.,\xspace causality dependencies) between relations,
which makes it hard to implement various tracking constraints concisely (discussed in \cref{subsubsec:eval-rq2}).
Similarly, NoSQL tools~\cite{chodorow2013mongodb} also lack efficient supports for tracking.
Unlike \textsc{Tstl}\xspace which models the high-level, domain-specific computer system concepts, these general-purpose query languages model low-level database concepts like tables or nodes.
This leads to verbose queries that are hard to write and revise, hindering the iterative attack investigation process.

\myparatight{Security-Related Languages}
There exist domain-specific languages in a variety of security fields that have a well-established corpus of low level algorithms, such as threat descriptions~\cite{cybox, stix}, secure overlay networks~\cite{mace, networklang}, and network intrusions~\cite{chimera, lambda}.
These languages are explicitly designed to solve domain-specific problems, providing specialized constructs for their particular problem domain and eschewing irrelevant features.
In contrast to these languages, \textsc{Tstl}\xspace focuses on facilitating integration of search and tracking for efficient attack investigation.
The language features provided by \textsc{Tstl}\xspace center around specifying various types of queries with constraints and manipulating resulting graphs generated from \textsc{Tstl}\xspace queries.
Splunk~\cite{splunk} and Elasticsearch~\cite{elasticsearch} are distributed search and analytic engine for application logs, which provide search languages based on keywords and shell-like piping.
These languages are too simple to support complex analytics like subgraph search or causality tracking, as compared to \textsc{Tstl}\xspace.

\section{System Overview}
\label{sec:overview}

\begin{figure*}[t]
    \centering
    \includegraphics[width=.7\linewidth]{figs/arch.pdf}
    \caption{The architecture of \textsc{Zebra}\xspace}
    \label{fig:arch}
\end{figure*}

\cref{fig:arch} shows the architecture of \textsc{Zebra}\xspace.
\textsc{Zebra}\xspace leverages monitoring agents (built upon mature system auditing frameworks~\cite{sysdig,etw,auditd}) deployed across hosts to collect system audit logs (\cref{subsec:auditing}).
\textsc{Zebra}\xspace then parses the collected audit logs into a sequence of system events among system entities (e.g.,\xspace files, processes, network sockets), and sends the parsed data to the central database for storage (\cref{subsec:storage}).
Before inserting the data into the database, \textsc{Zebra}\xspace employs state-of-the-art log reduction techniques~\cite{reduction} to merge excessive system events so that data can be stored and queried more efficiently with the critical causal dependency still preserved.

On top of the database, \textsc{Zebra}\xspace provides a DSL, \textsc{Tstl}\xspace, for investigating attack behaviors from the collected data.
\textsc{Tstl}\xspace uniquely integrates a collection of constructs for various types of attack pattern search and causal dependency tracking analyses, as well as the synergistic integration of the analyses to progressively refine the investigation results (\cref{subsec:language}).
For an input \textsc{Tstl}\xspace query, the language parser performs syntactic and semantic of it.
The execution scheduler then generates an optimized execution plan based on our scheduling algorithm and schedules the query execution.
In addition, execution results that are bound to variables in the query specification are managed in memory and passed to subsequent queries for progressive refinement (\cref{subsec:execution}).
A web GUI is provided to facilitate query construction and results inspection.

\myparatight{Threat Model}
Our threat model follows the threat model of prior works on system auditing~\cite{backtracking,ma2016protracer,liu2018priotracker,hassan2019nodoze,ji2017rain,gao2018aiql,gao2018saql,shu2018threat}.
We assume an outside attacker attacks the system from outside: the attacker either utilizes the vulnerabilities in the system or convinces the user to download a file with malicious payload.
We also assume that OS kernels and kernel-layer auditing framework are part of our trusted computing base, and that the system audit logging data collected from kernel space is not tampered.
Any kernel-level attacks that deliberately compromise security auditing systems are beyond the scope of this work.
Existing software and kernel hardening techniques~\cite{trustkernel,tamperlog} can be used to further secure log storage.
We also do not consider the attacks performed using implicit flows (e.g.,\xspace side channels) or inter-procedural communications that do not go through kernel-layer auditing and thus cannot be captured by the underlying system auditing frameworks.
Finer-grained auditing tools that capture memory traces or program analysis techniques can further be used to address these types of  attacks.