Graph Neural Networks for Vulnerability Detection: A Counterfactual Explanation
Zhaoyang Chu Yao Wan Qian Li Yang Wu Hongyu Zhang Yulei Sui Guandong Xu Hai Jin






Vulnerability detection is crucial for ensuring the security and reliability of software systems. 
Recently, Graph Neural Networks (GNNs) have emerged as a prominent code embedding approach for vulnerability detection, owing to their ability to capture the underlying semantic structure of source code. 
However, GNNs face significant challenges in explainability due to their inherently black-box nature.
To this end, several factual reasoning-based explainers have been proposed. 
These explainers provide explanations for the predictions made by GNNs by analyzing the key features that contribute to the outcomes.
We argue that these factual reasoning-based explanations cannot answer critical what-if questions: “What would happen to the GNN's decision if we were to alter the code graph into alternative structures?” 
Inspired by advancements of counterfactual reasoning in artificial intelligence, we propose , a novel counterfactual explainer for GNN-based vulnerability detection. 
Unlike factual reasoning-based explainers, seeks the minimal perturbation to the input code graph that leads to a change in the prediction, thereby addressing the what-if questions for vulnerability detection.
We term this perturbation a counterfactual explanation, which can pinpoint the root causes of the detected vulnerability and furnish valuable insights for developers to undertake appropriate actions for fixing the vulnerability.
Extensive experiments on four GNN-based vulnerability detection models demonstrate the effectiveness of over existing state-of-the-art factual reasoning-based explainers.



<ccs2012>
   <concept>
       <concept_id>10011007.10010940.10011003.10011004</concept_id>
       <concept_desc>Software and its engineering Software reliability</concept_desc>
       <concept_significance>500</concept_significance>
       </concept>
 </ccs2012>


[500]Software and its engineering Software reliability




Graph Neural Networks for Vulnerability Detection: A Counterfactual Explanation
    Kunihito Ioka0000-0002-3517-1956
    April 29, 2024
===============================================================================





§ INTRODUCTION



Software vulnerabilities, which expose weaknesses in a program, present a significant risk to data integrity, user privacy, and overall cybersecurity <cit.>.
As of now, the Common Vulnerabilities and Exposures (CVE) <cit.> has reported tens of thousands of software vulnerabilities annually.
Thus, vulnerability detection, which aims to automatically identify potentially vulnerable code, plays a pivotal role in ensuring the security and reliability of software. 



Existing efforts on vulnerability detection primarily fall within two main categories: static analysis-based approaches <cit.> and deep learning-based approaches <cit.>.
Traditional static analysis-based approaches (e.g., SVF <cit.> and Infer <cit.>) rely on human experts to manually define specific rules for detecting vulnerabilities.
Recently, deep learning-based approaches, exemplified by pioneering works such as VulDeePecker <cit.> and Devign <cit.>, have made remarkable strides, largely attributed to their capacity to learn comprehensive code representations, thereby enhancing the detection capabilities across diverse vulnerabilities.
Among these approaches, Graph Neural Networks (GNNs) <cit.> have recently attracted substantial attention, owing to their capacity to capture intricate structural information of code, e.g., syntax trees, control flows, and data flows.

Despite the significant progress made by GNNs in vulnerability detection, existing detection systems suffer from the explainability issues due to the black-box and complicated nature of deep neural networks.
Given a predicted result, developers are often confused by the following question: “Why my code is detected as vulnerable?”
From our investigation, existing studies <cit.> on explainable vulnerability detection are typically factual reasoning-based explainers.
The core idea of these explainers is to identify key features in the input data (e.g., sub-graphs in the code graph) that contribute to the final predictions.
The selected features are commonly regarded as factual explanations,
as they derive from empirical input data and serve as factual evidence for particular outcomes.


Here, we contend that those factual reasoning-based explanations, which merely delineate the features or sub-graphs contributing to the identified vulnerability, are not convincing enough.
One reason is that developers remain uncertain about the actual influence of the code segments, which constitute the explanation sub-graph, on the detection result. 
In other words, the factual reasoning-based explanations cannot answer “What would happen to the detection system's decision if we were to alter these code segments into alternative structures?” 
This perspective of what-if is often associated with a human cognitive activity that imagines other possible scenarios for events that have already happened <cit.>.
This motivates us to develop
a novel paradigm for analyzing detected vulnerabilities in source code - what-if analysis.
In our cases, what-if analysis explores hypothetical code instances with alternative structures. 
This approach aims to identify potential changes that would  fix the vulnerability, thereby providing a better explanation of the root causes and factors contributing to its existence.


