# Parsing Expression GLL

Moss, Aaron
<EMAIL_ADDRESS>This work was funded by a Shiley grant at the University of
Portland. Harrington, Brynn
<EMAIL_ADDRESS>Hoppe, Emily
<EMAIL_ADDRESS>
###### Abstract

This paper presents an extension of the GLL parsing algorithm for context-free
grammars which also supports parsing expression grammars with ordered choice
and lookahead. The new PEGLL algorithm retains support for unordered choice,
and thus parses a common superset of context-free grammars and parsing
expression grammars. As part of this work, the authors have modified an
existing GLL parser-generator to support parsing expression grammars, adding
operators for common parsing expressions and modifying the lexer algorithm to
better support ordered choice.

##  1 Introduction

The inherently unambiguous nature of parsing expression grammars (PEGs) makes
them an attractive choice for modelling structured text such as programming
languages and computing data formats, but in practice the superior performance
of parsers based on context-free grammars (CFGs) has led to CFGs being more-
widely used, despite the difficulty of disambiguating them. This work is an
initial effort toward a unified framework that provides the advantages of both
grammar formalisms: it is an algorithm adopted from an efficient, general-
purpose CFG parser that supports PEG semantics without discarding support for
the unordered choice operator of CFGs in cases where that ambiguity may be
desirable.

More specifically, this paper presents a modification of the GLL parser-
generator of Scott & Johnstone[1, 2]. The key contribution is the _FailCRF_
data structure, which adds a failure path to Scott & Johnstone’s call-return
forest; the addition of a failure path allows the lookahead and ordered choice
operations of the PEG formalism to be supported. The authors have extended
Ackerman’s GoGLL[3] parser-generator to implement this new algorithm, adding
syntactic sugar for common PEG operators and modifying the lexer algorithm to
allow the PEG parser to override the usual maximal-munch rule.

##  2 Parsing Expression Grammars

The primary difference between parsing expression grammars and the more
familiar context-free grammars is _ordered choice_ : PEGs, as a formalism of
recursive-descent parsing introduced by Ford [4], do not try subsequent
alternatives of an alternation if an earlier alternative matches. The other
significant difference between the PEG and CFG formalisms are the PEG
_lookahead_ expressions, $\mathord{!}\alpha$ and $\&\alpha$, which match only
if the subexpression $\alpha$ does not (resp. does) match, but consume no
input regardless. These lookahead operators provide the infinite lookahead of
the PEG formalism. The other fundamental PEG operators act much like their CFG
equivalents, and are described in Fig. 1 as functions over an input string $s$
drawn from some alphabet $\Sigma$ producing either a (matching) suffix of $s$
or the special value $\mathsf{fail}\not\in\Sigma^{*}$. In summary, the _string
literal_ $u$ matches and consumes the string $u$, the _empty expression_
$\varepsilon$ always matches without consuming anything, while the _failure
expression_ $\varnothing$ never matches. A _nonterminal_ $A$ is replaced by
the parsing expression $\mathcal{R}(A)$ it corresponds to. The _sequence_
expression $\alpha\beta$ matches $\alpha$ followed by $\beta$, while the
_ordered choice_ expression $\alpha/\beta$ only tries $\beta$ if $\alpha$ does
not match. To differentiate CFG _unordered choice_ , it is represented in this
paper as $\alpha|\beta$.

$\begin{aligned} u(s)&=\begin{cases}v&s=uv\\\
\mathsf{fail}&\text{otherwise}\end{cases}\\\ \varepsilon(s)&=s\\\
\varnothing(s)&=\mathsf{fail}\\\
\mathord{!}\alpha(s)&=\begin{cases}s&\alpha(s)=\mathsf{fail}\\\
\mathsf{fail}&\text{otherwise}\end{cases}\\\
\&\alpha(s)&=\begin{cases}s&\alpha(s)\neq\mathsf{fail}\\\
\mathsf{fail}&\text{otherwise}\end{cases}\end{aligned}~{}~{}~{}~{}\begin{aligned}
A(s)&=(\mathcal{R}(A))(s)\\\
\alpha\beta(s)&=\begin{cases}\beta(\alpha(s))&\alpha(s)\neq\mathsf{fail}\\\
\mathsf{fail}&\text{otherwise}\end{cases}\\\
\alpha/\beta(s)&=\begin{cases}\alpha(s)&\alpha(s)\neq\mathsf{fail}\\\
\beta(s)&\text{otherwise}\end{cases}\end{aligned}$ Figure 1: Formal
definitions of parsing expressions

##  3 GLL Parsing

_Generalized LL_ (GLL) parsing, introduced by Scott & Johnstone[1, 5], extends
the power of LL parsing to all CFGs through use of a _call-return forest_
(CRF) to represent the recursive-descent call stack of the LL parsing
algorithm. For efficiency, the CRF is implemented using the _graph-structured
stack_ (GSS) data structure introduced by Tomita[6] for the GLR parsing
algorithm. The gist of the GLL approach is that each CRF node represents a
function call (equivalently, nonterminal invocation) in a recursive-descent
parse, and includes an input position, a nonterminal to match, and a grammar
slot to return to on completion. The graph structure of this stack comes from
a dynamic de-duplication of CRF nodes which share a nonterminal and input
position, changing a stack data structure into a directed acyclic graph (DAG).
The GLL algorithm keeps a queue of CRF nodes which are pending parsing, and
handles the nondeterminism of unordered choice by enqueuing a CRF node for
each choice.

Scott et al.[5] introduced _binary subtree representation_ (BSR) sets as an
output format to represent nonterminal matches in GLL. The essential insight
is that, while the traditional _shared packed parse forest_ (SPPF)[6] data
structure representing possible parse trees requires significant complication
in the parser algorithm to properly store and update edges between parse tree
nodes, those edges can be efficiently reconstructed from an indexed set of
edgeless parse-tree nodes (the BSR set) with minimal added information.

A BSR element is a 4-tuple containing a _grammar slot_
$X::=\alpha\theta\cdot\beta$, and three input indices $i$, $j$, and $k$,
$i\leq j\leq k$. The BSR element represents a successful match of the
nonterminal $X$ up to the end of $\theta$, the single terminal or nonterminal
immediately before the dot of the grammar slot; $i$ is the input index where
$X$ began to match, $j$ is the index where $\theta$ began to match, and $k$ is
the index where $\theta$ finished matching. Note that if $\beta=\varepsilon$,
the BSR node represents a complete match of $X$. Parse trees can be
straightforwardly reconstructed from BSR sets: a predecessor of a BSR element
$(X::=\alpha\theta\cdot\beta,i,j,k)$ is any element
$(X::=\alpha\cdot\theta\beta,i,\ell,j)$, while its child where $\theta$ is
some nonterminal $A$ is any element $(A::=\delta\cdot,j,m,k)$. Successor and
parent elements can be defined analogously.

##  4 Parsing Expression GLL

The _Parsing Expression GLL_ (PEGLL) algorithm introduced in this paper uses
similar data structures and abstractions as GLL for CFGs. The main loop is
outlined in Figure 2; it first initializes an empty queue $R$ of slot
descriptors to parse, an empty cache $U$ of previously seen slot descriptors,
and an empty set $T$ of BSR elements to report. It then queues the start rule
of the grammar at input position 0 for parsing, parses each descriptor, and
completes by returning whether or not the start rule matched at position 0.
Note that (unlike CFGs), PEGs match prefixes of their input, so the start rule
may only consume the input up to some index $k$; if this behavior is not
desired, a match can be returned only if $k$ is the length of the input
string.

Figure 2: PEGLL main loop

$R\leftarrow\emptyset$, $U\leftarrow\emptyset$, $T\leftarrow\emptyset$

addNt($S$, 0)

while $R\neq\emptyset$ do

$(L,c_{U},c_{I})\leftarrow R$.remove

$t\leftarrow$ tokens($c_{I}$) $t^{\prime}\leftarrow t$

loop

switch $L$

$\langle$ generate code for each rule $R$ $\rangle$

end switch

nextSlot:

end loop

nextDesc:

end while

if $\exists\alpha,j,k,(S::=\alpha\cdot,0,j,k)\in T$ then

return match at maximal such $k$

else

return $\mathsf{fail}$;

end if

The primary thing the loop in Figure 2 does is dispatch the current descriptor
to the code which executes its parse. The code for each nonterminal may be
generated according to the patterns in Figures 3 and 4. This parser-generator
assumes any ordered choice expressions are at the very top level of a
nonterminal (parenthesized subexpressions are added as syntactic sugar, see
Section 4.2). A label is then generated for each alternate, failing over to
the next alternate if it does not match, with a synthesized failure alternate
at the end of each alternation.

Figure 3: Pattern for a nonterminal $X::=\tau_{1}/\ldots/\tau_{p},p\geq 1$

case $X::=\cdot\tau_{1}$:

$\langle$ generate code for $X::=\cdot\tau_{1}$ with failure path
$X::=\cdot\tau_{2}$ $\rangle$

rtn($X$, $c_{U}$, $c_{I}$); goto nextDesc

$\vdots$

case $X::=\cdot\tau_{p}$:

$\langle$ generate code for $X::=\cdot\tau_{p}$ with failure path
$X::=\cdot\varnothing$ $\rangle$

rtn($X$, $c_{U}$, $c_{I}$) goto nextDesc

case $X::=\cdot\varnothing$:

rtn($X$, $c_{U}$, $\mathsf{fail}$) goto nextDesc

Figure 4: Pattern for a nonterminal $X::=\varepsilon$

case $X::=\cdot\varepsilon$:

$T\leftarrow T\cup{(X::=\varepsilon\cdot,c_{I},c_{I},c_{I})}$

rtn($X$, $c_{U}$, $c_{I}$) goto nextDesc

The rtn$(X,c_{U},c_{I})$ function in PEGLL code is detailed below in Figure 7,
but its essential purpose is to modify the “call stack” in the CRF graph
consistently with a recursive call to the nonterminal $X$ at position $c_{U}$
returning at position $c_{I}$.

To parse each of the sequence expressions $\tau_{i}$ inside a nonterminal
alternative, PEGLL repeatedly executes the appropriate code for each
expression in the sequence, moving to the failure path if that expression does
not work. The code patterns for the sequence expression are in Figure 5, while
the code patterns for each atomic expression are in Figure 6. Terminal matches
advance the input index $c_{I}$ to the right extent $r$ of the token and find
the new tokens $t$ at that position, while mid-sequence errors reset $c_{I}$
and $t$ to their initial values in the descriptor, $c_{U}$ and $t^{\prime}$.
Note also that nonterminal calls preserve the failure path from their caller,
and in particular that negative-lookahead expressions swap the success and
failure results of the call.

