ProvX: Generating Counterfactual-Driven Attack Explanations for Provenance-Based Detection

Weiheng Wu, Wei Qiao, Teng Li, Yebo Feng, Zhuo Ma, Jianfeng Ma, Yang LiuarXiv 2025 · arXiv · OpenReview

TL;DR

This paper introduces PROVX, a novel framework for explaining Graph Neural Network (GNN)-based intrusion detection systems that use provenance graphs. PROVX generates counterfactual explanations by identifying the minimal set of graph elements whose removal would flip the model's malicious prediction, offering crucial insights into attack patterns and enhancing model trustworthiness.

What Problem Does This Paper Address?

Advanced Persistent Threats (APTs) are a significant cybersecurity challenge due to their stealthy and complex nature. Provenance graphs, which represent system activities as nodes and their causal relationships as edges, are a powerful tool for detecting these threats, especially when analyzed by Graph Neural Networks (GNNs). However, GNNs are often "black boxes," meaning they can detect threats but cannot explain why they flagged something as malicious. This lack of explainability hinders security analysts' ability to trust the system, understand the attack, and respond effectively. Existing explanation methods often provide only factual evidence, failing to pinpoint the critical causal elements that truly drive the model's decision.

Methods

PROVX tackles the explainability problem by employing a counterfactual explanation approach. Instead of just identifying what features contribute to a prediction (factual explanation), PROVX asks: "What minimal changes to this malicious graph would make the GNN predict it as benign?"

The core of PROVX involves:

  • Provenance Graph Perturbation: PROVX learns a differentiable "edge mask" that represents potential modifications to the provenance graph. This transforms the discrete problem of graph editing into a continuous optimization task.
  • Counterfactual Reasoning: This is achieved through a dual-objective optimization framework:
  • Prediction Flip Loss: Encourages the model to change its prediction from malicious to benign.
  • Mask Distance Loss: Minimizes the number of changes made to the graph, ensuring the identified elements are truly critical and minimal.
  • Staged Solidification: To improve the precision and stability of explanations, PROVX incorporates a strategy that reinforces the importance of edges that have consistently shown a strong trend towards being included or excluded during the learning process. This helps to focus on core attack elements and reduce noise.

Datasets

The paper evaluates PROVX on two widely recognized APT datasets:

  • DARPA TC (Transparent Computing program): This dataset captures real-world attack scenarios.
  • DARPA OpTC (Operationally Transparent Cyber): This dataset provides a broad view of benign and malicious audit records.

The authors also mention using the "Cadets, Theia, and Trace" scenarios from DARPA TC.

Key Insights and Ideas

  • Structural Features are Key: The research highlights that the topological structure of provenance graphs is more crucial for distinguishing malicious from benign activities than semantic similarity of node attributes.
  • Counterfactuals Offer Deeper Insight: By asking "what if" questions (i.e., what if these elements were removed?), PROVX can uncover the truly critical causal links that drive a GNN's malicious prediction, going beyond mere feature attribution.
  • Minimal Perturbation is Crucial: The focus on finding the minimal structural subset that flips the prediction ensures that the explanation points to the most impactful and concise set of attack elements.
  • Feedback Loop Enhances Robustness: The paper demonstrates that explanations generated by PROVX can be used to retrain the detection model, making it more robust against adversarial attacks by learning to identify and counter evasion techniques.

Key Results

  • High Explanation Necessity: PROVX achieves an average explanation necessity (PN) of 51.59%, meaning that removing the identified critical edges flips the model's prediction from malicious to benign in over half of the test cases. This significantly outperforms existing state-of-the-art explainers.
  • Relevant to Real-World Attacks: PROVX demonstrates high accuracy in identifying critical graph structures relevant to real-world attacks, with an average accuracy of 0.8861 across datasets.
  • Outperforms Baselines: In comparative experiments, PROVX consistently outperforms other explainers (e.g., GradCam, DeepLIFT, GNN-LRP, PGExplainer, SubgraphX, GNNExplainer) on key metrics like Accuracy, Precision, Recall, and F1-score.
  • Efficient Overhead: PROVX exhibits low time and memory overhead, making it practical for deployment in real-world security environments, even without GPU support.
  • Improved Adversarial Robustness: The feedback loop mechanism, where PROVX explanations are used to retrain the detector, leads to significant improvements in detection performance against adversarial attacks (e.g., 20.1% increase in Accuracy, 43.7% in Precision).

Limitations and Future Work

  • Explanation Granularity: PROVX currently focuses on edge-granular interpretability for graph-level detection. The authors suggest future work could explore finer granularities like node-level or edge-level detectors.
  • Closed-Loop Framework Refinement: While a preliminary validation of a closed-loop "Detection-Explanation-Feedback" framework is presented, further exploration and refinement are planned.
  • Subgraph Partitioning: The paper notes that the subgraph partitioning method can sometimes lead to explanations that are important for model prediction but not necessarily the true root cause of an attack, suggesting this area could be improved.
  • Understanding Semantic vs. Structural: While structural features are emphasized, the paper acknowledges that semantic properties also play a role, and future work might explore more nuanced combinations.

Summary updated

Abstract

Provenance graph-based intrusion detection systems are deployed on hosts to defend against increasingly severe Advanced Persistent Threat. Using Graph Neural Networks to detect these threats has become a research focus and has demonstrated exceptional performance. However, the widespread adoption of GNN-based security models is limited by their inherent black-box nature, as they fail to provide security analysts with any verifiable explanations for model predictions or any evidence regarding the model's judgment in relation to real-world attacks. To address this challenge, we propose ProvX, an effective explanation framework for exlaining GNN-based security models on provenance graphs. ProvX introduces counterfactual explanation logic, seeking the minimal structural subset within a graph predicted as malicious that, when perturbed, can subvert the model's original prediction. We innovatively transform the discrete search problem of finding this critical subgraph into a continuous optimization task guided by a dual objective of prediction flipping and distance minimization. Furthermore, a Staged Solidification strategy is incorporated to enhance the precision and stability of the explanations. We conducted extensive evaluations of ProvX on authoritative datasets. The experimental results demonstrate that ProvX can locate critical graph structures that are highly relevant to real-world attacks and achieves an average explanation necessity of 51.59\%, with these metrics outperforming current SOTA explainers. Furthermore, we explore and provide a preliminary validation of a closed-loop Detection-Explanation-Feedback enhancement framework, demonstrating through experiments that the explanation results from ProvX can guide model optimization, effectively enhancing its robustness against adversarial attacks.
BibTeX
@misc{wu2025provx,
  author = {Weiheng Wu and Wei Qiao and Teng Li and Yebo Feng and Zhuo Ma and Jianfeng Ma and Yang Liu},
  title = {{ProvX: Generating Counterfactual-Driven Attack Explanations for Provenance-Based Detection}},
  year = {2025},
  eprint = {2508.06073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.06073},
}
Figure