The Case for Learned Provenance-based System Behavior Baseline
Authors: Yao Zhu
Zhenyuan LI
Yangyang Wei
Shouling Ji
Venue: ICML 2025 poster (2025)
Keywords: graph representation learning
provenance graph
cyber attack detection
Primary area: applications->everything_else

Abstract: Provenance graphs describe data flows and causal dependencies of host activities, enabling to track the data propagation and manipulation throughout the systems, which provide a foundation for intrusion detection. However, these Provenance-based Intrusion Detection Systems (PIDSes) face significant challenges in storage, representation, and analysis, which impede the efficacy of machine learning models such as Graph Neural Networks (GNNs) in processing and learning from these graphs. This paper presents a novel learning-based anomaly detection method designed to efficiently embed and analyze large-scale provenance graphs. Our approach integrates dynamic graph processing with adaptive encoding, facilitating compact embeddings that effectively address out-of-vocabulary (OOV) elements and adapt to normality shifts in dynamic real-world environments. Subsequently, we incorporate this refined baseline into a tag-propagation framework for real-time detection. Our evaluation demonstrates the method's accuracy and adaptability in anomaly path mining, significantly advancing the state-of-the-art in handling and analyzing provenance graphs for anomaly detection.

The Case for Learned Provenance-based System Behavior Baseline
Yao Zhu
Zhenyuan Li
Yangyang Wei? Shouling Ji
Abstract
ponents nodes and their interactions as edges, for ex- ample, PROCESS exexe READ FILE B. txt. These edges are further enriched with temporal data, enhancing the graph's ability to chronologically trace system actions. Crucially, the inherent causal structure of these graphs en- sures that only prior actions can affect subsequent behaviors, providing a robust framework for analyzing and predicting system events.
Provenance graphs describe data flows and causal dependencies of host activities, enabling to track the data propagation and manipulation through- out the systems, which provide foundation for intrusion detection. However, these Provenance- based Intrusion Detection Systems (PIDSes) face significant challenges in storage, representation, and analysis, which impede the efficacy of ma- chine learning models such as Graph Neural Net- works (GNNs) in processing and learning from these graphs. This paper presents a novel learning- based anomaly detection method designed to effi- ciently embed and analyze large-scale provenance graphs. Our approach integrates dynamic graph processing with adaptive encoding, facilitating compact embeddings that effectively address out- of-vocabulary (OOV) elements and adapt nor- mality shifts in dynamic real-world environments. Subsequently, we incorporate this refined baseline into a tag- prgprropagttion framework for real-time de- tection. Our evaluation demonstrates the method's s accuracy and adaptability in anomaly path min- ing, significantly advancing the in handling and analyzing provenance graphs for anomaly detection.
Intrusion detection requires immediate responses due to the urgent nature of the task. While provenance graphs offer considerable benefits for security analysis, they face several challenges that impair their effectiveness (Alahmadi et al., 2022; Li et al., 2021). The constant growth of system logs generates vast and intricate provenance graphs, featuring many nodes and edges, along with a high average node de- gree. This complexity renders the graphs computationally intensive to manage and analyze. Additionally, although the rich semantic and contextual information within these graphs aids in understanding system behaviors, it also sig- nificantly increases computational overhead (Wang et al., 2022). Moreover, system logs are typically gathered con- tinuously, incorporating new entities and relationships fre- quently. This dynamic nature often results in an out-of- vocabulary (OOV) problem during event encoding, which affects the accuracy and effectiveness of the graph represen- tations and presents adaptability challenges.
To address these shortcomings, we propose a novel learning- based anomaly detection approach that more effectively cap- tures system behaviors from provenance graphs. Anomaly detection in dynamic graphs is crucial aspect of net- work analysis, especially in the intrusion detection sce- nario (Zeng et al., 2022). Existing frequency databases extract and record the frequency of each system event from logs, allowing a decoupled approach to handling provenance graphs (Hassan et al., 2019). Inspired by these databases, as well as learned storage techniques that optimize the storage and retrieval of large-scale graph data, our method begins by decoupling provenance graphs into individual system events along with their frequencies.
1. Introduction
Recently, Provenance-based Intrusion Detection Systems (PIDSes) that utilize provenance graphs for threat mod- eling gain widespread attention from both industry and academia (Rehman al., 2024: Cheng et al., 2023). Orig- inating from system audit logs, provenance graphs cap- ture detailed behaviors within operating systems through causally linked relationships (Gehani & Tariq, 2012). Prove- nance graphs model system activities by representing com-
'Equal contribution 'College of Computer Science and Technol- ogy, Zhejiang University, Hangzhou. China *College of Software Technology, Zhejiang University, Ningbo, China. Correspondence to: Zhenyuan Li <lizhenyuan @ zju.edu.en>>
We employ an embedding model to convert these events into vectors, which serve as inputs for a lightweight learning model. This model is trained to recognize patterns based on the frequency of occurrences, addressing the dynamic
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Case for Learned Provenance-based System Behavior Baseline
nature of system behaviors, As host behaviors evolve, the challenge of normality shifts, where previously learned be- haviors may not accurately classify new benign or malicious events, becomes evident. Our approach includes mech- anism specifically designed to manage the frequent intro- duction new entities and relationships in the graphs, ef- fectively tackling the out-of-vocabulae and normality shift challenges. By learning the distribution of vector frequen- cies that describe system behaviors, we establish baseline for normal system activity. This baseline is integrated into peg-propagation framework (Li et al., 2024a;b) for real- time anomaly detection. Our evaluations demonstrate the accuracy and adaptability of our method in anomaly path mining, showeasing significant improvements handling and analyzing provenance graphs for intrusion detection.
Wqgio Vex
memhelp.se
To Ra56.184.a By
niginx
PEjazamA
eraseme
Cron
grandom
PEjazamA
done.so
ineed
passwd
mlock
group
'imapd
13.55112.10
Mulicious Socket
Malicimux
Malicious
Malicimus Path
Henign Socket
Benign Procesa
Benign File
Beniga Path
Figure I. Nginx Backdoor Attack in Provenance Graph
Table I. Event Definitions
SRC(S)
DEST(d)
OPERATION(O)
We have developed prototype of our approach' that fea- tures an adaptive embedding method to address out-of- vocabulary elements and normality shifts in dynamic envi- ronments. This method preserves the essential semantic and contextual information in the provenance graphs and incor- porates lightweight machine learning model designed to efficiently learn behavioral patterns from large-scale prove- nance graph data in native streaming format. We utilized this model to establish a baseline for systems' normal be- haviors, which we then integrated with tag propagation framework to facilitate real-time detection. Our comprehen- sive evaluation, conducted on large-scale and open- open-source datasets, confirms the effectiveness and efficiency of our provenance graph embedding method. The results high- light its accuracy and adaptability in real-time anomaly path mining tasks, demonstrating its potential to significantly enhance anomaly detection capabilities.
Process
File
Write File; Create File
File
Process
Read File; Process Load
Process
Process
Start Process; End Process
Process
Network
Send Message
Network
Process
Receive Message
where (s, d. t) denotes an edge r from node to at time t, reflecting the causality direction. Table 1 lists detailed event flow mappings. Each event e = (s. r, d, t) E adds to the dynamic representation of the system, capturing the evolving nature of the provenance graph over time.
Figure shows local provenance graph from DARPA E3-CADETS² that describes nginx backdoor attack activ- ity (program, 2020). The attacker compromises a Ng nx web server by downloading a malicious payload and exe- cuting to gain root privileges. The ovals, diamonds, and rectangles represent provesses, sockets, and files, respec- tively. To emphasize malicious behaviors, highlight the nodes representing attack behaviors in red and depict the edges associated with these activities as dashed lines, while gray nodes and solid edges represent normal behaviors.
2. Provenance-based Intrusion Detection
2.1. Provenance Graph Definition
Provenance graphs describe the history of an operating sys- tem's execution (Gehani & Tariq, 2012), where nodes rep- resent system's entities, and edges capture the interactions between adjacent nodes. A provenance graph can be defined as G << V. R >, where V represents the set of nodes in G and R is the set of edges representing the relationship be- tween neighbor nodes. An edge (u, v) E R exists between two entities u and v (u, v E V) when their interactions are logged. The provenance graph is composed of sequence of events, each representing interaction between pair of adjacent nodes and the edge connecting them. Formally, the event streams can be aggregated into streaming prove- nance graph, represented as:
2.2. Frequence-based Anomaly Detection
Some anomaly detection approaches (Hassan et al., 2019; Xie et al., 2018) build event frequency databases (also known as baseline databases) to assess the suspiciousness of individual events and paths for detection and investigation. The frequency database stores the occurrence frequency of individual events in historical logs, where higher fre- quency indicates that the event is more likely to be normal. We assign regular score (Ie) to each event, representing the degree of normality of an event, as following:
Frequency of ets, F, d) T-
(2)
G ((s,r, : d.
(I)
Frequency of e(x, r, +)
https: https://github.ccm Addo/h// behavior_baseliae
Available
da Catrraaiiioaaaaappree---Coororro
2

---

The Case for Learned Provenance-based System Behavior Baseline
where Frequency of e(s, r, d) represents the number of the occurrence of event in the historical records where the triple (s, r, d) is identical, and Frequency of e(s, *) repre- sents the number of occurences of events that share the same source and relationship. The regular score (Tx) indicates the probability of a specific event occurring. If event e has never occurred, its regular score
C2. Graph Size and Complexity. Provenance graphs can become exceedingly large due to the complexity of modern software systems and the sophisticated na- ture of attacks such as Advanced Persistent Threats (APTs) (Ding et al., 2023). Managing such large graphs requires substantial memory and can force compro- mises between computational resources and the granu- larity of detection.
We illustrate an example of an Nginx backdoor attack in Fig- ure a behavior that has never been observed in the system logs. Since this attack has not occurred in historical logs, it
C3. Temporal Information. Other methods (Zeng et al., 2022: Wang et al., 2022) fail to fully leverage temporal information within system logs, resulting in suboptimal performance. Capturing and utilizing temporal patterns is essential for accurately identifying and understand- ing attack progressions.
is absent from the frequency database, leading to attack- related events, such as Network 25. 15.1159.6. 207 connect to Process Nginx, having very low regu- lar scores close to zero. In contrast, benign events similar to
this behavior, such as Process nginx connect to
C4. Coarse-grained Detection and Interpretability. Some approaches (Han et al., 2020; Wang et al., 2020; Manzoor et al., 2016) use coarse-grained detection strategies that may efficiently process data, but often produce alerts lacking sufficient detail for effective analysis, compromising their practical utility.
Network 205. 235. 65, may have appeared in his-
torical logs, resulting in high regular scores. However, if such a benign event is absent from the frequency database, this method becomes ineffective, highlighting its limited adaptability.
As the system logs accumulate, the methods relying on the baseline database struggle adapt to the normality shift problem, losing adaptability over time. Meanwhile, the accumulation of a large number of historical events in the databases results in memory storage pressure and query overhead.
C5. Adaptation to Unseen Benign Behaviors. Entities in provenance graphs, such as process names, file paths, and IP addresses, contain crucial semantic information for detection (Ding et al., 2023). The dynamic nature of system environments, where new entities and relation- ships frequently emerge, calls for adaptive embedding strategies to maintain accurate detection capabilities. Standard anomaly detection methods establish base- line from historical data, but often fail to recognize new benign behaviors. leading to false positives. While Graph Neural Networks (GNNs) offer a potential solu- tion by analyzing rich semantic contexts and complex relationships, their high computational demands limit the broader deployment.
2.3. Online Detection with Tag- Tag-propagation Framework
In order to handle the continuously generated event stream, several works (Hossain et al., 2017; Milajerdi et al., 2019) adopt tag-progg propagattion strategies to enhance the real-time capabilities of detection systems and their proficiency in handling streaming data. These strategies utilize tags to cache computation results and propagate them through the provenance graph based on causal attributes, ensuring that each event is checked only once. Therefore, tag- propagation- based methods can achieve real-time detection with high ac- curacy, minimizing redundant processing, and significantly reducing computational overhead. However, these methods with relatively simplified detection logic always struggle to adapt complex and novel attacks.
To sovle C2 and C5, we employ a learned storage method, utilizing a lightweight neural network model to capture the distribution of system behaviors in historical logs, en- abling efficient management of large and complex prove- nance graphs. Moreover, this embedding-based learning model possesses the generalization ability to alleviate the out-of-vocabulary (OOV) issue arising from newly intro- duced entities and relationships, as well as the normality shift induced by host behavior changes.
2.4. Practical Challenges
Despite their advances, existing PIDSes exhibit several lim- itations that impact their effectiveness in real-world applica- tions:
After that, we integrate this model with the tag- proopaaggttiin algorithm to process graph streams and enable real-time detection. Under this model, the causal order and temporal information between events are inherently captured through the tag propagation process, solving CI and C3. Mcanwhile, the anomaly scores of consecutive events are propagated and aggregated by the tag- eesprppagation algorithm to derive a path-level anomaly score, which facilitates real-time alerts
CI. Real-time Detection. Many existing systems (Hassan et al., 2019; Rehman et al., 2024) struggle with real- time detection, leading to significant delays in generat- ing alerts. These delays can be critical for preventing or mitigating ongoing cyber attacks (Li et al., 2021).
3

---

The Case for Learned Provenance-based System Behavior Baseline
are not present in the training corpus of the embedding models, as zero vectors. Formally, to encode event 6, {wi,, W22, ... Wiih, each word was is represented based on its presence in the system audit logs L. The event e; 's vector Ve, is as follow shows:
Offline Baseline Learning
Events
Medel Trainsg
Eatraction
Embhedling
Audit Logs
Frequency haved
Baseline
Fvant Vectors
Learned Baseline
Embed_s(ei]]
e E L, Embed w(w], if E L, e $ L.
Online Streaming Detection
Veg
Bventa
Vu
vector(0), otherwise,
Billodding
weeL
(3)
Realtime Event Stream
Event Veccors
Tag Propagation-besed
Anceally Path Mining
As Doc2Vec and FastText are capable of handling OOV words through specific encoding mechanisms. Their math- ematical formulations and underlying principles are pre- sented in Appendix B.2. In our experiments, we compared these models with the adaptive encoding method.
Figure 2. Approach Overview
while producing interpretable attack paths, thus addressing C4.
Dec2 can use infer_ vector () function to encode documents that do not appear in the training set. We treat an event as a document, which is the unit processed by Dec2 The inference process optimizes the event vector Ve to maximize its compatibility with the model's trained parameters, given the context of the words in 6ç- Formally, this can be expressed as:
3. Method
This section outlines the architecture of the provenance graph embedding method, representing the system behav- ior, and integrating with the proppagaattinn algorithm to conduct online streaming detection based provenance graphs. As shown in the overview of Figure 2, our method consists of two main phases: 1) an offline baseline learning phase, where a lightweight neural network model learns benign behavior patterns based on event frequencies to es- tablish learned baseline; and 2) an online streaming detec- tion phase, which integrates the learned baseline with the lng-rropagation algorithm to mine anomaly paths within real-time streams.
arg max II P((vv
(4)
tEc;
where represents tokens in the event e; and P(t|v, +) is the probability of token given the embedding v and the model parameters +. The optimization is typically performed through few iterations of the Stochastic Gradient Descent (SGD) algorithm, starting from random vector V.
As a subword-level embedding model, FastText could en- code each word into a targeted length vector using the sub- words. Each word is decomposed into a set of subwords S.e {81, 82, .... 8n). where each subword is substring of the word w. If w & L, its embedding vector v is com- puted as the average embeddings of its constituent subwords. Formally, this process can be expressed as:
3.1. Events Embedding
In the preprocessing of historical audit logs, we refine at- tributes such as process names, file paths, network IP ad- dresses, and interactions between entities, as illustrated in Table 1. Each event e is represented as a triple (s, r, d), and its regular score I' is computed using Equation 2. These events and scores are then aggregated to construct frequency-based baseline. Given event sequence E ={e1, .,,,,..,,,,,,,................., ), the goal is to process each event sequentially and encode it into fixed-dimensional vec- tor representation. This process enables downstream tasks such as graph representation learning. establishing a learned baseline, and anomaly detection. addition to encoding models, there are specific challenges and potential optimiza- tion methods for event encoding in provenance graphs. We have designed the following three mechanisms to address these issues.
V w
V
(5)
S
SESS
where |Sm|] is the cardinality of the subword set S... After obtaining the vector for each word in an event, we con- catenate them sequentially to form the completed vector representation of the event sentence.
Weight Embedding Long file paths may blur the distinction between vector representations of differ- ent regular score events. For example, the file path hhw.e//ossereeee htt.:/...///nnnn
and the file path / /home//ueeee /tt.euuer.... /malicious ciuus would be mapped to two very similar vectors, even though the regular score of the benign file is much higher than that of the malicious file.
Adaptive Embedding To address the vocabblay (OOV) problem, we encode unrecognized entities, which
4

---

The Case for Learned Provenance-based System Behavior Baseline
This makes it difficult for the subsequent learning model to capture the distinguishing data features. So assign differ- ent weights to each directory level, with directories closer to the file name receiving higher weights. The embedding of the file path is then calculated as the weighted sum of its directory levels. Formally, the embedding vector of a file name is defined as:
real-time detection by integrating with the tag- pag-propagatio algorithm. So select three popular regression models, namely, the Multilayer Perceptron (MLP) model, the Long Short-Term Memory (LSTM) model, and the Convolutional Neural Network (CNN) model.
In real-world scenarios, the model encounters unobserved events categorized as benign or malicious. Malicious events often feature unique entities and relationships, distin- guishing them from benign behaviors. Due to the mod- els' lack of exposure to malicious events during train- ing, it frequently misclassifies such events. To mitigate this issure, we construct relevant negative samples by re- placing subjects or objects in benign events with uncom- mon entities. For example, an uncommon network entity <10. 1.0.1.1.1 1..11.22.. replaces the common IP address in the be- nign event <128. 55. 12. 122, network connect, ngi nx>. Similarly, uncommon file paths and process names are used to create diverse negative samples. Then we assign regular scores to every negative samples, as follow- ing:
1 Σ W/ Σ We V.
V Fileename
(6)
where Ville.nome represents the embedding vector of the i-th element in the file path separated by slash, and wy is the weight. The weight w, of the i-th element in a file path =+1 is defined as uy; = log n-1- where n is the number of all elements in a file path. This weighting scheme is designed to reduce the influence of long file paths on the vectorization of file names, prioritizing the significance of directory levels closer to the file name.
One-hot Embedding Intuitively, ligher-dimensional vec- tors can encode more information, allowing the subsequent graph representation learning model to capture richer fea- tures. As the categories of relationships and entities are limited, as shown in Table 1, we can use one-hot encoding to represent the categories of entities and relationships, al- lowing more dimensions within the same vector sapce to be allocated for representing more critical features, such as process names and network IPs. To optimize storage space, can adopt 3-dimensional one-hot hot vector for the cate- gories of entities and an 8-dimensional one-hot vector for the types of relationships between entities. This approach reduces the dimensionality of individual event vectors and mitigates memory overhead. However, encoding these fea- tures as (1, 0, 0) can lead to conflicts with zero vectors used to encode OOV words, potentially reducing the predictive performance of the model. To avoid this issue, we adopt variant representation such as (0.5, -0.5, -0.5) for one-hot encoding.
Snegative [(Aevens)
(8)
where Aevent denotes the difference in event letters be- tween the negative samples and their corresponding benign counterparts. By incorporating such artificially constructed negative events, the model is better equipped to differentiate between benign and malicious events, thereby enhancing its predictive accuracy.
The encoding model maps an event sequence E en) into a series of vectors Ve (Ver, Vey....,, Ve,). J. where each event e; is represented by a vector Ve, E IR, with d denoting the dimensionality of the vector representation. Each event corresponds to a regu- lar score y/- E R, and the model outputs a predicted score ii E R. When applying three different models, we only add or modify specific layers unique to each model to flexibly construct the respective architectures. We parameterize a function fo using a model, which maps the input vector to the predicted score:
Ve, = on)- + v. + one-hot,(r) + one-hot, + va (7)
Despite this adjustment, one-hot vectors lack the capacity to capture meaningful information about relationships between entities, which is critical for understanding their structure and properties.
fo(ve.
(9)
To ensure that the predicted scores ÿ closely match the true regular scores yi. we adopt the Mean Squared Error (MSE), one of the most commonly used loss functions in regression tasks. The loss function Lois defined as:
3.2. Offline Baseline Learning
The task of learning the distribution of benign behaviors in provenance graphs is modeled as a frequency- based re- gression problem, where the goal is to predict the regular score of each event, which reflects the degree of abnormal- ity. To alleviate memory pressure and efficiently process real-time log streams, we employ a lightweight regression model that functions as a learned baseline and facilitates
1 Le
(1. 84)²
(10)
n
Using backpropagation, the model computes the gradient of the loss function with respect to the model parameters. The gradient of the loss with respect to the parameters of layer I
5

---

The Case for Learned Provenance-based System Behavior Baseline
is computed as:
once threshold-reaching events are processed, effectively shortening the system's is response time.
Oc
1+1
(h(
Oh (
V V
ay:
0h
(11)
We initialize the tags using our learned baseline model to predict the frequency of each event. We analyze each event in the log stream. Firstly, each event 6 is encoded into a vector representation Ve.. The trained machine learning model fo is then applied to compute the predicted regular score 9t- We use Io as the initial tag. In order to avoid excessive tags accumulation, only when the regular score of the event (T,,) is lower than the preset threshold and the source node does not have a tag, new tag will be assined and stored in the destination node. The regular score of the event r. propagates along the provenance graphs together with the initialized tags, resulting in the regular score of the path I'p according Equation 14. An alert will be triggered when Ip decreases below predefined threshold during propagation.
k=L
where & denotes the total number of layers in the neural net- work, i.e., the index of the output layer. And then the model
updates the parameters of the 1-th layer g()) via gradient descent to minimize the loss:
g() 8 7. L
(12)
where 17 is the learning rate.
As the regular scores of events range in (0, 1), we use the sigmoid function in the output layer to limit the prediction output of the model. The sigmoid function tacks its value in (0, 1) and reads
(x))
(13)
where x presents the input of the output layer.
4. Experiments
3.3. Online Anomaly Path Mining
4.1. Experimentanl Setting
We further conduct an anomaly path mining task, leveraging the embeddings learned from provenance graphs generated from benign system logs to establish learned baseline for normal system behaviors. This allows us to evaluate the effectiveness of our method for embedding provenance graphs in practical scenarios.
We utilize the TensorFlow library to construct neural net- work models, enabling flexible modifications of layer con- figurations implement various architectures such as MLP, LSTM and CNN. This approach facilitates the evaluation of different machine learning models in the provenance graph embedding and anomaly path mining task. Here, we evaluated the efficiency of various encoding and regression models, the accuracy of regression models in predicting reg- ular scores, the effectiveness of our approach in handling the real-time anomaly path mining task, and a comparison with state-of-the-ee provenance- trovenance-based intrusion detection sys- tems. We conducted all experiments on an Ubuntu 18.04.6 LTS server with an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2,40GHZ, GiB of memory, and three NVIDIA GeForce RTX 3090 GPUs.
Given each newly observed system event, the baseline model effectively and adaptively assesses the normality of the event, initializing a continuous regular score ranging from 0 to 1. Higher scores indicate more normal events, while lower scores suggest anomalies. Intuitively, while a single infrequent event might be coincidental, sequence of such events more likely indicative of an attack. Therefore, we employ the angpropaaattin algorithm to aggregate tags of causally related events, deriving the regular score of the path (T p), as the following shows:
TP (T.
(14)
Datasets In our experiments, we utilized datasets from the DARPA Transparent Computing (TC) dataset (tra, 2015.2), which contains millions of benign and hundreds of mali- cious events collected from platforms with diverse back- ground activities, providing provenance-rich data capturing system events and dependencies over time. This dataset includes a series of realistically simulated Advanced Persisi- tent Threats (APT), such as malware execution, privilege escalation, remote exploitation, and data extiltration. We pri- marily use the E3-CADETS dataset, constructing a training dataset with 1,042k system events and testing dataset with 26k events. Additionally, we demonstrate the adaptability of our method on other dataests in Appendix D.3.
'EP
where represents a decay factor, and le is generated by Equation 2. Since He ranges from 0 to 1, simply multiply- ing them cumulatively means that I'p will monotonically decrease, eventually falling below a specific threshold. The decay factor (a) (Hossain et al., 2020) can cause the normal score to increase when there are no anomalous events. The tag-proo propagation framework consists of four main stages: tag initialization, propagation, removal, and alert trigger- ing, tailored for anomaly path mining, to balance overhead and analytical capabilities. The detailed process of the tag- eegpprppagtiion framework is provided in the Appendix C. While reducing caching overhead and computational re- source, also ensures that alerts are triggered immediately
We categorize event encoding methods into two main types: one that encodes aut-of-vocabulayy (OOV) words as zero
6

---

The Case for Learned Provenance-based System Behavior Baseline
Table 2. Time of Eneoding
Table 3. Average Training Time of Models
Embedding Models
Training Set (s)
Testing Set (s)
Learning Models
Training Time (8)
Testing Time (s)
Word2Vec*
28.84
6.06
MLP
276.94
11.35
Voc2
30.78
6.41
LSTM
456.11
20.41
Vee2
488.24
122.23
CNN
2601.59
27.21
Fast
43.07
9.46
FastText
52.17
13,43
FastText(weight)
85.42
20.62
Table 2 presents the event encoding times for different en- coding models and methods. Similar results were obtained on other datascts, so we only display the results on the CADETS dataset as an example, showing in Table 8. We notice that if we directly encode the OOV words with zero vectors, it will accelerate the embedding process. In con- trast, encoding models tend to speed more time handling unknown words. For instance, in Doc2Vec, inferring the vector for an unseen event takes significantly more time compared to directly using pre-trained event vectors. In addition, we find that if we use one-hot encoding method, it will drastically reduce the encoding time. But we must remember that it only uses 214 dimensions to represent event, while other methods use 500 dimensions (except TERyBERT, which uses 312 dimensions).
Fas(Text(weight)
177.91
44.21
Fas/Text(one-hot)
14.2
3.16
(onthex(
43,41
10.53
Tiny BERT
5152.08
1338.71
vectors and another that does not apply special handling for OOV words. Since Word2 throws an exception when encoding OOV words, it can only be used for the first type. In contrast, the training corpus for TinyBERT is unknown, so it's only applicable to the second type. Among all the en- coding models that we employed, FastText demonstrated the best performance. Therefore, we further conducted experi- ments using FastText in combination with weight encoding and one-hot encoding to compare their effectiveness. In addition to the ablation experiments, we trained encoding models on system logs and mapped each event to a 500- dimensional vector. Apart from using the one-hot method to encode each event into a dimensniili vector, Tiny- BERT treats each event as a sentence and encodes it into 3 312-dimensional vector.
The encoding time of TinyBERT is significantly longer compared to other models, as they operate on entirely dif- ferent scales of computational complexity. TinyBERT based on the Transformer architexture, a deep neural net- work where every input token interacts with all other tokens in events. This results in substantial computational over- head during the encoding process. In contrast, other models such as Word2Vec are shallow neural networks with much lower computational complexity than TinyBERT. Overall, except for TinyBERT, the encoding time for each event using the other encoding models is in the microsecond range, which meets the requirements for processing real- time stream graphs and providing immediate response. Due to the inherent characteristics of provenance graphs and the real-time requirements of intrusion detection, complex encoding models are not suitable.
In training the baseline model for the regression task, we use the TensorFlow library to modify the regression models by adjusting the number of layers. Through controlled variable experiments, we ultimately employed the Adam optimizer with a learning rate of 0.001, and 200 training epochs for each model configuration. we evaluated the learned model's performance based on the prediction accuracy of event reg- ular scores. A prediction is considered true if the difference between the predicted regular score and the true score is less than a threshold of 0.2, which is selected because the frequencies of negative saples we constructed are generally below this value. For the anomaly path mining task, we use lath-level precision, recall, and Fl score as evaluation metrics. In the comparative experiments, due to the varying detection granularity across methods, we adopt node-level metrics for consistency.
Frequency Prediction We evaluated the regression perfor- mance of the baseline model using the model's prediction of the regular scores of events. We analyzed the predic- tion results on the testing dataset (Accuracy ((%) and for malicious events not present in the frequency dtabase (Accu- racy2(%)), indicating that regular scores of these events are expected be zero. Since we found that the event encod- ing methods have a significant impact on provenance graph embedding performance, while the effect of the learning models is relatively small, Table 4 presents the mean and standard deviations of the prediction for different encoding models and methods. More detailed results are provided in the Appendix D. Similarly, the training and testing time of the models was only dependent on the dimensionality of
4.2. Results
Events Embedding For the two types of encoding meth- ods, encoding OOV words as zero vectors and not applying special handling for OOV words, we use the asterisk (*) symbol to distinguish between them. Encoders marked with this symbol indicate the first encoding method.
7

---

The Case for Learned Provenance-based System Behavior Baseline
Table 4. Detection Accuracy of Single Events and Paths
Provenance Graph Embedding
Anomaly Path Mining Recall
Emhedding Models
Accuracy1($5)
Accuracy2 (%)
Precision
F1 Score
Word2Vee*
0.8886#0.0001
1.0000=0.0000
0.9545#0.0643
0.6852=0.1595
0.7809=0.0866
Doc2Vec"
1.9055=0.0058
1.0000=0.0000
0.9772+0.0004
0.7778=0.1571
0.8568#0.1055
Text
0.9058 0,058
1.0000=000000
0.9927=0.0052
1.0000=0,0000
0.9963#0.0226
FastTex((weigh))
0,9057=0.0011
0.5714=0.0117
0.946420.0758
0.3518=0.0262
0.5124
Fast "
0.8661
1.8809=0.1279
0.8302=0. 1322
0.5556=0.3175
0.6275#0.233 23331
Doc2Vec
0.6121 0992
0.2905=0.0135
0.0953#0.0710
0.1297=0.0524
0.0867#0.0651
FastText
0,9049=0. 0005
0.5952:0.0822
0.0467=0.0334
0.425
0.0694+0.0437
wweigh))
0.9057=0.0003
0.5619=0.0067
0,8493#0.2022
0.3333
0,471620.3357
Mnsteet((onchoo
0,9054=0.0000
0.5619=0,0243
0,4741=0.2373
0,2593+0. 2283
0.2734 20001
TinyBERT
0.9038=0.0014
0.1143=0.0117
0.6752#0.4591
0.0556=0.0485
0.0785=0.0871
the events. Table presents the average training and testing time when each event is encoded into 500-dimensional vector.
into the same dimensionality (except for the TinyBERT model and the one-hot embedding method), the testing time of three models increases. Moreover, reducing the dimen- sionality of event embeddings does not necessarily reduce training time. This is because lower-dimensional embed- dings may lose some semantic information, making it more difficult for the model capture data features and requiring more epochs to converge.
In general, special handling of OOV words by mapping them to zero vectors can improve the prediction performance of models, among which FastText demonstrated the best per- formance in this case. Since our processing unit is event, where each event consists of two entities and the interaction between them (i.e., adjacent nodes and the connecting edge in the provenance graph), malicious events typically contain a higher proportion of OOV elements. In contrast, unseen benign events tend to include fewer such elements. As a result, the model assigns lower regular scores to the former, enabling it to distinguish actual malicious behavior from unseen benign behavior, thereby reducing false positives. Therefore, for models that do not incorporate explicit han- dling of OOV words (as indicated by rows without asterisks in Table 4), although they achieve comparable performance on the overall testing set (AccuracyI% 1% column), their pre- dictions for actual malicious events are significantly less effective (Accurucy2% column). Meanwhile, prediction performance using the one-hot encoding method is the poor- est. The reason is that one-hot encoding fails to capture the inherent meaning of the categories of entities and relation- ships, resulting in a loss of semantic information during the encoding process.
Anomaly Detection Table presents the experimental results of integratiin the learned baseline model with the tag- propagation algorithm for the anomaly path mining task in real-time log streams. Our method enables the identification of anomalous paths and the generation of real-time alerts, thereby further reducing false positives.
In general, handling OOV words as zero vectors can signifi- cantly improve detection performance. This observation is closely related to the regression performance of the baseline model. The model predicts the regular score for each event and uses them as initial tags, which are subsequently propa- gated and aggregated following the information flow in the provenance graph. Among the evaluated methods, using the FastText model for events embedding and mapping OOV words to zero vectors performed best. The detection results achieved an F1 score that exceeded 99%.
The encoding methods that do not handle OOV words specif- ically, compared to the above methods, show little difference in the provenance graph embedding phase. However, the dis- tinction between the vectors of malicious and benign events is smaller, making it more difficult to detect malicious paths during the detection phase and leading to a higher rate of false positives.
In the absence of special handling for OOV words, the method of assigning weights to file paths can, to some extent, enhance the model's prediction performance. For long file path, if benign path and malicious path differ only in the final file name while sharing identical directories in the preceding segments, the two paths will be encoded into vectors that are relatively close to each other. By assigning greater weights to the directories towards the end of the path, this problem can be mitigated to a certain extent, thereby improving the model's 's prediction performance.
Although TinyBERT uses Transformer architecture and sur- passes traditional Natural Language Process (NLP) models in contextual modeling capability, the detection performance of using TinyBERT as the event encoder is suboptimal. This is due to the long-term and distributed nature of network attacks necessitates broader analytical scope beyond a
As Table 3 shows, the training time for the CNN model is much longer than other two models, and for events encoded
8

---

The Case for Learned Provenance-based System Behavior Baseline
5. Conclusion and Discussion
Table Node-Level Comparison with SOTA PIDSes
In this paper, we address the out-of-vocabulary (OOV) prob- lem caused by the constant emergence of new entities and relationships, and significant computational and memory overhead resulting from processing large-scale provenance graphs. To alleviate the issues, we propose an adaptive and scalable provenance-basee intrusion detection model. For real-time provenance graph streams, we use a lightweight neural model to assign a regular score to every event, com- bining with the tag- ang-propagation algorithm, to conduct efficient detection.
E3-CADETS
# of TPs
# of FNs
#f FPs
Fl score
Ours
32
1
69
0.4778
Nodoze
31
2
667
0.0885
ProvDetector
20
13
77
0.3636
Flash
7
25
6996
0.0019
Karios
23
10
119878
0.0003
E3-THEIA
# of TPs
# of FNs
# of FPs
Fl
Ours
12
5
46
0.3200
The prolonged apatio-temporal characteristics of APT at- tacks, along with the structural complexity and scale of provenance graphs, pose significant challenges to the widespread adoption of GNN-based models and transformer architectures for this task. We evaluated our method on mul- tiple datasets and conducted comparative analysis against SOTA approaches, demonstrating the efficiency, adaptabil- ity, and scalability of our method, as well its effectiveness in reducing false positives.
Nodoze
12
5
105
0.1791
ProvDetector
17
0.0000
Flash
2
15
23330
0.0002
Karios
11
6
10219
0.0021
E3-TRACE
# of TPs
# FNs
# FPs
Fl score
Ours
1448
0.0229
Nodoze
17
1
2689
0.0125
ProvDetector
5
13
44
0.1493
Flash
4
14
60484
0.0001
Karios
N/A
N/A
N/A
N/A
Acknowledgement
This work was supported in part by the National Key Research & Development Project of China (2023YFB3106800; the NSFC under No. U244120033, U24A20336, 62172243, 62402425, 62402418 and 62402419, the China Postdoctoral Science Foundation under No. 2024M762829, the Zhejiang Provincial Natural Science Foundation under No. LD24F020002, the Zhejiang Provincial Priority- Funded Postdoctoral Research Project under No. ZJ2024001, by the "Pioneer and Leading Goose" R&D Program of Zhejiang (2024C03288, 2025C02263), and by the Ningbo Yongjiang Talent Programme.
limited n-hop neighbors. We employ the tag propagation algorithm to aggregate information along long paths in the provenance graph, while requiring only minimal cache mem- ory.
Comparison We also provide a comparison with SOTA provenance- intrusion detection systems in Table 5, including Nodoze (Hassan et al., 2019), which uses the fre- quency database as a baseline, and Flash (Rehman et al., 2024) and Kairos (Cheng al., 2023), which adopt GNN- based approaches. Since different methods have different detection granularities, uniformly use node-level granu- larity for statistics.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
The results demonstrate the ad advantages of our approach in terms accuracy and the reduction of false positives. Mean- while, GNN-based methods not only incur high computa- tional and memory overhead when processing large-scale provenance graphs, but also struggle to support real-time intrusion detection tasks. Kairos (Cheng et al., 2023) adopts an approach based on time-window; however, due to the complex and prolonged spatio-temporal characteristics of APT attacks, a complete attack may span multiple disjoint time windows, thereby hindering the detection of the entire attack chain.
References
Darpa transparenteompptiing
2015.2.
URL
cransparent-comppte
Alahmadi, B. A., Axon, L., and Martinovic, I. 99% false positives: A qualitative study of SOC analysts' perspectives on security alarms. 3/st USENIX Security Symposium (USENIX Security 22), pp. 2783-2800, Boston, MA, August 2022. USENIX Association. ISBN

---

The Case for Learned Provenance-based System Behavior Baseline
978-1-939133-31-1 URL https::/www.usent
Joulin, A., Grave, E., Bojanowski, P., and Mikolov, T. Bag of tricks for efficient text classification, 2016. URL http//abs/6......11 01759..
org/conference/usee httpr//errreeeessssessssrr////// presentation/alammet
Bojanowski, P., Grave, E., Joulin, A., and Mikolov, T. En- riching Word Vectors with Subword Information. Trans- actions of the Association for Computational Linguis- tics, 5:135-146, 06 2017. ISSN 2307-387X. doi:
Kraska, T., Beutel, A., Chi, F. H., Dean, J., and Polyzotis, N. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD '18, pp. 489-504, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450347037. doi: 10. 10.144/31837133331100
10.1 a 00051.
Cheng, Z., Lv, Q., Liang, J., Wang, Y., Sun, D., Pasquier, T., and Han, X. Kairos:: Practical intrusion detection and investigation using whole-system provenance. arXiv preprint ar Xixv:2308.00034 2023.
Le, Q V. and Mikolov, T. Distributed representations of sen- tences and documents, 2014. URL https://arxits org/ abs 1405.4055
Li, Z., Chen, Q. A., Yang, R., Chen, Y., and Ruan, W. Threat detection and investigation with system-level provenance graphs: a survey. Computers Security, 106:102282, 2021.
Devlin, J. Bert: Pre-training of deep bidirectional trans- formers for language understanding. arXiv preprint arXiv: 1810.04805 2018.
Ding, H., Zhai, J., Deng, D., and Ma, The case for learned provenance graph storage systems. In Proceedings of the 32nd USENIX Conference on Security Symposium, SEC '23, USA, 2023. USENIX Association. ISBN 978-1- 939133-37-3.
Li, Z., Wei, Y., Shen, X., Wang, L.,, Chen, Y., Xu, H., Ji, S., and Zhang, F. Tags: Real-time intrusion detection with tag- pe--proaagttion-aaae
provenance graph alignment streaming events. arXiv preprint arXiv:2403. 12541, 2024a.
Gehani, A. and Tariq, D. SPADE: support for provenance au- diting in distributed environments, pp. 101-120. Springer- Verlag New York, Inc., 2012.
Li, Z., Wei, Y., Shen, X., Wang, L., Chen, Y., Xu, H., Ji, S., Zhang, F., Hou, L., Liu, W., Zhang, X., and Ying. J. Marlin: Knowledge-drine driven analysis of provenance graphs for efficient and robust detection of cyber attacks, 2024b. URL htwph:tt////et /arxivv.//iiv/////a///arer www.aawwwvv.oaa.ieaaaeooeooooooe .rgg /ttg////////////////////////ae// 220324033.2 12541.
Han, X., Pasquier, T. F. J., Bates, A., Mickens, J., and Seltzer, M. I. Unicorn: Runtime provenance-basee detec- tor for advanced persistent threats. In 27th Annual Net- work and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23-26, 2020. The Internet Society, 2020.
Manzoor, E., Milajerdi, S. M., and Akoglu, L. Fast memory- efficient anomaly detection in streaming heterogeneous graphs. In Proceedings of the 22nd ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 1035- 1044, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322. doi: 10. 00.114/999967222999977
Hassan, W. U., Guo, S., Li, D., Chen, Z., Jee, K., Li, Z., and Bates, A. 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, 2019.
Mikolov, T. Efficient estimation of word representations in vector space. arXiv preprint
2013
Milajerdi, S. M., Gjomemo, R., Eshete. B., Sekar, R., and Venkatakrishnan, V. Holmes: Real-time apt detection through correlation of suspicious information flows. In IEEE Symposium on Security and Privacy (SP), 2019. doi: 10.1 11911/P20199000000
Hossain, M. N., Milajerdi, S. M., Wang. J., Eshete, B., Gjomemo, R., Sekar, R., Stoller, S., and Venkatakrishnan, V. sleuth: Real-time attack scenario reconstruction from cots audit data. In 26th USENIX Security Symposium (USENIX Security 17), pp. 487-504, 2017.
program, D. T. Transparent Computing Engagement Data Release, 2020. URL htttps://githull com/ darpa- / rent cont--Comutiing/bllob Master/READoe mml.
Hossain, M. N., Sheikhi, S., and Sekar, R. Combating de- pendence explosion in forensic analysis using alternatiee tag propagation semantics. In 2020 IEEE Symposiun Security and Privacy (SP), pp. 1139-1155. IEEE, 2020,
Rehman, M. U., Ahmadi, H., and Hassan, W. U. Flash: A comprehensive approach to intrusion detection via prove- nance graph representation learning. In 2024 IEEE Sym- posium on Security and Privacy (SP), pp. 139-139, IEEE Computer Society, 2024.
Jiao, X., Yin, Y., Shang,
L., Jiang, X., Chen, X., Li, L., Wang, F., and Liu, Q Tinybert: Distilling bert for natural language understanding. 2020.
10

---

The Case for Learned Provenance-based System Behavior Baseline
Wang, Q. Hassan, W., Li, D., Jee, K., Yu, X., Zou, K., Rhee, J., Chen, Z.., Cheng, W., Gunter, C., and Chen, H. You are what you do: Hunting stealthy malware via data provenance analysis. 01 2020. doi: 10. 10.14722/mdss.2020 24167.
that can offer substantial advantages in storage and query efficiency (Kraska et al., 2018). Leonard (Ding al., 2023) applies learning-based indexing methods to the storage and querying of provenance graphs, simplifying both the storage and query process by optimizing the storage format and replacing traditional indexing methods with the Deep Neural Network (DNN).
Wang. S., Wang. Z., Zhou, T., Sun, H., Yin, X., Han, D., Zhang, H.. Shi, X., and Yang, J. Threatrace: Detecting and tracing host-based threats in node level through prove- nance graph learning. IEEE Transactions on Information Forensics and Security, 17:3972-3987, 2022.
Inspired by these works (Hassan et al., 2019; Ding et al., 2023; Kraska et al., 2018), introduce bearned-baseling based approach to overcome the challenges of PIDSes. This method adapts to various entities and events within real- world scenarios. Subsequently, we integrate an anomaly path mining algorithm into the tag pugoraaaattion framework, enabling efficiently process real-time event streams. This method optimizes the storage of raw provenance graphs, reduces caching overhead during real-time detection, and facilitates timely alerts.
Xie, Y., Feng, D., Hu, Y., Li, Y., Sample, S., and Long, D. Pagoda: A Hybrid Approach to Enable Efficient Real- time Provenance Based Intrusion Detection in Big Data Environments. IEEE Transactions on Dependable and Secure Computing, pp. 1-1, 2018. ISSN 1545-5971. doi: 10.1 1099/TDSC.201888875555
Zeng, J., Wang. X., Liu, J., Chen, Y., Liang, Z., Chua, T.-S., and Chua, Z. L. Shadewatcher:
B. Selected Models for Our Tasks
recommendatioo-guidee cyber threat analysis using system audit records. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 489-
B.1. Embedding Models
Word2Vec. Word2Vec (Mikolov, 2013) uses deep neu- ral networks with two hidden layers, continuous hag-of- words (CBOW) model create low-dimensional dense vector for each word, ensuring that semantically similar words have similar vector representations.
506. IEEE, 2022.
A. Related Work
A.1. Anomaly-based PIDSes
Doc2Vec. While bag-of-word: features have notable limi- tations, Doc2Vec (Le & Mikolov, 2014) represents each document as a dense vector. offering a solution to over- come the shortcomings of bag-of-words models.
As cyberattacks become increasingly rampant, provenance graphs are widely used in network malicious activity de- tection. The anomaly detection approaches (Rehman et al., 2024; Cheng et al., 2023; Wang et al., 2022; Zeng et al., 2022) train learning models that learn the benign behay- ior patterns based on the historical provenance graphs, and subsequently detect anomalous behaviors that deviate from these learned benign baseline. To extract semantic informa- tion during detection, some methods employ embedding techniques to encode various node attributes present in provenance graphs, such as process names, command line ar- guments, file paths, and IP addresses, into semantically rich feature vectors. Some methods also use machine learning models to generate contextual embeddings, thereby estab- lishing a baseline for benign behavior. For example, Shade- Watcher (Zeng et al., 2022) used TransR to learn a separate representation for a system entity conditioned on different relations and then used Graph Neural Network (GNN) to capture high-order connectivity. And Flash (Rehman et al., 2024) generated semantic and contextual embeddings using Word2 and GNN, respectively.
FastText. Unlike Word2Vec which feeds individual words into the neural network, FastText (Joulin et al., 2016; Bojanowski et al., 2017) breaks words into n-grams (sub-words) and then represents words as the sum of the n-gram vectors to enhance its embedding capability of words.
TenyBert. While contextual word embedding techniques like BERT (Devlin, 2018) effectively capture entity infor- mation, their high computational cost makes them ineffi- cient for large-scale provenance graph processing; there- fore, we adopt TinyBERT (Jiao et al., 2020) to perform the event embedding task.
B.2. Out-of-vocabulary Embedding
As Doc2Vec and FastText are capable of handling OOV words through specific encoding mechanisms.
Doc2Vec can use infer-vecten () function to encode documents that do not appear in the training set. We treat an event as sentence, which is the unit processed by Doc2Vec. The inference process optimizes the event vector V. to max- imize its compatibility with the model's 's trained parameters, given the context of the words e,. Formally, this can be
A.2. Learned Storage
The learned indexes, replacing traditional index structures with machine learning models, have been demonstrated

---

The Case for Learned Provenance-based System Behavior Baseline
expressed as:
each convolutional layer requires extensive matrix opera- tions and local feature extractions, and pooling layers con- tribute to additional computational complexity. A CNN is formed by several convolution and pooling operations, usually followed by one or more fully connected layers. While CNNs are traditionally applied to spatial data, they can be adapted to regression tasks by modifying the ar- chitecture and loss functions. In an MLP, one just has to compute two kinds of backpropagations: from output to fully connected layers and fully connected layers to fully connected layers. In traditional CNN, four new kinds of propagations have to be computed: fully connected layers to pool layers, pool layers to conv layers, cony layers to conv layers and conv layers to pool layers.
Ve, = arg max v
II P(tvv, ()
(15)
DECL
where É represents tokens in the event e; and v(tvv, Q) is the probability of token / given the embedding v and the model parameters O. The optimization is typically performed through a few iterations of the stochastic gradient descent (SGD) algorithm, starting from a random vector v.
As bebword-levell embedding model, FastText could en- code each word into a targeted length vector using the sub- words. Each word w is decomposed into set of subwords S.. = {81, 82, .... 8r1 J. where each subword is a substring of word w. I & L, its embedding vector Vu is computed as the average embeddings of its constituent subwords. For- mally, this process can be expressed
C. Tlgg-propagation Framework
1 SNO
Σ S
V
(16)
Here, we provide detailed description of the four stages of the tag nug-rropggation framework: tag initialization, tag propagation, tag removel, and alert triggering.
where |Sm.l is the cardinality of the subword set S... After obtaining the vector for each word in an event, we con- catenate them sequentially to form the completed vector representation of the event sentence.
Tag Initialization. We analyze each event in the log stream. Firstly, each event e; is encoded into vector representation Ve,- The trained machine learning model fe is then applied to compute the predicted regular score g.. We use d as the event frequency Fe. In order to avoid excessive tags accumulation, only when the regular score of the event (Tx) is lower than the preset threshold and the source node does not have a tag, a new tag will be
B.3. Learning Models
MLP. A Multi-Layer Perceptron (MLP) model is com- posed of fully connected layers that perform feature ex- traction and transformation. The input layer receives encoded event vectors, which are subsequently processed by the hidden layers. During training, the system employs the backpropagation algorithm to compute the gradients of the loss function with respect weights and biases. These parameters are iteratively updated via the gradient descent method to minimize loss.
assined and stored in the destination node.
Tag Propagation. We check whether there is a tag in the source node of each event. If so, we will update the regular score of the path (T)) according to Equation 14 and log the new tag result, while retaining the previous tag for subsequent propagation. When different tags converge on a node, we will retain the lowest regular score and its corresponding path, while archiving other paths for potential backtracking and attack reconstruction.
LSTM. Long Short Term Memory (LSTM) networks forward the data not only in a spatial direction, but also in a time-dependent direction, allowing the network to capture temporal dependencies more effectively. A key advantage of L.STM lies in their ability address the gra- dient vanishing problem often encountered by standard RNNs when processing long sequences. Utilizing mem- ory cells, LSTM retains long-term context information, making them particularly well suited for tasks requiring the modeling of extended dependencies. Despite these advantages, training LSTM can be more computation- ally demanding than training simpler architectures like
Tag Removal. To avoid the dependency explosion prob- lmm (Hossain et al., 2020), we use the dacay factor (a) to remove tags. If suspicious events are encountered during the propagation process, I gradually increases and is removed when it reaches a certain threshold. On the other hand, tags that have not been updated for long time will also be removed.
Alert Triggering. If suspicious events are continuously encountered, I'p will gradually decrease. Once it falls below a predefined threshold, an alert will be triggered to provide timely notifications. The triggered alert tag is also retained and propagated for several more rounds to ensure that subsequent suspicious activities can be effectively captured.
MLP, due to the complexity of their internal structure, which involves multiple gating mechanisms and memory updates.
CNN. Convolutional Neural Network (CNN) models are featured by varying groups of convolutional and pooling layers, which make them computationally intensive, as
12

---

The Case for Learned Provenance-based System Behavior Baseline
Table 6. Detailed Detection Results of Single Events and Paths
Provenance Graph Embedding
Anomaly Path Mining
Embedding Models
Learning Models
True Positives
Falsc Positives
Train Time(s)
Accuracy (())
(ccuracy2($6)
Precision
Recall
Score
MLP
302.22
87.03
100.00
67
0
1,0000
0. 0.6667
0,8000
Word2Vee'
LSTM
648 85
89.01
100.00
38
0.8636
0. 0,8889
0.8761
CNN
2120.37
90.54
100.00
598
1,0000
0.5000
0.6667
MLP
157
100.00
0.9775
Doc2Vee"
LSTM
288.44
90.55
100.00
87
0.9775
0 8889
0.9311
CNN
2148.61
90.54
100.00
84
0.9767
0.5556
0,7083
MLP
184.02
90.59
100.00
90
0,9890
1 1.0000
0.9945
FastText"
LSTM
289.03
100.00
CNN
2435.54
90.58
100.00
90
1,0000
1,00000
1,0000
MLP
170.80
90.56
57.14
978
1,0000
0.3333
0.5000
(weeihx(
LSTM
290.31
90.56
58.57
21
1,0000
0,3889
0,5600
CNN
2289.49
90.55
55.71
1722
330
0.8392
0.3333
0,4771
MLP
328.71
85.58
70.00
0.6471
0.2778
0,3887
LSTM
478.22
84.91
97.14
21
0.9545
0,3889
0.5526
CNN
955.17
89.34
97.14
104
0.8889
1,0000
0.9412
MLP
631.38
67.40
27.14
154
1460
0.0954
0.0556
0.0708
Doc2Vee
LSTM
1072.17
CNN
4543.2
47.22
30.00
271
1217
0.1821
0.1667
0.1471
MLP
298.32
90.54
48.57
47
9091
0.0051
0.7778
0.0102
FasTText
LSTM
317.98
90.42
68.57
379
0.0867
0.1667
0.1141
CNN
2457.85
0.0481
MLP
194.24
90.58
55.71
1,0000
0.3333
0,5000
FasTeenn(weigh))
LSTM
286.00
90.57
57.14
1,0000
0.3333
0.5000
CNN
2216.07
90.55
55.71
39
32
0.5493
0.3333
0.4149
MLP
216.71
90.57
$8.57
48577
69868
0.4101
0,5556
0.4719
FastTexttonehot)
LSTM
267.41
22824
CNN
740.50
90.52
57.14
70
249
0,2194
0.0000
0.0000
MLP
275.06
90.45
12.86
435
1,0000
0,0000
0,0000
Tiny BERT
STT
298.42
90.16
10.00
85
3183
0.0260
0.0556
0,0354
CNN
1838.12
90.45
11.43
8050
0,9996
0.1111
0,2000
D. More Results
considered a True Positive (TP) if contains least one ma- licious node from the ground truth. Conversely, if the alert path does not contain any malicious nodes, it is condidered False Positive (TP).
Here, we present more detailed experimental results. To pro- vide more comprehensive explanation of the experimental design and demonstrate the effectiveness of our method, Table 6 presents more detailed breakdown of the results shown in Table 4. In addition, we conducted parameter sensitivity analysis on the regression model, evaluated the model's adaptability on additional datasets, and performed ablation studies on the learned baseline.
D.2. Parameter Sensitivity
Empirically chosen default parameters are used for the em- bedding model, whereas optimal hyperparameters for the regression model are identified through controlled exper- iments. Table 7 illustrates the controlled experiments for tuning hyperparameters
D.1. Detection Results
the regression model, such as learning rate and optimizer. Figure represents the effects of the batch size and the dimension of the event embedding memory usage, computational efficiency, prediction ac- curacy, and et al. Table 7 shows that hyperparameter tuning has limited influence on the predictive performance of the regression model. Therefore, in the experiments reported in the main text, we use an LI kernel regularizer with a coefficient of 0.001, the Adam optimizer (learning rate 0.001), and the Mean Squared Error (MSE) loss function.
Different representation methods and learning models can affect the performance of provenance graph embedding and representation learning. As shown the Provenance Graph Embedding section of Table 6, we present the training time, testing time, and prediction accuracy of different methods and models. The meanings of Accuracy] (%) and Accu- racy2(%) are consistent with those described in the main text. Similarly, Table 6 also presents the performance of using embedded provenance graphs as a baseline the downstream task of anomaly detection, specifically in the Anomaly Path Mining section. In this case, an alert path is
To study the impacts of batch sizes, different batch sizes from 32 to 2048 to train MLP models on the E3-
13

---

The Case for Learned Provenance-based System Behavior Baseline
2002
3530
Table? Hyperparameters Tuning for Regression Models
Ahipe Tharmng Timets
-0300
5 6002
J5330
Kernal Regularizer
5000
2030
1530
Training Time(s)
Accuracy ((%)
Accuracy 2(%)
1030
)
176.51
90.59
100.00
502
More S10
1,(00001)
179.33
90.59
100.00
1.200.01
229.91
90.59
100.00
L1(0.0001)
174.01
90.59
100.00
(a) Batch Size
(b) Batch Size
L110,001)
278.39
90.59
100.00
L1(0.01)
123.69
35,86
0,00
5003
100
04
-rspartan Dowatoon - Kode SonM
kiineeal Timweed
leainng Rate
03-
6000
Devatbr100
Training Time(s)
Accuracy 1(%)
Accuracy 2(52)
Adam(0000001)
176.30
90,59
100.00
Adam100.00)
155.75
90.59
100.00
3063
Adam(1.01)
124,24
90.50
100.00
SGD(0.000 0001)
605.49
90,47
100.00
SGD(0.001)
244.00
90,51
100.00
SGD(0.01)
1298.20
90.56
100.00
(c) Embedding Dimension
(d) Embedding Dimension
Loss Function
Training Time(s)
Accuracy 1(%)
Accuracy 2(%)
Figure 3. Hyperparameters Tuning
MSE MAE
117.25
90.59
100.00
169.29
90.44
100.00
Huber
148.53
90.53
100.00
D.3. Adaptability Experiment
To evaluate the adaptability of our provenance graph embed- ding method, we tested the two best performing methods from Table 4 and Table 6 on other datasets, with the results presented in Table 8. Our method demonstrates good em- hedding performance and detection result on these datasets as well, indicating its adaptability.
CADETS dataset, using the FastText model to generate event embeddings. Figure 3a shows the maximum memory usage during training and the time cost of training models with different batch sizes. As the batch size increases, the memory usage during model training gradually rises. It remains relatively constant for batch sizes below 256, but exhibits a significant upward trend for batch sizes above 256. Mcanwhile, the training time decreases as the batch size increases, though the rate of decrease becomes pro- gressively smaller. Figure 3b shows the model size and the prediction accuracy. As the batch size increases, the model size remains unchanged, while the prediction performance shows slight flustuations, but remains largely consistent. In general, the batch size can be appropriately increased within the limits of the hardware capabilities.
D.4. Ablation Study
To assess the effectiveness of the learned baseline con- structed by our method compared to the traditional dababase baseline, we conducted an in-depth evalution of the predic- tion accuracy of the learned baseline and the frequency database in the ablation study, illustrated in Figure 4. Fig- ure 4a shows the proportion of correct predictions made by the learning model and the frequency database predic- tion model. We find that even using a 200-dimensional vector to represent each event, the deviation rate remains smaller than the frequency database. Figure 4b illustrates the storage of the database compared to the learning- baseline at different embedding dimensions. It is evident that the storage of the learning model is much smaller than the frequency database. When each event is encoded into a 500-dimensional vector space, the storage of the frequency database is approximately 28 times larger than the learning model. The results indicate that the learning-based baseline not only significantly optimizes storage but also outperforms the frequency database in terms of prediction accuracy for unseen events.
The dimension of event embeddings represents the complex- ity of encoding entities and their relationships within event. As shown in Figure 3c, the event encoding time ex- hibits a fluctuating upward trend with increasing embedding dimensions, and the storage space required for the encoded files increases linearly. The model prediction results of dif- ferent embedding dimensions are shown in Figure 3d. As the embedding dimension increases, the size of the learn- ing model rises approximately linearly. Meanwhile, the proportion of predictions with deviations smaller than the threshold gradually decreases. For dimensions less than 300 or greater than 500, the decrease in deviation is not obvious; whereas between 300 and 500 dimensions, the deviation decreases markedly. Therefore, encoding each event into a 500-dimensional space is considered more appropriate.
This discrepancy arises primarily from fundamental dif- ferences in their prediction mechanisms. The frequency database relies on the frequencies of historical events stored in its database for predictions. If an event is not stored in
14

---

The Case for Learned Provenance-based System Behavior Baseline
Table 8. Results Other Datasets
Provenance Graph Emnhediin
Anomaly Path Mining
Emnhedding Models
True Positive
False Positive
Dalasets
Training Timets)
Testing Time(s)
Accuracy 1(3)
Precision
Recall
Fl
Fast
0.9676
0.8866
E3-TRACE
weiggh)
57.21
2,73
91.76
1374
424
0.7642
0.8182
0.7903
Fast
207.6 60
8.63
86.73
123
1,0000
0.7692
0.8695
E3-THEIA
wai(Te))(eeight)
316.29
8.36
86.43
121
0.9837
0.6154
0.7571
Lranee Bood
250
400
150
000
290
400
592
000
(a) Comparison
(b) Comparison
Figure 4. Ablation Study
the database occurs infrequently, the prediction relied on the frequency database often exhibits considerable bias or is entirely inaccurate. While the database can provide frequency of known events, there is no effective strategy to predict the frequency of unseen or less frequent events in history.
15


Reviews:
[{"review_id": "5WEAXAOjFG", "reviewer": "Reviewer_q9G4", "summary": "The paper proposes a learning-based anomaly detection workflow for large-scale provenance graphs, addressing challenges like out-of-vocabulary elements and normality shifts in dynamic environments. It integrates dynamic graph processing with adaptive encoding to create compact embeddings, improving anomaly detection accuracy and adaptability. This approach is further enhanced with a tag-propagation framework for real-time anomaly path mining, significantly advancing provenance graph analysis for intrusion detection.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review efforts and insightful comments. We provide our responses to each specific issue in order.\n\nQ1: The paper feels more like a benchmark for a new application scenario, with limited methodological innovation.\n\nA1: This manuscript work towards to address an important and open research problem, namely, performing real-time provenance-based intrusion detection in an adaptive and scalable manner.\n\nSpecifically, the continuously generated audit logs in complex modern operating systems lead to the constant emergence of new entities and relationships, which causes out-of-vocabulary (OOV) problem. The presence of OOV words poses challenges to adaptability of the model. Furthermore, the complexity of attacks and their spatiotemporal persistence characteristics necessitate the detection of large-scale provenance graphs, leading to significant computational and memory overhead. **These challenges remain open problems in the field of cybersecurity, and existing works lack a general solution to address them.** In this paper, we propose an adaptive and scalability approach to reduce false positive and conduct efficient provenance-based intrusion detection.\n\nQ2: How many anomalous edges in the experiments are associated with OOV nodes? Could authors provide the ratio of anomalous nodes to normal nodes among all OOV nodes? If the majority of OOV nodes exhibit normal behavior, how would this affect performance?\n\nA2: We first refine the definition of OOV nodes mentioned in the comment. Each node may contain multiple words, and when a new node appears, it should be referred to as a node containing OOV words rather than simply an OOV node.\n\nAnomalous edges fall into three categories:\n(1) Both nodes are seen, but the edge represents an anomalous access;\n(2) One of the nodes contains OOV words.\n(3) Both nodes contain OOV words.\n\nIn the provenance graphs constructed from the *ta1-cadets-e3-official.json.1* log of the CADETS dataset, there are a total of 2,163,141 edges, among which 351 are anomalous.\nSpecifically, there are 2 edge of the first type, 30 edges of the second type, and 319 edges of the third type.\n\nIn the provenance graphs generated from the *ta1-cadets-e3-official.json.1* log of the CADETS dataset, there are a total of 114,969 nodes.\nAmong them, 2,372 nodes contain OOV words, accounting for 2.06% of all nodes.\nAmong these OOV-containing nodes, 833 are anomalous nodes, while 1,539 are normal nodes, with anomalous nodes comprising 35.11% of the total OOV-containing nodes.\n\nIndeed, most OOV-containing nodes exhibit normal behavior. However, these nodes generally share more common elements with the training dataset, whereas malicious nodes deviate more significantly from the behavioral patterns in the training dataset. \n**Since our unit of processing is an event (edge), the regression model assigns benign-like regular scores to events with normal nodes and much lower scores to event related to malicious nodes in most situations.**\nDuring real-time detection, these regular scores serve as initial tags for the tag propagation algorithm, propagating and aggregating along information streams to compute path-level regular scores. Alerts are triggered only for sequences of multiple suspicious events.\n\nQ3: I suggest renaming the Ablation Study section to Parameter Sensitivity.\n\nA3: We agree that Figure 3 (a/b/c/d) addresses parameter sensitivity, but we believe that Figure 3 (d/f) demonstrates how our approach to processing provenance graphs significantly improves performance in terms of storage and computational resource compared to traditional frequency databases.\nWe provide a comparison table against SOTA approaches in the Cadets dataset, showing that our approach effectively reduces false positives and minimizes manual analysis efforts. We observe comparable results in the Theia and Trace datasets.\n||TPs|FNs|FPs|F1-score|\n|-|-|-|-|-|\n|Ours|32|1|69|0.4776|\n|Nodoze|31|2|667|0.0885|\n|ProvDetector|20|13|77|0.3636|\n|Flash|7|25|6996|0.0019|\n|Kairos|23|10|119878|0.0003|\n\nIn the revised manuscript, since the detection granularity of our approach (path-level) differs from that of some SOTA works (graph-level or node-level), we have standardized the detection and comparison at the node level.\n**The results demonstrate the advantages of our approach in terms of accuracy and the reduction of false positive.**\nNodoze [NDSS'2019] and ProvDetector [NDSS'2020] are based on frequency databases, and the results highlight that our approach to processing and embedding provenance graphs can improve detection performance compared to traditional methods.\n\nQ4: There are some inconsistent format errors.\n\nA4: Thank you for your thoughtful review, we will carefully refine our paper to ensure that its format, content, and presentation remain objective, accurate, and well-reasoned.", "claims_and_evidence": "The proposed model claims that they can handle real-time dynamic graph problem (OOV words) and they surely through some ways (treat them as all-zero vectors or Doc2Vec) to well solve it.", "methods_and_evaluation_criteria": "The experimental settings, including datasets and evaluation criteria, are fair. The method consists of existing works, but the workflows make sense.", "theoretical_claims": "There’s no theoretical claim.", "experimental_designs_or_analyses": "The experimental settings, including datasets and evaluation criteria, are fair.", "relation_to_broader_scientific_literature": "The contributions lie in the application perspective, all used modules come from existing works.", "essential_references_not_discussed": "The references covering contributions are comprehensive and well-explained.", "other_strengths_and_weaknesses": "**Strength:**\n\n1) The paper is well-written.\n\n2) The experimental settings are fair. The whole benchmark is relatively comprehensive.\n\n3) The whole paper is well-organized and easy to follow.\n\n**Weaknesses:**\n\n1) The paper feels more like a benchmark for a new application scenario, with limited methodological innovation.\n\n2) I wonder how many anomalous edges in the experiments are associated with OOV nodes. This may help to explain why treating OOV words as zero vectors significantly boosts detection performance. Could authors provide the ratio of anomalous nodes to normal nodes among all OOV nodes? Additionally, if the majority of OOV nodes exhibit normal behavior (in terms of edges), how would this affect performance?\n\n3) I suggest renaming the Ablation Study section to Parameter Sensitivity, as Figure 3 doesn’t seem to effectively demonstrate an ablation study in this context.", "other_comments_or_suggestions": "There are some inconsistent format errors, like the title of Appendix A.2.", "questions_for_authors": "Please refer to Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3H7ehsfAiX", "reviewer": "Reviewer_kJxp", "summary": "This paper proposes a novel learning-based anomaly detection method that effectively embeds and analyzes large-scale provenance graphs. The approach integrates dynamic graph processing with adaptive encoding mechanisms, which facilitates compact embeddings, effectively addresses out-of-vocabulary (OOV) elements, and adapts to normal variations in dynamic real-world environments. The enhanced baseline is incorporated into a label propagation framework to enable real-time detection. The main contributions are threefold: (1) An adaptive event encoding mechanism is designed to dynamically generate event vectors by analyzing frequency characteristics in system logs; (2) A lightweight regression model is developed to capture normal event distribution patterns with low computational overhead; (3) An integrated framework combining offline learning and online detection is established, where the offline phase constructs behavioral baselines while the online phase performs anomaly path detection through direct comparison with real-time data streams.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review efforts and insightful comments. We provide our responses to each specific issue in order.\n\nQ1: The selection of learning models does not include a discussion on Transformer or GRU. It would be beneficial to discuss and compare more recent embedding models.\n\nA1: **Intrusion detection and threat analysis is a computationally intensive task with stringent real-time requirements.**\nDue to the complexity of attacks and their spatiotemporal persistence characteristics, it is necessary to detect large-scale provenance graphs.\n\nWe have try Transformers such as BERT and TinyBERT, due to the large dataset size (containing millions of unique system events), Transformers exhibited significantly higher processing times--as shown in Table 2, their event processing time is tens to hundreds of times that of traditional NLP models.\nGiven the real-time requirements of the detection process, we abandoned some advanced models due to computational and time constraints.\n\nMoreover, our experimental results (Table 4) indicate that the Transformer model fails to enhance detection performance in our task, primarily due to the unique characteristics of the provenance graph intrusion detection scenario. While the Transformer architecture surpasses traditional NLP models in contextual modeling capability, **the long-term and distributed nature of network attacks necessitates a broader analytical scope beyond a limited n-hop neighbors.**\nIn this context, simply applying SOTA models proves ineffective, leading to challenges regarding both effectiveness and scalability.\n\nQ2: It does not include a comparative study with some of the latest neural networks or embedding models.\n\nA2: The rationale for not utilizing the latest embedding models aligns with our previous discussion.\n**Given the unique characteristics of the provenance-based intrusion detection task and the prolonged, distributed nature of APT attacks, a broader graph structure must be collected and processed as contextual information.**\nIn this scenario, directly applying latest models often incurs substantial computational overhead, resulting in suboptimal efficiency and scalability.\nInstead, we adopt a tag propagation algorithm, which efficiently aggregates contextual information with minimal storage for tags, thereby facilitating computationally efficient detection.\n\n**As system logs accumulate over time, the provenance graphs inherently grow to a large scale.**\nThe Cadets dataset comprises 309k entities and 5,509k events, the Trace dataset include 505k entities and 910k events, and the Theia dataset contains 104k entities and 1,420k events. Specifically, the Cadets dataset spans approximately two weeks, generating 2.6GB of audit logs per day, whereas the Theia dataset, also covering two weeks, amounts to a total of 85GB. These figures underscore the substantial scale of provenance graphs.\nGiven the current state of technology, future analysis of log data from a single office computer may necessitate a high-performance server, posing significant challenges for real-world deployment.\n\nGNN-based models or other latest neural networks primarily concentrate on small graphs or local n-hop neighbors.\nHowever, **due to the prolonged spatiotemporal nature of attacks, attack chains typically span beyond the n-hop range.**\nAs a result, analyzing a larger graph structure becomes necessary, which increases the computational burden and leads to excessive resource consumption.\nSome methods, such as Flash [S&P'24] and Kairos [S&P'24], have employed advanced neural network models, including GNN and TGN, respectively.\nHowever, these models still face challenges in effectively solving the issues due to computational overhead.\nThey either reduce the training dataset or overlook critical graph information, which results in suboptimal training performance and poor detection outcomes.\nGiven these considerations, we did not employ the latest neural networks or embedding models for experiments, recognizing their inherent unsuitability for this task.\n\nQ3: There is a spelling error in the first paragraph of Section 3.2. Certain definitions need to be clarified, such as the notation L in the text. Additionally, the formulas for some embedding models should be properly introduced.\n\nA3: Thank you for your thoughtful review, we will carefully refine our paper to ensure that its format, content, and presentation remain objective, accurate, and well-reasoned. We will also add the necessary formulas to improve our paper.", "claims_and_evidence": "This paper validates its claims through a comparative analysis of various embedding models in prediction tasks and anomaly path mining.", "methods_and_evaluation_criteria": "The proposed evaluation metrics – particularly prediction accuracy and precision/recall/F1-scores for fault detection – demonstrate practical significance for the addressed problem.", "theoretical_claims": "The theoretical framework and mathematical formulations are fundamentally sound, offering valuable references for this research domain.However, the manuscript would benefit from explicit clarification of variable definitions in the equations, particularly regarding the specification of L and its operational semantics.", "experimental_designs_or_analyses": "A comparative analysis of multiple embedding models in terms of performance is conducted, with a detailed examination of their respective advantages, disadvantages, and underlying reasons.", "relation_to_broader_scientific_literature": "This paper provides a detailed review of previous contributions, highlighting their advantages and limitations. Based on the identified limitations, corresponding experiments are designed to address the existing issues.", "essential_references_not_discussed": "The selection of learning models does not include a discussion on Transformer or GRU.\nIt would be beneficial to discuss and compare more recent embedding models.", "other_strengths_and_weaknesses": "The experiments in the paper are comprehensive, with a strong emphasis on comparative studies. The proposed approach is tested on multiple models and datasets.  \nIt effectively integrates graph networks with adaptive encoding, achieving compact embeddings of elements.  \nHowever, it does not include a comparative study with some of the latest neural networks or embedding models.", "other_comments_or_suggestions": "There is a spelling error in the first paragraph of Section 3.2.\nCertain definitions need to be clarified, such as the notation L in the text.\nAdditionally, the formulas for some embedding models should be properly introduced.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "7RMqsIBDsR", "reviewer": "Reviewer_qnrS", "summary": "This paper proposes a learning-based anomaly detection method for provenance graphs, which are critical for cybersecurity. The approach decouples provenance graphs into system events, encodes them adaptively to handle out-of-vocabulary (OOV) elements and normality shifts, and trains lightweight regression models (MLP, LSTM, CNN) to predict event regularity scores. The experiment demonstrates high accuracy on DARPA datasets.\n\n## update after rebuttal\n\nThanks for the authors' rebuttal. I have raised my score since most of my concerns have been addressed. However, I'm still concerned about some new results during the rebuttal, specifically, the usability considering the low F1-score (0.4776) and how you deal with your 69 false positives. I hope the authors can address them in the revised paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review efforts and insightful comments. We provide responses to each specific issue.\n\nQ1: GNN-based anomaly detection & Temporal graph learning\n\nA1: GraphSAGE samples k-hop neighbors instead of traversing the entire graph. **APT attacks exhibit complex and prolonged spatiotemporal characteristics, requiring collecting a comprehensive provenance graph over an extended period for full capture**. Moreover, **provenance graphs are inherently complex, with multiple nodes and high average degrees, causing exponential information growth during propagation**.\n\nGAT employs a global attention mechanism, making it more suitable for small graphs rather than large-scale provenance analysis. Our datasets are large: Cadets (309k entities, 5,509k events), Trace (505k entities, 910k events), and Theia (104k entities, 1,420k events). Cadets generates 2.6GB of audit logs daily over two weeks, while Theia spans 85GB in the same period.\n\nTemporal graph learning models like TGAT or TGN encounter similar issues. While real-time detection is critical, **GNNs struggle with streaming data,** as time-windowed processing introduces latency. APT attacks spanning disjoint time windows further hinder GNNs from capturing the full attack chain.\n\nQ2: The selection and tuning of hyperparameters for the various embedding and regression models\n\nA2: We present the results of hyperparameter tuning for kernel regularizer. We observed similar patterns when tuning other hyperparameters like learning rates, loss functions and so on, finding that these hyperparameters had minimal impact on the model's regression performance. For embedding models, we used the default hyperparameters, adjusting only embedding dimensions, with results in Figure 3.\n||Training Time(s)|Accuracy 1(%)|Accuracy 2(%)|\n|-|-|-|-|\n|L2(0.0001)|176.51|90.59|100.00|\n|L2(0.001)|179.33|90.59|100.00|\n|L2(0.01)|229.91|90.59|100.00|\n|L1(0.0001)|174.01|90.59|100.00|\n|L1(0.001)|278.39|90.59|100.00|\n|L1(0.01)|123.69|35.86|0.00|\n\nQ3: Sufficient comparison experiments with other SOTA approaches\n\nA3: We provide a comparison table against SOTA approaches in the Cadets dataset, showing that our approach effectively reduces false positives and minimizes manual analysis efforts. We observe comparable results in the Theia and Trace datasets. In the revised manuscript, we standardize the different detection granularity to the node level.\n||TPs|FNs|FPs|F1-score|\n|-|-|-|-|-|\n|Ours|32|1|69|0.4776|\n|Nodoze|31|2|667|0.0885|\n|ProvDetector|20|13|77|0.3636|\n|Flash|7|25|6996|0.0019|\n|Kairos|23|10|119878|0.0003|\n\nQ4: Why are GNN-based methods excluded from comparisons? Could they be used as baseline for evaluation?\n\nA4: In the preceding table, Flash utilizes GraphSAGE, while Kairos employs TGN. Flash reduces training overhead by limiting dataset size and graph traversal, while Kairos uses a time-window approach for real-time detection. Besides the delay introduced by collecting the first time window, **attacks may extend across multiple non-contiguous time windows, resulting in incomplete detection of the attack chain**.\n\nQ5: How the approach scales with increasing data rates and graph sizes in a production environment?\n\nA5: For real-time data streams, the model assigns a regular score immediately upon an event arrival, maximizing detection efficiency. The initial tags propagate and aggregate along graph edges as described in Section 3.2. **Memory usage grows linearly, and the required cache is minimal.** To prevent dependency explosions, we implement tag removal conditions to limit the number of cached tags, effectively controlling memory overhead.\n\nQ6: How sensitive is the performance of your method to the choice of hyperparameters in the embedding and regression models and decay factor?\n\nA6: The results for embedding dimensions are presented in Figure 3 (c&d). Q3 presents experiments on hyperparameter adjustments for regression models. We manually fine-tuned the decay factor to achieve the best detection results. As it is not a major contribution, further details are omitted from the main paper.\n\nQ7: Can the approach handle gradual shifts in benign behaviors?\n\nA7: **Our approach effectively adapts to gradual changes in benign behaviors.** Since gradual shifts may introduce OOV words that are not present in the training set, we encode them as zero vectors to ensure all anomalies are detected.\nBenign nodes generally share more common elements with benign behaviors in the training set, whereas malicious nodes deviate more significantly from benign behavioral patterns. \n**Since our unit of processing is an event, the regression model assigns benign-like regular scores to events with normal nodes and much lower scores to events related to malicious nodes.**\nThese regular scores serve as initial tags for the tag propagation algorithm, propagating and aggregating along edges to compute path-level regular scores. Alerts are triggered only for sequences of multiple suspicious events.", "claims_and_evidence": "Most of the claims are well-supported.", "methods_and_evaluation_criteria": "The methodology is clearly motivated by the challenges inherent in processing large-scale and dynamic provenance graphs. The authors explore multiple embedding models and regression models to determine the best combination for predicting event \"regular scores\" that indicate normal system behavior. The evaluation is performed on realistically simulated DARPA datasets, which is a conventional choice in this field. The authors use accuracy metrics, which are also standard for anomaly detection.", "theoretical_claims": "The paper does not focus on deep theoretical derivations.", "experimental_designs_or_analyses": "The paper reports detailed timing and accuracy metrics, which answers most of the research questions. I also like that the paper presents impressive ablation studies on embedding methods and OOV handling approaches. \n\nHowever, it severely lacks comparison with other state-of-the-art provenance-based intrusion detection methods, such as those most related works the authors discuss. Besides, despite citing the scalability limitations of GNN-based methods, there have been more efficient GNNs (e.g., GAT, GraphSage), making it strange to exclude them arbitrarily from the comparison. In addition, the choice of $\\alpha$ and detection thresholds is also not evaluated.", "relation_to_broader_scientific_literature": "The work builds on frequency-based anomaly detection (Hassan et al., 2019) and tag propagation (Li et al., 2024). It specifically addresses gaps in handling OOV elements and dynamic system behaviors, which are underexplored in prior PIDS literature.", "essential_references_not_discussed": "* GNN-based anomaly detection: The paper critiques GNNs’ computational overhead but omits comparisons with scalable GNN variants like GraphSAGE (Hamilton et al., 2017) or GAT (Veličković et al., 2018).\n\n* Temporal graph learning: Methods like TGAT (Xu et al., 2020) could strengthen the handling of temporal information in provenance graphs (C3).", "other_strengths_and_weaknesses": "Strengths:\n* The paper addresses a critical problem in real-time intrusion detection.\n* The paper is well-written and well-structured; I enjoy reading it most of the time.\n* It has a practical focus on real-time detection and storage efficiency, which is important to real-world use.\n\nWeaknesses:\n* Some parts of the paper would benefit from a clearer exposition, particularly regarding the selection and tuning of hyperparameters for the various embedding and regression models.", "other_comments_or_suggestions": "Please refer to the questions below.", "questions_for_authors": "* Could the authors provide sufficient comparison experiments with other SOTA approaches?\n* Why are GNN-based methods excluded from comparisons? Could they be used as baseline for evaluation?\n* Could the authors elaborate on how the approach scales with increasing data rates and graph sizes in a production environment?\n* How sensitive is the performance of your method to the choice of hyperparameters in the embedding and regression models and decay factor?\n* Can the approach handle gradual shifts (not really unseen, but changing) in benign behaviors (e.g., software updates)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oHiGXAuNng", "reviewer": "Reviewer_Yzgk", "summary": "This paper proposes a new ML method for anomaly detection in provenance graphs. The results demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review efforts and insightful comments. We provide our responses to each specific issue in order.\n\nQ1: I would suggest adding experiments on transformers if possible.\n\nA1:  **Intrusion detection and threat analysis is a computationally intensive task with stringent real-time requirements.**\nDue to the complexity of attacks and their spatiotemporal persistence characteristics, it is necessary to detect large-scale provenance graphs.\n\nWe have try Transformers such as BERT and TinyBERT, due to the large dataset size (containing millions of unique system events), Transformers exhibited significantly higher processing times--as shown in Table 2, their event processing time is tens to hundreds of times that of traditional NLP models.\n**Given the real-time requirements of the detection process, we abandoned some advanced models due to computational and time constraints.**\nReferring to existing works, such as Flash [S&P'24], which uses Word2Vec for node encoding, and ProvDetector [NDSS'20], which employs Doc2Vec, we adopted similar NLP models and configurations, considering the need for efficient large-scale graph encoding.\n\nMoreover, our experimental results (Table 4) indicate that the Transformer model fails to enhance detection performance in our task, primarily due to the unique characteristics of the provenance graph intrusion detection scenario. **While the Transformer architecture surpasses traditional NLP models in contextual modeling capability, the long-term and distributed nature of network attacks necessitates a broader analytical scope beyond a limited n-hop neighbors.**\nIn this context, simply applying SOTA models proves ineffective, leading to challenges regarding both effectiveness and scalability.\n\nQ2: I would suggest the authors discuss more existing works on anomaly detection, e.g., CADE [USENIX'21].\n\nA2: We have supplemented a table of experimental results comparing with SOTA approaches, highlighting its advantages in accuracy and the reduction of false alarms.\nIn the revised manuscript, since the detection granularity of our approach (path-level) differs from that of some SOTA works (graph-level or node-level), we have standardized the detection and comparison at the node level.\n**The results demonstrate the advantages of our approach in terms of accuracy and the reduction of false positive.**\n\n**Dataset: E3-CADETS**\n||TPs|FNs|FPs|F1-score|\n|-|-|-|-|-|\n|Ours|32|1|69|0.4776|\n|Nodoze|31|2|667|0.0885|\n|ProvDetector|20|13|77|0.3636|\n|Flash|7|25|6996|0.0019|\n|Kairos|23|10|119878|0.0003|\n\n**Dataset: E3-THEIA**\n||TPs|FNs|FPs|F1-score|\n|-|-|-|-|-|\n|Ours|12|5|46|0.3200|\n|Nodoze|12|5|105|0.1791|\n|ProvDetector|0|17|91|0.0000|\n|Flash|2|15|23330|0.0002|\n|Kairos|11|6|10219|0.0021|\n\n**Dataset: E3-TRACE**\n||TPs|FNs|FPs|F1-score|\n|-|-|-|-|-|\n|Ours|17|1|1448|0.0229|\n|Nodoze|17|1|2689|0.0125|\n|ProvDetector|5|13|44|0.1493|\n|Flash|4|14|60484|0.0001|\n|Kairos|N/A|N/A|N/A|N/A|\n\nThank you for your thoughtful review, we will carefully refine our paper to ensure that its format, content, and presentation remain objective, accurate, and well-reasoned.", "claims_and_evidence": "The claims and assumptions as well as the evaluation metrics are reasonable to me.", "methods_and_evaluation_criteria": "The proposed method is well presented.", "theoretical_claims": "The paper does not have a theoretical claim.", "experimental_designs_or_analyses": "The experiment design is comprehensive in general and the results are impressive. I would suggest adding experiments on transformers if possible.", "relation_to_broader_scientific_literature": "This paper advances the field of ML-based anomaly detection, an important and practical domain.", "essential_references_not_discussed": "I would suggest the authors discuss more existing works on anomaly detection, e.g., CADE [USENIX'21].", "other_strengths_and_weaknesses": "The paper is well written.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors propose a learning-based approach for efficiently embedding and analyzing large-scale provenance graphs. Their method integrates dynamic graph processing with adaptive encoding techniques to generate compact embeddings capable of handling out-of-vocabulary (OOV) elements and distributional shifts in dynamic environments. 

One potential concern is the role of OOV nodes in the observed performance gains. Specifically, it would be helpful to know how many anomalous edges in the experiments are associated with OOV nodes. This insight could shed light on why representing OOV elements as zero vectors significantly enhances detection accuracy to further improve the paper.
Decision: Accept (poster)