Figure 5: Pattern for a sequence $X::=\cdot x_{1}\ldots x_{d}$ with failure
path $L_{f}$

$r\leftarrow$ testSelect($X::=\cdot x_{1}\ldots x_{d}$, $t$)

if testSelect failed then

report error

$(L,c_{I},t)\leftarrow(L_{f},c_{U},t^{\prime})$ goto nextSlot

end if

$\langle$ generate code for $X::=x_{1}\cdot x_{2}\ldots x_{d}$ with failure
path $L_{f}$ $\rangle$

$\vdots$

$\langle$ repeat for remaining atoms $x_{2}\ldots x_{d}$ in sequence $\rangle$

Figure 6: Pattern for an atomic expression $X::=\alpha\varphi\cdot\beta$ with
failure path $L_{f}$

$\varphi=a$ $\implies$

$R\leftarrow R\cup(X::=\alpha a\cdot\beta,c_{U},c_{I},r)$

$c_{I}\leftarrow r$

$t\leftarrow$ tokens($c_{I}$)

$\varphi=Y$ $\implies$

call($X::=\alpha~{}Y\cdot\beta$, $L_{f}$, $Y$, $c_{U}$, $c_{I}$) goto nextDesc

case $X::=\alpha~{}Y\cdot\beta$:

$\varphi=\&Y$ $\implies$

call($X::=\alpha~{}\&Y\cdot\beta$, $L_{f}$, $Y$, $c_{U}$, $c_{I}$) goto
nextDesc

case $X::=\alpha~{}\&Y\cdot\beta$:

$\varphi=\mathord{!}Y$ $\implies$

call($L_{f},X::=\alpha~{}\mathord{!}Y\cdot\beta$, $Y$, $c_{U}$, $c_{I}$) goto
nextDesc

case $X::=\alpha~{}\mathord{!}Y\cdot\beta$:

Together, the helper functions call and rtn simulate the call stack of a
recursive-descent PEG parser; full code is in Figure 7. The significant
difference between the _FailCRF_ of PEGLL and the _CRF_ of Scott et al.[5] is
that edges in the _FailCRF_ are labelled as either “match” edges or “fail”
edges, representing successful and unsuccessful return paths, respectively.
The motivation for this modification is handling negative lookahead
expressions — $\mathord{!}X$ matches only if $X$ does not, and thus the CRF
needs to encode the failure of $X$ as the trigger of a move from slot
$Y::=\alpha\cdot\mathord{!}X\beta$ to slot $Y::=\alpha\mathord{!}X\cdot\beta$.
Fail edges are also used to encode the ordered choice rule; while the GLL
algorithm attempts to parse all alternates of a nonterminal concurrently,
PEGLL attempts one at a time, following its fail edge to the next alternate if
that one fails.

In more detail, the call$(L_{m},L_{f},X,i,j)$ function enqueues parsing of
nonterminal $X$ at position $j$, returning to slot $L_{m}$ on match or $L_{f}$
on failure, where $L_{m}$ or $L_{f}$ began parsing at position $i$. The
rtn$(X,j,h)$ function reports the result of parsing nonterminal $X$ begining
at position $j$, where $h$ is either the last consumed position or the special
value $\mathsf{fail}$ indicating that the parse did not succeed. For
convenience, this presentation assumes the call-return forest (CRF) is stored
in a global cache. The “popped cache” of previously-parsed results is included
to allow updating of previous parse results when they are used in a new
context and also assumed to be global.

Figure 7: Code for call and rtn functions

function call(slot $L_{m}$, slot $L_{f}$, nonterminal $X$, int $i$, int $j$)

$u_{m}\leftarrow$ CRF node $(L_{m},i)$, created if not in cache

$u_{f}\leftarrow$ CRF node $(L_{f},i)$, created if not in cache

$v\leftarrow$ CRF node $(X,j)$, created if not in cache

if $v$ was not previously in cache then

add a match edge from $v$ to $u_{m}$ and a fail edge from $v$ to $u_{f}$

addNt($X$, $j$)

else

if there is not a match edge from $v$ to $u_{m}$ then

add a match edge from $v$ to $u_{m}$

for all $(X,j,h),h\neq\mathsf{fail}$ in popped cache do

addMatch($L_{m}$, $i$, $j$, $h$)

end for

end if

if there is not a fail edge from $v$ to $u_{f}$ then

add a fail edge from $v$ to $u_{f}$

for all $(X,j,\mathsf{fail})$ in popped cache do

addFail($L_{f}$, $i$, $j$)

end for

end if

end if

end function

function rtn(nonterminal $X$, int $j$, int $h$)

if $(X,j,h)$ not in popped cache then

add $(X,j,h)$ to popped cache

for all children $(L,i)$ of $(X,j)$ in the CRF do

if $h\neq\mathsf{fail}$ then

addMatch($L$, $i$, $j$, $h$)

else

addFail($L$, $i$, $j$)

end if

end for

end if

end function

In addition to call-stack management, a PEGLL parser-generator depends on
helper functions to fill the descriptor queue $R$, descriptor cache $U$, and
the BSR set $T$ representing the parse forest. The descriptor queue management
functions are all in Figure 8. addMatch and addFail enqueue the next
descriptor after a nonterminal match or failure, accounting for the fact that
lookahead expressions consume no input and adding a BSR element for matches.
addNt is a convenience function which enqueues the first alternate of a
nonterminal in the descriptor queue. addDesc checks if a given descriptor has
already been processed, adding it to the descriptor queue and the cache of
processed descriptors if not.

Figure 8: Code for descriptor queue management functions

function addMatch(slot $L$, int $i$, int $j$, int $h$)

$T\leftarrow T\cup{(L,i,j,h)}$

if there is a lookahead expression before the dot in $L$ then

addDesc($L$, $i$, $j$)

else

addDesc($L$, $i$, $h$)

end if

end function

function addFail(slot $L$, int $i$, int $j$)

if there is a lookahead expression before the dot in $L$ then

addDesc($L$, $i$, $j$)

else

addDesc($L$, $i$, $i$)

end if

end function

function addNt(nonterminal $X$, int $i$)

$L\leftarrow$ initial slot of first alternate of $X$

addDesc($L$, $i$, $i$)

end function

function addDesc(slot $L$, int $i$, int $h$)

if $(L,i,h)\not\in U$ then

$R\leftarrow R\cup{(L,i,h)}$

$U\leftarrow U\cup{(L,i,h)}$

end if

end function

###  4.1 Lexing

Traditional maximal-munch lexers interact poorly with PEG parsers; in
particular, the recursive-descent structure of a parsing expression grammar
may impose context-sensitive priorities between tokens, and the usual
scannerless design of a PEG may result in difficult-to-decompose token sets.
Nonetheless, experience [3, 7] has shown that a separate lexing pass is a
useful performance optimization. As such, the PEGLL parser-generator uses a
regular-expression lexer modified from the traditional maximal-munch approach
[8]. Rather than returning a single maximal-munch token at a given input
position, as in the classical algorithm , the PEGLL lexer returns (from the
tokens$(i)$ function) a map of all the tokens which match starting at position
$i$ to their greatest right extent, defering the choice of which token to
actually match to the PEG rules in the parser. The testSelect function,
described in Figure 9 in the parser is used to check if any tokens in the
FIRST set of the expression [9] are also present in the token set returned
from the lexer.

Figure 9: Code for testSelect function

function testSelect(slot $L$, token set $T$, int $c_{I}$)

$b\leftarrow-1$

if $L$ is nullable then $b\leftarrow c_{I}$

end if

for all $(t,r)$ in $T$ do

if $r>b$ and $t\in FIRST(L)$ then $b\leftarrow r$

end if

end for

return $b$

end function

###  4.2 Syntactic Sugar

The preceding discussion has outlined how PEG semantics are supported within
the framework of the GLR algorithm; however, support for the fundamental PEG
operators does not cover how several common PEG idioms are supported. Much
like the EBNF notation for CFGs, PEGs typically support the “syntactic sugar”
operators defined in Figure 10 for optional and repeated matches. The
$\alpha?$, $\alpha^{*}$, and $\alpha^{+}$ operators have their usual semantics
of match $\alpha$ zero-or-one, zero-or-more, and one-or-more times,
respectively, though note that the ordered-choice semantics of PEGs imply
greedy match. The PEGLL parser supports expressions using these operators by
replacing such expressions during AST generation with a fresh nonterminal
defined as in Figure 10.

$\displaystyle\mathcal{R}_{\alpha?}$ $\displaystyle=\alpha/\varepsilon$
$\displaystyle\mathcal{R}_{\alpha^{*}}$
$\displaystyle=\alpha\mathcal{R}_{\alpha^{*}}/\varepsilon$
$\displaystyle\mathcal{R}_{\alpha^{+}}$
$\displaystyle=\alpha\mathcal{R}_{\alpha^{*}}$ Figure 10: Each syntactic sugar
expression $\varphi$ is replaced by a fresh nonterminal
$\mathcal{R}_{\varphi}$ defined as in this table.

###  4.3 Unordered Choice

PEGLL also supports an unordered-choice operator; the main challenge in
implementing unordered choice in PEGLL is determining when to trigger the
failure path for a nonterminal. PEGLL introduces the failure paths in the
FailCRF data structure to support the sequential nature of ordered choice –
when one alternate fails, it enqueues the next, and when the final alternate
fails the algorithm marks the failure of the entire nonterminal. Unordered
choice, by contrast, has concurrent semantics; all alternates can conceptually
be executed in parallel (as in Scott & Johnstone’s GLL [1, 2]), and the
nonterminal only fails if _all_ alternates fail.

The approach taken by PEGLL is formalized in Figure 11, but the essential idea
is to duplicate all alternates of an unordered choice into a _pass_ alternate
and a _fail_ alternate. Matching of an unordered choice begins with the first
fail alternate, and proceeds sequentially through the alternates in source
order, as in PEGLL’s handling of ordered choice. Fail alternates all enqueue
the next fail alternate on failure, or the next pass alternate on success,
while pass alternates enqueue the next pass alternate on either success or
failure; the final fail alternate marks the failure of the nonterminal on
failure, while any alternate that succeeds marks the success of the
nonterminal. The effect of this duplication of alternates is to encode the
failure or success of previous unordered alternates in the control-flow of the
algorithm, rather than modifying the FailCRF to store this information in the
data structure. This choice was made to avoid a memory-usage penalty in all
FailCRF nodes to support unordered choice, but empirical investigation of the
relative trade-offs of both approaches would be a fruitful direction for
future work.