We use Figure <ref> as an example to illustrate the advantage of analyzing what-if in explaining vulnerability detection compared to factual reasoning-based explanations.
This example involves a heap-based buffer overflow vulnerability in the  project[<https://github.com/FFmpeg/FFmpeg>], reported by CVE-2016-10190[<https://www.cvedetails.com/cve/CVE-2016-10190>], which allows remote Web servers to execute arbitrary code via a negative chunk size in an HTTP response.
Specifically, this vulnerability arises from misuse of the  function for parsing  from HTTP responses into  format, without properly validating for negative values (4).
Then, a negative  can result in an erroneous calculation in the  function, producing a negative  for buffer operations (5). 
This negative  potentially triggers out-of-bounds write operations, ultimately leading to a heap buffer overflow (7 and 8). 
In this example, the vulnerability detection system parses the code snippet into a semantic code graph (e.g., Abstract Syntax Tree (AST), Control Flow Graph (CFG), Data Flow Graph (DFG), or Program Dependency Graph (PDG)).
Here, without loss of generality, we consider the parsed code graph as a DFG for better illustration.


The vulnerability detection systems employ GNNs to model the DFG and yield a prediction outcome that classifies the input code snippet as vulnerable.
To explain the prediction of “vulnerable”, the factual reasoning-based explanation identifies a compact sub-graph in the code graph (1, 5, 7, and 8) as the key feature that contributes to the detected vulnerability.
This allows developers to recognize segments 7 and 8, which involve buffer write operations (1 and 5 are not involved), as potentially vulnerable blocks.
However, the explanation provided is inadequate for guiding code rectification to alter the detection system's decision, leaving developers to manually check variables such as , , and  to identify the actual cause of the vulnerability.

In contrast, to investigate the context of vulnerability occurrences, what-if analysis proactively and iteratively explores diverse hypothetical code structures (e.g., (a), (b), (c), and (d)), by inputting each into the detection system to observe varied prediction outcomes.
Taking structure (a) as an example, it is evident that removing the data-flow dependencies 5→7 and 5→8, while retaining 6→7, leads to a prediction of “non-vulnerable”.
It suggests that calculating  at 5 may be a vulnerability source, while the computation of  at 6 does not contribute to the vulnerability.

Through iterative exploration for subsequent structures (b), (c), and (d), what-if analysis functions as an “optimization” process, eventually “converging” to a minimal change that alters the detection system's decision, i.e., only removing 4→5 in structure (d).
The minimal change highlights the data flow 4→5 as the root cause, which passes potentially incorrect , resulting in a miscalculation of  at 5 and in turn triggering the buffer overflow at 7 and 8. 
Consequently, developers receive an actionable insight, i.e., directly inspecting the value of  at 4 for potential errors.
Overall, we can conclude that the what-if analysis essentially simulates the interactions between developers and the vulnerability detection system during debugging, methodically identifying the root causes of the detected vulnerabilities and guiding developers to effective solutions.




Recent advances of counterfactual reasoning in artificial intelligence <cit.> shed light on the possibility of applying what-if analysis for GNN-based vulnerability detection.
A counterfactual instance represents an instance that, while closely similar to the original instance, is classified by the black-box model in a different class.
Thus, counterfactual reasoning aims to identify minimal changes in input features that can alter outcomes, thereby addressing the what-if questions.

Building upon this motivation, we propose , the first explainer to introduce counterfactual reasoning for enhancing the explainability of GNNs in vulnerability detection.
Given a code instance, aims to identify a minimal perturbation to the code graph input that can flip the detection system's prediction from “vulnerable” to “non-vulnerable”.
formulates the search problem for counterfactual perturbations as an edge mask learning task, which learns a differentiable edge mask to represent the perturbation.
Based on the differentiable edge mask, builds a counterfactual reasoning framework to generate insightful counterfactual explanations for the detection results.
Extensive experiments on four representative GNNs for vulnerability detection (i.e., GCN, GGNN, GIN, and GraphConv) validate the effectiveness of our proposed , both in terms of vulnerability-oriented and model-oriented metrics.


The key contributions of this paper are as follows.


  * To the best of our knowledge, we are the first to discuss the what-if question and introduce the perspective of counterfactual reasoning for GNN-based vulnerability detection.

  * We propose a counterfactual reasoning-based explainer, named , to generate explanations for the decisions made by the GNN-based vulnerability detection systems, which can help developers discover the vulnerability causes.

  * We conduct extensive experiments on four GNN-based vulnerability detection systems to validate the effectiveness of . 
Our results demonstrate that outperforms the state-of-the-art factual reasoning-based explainers.





§ BACKGROUND


In this section, we begin by introducing essential preliminary knowledge necessary for a better understanding of our model. Subsequently, we present a mathematical formulation of the problem under study in this paper.



 §.§ GNN-based Vulnerability Detection Model


Suppose that we have a set of N code snippets 
𝒟 = {C_1, C_2, …, C_N}, 
and each code snippet C_k is associated with a ground-truth label Y_k ∈{0, 1}, which categorizes the code snippet as either non-vulnerable (0) or vulnerable (1).
The goal of vulnerability detection is to learn a mapping function f(·) that assigns a code snippet to either a non-vulnerable or vulnerable label. 

Current deep learning-based approaches follow a fundamental pipeline wherein the semantics of the source code are embedded into a hidden vector, which is then fed into a classifier.
Recently, GNNs have been designed to capture the semantic structures of source code, e.g., ASTs, CFGs, DFGs, and PDGs.
Given a code graph G_k of C_k, GNN typically follows a two-step message-passing scheme (i.e., aggregate and update) at each layer l to learn node representations for G_k.

Firstly, GNN generates an intermediate representation 𝐦_i^l for each node i in G_k by aggregating information from its neighbor nodes, denoted by 𝒩(i), using an aggregation function: 

    𝐦_i^l = Aggregation({𝐡_j^l - 1| j ∈𝒩(i)}) ,

where 𝐡_j^l - 1 denotes the representation of node j in the previous layer. 
Subsequently, the GNN updates the intermediate representation 𝐦_i^l for each node i via an update function: 

    𝐡_i^l = Update(𝐦_i^l, 𝐡_i^l - 1) .

For a L-layer GNN, the final representation of the node i is 𝐡_i^L.
To obtain a graph representation 𝐡_k for the code graph G_k, a readout function (e.g., graph mean pooling) is applied to integrate all the node representations of G_k:

    𝐡_k = Readout({𝐡_i^L}) .

Finally, the graph representation 𝐡_k is fed into a classifier (e.g. Multi-Layer Perception (MLP)) followed by a Softmax function to calculate the probability distribution of non-vulnerable and vulnerable classes, as follows:

    P (c | G_k) = Softmax(MLP(𝐡_k)) ,

where P (c | G_k) is the predicted probability of the code snippet C_k that belongs to each class in {0, 1}, i.e., C_k is vulnerable or not.
The GNN model can be optimized by minimizing the binary cross-entropy loss between the predicted probabilities and the ground-truth labels, allowing it to learn from both non-vulnerable and vulnerable code instances in the training set.

As the model trained, in the testing phase, when presented with a code snippet C_K accompanied by its code graph G_k, the trained GNN model f(·) is employed to compute the predicted probability P(c | G_k) for each class. The resulting estimated label Ŷ_k for C_k is determined by selecting the class with the highest probability:

    Ŷ_k = _c ∈{0, 1} P (c | G_k) .



In this study, we investigate four widely used GNNs for vulnerability detection.
These GNNs employ various implementations of the Aggregation(·) and Update(·) functions to capture structural code information for vulnerability detection.

▹ Graph Convolutional Network (GCN) <cit.> generalizes the idea of convolutional neural networks to graphs.
It aggregates neighbor node representations by summing them and utilizes an MLP to update the aggregated node representations.

▹ Gated Graph Neural Network (GGNN) <cit.> utilizes a Gated Recurrent Unit <cit.> to control information flow through edges when updating the aggregated node representations.

▹ Graph Isomorphism Network (GIN) <cit.> introduces the concept of graph isomorphism to ensure permutation invariance.
It employs a graph isomorphism operator to update the aggregated node representations.

▹ GraphConv <cit.> incorporates higher-order graph structures at multiple scales to enhance GNN's expressive power.






 §.§ Model Explainability: The Problem

Suppose that we have a trained GNN model f(·) and its prediction Ŷ_k on the target code C_k represented by a code graph G_k. 
In this paper, we explore the explainability of GNNs within a black-box setting, recognized as a more challenging context for exploring model interpretability, where access to model parameters, training data, and gradients of each layer is unavailable.
In the black-box setting, we constrain the explainer to derive the prediction probability P(c | G_k) exclusively by querying the model f(·) with the code graph G_k as the input.

Under the aforementioned scenario, the factual reasoning-based explainers provide explainability by identifying key features that contribute to the model's prediction. 
For example, <cit.> propose to seek a compact sub-graph G_k^S that maintains the same prediction result as using the whole code graph G_k. They optimize the explainer by maximizing the probability of predicting the original estimated label Ŷ_k when the input graph is limited to the sub-graph G_k^S, defined as:


    max_G_k^S P(Ŷ_k | G_k^S) .

On the contrary, counterfactual reasoning provides explainability by generating counterfactual instances to address what-if questions. 
For the given code graph G_k, we generate its counterfactual instance by introducing a subtle perturbation to it, resulting in a new graph G̃_k. 
The perturbed graph G̃_k differs minimally from the original G_k but is classified in a different class, i.e., f(G̃_k)  f(G_k).
As a result, counterfactual reasoning aims to identify a minimal perturbation to G_k that alters the decision of the detection system.
We mathematically formulate the counterfactual reasoning problem as follows:

    min_G̃_k d(G̃_k, G_k) 
     , 
    s.t., _c ∈{0, 1} P (c |G̃_k) Ŷ_k ,

where d(·, ·) represents a distance metric that quantifies the differences between G̃_k and G_k, e.g., the number of edges removed by the perturbation. 




§ PROPOSED 


In this section, we propose a counterfactual reasoning-based explainer, named , for GNN-based vulnerability detection. 
comprises several key components: 
(1) Code Graph Perturbation.
employs a differentiable edge mask to represent the perturbation to the code graph, which transforms the discrete search task for counterfactual perturbations into a continuous learning task for edge masks. 
(2) Counterfactual Reasoning Framework.
Based on the differentiable edge mask, constructs a counterfactual reasoning framework and designs a differentiable loss function to make this framework optimizable, as illustrated in Figure <ref>.
(3) Counterfactual Explanation Generation.
After optimization for the counterfactual reasoning framework, generates counterfactual explanations for the detection system's predictions.
We will elaborate on each component of in the following. 



 §.§ Code Graph Perturbation

In our scenario, vulnerabilities often arise from incorrect or inconsistent structural relations in the source code, such as control and data flow flaws. Thus, for the given code graph G_k, we focus on perturbing its graph structures (i.e., edges), represented by the adjacency matrix 𝐀_k ∈{0, 1}^n × n, rather than perturbing the node features 𝐗_k ∈ℝ^n × d, where n is the number of nodes in G_k and d represents the feature dimension. Note that the code graph G_k is a directed graph, hence, 𝐀_k is unsymmetrical. 

One straightforward approach for generating counterfactual perturbations is through greedy search, which iteratively edits the code graph by removing or re-adding edges.
However, its practicality is limited by the vast size of the search space, leading to inefficiency <cit.>.
Although heuristic strategies can potentially explore the search space more efficiently, identifying the optimal counterfactual instance with precision is challenging. 
Specifically, there is no guarantee that the counterfactual perturbation identified is the minimal one necessary.


To overcome these limitations, inspired by prior work <cit.>, we adopt the edge masking technique.
This technique treats the searching for counterfactual perturbations as an edge mask learning task. 
The idea is that a perturbed graph G̃_k can be derived by masking out edges from the original code graph G_k, as follows:

    Ã_k = 𝐀_k ⊙𝐌_k ,

where Ã_k is the perturbed version of 𝐀_k, 𝐌_k ∈{0, 1}^n × n is a binary edge mask matrix, and ⊙ denotes element-wise multiplication. If an element 𝐌_k,ij = 0, it indicates the edge (i, j) is masked out in 𝐀_k. 
As directly learning the binary edge mask matrix 𝐌_k is not differentiable, we relax 𝐌_k to continuous real values, which is 𝐌̂_k ∈ℝ^n × n. Then, as illustrated in Figure <ref>(b), the perturbed adjacency matrix is generated by:

    Ã_k = 𝐀_k ⊙σ(𝐌̂_k) ,

where σ(·) represents the sigmoid function that maps the edge mask into the range [0, 1], allowing a smooth transition between the presence and absence of edges. 
As a result, starting from a randomly initialized edge mask matrix, 𝐌̂_k can be optimized via gradient descent.
This approach enables a quicker and more precise determination of the minimal counterfactual perturbation compared to search-based strategies.



 §.§ Counterfactual Reasoning Framework


We build a counterfactual reasoning framework to generate explanations for the predictions made by the GNN-based vulnerability detection system. The core idea of our proposed framework is to identify a minimal perturbation to the code graph that flips the detection system's prediction.
This is achieved by addressing a counterfactual optimization problem, which will be formulated in the following.

Suppose that we have a trained GNN model (whose weight parameter 𝐖 is fixed and inaccessible) and the code graph G_k for the target code snippet C_k.
We first apply the edge mask 𝐌̂_k on the code graph G_k to generate a perturbed graph, i.e., G̃_k.
Subsequently, as shown in Figure <ref>, we feed the original and perturbed code graphs into the GNN model to produce respective estimated labels:

    Ŷ_k = GNN(𝐀_k, 𝐗_k |𝐖)  , 
    Ỹ_k = GNN(Ã_k, 𝐗_k |𝐖)  .

where 𝐗_k denotes the features of the nodes in G_k.
To identify a minimal counterfactual perturbation, we learn the edge mask 𝐌̂_k based on the optimization objective of the counterfactual reasoning problem.
Specifically, we reformulate Eq. (<ref>) as follows:

    min_𝐌̂_k d(Ã_k, 𝐀_k) 
     , s.t., Ỹ_k Ŷ_k .

Here, the constraint part aims to ensure that the new prediction Ỹ_k is different from the original prediction Ŷ_k, while the objective part aims to encourage that the perturbed adjacency matrix Ã_k is as close as possible to the original adjacency matrix 𝐀_k.

Direct optimization of Eq. (<ref>) is challenging since both its objective and constraint parts are non-differentiable.
To address this, we design two differentiable loss function items to make the two parts optimizable, respectively.


To satisfy the constraint condition in Eq. (<ref>), we design a prediction loss item ℒ_pred to encourage the detection system towards producing a different prediction when the original code graph G_k is perturbed into G̃_k, as follows:

    ℒ_pred = P(Ŷ_k |Ã_k, 𝐗_k)  .

This loss item aims to minimize the likelihood that the perturbed graph G̃_k will maintain the original prediction Ŷ_k, thereby maximizing the chances of achieving an altered prediction outcome.


To address the objective part in Eq. (<ref>), we utilize binary cross entropy as a differentiable distance function to quantify the divergence between the original and perturbed adjacency matrixes, which is formulated as follows:

    ℒ_dist = BinaryCrossEntropy(Ã_k, 𝐀_k)  .

This distance function is chosen for its efficacy in measuring the difference between two probability distributions.
In our case, we consider the presence and absence of edges in the graph as binary classes, thus conceptualizing Ã_k as the estimated distribution of edges and 𝐀_k as the actual distribution.
During optimization, ℒ_dist ensures that Ã_k remains as close as possible to 𝐀_k, thus determining a minimal counterfactual perturbation to the code graph G_k.


We integrate the above two loss items into an overall loss function to optimize them collaboratively:

    ℒ = α·ℒ_pred + (1 - α) ·ℒ_dist ,

where α is a hyper-parameter that regulates the trade-off between the prediction loss item and the distance loss item. 
Higher α prioritizes changing the prediction outcome, potentially at the expense of a larger perturbation, whereas lower α focuses more on minimizing the perturbation.
Based on the overall loss function, we optimize the counterfactual reasoning framework using the gradient descent algorithm and the Adam optimizer <cit.>. 
Note that our framework operates in the black-box setting, indicating that the process of counterfactual reasoning focuses solely on updating the edge mask 𝐌̂_k to find the optimal perturbation while holding the underlying GNN model's parameters fixed.



 §.§ Counterfactual Explanation Generation

Utilizing an optimized counterfactual reasoning framework, we generate counterfactual explanations to explain the predictions made by the vulnerability detection systems.


After optimization, we obtain the optimal edge mask 𝐌̂_k^*.
In this mask matrix, higher values indicate their corresponding edges should be preserved while lower values indicate their corresponding edges should be removed to reverse the detection system's decision. 
To form the final explanation, we employ a hyper-parameter K_M to control the number of edges to be perturbed, i.e., taking the K_M edges with the lowest mask values.
Then, we obtain the optimal counterfactual perturbed graph G̃_k^* by removing the K_M selected edges and derive a sub-graph:

    G_k^S* = G_k - G̃_k^* .

As a result, the optimal counterfactual explanation takes the following form: 
the derived sub-graph G_k^S* is the most critical factor on the detection result, that if removed, then the code would not be predicted as vulnerable.


In real-world scenarios, developers may need diverse counterfactual explanations to explore and understand the context of the detected vulnerability.
To achieve this, we build a narrowed search space based on the sub-graph G_k^S*.
Within this space, we employ exhaustive search to methodically explore and filter various edge combinations in G_k^S* whose removal would alter the detection system's prediction. 
This process generates a set of diverse counterfactual explanations, each offering insights into the detected vulnerability from different perspectives.
Moreover, such diversity provides developers with multiple actionable options to address the detected vulnerability.



§ EXPERIMENTAL SETUP

In this section, we begin by presenting the dataset, the baseline explainers for comparison, and the implementation details. Subsequently, we introduce two types of evaluation metrics to quantitatively evaluate the effectiveness of our proposed .



 §.§ Dataset


Aligning with previous studies <cit.>, we conduct our experiments on the widely-used vulnerability dataset, Big-Vul <cit.>.
Linked to the public CVE database <cit.>, Big-Vul comprises extensive source code vulnerabilities extracted from 348 open-source C/C++ GitHub projects, spanning from 2002 to 2019.
It encompasses a total of 188,636 C/C++ functions, including 10,900 vulnerable ones, covering 91 various vulnerability types. 
Unlike other existing vulnerability datasets (i.e., Devign <cit.> and Reveal <cit.>) which only provide vulnerability labels at the function level, Big-Vul offers more detailed, statement-level code changes derived from original git commits. These code changes for fixing vulnerabilities are crucial in our study. They enable us to build ground-truth labels for quantitatively evaluating the quality of the generated explanations (see Section <ref>).

To enhance the dataset's quality, we follow the cleaning procedure proposed by <cit.>.
Specifically, we remove comment lines from the code and ignore purely cosmetic code changes (e.g., changes to whitespace).
We also exclude improperly truncated or unparsable code snippets. 
Additionally, following the practices of previous research <cit.>, we perform random undersampling for non-vulnerable code snippets to obtain a balanced dataset. 
In this work, we employ an open-source code analysis tool, Joern <cit.>, to parse each code snippet into a PDG, which serves as the input for the GNN-based detection model.
PDG is a commonly used graph representation for code in vulnerability detection research <cit.>, which takes code statements as nodes and control-flow or data-flow dependencies as edges.
Finally, the dataset is randomly divided into training, validation, and testing sets with a ratio of 8:1:1.
Note that the explainers only generate explanations for the detection model's predictions on the test set.



 §.§ Baselines

To provide a comparative analysis, we investigate six prominent factual reasoning-based GNN explainers as our baselines:


    
  * GNNExplainer <cit.> seeks a crucial sub-graph by maximizing the mutual information between the original GNN's prediction and the sub-graph distribution. 
    
  * PGExplainer <cit.> learns an edge mask predictor based on the mutual information loss used in <cit.>. It accesses the training set to train the edge mask predictor.
    
  * SubgraphX <cit.> employs the Monte Carlo tree search algorithm <cit.> to efficiently identify important sub-graphs with a node pruning strategy.
    
  * GNN-LRP <cit.> decomposes the GNN's prediction scores into the importance of various graph walks using a higher-order Taylor decomposition and returns a set of most important graph walks as an explanation.
    
  * DeepLIFT <cit.> is another decomposition-based explainer but originally designed for image classification. 
    A previous work <cit.> extends it to explain GNN models, denoted as DeepLIFT-Graph.
    
  * GradCam <cit.> is a popular gradient-based explainer for image classification. It backpropagates the prediction scores to compute the gradients, which are then used to approximate the input importance. The previous work <cit.> adapts it for explaining GNN models, denoted as GradCam-Graph.


For the hyper-parameters of these baseline explainers, we adopt the implementation provided by previous research <cit.>. 
Note that PGExplainer, GNN-LRP, DeepLIFT-Graph, and GradCam-Graph do not operate in the black-box setting, as they require access to model parameters, training data, and gradient information of GNNs.



 §.§ Implementation Details

Our implementation comprises two main components: training GNN-based vulnerability detection models and generating explanations for the detection model's predictions.



  §.§.§ GNN-based Vulnerability Detection

In our experiments, we reimplement four vulnerability detection models employing different GNN cores (i.e., GCN, GGNN, GIN, and GraphConv). 
Each detection model adopts a two-layer GNN architecture with a hidden dimension of 256, followed by graph mean pooling to derive graph-level representations.
The graph-level representations are then input to a two-layer MLP classifier for vulnerability detection. 
In the model, we utilize GraphCodeBERT's token embedding layer <cit.> to initialize node features for the input code graph.
ReLU activation functions are used after each layer, except for the final one, to introduce non-linearity. 
Based on the binary cross-entropy loss, we train each detection model using the Adam optimizer <cit.> for 50 epochs, with a learning rate of 0.005 and a batch size of 64.
As shown in Tabel <ref>, following prior research <cit.>, we evaluate the performance of the reimplemented detection models using Accuracy, Precision, Recall, and F_1 score.
The results show that all four detection models achieve an Accuracy over 70%, a Precision over 55%, a Recall over 40%, and an F_1 score over 50%. 
Among them, GCN excels in Precision, while GIN leads in Accuracy, Recall, and F_1 score.
Overall, these models exhibit similar performance with high Precision and relatively low Recall. 



  §.§.§ Explanation Generation

For the implementation of our proposed , we train it using Adam to minimize the loss function described in Section <ref> for 800 epochs at a learning rate of 0.05. 
Note that, for each code snippet sample, is trained individually to explain the detection model's prediction.
We set the hyper-parameter K_M to 8 by default and use the same K_M value to control the size of the explanation sub-graphs generated by the factual reasoning-based explainers for fair comparison.
In addition, in Section <ref>, we conduct a parameter analysis on the hyper-parameter α, exploring values from 0.1 to 0.9 to understand its influence on 's performance.
It should be noted that the explainers aim to provide explanations by identifying the critical factors that contribute to the detected vulnerability. Thus, it is meaningless to explain the non-vulnerable code snippets and unfair to explain the code snippets that are incorrectly detected as vulnerable. As a result, we only consider explaining vulnerable code snippets that are correctly detected.







 §.§ Evaluating the Explainability


In this section, we introduce two types of metrics to evaluate the quality of the generated explanations quantitatively.



  §.§.§ Vulnerability-oriented Evaluation Metric


Evaluating counterfactual explanations in code is challenging due to the difficulty in obtaining standardized ground truth. 
Previous research <cit.> has relied on manual labeling for evaluation, which is costly, not easily scalable, and lacks standardization.
Fortunately, the Big-Vul dataset mitigates this issue by providing detailed statement-level fixes within git commits, which accurately reflect the changes addressing vulnerabilities. 
We utilize these commits to construct standardized ground-truth labels for our generated counterfactual explanations. 

In the vulnerability-oriented evaluation, following methodologies established in vulnerability detection research <cit.>, we adopt the statements that are deleted or modified in the commit (marked with “” signs) as ground-truth labels.
Specifically, we extract all the statements from the vulnerable version of the code to build a binary ground-truth vector, denoted as S = [s_1, s_2, …, s_r], where s_i = 1 indicates the i-th statement is deleted or modified in the fixed version, and s_i = 0 otherwise.
Correspondingly, we construct a binary explanation vector Δ = [δ_0, δ_1, …, δ_r], where non-zero values in Δ represent the corresponding statements included in the generated explanation sub-graph. 
The comparison of Δ with the ground-truth vector S allows for a quantitative evaluation of how accurately the generated explanations identify critical statements associated with the vulnerability.

Consider a given set of M vulnerable code snippets denoted as {C_1, C_2, …, C_M} for evaluation.
For each code snippet, an explanation is deemed correct if it encompasses the deleted or altered statements. Consequently, we compute the Accuracy score by determining the percentage of accurate explanations among all generated explanations.
Moreover, we calculate the Precision and Recall scores for each code snippet by comparing the explanation vector Δ and the ground-truth vector S:

    Precision = ∑_i=1^r s_i ·δ_i/∑_i=1^r δ_i ,   Recall = ∑_i=1^r s_i ·δ_i/∑_i=1^r s_i .

In our scenario, Precision measures the proportion of statements in the explanation that are relevant and accurately pertain to the vulnerability. On the other hand, Recall measures the proportion of ground-truth statements that are accurately included in the explanation. 
Additionally, we compute F_1 as the harmonic mean of the two scores to evaluate the overall performance. The formula for F1 is given as follows:

    F_1 = 2 ·Precision·Recall/Precision + Recall .

Finally, we calculate the average scores of Precision, Recall, and F_1 across all code snippets.



  §.§.§ Model-oriented Evaluation Metric


The vulnerability-oriented evaluation metrics primarily focus on assessing the consistency between the generated explanations and the root causes of the detected vulnerabilities. 
However, these metrics cannot quantify to what extent the generated explanations really influence the detection system's decisions.
Thus, inspired by previous research <cit.>, our model-oriented evaluation borrows insights from causal inference theory and introduces Probability of Necessity (PN) <cit.> to fill this gap. 
Intuitively, for an explanation E that is generated to explain prediction P, if E does not happen then P will not happen, we say E is a necessary explanation for supporting the prediction P. 
The core idea of PN is that: if we imagine a counterfactual world where the explanation sub-graph G_k^S did not exist in the original code graph G_k, then whether the corresponding code snippet C_k would not be detected as vulnerable? 
This is critical for understanding the causal impact of the explanations on the prediction outcomes.
Following this idea, we define PN as the proportion of the generated sub-graph explanations that are necessary to influence the detection system's predictions, as follows:

    PN = 1/M∑_k^M pn_k ,   where pn_k = 
            
            1,    if Ŷ_k^'Ŷ_k , 
    
            0,    else ,

where Ŷ_k^' = max_c ∈{0, 1} P (c | G_k - G_k^S) represents the prediction result for the code snippet C_k when the explanation sub-graph G_k^S is removed from the original code graph G_k.
If removing G_k^S changes the prediction Ŷ_k, the explanation is considered necessary. 




§ EXPERIMENTAL RESULTS

To evaluate the performance of our counterfactual reasoning approach, we address the following Research Questions (RQs):

    
  * RQ1: Vulnerability-oriented Evaluation. 
    How well does perform in comparison with state-of-the-art factual reasoning-based explainers in identifying the root causes of the detected vulnerabilities?
    
  * RQ2: Model-oriented Evaluation. 
    How well does perform in comparison with state-of-the-art factual reasoning-based explainers in generating explanations that really influence the detection model's decision?
    
  * RQ3: Influence of Hyper-parameter α. How do different settings of the trade-off hyper-parameter α impact the performance of ?







 §.§ RQ1: Vulnerability-oriented Evaluation


One of the key objectives of explainers in our context is to accurately identify the root causes of detected vulnerabilities. 
The effectiveness of our proposed , in comparison to factual reasoning-based explainers, is quantitatively showcased in Table <ref>, which reports the vulnerability-oriented evaluation results on four GNN-based detection models: GCN, GGNN, GIN, and GraphConv.
These results reveal that outperforms the baseline explainers in most scenarios, demonstrating the effectiveness of our counterfactual reasoning approach. Across the four GNN-based detection models, achieves average improvements of 
24.32%, 12.03%, 28.22%, and 14.29% in Accuracy,
7.93%, 4.43%, 14.36%, and 2.72% in Precision,
32.28%, 12.47%, 33.51%, and 18.19% in Recall,
17.10%, 7.18%, 19.71%, and 8.22% in F_1 score
over the factual reasoning-based explainers.

Among all baseline explainers, the perturbation-based GNNExplainer exhibits relatively good performance by directly searching for a crucial sub-graph that significantly contributes to the vulnerability detected by GNNs. 
Besides, the decomposition-based methods (i.e., GNN-LRP and DeepLIFT-Graph) directly decompose the detection model's predictions into the importance of edges in the code graph and select the most important edges as an explanation, resulting in slightly inferior performance compared to GNNExplainer.
However, the other two perturbation-based methods (i.e., PGExplainer and SubGraphX) and the gradient-based GradCam-Graph method perform relatively poorly. 
This is because PGExplainer's mask predictor may suffer from the distribution shift between the training and test sets, while SubGraphX's node pruning strategy may be not compatible with our scenario of perturbing edges in the code graph.
GradCam-Graph utilizes gradient values to measure the edge importance, leading to an explanation sub-graph that correlates with the detection model's hidden information rather than the actual vulnerabilities.
In contrast to these factual reasoning-based explainers, aims to address what-if questions by seeking a minimal perturbation to the code graph that alters the detection model's prediction from “vulnerable” to “non-vulnerable”.
Through this exploration, delves deeply into the context where the vulnerability occurs, revealing causal relationships between code structures and detection outcomes, thereby discovering the root causes of the detected vulnerabilities.



Answer to RQ1: exhibits superior effectiveness in vulnerability-oriented evaluation, outperforming state-of-the-art factual reasoning-based explainers. 







 §.§ RQ2: Model-oriented Evaluation



Compared to vulnerability-oriented evaluation, model-oriented evaluation focuses on assessing the necessity of the generated explanations for supporting the detection model’s predictions. 
As illustrated in Figure <ref>, demonstrates superior performance over state-of-the-art factual reasoning-based explainers across four GNN-based detection models. Notably, the PN curve for consistently encompasses those of the baseline explainers under various K_M settings, visually indicating its effectiveness.
Unlike factual reasoning-based explainers that identify crucial sub-graphs but fall short in determining their actual influence on detection outcomes, targets a minimal change to the code graph that alters the prediction. 
This approach ensures the identification of edges that are truly necessary for the prediction outcome. 
This distinction is crucial in understanding 's ability to provide more accurate and essential explanations.
Moreover, we can observe that as the value of K_M increases, the PN scores of all explainers generally show improvement.
This improvement can be attributed to that with a higher K_M value, more crucial edges necessary for supporting the detection result are identified and included in the generated explanation sub-graph.




Answer to RQ2: demonstrates superior performance in model-oriented evaluation, outperforming state-of-the-art factual reasoning-based explainers. 









 §.§ RQ3: Influence of Hyper-parameter α



Understanding the impact of the trade-off hyper-parameter α is crucial for optimizing 's performance in generating counterfactual explanations.
The hyper-parameter α plays a pivotal role in balancing the emphasis between the prediction loss item and the distance loss item. 
We conduct the parameter analysis on by varying α from 0.1 to 0.9 while keeping other hyper-parameters fixed.

As shown in Figure  <ref>, α significantly influences the effectiveness of the counterfactual explanation generated by . 
We can see that with the increase in α, the differences between the predictions using the perturbed graph and the original graph are more encouraged, thereby pushing the explanation to be more counterfactual, which leads to dramatic performance improvements. 
However, after α reaches its optimal value, the performance begins to decline because tends to generate a counterfactual larger perturbation to the code graph that may fail to identify the most critical factor influencing the detection system's prediction.
Based on our parameter analysis, we set α=0.9 for GCN and GraphConv, α=0.8 for GGNN, and α=0.5 for GIN.
These values are chosen to ensure optimal performance across different models, accommodating their unique characteristics and sensitivities to the balance between prediction and distance loss.



Answer to RQ3: The trade-off hyper-parameter α has a significant impact on 's performance. Optimal settings vary across models, with α=0.9 for GCN and GraphConv, α=0.8 for GGNN, and α=0.5 for GIN.






 §.§ Case Study


We conduct a case study to qualitatively assess the effectiveness of compared to factual reasoning-based explainers, as shown in Figure <ref>.
This case study involves a specific code commit of the  function in the  file from the  project[<https://github.com/the-tcpdump-group/tcpdump>]. 
The added lines are indicated with a “” sign, while the deleted lines are marked with a “” sign. 
This commit addresses a buffer over-read vulnerability of the NFS parser, reported by CVE-2017-13001[<https://www.cvedetails.com/cve/CVE-2017-13001>]. 
This vulnerability arises from the original code failing to ensure that the source string  is shorter than the destination buffer  (20).
As a result,  could copy more characters than  can safely contain, without null-terminating it immediately after the last copied character (21). 
This leads to potential buffer over-reads when  is later accessed as a string.
To address this vulnerability, the code should copy no more than  can hold and must explicitly null-terminate the buffer after the last character copied from . 
The fix introduced in the commit ensures that the length of the data copied does not exceed  (23) and that  is correctly null-terminated after the copy (25), preventing any over-read.



In this case study, we observe that factual reasoning-based explainers like GNN-LRP and GradCam fail to identify the vulnerability cause (20 and 21) in their generated explanation sub-graphs.
While other factual reasoning-based explainers effectively point out 20 or 21, their generated explanations also contain a few code statements unrelated to the vulnerability.
This dilutes the clarity of the explanations, leaving developers to manually check the code to find out the actual vulnerability cause.
Conversely, excels by generating a set of diverse counterfactual explanations to help developers understand the context of the detected vulnerability.
For example, in structure (c), identifies that removing the program dependencies 2→1, 20→1, and 21→1 alters the detection result.
This directly leads developers to the critical statements 20 and 21, which involve buffer operations (1 and 2 are not involved), and identifies them as potential areas of the vulnerability.
Further, through the analysis of the minimal counterfactual perturbation as in structure (f), offers an actionable insight, i.e., inspecting the null-terminating operation at 21 for potential errors.




§ THREATS TO VALIDITY


The threats to the validity of our work are discussed as follows.


The effectiveness of the counterfactual explainer is heavily influenced by the detection performance of the GNN model. Since our explainer generates explanations by perturbing the code graph instance, it relies on a reliable detection model to determine whether the perturbed instance is vulnerable or not. If the detection model has learned biased patterns and fails to produce the correct detection result for the perturbed instance, it can undermine the effectiveness of the explainer. 
Thus, to ensure the optimal performance of the explainer, we recommend using it in conjunction with GNN-based detection models that exhibit ideal detection performance. By combining the counterfactual explainer with high-performing detection models, we can enhance the overall effectiveness and reliability of the explanation process.



Our current counterfactual explainer is primarily based on graph theory principles and does not specifically consider the unique features of vulnerabilities. In our future work, we plan to enhance our explainer by incorporating perturbation algorithms specifically tailored to the vulnerabilities in code graphs. 
This will enable us to achieve a more specialized counterfactual explainer, which can better capture the underlying characteristics of vulnerabilities and provide more accurate insights into the behavior of GNN-based vulnerability detection models.



§ RELATED WORK

In this section, we review the related literature about vulnerability detection and localization, explainability in software engineering, and counterfactual reasoning in GNNs.



 §.§ Vulnerability Detection and Localization

Vulnerability detection plays a crucial role in ensuring the security and reliability of software systems. 
Existing efforts in vulnerability detection can be generally divided into two main approaches: 
static analysis-based <cit.> and deep learning-based <cit.> approaches.
Traditional static analysis-based approaches require human experts to manually define specific rules, which suffers from efficiency issues.
On the other hand, deep learning-based approaches have gained increasing interest in vulnerability detection, due to their strong capability in representing the semantics of source code.
However, compared with static analysis-based approaches, the deep learning-based approaches cannot provide a fine-grained analysis of which lines of the code may cause the detected vulnerabilities.


Although fault localization techniques like spectrum-based methods <cit.> and delta debugging <cit.> could be employed to locate vulnerable code statements, their effectiveness relies on either the availability of extensive test suites or numerous time-consuming testing executions.
Recently, several deep learning-based line-level detection methods <cit.> have been proposed to predict which statements in the code are vulnerable. 
However, these methods not only require large training samples to train the deep-learning models but also lack explainability in why certain statements are predicted as vulnerable.
Consequently, explainable approaches have attracted increasing attention in vulnerability detection.
Existing explainable approaches are mainly based on factual reasoning, which aims to find the input features that play a crucial role in the detection model's prediction <cit.>.
However, these approaches are limited in their ability to provide further insights on how to alter the detection model's prediction, especially when the code is predicted as vulnerable.
In contrast to the previous work, introduces counterfactual reasoning to identify what input features to change would result in a different prediction, thereby providing actionable guidance for developers to address the detected vulnerabilities.






 §.§ Explainability in Software Engineering

Explainability poses a challenging issue in software engineering, especially due to the increasing dependence of developers on using the predictions provided by deep learning models to optimize their codes.
Recently, many efforts have been made to improve the explainability of deep learning models in software engineering <cit.>.
For instance, <cit.> focused on global explainability, which aims to find specific input data types on which the model exhibits poor performance. 
<cit.> introduced a neuron-level explainability technique to identify important neurons within the neural network and eliminate redundant ones. 
<cit.> addressed the structural information of source code under a multi-modal neural network equipped with an attention mechanism for better explainability.
<cit.> investigated the explainability of pre-trained language models of code (e.g., CodeBERT and GraphCodeBERT), which conducts a structural analysis to explore what kind of information these models capture.
Furthermore, several factual reasoning approaches have been proposed recently. 
For example, AutoFocus <cit.> employed attention mechanisms to rate and visualize the importance of code elements.
<cit.> proposed an explainable approach based on heuristic searching, aiming to identify the code tokens contributing to the vulnerability detector's prediction.
In addition, two previous studies <cit.> proposed model-agnostic explainers based on program simplification techniques, which aims to simplify the input code while preserving the model's prediction results, inspired by the delta debugging algorithms <cit.>.
Counterfactual reasoning has also been explored by a recent work <cit.>, similar to our work. However, this work focused on perturbing the plain text input of code to generate counterfactual explanations, in contrast to our work focusing on perturbing the graph input of code.




 §.§ Counterfactual Reasoning in GNNs

Recently, several studies have explored the use of counterfactual reasoning to provide explanations for GNNs <cit.>.
For example, <cit.> generated counterfactual explanations by identifying a minimal perturbation to a node's neighborhood sub-graph that would change the GNN's prediction on this node.
<cit.> employed Granger causality for counterfactual reasoning to learn explanations based on an auto-encoder model via supervised learning.
<cit.> identified robust edge subsets whose removal would alter the GNN's predictions by learning the implicit decision regions in the graph.
<cit.> utilized a graph variational autoencoder for the optimization and generalization of counterfactual reasoning on graphs.
<cit.> incorporated both counterfactual and factual reasoning perspectives from causal inference theory.
<cit.> explored global counterfactual reasoning for GNNs' global explainability.
Furthermore, counterfactual reasoning has been applied in domain-specific graph scenarios, such as molecular graphs <cit.> and brain networks <cit.>.
While the idea of counterfactual reasoning in these studies is similar to our work, we are the first to investigate counterfactual reasoning on code graphs and provide counterfactual explanations for the vulnerability detection task.




§ CONCLUSION

In this paper, we propose , a novel counterfactual reasoning-based explainer for explaining the predictions made by GNN-based vulnerability detection models. 
generates counterfactual explanations by identifying the minimal perturbation to the code graph that can alter the detection system's prediction, thus addressing what-if questions for vulnerability detection.
The counterfactual explanations can identify the root causes of the detected vulnerabilities and provide actionable insights for developers to fix them. 
Our extensive experiments on four GNN-based vulnerability detection models show that outperforms the existing state-of-the-art factual reasoning-based explainers.

The application of counterfactual reasoning in software engineering, particularly in the domain of vulnerability detection, is still in its early stages, offering substantial opportunities for further exploration. 
The success of encourages us to explore its application in broader tasks, including but not limited to bug detection, code search, and code clone detection. 
We believe that the principles of counterfactual reasoning can be effectively adapted to these areas, potentially transforming the way developers interact with and understand software systems.




All the experimental data and code used in this paper are available at 
.



§ ACKNOWLEDGMENT

This work is supported by the Major Program (JD) of Hubei Province (Grant No. 2023BAA024).


We would like to thank all the anonymous reviewers for their insightful comments.

ACM-Reference-Format



