#  TagS: Real-time Intrusion Detection with Tag-Propagation-based Provenance
Graph Alignment on Streaming Events

Zhenyuan Li*, Yangyang Wei*, Xiangmin Shen†, Lingzhi Wang†, Yan Chen†, Haitao
Xu*, Shouling Ji*, Fan Zhang  *Zhejiang University, †Northwestern University

###### Abstract.

The evolution and advancement of cyberattacks pose challenges to existing
security products. Recent concentrated research on provenance graph-based
detection has proved its effectiveness in attack detection and investigation.
However, implementing these approaches in practice encounters challenges such
as high overhead, slow responsiveness, and low interpretability and
extensibility.

Towards practical attack detection and investigation with provenance graphs,
we propose TagS, a tag-propagation-based streaming provenance graph alignment
system. Utilizing the tag-based intermediate result caching mechanism
alongside carefully crafted propagation rules, we eliminate the need to store
and duplicate raw data processing. This approach effectively mitigates in-
memory storage requirements and minimizes data processing overhead,
facilitating rapid on-stream graph alignment while significantly conserving
CPU and memory resources. As a result, TagS can detect and investigate various
cyber-attacks in real time. Moreover, TagS allows analysts to customize attack
query graphs flexibly to identify extended attacks in data streams.

We conduct experimental evaluations on two large-scale public datasets
containing 257.42 GB of audit logs with 12 relevant query graphs of varying
sizes, covering multiple attack techniques and scenarios. The results
demonstrate that TagS is sufficiently efficient to process 176K events per
second while sufficiently accurately identifying all 29 alignments in massive
data. Moreover, it can effectively handle the dependency explosion problem
with steady, low-level memory consumption (less than 300MB), producing only 3
false positives. Overall, the performance of TagS significantly outperforms
the state-of-the-art methods.

##  1\. Introduction

With the rapid development of information technology, the boundary between
cyberspace and the real world is blurring. There have been over a dozen
cyberattacks on infrastructure worldwide in the last year, targeting power
supplies, water plants, and banks (SentinelOne, 2023). Meanwhile, The digital
world is constantly growing and providing new opportunities for attackers to
exploit vulnerabilities and attack surfaces. Although measures such as
vulnerability patching and security policies have demonstrated efficacy in
mitigating attacks, they are not infallible and may exhibit sluggish responses
to organized and sophisticated attacks (fas, 2023).

Thus, intrusion detection and threat analysis systems that can respond to
attacks promptly and proactively draw wide attention from both industry and
academia (web, 2023). Recent research (Li et al., 2021, 2019; Munoz-Gonzalez
et al., 2017) has illustrated that graphs are an effective and generic
representation of system behaviors, which can capture both data flow and
control flow within a system comprehensively. The provenance graph-based
detection scheme (Milajerdi et al., 2019a) offers a coherent representation of
system-level behavior. Moreover, it can be expanded through plug-ins to
support additional data sources, such as containers (Chen et al., 2021),
microservices (Datta et al., 2022), and web applications (Hassan et al.,
2020).

Table 1. Comparsion of Existing PIDSs Methods |  Low O/H Realtime |  Interpret -ability |  Extensi -bility
---|---|---|---
Anomaly-based (Hassan et al., 2019; Wang et al., 2020; Li et al., 2023) | - | N | Y
Learning-based (Alsaheel et al., 2021; Zengy et al., 2022; Altinisik et al., 2023) | N | N | Y
Query-based (Gao et al., 2018b, a; Milajerdi et al., 2019a) | N | Y | Y
Tag-propagation-based (Hossain et al., 2017, 2020a) | Y | Y | N
TagS (our work) | Y | Y | Y

However, provenance graphs, known as streaming provenance graphs when derived
from audit logs, are continuously generated as streams as long as the system
remains active (Li et al., 2021). Analyzing these streaming provenance graphs
can impose significant resource demands and costs. However, defenders
typically operate within constrained budgets and computational capacities when
identifying attacks amidst diverse system behaviors and vast datasets
(Alahmadi et al., 2022). Therefore, the design of practical intrusion
detection systems must extend beyond mere accuracy considerations. Factors
such as overhead, interpretability, and extensibility are pivotal in ensuring
the practicality of detection systems but are frequently overlooked within
academia (Kokulu et al., 2019a). Table 1 compares existing mainstream
provenance-based intrusion detection systems (PIDSs) across these metrics.

Despite the benefits of extensibility, both learning-based approaches
(Alsaheel et al., 2021; Zengy et al., 2022; Altinisik et al., 2023) and
anomaly-based approaches (Hassan et al., 2019; Wang et al., 2020; Li et al.,
2023) may lack interpretability, a crucial aspect for facilitating subsequent
attack investigation and response. Specifically, learning-based methods often
involve converting provenance graphs into vectors before inputting them into
machine learning models, leading to a loss of interpretability of the original
graph structures. Conversely, anomaly-based techniques focus on identifying
deviations from typical behavioral patterns, which may flag potential attacks
but fail to provide interpretable insights. In contrast, detection schemes
based on query and tag propagation offer interpretable insights into the
detection outcomes. However, query-based schemes (Milajerdi et al., 2019a; Gao
et al., 2018b, a) need to cache substantial data (¿2GB) to support random data
access, resulting in high overhead and detection latency. Conversely, tag-
based approaches (Hossain et al., 2017, 2020a), leveraging a space-for-time
strategy by caching intermedia results in tags, exhibit reduced overhead, and
deliver prompt results. Nonetheless, current fixed-rule designs of tags limit
their adaptability to diverse attack scenarios.

To fulfil all the metrics, we propose TagS, the first tag propagation-based
streaming provenance graph alignment system in this paper. We model the
detection problem as a graph alignment problem for provenance graphs. Using
either automatic or manual methods (Milajerdi et al., 2019a; Hankin et al.,
2022; Li et al., 2022; Kaiser et al., 2023), we can abstract variants of
attack techniques or complete attacks into query graphs. Therefore, the
detection coverage can be extended by incorporating more query graphs,
allowing greater flexibility in detecting various attacks.

Graph querying and matching tasks often entail significant computational
costs, stemming from the necessity to traverse numerous branches and identify
potential matches (Livi and Rizzi, 2013). To address this challenge, we
leverage the inherent causality within provenance graphs, where events in an
attack manifest sequentially. This allows us to use tags to cache summaries of
past events and propagate them throughout the graph while awaiting alignment
with subsequent events. Each tag is associated with a query graph comprising
both the requisite propagated state records and the current aligned state.
Consequently, our framework circumvents the need to cache the entire graph for
querying, thus curtailing memory consumption. Notably, processing each event
only once significantly diminishes computational overhead.

To evaluate TagS’s accuracy and efficiency in graph alignment, we evaluated it
on two publicly available datasets, namely, the DARPA T3 Engagement 3 dataset
(TC, 2023) and the PKU-ASAL dataset (asa, 2023), which comprise a total of
257.42GB of data collected over 694 hours and dozens of attack stages.
Concurrently, we construct 12 query graphs, 6 of which correspond to attack
techniques or simple combinations, while the remaining 6 correspond to
complete attack scenarios, typically larger in scale and containing more than
10 nodes and edges. Notably, the construction logic for query graphs differed
between these two categories. Query graphs tailored to attack techniques were
optimized for real-time attack detection and aimed for generalization to
detect various attack variants. In contrast, those intended for complete
attacks could afford to be more specific to accurately pinpoint attacks.

Our evaluation outcomes demonstrate that TagS exhibits remarkable efficiency,
capable of processing 176K events per second utilizing only 6 CPU cores and
less than 300MB of RAM. Furthermore, in a dataset containing nearly 74.1
million events, TagS demonstrated notable accuracy by identifying all 29
alignments while yielding just 3 false positives. Besides, to tackle the
dependency explosion problem, which often leads to increased computational
overhead and false positives in provenance analysis, we have implemented two
strategies, namely, limiting tag initialization and removing tags based on the
number of propagation rounds and time (Hossain et al., 2020b). Our evaluation
results indicate that these strategies have successfully contained the problem
with minimal memory consumption and a low number of false positives.

In summary, this paper makes the following contributions:

  * •

Taking advantage of the inherent causality within provenance graphs, we
incorporate the streaming graph alignment problem into the tag propagation
framework. With meticulously crafted tag and propagation rules, each event
undergoes processing only once, mitigating the need for caching and
duplication processing of the raw logs, which reduces computational and memory
resource usage significantly.

  * •

Benefiting from the tag propagation framework, we are able to propose TagS,
the first real-time attack detection and investigation system with streaming
provenance graph alignment. With TagS, analysts can flexibly extend the
detection capabilities by adding query graphs to TagS. Meanwhile, the query
graphs provide interpretable insights into the detected attacks, supporting
subsequent attack responses.

  * •

Utilizing two open-source and large-scale datasets and twelve query graphs, we
systematically evaluate TagS, showcasing its superiority in accuracy, real-
time processing, and high-throughput handling of vast data volumes while
requiring minimal computational resources.