Figure 11: Pattern for an unordered-choice nonterminal
$X::=\tau_{1}|\ldots|\tau_{p},p\geq 1$

case $X_{fail}::=\cdot\tau_{1}$:

$\langle$ generate code for $X::=\cdot\tau_{1}$ with failure path
$X_{fail}::=\cdot\tau_{2}$ $\rangle$

rtn($X$, $c_{U}$, $c_{I}$);

$(L,c_{I},t)\leftarrow(X_{pass}::=\cdot\tau_{2},c_{U},t^{\prime})$ goto
nextSlot

case $X_{pass}::=\cdot\tau_{2}$:

$\langle$ generate code for $X::=\cdot\tau_{2}$ with failure path
$X_{pass}::=\cdot\tau_{3}$ $\rangle$

rtn($X$, $c_{U}$, $c_{I}$);

$(L,c_{I},t)\leftarrow(X_{pass}::=\cdot\tau_{3},c_{U},t^{\prime})$ goto
nextSlot

$\vdots$

case $X_{fail}::=\cdot\tau_{p}$:

$\langle$ generate code for $X::=\cdot\tau_{p}$ with failure path
$X_{fail}::=\cdot\varnothing$ $\rangle$

rtn($X$, $c_{U}$, $c_{I}$) goto nextDesc

case $X_{fail}::=\cdot\varnothing$:

rtn($X$, $c_{U}$, $\mathsf{fail}$) goto nextDesc

##  5 Related Work

There are a number of pre-existing approaches to PEG parsing; Ford [4]
introduced the PEG formalism and two algorithms, a backtracking _recursive
descent_ algorithm and a memoized _packrat_ algorithm. In practice, recursive
decent is more efficient, but has exponential worst-case runtime, while
packrat trades increased space and time in the common case for linear worst-
case runtime[10]; most subsequent work has attempted to mitigate one or both
of these shortcomings. Mizushima et al. [11] use _cut operators_ to reduce the
memory usage of packrat parsing, while Kuramitsu [12] and Redziejowski [13]
use heuristic table-trimming mechanisms to similar effect. Medeiros &
Ierusalimschy [14] and Henglein & Rasmussen [15] have developed a parsing
machine approach and a tabular parsing algorithm, respectively, both of which
have some evidence of efficient performance. Moss [16] and Garnock-Jones et
al. [17] have independently developed derivative parsing algorithms for PEGs,
neither of which claim improved performance, but which allow use of PEGs with
algorithmic tools based on derivative parsing. Similarly to this work, Chida &
Kuramitsu [18] have extended the PEG formalism to include unordered choice.
Medeiros et al.[19] and Hutchinson [20] have developed PEG parsers that accept
left-recursive grammars, while Redziejowski [21] has developed a grammar re-
writing scheme that accomplishes the same end.

Scott & Johnstone’s GLL algorithm [1, 2] is based on the GLR algorithm of
Tomita[6]. The PEGLL implementation (based on Ackerman’s GoGLL [3]) also uses
a modified call-return forest (CRF) for control flow and a binary subtree
representation (BSR) for parse results, both as in Scott et al.[5]. Afroozeh &
Izmaylova [22] have contributed performance improvements and extensions to the
original GLL algorithm. Parr et al.[23] have developed the _ALL(*)_ parsing
algorithm, with similar power to GLL but better reported runtime performance.

##  6 Conclusion & Future Work

This paper has described PEGLL, a new algorithm for parsing parsing expression
grammars, based on Scott & Johnstone’s GLL [1, 2]. The primary contribution is
the FailCRF data structure, which adds failure paths to GLL’s call-return
forest, and code-generation algorithms to implement PEG semantics on top of
this data structure. In addition to supporting the fundamental ordered-choice
and lookahead operators of PEG, PEGLL also includes support for repetition
operators as syntactic sugar, and also for CFG-style unordered choice using a
duplication approach to track whether any of the unordered alternates have
matched.

An Apache-licenced implementation of PEGLL is available on
GitHub111https://github.com/bruceiv/pegll; this implementation passes the
research team’s internal correctness tests, but performance testing is left to
future work. In addition to measuring and optimizing the performance of the
PEGLL algorithm, a straightforward piece of future work would be to expand the
expressivity of PEGLL’s operator set; parenthesized subexpressions would be a
natural expansion, as would more variants on the repetition operators – in
particular, non-greedy variants could be implemented by using unordered choice
instead of ordered choice in the generated nonterminals.

A more ambitious advance would be to support left-recursive rules in PEGLL.
Combined with PEGLL’s existing support for unordered choice, allowing left-
recursive rules would make the set of languages parsed by PEGLL a superset of
both parsing-expression languages and context-free languages, allowing
language designers to apply the idioms and capabilities of both formalisms as
desired. Given that GLL already supports left-recursive rules [1] and a number
of approaches have been suggested for PEG-parsing as well [19, 20, 21], this
goal should be achievable.

## References

  * [1] E. Scott and A. Johnstone, “GLL parsing,” Electronic Notes in Theoretical Computer Science, vol. 253, no. 7, pp. 177–189, 2010.
  * [2] E. Scott and A. Johnstone, “Structuring the GLL parsing algorithm for performance,” Science of Computer Programming, vol. 125, pp. 1–22, 2016\.
  * [3] M. Ackerman, “GoGLL.” https://github.com/goccmack/gogll, 2019.  accessed 24-Nov-2021.
  * [4] B. Ford, “Packrat parsing: a practical linear-time algorithm with backtracking,” Master’s thesis, Massachusetts Institute of Technology, September 2002.
  * [5] E. Scott, A. Johnstone, and L. T. van Binsbergen, “Derivation representation using binary subtree sets,” Science of Computer Programming, vol. 175, pp. 63–84, 2019.
  * [6] M. Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, vol. 8.  Springer Science & Business Media, 1985.
  * [7] N. Laurent, Principled Procedural Parsing.  PhD thesis, Université catholique de Louvain, 2019.
  * [8] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques & Tools.  Boston: Pearson Education, second ed., 2007.
  * [9] R. R. Redziejowski, “Applying classical concepts to parsing expression grammar,” Fundamenta Informaticae, vol. 93, no. 1-3, pp. 325–336, 2009\.
  * [10] A. Moss, “Derivatives of parsing expression grammars,” in Proceedings 15th International Conference on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, September 4-6, 2017., pp. 180–194, 2017.
  * [11] K. Mizushima, A. Maeda, and Y. Yamaguchi, “Packrat parsers can handle practical grammars in mostly constant space,” in Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE ’10, (New York, NY, USA), pp. 29–36, ACM, 2010.
  * [12] K. Kuramitsu, “Packrat parsing with elastic sliding window,” Journal of Information Processing, vol. 23, no. 4, pp. 505–512, 2015.
  * [13] R. R. Redziejowski, “Parsing expression grammar as a primitive recursive-descent parser with backtracking,” Fundamenta Informaticae, vol. 79, no. 3-4, pp. 513–524, 2007.
  * [14] S. Medeiros and R. Ierusalimschy, “A parsing machine for PEGs,” in Proceedings of the 2008 Symposium on Dynamic Languages, DLS ’08, (New York, NY, USA), pp. 2:1–2:12, ACM, 2008.
  * [15] F. Henglein and U. T. Rasmussen, “Peg parsing in less space using progressive tabling and dynamic analysis,” in Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2017, (New York, NY, USA), pp. 35–46, ACM, 2017.
  * [16] A. Moss, “Simplified parsing expression derivatives,” in International Conference on Language and Automata Theory and Applications, pp. 425–436, Springer, 2020.
  * [17] T. Garnock-Jones, M. Eslamimehr, and A. Warth, “Recognising and generating terms using derivatives of parsing expression grammars,” arXiv preprint arXiv:1801.10490, 2018.
  * [18] N. Chida and K. Kuramitsu, “Parsing expression grammars with unordered choices,” Journal of Information Processing, vol. 25, pp. 975–982, 2017\.
  * [19] S. Medeiros, F. Mascarenhas, and R. Ierusalimschy, “Left recursion in parsing expression grammars,” Science of Computer Programming, 2014.
  * [20] L. A. Hutchison, “Pika parsing: reformulating packrat parsing as a dynamic programming algorithm solves the left recursion and error recovery problems,” arXiv preprint arXiv:2005.06444, 2020.
  * [21] R. R. Redziejowski, “Left recursion by recursive ascent,” in Proceedings of the 29th International Workshop on Concurrency, Specification and Programming (CS&P 2021), pp. 27–29, 2021.
  * [22] A. Afroozeh and A. Izmaylova, “Faster, practical gll parsing,” in International Conference on Compiler Construction, pp. 89–108, Springer, 2015\.
  * [23] T. Parr, S. Harwell, and K. Fisher, “Adaptive ll(*) parsing: The power of dynamic analysis,” in Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’14, (New York, NY, USA), pp. 579–598, Association for Computing Machinery, 2014.


# After the Breach: Incident Response within Enterprises

Sumanth Rao  0000-0002-0075-457X UC San DiegoLa JollaCAUSA<EMAIL_ADDRESS>
###### Abstract.

Enterprises are constantly under attack from sophisticated adversaries. These
adversaries use a variety of techniques to first gain access to the
enterprise, then spread laterally inside its networks, establish persistence,
and finally exfiltrate sensitive data, or hold it for ransom. While
historically, enterprises have used different Incident Response systems that
monitor hosts, servers, or network devices to detect and report threats, these
systems often need many analysts to triage and respond to alerts. However, the
immense quantity of alerts to sift through, combined with the potential risk
of missing a valid threat makes the task of the analyst challenging. To ease
this manual and laborious process, researchers have proposed a variety of
systems that perform automated attack investigation. These systems collect
data, track causally related events, and present the analyst with an
interpretable summary of the attack. In this paper, we present a survey of
systems that perform automated attack investigation, and compare them based on
their designs, goals, and heuristics. We discuss the challenges faced by these
systems, and present a comparison in terms of their ability to address these
challenges. We conclude with a discussion of open problems in this space.

††copyright: none††copyright: none††conference: ; ††booktitle: ;

##  1\. Introduction

Attacks that target enterprises are often multi-stage, and involve a variety
of creative techniques at each step. Indeed, so are some of the famous hacks
in recent years that target software, systems, or accounts. For example, the
2020 SolarWinds hack involved compromising the SolarWinds Orion software,
which was used by thousands of organizations. The 2022 Cash App breach
involved a former employee accessing financial reports containing user
information. The 2023 CitrixBleed hack exploited a vulnerability in Citrix’s
NetScalar product, and used it to gather sensitive information from several
enterprises deployments of the product. While the occurrence of such attacks
is nothing new, the scale and sophistication of such attacks has exploded in
recent years. 111HHS reports the largest data breaches affected 60% more
individuals in 2023 than in 2022 (U.S. Department of Health & Human Services,
2023).

