The Case for Learned Provenance-based System Behavior Baseline

Thank you for your review efforts and insightful comments. We provide our responses to each specific issue in order.

Q1: I would suggest adding experiments on transformers if possible.

A1: Intrusion detection and threat analysis is a computationally intensive task with stringent real-time requirements. Due to the complexity of attacks and their spatiotemporal persistence characteristics, it is necessary to detect large-scale provenance graphs.

We 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. Given the real-time requirements of the detection process, we abandoned some advanced models due to computational and time constraints. Referring 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.

Moreover, 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. In this context, simply applying SOTA models proves ineffective, leading to challenges regarding both effectiveness and scalability.

Q2: I would suggest the authors discuss more existing works on anomaly detection, e.g., CADE [USENIX'21].

A2: We have supplemented a table of experimental results comparing with SOTA approaches, highlighting its advantages in accuracy and the reduction of false alarms. In 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. The results demonstrate the advantages of our approach in terms of accuracy and the reduction of false positive.

Dataset: E3-CADETS

Dataset: E3-THEIA

Dataset: E3-TRACE

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.

Thanks for your review efforts and insightful comments. We provide responses to each specific issue.

Q1: GNN-based anomaly detection & Temporal graph learning

A1: 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.

GAT 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.

Temporal 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.

Q2: The selection and tuning of hyperparameters for the various embedding and regression models

A2: 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.

Q3: Sufficient comparison experiments with other SOTA approaches

A3: 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.

Q4: Why are GNN-based methods excluded from comparisons? Could they be used as baseline for evaluation?

A4: 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.

Q5: How the approach scales with increasing data rates and graph sizes in a production environment?

A5: 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.

Q6: How sensitive is the performance of your method to the choice of hyperparameters in the embedding and regression models and decay factor?

A6: 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.

Q7: Can the approach handle gradual shifts in benign behaviors?

A7: 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. Benign nodes generally share more common elements with benign behaviors in the training set, whereas malicious nodes deviate more significantly from benign behavioral patterns. 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. These 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.

Thank you for your review efforts and insightful comments. We provide our responses to each specific issue in order.

Q1: 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.

A1: Intrusion detection and threat analysis is a computationally intensive task with stringent real-time requirements. Due to the complexity of attacks and their spatiotemporal persistence characteristics, it is necessary to detect large-scale provenance graphs.

We 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. Given the real-time requirements of the detection process, we abandoned some advanced models due to computational and time constraints.

Moreover, 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. In this context, simply applying SOTA models proves ineffective, leading to challenges regarding both effectiveness and scalability.

Q2: It does not include a comparative study with some of the latest neural networks or embedding models.

A2: The rationale for not utilizing the latest embedding models aligns with our previous discussion. 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. In this scenario, directly applying latest models often incurs substantial computational overhead, resulting in suboptimal efficiency and scalability. Instead, we adopt a tag propagation algorithm, which efficiently aggregates contextual information with minimal storage for tags, thereby facilitating computationally efficient detection.

As system logs accumulate over time, the provenance graphs inherently grow to a large scale. The 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. Given 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.

GNN-based models or other latest neural networks primarily concentrate on small graphs or local n-hop neighbors. However, due to the prolonged spatiotemporal nature of attacks, attack chains typically span beyond the n-hop range. As a result, analyzing a larger graph structure becomes necessary, which increases the computational burden and leads to excessive resource consumption. Some methods, such as Flash [S&P'24] and Kairos [S&P'24], have employed advanced neural network models, including GNN and TGN, respectively. However, these models still face challenges in effectively solving the issues due to computational overhead. They either reduce the training dataset or overlook critical graph information, which results in suboptimal training performance and poor detection outcomes. Given these considerations, we did not employ the latest neural networks or embedding models for experiments, recognizing their inherent unsuitability for this task.

Q3: 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.

A3: 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.

Thank you for your review efforts and insightful comments. We provide our responses to each specific issue in order.

Q1: The paper feels more like a benchmark for a new application scenario, with limited methodological innovation.

A1: 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.

Specifically, 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.

Q2: 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?

A2: 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.

Anomalous edges fall into three categories: (1) Both nodes are seen, but the edge represents an anomalous access; (2) One of the nodes contains OOV words. (3) Both nodes contain OOV words.

In 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. Specifically, there are 2 edge of the first type, 30 edges of the second type, and 319 edges of the third type.

In 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. Among them, 2,372 nodes contain OOV words, accounting for 2.06% of all nodes. Among 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.

Indeed, 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. 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. During 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.

Q3: I suggest renaming the Ablation Study section to Parameter Sensitivity.

A3: 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. 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, 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. The results demonstrate the advantages of our approach in terms of accuracy and the reduction of false positive. Nodoze [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.

Q4: There are some inconsistent format errors.

A4: 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.