##  2\. Background & Motivation

Figure 1. Motivating Example. (Scheduled tasks (A) based on cron are commonly
used threat persistence approaches. In some complex scenarios (BC), attackers
can evade trivial rule-based detection by exploiting the existing cron tasks’
control flow. However, utilizing a graph-based pattern (D), we can accurately
identify such attack variants.)

Cybercriminals are motivated by their interests and often carry out complex
attacks using advanced techniques such as Live-off-the-Land. These techniques
blur the line between regular and malicious activities, making it challenging
for defenders to detect and investigate attacks. Additionally, defenders face
not only a range of attacks but also practical limitations.

###  2.1. Restrictions and Challenges of Cyber Attack Detection in Practice

Many research works regard detection and false alarm rates as the most
important evaluation metrics for cyber attack detection systems. However, in
practice, detection systems face more restrictions and challenges. Some
requirements are even prioritized over detection and false alarm rates.
Firstly, limited security budgets constrain the use of computational and
caching resources, which limits the complexity of algorithms that can be
employed.

Besides, there is a high demand for real-time detection results and
responsiveness to effectively block attacks in real-time and minimize losses
(Kokulu et al., 2019b). Lack of funds likewise restricts the hiring of
security analysts, hampers analysis and response to alarms, and contributes to
alarm fatigue (Alahmadi et al., 2022) and burnout (Sundaramurthy et al., 2015)
problems along with the excessive number of false alarms. A recent study
(Alahmadi et al., 2022) of real-world security operation centers (SOCs)
reveals the overwhelming number of false positives generated by security tools
and the reliance on human efforts in tool configurations, alarm tuning, and
base-lining. For instance, in the 2013 Target data breach, the malicious
activities were detected and reported by security tools but still overlooked
by analysts due to alarm fatigue, resulting in delayed response and expanded
losses (Committee, 2014). To alleviate this problem, detection systems should
yield more precise and interpretable results to facilitate analysts in
reducing repetitive and tedious tasks.

Besides, as discussed in §2.3, recent cyberattacks are becoming increasingly
sophisticated, stealthy, and mutable, making it challenging to detect all
attacks, particularly emerging ones, with a shared model or set of policies.
Therefore, the detection system must be versatile and extensible to
accommodate more attack techniques. To overcome the above challenges and
accelerate intrusion detection rollout in the industry, in this paper, we
proposed TagS with an efficient and timely tag-propagation-based graph
alignment framework and extendability and interpretable query graphs.

###  2.2. Provenance graph-based Threat Analysis

The concept of provenance originates from data lineage analysis in the
database domain. In intrusion detection, provenance analysis aims to identify
potential attack paths by tracing data and control flow. Typically, provenance
analysis is performed on entities in the system, such as process, files, and
their interactions with each other, such as reading files, forking processes,
and so on. Various data collection tools for different operating systems have
been proposed for provenance analysis utilizing mechanisms such as eBPF (ebp,
2023) and ETW (etw, 2023). Typically, these tools will fetch audit log data
actively and parse them into a unified 4-tuple $(s,v,o,t)$ event format, in
which $s$ denotes subjects of operations, $v$ denotes operation details, $o$
denotes objects of behaviors and $t$ denotes occurring time of operations.
These 4-tuple form temporal graphs through shared nodes, including subjects
and objects. Several recent studies (Chen et al., 2021; Datta et al., 2022;
Hassan et al., 2020) have expanded the scope of research by incorporating
additional data sources, such as serverless functions and web applications, to
enhance observability.

Meanwhile, a variety of provenance-graph-based detection schemes have been
proposed, demonstrating that provenance analysis excels in attack semantic
analysis, correlation behavior analysis, and interpretability of detection
results. These approaches can be roughly divided into several major
categories, namely anomaly-based, learning-based, query-based, and tag-
propagation-based (or rule-based).

Despite the benefits afforded by provenance graphs, graph analysis poses
significant computational and memory challenges, particularly when dealing
with extensive logs. To alleviate these issues, tag-propagation-based
techniques offer a promising avenue by leveraging causality analysis to
effectively reduce computational overhead. A key aspect of this approach
involves the detector’s ability to conduct causal analysis and encapsulate a
behavioral history summary within a tag. This summarized tag can then be
propagated through the provenance graph as an intermediary outcome. It’s
crucial to emphasize that the scope of tag propagation will cover the extent
of influence. Consequently, tag-propagation-based methods circumvent the need
for repetitive access to the entire provenance graph, thereby substantially
diminishing computational and caching burdens during analysis. However, as
cyber attackers continue to devise more intricate and covert attack
strategies, the limitations of existing tag-propagation-based approaches
become evident, primarily due to their reliance on fixed policies, which
hampers their adaptability and expansion of detection capabilities (Hossain et
al., 2017; Milajerdi et al., 2019a). In this paper, we introduce a novel graph
alignment algorithm designed to operate within a tag-propagation framework
with generalized and extendable detection capability.

###  2.3. Motivating Example: Attack Mutation by Hijacking Execution Flow

To further illustrate the effectiveness and efficiency of TagS, we highlight
the challenges associated with detecting an attack technique and its variants
through a motivating example, depicted in Fig. 1.