Once inside, attackers use a variety of techniques to move laterally through
the network (e.g., pass-the-hash, Kerberoasting, etc), compromise accounts
with high privileges and access to sensitive systems or data, and use those
privileges to ferry data outside the network. Throughout this process,
attackers play a carefully crafted cat-and-mouse game against threat detection
systems, trying to masquerade as legitimate users within the network (e.g., by
using legitimate tools, or probing access to systems infrequently). Indeed,
this process can often be long, and as a result, attackers can persist inside
the network for weeks, if not months before being detected.222IBM reports the
average time to detect and contain a data breach in 2023 being 204 days (IBM,
2023) For example, the 2020 SolarWinds hack persisted in the network for 14
months before being detected. The 2023 HHS ransomware attack persisted in the
network for 9 months before being detected. The 2023 23andMe breach took place
over a duration of 5 months before being detected.

Enterprises too employ various systems to detect and respond to such attacks –
those that monitor endpoint or host activities (e.g., Endpoint Detection and
Response systems), those that monitor network traffic (e.g., Intrusion and
Detection Systems, or Intrusion Prevension Systems), monitor user activity
(e.g., User and Entity Behavior Analytics), aggregate and monitor system
information such as logs (e.g., Security Information and Event Management).
These systems are often deployed on endpoint devices (e.g., servers, laptops),
inside network infrastructures (e.g., routers, switches), or in centralized
hardware (e.g., Active Directory server), and are passively monitoring for
threats. While a combination of these systems is deployed in modern
enterprises today, a team of analysis are tasked to triage and respond to
threats these systems generate. It is this step that is labor intensive and
time consuming, and often has the highest risk of missing a true positive
(commonly termed the needle-in-the-haystack problem). As a result, several
systems have been proposed to aid the investigative process by tracking
related events, piecing together a causal reasoning of those events that led
to the attack (termed ”causal analysis”), and understanding the scope of the
attack, all in an effort to minimize false positives, and accelerate the
triage process.

Unfortunately, the scale and complexity of an enterprise poses several
challenges in building such systems. First, the sheer volume of data that
needs to be analyzed is large. Second, the data is often noisy, and is heavily
skewed towards benign activities. Third, the data is often spread across
multiple systems, and piecing together a causal graph is challenging. As a
result these systems employ numerous heuristics and models to prevent false
positives, and make the investigative process tractable. For example, systems
often prune irrelevant dependencies, and only track those that are relevant to
the attack, or prioritize alerts based on the severity of the attack, and the
likelihood of the alert being a true positive. Systems also use a variety of
techniques to reduce the number of alerts that need to be investigated,
including using graph topological properties, or rareness scores to prioritize
alerts.

The drawback however is that automated investigation systems assume an ideal
world – one where the system has access to all the data, every event is
logged, and often ignore the practical challenges in analyzing such threats
(e.g., the time cycles an analyst spends on a threat, missing or restricted
access to data). In this paper, we survey the state-of-the-art in enterprise
threat response systems. We first describe the challenges in building such a
detection or investigation system. We then describe the different types of
systems proposed by prior work, the heuristics or models they use, and end
with a discussion of open problems in this space.

##  2\. Background

In this section, we start by discussing Endpoint Detection and Response (EDR)
tools, a suite of tools widely deployed within todays enterprises, and their
use in hunting for threats. We then discuss the origins of automated attack
investigation, followed by a birds-eye view of a typical attack kill chain.
Lastly, we present a classification of systems that perform automated attack
investigation.

###  2.1. Classic EDR and SIEM Systems

EDR systems or tools are pieces of software installed on endpoints (such as
laptop, computers, mobile devices) within an enterprise, to continuously
monitor low-level system activities (such as processes, network, files, etc).
These work by rule-matching events to a known database of curated rules (such
as MITRE ATT&CK (MITRE, 2024)) and flag threats that positively match. For
matched events, the EDR tool can query additional context from the endpoint,
and optionally stream the data to a centralized server for further analysis.
Systems like IBM QRadar (IBM, 2024), Splunk (Splunk, 2024), and ElasticSearch
(Elastic, 2024) are examples of centralized servers that collect and analyze
data from EDR systems. These are often termed as Security Information and
Event Management (SIEM) systems, and offer an interface for threat analysts to
query, merge related events, and analyze the veracity of these warnings.

However, while these systems can provide good coverage in tracking low-level
system events, the burden often lies on the analyst to leverage their skill,
and expertise to piece together the context of an attack. Indeed, SIEM rules
aid by automatically detecting signatures or rules from collected events.
Unfortunately, these rules aren’t bullet-proof and can often be evaded by
subtly modifying the attack to avoid detection via rule-matching 333Indeed
Uetz et al. (Uetz et al., 2023) showed in their recent USENIX ’23 paper that
nearly half of the current SIEM rules could be easily evaded by adversaries by
using simple evasion tactics..

The industry’s adoption of EDR systems has been sudden and quick, with nearly
56% of organizations in 2021 having begun to deploy these within their
enterprise, according to a survey (Business, 2024). As a result, enterprises
today have contractual obligations with their EDR vendor (e.g., Qualys,
FireEye), to deploy EDR tools in a low-cost, scalable manner within their
enterprise, plugged in and ready to capture threats444Often motivated by
indirect reasons, e.g., lowering the premiums on your cyber insurance policy..
This further compounds the fact that there is ultimately a “human-in-the-loop”
to make sense of the various alert, and indeed. However, nearly 70% of
organizations have reported that they struggle to keep up with the volume of
alerts these EDR systems generate (Kaspersky, 2022). In parallel, a myriad of
automated attack investigation systems have been proposed in recent literature
to aid the process of threat investigation.

Figure 1. Reconstruction of an APT style attack kill chain based on a real-
world incident at Cloudflare detected on November 2023. The sequential
numbering represent the timeline of the attack as reported by Cloudflare’s
internal investigation (Prince et al., 2024).

###  2.2. Origins of Automated Investigation

Perhaps the earliest work that performs automated attack investigation is
BackTracker (King and Chen, 2003). BackTracker uses system-call logs at the
hypervisor level to piece together a graph that is used for investigating. The
idea of using logs (as an auditing mechanisms) for attack investigation stems
from ReVirt (Dunlap et al., 2002). ReVirt replays system events in a Virtual
Machine to analyze intrusions. Similarly, systems like Taser (Goel et al.,
2005), and Back-to-the-Future (Hsu et al., 2006) use logging to achieve
similar goals of recovering system state. Taser uses kernel-based logging to
do so, while Back-to-the-Future presents a framework for automatically rolling
back system state to a previous, safe checkpoint, and only replaying the
”clean” events.

The idea of using causality graph to aid in investigation originates from King
et al. (King et al., 2005), who use a combination of network IDS (Snort) and
host IDS to verify the veracity of the alerts. Sitaraman et al. (Sitaraman and
Venkatesan, 2005) also propose augmenting existing IDS by logging additional
parameters which is then used during analysis. Similarly, the use of
investigative tools for analyzing malware has also led to several proposed
systems (Yin et al., 2007; Vasudevan and Yerraballi, 2006). Panorama (Yin et
al., 2007) analyzes taint graphs (at a hardware-level) to identify suspicious
information access and processing behavior of foreign code. Cobra (Vasudevan
and Yerraballi, 2006) presents a dynamic code analysis tool that tracks fine-
grained information flow to identify malicious code.

###  2.3. Modern Investigation Systems

System | Attack Focus | Data | Host | Detection | Provenance
---|---|---|---|---|---
|  | Source | Coverage | Type | Type
Hopper (Ho et al., 2021) | Lateral Movement | Log-in | Multi | Offline | -
Latte (Liu et al., 2018a) | Lateral Movement | Kerberos requests | Multi | Offline | -
SAL (Siadati and Memon, 2017) | Lateral Movement | Log-in | Multi | Offline | -
PrioTracker (Liu et al., 2018b) | APT | Provenance | Multi | Offline | Coarse
RapSheet (Hassan et al., 2020a) | APT | Provenance | Multi | Online | Coarse
NoDoze (Hassan et al., 2019) | APT | Provenance | Multi | Offline | Coarse
ProvDetector (Wang et al., 2020) | Stealthy Malware | Provenance | Multi | Online | Coarse
AirTag (Ding et al., 2023) | APT | Provenance | Multi | Offline | Coarse
Morse (Hossain et al., 2020) | APT | Provenance | Multi | Offline | Coarse
SEAL (Fei et al., 2021) | Causality Analysis | Provenance | Multi | Offline | Coarse
NodLink (Li et al., 2023) | APT | Provenance | Multi | Online | Coarse
Table 1. Classifying 10 systems based on their capability, data source, hosts
covered, system type, and detection type (APT – Advanced Persistent Threat).

Systems that perform automated attack investigation vary on several parameters
– data source, investigation type, system type, etc. Perhaps the broadest
classification we can make is based on the detection system itself, i.e., if
it is online or offline system. Online systems are those that detect attacks
in a real-time (e..g, NodLink (Li et al., 2023)), while offline systems work
by analyzing already collected logs or events (e.g., Airtag (Ding et al.,
2023), ProvDetector (Wang et al., 2020), OmegaLog (Hassan et al., 2020b)).
Based on the data source used for investigation, systems can be classified as
provenance-based (e.g., Morse (Hossain et al., 2020), NoDoze (Hassan et al.,
2019), PrioTracker (Liu et al., 2018b)), or other data sources (e.g., Hopper
(Ho et al., 2021), Latte (Liu et al., 2018a)). Fine-grained systems exploit
provenance by tracking OS-level events, while coarse-grained systems track
specific components such as Active Directory log-on events.

Systems can also be classified as single-host and multi-host based on if their
investigation capacity. Single host systems (e.g., ProvDetector (Wang et al.,
2020)) and multi-host systems (e.g., RapSheet (Hassan et al., 2020a)). While
single host systems track events within a single host, they fail to catch
lateral movement, APT style attacks that traverse across multiple systems and
networks. Lastly, provenance systems can further be classified as those that
track fine-grained provenance and coarse-grained provenance. The former maps
each output byte to its input byte, incurring high overheads in the process
(Xu et al., 2006; Newsome and Song, 2005), while the latter tracks information
flow at a coarser level (Hossain et al., 2020; Hossain et al., 2017). Table 1
presents a classification of 10 systems we study in this paper based on the
above taxonomy.

###  2.4. Birds-Eye View of an Attack Kill Chain

To constrast these tools and the nature of their design, we present a modern
APT style attack kill chain. Figure 1 presents a birds-eye view of an attack
kill chain based on a real incident report at Cloudflare (Prince et al.,
2024). The kill chain starts with the attacker gaining access to three systems
using unrotated credentials from the okta credential breach (Zaman et al.,
2023). The attackers first authenticates with the Gateway using an access
token they (step 1), and proceeds to access the Atlassian Server using a
service account credential(associated with SmartSheet SaaS application). The
attacker then proceeds to do reconnaissance for a period of time by accessing
Atlassian tools like Jira, and Confluence, and viewing support tickets and
product documentation (step 2). The attacker then creates a new user and adds
them to privileged groups, as a measure to ensure their persistence in the
event the SmartSheet credential gets revoked (step 3). Further, to establish
persistence, a Command-and-Control (C2) backdoor software (Sliver Adversary
Emulation Framework) is installed and used to exfiltrate data. Lastly, the
attackers accessed BitBucket Code repositories (again using compromised
credentials), and download several repositories of data. This attack was
detected by the Cloudflare team (nearly a month from initial compromise, by an
alert) and the user accounts were deactivated, and the C2 backdoor was
removed. The attackers also failed to laterally move but access a non-
production console server in a different data center (based on a non-enforced
ACL) but no evidence of further access was found.

##  3\. Challenges

The classic systems used in enterprises suffer from a rates of high alert
reporting/alarms (and high false positives). Analysts are overwhelmed by the
number of alerts, and is unable to respond to all of them – a condition termed
“Alert Fatigue”. Compounding this problem is the fact that debugging each
alert is a time-consuming, manual process of reverse-engineering the context,
querying SIEM tools for more context, pulling logs from different endpoints
EDR tools if needed, and so on. Missing a true positive when assessing the
veracity of these alerts has a high cost. Alas, attacks in the wild such as
the 2013 Target data breach (Committee on Commerce, Science, and
Transportation, 2014) can be attributed to this very reason.

Hence, a fundamental challenge of automated attack systems is to reduce the
number of false positives, while maintaining accurate detection rate. However,
in doing so, a collection of new problems emerge. Dependencies explode as more
dependencies are tracked to verify truthfulness around each alert. Storage
size for logs and events increase exponentially, as more volume and variety of
events are logged.555Fei et al. (Fei et al., 2021) report that a typical
enterprise produces 50GB amount of logs daily, from a group of 100 hosts.
Performance of the systems is time-critical and should not be a bottleneck in
the detection process.

Even when constructed, such systems have a challenging problem evaluating
their accuracy or performance. The problem lies in the fact that these systems
rely on benign or normative data to train, and obtaining real-world benign
enterprise data is challenging. Such data is often proprietary and reveals
sensitive information about the structure and operations of the enterprise.
Even when such data is available, the imbalance in real threats versus benign
data makes it difficult to evaluate the performance of these systems (one
event in a million may be malicious). Systems have resorted to using synthetic
data, or simulating attacks to evaluate their performance, which may not be
representative of real-world attacks.

Despite these challenges, the reality is that a “human-in-the-loop” approach
is still the norm in many enterprises. The analyst has a limited time-budget
(e.g., 15 minutes per alert) to investigate and respond to each alert.
Therefore, systems should to be able to prioritize “more important” alerts,
and provide the analyst with interpretable information to make a timely
decision.

##  4\. Attack Investigation Approach

The first step in attack investigating involves causality analysis, that is,
inferring the root cause of the attack and its scope by linking dependent
events. This is done typically by building a causal graph modeling events or
logs that are collected within the enterprise. The causal graph can be
constructed using different types of data (e.g., Hopper (Ho et al., 2021) and
Structurally Anomalous Logins (SAL) (Siadati and Memon, 2017) detector use
login information from system logs, Latte (Liu et al., 2018a) uses Kerberos
Service Ticket Requests, Morse (Hossain et al., 2020), NoDoze (Hassan et al.,
2019) and other provenance-tracking systems exploit low-level OS related
events like files and processes). The second step in attack investigation is
prioritize anomalous events or paths (e.g., PrioTracker (Liu et al., 2018b)
uses graph topological properties and rareness score to prioritize anomalous
paths, NodLink (Li et al., 2023) also uses topological features modeled as a
tree). Simultaneous, systems tend to deprioritize paths based on other
heuristics (e.g., PrioTracker (Liu et al., 2018b) deprioritizes paths without
high fanout).

Figure 2. General architecture of systems that perform automated attack
investigation.

###  4.1. Causality Graph Construction

In order to establish the veracity of a warning, the system performs causality
analysis to determine the root cause (aka root cause analysis). When building
a causal graph, the system exploits data provenance, logs, or other data
sources it is tracking. Below we discuss three different systems that exploit
different data sources to build a causal graph – Hopper, Latte, and
PrioTracker. Hopper (Ho et al., 2021) uses login information from system logs
to build a login graph. Each edge forms a login event from a source machine to
a destination machine, timestamped at the time of the login. Hopper then
infers a causal user, a user who originally logged in, resulting in this edge,
along with the a set of rareness rules to decide if the event is an example of
lateral movement. Latte (Liu et al., 2018a) instead uses Kerberos Service
Ticket Request events (filtered based on a specific windows event alert code)
to model a graph of computer-to-computer user logins. Similar to Hopper, each
edge is directed from a source node to a destination node, timestamped at when
the connection was made. Latte then uses a set of heuristics to determine if
the event is an example of lateral movement. PrioTracker (Liu et al., 2018b)
like other provenance systems, builds a dependency graph of OS-level system
events. Each node in the graph represents a system object (e.g., process,
network socket, or file), and the edges represent the flow of data (e.g.,
process creation, file read, etc.). Again, multiple edges are temporally
ordered. PrioTracker then uses a set of heuristics to associate priority with
every causal event that it uses during investigation.

###  4.2. Root Cause and Scope Analysis

Once the causal graph has been constructed, the system determines the root
cause and the scope, using forward and backward tracing respectively. The root
cause is inferred using backward tracking, starting from a known malicious
event and tracing incident edges to determine the source. The scope, in
contrast, is determined using forward tracking, starting from the known
malicious event, and tracing forward by following incident edges. During both
these cases, the system causally tracks an immense number of paths that
explode exponentially based on linked dependencies. In section 5 we’ll discuss
how systems mitigate this dependency explosion during their analysis. For now,
we discuss four systems from prior literature, RapSheet, NoDoze, PrioTracker,
and Hopper that perform root cause and scope analysis.

RapSheet (Hassan et al., 2020a) uses Symantec’s EDR system to build a Tactical
Provenance Graph by tracking Initial Infection Points (IIP) vertices from the
provenance graph. By defining a set of rules that involves backtracking from a
known malicious event, RapSheet determines the IIP vertices, and then issues
forward traces from these points to generate IIP graphs that it uses to model
the scope of the attack. NoDoze (Hassan et al., 2019) directly uses progeny
and ancestry of the infected node to determine if the alert is true attack or
a false alarm, using backward and forward propagation. PrioTracker (Liu et
al., 2018b) introduces the notion of priority when performing forward and
backward tracking. The system uses a set of heuristics to score each path with
a priority score, and picks the path with the highest priority score during
forward and backward propagation. Hopper (Ho et al., 2021) produces a sequence
of causally-related logins using backward-tracing. This is based on a
heuristic that two edges are correlated if they are incident on the same
vertex, and are within a threshold time window. Hopper then uses a set of
rules to determine if the path is an example of lateral movement.

###  4.3. Anomaly Detection

During root cause and scope analysis, systems employ various heuristics to
detect anomalous paths. These heuristics can be based on topological graph
features, machine learning models, or other relationships, and are used to
score paths based on their likelihood of being malicious.

####  4.3.1. Topological Graph Heuristics

For those systems that use topological graph features, the scoring is based on
event granularity, the whole path, or parts of the whole graph. We discuss
each of these three types using PrioTracker, NoDoze, Hopper, and RapSheet as
examples.

PrioTracker (Liu et al., 2018b) assigns a priority score (a measure of
suspiciousness) to each event representing an edge in the causal graph, using
a combination of rareness and fanout score. While fanout can be calculated
using the number of incident edges at a node, rareness is a function of
deviation from normal behavior. PrioTracker thus uses a reference model of
system events (collected from 150 hosts within an enterprise) to define
“normal behavior”, and measures rareness as a deviation.

NoDoze (Hassan et al., 2019) in contrast assigns an anomaly score to the
entire path by associating the contexts in which each event occurs. This helps
NoDoze distinguishing between legitimate use of a software (e.g., cclearner
for cleaning disk) and its malicious use (ccleaner used by ransomware for
destroying evidence). To do so, NoDoze uses a network diffusion algorithm to
combine scores from events along a path. NoDoze generates a regularity score
to each dependency path, which is a combination of fanout (using IN and OUT
scores), and rareness (using historical window). NoDoze then normalizes the
anomaly score using a decay factor that prevents the anomaly scores of longer
paths from being skewed.

Hopper (Ho et al., 2021) also uses a path-based scoring heuristic modeled on
credential switches – if a path involves a credential switch to access a
resource that the user has not accessed recently (30 days), then it is
considered malicious. If the credential switch in the path is less clear,
Hopper uses a probability scoring model to score events along a path based on
their historical context.

RapSheet (Hassan et al., 2020a) relies on constructing a subgraph (a Tactical
Provenance Graph (TPG)) by identifying the initial points of compromise in a
causal graph. Such graph-based systems capture scenarios where an attacker
spawns multiple processes after compromise, while a path-based system treats
each of those causally related paths different. RapSheet relies on MITRE’s
ATT&CK framework 666A curated set of expertly-written rules based on analysis
of real-world APT attacks (MITRE, 2024). to categorically match and score the
graph, maximizing the threat score of the TPG. For each MITRE techniques that
is matched, RapSheet uses a categorical score for severity and likelihood
(e.g., 1 for very low, 5 for very high, etc.) which it weights and combines to
produce a final score for the TPG. Intuitively, the TPG graph is a combination
of the sequences of possible kill-chain of the APT attack, temporally ordered,
and scored using the ATT&CK framework.

####  4.3.2. Machine Learning Models