Monitoring specific system entities or single-step behavior is a common threat
detection strategy. For example, Fig. 1 (A) demonstrates a simpler way for
attackers to utilize cron for scheduled tasks and thus persistence (T1053 -
Scheduled Task/job: Cron
111https://attack.mitre.org/versions/v6/techniques/T1035/). Defenders can
easily detect such attacks by monitoring the cron configuration file. However,
as shown in Fig. 1 (B) and (C), attackers can construct attack variants by
hijacking the normal execution flow of a cron task. Specifically, in the first
variant, the attacker rewrites the /usr/bin/backup.sh that is already in the
cron scheduled task list to inject the attack logic. Attackers can further
exploit the execution flow to inject the attack logic to /usr/bin/compare.sh
that execute by backup.sh, as the second variant shows. Merely monitoring
involved file changes could result in many false alarms as the execution chain
gets longer. Thus, we need a more general and semantic-aware attack behavior
representation to cover these variants and keep a low false-positive rate.

Graphs are a highly expressive representation of cyber attacks and are
effective in detecting attacks as a graph-matching or graph-querying problem
(Milajerdi et al., 2019a; Li et al., 2022). An example of a query graph
corresponding to T1053 is presented in Fig. 1 (D). As shown, this query graph
is general enough to contain the key behaviors for persistence with cron and
match any of the above variants. Instead of an exact match, we adopt a fuzzy
graph matching (graph alignment) method to cover attack variants, including
three fuzzy strategies: fuzzy node matching, fuzzy path matching, and
incomplete graph matching. Specifically, Nodes in a graph can be matched with
a set of regular expressions based on their attributes, while edges in query
graphs may correspond to multi-hop paths in the provenance graphs. Besides, it
is not necessary to align the entire query graph with the provenance graph.
Partial matching and reaching pre-defined thresholds are considered matches.

Despite many advantages, graph matching-based methods have not been able to be
used for real-time analysis due to high overhead. In this paper, we proposed
the first real-time graph alignment-based (or fuzzy graph matching-based)
provenance system on events stream with the following advantages:

  * •

Real time.  Real-time processing based on streaming data can detect attacks
within seconds of their occurrence, significantly helpful for timely attack
blocking and damage containment.

  * •

Interpretability.  The clear attack semantics contained in the attack graph
representation can facilitate subsequent attack investigation and response.

  * •

Extensibility.  Our graph alignment-based detection can support detecting a
wider variety of attacks by extending the query graphs without changing the
system.

##  3\. System Overview

Fig. 2 presents the overall architecture of TagS. As shown, the system can be
divided into three major components, namely, the provenance graph collection
module, query graph generation module, and tag propagation-based detection
module. This section briefly describes the framework and design ideas of the
system, with more design and implementation details presented in §4 and §5.

Figure 2. System Overview

###  3.1. Streaming Provenance Graph Construction and Processing

TagS is a system for aligning streaming provenance graphs. It supports any
operating system and can convert data from different sources, such as ETW and
eBPF, into a uniform data format prior to analysis.

When a system is running, massive events are constantly generated in real-time
as a stream, which is called the streaming provenance graph in this paper. The
stream is generated quickly, and even just caching data for a short period of
time for analysis can take up a lot of memory and involve query overhead.
Therefore, it is necessary to design a streaming provenance graph analysis
framework and corresponding algorithm to reduce the cache size while still
maintaining the benefits of provenance analysis.

In this paper, we use tags to cache intermediate results, avoid repeated
consumption of events, and directly cache original logs. Besides, we design
tag propagation rules, which define strategies for initializing tags, where to
propagate them, and cache updates to ensure that each event needs to be
processed only once. Intuitively, tags cache the result of precedence behavior
summarized by propagation rules and can be viewed as the state of a particular
entity at a specific time. Thus, We can utilize an entity-to-tag map to cache
tags in memory. It is worth noting that this approach is more efficient than
caching the entire graph ($O(N)$ vs. $O(N^{2})$), especially for provenance
graphs of long-running systems where the number of events exceeds the number
of entities.

###  3.2. Tag Propagation-based Graph Alignment

Using tag-propagation for provenance graph analysis is not a new idea. Some
studies have attempted to use tags to analyze sensitive data leakage and the
combination of attack stages in systems. However, the structure and
propagation policies of these tags are relatively simple. It is still an open
question whether more complex tags can be designed to handle a more complex
problem like graph alignment on stream while maintaining high efficiency.

Specifically, there are several challenges to overcome. First, we need to try
to aggregate the alignment results of multiple branches in the graph with a
single-line tag propagation. In this paper, we adopt a “Tag - Alignment
Status” two-tier caching structure to merge aligned results in the second
caching. It is worth noting that the two-tier cache we use already merges
multiple branches. Therefore, no additional alert merging scheme is required.

Then, we adopt several strategies to minimize the processing and caching
overhead of complex tag structures. Firstly, during the tag initialization
phase, we designate seed nodes or edges for the query graph. A new tag is
initialized only when a seed node or edge is matched. Secondly, during the tag
propagation phase, we have designed an optimization algorithm for query graph
matching, which helps to reduce the number of query graph nodes that need to
be matched in each propagation. We also implement a tag removal mechanism
based on the time and the number of propagation rounds to further control the
number of labels in the system. Additionally, we can split the query graph in
a way that reduces the complexity of a single query.

###  3.3. Generating Query Graph

In this paper, we model the real-time detection problem as a graph alignment
problem, where the query graph should represent the main behaviors of an
attack and have some generalization ability to cover similar forms of attacks.
Such graphs can be generated manually, as done by Poirot (Milajerdi et al.,
2019a), or in some recently automated ways (Li et al., 2022). We apply
generalization operations to the graph, such as removing non-essential nodes
and edges and generalizing node attributes. For instance, the configuration
file of cron can be represented by the regular expression /etc/cron*. Besides,
seed nodes can also be defined by graphs. For example, all nodes that are
associated with an unknown network can be identified as attacker nodes.

In addition, we prefer to design TagS for real-time attack detection rather
than just offline attack investigation as Poirot. Thus, we also choose query
graphs corresponding to attack techniques that are more helpful for detection.
It is noteworthy that the logic of writing query graphs for attack techniques
and complete attacks differs. Query graphs for attack techniques are employed
for real-time attack detection and should be generalized to detect attack
variants. Conversely, query graphs for complete attacks can be more specific
to accurately locate attacks. In this paper, we provide 12 query graphs
covering multiple attack techniques and scenarios, whose characteristics are
presented in Table 5. In practice, analysts can customize query graphs to meet
varying targets.

##  4\. Realtime Graph Alignment with Tag Propagation Framework

Figure 3. Tag Propagation Process of Attack Technique “T1547 - Autostart with
Registry Run Keys”

As a stream-based algorithm, tag propagation only handles one event at a time
and thus reduces processing and caching overhead. The tag design is presented
in Table 2, and the overall detection process and the final result are
presented in Fig. 3 and Table 3 correspondingly. As shown, the process
consists of 5 major phases, including the tag lifecycle (initialization,
propagation, and removal), tag merging, and alert trigging. An example is
presented in Fig. 3 for clarification.

###  4.1. Tag Design

Caching is a commonly used space-for-time trick in computer science. Recently,
several approaches (Hossain et al., 2017, 2020a; Xiong et al., 2022) have
adopted tags, which are attached to nodes in provenance graphs, as a cache of
intermediate results for efficient provenance analysis. In this paper, we
propose a new tag design tailored for streaming provenance graph alignment. In
streaming graph alignment, each event can only be handled once. Thus, tags
need to cache potentially aligned subgraphs (Node List, Edge List), as well as
active fields (Active Node, Cached Path) and computational intermediate
results (Aligned Score), as Table. 2 shows.

Table 2. Key Fileds in Tags and Graph Alignment Status | Fields | Description
---|---|---
Tag | Query Graph (QG) | The query graph this tag try to align
Align Score (S) | The overall alignment status as score
Active Node ($N_{A}$) | Last query graph node aligned in tag
Cached Path (Path) | Path from the last aligned node
*Align Status (Status) | Pointer to alignment status instance
Status | Node List | Aligned node list
Edge List | Aligned edge list
Table 3. Graph Alignment Status of the Example Node /Edge ID |  Node/Edge Properties |  Aligned Result |  Align Score
---|---|---|---
➊ | [process] | firefox | -
➋ | [executable] |  C:$\backslash temp\backslash evil.dll$ | 1
➌ | reg.exe | reg.exe | 1
➍ |  $hkcu\backslash$*$\backslash run\backslash$* |  $hkcu\backslash software\backslash microsoft\backslash w$ $indows\backslash currentVersion\backslash run$ | 1
① |  ➊$\rightarrow$➋ |  (firefox $\rightarrow$ **.sh) (**.sh $\rightarrow C:\backslash temp\backslash evil.dll)$ | 0.5
② |  ➊$\rightarrow$➌ |  (firefox $\rightarrow$ reg.exe) | 1
③ |  ➌$\rightarrow$➍ |  (reg.exe $\rightarrow$ $hkcu\backslash...\backslash run...$) | 1
Total | T1547 - Autostart with Registry Run Keys | 5.5/6

Among the fields, the Query Graph (QG) illustrates the corresponding query
graphs for a tag. The Align Score (S) is a numerical evaluation of the overall
alignment status of the graph. The Active Node ($N_{A}$) and Cached Path
(Path) keep a record of the last aligned node and the subsequent path during
the tag propagation process. These two active fields can be useful for
speeding up graph alignment search, determining tag removal, and so on. The
Node List and Edge List archive complete information for additional graph
analysis.

Furthermore, query graphs that represent attack behaviors often have various
branches, as illustrated by the two ”② Tag Propagation” instances in Fig. 3.
It should be noted that the propagation of individual labels is
unidirectional, making it impossible for the ancestor nodes to know if their
following descendants are matched as well. The tags on one branch also can not
reveal the alignment status of the other sibling branches. As a solution, we
implement a secondary caching mechanism (*Align Status) to share alignment
status among tags on different branches. Therefore, all nodes in the same
alignment would have the same alignment status.

Data: streaming event: $S_{E}=[e_{i}]$, query graph list: $L_{QG}=[QG_{i}]$

Result: graph alignment Tags: $T_{GA}$

1

$M_{TC}\leftarrow$ new Map($\text{node},T_{GA}$) // init tag cache

2

3foreach  _event $e_{i}=(N_{si},R_{i},N_{di})$ in $S_{E}$_ do

4

/* Tag Initialization */

5 $(QG_{j},seed)\leftarrow$ SearchSeed($e_{i},L_{QG}$)

6 if  _$seedNode\neq null$_ then

7 $T_{GAJ}\leftarrow$ InitTag($QG_{j},seed$)

8 $M_{TC}.\textsc{Put}(N_{si},T_{GAj})$

9 end if

10

11 if  _$M_{TC}$.Contains($N_{si}$)_ then

12

/* Tag Removal */

13 if  _$T_{GA}^{\prime}$.IsOutDated()_ then

14 $M_{TC}$.RemoveTag($T_{GA}^{\prime}$)

15 else if  _$T_{GA}^{\prime}$.IsOutRounded()_ then

16 continue

17 end if

18

/* Tag Propagation */

19 $T_{GA}^{\prime}\leftarrow
T_{GA}.\textsc{Get}(N_{si}).\textsc{PropagateTag}(e_{i})$

20

/* Tag Merging */

21 if  _$M_{TC}.\textsc{Contains}(N_{di})$_ then

22 $T_{GA}^{\prime}\leftarrow
M_{TC}.\textsc{Get}(N_{di}).\textsc{MergeTag}(T_{GA}^{\prime})$

23 else

24 $M_{TC}.\textsc{Put}(N_{di},T_{GA}^{\prime})$

25 end if

/* Alert Triging */

26 if  _$T_{GA}^{\prime}$.ShouldRaiseAlert()_ then

27 $M_{TC}$.RemoveTag($T_{GA}^{\prime}$)

28 return _$T_{GA}^{\prime}$_

29 end if

30

31 end if

32

33 end foreach

Algorithm 1 Tag Propagation-based Graph Alignment

###  4.2. Tag Initialization

The tag initialization, propagation, and removal lifecycle accounts for most
of the overhead of TagS. Limiting tag initialization can effectively reduce
the system overhead. Inspired by Poirot (Milajerdi et al., 2019a), we pick one
or more seed nodes and events in each query graph. During the initialization
phase of TagS, the seeds of all query graphs are registered into a
$(seed\rightarrow query\ graph)$ map. During the stream processing phase, as
lines 3-7 in Algorithm 1 show, tags will be initialized accordingly only when
seeds are matched. Then, these initialized tags will be cached in $M_{TC}$,
which is a $(node\rightarrow tag)$ map.

When selecting seeds for a query graph, it’s important to choose the nodes and
events at the early stages of the attack chain in the causal graph, which
ensures that the entire attack can be captured during propagation. To minimize
the number of tags, it’s recommended to use unique nodes or events as seeds to
initialize the query graph. If necessary, a multi-events subgraph alignment
can be used as a condition to initialize the tag for whole graph matches for
better overall performance.

###  4.3. Tag Propagation

Tags are created to store the results of the detection process. Specifically,
in this paper, tags are used to store the partial graph alignment results,
i.e., a set of suspicious behaviors. The tag propagation process involves two
tasks: firstly, to transfer the tags and their states to the relevant nodes,
and secondly, to search for nodes and edges that match the query graphs.

Data: graph alignment Tags: $T_{GA}$, event: $e_{i}$

Result: new graph alignment Tags: $T_{GA}^{\prime}$

1

$T_{GA}^{\prime}\leftarrow$ new GraphAlignmentTag($T_{GA}$) // Copy
constructions

2 $T_{GA}^{\prime}$.Path.add($e_{i}$)

3 matchResult $\leftarrow T_{GA}$.QG.Search($N_{A}$, $e_{i}$)

4 if  _matchResult $\neq\text{null}$_ then

5 $T_{GA}^{\prime}.N_{A}\leftarrow N_{di}$

6 $T_{GA}^{\prime}$.Path $\leftarrow$ new Path()

7 $T_{GA}^{\prime}$.S $\leftarrow
T_{GA}^{\prime}$.Status.UpdateStatus(matchResult, $T_{GA}^{\prime}$.Path)

8

9 end if

10return _$T_{GA}^{\prime}$_ ;

Algorithm 2 Tag Propagation (PropagateTag())

Lines 14-19 in Algorithm 1 and 2 illustrate the tag propagation process. In
this process, tags with partial alignment results search for subsequent
alignments as they travel across the graph with the stream, completing overall
graph alignment. Specifically, for each income event ($e_{i}$), we will check
if tags exist on its source node in $M_{TC}$. If so, tags on source nodes,
including the ones just initialized, will trigger the PropagateTag() function.
A graph alignment tag records the graph alignment state up to the current
node. Therefore, the first step in propagation is to copy the contents of
existing tags ($T_{GA}$) to new instances ($T_{GA}^{\prime}$) for new nodes.
Meanwhile, $e_{i}$s will be added to the cached path in new tags.

We then check if the current event is one of the next steps in the query graph
for the currently active node ($N_{A}$). The process can also be viewed as
searching for the current event in a query graph
($GQ.\textsc{Search}(N_{A},e_{i})$), and the active nodes are set up to limit
the scope of the query and reduce the overhead. Specifically, for each
propagation, the search in the query graph only covers neighboring nodes of
the active node. This ensures a constant complexity search task irrespective
of the query graph’s size. If the current event is found, we update the latest
align to the tag and alignment status, as lines 5-7 shown in Algorithm 2.

When propagating tags, it’s possible for multiple tags to be propagated to the
same node. If the tags correspond to different query graphs, we will keep all
of them. However, if they belong to the same query graph, we need to merge
them. To do so, we use a simple greedy strategy that aims to retain as many
matching events as possible with high scores.

###  4.4. Tag Removal

Dependency explosion is a universal problem that all provenance graph analysis
encounters (Li et al., 2021). In our tag propagation scenario, dependency
explosion leads to the overspreading of the tag, which could involve excessive
computational overhead and ultimately make the solution unusable. Therefore,
except for limiting the initialization and propagation of tags, it is also
necessary to set up tag removal mechanisms (Hossain et al., 2020b).

We design two mechanisms for tag removal, namely, time-based (IsOutDated())
and propagation round-based (IsOutRounded()), as shown in lines 9-13 in
Algorithm 1, the time-based method removes tags based on their duration of
existence, which can be implemented by setting expiration times for key-valued
pairs in $M_{TC}$, while the propagation-based method stops tags propagation
after a certain number of propagation rounds (Length(Path)). These values will
be reset every time a new node is aligned or two tags are merged. By adjusting
these thresholds, we can balance the depth and time window of detection with
the overhead. More experimental results of the effectiveness of the tag
removal mechanisms and threshold selection are discussed in §6.2.1.

###  4.5. Alert Triging

As line 7 in Algorithm 2 shows, the overall graph alignment score will be
updated each time the tag propagates. The score is defined by Equation (1) and
(2):

(1) $S_{ei}=S_{sink}+\frac{1}{path\\_length}$

(2) $S_{QG}=\frac{1}{2\times
edge\\_count}\times\sum_{i=0}^{edge\\_count}S_{ei}$

Specifically, the alignment score for the whole graph ($S_{QG}$) is calculated
by adding up the alignment scores for each of the edges ($S_{ei}$) in the
graph and then dividing by twice the total number of edges ($edge\\_count$).
The alignment score for each edge is the sum of the alignment score of its
sink node ($S_{sink}$), which is fixed to 1 in this paper, plus the reciprocal
of the path length($\frac{1}{path\\_length}$). The final alignment score
ranges from 0 to 1; an example calculation is provided in Table 3.

Then we can determine whether an alert should be triggered by comparing the
score to a predefined threshold. Besides, it is worth noting that alerts
generated by TagS contain semantic information about nodes, paths, and attack
types corresponding to query graphs, which can effectively assist subsequent
attack analysis and response.

##  5\. Implementations

Based on streaming processing framework Flink (Fli, 2023) and Kafka (Kaf,
2023), we implement TagS with about 2K lines of Java code, which is publicly
available online 222https://github.com. Specifically, we first read data from
files and send original logs in string format to Kafka. Then, we adopt Flink,
a stateful stream computation framework, to process the stream cached in
Kafka.

A Flink streaming processing job can be divided into several operators of
dependency, which means that the execution of the downstream operator(s)
depends on the output produced by the upstream operator. These dependencies
dictate the order and flow of data processing within the dataflow graph,
ensuring that data is processed correctly and consistently. Note that each
operator can be subject to a separate parallelism setting, allowing flexible
control over computational resources and enabling automatic scaling for
larger-scale data synchronization.

In TagS, the Flink job consists of four operators that work together. The
first operator, called “Kafka Source,” reads string logs from Kafka. The
second operator, “Log Parsing,” extracts attribute names and values from the
strings. The third operator, “Graph Construction,” further extracts the
attributes of interest and saves the node information needed for constructing
normalized $(s,v,o,t)$ 4-tuple. Finally, the last operator, “Graph Alignment,”
performs graph alignment on the 4-tuple stream.

##  6\. Evaluation

In this section, we focus on evaluating the efficacy and efficiency of TagS as
a scalable and real-time attack detection system. In particular, we
investigated the following research questions (RQs):

  * •

RQ1: How accurate is TagS in detecting attacks?

  * •

RQ2: How efficient is TagS in handling large amounts of data?

  * •

RQ3: Are alerts generated by TagS interpretable?

###  6.1. Evaluation Setup

Table 4. Statistics of Logs and Processing Dataset & Description |  # of Entities |  # of Events |  Duartion (Data Size) |  Avg. Event Generate Rate |  # of Init Tags |  # of Propagated Tags |  Processing Time |  Avg. Event Process Rate |  Max Memory
---|---|---|---|---|---|---|---|---|---
DARPA TC E3 | CADETS | 626K | 15.2M | 260h (35.63GB) | 16eps | 6K | 373K | 75s | 202Keps | 247MB
FD | 239K | 20.6M | 172h (127.53GB) | 33eps | 110K | 249K | 108s | 173Keps | 242MB
THEIA | 1,142K | 8.1M | 135h (79.23GB) | 17eps | 1,036K | 1,540K | 56s | 150Keps | 302MB
PKU ASAL | WinServer | 11K | 8.3M | 32h (2.63GB) | 72eps | 7K | 22K | 38s | 203Keps | 183MB
Win10 | 66K | 7.9M | 30h (2.65GB) | 73eps | 65K | 451K | 42s | 188Keps | 257MB
Linux | 22K | 14.0M | 65h (9.75GB) | 60eps | 1,547K | 2,202K | 102s | 142Keps | 202MB
Overall | 2,106K | 74.1M | 694h (257.42GB) | 30eps | 2,771K | 4,837K | 421s | 176Keps | 239MB

Dataset.  To assess the effectiveness of TagS, we evaluated it on two public
large-scale datasets, which included almost 700 hours of logs, totaling nearly
250GB of data.

DARPA TC Dataset (TC, 2023). DARPA Transparent Computing program conducted red
team assessments from 2016 to 2019. Platforms with various services were set
up, and benign activities were simulated. Engagement datasets contain millions
of benign events and hundreds of malicious events, making detection a needle-
in-a-haystack task. We used public Engagement 3 datasets from Theia , Cadets ,
and Five Directions, collected on mainstream Linux, BSD, and Windows platforms
to evaluate TagS.

PKU ASAL Dataset (asa, 2023). The PKU ASAL dataset provided by NODLINK (Li et
al., 2023) consists of three hosts: a Linux server running Ubuntu, a Windows
server, and a Windows 10 host. These machines were used to carry out various
normal activities, such as file downloads, execution of privileged commands,
and compilation and execution of scripts. The PKU ASAL dataset comprises five
emulated APT attack scenarios, which include APT29, Sidewinder, and Fin6. One
attack was performed on the Linux server, three on the Windows host, and the
final attack on the Windows server involved malicious activities like
information gathering, privilege escalation, circumventing security tools,
etc.

Query Graphs.  We craft 12 query graphs, ranging from simple to sophisticated,
to assess the performance of TagS. Initially, we analyzed the attack
descriptions within each dataset, extracting MITRE ATT&CK techniques that
occurred at least once, as summarized in Table 5. Subsequently, we chose
individual techniques or combinations thereof, spanning different attack
stages, to formulate corresponding query graphs. We use the detailed technique
descriptions available in (Canary, 2023) to construct these query graphs.
Additionally, we extended our query graph set by generating more intricate
structures based on the complete attack chains outlined in the DARPA TC and
PKU ASAL datasets, as previously mentioned.

The ground truth report of the DARPA dataset describes the processing details
of all the attacks they conducted during the engagement. From that, we
extracted six attack scenarios and created corresponding attack query graphs,
including two on the CADETS dataset, two on the FiveDirections dataset, and
two on the THEIA dataset. Specifically, the selected attacks in the CADETS
data involve attacks on a web server running a backdoored version of Nginx.
The attacks in the FiveDirections dataset include a phishing email with a
malicious Excel macro attachment and exploitation of a vulnerable version of
the Firefox browser. The attacks in the THEIA dataset involve the exploitation
of malicious browser extensions.

Table 5. Characteristics of Query Graphs ID | Query Graph Description |  # of Entities |  # of Events
---|---|---|---
QG1 | T1053-Scheduled Task | 4 | 3
QG2 | T1547-Boot AutoStart | 4 | 3
QG3 | T1003-Credential Theft | 5 | 4
QG4 | T1022-Encrypt Data | 4 | 4
QG5 | T1105+T1059 (Download&Execution) | 7 | 6
QG6 | Live-off-the-Land (T1124/T1082/…) | 6 | 5
QG7 | CADETS Nginx Backdoor 3.1 | 12 | 12
QG8 | CADETS Nginx Backdoor 3.14 | 14 | 15
QG9 | FD Browser Extension 3.10 | 5 | 4
QG10 | FD Phishing E-mail 4.4 | 4 | 3
QG11 | THEIA Browser Extension 3.3 | 7 | 6
QG12 | THEIA Browser Extension 3.11 | 14 | 15

In total, we constructed 12 distinct query graphs. Half of these graphs
originated from MITRE ATT&CK technique descriptions, while the remainder were
derived from attack descriptions provided by the DARPA TC and PKU ASAL
datasets. Query graph construction differs between attack techniques and
complete attacks. For real-time detection, graphs for attack techniques
require generality to detect variants, while those for complete attacks can
prioritize specificity for accurate identification. Characteristics and
Examples of query graphs are illustrated in Table 5 and Fig. 4, which provides
a detailed overview of the characteristics of all query graphs. And all query
graphs are presented in §A.

Platform.  All experiments are performed on a laptop with AMD Ryzen 5 7600X
6-Core CPUs @ 4.70 GHz, 32 GB physical memory, and 1TB SSD, running Windows
11.

###  6.2. Evaluation Results

####  6.2.1. RQ1: How accurate is TagS in finding subgraphs?

To measure the accuracy of TagS, we perform graph alignment of all query
graphs on the datasets. Table 6 presents the true positive (TP) and false
positive (FP) of query graphs on different datasets with the threshold set to
0.6. Overall, the query graphs aligned with 32 subgraphs among the datasets.
29 out of 32 are true positive, suggesting TagS can detect threats
corresponding to the query graph with high precision. Several techniques
successfully aligned with subgraphs in multiple datasets, demonstrating query
graphs’ generality in detecting attack variants in various scenarios.

Figure 4. Query Graph of “CADETS Nginx Backdoor 3.14” (QG8) and Corresponding True Positive and False Positive (The stars label the seed edges, and the green and orange boxes mark the difference between true positive and false positive.) Table 6. TP and FP of Query Graphs Query Graph | True-Positives | False-Positives
---|---|---
QG1 | CADETS(1), THEIA(5) | 0
QG2 | Win10(4) | 0
QG3 | Win10(3) | 0
QG4 | Win10(2) | 0
QG5 | CADETS(3), THEIA(2) | 0
QG6 |  Linux(1), Win10(1), WinServer(1) | 0
QG7 | CADETS(1) | CADETS(1)
QG8 | CADETS(1) | CADETS(1)
QG9 | FD(1) | 0
QG10 | FD(1) | FD(1)
QG11 | THEIA(1) | 0
QG12 | THEIA(1) | 0
Summary | 29 | 3
Precision | 0.906

It is worth noting that not all aligned subgraphs are indicative of the
attack. For example, QG5 for “Download & execution” can be part of normal
behavior and should not be considered as false positives. False positives will
only be counted when there is an over-propagation of tags that leads to false
alarms. The example depicted in Fig. 4 illustrates the performance of QG8 for
”CADETS Nginx Backdoor 3.14” (A) on the CADETS dataset. Specifically, QG8
successfully aligned two subgraphs (B) within the dataset, one representing a
true positive and the other a false positive. Notably, both subgraphs exhibit
identical behaviors attributed to the process pEja72mA. However, the false
positive arises due to the excessive propagation of a partially matched tag
and its corresponding status from the node representing the file /etc/passwd
to another instance of nginx.

Selecting the Threshold. The selection of the threshold significantly
influences the outcomes of detection. If set too low, the threshold may cause
a surge in false positives, whereas an excessively high threshold could result
in overlooking true positives. To identify the optimal threshold, we computed
the $precision=\frac{TP}{TP+FP}$, $recall=\frac{TP}{TP+FN}$, and $F1\
Score=\frac{2TP}{2TP+FP+FN}$ across various threshold values using all
available datasets, as depicted in Fig. 5. It’s important to note that we
manually verified the alignment of graphs at a low threshold (0.5) to
establish ground truth for the aforementioned value computations.

The analysis results underscore the challenge of striking a delicate balance
between detection accuracy and minimizing false alarms when employing a
unified threshold selection method. In our specific context, prioritizing high
detection rates takes precedence over minimizing false alarms. Consequently,
we have elected to adopt a unified threshold of 0.6, which effectively
captures all true positives while concurrently minimizing false positives.
Furthermore, analysts are encouraged to tailor thresholds to individual query
graphs to optimize accuracy in practical applications.

Figure 5. Selecting the Threshold

####  6.2.2. RQ2: How efficient isTagS in handling large amounts of data?

To evaluate the efficiency of TagS, we searched the 12 query graphs on all
datasets simultaneously. The overall results are presented in Table 4, which
reveals that processing a total of 257.42 GB of data collected in 694 hours
took only 421 seconds, with a throughput of 176K events per second on average.
This means that even a personal laptop can process real-time streaming data
from nearly 6,000 devices at the same time.

During detection, 2.771 million tags are initialized, and an additional 4.837
million tags are propagated. Fig. 8 and 9 further show the number of
initialized tags and the number of propagation of each query graph on each
dataset, respectively. As shown, some query graphs initialize a large number
of tags and propagate many times. These graphs, such as QG5 for “Download &
execution”, often involve common system behaviors. As discussed in §4, each
tag propagation has roughly the same overhead, which is independent of the
specific query graph. Thus, the query graphs with more complicated structures
take up more computational resources. However, in practice, most complicated
attacks differ significantly from normal behavior (Milajerdi et al., 2019b;
Altinisik et al., 2023). Therefore, corresponding query graphs would not
initialize nor propagate frequently, such as QG1 for “Scheduled Task” and QG7
for “Nginx Backdoor”. Thus, these complicated query graphs would not cause too
much overhead. Analysts can also customize their query graphs to prevent
excessive overhead.

Figure 6. Comparsion of Throughput with Existing Works

Comparsion with Existing Works. To further clarify the efficiency of TagS, we
compare it with several existing works, including NODLINK (Li et al., 2023),
ProvDetector (Wang et al., 2020), UNICORN (Han et al., 2020), HOLMES
(Milajerdi et al., 2019b), and SAQL (Gao et al., 2018a).

Fig. 6 illustrates a comparison of the throughput of TagS and several other
systems when processing the same datasets. The baseline result is from NODLINK
(Li et al., 2023). The experiments were conducted on the hardware with a
32-core CPU, which is much better than ours. Despite this, TagS shows higher
throughputs on every dataset. Therefore, we believe that TagS is more
efficient than these existing systems. Besides, SAQL (Gao et al., 2018a) also
shows a high throughput of up to 110K events per second on a 12-core CPU.
However, due to the lack of open-source systems and datasets, it is
challenging to perform a fair comparison. Nevertheless, the results from their
original paper indicate that SAQL’s memory occupation, approximately 2GB, and
the overhead of parallel performing multiple queries are larger than ours.

Figure 7. CPU and Memory Occupation of Each Component

Breakdown Analysis.  In order to analyze the computational resource usage, we
decomposed and examined the computational resource consumption of each Flink
operator. The task allocation for each operator has been discussed in §5.
Brefily, the Kafka source operator pulls data from Kafka and the Flink
framework, while the log parsing and graph construction operators parse raw
string format logs and construct the streaming provenance graph, respectively.
The graph alignment operator aligns graphs with the tag-propagation framework.
All these operators depend on the output of the previous operators. To analyze
each module individually, we disabled one operator at a time, starting from
the back to the front, and recorded the average time and memory consumption.

The summarized results are presented in Fig. 7. As shown in the figure,
pulling data from Kafka requires more resources, accounting for approximately
40% of the computation time and 25% of the memory. Besides, Raw log parsing
occupies more memory as it caches some of the data for event merging. The
graph construction operator utilizes resources in a more balanced way.
Finally, The graph alignment operator consumes only about 25% of the overall
resources. Therefore, if the data structure generated by the collector at the
beginning meets the requirements, the detection overhead can be significantly
reduced.

Figure 8. Number of Init Tags Figure 9. Number of Propagated Tags

####  6.2.3. RQ3: Are alerts generated by TagS interpretable?

Interpretability of detection results is important for subsequent alarm
analysis, confirmation, and response. In this section, we performed a case
study to illustrate the interpretability of the alerts generated by TagS in
Fig. 4,. As Table 3 shows, during tag propagation, TagS records the nodes and
edges corresponding to the query graph. Therefore, based on the information in
the alerts, we can reconstruct a precise system behavior graph, exemplified in
Fig. 4 (B), eliminating the need for reiterative querying of the original
logs, which ensures timely response.

Based on the alignment results, the semantics of nodes and edges within
behavior graphs can be extracted. For instance, the file /tmp/pEja72mA and the
process pEja72mA represent a suspicious program downloaded from the internet
and its associated process, respectively. This suggests that analysts could
devise automated response strategies leveraging the query graph, such as
automatically uploading /tmp/pEja72mA for further analysis or terminating
pEja72mA to mitigate potential malicious activity.

##  7\. Related Work

###  7.1. Intrusion Detection and Investigation

Cyber attack detection is a highly explored field, yet traditional
methodologies often encounter difficulties when confronted with sophisticated
attacks. Static analysis-based approaches (Cha et al., 2011; Baldangombo et
al., 2013; Malhotra and Bajaj, 2016) rely on predefined rules and signatures,
rendering them susceptible to obfuscation and encryption. Conversely, dynamic
API behavior analysis techniques (Or-Meir et al., 2019; Afianian et al., 2019;
Yang et al., 2020) demonstrate proficiency in pinpointing specific malicious
behaviors but struggle to adapt to the evolving system landscape, thus
hindering their efficacy in detecting multi-stage attacks that unfold
gradually over time. In recent years, there’s been growing interest in
provenance-based detection for its effective intrusion detection capabilities.
Provenance-based Intrusion Detection Systems (PIDSs) offer semantic awareness
and robust detection by recording complete execution history capturing
information flow among system entities. PIDSs are categorized based on their
underlying detection mechanisms.

Anomaly-based Approaches: NODOZE (Hassan et al., 2019) and its subsequent
work, PROVDETECTOR(Wang et al., 2020), represent two state-of-the-art anomaly
detection approaches for provenance data. NoDoze traverses the provenance
graph to a specified depth and computes an anomaly score. At the same time,
PROVDETECTOR identifies rare paths within the graph and them into numerical
vectors for anomaly score calculation. These anomaly scores are then compared
against manually defined thresholds to determine whether an alert should be
triggered.

Learning-based Approaches: ATLAS (Alsaheel et al., 2021) extracts sequences
from the graph and employs a Long Short-term Memory model for sequence
classification. UNICORN (Han et al., 2020) extracts histograms from the
provenance graph and transforms them into numerical vectors using the
HistoSketch approach (Yang et al., 2017). On the other hand, SHADEWATCHER
(Zengy et al., 2022) learns a recommendation model to rank interactions based
on their likelihood of occurring in benign scenarios.

Query-based Approaches: SAQL (Gao et al., 2018a) and AIQL (Gao et al., 2018b)
represent two state-of-the-art query-based PIDSs. These systems employ query
languages designed for efficient searching on cached data, although this
approach requires significant storage space for data caching, leading to
overhead and scalability concerns. Additionally, POIROT (Milajerdi et al.,
2019a) establishes a knowledge base of attack behavior graphs and performs
graph alignment queries to generate alignment scores.

Tag-propagation-based Approaches: In tag propagation-based detection, event
histories are condensed into tags and disseminated to capture subsequent
interactions. These tags contain diverse information, such as numerical values
representing confidentiality and integrity levels (Hossain et al., 2017,
2020a). Eventually, these tags aggregate to reach a predefined threshold,
triggering alarms. For instance, SLEUTH (Hossain et al., 2017) utilizes a tag
propagation-based approach by defining two types of tags for each node,
namely, trustworthiness tags and confidentiality tags. Similar tags design is
also used in MORSE (Hossain et al., 2020a) to emphasize critical aspects of
the provenance graph. Conversely, HOLMES (Milajerdi et al., 2019b) constructs
a high-level scenario graph (HSG) from the original provenance graph and maps
scenarios to the lifecycle of APT attacks to determine alarm generation based
on predefined policies.

While these studies effectively analyze provenance graphs from various angles
and demonstrate strong performance in experimental evaluations, their
practical applicability remains limited. System-wide provenance analysis
entails significant overhead in data collection and analysis, potentially
impacting responsiveness and employability. In this paper, we propose TagS,
which upholds excellent interpretability and scalability while minimizing
overhead and maximizing throughput.

###  7.2. Graph Searching

While graph-searching techniques are widely employed, existing approaches face
limitations when applied to provenance graphs due to inherent conflicts in
their underlying assumptions. For example, G-Ray (Tong et al., 2007), NeMa
(Khan et al., 2013), and REGAL (Heimann et al., 2018) are tailored for
undirected graphs, focus solely on node features, presume static node
properties, and are restricted to offline query scenarios. Additionally, while
some works like MAGE (Pienta et al., 2014) integrate edge features, they fail
to meet the specific demands of provenance-based detection scenarios.
Recently, Graph Convolutional Networks (GCNs) and Graph Neural Networks (GNNs)
have emerged as promising tools for learning graph representations and
enabling efficient graph matching (Chen et al., 2020). These methods leverage
embedding functions to map each graph into a vector space where similar graphs
are close while dissimilar ones are distant. Despite their success in certain
applications (Yan et al., 2021; King et al., 2023; Roy et al., 2022), GCNs and
GNNs face challenges in terms of computational complexity, particularly when
increasing model depth to enhance matching performance.

In security, graph matching-based detection techniques match subgraphs against
known malicious patterns to identify potential threats. Traditional search
algorithms struggle to scale to large graphs, necessitating the use of graph
embedding (Wang et al., 2022) or other approximate (Manzoor et al., 2016; Han
et al., 2020; Bhatia et al., 2023) methods for graph comparison. For
provenance graph analysis, Poirot (Milajerdi et al., 2019a) proposes a graph
alignment metric and a similarity search algorithm. However, it requires
significant storage space and only supports offline queries. In response to
storage space constraints, ProvG-Searcher (Altinisik et al., 2023) employs a
provenance graph partition mechanism and a graph embedding algorithm to reduce
storage requirements. Nevertheless, the graph embedding method still suffers
from exponentially growing computational complexity. To overcome the above
issues, TagS is designed to efficiently perform graph matching by caching
graph information on tags and propagating tags on nodes to facilitate
alignment search. The cached information can also provide contextual details,
such as matched entities, upon identifying a graph match.

##  8\. Discussion & Conclusion

###  8.1. Feasibility in Practice

Stream-based & Scalability.  In reality, intrusion detection systems are
deployed in many continuously operating machines, which generate an enormous
amount of logs every moment. Storing the raw logs, even for a small period of
time, takes up a significant amount of memory. Short caching times result in
the system being easily bypassed by long, stealthy APT attacks, while long
caching times can lead to long response times and massive overhead. On the
other hand, selective data caching can create new opportunities for attackers
to bypass the system. Therefore, we choose a streaming scheme for efficient
processing and responding.

Interpretability, False-positives & Alarm Fatigue.  Once the security
operations center receives alerts, it is necessary to analyze and respond to
the alarms manually. However, false alarms and incomprehensible results can
make analysis tasks complex and time-consuming. To address this issue, we use
graph-based detection to provide a graph-based description of detection
results. We also implement two strategies to reduce the false alarms and
mitigate the dependency explosion problem, including limited tag
initialization and removing tags based on the number of propagation rounds and
time.

###  8.2. Limitation

Out of Observability. Observability is crucial for effective intrusion
detection. However, it’s worth noting that some intrusion behaviors may not be
detectable with basic provenance graphs. In some cases, lacking nodes or edges
could lead to detection failure. To overcome this limitation, recent studies
have proposed incorporating additional data layers, such as web (Hassan et
al., 2020) and microservices (Datta et al., 2022), into the provenance graph.
We can extend our detection capabilities by integrating these data into TagS.

Out of Query Graphs. In this paper, we present a generalized framework for
streaming graph alignment that can detect various types of attacks. The
detection capability of the framework is determined by the query graph set
used. It’s important to note that attackers may design attack paths beyond the
query graphs’ scope despite their generalization ability. To address this
issue, analysts can create customized query graphs to flexibly extend TagS’s
detection coverage. Moreover, recent work on extracting graph-structured
attack representations from cyber threat intelligence (Li et al., 2022)
suggests that automating query graph extraction could be a promising direction
for future work.

###  8.3. Conclusion

This paper proposes TagS, a real-time intrusion detection system that utilizes
tag-propagation-based steaming provenance graph alignment for accurate attack
detection. By framing attack detection as a graph alignment challenge, we not
only enhance the interpretability of the system but also ensure its
effectiveness. TagS adopts a tag-propagation framework, circumventing the
substantial memory overhead associated with caching the entire provenance
graph and the excessive computational burden typically encountered with
conventional graph-matching algorithms.

Furthermore, we perform experimental evaluations on two large-scale public
datasets, including 257.42 GB of audit logs with 12 relevant query graphs of
varying sizes, covering multiple attack techniques and scenarios. Our results
demonstrate that TagS is efficient enough to process 176K events per second
while accurately identifying all 29 alignments in massive data, significantly
outperforming the state-of-the-art methods.

## References

  * (1)
  * Fli (2023) 2023\.  Apache Flink, Stateful Computations over Data Stream.  https://flink.apache.org/.
  * Kaf (2023) 2023\.  APACHE KAFKA.  https://kafka.apache.org/.
  * fas (2023) 2023\.  Cloud Endpoint Protection - Stop Threats at a Faster Speed.  https://www.sentinelone.com/beyond_endpoint/xdr_protection.
  * ebp (2023) 2023\.  eBPF.  https://ebpf.io/.
  * etw (2023) 2023\.  Event Tracing for Windows (ETW).  https://learn.microsoft.com/en-us/windows-hardware/drivers/devtest/event-tracing-for-windows--etw-.
  * web (2023) 2023\.  Microsoft Sentinel.  https://www.microsoft.com/en-us/security/business/siem-and-xdr/microsoft-sentinel.
  * asa (2023) 2023\.  PKU ASAL Dataset.  https://github.com/PKU-ASAL/Simulated-Data.
  * TC (2023) 2023\.  Transparent-Computing.  https://github.com/darpa-i2o/Transparent-Computing.
  * Afianian et al. (2019) Amir Afianian, Salman Niksefat, Babak Sadeghiyan, and David Baptiste. 2019.  Malware Dynamic Analysis Evasion Techniques: A Survey.  _ACM Comput. Surv._ 52, 6, Article 126 (nov 2019), 28 pages.  https://doi.org/10.1145/3365001
  * Alahmadi et al. (2022) Bushra A. Alahmadi, Louise Axon, and Ivan Martinovic. 2022.  99% False Positives: A Qualitative Study of SOC Analysts’ Perspectives on Security Alarms. In _31st USENIX Security Symposium (USENIX Security 22)_. USENIX Association, Boston, MA, 2783–2800.  https://www.usenix.org/conference/usenixsecurity22/presentation/alahmadi
  * 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 _USENIX Security Symposium_. 3005–3022.
  * Altinisik et al. (2023) Enes Altinisik, Fatih Deniz, and Hüsrev Taha Sencar. 2023.  ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search. In _Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security_. 2247–2261.
  * Baldangombo et al. (2013) Usukhbayar Baldangombo, Nyamjav Jambaljav, and Shi-Jinn Horng. 2013.  A static malware detection system using data mining methods.  _arXiv preprint arXiv:1308.2831_ (2013).
  * Bhatia et al. (2023) Siddharth Bhatia, Mohit Wadhwa, Kenji Kawaguchi, Neil Shah, Philip S Yu, and Bryan Hooi. 2023.  Sketch-based anomaly detection in streaming graphs. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 93–104.
  * Canary (2023) Red Canary. 2023.  Explore Atomic Red Team.  https://atomicredteam.io/
  * Cha et al. (2011) Sang Kil Cha, Iulian Moraru, Jiyong Jang, John Truelove, David Brumley, and David G Andersen. 2011.  SplitScreen: Enabling efficient, distributed malware detection.  _Journal of Communications and Networks_ 13, 2 (2011), 187–200.
  * Chen et al. (2020) Fenxiao Chen, Yun-Cheng Wang, Bin Wang, and C-C Jay Kuo. 2020.  Graph representation learning: a survey.  _APSIPA Transactions on Signal and Information Processing_ 9 (2020), e15.
  * Chen et al. (2021) Xutong Chen, Hassaan Irshad, Yan Chen, Ashish Gehani, and Vinod Yegneswaran. 2021.  $\\{$CLARION$\\}$: Sound and clear provenance tracking for microservice deployments. In _30th USENIX Security Symposium (USENIX Security 21)_. 3989–4006.
  * Committee (2014) Senator Commerce Committee. 2014.  A “Kill Chain” Analysis of the 2013 Target Data Breach.  https://www.commerce.senate.gov/services/files/24d3c229-4f2f-405d-b8db-a3a67f183883
  * Datta et al. (2022) Pubali Datta, Isaac Polinsky, Muhammad Adil Inam, Adam Bates, and William Enck. 2022.  ALASTOR: Reconstructing the Provenance of Serverless Intrusions. In _31st USENIX Security Symposium (USENIX Security 22)_. 2443–2460.
  * Gao et al. (2018a) Peng Gao, Xusheng Xiao, Ding Li, Zhichun Li, Kangkook Jee, Zhenyu Wu, Chung Hwan Kim, Sanjeev R Kulkarni, and Prateek Mittal. 2018a.  $SAQL$: A Stream-based Query System for $\\{$Real-Time$\\}$ Abnormal System Behavior Detection. In _27th USENIX Security Symposium (USENIX Security 18)_. 639–656.
  * Gao et al. (2018b) Peng Gao, Xusheng Xiao, Zhichun Li, Fengyuan Xu, Sanjeev R Kulkarni, and Prateek Mittal. 2018b.  $AIQL$: Enabling efficient attack investigation from system monitoring data. In _2018 USENIX Annual Technical Conference (USENIX ATC 18)_. 113–126.
  * Han et al. (2020) Xueyuan Han, Thomas F. J.-M. Pasquier, Adam Bates, James Mickens, and Margo I. Seltzer. 2020.  Unicorn: Runtime Provenance-Based Detector for Advanced Persistent Threats. In _27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23-26, 2020_. The Internet Society.  https://www.ndss-symposium.org/ndss-paper/unicorn-runtime-provenance-based-detector-for-advanced-persistent-threats/
  * Hankin et al. (2022) Chris Hankin, Pasquale Malacaria, et al. 2022\.  Attack dynamics: an automatic attack graph generation framework based on system topology, CAPEC, CWE, and CVE databases.  _Computers & Security_ 123 (2022), 102938.
  * 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 _26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24-27, 2019_. The Internet Society.  https://www.ndss-symposium.org/ndss-paper/nodoze-combatting-threat-alert-fatigue-with-automated-provenance-triage/
  * Hassan et al. (2020) Wajih Ul Hassan, Mohammad Ali Noureddine, Pubali Datta, and Adam Bates. 2020.  Omegalog: High-fidelity attack investigation via transparent multi-layer log analysis. In _Network and distributed system security symposium_.
  * Heimann et al. (2018) Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. 2018.  REGAL: Representation Learning-Based Graph Alignment. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ (Torino, Italy) _(CIKM ’18)_. Association for Computing Machinery, New York, NY, USA, 117–126.  https://doi.org/10.1145/3269206.3271788
  * 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. (2020a) Md Nahid Hossain, Sanaz Sheikhi, and R. Sekar. 2020a.  Combating Dependence Explosion in Forensic Analysis Using Alternative Tag Propagation Semantics. In _IEEE Symposium on Security and Privacy (SP)_.
  * Hossain et al. (2020b) Md Nahid Hossain, Sanaz Sheikhi, and R Sekar. 2020b.  Combating dependence explosion in forensic analysis using alternative tag propagation semantics. In _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 1139–1155.
  * Kaiser et al. (2023) Florian Klaus Kaiser, Uriel Dardik, Aviad Elitzur, Polina Zilberman, Nir Daniel, Marcus Wiens, Frank Schultmann, Yuval Elovici, and Rami Puzis. 2023.  Attack Hypotheses Generation Based on Threat Intelligence Knowledge Graph.  _IEEE Transactions on Dependable and Secure Computing_ (2023).
  * Khan et al. (2013) Arijit Khan, Yinghui Wu, Charu C. Aggarwal, and Xifeng Yan. 2013.  NeMa: Fast Graph Search with Label Similarity.  _Proc. VLDB Endow._ 6, 3 (jan 2013), 181–192.  https://doi.org/10.14778/2535569.2448952
  * King et al. (2023) Isaiah J King, Xiaokui Shu, Jiyong Jang, Kevin Eykholt, Taesung Lee, and H Howie Huang. 2023.  EdgeTorrent: Real-time Temporal Graph Representations for Intrusion Detection. In _Proceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses_. 77–91.
  * Kokulu et al. (2019a) Faris Bugra Kokulu, Ananta Soneji, Tiffany Bao, Yan Shoshitaishvili, Ziming Zhao, Adam Doupé, and Gail-Joon Ahn. 2019a.  Matched and Mismatched SOCs: A Qualitative Study on Security Operations Center Issues. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ (London, United Kingdom) _(CCS ’19)_. Association for Computing Machinery, New York, NY, USA, 1955–1970.  https://doi.org/10.1145/3319535.3354239
  * Kokulu et al. (2019b) Faris Bugra Kokulu, Ananta Soneji, Tiffany Bao, Yan Shoshitaishvili, Ziming Zhao, Adam Doupé, and Gail-Joon Ahn. 2019b.  Matched and mismatched SOCs: A qualitative study on security operations center issues. In _Proceedings of the 2019 ACM SIGSAC conference on computer and communications security_. 1955–1970.
  * 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).
  * Li et al. (2019) Zhenyuan Li, Qi Alfred Chen, Chunlin Xiong, Yan Chen, Tiantian Zhu, and Hai Yang. 2019.  Effective and light-weight deobfuscation and semantic-aware attack detection for powershell scripts. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_. 1831–1847.
  * Li et al. (2021) Zhenyuan Li, Qi Alfred Chen, Runqing Yang, Yan Chen, and Wei Ruan. 2021.  Threat detection and investigation with system-level provenance graphs: a survey.  _Computers & Security_ 106 (2021), 102282.
  * Li et al. (2022) Zhenyuan Li, Jun Zeng, Yan Chen, and Zhenkai Liang. 2022.  AttacKG: Constructing technique knowledge graph from cyber threat intelligence reports. In _European Symposium on Research in Computer Security_. Springer, 589–609.
  * Livi and Rizzi (2013) Lorenzo Livi and Antonello Rizzi. 2013.  The graph matching problem.  _Pattern Analysis and Applications_ 16 (2013), 253–283.
  * Malhotra and Bajaj (2016) Aashima Malhotra and Karan Bajaj. 2016.  A hybrid pattern based text mining approach for malware detection using DBScan.  _CSI transactions on ICT_ 4 (2016), 141–149.
  * Manzoor et al. (2016) Emaad Manzoor, Sadegh M. Milajerdi, and Leman Akoglu. 2016.  Fast Memory-Efficient Anomaly Detection in Streaming Heterogeneous Graphs. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (San Francisco, California, USA) _(KDD ’16)_. Association for Computing Machinery, New York, NY, USA, 1035–1044.  https://doi.org/10.1145/2939672.2939783
  * Milajerdi et al. (2019a) Sadegh M Milajerdi, Birhanu Eshete, Rigel Gjomemo, and VN Venkatakrishnan. 2019a.  Poirot: Aligning attack behavior with kernel audit records for cyber threat hunting. In _Proceedings of the 2019 ACM SIGSAC conference on computer and communications security_. 1795–1812.
  * Milajerdi et al. (2019b) Sadegh M. Milajerdi, Rigel Gjomemo, Birhanu Eshete, R. Sekar, and V.N. Venkatakrishnan. 2019b.  HOLMES: Real-Time APT Detection through Correlation of Suspicious Information Flows. In _IEEE Symposium on Security and Privacy (SP)_.  https://doi.org/10.1109/SP.2019.00026
  * Munoz-Gonzalez et al. (2017) Luis Munoz-Gonzalez, Daniele Sgandurra, Andrea Paudice, and Emil C Lupu. 2017.  Efficient attack graph analysis through approximate inference.  _ACM Transactions on Privacy and Security (TOPS)_ 20, 3 (2017), 1–30.
  * Or-Meir et al. (2019) Ori Or-Meir, Nir Nissim, Yuval Elovici, and Lior Rokach. 2019.  Dynamic Malware Analysis in the Modern Era—A State of the Art Survey.  _ACM Comput. Surv._ 52, 5, Article 88 (sep 2019), 48 pages.  https://doi.org/10.1145/3329786
  * Pienta et al. (2014) Robert Pienta, Acar Tamersoy, Hanghang Tong, and Duen Horng Chau. 2014.  MAGE: Matching approximate patterns in richly-attributed graphs. In _2014 IEEE International Conference on Big Data (Big Data)_. 585–590.  https://doi.org/10.1109/BigData.2014.7004278
  * Roy et al. (2022) Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. 2022.  Interpretable neural subgraph matching for graph retrieval. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 8115–8123.
  * SentinelOne (2023) SentinelOne. 2023.  High-impact attacks on critical infrastructure climb 140%.  https://securityintelligence.com/news/high-impact-attacks-on-critical-infrastructure-climb-140/.
  * Sundaramurthy et al. (2015) Sathya Chandran Sundaramurthy, Alexandru G Bardas, Jacob Case, Xinming Ou, Michael Wesch, John McHugh, and S Raj Rajagopalan. 2015.  A human capital model for mitigating security analyst burnout. In _Eleventh Symposium On Usable Privacy and Security (SOUPS 2015)_. 347–359.
  * Tong et al. (2007) Hanghang Tong, Christos Faloutsos, Brian Gallagher, and Tina Eliassi-Rad. 2007.  Fast Best-Effort Pattern Matching in Large Attributed Graphs. In _Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (San Jose, California, USA) _(KDD ’07)_. Association for Computing Machinery, New York, NY, USA, 737–746.  https://doi.org/10.1145/1281192.1281271
  * Wang et al. (2020) Qi Wang, Wajih Hassan, Ding Li, Kangkook Jee, Xiao Yu, Kexuan Zou, Junghwan Rhee, Zhengzhang Chen, Wei Cheng, Carl.A. Gunter, and Haifeng Chen. 2020.  You Are What You Do: Hunting Stealthy Malware via Data Provenance Analysis.  https://doi.org/10.14722/ndss.2020.24167
  * Wang et al. (2022) Su Wang, Zhiliang Wang, Tao Zhou, Hongbin Sun, Xia Yin, Dongqi Han, Han Zhang, Xingang Shi, and Jiahai Yang. 2022.  Threatrace: Detecting and tracing host-based threats in node level through provenance graph learning.  _IEEE Transactions on Information Forensics and Security_ 17 (2022), 3972–3987.
  * Xiong et al. (2022) Chunlin Xiong, Tiantian Zhu, Weihao Dong, Linqi Ruan, Runqing Yang, Yueqiang Cheng, Yan Chen, Shuai Cheng, and Xutong Chen. 2022.  Conan: A Practical Real-Time APT Detection System With High Accuracy and Efficiency.  _IEEE Transactions on Dependable and Secure Computing_ 19, 1 (2022), 551–565.  https://doi.org/10.1109/TDSC.2020.2971484
  * Yan et al. (2021) Yuchen Yan, Lihui Liu, Yikun Ban, Baoyu Jing, and Hanghang Tong. 2021.  Dynamic Knowledge Graph Alignment.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 35, 5 (May 2021), 4564–4572.  https://doi.org/10.1609/aaai.v35i5.16585
  * Yang et al. (2017) Dingqi Yang, Bin Li, Laura Rettig, and Philippe Cudré-Mauroux. 2017.  Histosketch: Fast similarity-preserving sketching of streaming histograms with concept drift. In _2017 IEEE International Conference on Data Mining (ICDM)_. IEEE, 545–554.
  * Yang et al. (2020) Runqing Yang, Xutong Chen, Haitao Xu, Yueqiang Cheng, Chunlin Xiong, Linqi Ruan, Mohammad Kavousi, Zhenyuan Li, Liheng Xu, and Yan Chen. 2020.  Ratscope: Recording and reconstructing missing rat semantic behaviors for forensic analysis on windows.  _IEEE Transactions on Dependable and Secure Computing_ 19, 3 (2020), 1621–1638.
  * Zengy et al. (2022) Jun Zengy, Xiang Wang, Jiahao Liu, Yinfang Chen, Zhenkai Liang, Tat-Seng Chua, and Zheng Leong Chua. 2022.  Shadewatcher: Recommendation-guided cyber threat analysis using system audit records. In _2022 IEEE Symposium on Security and Privacy (SP)_. IEEE, 489–506.

##  Appendix A Query Graphs

Figure 10. The Rest of Query Graphs Used in This Paper (Seed nodes and edges
are labeled with stars.)