A subset of ML models use Natural Language processing (NLP) methods to
directly process logs, a task well suited for unstructured text (Ding et al.,
2023; Wang et al., 2020). Other systems use ML techniques to capture
information from provenance graphs and learn benign vs malicious behaviors
automatically. We discuss ProvDetector, Airtag, and NodLink as examples.

ProvDetector (Wang et al., 2020) tracks events at the OS-level tracker to
build a per-process provenance graph aimed at detecting stealthy malware. It
then finds the K-rare paths in the graph (using an idea based on regularity
scoring similar to NoDoze (Hassan et al., 2019)) and uses doc2vec to learn the
embeddings of these paths. This method has an advantage that it is self-
supervised, since the model can learn based on purely benign data. Lastly, it
uses a classification based on threshold of embedded vectors detected as
anomalous, to determine if the process is malicious.

AirTag’s (Ding et al., 2023) main intuition is that logs and causal graphs are
different representations of the same problem, however logs are in Euclidean
space, and easier for ML models to learn. Thus, AirTag works by directly
training on benign logs (preprocessed and embedded with a customized BERT
language model (Devlin et al., 2018)) and learns a decision boundary using
one-class Support Vector Machine (OC-SVM (sklearn, 2024)). It then uses the
same embedding during testing to detect anomalous log entries that lie outside
the decision boundary. However, AirTag reconstructs the detected attack causal
graph from the anomalous log entries to present the result to the analyst.

NodLink (Li et al., 2023) constructs a Steinier Tree from the provenance data
by searching for a tree that minimizes the number of edges. The tree spans
anomalous events and IOCs with minimum edges, and has a theoretical guarantee
of finding such a subgraph in polynomial time. However, to identify suspicious
processes in an online manner, NodLink uses a document embedding technique to
embed processes, and uses a Variational Auto Encoder (VAE) to generate an
anomaly score. The anomaly score is then used to determine if the process is
malicious.

##  5\. Solutions

Each system discussed so far (Section 3) addresses the challenges of classic
EDR systems (e.g., alert fatigue, storage limitations, etc.) in their
individual, creative ways. The common themes involve mitigating dependency
explosion, prioritizing alerts, mitigating storage requirements, and improving
interpretability. Table 2 scores each of the systems based on these
capabilities. In this section, we discuss a subset of systems when discussing
each capability in detail.

System | Mitigating Dependency | Prioritizing Alerts | Interpretable | Mitigating Storage |
---|---|---|---|---|---
| Explosion |  | Results |  |
Hopper (Ho et al., 2021) | Deduplicate paths, | Time-budget | ✗ | ✗ |
| optimized backtracing |  |  |  |
Latte (Liu et al., 2018a) | ✗ | Path ranking | ✗ | Graph pruning |
SAL (Siadati and Memon, 2017) | ✗ | ✗ | ✗ | ✗ |
PrioTracker (Liu et al., 2018b) | Prioritize dependencies | Anomaly scoring | ✗ | ✗ |
RapSheet (Hassan et al., 2020a) | Concise graph | ✗ | Concise graphs | Graph pruning |
NoDoze (Hassan et al., 2019) | Execution partitioning | Anomaly scoring | ✗ | ✗ |
ProvDetector (Wang et al., 2020) | Path sampling | ✗ | ✗ | ✗ |
AirTag (Ding et al., 2023) | - | ✗ | Concise graphs | ✗ |
Morse (Hossain et al., 2020) | Tag propagation | ✗ | ✗ | ✗ |
SEAL (Fei et al., 2021) | ✗ | - | ✗ | Graph compression |
NodLink (Li et al., 2023) | Threshold cutoff | Anomaly scoring | ✗ | In-memory cache |
Table 2. Scoring 11 systems based on their capability to solve challenges of
classic EDR tools. ✗indicates the system does not have that capability, and -
indicates the capability is not applicable.

###  5.1. Mitigating Dependency Explosion

With an increase in provenance tracking, systems gather an abundant amount of
fine grained data spanning multiple hosts, and causally links these events
with their predecessors in time. For long running processes that involve large
data flows, the number of dependencies can grow exponentially (e.g., a long
running browser process). Systems therefore have used ingenious ways to
mitigate this dependency explosion. We discuss traditional systems (e.g.,
ProTracer) and recent systems (e.g., Morse, NoDoze) that address this
challenge.

The traditional approach to handle dependency explosion has been to partition
long running processes into individual units to which dependencies are
confined (e.g., an output can only be dependent on an input in the same
unit/partition). Indeed, systems like ProTracer (Ma et al., 2016), BEEP (Lee
et al., 2013), MCI (Kwon et al., 2018), and MPI (Ma et al., 2017) use this
approach to provide a more granular view of the system. Unfortunately though,
these systems require user interactions, kernel modifications, or are limited
to specific operating systems (e.g., Linux).

Morse (Hossain et al., 2020) associates tags to subjects and objects within
the system that it attenuates and decays as data propagates through the
system. Specifically Morse assigns two types of tags – subject tags that it
uses to determine if the process or the environment is benign or suspicious,
and data tags that captures the confidentiality and integrity of values. It
then uses tag propagation rules to determine the value of the tags as they
propagate through the system. For example, tags for benign subjects are
attenuated, and decayed periodically with a quiescent factor. This way, the
system can prune irrelevant system dependencies, and focus on the relevant
ones.

NoDoze (Hassan et al., 2019) specifically handles long running processes by
using a partitioning technique (termed behavioral execution partitioning) that
separates the normal and anomalous behavior of long running processes. NoDoze
does this by generating a True Alert Dependency Graph that includes only
relevant, true dependencies of particular length ($\tau_{l}$), with a anomaly
score higher than a threshold ($\tau_{d}$). To generate the anomaly score,
NoDoze uses topological features such as regularity score, and fanout (see
Section 4.3), and merges anomalous paths to reduce the number of alerts
generated.

ProvDetector (Wang et al., 2020) uses a path sampling technique to mitigate
dependency explosion. From each per-process dependency graph, ProvDetector
samples a set of paths that are representative of the graph. It then uses
these sampled paths to generate embedding and classify the process as benign
or malicious.

###  5.2. Prioritizing Alerts

While mitigating dependency explosion when backtracking an attack is
important, it need not reduce the number of alerts generated, and hence may
not reduce the time budget for an analyst. We discuss three systems that
associate priority and rank alerts based on their importance – Hopper, and
PrioTracker.

Priotracker (Liu et al., 2018b) uses a priority assignment algorithm that is a
combination of rareness and fanout scores to assign priority to alerts
(Section 4.3.1). Both the rareness and fanout scores are weighted in a
combined priority assignment using weights learnt from events within an
enterprise. In practice, PrioTracker uses a threshold for rareness to assign
alarms to categories of alerts (e.g., Critical events, Rare critical events).

Hopper (Ho et al., 2021) makes a distinction with login paths with clear
credential switch (which is earlier to analyze) and unclear credential switch
(based on a probabilistically heuristic). Hopper uses a user-inputted time
budget when generating alerts for paths with unclear credential switches. This
way, Hopper can prioritize alerts based on the time budget of the analyst. For
each unclear path P, Hopper extracts three features (based on path
characteristics) and computes an anomaly score. Then, the anomaly score is
ranked relative to a historical paths and if within a window of 30 $\times$
alert-budget, Hopper generates an alert for the path.

###  5.3. Mitigating Storage

System logs within an enterprise can grow exponentially over time as more
dependencies get tracked. Throwing out old logs with sensitive information can
hinder the ability to backtrack an attack and decipher its root cause. Indeed,
to detect long running APT attack campaigns, the ability to retain old logs
becomes crucial. To avoid this, the general approach taken relies on pruning
graph sizes and hence compressing the associated log storage to save storage
space (Fei et al., 2021; Hassan et al., 2020a). We discuss RapSheet, and SEAL
as examples.

RapSheet (Hassan et al., 2020a) uses a graph-based pruning approach to compact
storage by applying two graph reduction rules. First, RapSheet removes object
nodes if they have no alert dependencies in the backward chain of the TPG, and
no alert edges incident. Second, RapSheet removes process nodes that have no
alert events in the backward chain of the TPG, and if the process has already
been terminated. Applying these two rules, RapSheet periodically runs the
graph reduction algorithm to generate a space-efficient TPG that can be stored
for long periods of time.

Unlike prior work that does lossy compression (e.g., (Hossain et al., 2018;
Tang et al., 2018)), SEAL (Fei et al., 2021) uses a lossless compression
technique that ensures it can be queried without much decompression overhead
by an analyst. To do this, SEAL ensures decompression-free compression on
graph structure by merging edges with similar patterns, and query-able
compression on edge properties by using different coding (delta, golomb) to
compress edge properties (like timestamps). Further, SEAL selectively
decompresses only necessary parts of the graph by comparing timestamps of the
compressed edge and that of the query.

###  5.4. Interpretable Results

While both mitigating dependency explosion and prioritizing alert help the
automated triaging of alerts, ultimately, the issue is flagged to a human
analyst for further analyst. Thus, making the result interpretable and
providing sufficient context to validate the threat is crucial. We discuss how
AirTag, and Dong et al. (Dong et al., 2023) address this challenge.

Having prioritized logs with anomalous behaviors, AirTag (Ding et al., 2023)
generates anomalous causal graphs for the analyst to investigate. AirTag uses
a greedy algorithm by generating disjoin graphs for every logs flagged by the
classifier (OC-SVM) and merging them by finding the first common node between
disjoin graphs. AirTag only tries to find the first common node between
disjoin paths, and is able to recover the attack story (based on its
evaluations) by repeating this approach.

Dong et al. (Dong et al., 2023) conduct a survey on industrial viewpoint of
different provenance system, Indeed, most industry managers view
interpretability as a crucial feature which adds more context and aids in
investigation, and that basic provenance systems that consists of low-level
audit events from logs are understandable for skilled analysts, as long as
they are concise. However, when reimplementing different provenance system
from prior work, Dong et al. found that atleast one system (Unicorn (Han et
al., 2020)) has a low alert frequency (alarms/host/day), but reports the whole
provenance graph as an attack alarm, without pinpointing the location within.
Such tradeoffs in interpretability can hinder the ability of an analyst to
validate the threat. We defer a more detailed discussion of this to Section 6.

##  6\. Open Problems

System | Benign Data Source | Attack Data Source
---|---|---
Hopper (Ho et al., 2021) | Enterprise data (Dropbox) | Red-team testing,
|  | Simulated attacks
Latte (Liu et al., 2018a) | Enterprise data (Microsoft and | Red-team testing,
| unnamed organization) | Real-world attack
SAL (Siadati and Memon, 2017) | Enterprise data (Unnamed financial company) | Simulated attacks
PrioTracker (Liu et al., 2018b) | Enterprise data (Unnamed IT organization) | Simulated attacks
RapSheet (Hassan et al., 2020a) | Enterprise data (Symantec) | Red-team testing,
|  | Simulated attacks
NoDoze (Hassan et al., 2019) | Enterprise data (NEC Labs America) | Simulated attacks
ProvDetector (Wang et al., 2020) | Enterprise data (Unnamed organization) | Simulated attacks
AirTag (Ding et al., 2023) | Public datasets (ATLAS, DEPIMPACT), | Simulated attacks,
|  | Public datasets (ATLAS, DEPIMPACT)
Morse (Hossain et al., 2020) | Public datasets (DARPA TC) | Public datasets (DARPA TC)
SEAL (Fei et al., 2021) | Enterprise data (Unnamed enterprise), | Simulated attacks,
| Public datasets (DARPA TC) | Public datasets (DARPA TC)
NodLink (Li et al., 2023) | Public datasets (DARPA TC datasets), | Public datasets (DARPA TC datasets),
| Enterprise data (Sangford) | Red-team testing,
|  | Real-world deployment (Sangford)
Table 3. Evaluation datasets used by 11 systems in prior literature.

Section 5 discusses creative way of addressing new challenges in attack
investigation, namely mitigating dependency explosion, managing storage,
prioritizing alerts, and presenting interpretable results. However, new
challenges arise as a result of these solutions. We discuss these challenges
in this section, and propose a set of open problems that future work should
consider.

###  6.1. Push towards Real-time Analysis

8/11 systems we study (Table 1) are designed for offline analysis. The
motivation is that offline analysis allows more comprehensive analysis, and
does not need to be resource constrained as online analysis. However, offline
analysis has its own limitations. For instance, Verizon Data Breach Report
(Verizon, 2023) found that it takes a matter of seconds to compromise a
system, and then several minutes to hours for exfiltration. This means that
offline analysis may not best geared to detect breaches in real-time. Indeed,
systems like ProvDetector (Wang et al., 2020) and NodLink (Li et al., 2023)
propose an online detection algorithm, and we believe that this is a promising
direction for future work.

We also believe that the bottleneck for online systems does not lie in the
storage. Indeed, a number of creative systems have proposed compressing the
provenance graph (lossless and lossy) (Hossain et al., 2018; Tang et al.,
2018; Fei et al., 2021), pruning the size of the graph . Instead, we believe a
combination of storage factored with performance is more important. For
instance, NodLink (Li et al., 2023) prunes the dependencies with a threshold,
and then uses a combination of in-memory cache and disk storage to improve the
performance. Other systems should also consider this tradeoff as a motivation
for future work.

###  6.2. Failure Reducing Analyst Workload

Unfortunately, the real motivation behind automated analysis is to reduce the
workload of the analyst. This is where a bulk of the systems we studied fall
short. Indeed, 5/11 (Table 2) systems prioritize alerts the system generates,
and nearly all the systems we studied attempt to improve the quality of these
alerts (e.g., by exploiting context around the event). However, only 1/11
systems consider the time cycles of the analyst as a parameter. Further, only
1/11 systems considers how interpretable the result is to the analyst. This is
a significant limitation, and we believe that future work should consider the
workload of the analyst as a parameter.

Dong et al. (Dong et al., 2023) also mentions that none of the systems in
their evaluation accounted for the number of alerts/host/day raised, in an
attempt to minimize it. Further, when reimplementing three systems from prior
literature and evaluating their accuracy, they found only 1/3 systems (Unicorn
(Han et al., 2020)) with a low enough rate of alerts/host/day to be practical
for real-world use. Ironically though, the same system had poor
interpretability since it would flag the entire provenance graph as malicious
to the analyst.

###  6.3. Unrealistic Assumptions

A number of systems make unrealistic assumptions in their design or
evaluation. For instance, nearly all the systems we studied assume that the
logs are tamper evident. While, this maybe a reasonable assumption, and
systems indeed have been proposed to make logs tamper proof (Bellare and Yee,
1997), we believe systems should incorporate this as a feature in their
design. Further, nearly all the systems we studied assume that the data is
complete – e.g., all the logs are available, all the log-in events are logged,
access to all hosts or endpoints is unfettered. This indeed is a significant
limitation, and in our own experience, we have found this to not be the case.
Some systems are more well monitored that the rest, crucial logs might be
missing, access to logs on some endpoint might be restricted, and so on. We
believe that future work should consider these limitations in their design.

Besides these general observations, we also note a number of minor assumptions
in the design of the systems we studied. For instance, Latte (Liu et al.,
2018a) prunes systems with a high in-degree or out-degree, potentially
allowing an attacker who purely hides in “more popular” systems to go
unnoticed. SAL (Siadati and Memon, 2017) and Hopper (Ho et al., 2021) exploit
the structure of the enterprise to detect attacks, which though is a
reasonable assumption, might not be generalizable to all enterprises (e.g.,
SAL fails to consider if enterprises have no functional units, or if the
functional units are not well defined).

Lastly, only one system we studied (RapSheet (Hassan et al., 2020a)) considers
a less invasive approach by building on top of existing EDR systems, while
others use classic auditing systems like Auditd, or Sysdig. While these
approaches aren’t necessarily bad, we believe that future work should consider
the adaptability of research solution in the real world enterprises, by using
existing EDR systems as a base.

###  6.4. Realistic Evaluations are Tough

Alas the one challenge that remains the most difficult to address involves
finding a high-quality dataset that is representative of real-world attacks.
Table 3 shows the datasets used by the systems we studied for benign and
attack data.

To generate benign data, systems partner with enterprises (e.g., Hopper (Ho et
al., 2021) uses data from Dropbox, and NodLink (Li et al., 2023) uses data
from Sangford), or use public data traces with simulated attacks (e.g., Darpa
TC datasets (DARPA, 2020), ATLAS (Alsaheel et al., 2021), DEPIMPACT (Fang et
al., 2022)). Finding high-quality dataset with real-world attacks on the other
hand is a significantly more challenge – both in terms of privacy, and in
terms of enterprises being willing to share such data publicly. Hence, nearly
all the systems we studied use simulated attacks, or red-team testing, or use
simulated attacks from public datasets.

How realistic these simulations are to real-world attacks or representative of
them is an open question. To the best of our knowledge only one system (Latte
(Liu et al., 2018a)) uses real-world instance of Lateral Movement attack in
their dataset for evaluation.

Finally, even when a system proposed performs well on static traces, or
synthetic data, it is not clear how well it would perform in the real-world.
Again, to the best of our knowledge, only one system (NodLink (Li et al.,
2023)) reimplemented its system in an online setup to capture real-world
threats.

Thus, the quality of evaluation data, and its representativeness are both open
questions that we urge future work to consider.

##  7\. Conclusion

In this paper, we survey 11 state-of-the-art systems for automated attack
investigation in enterprises. We find that these systems are designed to
address challenges in attack investigation, namely dependency explosion,
limited storage, alert fatigue, and do so with their own flavors. However,
there is no universal solution addressing each of these challenges, and
systems therefore strike a balance in prioritizing some features more than the
rest. We scored each of the 11 systems based on their techniques for
overcoming these challenges, and extracted a set of similar approaches. We
further discussed four open challenges in this line of work – namely, the push
towards real-time analysis, focus on reducing analyst workload, minimizing
unrealistic assumptions, incorporating realistic evaluations. We believe that
future work should consider these challenges in their design, and evaluation.

###### Acknowledgements.

Much thanks to Grant Ho, Stefan Savage and Geoffrey M. Voelker for their
insights on this work.

## References

  * (1)
  * Alsaheel et al. (2021) Abdulellah Alsaheel, Yuhong Nan, Shiqing Ma, Le Yu, Gregory Walkup, Z Berkay Celik, Xiangyu Zhang, and Dongyan Xu. 2021.  $\\{$ATLAS$\\}$: A sequence-based learning approach for attack investigation. In 30th USENIX security symposium (USENIX security 21). 3005–3022.
  * Bellare and Yee (1997) Mihir Bellare and Bennet Yee. 1997.  Forward integrity for secure audit logs.  Technical Report. Citeseer.
  * Business (2024) Comcast Business. 2024\.  How Endpoint Detection and Response (EDR) Can Help Reduce Serious Incidents.  (Feb. 2024).  https://business.comcast.com/community/browse-all/details/how-endpoint-detection-and-response-edr-can-help-reduce-serious-incidents
  * Committee on Commerce, Science, and Transportation (2014) Committee on Commerce, Science, and Transportation. 2014.  A “Kill Chain Analysis” of the 2013 Target Data Breach.  (March 2014).  https://www.commerce.senate.gov/services/files/24d3c229-4f2f-405d-b8db-a3a67f183883
  * DARPA (2020) DARPA. 2020.  Transparent Computing Engagement 5 Data Release.  (Oct. 2020).  https://github.com/darpa-i2o/Transparent-Computing
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805 (2018).
  * Ding et al. (2023) Hailun Ding, Juan Zhai, Yuhong Nan, and Shiqing Ma. 2023\.  $\\{$AIRTAG$\\}$: Towards Automated Attack Investigation by Unsupervised Learning with Log Texts. In 32nd USENIX Security Symposium (USENIX Security 23). 373–390.
  * Dong et al. (2023) Feng Dong, Shaofei Li, Peng Jiang, Ding Li, Haoyu Wang, Liangyi Huang, Xusheng Xiao, Jiedong Chen, Xiapu Luo, Yao Guo, et al. 2023\.  Are we there yet? An Industrial Viewpoint on Provenance-based Endpoint Detection and Response Tools. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. 2396–2410.
  * Dunlap et al. (2002) George W Dunlap, Samuel T King, Sukru Cinar, Murtaza A Basrai, and Peter M Chen. 2002.  ReVirt: Enabling intrusion analysis through virtual-machine logging and replay.  ACM SIGOPS Operating Systems Review 36, SI (2002), 211–224.
  * Elastic (2024) Elastic. 2024.  The Elasticsearch Platform.  (Feb. 2024).  https://www.elastic.co/platform
  * Fang et al. (2022) Pengcheng Fang, Peng Gao, Changlin Liu, Erman Ayday, Kangkook Jee, Ting Wang, Yanfang Fanny Ye, Zhuotao Liu, and Xusheng Xiao. 2022.  $\\{$Back-Propagating$\\}$ System Dependency Impact for Attack Investigation. In 31st USENIX Security Symposium (USENIX Security 22). 2461–2478.
  * Fei et al. (2021) Peng Fei, Zhou Li, Zhiying Wang, Xiao Yu, Ding Li, and Kangkook Jee. 2021\.  $\\{$SEAL$\\}$: Storage-efficient causality analysis on enterprise logs with query-friendly compression. In 30th USENIX Security Symposium (USENIX Security 21). 2987–3004.
  * Goel et al. (2005) Ashvin Goel, Kenneth Po, Kamran Farhadi, Zheng Li, and Eyal De Lara. 2005.  The taser intrusion recovery system. In Proceedings of the twentieth ACM symposium on Operating systems principles. 163–176.
  * Han et al. (2020) Xueyuan Han, Thomas Pasquier, Adam Bates, James Mickens, and Margo Seltzer. 2020.  Unicorn: Runtime provenance-based detector for advanced persistent threats.  arXiv preprint arXiv:2001.01525 (2020).
  * Hassan et al. (2020a) Wajih Ul Hassan, Adam Bates, and Daniel Marino. 2020a.  Tactical provenance analysis for endpoint detection and response systems. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 1172–1189.
  * Hassan et al. (2019) Wajih Ul Hassan, Shengjian Guo, Ding Li, Zhengzhang Chen, Kangkook Jee, Zhichun Li, and Adam Bates. 2019.  Nodoze: Combatting threat alert fatigue with automated provenance triage. In network and distributed systems security symposium.
  * Hassan et al. (2020b) Wajih Ul Hassan, Mohammad Ali Noureddine, Pubali Datta, and Adam Bates. 2020b.  Omegalog: High-fidelity attack investigation via transparent multi-layer log analysis. In Network and distributed system security symposium.
  * Ho et al. (2021) Grant Ho, Mayank Dhiman, Devdatta Akhawe, Vern Paxson, Stefan Savage, Geoffrey M Voelker, and David Wagner. 2021.  Hopper: Modeling and detecting lateral movement. In 30th USENIX Security Symposium (USENIX Security 21). 3093–3110.
  * Hossain et al. (2017) Md Nahid Hossain, Sadegh M Milajerdi, Junao Wang, Birhanu Eshete, Rigel Gjomemo, R Sekar, Scott Stoller, and VN Venkatakrishnan. 2017\.  $\\{$SLEUTH$\\}$: Real-time attack scenario reconstruction from $\\{$COTS$\\}$ audit data. In 26th USENIX Security Symposium (USENIX Security 17). 487–504.
  * Hossain et al. (2020) Md Nahid Hossain, Sanaz Sheikhi, and R Sekar. 2020.  Combating dependence explosion in forensic analysis using alternative tag propagation semantics. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 1139–1155.
  * Hossain et al. (2018) Md Nahid Hossain, Junao Wang, Ofir Weisse, R Sekar, Daniel Genkin, Boyuan He, Scott D Stoller, Gan Fang, Frank Piessens, Evan Downing, et al. 2018\.  $\\{$Dependence-Preserving$\\}$ data compaction for scalable forensic analysis. In 27th USENIX Security Symposium (USENIX Security 18). 1723–1740.
  * Hsu et al. (2006) Francis Hsu, Hao Chen, Thomas Ristenpart, Jason Li, and Zhendong Su. 2006.  Back to the future: A framework for automatic malware removal and system repair. In 2006 22nd Annual Computer Security Applications Conference (ACSAC’06). IEEE, 257–268.
  * IBM (2023) IBM. 2023.  Cost of a Data Breach Report 2023.  (Oct. 2023).  https://www.ibm.com/reports/data-breach
  * IBM (2024) IBM. 2024.  IBM Security QRadar SIEM.  (Feb. 2024).  https://www.ibm.com/products/qradar-siem
  * Kaspersky (2022) Kaspersky. 2022\.  SOC Modernization and the Role of XDR.  (July 2022).  https://go.kaspersky.com/xdr_report
  * King and Chen (2003) Samuel T King and Peter M Chen. 2003.  Backtracking intrusions. In Proceedings of the nineteenth ACM symposium on Operating systems principles. 223–236.
  * King et al. (2005) Samuel T King, Zhuoqing Morley Mao, Dominic G Lucchetti, and Peter M Chen. 2005.  Enriching Intrusion Alerts Through Multi-Host Causality.. In Ndss.
  * Kwon et al. (2018) Yonghwi Kwon, Fei Wang, Weihang Wang, Kyu Hyung Lee, Wen-Chuan Lee, Shiqing Ma, Xiangyu Zhang, Dongyan Xu, Somesh Jha, Gabriela Ciocarlie, et al. 2018\.  MCI: Modeling-based causality inference in audit logging for attack investigation. In Network and Distributed Systems Security (NDSS) Symposium.
  * Lee et al. (2013) Kyu Hyung Lee, Xiangyu Zhang, and Dongyan Xu. 2013.  High Accuracy Attack Provenance via Binary-based Execution Partition.. In NDSS, Vol. 16.
  * Li et al. (2023) Shaofei Li, Feng Dong, Xusheng Xiao, Haoyu Wang, Fei Shao, Jiedong Chen, Yao Guo, Xiangqun Chen, and Ding Li. 2023.  NodLink: An Online System for Fine-Grained APT Attack Detection and Investigation.  arXiv preprint arXiv:2311.02331 (2023).
  * Liu et al. (2018a) Qingyun Liu, Jack W Stokes, Rob Mead, Tim Burrell, Ian Hellen, John Lambert, Andrey Marochko, and Weidong Cui. 2018a.  Latte: Large-scale lateral movement detection. In MILCOM 2018-2018 IEEE Military Communications Conference (MILCOM). IEEE, 1–6.
  * Liu et al. (2018b) Yushan Liu, Mu Zhang, Ding Li, Kangkook Jee, Zhichun Li, Zhenyu Wu, Junghwan Rhee, and Prateek Mittal. 2018b.  Towards a Timely Causality Analysis for Enterprise Security.. In NDSS.
  * Ma et al. (2017) Shiqing Ma, Juan Zhai, Fei Wang, Kyu Hyung Lee, Xiangyu Zhang, and Dongyan Xu. 2017\.  $\\{$MPI$\\}$: Multiple perspective attack investigation with semantic aware execution partitioning. In 26th USENIX Security Symposium (USENIX Security 17). 1111–1128.
  * Ma et al. (2016) Shiqing Ma, Xiangyu Zhang, and Dongyan Xu. 2016.  Protracer: Towards practical provenance tracing by alternating between logging and tainting. In 23rd Annual Network And Distributed System Security Symposium (NDSS 2016). Internet Soc.
  * MITRE (2024) MITRE. 2024.  MITRE ATT&CK.  (Feb. 2024).  https://attack.mitre.org/
  * Newsome and Song (2005) James Newsome and Dawn Xiaodong Song. 2005.  Dynamic taint analysis for automatic detection, analysis, and signaturegeneration of exploits on commodity software.. In NDSS, Vol. 5. Citeseer, 3–4.
  * Prince et al. (2024) Matthew Prince, John Graham-Cumming, and Grant Bourzikas. 2024\.  Thanksgiving 2023 security incident.  (Feb. 2024).  https://blog.cloudflare.com/thanksgiving-2023-security-incident
  * Siadati and Memon (2017) Hossein Siadati and Nasir Memon. 2017.  Detecting structurally anomalous logins within enterprise networks. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 1273–1284.
  * Sitaraman and Venkatesan (2005) Sriranjani Sitaraman and S. Venkatesan. 2005.  Forensic Analysis of File System Intrusions Using Improved Backtracking. In Proceedings of the Third IEEE International Workshop on Information Assurance (IWIA ’05). 154––163.
  * sklearn (2024) sklearn. 2024.  sklearn.svm.OneClassSVM.  (Oct. 2024).  https://scikit-learn.org/stable/modules/generated/sklearn.svm.OneClassSVM.html
  * Splunk (2024) Splunk. 2024.  Why Splunk?  (Feb. 2024).  https://www.splunk.com/en_us/about-us/why-splunk.html
  * Tang et al. (2018) Yutao Tang, Ding Li, Zhichun Li, Mu Zhang, Kangkook Jee, Xusheng Xiao, Zhenyu Wu, Junghwan Rhee, Fengyuan Xu, and Qun Li. 2018\.  Nodemerge: Template based efficient data reduction for big-data causality analysis. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 1324–1337.
  * Uetz et al. (2023) Rafael Uetz, Marco Herzog, Louis Hackländer, Simon Schwarz, and Martin Henze. 2023\.  You Cannot Escape Me: Detecting Evasions of SIEM Rules in Enterprise Networks.  arXiv preprint arXiv:2311.10197 (2023).
  * U.S. Department of Health & Human Services (2023) U.S. Department of Health & Human Services. 2023.  HHS’ Office for Civil Rights Settles Ransomware Cyber-Attack Investigation.  (Oct. 2023).  https://www.hhs.gov/about/news/2023/10/31/hhs-office-civil-rights-settles-ransomware-cyber-attack-investigation.html
  * Vasudevan and Yerraballi (2006) Amit Vasudevan and Ramesh Yerraballi. 2006.  Cobra: Fine-grained malware analysis using stealth localized-executions. In 2006 IEEE Symposium on Security and Privacy (S&P’06). IEEE, 15–pp.
  * Verizon (2023) Verizon. 2023.  2023 Data Breach Investigations Report.  (Nov. 2023).  https://www.verizon.com/business/resources/reports/dbir/
  * Wang et al. (2020) Qi Wang, Wajih Ul Hassan, Ding Li, Kangkook Jee, Xiao Yu, Kexuan Zou, Junghwan Rhee, Zhengzhang Chen, Wei Cheng, Carl A Gunter, et al. 2020\.  You Are What You Do: Hunting Stealthy Malware via Data Provenance Analysis.. In NDSS.
  * Xu et al. (2006) Wei Xu, Sandeep Bhatkar, and Ramachandran Sekar. 2006.  Taint-enhanced policy enforcement: a practical approach to defeat a wide range of attacks.. In USENIX Security Symposium. 121–136.
  * Yin et al. (2007) Heng Yin, Dawn Song, Manuel Egele, Christopher Kruegel, and Engin Kirda. 2007.  Panorama: capturing system-wide information flow for malware detection and analysis. In Proceedings of the 14th ACM conference on Computer and communications security. 116–127.
  * Zaman et al. (2023) Sourov Zaman, Lucas Ferreira, Kimberly Hall, and Grant Bourzikas. 2023.  How Cloudflare mitigated yet another Okta compromise.  (Oct. 2023).  https://blog.cloudflare.com/how-cloudflare-mitigated-yet-another-okta-compromise