Short Title]: A Method for Explaining the Predictions of Models of Code

Yu Wang

State Key Laboratory for Novel Software Technology Department of Computer Science and Technology
Nanjing University

Ke Wang

Visa Research

Palo Alto

Linzhang Wang

State Key Laboratory for Novel Software Technology Department of Computer Science and Technology
Nanjing University

Attribution methods have emerged as a popular approach to interpreting model predictions based on the relevance of input features. Although the feature importance ranking can provide insights of how models arrive at a prediction from a raw input, they do not give a clear-cut definition of the key features models use for the prediction.

In this paper, we present a new method, called , for explaining the predictions of code models.

Although employs the same mechanism of tracing model predictions back to the input features, it differs from all existing attribution methods in crucial ways. Specifically, divides an input program into “” (, the defining features that are the reason for which models predict the label that they predict) and the rest “”

for any prediction of a learned code model.

We realize in a tool, , and use it to explain four prominent code models: code2vec,
, GGNN, and CodeBERT. Results show (1) is efficient — taking on average under twenty seconds to compute the for an input program in an end-to-end fashion (, including model prediction time); (2) the that all models use to predict input programs is made of simple syntactic or even lexical properties (, identifier names);

(3) Based on , we present a novel approach to explaining the predictions of code models through the lens of training data.

§ INTRODUCTION

Riding on the major breakthroughs in deep learning methods along with the ever-increasing public datasets and computation power, modern machine learning (ML) models, such as neural networks, have been increasingly applied to solve programming language tasks, and achieved remarkable success in a variety of problem domains: method name prediction <cit.>, program repair <cit.>, and program verification <cit.>.
Despite those accomplishments, neural networks mostly operate in a black-box manner, making it difficult to get insight into their internal mechanism of work. This lack of transparency has become an impediment to the use of learning-based program analysis tools, especially in security-critical settings (, malware detection) as the degree to which their predictions can be trusted is rather unclear.
From a scientific standpoint, improving the transparency of neural models is also essential to the soundness of science.
Because their inability to provide explanations for their decisions not only weakens the validity but also hinders the openness of
scientific discovery.

A Review of Attribution Methods.
In the past few years, significant progress has been made in explaining the predictions of ML models. A prominent class of explainability techniques, called attribution methods, has sparked a lot of interest in the ML community. The idea is to assign an attribution score to each input feature a particular output of a network. In general, attribution methods can be classified into two categories: perturbation-based and backpropagation-based. The former refers to those that make perturbations to input features and observe the impact on later neurons in the network. <cit.> is a typical example in the image classification domain. In particular, it occludes different segments of an input image and visualizes the change in the activation of later layers. The strength of perturbation-based methods lies in their visibility, that is, one can directly visualize the marginal effect of any input feature via perturbation. Backpropagation-based methods exceed the perturbation-based in terms of efficiency. In particular, they can compute the attributions for all input features in a single forward and backward pass through the network.

As an early attempt, <cit.> proposed using the gradient of the output pixels of an input image to compute a saliency map of the image. A key drawback of this approach is its inability to address the saturation problem, namely, gradients can be tiny at certain inputs that may yield significant activations within the network <cit.>.

Integrated Gradients <cit.>, a well-known explainability technique, offers a solution. Instead of computing the gradients at only the current value of the input, <cit.> propose to integrate the gradients as the inputs are scaled up from a pre-set starting value to their current value. We defer a detailed survey on the attribution methods to Section <ref>.

[basicstyle=,  morekeywords=var, public, String, Object]code/newAddItem-ori.cs

An example method whose name is correctly predicted by  <cit.>. The top-five predictions made by are shown on the right. Throughout the paper, we will use this program as our running example.

Insights of .
While the attribution methods can be readily applied to explain the predictions of learning-based program analysis tools, such as producing a ranking on the importance of different parts of the input program,
they do not give a clear-cut definition of the critical features that models use for that prediction. Considering the ideal case in which there might exist a “sweet-spot” in the ranking that separates the critical features from the rest, then how to determine the “sweet-spot” is rather unclear. To address this shortcoming, this paper presents a new explanation method, (Wheat and Chaff), for interpreting the predictions of models of code, a broad class of models that predict the properties of source code. Figure <ref> shows one such task called method name prediction. We will use the program as our running example throughout the paper. Unlike the existing attribution methods that assign a relevance score to each input feature, classifies an entire input into two kinds of features: the defining features, , that are the reason models predict the label that they predict, and the remaining features, .

A natural question arises: how do we define for an input program given a particular model prediction? Our insight is to observe how models react to a pair of complementary prediction samples derived from the original input. Technically, we formulate the following two constraints to quantify the influence of . That is, the very same model must (1) preserve its prediction when the original input becomes ; and (2) change its prediction when the original input becomes .

Below we illustrate these two constraints with our running example. Figure <ref> shows that the expression, , alone preserves the prediction, , makes for the original input, thus the first constraint is satisfied; Figure <ref> shows that removing  from the input program changes 's prediction to , therefore the second constraint is also met. Compared to the existing attribution methods, 's explanations allow end users to know precisely and definitively the features that models use for a prediction they make, and in turn evaluate the trustworthiness of the prediction more accurately. Considering the running example, lets end users know exactly  are the features uses to predict the label , whereas, a ranking of the attribution score for each feature would have been vague (, unclear how small an attribution score indicates feature irrelevance) and redundant (, unnecessary to compare the attribution scores of features in the , such as  vs. , or those in such as  vs. ).

style=mystyle[basicstyle=, morekeywords=var, public, String, Object]code/newAddItem-sufficient1.cs

style=mystyle[basicstyle=,morekeywords=var, public, String, Object]code/newAddItem-necessary1.cs

A statement in the example program that satisfies the two constraints.

The reason that does not compile is that , like most code models, does not require input programs to compile. In fact, is general, capable of explaining models with or without compilation requirements.

Using 's explanations as the ground-truth,

we find that the ranking produced by some of the most prominent attribution methods routinely underestimates the importance of . Take 's prediction for the example program as an instance, Figure <ref> shows that none of the top-five important tokens computed by Integrated Gradients <cit.> is part of the , the underlined expression in the program. This finding rebuts the aforementioned “sweet-spot” hypothesis, and confirms that existing attribution methods are unsuitable for detection.

[basicstyle=,morekeywords=var, public, String, Object]code/newAddItem-ori-mark.cs

Regarding 's prediction for the running example, the left shows the five most important features (highlighted within the shadow boxes) computed by Integrated Gradients and the (underlined). The ranking of the attribution scores of the five most important features is shown on the right.

Identifying the from an input program is a challenging task.

With a token-based representation, a program composed of $n$ tokens will yield a search space of $2^n$ candidates (, every token may or may not be part of the ). Even after taking into account the syntactic and semantic constraints, the search space will not shrink dramatically. As a result, a brute-force search would be computationally intractable for any non-trivial program.

Our solution is based on the finding from <cit.> —

few simple code edits, albeit preserving the property of interest for input programs, frequently cause models to alter their predictions — we hypothesize that models heavily utilize small, local program features for predictions.
To confirm our hypothesis, we conduct a preliminary study in which we test how models respond to new programs obtained via systematic reduction of the input programs.
Quite surprisingly, we find that almost always an input program can be reduced to very few statements (, $\leq$ 3) for which models make the same prediction as they do for the original program. This observation indicates that a small code fragment may already contain the that models need for making the correct prediction.
Therefore, a more efficient approach is to first detect such code fragments, and then locate the within them. At the technical level, we present “Reduce and Mutate”, a coarse-to-fine method for identifying the that code models use for prediction. Given a program $P$ for which a model $M$ makes a prediction. First, we find a global minimum program $\bar{P}$ for ${P}$ that satisfies the first two above-mentioned constraints (coarse-grained search).
Second, we mutate the expressions
in $\bar{P}$'s statements to pinpoint the program properties $\tilde{P}$ that led to the satisfaction of the two constraints (fine-grained search). Although it looks like, at this point, we have found the $\tilde{P}$ that $M$ uses to predict $P$,

a core issue must be resolved: are $M$'s predictions for all intermediate programs that uses to query $M$

(, $\bar{P}$, $\tilde{P}$, ) still valid given the seemingly distribution shift between intermediate programs and original programs on which $M$ is trained (, $P$). Inspired by ROAR <cit.>, we present a similar approach to tackle the potential out-of-distribution issue. The key idea is to retrain $M$ with additional data that resembles the intermediate programs. If finds the same $\tilde{P}$ — which are now clearly in distribution thanks to the retraining of $M$ — that retrained $M$ uses to predict $P$, we have confirmed that $\tilde{P}$ is indeed the of $P$ that $M$ uses for prediction.

We realize our approach in a tool, called , and use it to evaluate four pioneering code models: code2vec <cit.>,  <cit.>, GGNN <cit.>, CodeBERT <cit.>. We choose them not only because they are prominent representatives of models of code, but more importantly, they reflect a wide variety of both model architectures and downstream tasks so that the effectiveness and generality of can be thoroughly tested. Our evaluation

results show (1) first, is efficient — taking on average less than twenty seconds to compute the for each evaluated model; (2) the that all evaluated models use for prediction are simple as they never exceed fifteen tokens, many times down to the name of a single variable; (3) After training models on programs coming from a similar distribution to those with which queried the models before, almost always finds the same that original and retrained models use for prediction. This is strong evidence that 's approach is valid in light of the out-of-distribution issues;

(4) Integrated Gradients and SHAP <cit.>, two among the most well-known attribution methods, do not precisely identify the because those they assign higher scores frequently miss out on the .

As an example use of , we present a novel approach to explaining the predictions of code models. At the high-level, our approach answers a more fundamental question: which programs in the training set are most responsible for a model prediction? Ultimately, the weights of a model are derived from the training data. Hence our approach identifies the root cause for a prediction rather than interpreting the internal states of a model after its weights have been learned. At the technical level, given an unseen program $P$ for which a model $M$ predicts a label $L$, we rank $M$'s training programs with the label $L$ based on their distance to $P$, measured using their respective feature properties, and then present the top-$k$ closest programs as the explanations for the prediction $M$ made for $P$.

This paper makes the following contributions:

* A method for explaining predictions of models of code.

* A definition of the defining features (, ), the reason for which code models predict the label that they predict.

* A method for identifying the that code models use for predictions.

* An implementation, , which we use to evaluate code2vec, , GGNN, and CodeBERT. Results show that (1) is efficient: taking on average less than twenty seconds to compute the ; (2) all models use simple syntactic or even lexical properties for prediction; (3) Integrated Gradients and SHAP, two attribution methods do not precisely identify the for any evaluated model.

* An approach to explaining predictions of code models through the lens of training data.

The rest of the paper is structured as follows. Section <ref> gives the formalization. Section <ref> describes in detail our method including the discussion on the out-of-distribution issues and

an example application of . Next, we present our evaluation of (Section <ref>). Finally, we survey related work (Section <ref>) and conclude (Section <ref>).

§ FORMALIZATION

We consider a machine learning model $M$ as a program (with semantics $\llbracket M \rrbracket$) which executes on an input (, an image,

a document, a piece of code, ) and returns a prediction as output. Given a prediction $L$ that $M$ makes for an input program $P$

(, $\llbracket M \rrbracket \big(P\big) = L$), the problem aims to solve is to identify the $M$ uses for this prediction. Below, we give a formal definition of , which is at the core of .

The that $M$  uses for predicting the label of $P$ is a set of statements $\tilde{P}$ such that (1) $\tilde{P}$ is a constituent of $P$: $\tilde{P}$'s token sequence, denoted by $(t_{n}^{\tilde{P}})_{n\in\mathbb{N}}$, is a subsequence of $P$'s denoted by $(t_{m}^{P})_{m\in\mathbb{N}}$. Formally, $(t_{n}^{\tilde{P}})_{n\in\mathbb{N}} = (t_{m_{k}}^{P})_{k\in\mathbb{N}}$ where $(m_k)_{k\in\mathbb{N}}$ is a strictly increasing sequence of positive integers.

(2) $\tilde{P}$ is sufficient: $M$ makes the same prediction for $\tilde{P}$ as it does for $P$ (, $\llbracket M \rrbracket \big(P\big) = \llbracket M \rrbracket \big(\tilde{P}\big) = L$);

(3) $\tilde{P}$ is necessary: $M$ makes a different prediction for $P \setminus \tilde{P}$ than it does for $P$ (, $\llbracket M \rrbracket \big(P \setminus \tilde{P}\big) \neq \llbracket M \rrbracket \big(P\big)$) where $P \setminus \tilde{P}$ denotes the operation that subtracts program $\tilde{P}$ from $P$ (Definition <ref>).

Finally (4) $\tilde{P}$ is minimum: there does not exist $\tilde{P}^\prime$ such that $\tilde{P}^\prime$ satisfies the above three requirements, and $\lvert\tilde{P}^\prime\rvert < \lvert\tilde{P}\rvert$ where $\lvert \cdot \rvert$ denotes the length of a sequence.

Here we discuss the intuition behind Definition <ref>. First, the constituent requirement captures an obvious intuition, that is,
the must be part of an input program. Second, the sufficient requirement is also quite intuitive — as the , they must single-handedly lead models to predict the same label as before without the rest of the input. However, the satisfaction of sufficient requirement alone does not suffice features to be the . Consider the following example in Figure <ref>. Even though Figure <ref> shows the statement, , manages to preserve the prediction, , the model makes for the original input (, the sufficient requirement is satisfied), it is not the reason for which makes this prediction because removing it from the input program barely influences . As displayed in Figure <ref>, the probabilities at which predicts the top-five labels remain almost unchanged. Clearly, this prediction result suggests that does not even need  let alone use it as the to predict the example program. This is precisely the reason that <cit.>, which seeks exclusively the sufficient features as model interpretations, is flawed. In fact, our large-scale study shows that removing the features discovered by <cit.> from input programs always never makes models alter their original predictions.

To address this issue, we design the necessary requirement: the removal of the from the input program, which we call the subtraction operation (Definition <ref>), must lead models to predict different labels than they did for the original input.

style=mystyle[basicstyle=,morekeywords=var, public, String, Object,xleftmargin=.05, xrightmargin=.05]code/newAddItem-sufficient2.cs
A statement that satisfies the sufficient requirement.

[basicstyle=, morekeywords=var, public, String, Object]code/newAddItem-notnecessary2.cs

The same statement does not satisfy the necessary requirement. 's prediction probabilities of the top-five labels remain almost unchanged.

A statement that satisfies the sufficient but not necessary requirement.

Given a program $P$ and a set of statements $\hat{P}$, $P \setminus \hat{P}$ means for each statement $S$ in $\hat{P}$, first locate the subtree, which is equivalent to the Abstract Syntax Tree (AST) of $S$, from the AST of $P$; then remove the located subtree from the AST of $P$. Finally, serialize the resultant AST back to source code.

Using only the constituent, sufficient, and necessary requirement,
every input program is the for itself — an uninteresting explanation for any model
prediction. To address this issue, we impose the last constraint to ensure the precision of .
Specifically, we argue that $\tilde{P}$ should be the globally minimum sequence of tokens since it's the most precise — covering the pattern that models have learned with the least amount of features (, having the highest signal-to-noise ratio).

Given Definition <ref>, it is obvious that the always exists for any input program for which models make a prediction. We left the proof to the supplemental material.

Given a prediction $L$ that $M$ makes for an input program $P$, the $\tilde{P}$ that models use to predict the label of $P$ always exists.

§ METHODOLOGY

In this section, we first briefly describe a crucial weakness of models of code, which motivates a key idea of finding the . Then, we give a detailed presentation of

Reduce and Mutate, a simple yet efficient method for identifying the defining
features. Next, we address the out-of-distribution issues, a potential validity concern about 's approach. Finally, we present an application of the .

§.§ Background

While deep neural networks have been gaining increasing levels of interest in programming languages research, <cit.> cautioned that some eminent code models are surprisingly unstable with their predictions. Simple, natural, and semantically-preserving transformations frequently cause models to alter their predictions. Here we use an example to demonstrate their finding. Figure <ref> depicts the original method which is correctly predicted by code2vec to be factorial; Figure <ref> depicts the transformed method, albeit semantically equivalent, is totally mishandled. None of the top-five predictions even remotely resemble the ground truth considering that all we changed is the order of the operands in a multiplication expression.

[linewidth=2.8cm,morekeywords=var, public, String]code/facbef.cs

Prediction for the original method.

[linewidth=2.8cm,morekeywords=var, public, String]code/facaft.cs

Prediction for the transformed method.

A simple, natural, semantically-preserving transformation causes code2vec to change its prediction. Note that the probability of the top-one prediction is even higher on the transformed method.

Reducing the running example using DD. $\Delta_i$ denotes partitions and $\nabla_i$ is the complement of $\Delta_i$. For simplicity, we use tokens to represent programs that are tested against the sufficient and necessary requirement at each step. The last column shows the requirement that partitions do not satisfy.

max width=

2*cStep     2*cPartition     5c|Tokens     2*cUnsatisfied

size       return      mItems      add      position
1     $\Delta_{1}$      $\checkmark$                          Both
2     $\Delta_{2}$            $\checkmark$                     Both
3     $\Delta_{3}$                 $\checkmark$                  Both
4     $\Delta_{4}$                        $\checkmark$            Both
5     $\Delta_{5}$                             $\checkmark$       Both
6     $\nabla_{1}$             $\checkmark$       $\checkmark$      $\checkmark$     $\checkmark$      Sufficient
7     $\nabla_{2}$       $\checkmark$             $\checkmark$      $\checkmark$     $\checkmark$     Sufficient
8     $\nabla_{3}$       $\checkmark$        $\checkmark$           $\checkmark$     $\checkmark$        Sufficient
9     $\nabla_{4}$        $\checkmark$      $\checkmark$      $\checkmark$          $\checkmark$      Sufficient
10     $\nabla_{5}$        $\checkmark$      $\checkmark$      $\checkmark$       $\checkmark$           Sufficient

Applicability of Delta Debugging.
Their finding suggests that models don't evenly distribute their attention across the entire structure of input programs; instead, they focus on a small fragment of code. At first glance, Delta Debugging (DD) <cit.> seems to be a perfect approach to finding such code fragment from input programs. In particular, we can apply DD to remove the irrelevant code in reference to the sufficient and necessary requirement.

It is worth mentioning a property that has to be satisfied in order for DD to be applicable is Monotony (Definition 6 in <cit.>), meaning, in the software debugging setting, whenever an input causes a program to fail a test, others that include this input will also cause the program to fail. This property is crucial because it allows DD to remove partitions of the input that are unrelated to the cause of the failure. As a result, the search space still shrinks even when the failure-inducing faults can not be precisely located from the input. Conversely, without the monotony property, an irrelevant partition may not be removed from the input because its complement, albeit including the failure-inducing faults, can still have the program pass the test. We can easily redefine monotony in our settings to be whenever $p$ satisfies both the sufficient and necessary requirement, then every super-sequence of $p$  satisfies the two requirements as well, formally,
$\forall p \preceq P \, (\llbracket M \rrbracket  \big(p\big) =  L \land \llbracket M \rrbracket\big(P \setminus  p\big) \neq  L \land p \preceq p') \Rightarrow \llbracket M \rrbracket \big(p'\big) =  L \land \llbracket M \rrbracket\big(P \setminus  p'\big) \neq L $

where $p\preceq P$ denotes $p$ is a sub-sequence of $P$.

It is rather clear that machine learning models do not guarantee to satisfy this property.

Below, we use the running example to demonstrate 's non-satisfaction of the monotony property (Table <ref>), and in turn the ramifications of applying DD for detection.

We skip the steps in which DD successfully reduces the example into the code fragment consisting of ,  and . Since then DD can not make further reductions even though the fragment is clearly not the . In fact, DD had an opportunity to remove either the statement  (at Step 6), the statement  (at Step 7), or the parameter  (at Step 10) had the model satisfied the monotony property. That is, in any of the three steps, the reduced program, which includes the , would have satisfied the sufficient and necessary requirement and allowed DD to proceed. However, since predictions of are not monotonic, the resultant programs at all three steps turn out to violate the sufficient requirement. As a result, DD gets stalled and the final output is not minimal. For interested readers, we left DD's complete procedure in reducing the example program to Section <ref>  in the supplemental material.

Although refining DD to deal with non-monotony subjects is a pathway forward, it is out of the scope of this work. Instead, we present a simple, efficient search strategy that first aggressively prunes the search space of the (, the goal of Reduce), and then precisely locate its constituent program properties from the remaining code fragment (, the goal of Mutate).

[font=,thick,node distance=0.5cm]

[matrix of nodes, shape=rectangle,draw,
nodes=anchor=center,column sep=-1.5em, row sep=1pt, inner sep=1.65pt,outer sep=0pt, ampersand replacement=&](blockStep1)

Step 1

[frame=none, morekeywords=var, public, String]code/newAddItem-reduce1.cs

List of statements

max width=1

Stmt. 1
Stmt. 2
Stmt. 3
Stmt. 4
Stmt. 5

Stmt. 6

right=of blockStep1] (blockStep2)
Step 2
[frame=none,  morekeywords=var, public, String]code/newAddItem-reduce2.cs

below=of blockStep2] (blockStep21)
Step 3
[frame=none, morekeywords=var, public, String]code/newAddItem-reduce2.1.cs

left=of blockStep21] (blockStep3)
Step 4
[frame=none, morekeywords=var, public, String]code/newAddItem-reduce3.cs

left=of blockStep3] (blockStep4)
Step 5
[frame=none, morekeywords=var, public, String, Object]code/newAddItem-reduce4.cs

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep1) – (blockStep2);

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep2)– (blockStep21);

[draw half paths=dotted,line width=2pt line width=5pt,-Triangle[width=10pt,length=4pt],solid]  (blockStep21) – (blockStep3);

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep3)– (blockStep4);

High-level steps of Reduce. The label that predicts at each step is highlighted in shadowbox.

§.§ Reduce

Because fragments that contain the are usually small, the search can be made very efficient by testing out smaller code fragments first. Figure <ref> illustrates the high-level steps of Reduce on the running example.

First, we flatten the input method into a list of statements (Step 1).

We then traverse the fragments (, combination of statements) in the ascending order of their size, starting with those that contain only one statement.

We pick Stmt. 1:  as the first statement to check against the sufficient and necessary requirement. As depicted in Step 2, makes a different prediction for this statement[To facilitate readers' understanding, we highlight the predicted label within the shadowbox at each step in Figure <ref> and <ref>.], thus, the sufficient requirement is not met.

We move on to the other statements. As shown at Step 3, Stmt. 2 also does not satisfy the sufficient requirement. We omit Stmt. 3 for its non-satisfaction of the sufficient requirement either. Next, we arrive at Stmt. 4: . In particular, we find that Stmt. 4 satisfies the sufficient requirement at Step 4 and necessary requirement at Step 5, we declare Stmt. 4 to be the fragment that contains the .

To avoid missing other candidates, we continue the traversal until reaching the last statement Stmt. 7 , which violates the necessary requirement. Because future fragments to be explored will be non-minimum compared to Stmt. 4, the Reduce step completes with the lone output of Stmt. 4.

new Method(remaining_statements, method.head)
[Foreach]ForeachEndForeach[1]foreach #1 doend foreach

Find the minimum fragment of code.

[1]
FindMinimumFragment$program, model$
statements $\gets$ Flatten (program)
\(\triangleright\)  traversing all subsets in the ascending of the
cardinality; `-1' excludes the entire set.
k $\gets 1$  to statements.size - 1

\(\triangleright\) getting combinations of size k
sets $\gets$ CombineKStmt (, )
fragments $\gets$ $\varnothing $
set $\in$ sets
suff_mth, nec_mth $\gets$  (set, program)
(suff_mth, nec_mth, )
fragments $\gets$ fragments $\cup$ set
fragments $\neq$ $\varnothing$

Algorithm <ref> gives the details of the Reduce step. The goal of the  function is to reduce an input program into a list of statements (line <ref>). The  loop at line <ref> gradually increases the size of the subsets drawn from the   function (line <ref>) while searching for the minimum code fragments. The  function at line <ref> creates subsets of statements with size . Then, for each subset, the algorithm invokes  function (line <ref>) to return two new programs: one for verifying against the sufficient requirement (, ) and the other for verifying against the necessary requirement (, ). In particular,  is simply the current subset being explored, whereas  is resulted from the subtraction of  from  (Definition <ref>).

Once the created subset is found out to be valid by

function (line <ref>), we add it to the collection of all minimum subsets  (line <ref>). After we have traversed
all combinations of  statements, we return  if it's not an empty set (line <ref>), otherwise, we will continue to explore the code fragments with the size of .

Reduce vs. DD Regarding Non-monotony.  Since the code fragments that
Reduce identifies also include extra code that is irrelevant to the , Reduce is affected by models' non-monotony, the same way DD is affected. However, the degree to which non-monotony impacts Reduce is in general less than that impacts DD. This is because the extra features included always stem from the same statement where the is, as a result, models, by and large, still behave monotonically (, makes the same prediction for  and ). On the contrary, what DD encounters

is that the extra code included along with the is significantly less constrained (, it can be any statement or expression in the program) and come in larger quantities, making models far more likely to be non-monotonic.

[font=,thick, node distance=0.5cm]

Step 1
[frame=none, morekeywords=var, public, String]code/newAddItem-mutate1.cs

right=of blockStep1] (blockStep2)
Step 2
[frame=none,  morekeywords=var, public, String]code/newAddItem-mutate2.1.cs

right=of blockStep2] (blockStep3)
Step 3
[frame=none,  morekeywords=var, public, String]code/newAddItem-mutate2.cs

below=of blockStep3] (blockStep4)
Step 4
[frame=none, morekeywords=var, public, String]code/newAddItem-mutate5.cs

left=of blockStep4] (blockStep5)
Step 5
[frame=none, morekeywords=var, public, String]code/newAddItem-mutate6.cs

left=of blockStep5] (blockStep6)
Step 6
[frame=none, morekeywords=var, public, String]code/newAddItem-mutate7.cs

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep1)– (blockStep2);

[draw half paths=dotted,line width=1.2pt line width=5pt,-Triangle[width=10pt,length=4pt],solid]  (blockStep2) – (blockStep3);

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep3) – (blockStep4);

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep4) – (blockStep5);

[-Triangle[width=10pt,length=4pt], line width=5pt](blockStep5) – (blockStep6);

High-level steps of Mutate. - expression (, + expression) signals removed (, added) lines.

§.§ Mutate

The features discovered in the Reduce step lie at the level of statements (, coarse-grained), thus they are likely to contain redundant elements. To pinpoint the fine-grained , we mutate the program discovered in the Reduce step in an attempt to identify the minimal features that keep the sufficient and necessary requirement satisfied.

Since the number of tokens in the is not guaranteed to be so small as that of the statements in the minimum code fragment, the style of search adopted by the Reduce step is likely to be inefficient for the Mutate step.

For this reason, we only remove the irrelevant part of the code fragment that does not cause the violation of either the sufficient or necessary requirement.

Mutation as well as Reduction.  It is worth mentioning that a significant difference between the two steps is Mutate does not adopt solely a program reduction approach to identifying the fine-grained .
As an example, suppose a code fragment is already successfully reduced to a field access expression, . We then attempt to further reduce the expression into a single identifier . If  turns out to be invalid, we will mutate  back into a field access expression, this time with an out-of-vocabulary field name instead of  — [out-of-vocabulary words are those models have never encountered during training. Thus, replacing a token with an out-of-vocabulary word erases the influence of the replaced name on models. Throughout the paper, we use  to represent out-of-vocabulary words for simplicity and clarity.].

Our rational is, even if  satisfies both the sufficient and necessary requirement, it is still possible that models use the type of the syntactic structure — field access expression — associated with the object  rather than the specific name of its field —  — as the . To deal with

features of this kind that are not explicitly presented,

we mix the deletion and modification operations in the Mutate step to pinpoint both the explicit and implicit fine-grained features.

A illustration of the four-step process of subtracting  from the original program. (1) Figure (fig:subtraction1) presents the AST of the running example, and the AST of  in the bottom left corner. For brevity, the ASTs are simplified. (2) Figure (fig:subtraction2) highlights the overlapping nodes between the two ASTs. (3) Figure (fig:subtraction3) emphasizes the resultant AST after the overlapping nodes are removed, as a result,  becomes a dangling node. (4) Figure (fig:subtraction4) connects  to the body of the method as the completion of the subtraction operation.

Figure <ref> illustrates the procedure of the Mutate step. As depicted in Step 1 and 2, it turns out that neither removing  nor mutating  into  satisfies the sufficient requirement. Similarly, we find that the identifier  is also integral to 's prediction that can not be changed. Next, we move our attention to the first parameter . It turns out that  satisfies both the sufficient (Step 3) and necessary (Step 4) requirement, thus, we remove  from the code fragment. Regarding the subtraction operation (Definition <ref>) invoked for checking code against the necessary requirement, directly removing a subtree from an entire AST may result in dangling nodes that do not connect to any other node in the AST (, the identifier  marked in dashed box in Figure <ref> after we remove the AST of  from that of the original program). In such cases, we simply connect the dangling nodes to the parent node of the root node for the deleted AST (, connecting  to the method body as depicted in Figure <ref>). Figure <ref> gives a detailed illustration of this procedure.

Subsequently, we succeed in removing the second parameter  because  also satisfies the sufficient (Step 5) as well as the necessary requirement (Step 6). Note that the comma that separates the two then parameters  and  becomes a semicolon at Step 6 because both  and  will be considered as standalone statements in the resultant program of the subtraction of  (Figure <ref> in the supplemental material gives a detailed illustration).

Finally, we conclude that  is the that uses for predicting the running example.

[Foreach]ForeachEndForeach[1]foreach #1 doend foreach

Find the .

[1]

FindFeatures$\Md, \OMT, \Ml$

$\gets$ Parse (). is defined to track the minimal features

\(\triangleright\)   is a list of the minimum fragments returned
from the Reduce step
min_mth $\in$
$\gets$ Parse (min_mth).
MutateToFixpoint, ,

$\gets$  Min (, ) return the minimum of two code features

MutateToFixpoint$\Rt, \OMT, \Ml$

last_root $\gets$ $\emptyset $
last_root $\neq$
last_root $\gets$ Mutate, , ,

Mutate$\Ne, \Rt, \OMT, \Ml$
Mutate, , ,

== 0

not , , ,   removing node
\(\triangleright\)  if fails, mutating node
, , ,

Algorithm <ref> gives the details about how to pinpoint the within the minimum code fragment discovered by the Reduce step.

we perform a postorder traversal on the AST (line <ref>) of the minimum fragments. For each node operation in the AST, we consider the following two cases. If a node does not have any child node, then we first try deleting the node (line <ref>). If the resultant program no longer satisfies both the sufficient and necessary requirement, we will mutate the node into one with an out-of-vocabulary value (line <ref>).

If a node has children nodes, it will be kept intact to preserve the status of its children (the  condition at line <ref> will be evaluated to ).

If by any chance a node happens to be irremovable (, immutable), we simply skip the deletion (, mutation) operation.

This entire process is repeated until the AST of the code fragment can not be reduced any further (line <ref> to <ref>). Considering some expressions, which can not be removed or mutated before, may become removable or mutable after others are dealt with first, thus, we compute a fixed point on the result of the Mutate function to make certain the final output will be minimal. (lines <ref> to <ref>).[Interested readers may refer to Section <ref> in the supplemental material for the details of  and  in Algorithm <ref>.]

Minimality  Although the result of Algorithm <ref> may not satisfy the
minimum requirement in Definition <ref>, it satisfies 1-minimality, or more precisely 1-tree-minimality <cit.> that DD no longer satisfies due to the non-monotony of machine learning models. In addition, we show in Section <ref> that even without the guarantees in theory, Reduce and Mutate is in fact remarkably effective in finding the global minimum features in practice.

Compilability  We can easily adjust Reduce and Mutate to accommodate code models that do require input programs to compile. For example, we can filter out uncompilable code with the help of existing compilers in both steps and only use those that compile to query the model.

§.§ The Validity of 's Approach in Light of the Out-of-distribution Issues

Since the programs that queries a model with at both Reduce and Mutate step differ from those that the model has seen in training, it seems that violates one of the key assumptions
in machine learning: the training and evaluation data come from the same distribution, in which case the predictions that the model makes for the query programs will be unsound, and the validity of 's approach will be called into serious question. To address this issue, we draw from a seminal work in explainable ML, ROAR <cit.>, which proposes a retraining approach for handling the distribution shift when evaluating the explainability methods. Their insight is that a commonly used strategy in estimating the feature importance — removing the supposedly informative features from the input and observing how the classifier degrades — comes at a significant
drawback because a performance degradation might be caused by a shift in distribution instead of removal of information. In contrast, <cit.> first retrains the model on the modified data (, in image classification domain, they replace the fraction of the pixels estimated to be most important by an attribution method with a fixed uninformative value for each training image) and then evaluates on test images, which are modified in the same manner, if a feature estimator can identify the important input pixels whose subsequent removal causes the sharpest degradation in accuracy. Since retraining makes certain that training and test data comes from a similar distribution,

the removal of important features becomes the only plausible explanation for accuracy degradation.
On the other hand, ROAR is not without limitations. For one, while the architecture is the same, the model used during evaluation is not the same as the model on which the feature importance estimates were originally obtained.

Inspired by <cit.>'s approach, we design a similar retraining procedure that not only tackles the out-of-distribution issue but also addresses the inherent limitation of ROAR. Denoting the model by $M$, its training set by $\mathcal{P}$ and test set by $\mathcal{Q}$, we describe the steps of our approach:

* for each program $P \in \mathcal{P}$, we perform Reduce and Mutate to generate new programs $\mathbb{P}$ — what would have queried the model with for finding the of $P$.

* we manually label each program $P \in \mathbb{P}$ before training $M$ on $\mathcal{P} \cup \mathbb{P}$.

* we deploy to find the that retrained $M$ uses to predict each program $Q \in \mathcal{Q}$.

* we compare the that finds for each program $Q \in \mathcal{Q}$ before and after the retraining of $M$.

Using the produced by step (3), albeit no longer out-of-distribution, creates the same problem: is essentially explaining the predictions of the retrained model rather than the original model. Instead, we check the equivalence of the two sets of at step (4), if they turn out to be identical, we declare that the finds for each test program $Q$ are indeed the that $M$ uses for prediction; furthermore, the consistency between the two sets of also indicates the retraining procedure does not fundamentally change the model behavior, therefore, can explain predictions of a model in its original form (without retraining).

§.§ An Application of The

We utilize the revealed features code models use to explain their predictions. The idea is as follows. Given a Model $M$, and a program $P$ from $M$'s test set for which $M$ predicts $L$. First, we discover the $M$ uses to predict $L$; Second, we do the same thing for all programs in $M$'s training set with the label $L$. Note that in a generative setting (, code2vec, seq-GNN) where training set might not contain a method of label $L$, we consider all methods whose name is a subset of the words in $L$. Finally, we rank these training programs based on the distance between their and $P$'s revealed features. Our rationale is to find the training programs from which models extracted the at the first place. Thus, our method explains the root cause of a prediction rather than interprets the internal state of models.

In this section, we give a detailed presentation of Reduce and Mutate for identifying the defining features that code summarization models use for prediction.

§.§ Reduce

Algorithm <ref> gives the functionality of the Reduce step. The  loop at line <ref> gradually increases the size of the subsets drawn from the list of flattened statements (line <ref>) while searching for the minimal code fragments. The function  first creates a subset with the parameter , then invokes

, another function that checks the validity of the created subset against the sufficient and necessary requirement. Once the created subset is found out to be valid, we add it to the collection of all minimal subsets  (line <ref>). Below, we present the technical details about two functions:  (line <ref>) and  (line <ref>).

The goal of the  function is to reduce an input method into a set of statements. Specifically, for a non-control statement such as declarations, assignments, or method calls,  directly adds them to the set (line <ref>); for a control statement such as  statement or  loop,  first adds the predicate of the control statement (,  condition) with an empty body

as a separate statement to the set (line <ref>);

and then in order to process statements in their body, we recursively call function  with the body of the control statement as the function argument  (line <ref>). The function terminates when we completely flatten the input program. Note that we bind certain code structures as a single statement to ensure the syntactic validity of the added statements. For example,  or  labels will be automatically added with the  predicate whenever a  statement is flattened.

new Method(remaining_statements, method.head)
[Foreach]ForeachEndForeach[1]foreach #1 doend foreach

Find the minimal fragment of code in a method.

[1]
FindMinimalFragment$method, model$
statements $\gets$ Flattenmethod
\(\triangleright\)  traversing all subsets in the ascending of the cardinality; `-1' excludes the entire set.
k $\gets 1$  to statements.size - 1

fragments $\gets$ SelectionUtilstatements, k, method, model
fragments $\neq$ $\varnothing$

stmts $\gets$ $\varnothing $
stmt $\in$ $\Md$.statements
stmt is ControlStmt if stmt is a control statement
stmts $\gets$ stmts $\cup$ stmt.predicate
stmts $\gets$ stmts $\cup$ Flattenstmt.body
stmts $\gets$ stmts $\cup$ stmt

SelectionUtil$\Ts, \K, \Md, \Ml$

sets $\gets$ CombinationsOfKStatement (, ) getting combinations of size k
fragments $\gets$ $\varnothing $
set $\in$ sets
suff_mth, nec_mth $\gets$  (set, )
(suff_mth, nec_mth, ) check the validity of set
fragments $\gets$ fragments $\cup$ set

function (line <ref>) returns two new programs: one for verifying against the sufficient requirement (, ) and the other for verifying against the necessary requirement (, ).
Regarding the construction of , when the selected combination, denoted by , contains only one element, we place the single statement inside the body of suff_mth while copying the method header from , otherwise, we rearrange the statements in  to reflect the syntactic structure of the input method. For example, an assignment statement will be placed back into the body of a  loop if that was the syntactic structure the input method possesses originally. To construct , we simply subtract the statements in  from the original input  (Definition <ref>).

Minimality  Algorithm <ref> traverses the subsets of $P$ in the ascending order of the cardinality while checking the validity of each subset against the two requirements, therefore, the first subset it finds is the smallest among all. Furthermore, Algorithm <ref> only collects the subsets that have the same size as the first subset it finds. Therefore, Algorithm <ref> always returns the minimal sets of statements that satisfy the two requirements.

§.§ Mutate

In the Mutate step, we aim to pinpoint the defining features within the minimal code fragment discovered by the Reduce step.

[Foreach]ForeachEndForeach[1]foreach #1 doend foreach

Find the defining features in the minimal code fragment.

[1]

FindFeatures$\Md, \OMT, \Ml$
$\gets$ Parse  ().
Mutate, , ,   is the minimal fragment of

Mutate$\Ne, \Rt, \Me, \Ml$
Mutate, , ,
$\gets$ backing up node

count == 0
not , , , ,   removing node
, , , ,    if fails, mutating node

$\Ne, \NB, \Rt, \Me, \Ml$
$\gets$ Delete ()
, , , ,

$\Ne, \NB, \Rt, \Me, \Ml$

$\gets$ Replace (, oov) mutating node into  node
, , , ,

$\Ne, \NB, \Rt, \Me, \Ml$
suff_mth, nec_mth $\gets$ ReconstructByNode (, , )

Verify (suff_mth, nec_mth, )
$\gets$ RestoreNode ()reverting to the backup node

Algorithm <ref> gives the details. At a high-level, we perform a postorder traversal on the AST of the minimal statements. For each node operation, we consider the following two cases. If a node does not have any child node, then we first try deleting the node (line <ref>). If the resultant program no longer satisfies both the sufficient and necessary requirement, we will mutate the node into one with an out-of-vocabulary value (line <ref>). As explained in Section <ref>, the reason we attempt the deletion operation prior to the mutation operation is that even when an expression can not be further reduced, we may only need to retain its syntactic structure without the specific identifier names.

If a node has children nodes,

the parent node will be kept intact to preserve the status of its children. Note that whenever we attempt to delete a node, we may delete addition nodes (, the minimal set of nodes required) just to ensure the syntactic validity of the resultant programs. If the node happens to be irremovable, we simply skip the deletion operation. The same strategy also applies to mutation operations.

For other functions not explicitly defined in Algorithm <ref>,  extracts the AST out of a method,  removes a node,  replaces  a node with a new node,  constructs method  for verifying against the sufficient requirement and method  for verifying against the necessary requirement, and finally RestoreNode reverts a node back to the saved node.

Minimality  Obviously, the result of Algorithm <ref> may not satisfy the minimality requirement in Definition <ref>. In principle, it satisfies the 1-tree-minimality <cit.> property because no node can be further removed from the AST of the defining features. On the other hand, the style of search adopted in Reduce also can not guarantee the global minimality of its outcome because the defining features may exist in a non-minimal code fragment that Reduce can not find. This is the reason that we only consider 1-tree-minimality in the Mutate step, especially given that (1) the size of the defining features is already small, thus the explanations to be generated will be informative to end users; (2) the current algorithm is highly efficient.

Time Complexity  Since Algorithm <ref> performs a linear traversal on the AST of the input program, it has a complexity $O(n)$ where $n$ is the number of the nodes in the tree. Given the dominance of Reduce in terms of the time complexity, our method — Reduce and Mutate — runs in exponential time in theory and quadratic time in practice.

§ EVALUATION

We realize our method Reduce and Mutate in a tool, called , which extracts the that code models use for prediction. In this evaluation, we first deploy to explain several prominent code models. Then we examine the validity of 's approach. Next, we evaluate if attribution methods can find the that finds. Finally, we evaluate the effectiveness of our -based explanation to code models.

§.§ Evaluation Subjects

Models.  We choose code2vec <cit.> because it is among the first to predict method names in large-scale, cross-project settings. We choose since it's the state-of-the-art model in method name prediction. GGNN <cit.> is selected because it is the first graph model applied in the programming domain for variable misuses detection.

We also include CodeBERT <cit.>, a bimodal pre-trained model for programming language and natural language. It achieves state-of-the-art performance on both natural language code search and code documentation generation, the latter of which is used in this evaluation.

Datasets.  For all models except code2vec, we use the datasets on which they are evaluated when they are first proposed. That is Java-small for ; a dataset of 2.9 million lines of real-world C# code for GGNN; and CodeSearchNet <cit.> for CodeBERT. To keep our engineering effort manageable, we only use Java programs in CodeSearchNet (496,688 in total), which should be sufficient for validating 's effectiveness.

Since Java-med, and Java-large share similar characteristics with Java-small except for their bigger size, and code2vec and target the same downstream tasks, we use Java-small, Java-med, and Java-large to evaluate both models.

We have re-trained all models using their implementations open-sourced on GitHub. The performance of all re-trained models is either comparable or superior to the original (Table <ref>-<ref> in the supplemental material). Note that we only use programs in test sets as the evaluation subjects in case models over-fit to training sets.

Baseline.  We use DD as a baseline method; in particular, we apply DD to remove code that is irrelevant to a prediction (determined by the sufficient or necessary requirement). In the end, we declare the program that can not be further removed as the .

Hardware.  All experiments are conducted on 5 Red Hat Linux servers each having 64 Intel(R) Xeon(R) 2.10GHz CPU, 755GB RAM and 4 Tesla V100 GPU (32GB GPU memory).

§.§ Performance of

We evaluate the performance of by the time spends generating explanations end-to-end (, including the time models spend on prediction). The results show that the two methods are neck and neck in practice even though DD is more efficient than in terms of the worst-case complexity (, quadratic time vs. exponential time). This is due to the size of the minimum code fragment finds, which never exceeds three statements for over a million programs used in the evaluation. Furthermore, since the minimal fragment of three statements rarely occurs, DD would not display a significant upgrade. To conclude, is efficient: taking on average less than twenty seconds to compute the .

Avg. end-to-end time for and the baseline. Hereinafter, stronger results are marked in bold.
max width=1

2*Methods     3c|code2vec      3c|seq-GNN      GGNN     CodeBERT
Java-small     Java-med     Java-large     Java-small     Java-med     Java-large     C# Datasets     CodeSearchNet
Baseline     26.45     18.24      23.28     7.28 	   	12.78	    5.34      5.21     16.37
19.76	    	14.37	    	17.71       10.57	    	12.07	    	9.79     7.54      11.23

§.§ Makeup of the

Finding the    We follow Algorithm <ref> and <ref> to identify the minimum code fragments and pinpoint the fine-grained features within these fragments. Table <ref> gives the average number of tokens the is composed of.
Overall, we find that none of the that any evaluated model uses for prediction exceed
fifteen tokens. This result indicates that existing code models use simple program properties for prediction. Additionally, the generated with those properties, albeit not guaranteed to be the global minimum, still help end users to know the that models use for predictions. Table <ref> also gives a comprehensive, head-to-head comparison between and DD. Clearly, is better across the board. A deeper analysis reveals that

for less than 9% of all test programs, DD manages to find the same as , while finds smaller for the remaining over 91%.
In other words, DD never finds smaller than .

This is a concrete piece of evidence that

the degree to which non-monotony impacts is significantly less than that impacts DD.

The average number of tokens in the .
max width=1

2*Methods      3c|code2vec      3c|seq-GNN      GGNN     CodeBERT
Java-small     Java-med     Java-large     Java-small     Java-med     Java-large     C# Datasets     CodeSearchNet
Baseline     14.21     17.13      16.24     12.30     14.84     10.04     14.22     13.63
8.53     9.91      9.58     6.74     6.79     5.66     6.81     6.78

[morekeywords=Object, String]code/init-ori.cs

[morekeywords=Object, String]code/sort-ori.cs

[morekeywords=Object, String]code/init-seed.cs

[morekeywords=Object, String]code/sort-seed.cs

Lexical . Top (, bottom) figures are the original methods (, ).

[morekeywords=Object, String]code/checkDone-ori.cs

[morekeywords=Object, String]code/nextInt-ori.cs

[morekeywords=Object, String]code/checkDone-seed.cs

[morekeywords=Object, String]code/nextInt-seed.cs

Syntactic .

Investigating the Substance of the .  We classify the into three categories according to their constituent program properties: lexical, syntactic, and semantic.

* Lexical: If each statement in the consists of a single identifier. Figure <ref> depicts two examples, in both cases, the consist of only one identifier.

* Syntactic: If there is at least one statement in the composed of a syntactic expression (Figure <ref>).

* Semantic: and GGNN are the two models which take in semantic properties as model inputs. In particular, they use nine kinds of manually designed edges (described in Section <ref> of the supplemental material), out of which seven can be deemed as semantic in nature, to enrich the original AST of input programs. Therefore, we define the to be semantic if its AST is augmented with at least one semantic edge. Take the method  in Figure <ref> as an example, the three semantic edges — one  edge and two  edges — must be present in the AST of the , otherwise the sufficient and necessary requirement are no longer satisfied at the same time. Thus, we classify this example as semantic. To determine whether and GGNN used semantic properties in their , we first run Reduce and Mutate as usual, then we remove all semantic edges from the augmented AST of the obtained . If the resulted tree no longer satisfies both the sufficient and necessary requirement, we categorize the to be semantic.

[morekeywords=Object, String]code/writeArrayToFile-ori.cs

[morekeywords=Object, String]code/compare-ori.java

Semantic . The bottom figure shows the AST of the , in which dash arrows denote the semantic edges. For clarity, the AST is simplified.

Table <ref> gives detailed statistics on the classification for each model. Clearly, for all evaluated models, the primarily consists of lexical properties.

Types of the that each model uses for prediction.
max width=0.95

2*Types     3c|code2vec      3c|seq-GNN      GGNN     CodeBERT
Java-small     Java-med     Java-large     Java-small     Java-med     Java-large     C# Datasets     CodeSearchNet
Lexical     59.27%      51.34%     50.22%     77.60%     64.39%     71.25%      53.39%      49.17%
Syntactic     40.73%    48.66%       49.78%    21.73%    32.96%     26.24%     46.12%     50.83%
Semantic     –     –      –    0.67%     2.65%     2.51%     0.49%     –

§.§ Confirm the Validity of in Light of the Out-of-distribution Issues

Based on the high-level steps introduced in Section <ref>, we present the technical details from two key aspects: data generation and labeling.

Data Generation.  First, we perform the Reduce operation to generate code fragments for each program in the training set.

Then, for each code fragment, we generate additional programs by randomly removing or mutating its constituent expressions. Such programs resemble the code produced out of the Mutate step.

Data Labeling.
Given the amount of work, we attempt to recruit all undergraduate, master and PhD students from Math, Physics, Chemistry, Electronic Engineering, and Computer Science department at our university for the labeling task. In the end, we find 458 students in total and each student has at least one year of programming experience. We also hired 84 professional developers via Amazon Mechanical Turk. Here, we describe the set-up of this experiment in detail. First, for each generated program, we assign it the label of the program from which the is derived. Second, we ask participants to confirm the assigned label for each generated program. Specifically, participants are required to assess based on their intuition if the assigned label correlates to the generated program. An example we gave to all participants is that the of the running example correlates well to the label , therefore, the label should be accepted for the as a stand-alone program. To ensure the quality of labeling, we present every generated program with the assigned label to two participants, and we will only approve the program if both agree to accept the label, otherwise, the program is rejected. We also assign all rejected programs a new label that has not appeared in the original training set.

We randomly select either training or validation set to add each approved program. We keep the same ratio between the added training programs and validation programs as the original dataset. To keep the added data balanced, we also randomly sample a rejected program to accompany each approved program.

Table <ref> shows the number of programs we add including both the confirmed and rejected into Java-small, Java-med, C# Datasets, and CodeSearchNet. We disregard Java-large because it demands excessive human effort to label enough programs given the size of its training set (more than 15 million programs). In addition, Java-small and Java-med should already contain enough data points to validate model behavior, in turn, 's approach.

The number of programs that we add into each dataset for retraining.

max width=1

Java-small     Java-med    C# Datasets     CodeSearchNet
#original programs – training         665,115     3,004,536     130,101     454,451

#added programs  – training          336,938     1,106,288     46,862     267,922
#original programs – validation         23,505     410,699     21,594     15,328

#added programs – validation          11,908     151,222     7,778     9,036

First, we validate the accuracy of all evaluated models on the augmented datasets. We find that all retrained models become more accurate even though the increase of accuracy is negligible (Table <ref>-<ref>  in the supplemental material). We deploy to explain the retrained models, and then compare the two sets of before and after the retraining. It is worth mentioning we also set out to validate Sivand's approach <cit.> using the same original and retrained models. Considering the manually labeled programs also resemble those with which Sivand would have queried the model, thus, in the same way we can evaluate if

Sivand's approach is still valid after the distribution shift between the training and test data is erased. Table <ref> presents the results. Regarding , we find that an overwhelming majority of the programs in every dataset has the same before and after the retraining (the row designated by “Matched”), confirming that those are indeed the models use for prediction with or without the seemingly distribution shift. “Related” represents the models use before and after the retraining come from the same code fragment. They differ at the level of expressions, for example, using retrained models, manages to reduce more features from the previous at the Mutate step or vice versa. “Distinct” means retrained models use entirely different than the original model. Apparently, this raises issues despite the tiny number of programs that falls into this category. To dig deeper, we discover that all such met the sufficient and necessary requirement before, only to get discarded due to the violation of the minimum requirement. The reason that they become the for retrained models is simple:

the then that original models use gets bloated after the retraining (, Mutate operation could not reduce so many features as before), making the minimum. Nevertheless, the “Distinct” (as well as the “Related”) scenario does not invalidate 's approach considering the change of model behavior, to a minor degree, is to be expected after retraining. Overall, we conclude 's approach is valid in light of the out-of-distribution issues.

On the contrary, Sivand's explanations change significantly after the retraining. In particular, only around 40% of the that retrained models use are the same as those that original models use. There is also a large number of programs on each dataset that falls into the “Distinct” category. Given that Sivand's approach does not have a similar notion of minimality, “Distinct” suggests a drastic change in Sivand's explanations after retraining,
Overall, the results strongly indicate the distribution shift heavily influences Sivand.

This is yet another fundamental flaw of <cit.> in addition to ignoring the necessary requirement when producing model explanations.

Discussion.  A natural question arises: for the original models (without retraining) how is it possible for the , which is far from the data that models have seen during training, still within the learned distribution? We believe it is because of the very intrinsic limitation of models’ that they only learn local, lexical/syntactic features from training programs, In other words, even with a whole program to learn, models still extract patterns from simple parts of the program which the is likely to resemble, as a result, they lie in the distribution that models learned.

The percentage of programs for which are identical (designated by “Matched”), come from the same code fragment (designated by “Related”), or entirely different (designated by “Distinct”) before and after retraining for Sivand and .
max width=1

2*Approach     2*Comparison     2c|code2vec     2c|seq-GNN      GGNN     CodeBERT

Java-small     Java-med     Java-small     Java-med    C# Datasets     CodeSearchNet
3*Sivand     Matched     46.2%     37.8%     44.9%     41.2%     38.4%     41.9%

Related     23.9%     30.8%     32.5%     29.5%     26.4%     36.7%

Distinct     29.9%     31.4%     22.6%     29.3%     35.2%     21.4%
3*     Matched     92.5%     96.8%     94.8%     97.3%     93.9%     96.5%

Related     3.6%     2.4%     2.1%     1.7%     4.3%     2.2%

Distinct     3.9%     0.8%     3.1%     1.0%     1.8%     1.3%

§.§ Can Find the Global Minimum Features

In this experiment, we set out to confirm the minimality of the found by . As explained earlier, finding the global minimum requires exhausting all subsequences of the token sequence of the input method. Therefore, to lessen the computational burden, we limit the evaluation data for this experiment to those methods that have either a small set of tokens or small found by (Table <ref>). We also diversify the data the size of programs and to make our results unbiased. To confirm the global minimality of the for the selected methods, we exhaust all subsequences of the token sequence of the input method up to the size of the , specifically, we start from the subsequences of size one, and gradually increase to the size of the . Note that this is also the way in which we verify the for our running example. To cope with such a heavy computational burden, we exhaustively generate the test candidates for each program beforehand in a parallel fashion; then we place them into separate batches to fully exploit the potential of our GPUs (, $\approx$10K test candidates per second per GPU). The whole experiment takes almost three months to complete.

We find that for 79,208 that identified, the brute-force search never finds a single instance where the is smaller. Our results speak volume to the precision of our Reduce and Mutate method in finding the critical features that models use for prediction even if they are not guaranteed to be the global minimum.

Statistics on the selected methods for the minimality experiment.
max width=1

2*Models     4c|#statements in methods      4c|#tokens in       2*#methods in total

Min     Max     Mean     Median     Min     Max     Mean     Median
code2vec     1.0     12.0     7.4     5.0     2.0     17.0     9.4     8.0     21,324
code2seq     1.0     15.0     7.2     6.0     2.0     16.0     10.1     9.0     18,105
seq-GNN      1.0     12.0     5.8     5.0     2.0     16.0     8.2     7.0     19,751
extreme      1.0     14.0     8.1     6.0     2.0     15.0     7.5     7.0     20,028

§.§ Can Other Explainability Methods Find

Percentage of programs whose are fully covered by explainability methods.
max width=1

2*Models     5c|Integrated Gradients (Top-N%)     5c|Attention-based (Top-N%)      5cSHAP (Top-N%)

10%      30%     50%     70%     90%     10%      30%     50%     70%     90%     10%      30%     50%     70%     90%
code2vec        8.23     11.42     13.85     21.69     27.93      52.50     60.00     62.50      64.91     69.22      4.38      5.02      6.37       15.24     55.19
seq-GNN         1.74     6.32     10.17      17.90     25.54      41.36     45.81     51.27      56.92     60.14     6.12      9.33      12.02      38.24     60.58
GGNN        1.95     4.56     9.23       15.68     23.18     38.23     42.32     52.53      57.21     61.21     4.72      7.64      11.72       21.45     65.23
CodeBERT         6.23     10.33     13.12      20.90     29.50      41.97     48.44     52.02     58.19     63.12    6.20     11.54     15.67     27.30     73.56

In this experiment, we evaluate whether or not some of the most prominent attribution methods can also find the that finds. We choose Integrated Gradients <cit.> and SHAP <cit.>, both of which have been widely used for explaining the predictions of image and natural language models.

Worth noting that the two methods are typically contrastive (, they account for deviations from a baseline), we design a baseline in which the embedding for each token (or node) is set to 0. This is the conventional approach followed by the explainability literature. Additionally, we choose the attention mechanism <cit.>, which makes models pay greater attention to certain factors (, elements in an input) when processing the input data. Therefore, the features that are heavily attended to can be deemed as an explanation naturally. In theory, the three explainability methods may find the that does not, therefore, we only use

the 79,208 programs whose are already verified in Section <ref>.

First, we pick input features with top-$N$% highest attribution scores computed by the method. Then, we show the percentage of the programs that are fully covered by those input features (Table <ref>).

Quite unexpectedly, the attention mechanism turns out to be the top performer in this experiment. Up to the features that receive the top-70% attribution scores, attention beats the other two methods by a significant margin across all evaluated models. Another interesting observation we made about the attention is it can already cover a good amount of programs when only using the top-10% of the input features and the increase of the coverage slows down when more features are selected. This indicates the important role the attention plays in helping models to learn the right features for prediction. As for the other two methods, SHAP's advantage over Integrated Gradients only stands out after the 50% mark, otherwise, their numbers are in the same ballpark. Overall, it's evident that none of those explanation methods are good at finding the .
This is an expected outcome because the criteria by which evaluates the importance of input features is fundamentally different than the above explanation methods. Specifically, uses sufficient, necessary and Minimum requirement whereas

the other three methods quantify the influence of features in mathematical terms (, gradients, SHAP values, or attention scores).

§.§ Explaining the Predictions of Code Models

We conduct a user study to evaluate our technique for producing explanations for the prediction of all four models. As described in Section <ref>, our technique finds training methods similar to a test method based on the AST distance between their . We also adopt a simple baseline that searches for training methods based on the AST distance of the entire method.

[morekeywords=Object, String]code/reverse-ori.java
A test method.

[morekeywords=Object, String]code/reverse-our.java
The closet found by our technique.

[morekeywords=Object, String]code/reverse-baseline.java
The closet found by baseline.

An example prediction produced by our technique and baseline.

fontupper=,drop shadow southwest,sharp corners]

* The system finds training examples that have similar structure (or substructure) to the test example.

* Given the similarity of the structure (or substructure), explanations that the system produce are accurate.

* As a user of the model, I find the system helpful in provide an insight of how models work.

* As a user of the model, I feel comfortable using this model along with the system providing the explanations.

* As a designer of the model, I find the system helpful in debugging models' mispredictions and improves their quality.

Questionnaire used in the study.

Procedure.  Each participant is given two sets of methods. One set contains 4 methods randomly selected from the test set of the three datasets, and each method is accompanied with 5 methods found to the closet by our technique on the corresponding training set.
As an example, we show a test method (Figure <ref>) accompanied by a training method (Figure <ref>) that is the closest found by our technique. We highlight their in the shadow box. Similarly, the other set presents the same content except that the 5 methods are found by the baseline approach. An example is shown in Figure <ref>. After reviewing a set of methods, each participant is given a set of questions to answer. The questionnaire is depicted in Figure <ref>. For each question, participants are given 5 choices to make: strong disagree, disagree, neutral, agree, and strongly agree. Each choice is interpreted as a score starting from 1 for strongly disagree all the way to 5 for strong agree. We also conduct an interview after the study during which we encourage them to give any comments/suggestions that they may have.

Participants.  We have recruited 32 data scientists from a high-tech company through an internal email thread and paid them $50 each for participating the study. Each participant has at least one year of Java programming experience. All of them have at least two years of experience in developing machine learning models at work. We have explained to each participant beforehand that our technique finds the training programs from which models learned their parameters for predicting the name of a particular test method, and they are asked to rate the quality of the explanations.

Results.  Table <ref> shows the results of the questionnaire. In particular, each row contains the average score to a question for our technique and baseline approach. It is clear that participants have rated our technique consistently higher than the baseline approach by a notable margin. In terms of the actual score, participants have given more than 3 to all questions indicating an overall positive attitude toward our technique. Specifically, for Questions 1 and 2, participants are very positive about the accuracy of the predictions found by our technique. For Question 3 and 5, participants also agree that the system would benefit both users and designers of the model by providing the rationale of model predictions. One participant even raises the possibility of performing re-training with examples generated based on the to improve the model accuracy. Question 4 is the only one to which participants reacted a bit more negatively. Therefore, we focus on this question in our post-study interview.

Participants' responses.
max width=1

Question     Our technique       Baseline
1     4.7      2.1
2     4.5      1.8
3     3.9      1.8
4     3.1      1.2
5     3.6      1.5

The main message we received from participants who give particularly low scores to this question is that even though the system gives accurate explanations, they won't be very helpful when models only seem to use almost random textual properties to predict. For example, one participant explained that once is explanation is given, albeit having a similar substructure of the test method, users still have to manually examine the rest of the program in order to decide if the explanation can really match the prediction of the test method. Therefore, having a model that learns the right features is also necessary.

As standard in user studies, we performed a t-test to evaluate the statistical significance of our results. The p-value of a two-tailed
t-test (assuming potentially unequal variance) comparing our technique against the baseline approach is $2 \times 10^{-6}$. This means
the probability that our technique has no influence on classification accuracy is less than 1 in 100,000, indicating our results are statistically significant.

§ RELATED WORK

The work closest to ours is <cit.>, which discovers that input programs can be reduced to significantly smaller code snippets for which models still make the correct predictions. Our work in fact surpasses <cit.> at many levels. Conceptually, we propose necessary requirement that has to satisfy in addition to the sufficient requirement. Technically, we show DD, which powers Sivand <cit.>, suffers from models' non-monotony. In contrast, our technique Reduce and Mutate is more precise in identifying the evidenced by our extensive evaluation. Empirically, we demonstrate the validity of 's approach in light of out-of-the distribution issues, whereas, Sivand is fundamentally flawed in dealing with the distribution shift between the training and query programs. Finally, we also present a novel application of the while <cit.> have not demonstrated any utility of their method. For the remainder of this section, we survey two lines of related work: attribution methods and models of code.

§.§ Attribution Methods

In machine learning field, attribution methods are usually classified into two categories: Perturbation-based and backpropagation-based. The former generates explanations by iteratively probing a trained machine learning model with different variations of the inputs. As a few representatives, <cit.> visualized the neural activations of individual layers of a deep convolutional network by occluding different segments of the input image and generating visualizations using a deconvolution network (DeConvNet). <cit.> use a conditional sampling
based multi-variate approach to generate more targeted explanations on image classification CNNs. The Interpretability Randomization Test (IRT) and the One-Shot Feature Test
(OSFT) introduced by <cit.> focuses on discovering important features by replacing the features with uninformative counter-factuals. To derive a representation that is understandable by humans, LIME <cit.> tries to find important contiguous superpixels (a patch of pixels) in a source image towards the output class. <cit.> present a unified framework, SHAP, which computes individual feature contributions towards that output prediction.

As for the backpropagation-based methods, Saliency maps <cit.> construct attributions by taking the absolute value of the partial derivative of the target output with respect to the input features.
Gradient$^\ast$Input <cit.> was then proposed to improve the sharpness of the attribution maps. The attribution is computed by taking the (signed) partial derivatives of the output with respect to the input and multiplying them with the input itself. Integrated Gradients <cit.>, similarly to Gradient$^\ast$Input, computes the partial derivatives of the output with respect to each input feature. However, while Gradient$^\ast$Input computes a single derivative, evaluated at the provided input $x$, Integrated Gradients computes the average gradient while the input varies along a linear path from a baseline $\hat{x}$ to $x$. Layer-wise Relevance Propagation (LRP) introduced by <cit.> is used to find relevance scores for individual features in the input data by decomposing the output predictions of the DNN. DeepLIFT <cit.>, similar to LRP, assigns each unit $i$ an attribution that represents the relative effect of the unit activated at the original network input $x$ compared to some other reference input.

§.§ Models of Code

Machine learning methods have been applied to a variety of programming language tasks such as method name prediction <cit.>, bug detection <cit.>, program repair <cit.>, and type inference <cit.>. Below we survey a few notable representatives. GGNN is the first to learn program embeddings from graph representations of source code. code2vec and code2seq are among the first in predicting method names in large-scale, cross-projecting settings. <cit.> is the first to use static program traces to learn function embeddings. <cit.> is the first to embed programs with their executions. <cit.> and <cit.> utilize sequence and graph models for program repair. <cit.> and  <cit.> are the noteworthy efforts in inferring loop invariant with deep learning models. CodeBERT <cit.> learns general-purpose representations that support downstream natural language-programming language applications.

§ CONCLUSION

In this paper, we present , an explanation method for models of code. Conceptually, we formalize the defining features that models use for predicting the label of input programs. Technically, we develop Reduce and Mutate and its implementation , which we use to explain code2vec, , GGNN, and CodeBERT.

We found that (1) is efficient and effective in finding ;

(2) through retraining, we confirm the validity of amid the distribution shift between training and queried programs;

(3) all models use simple syntactic or even lexical properties for prediction;
(4) some of the most popular attribution methods routinely miss out on the ;

(5) we present an example application of the revealed features: providing explanations for predictions of code models. Through a user study, we have shown the usefulness of our -based explanation method.

Here are my comments

1.  Regarding `$(t_{n}^{\tilde{P}})_{n\in\mathbb{N}} = (t_{m_{k}}^{P})_{k\in\mathbb{N}}$ where $(m_k)_{k\in\mathbb{N}}$ is a strictly increasing sequence of positive integers.' The formula doesn't restrict $n$, it may indicate ($1,2,3,4,5$) is a subsequence of ($5,4,3,2,1$).

I think the following two may be better:

$(t_{n}^{\tilde{P}})_{n\in\mathbb{N}} = (t_{m_{k}}^{P})_{k\in\mathbb{N}}$ where $(m_k)$ and $(n)$ are strictly increasing sequences of positive integers.

$(t_{k}^{\tilde{P}}) = (t_{m_{k}}^{P})_{k\in\mathbb{N}}$ where $(m_k)_{k\in\mathbb{N}}$ is a strictly increasing sequence of positive integers.

2. Regarding the proof of theorem 2.1, Is the following proof also ok (may reduce the space if it is ok)?

Because $P$ itself satisfies constituent, sufficient, and necessary requirement in Definition <ref>. It has to be the minimal requirement that $P$ violates.
Because the domain that contains all sets of statements/expressions whose token sequence is a subsequence of $P$'s is finite, and the size of the candidate programs will monotonically decreases (,
$\lvert (t_{n}^{P^\prime})_{n\in\mathbb{N}} \rvert < \lvert(t_{n}^{P})_{n\in\mathbb{N}}\rvert$,
$\lvert (t_{n}^{P^{\prime\prime}})_{n\in\mathbb{N}} \rvert < \lvert(t_{n}^{P^{\prime}})_{n\in\mathbb{N}}\rvert$, and so on), there will be a global minimal set of statements/expressions $\tilde{P}$ that satisfies all requirements in Definition <ref>, which implies that $\tilde{P}$ is the defining features for $P$. This contradicts the assumption that $\tilde{P}$ does not exist for $P$.

3. please double check my edits.

4. (1)  `However, they can compute the attributions for all input features in a single forward and backward pass through the network, resulted ( resulting ) in higher efficiency.'  (2) `We study code summarization models due to the tremendous impact they made to (on?) the programming language field.' (3) To sum up, an input feature’s satisfaction of the sufficient requirement does not give any indication on (of?) the necessity of the remaining features in the same input, thus the contradiction dissolves. (4) I change the only two occurrences of `defining feature' to `defining features'. (5) `we may only need to retrain (retain?) its syntactic structure without the specific identifier names.' (6) `finally RestoreNode reverts a node back (remove back?) to the saved node.' (7) I changed ` <cit.> is the first' to ` <cit.> are the first to discover'. But didn't change `<cit.> is a typical example in the image classification domain. In particular, it occludes different segments of an input image and visualizes the change in the activation of later layers. ' (8) `The function  first creates a subset with the parameter , ' The  here seems to be . (9) I removed 'a' in  'a smaller defining features'.  (10) 'Surprisingly, the defining features that sequence GNN uses is the smallest while it is the supposedly the most expressive model that also utilizes semantic properties of input programs.' shall we change it to 'Surprisingly, the defining features that sequence GNN uses are the smallest while the model is supposedly the most expressive one that also utilizes semantic properties of input programs.' (11) `we exhaustively generate the test candidates for each method before hand (beforehand?) in a parallel fashion'

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Allamanis, Barr, Ducousso, and GaoAllamanis
et al2020]
authorpersonMiltiadis Allamanis,
personEarl T. Barr, personSoline Ducousso, and
personZheng Gao. year2020.
Typilus: Neural Type Hints
(seriesPLDI '20). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Allamanis, Brockschmidt, and
KhademiAllamanis et al2018]
authorpersonMiltiadis Allamanis, personMarc
Brockschmidt, and personMahmoud Khademi.
Learning to Represent Programs with Graphs. In
booktitleInternational Conference on Learning
Representations (seriesICLR '18).

[Alon, Levy, and YahavAlon
et al2019a]
authorpersonUri Alon, personOmer Levy,
and personEran Yahav. year2019a.
code2seq: Generating Sequences from Structured
Representations of Code. In booktitleInternational
Conference on Learning Representations (seriesICLR '19).

[Alon, Zilberstein, Levy, and YahavAlon
et al2019b]
authorpersonUri Alon, personMeital
Zilberstein, personOmer Levy, and personEran
Yahav. year2019b.
code2vec: Learning Distributed Representations of
journalProceedings of the ACM on Programming
Languages volume3, numberPOPL
(year2019), pages1–29.

[Bach, Binder, Montavon, Klauschen, Müller,
and SamekBach et al2015]
authorpersonSebastian Bach, personAlexander
Binder, personGrégoire Montavon, personFrederick
Klauschen, personKlaus-Robert Müller, and
personWojciech Samek. year2015.
On Pixel-Wise Explanations for Non-Linear
Classifier Decisions by Layer-Wise Relevance Propagation.
journalPLOS ONE volume10,
number7 (date07 year2015),

[Bahdanau, Cho, and BengioBahdanau
et al2015]
authorpersonDzmitry Bahdanau,
personKyunghyun Cho, and personYoshua Bengio.
Neural machine translation by jointly learning to
align and translate. In booktitleInternational Conference
on Learning Representations (seriesICLR '15).

[Burns, Thomason, and TanseyBurns
et al2020]
authorpersonCollin Burns, personJesse
Thomason, and personWesley Tansey.
Interpreting Black Box Models via Hypothesis
Testing. In booktitleProceedings of the 2020 ACM-IMS on
Foundations of Data Science Conference (Virtual Event, USA)
(seriesFODS '20). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Chen, Kommrusch, Tufano, Pouchet, Poshyvanyk,
and MonperrusChen et al2019]
authorpersonZimin Chen, personSteve James
Kommrusch, personMichele Tufano, personLouis-Noël
Pouchet, personDenys Poshyvanyk, and personMartin
Monperrus. year2019.
Sequencer: Sequence-to-sequence learning for
end-to-end program repair.
journalIEEE Transactions on Software Engineering

[DeFreez, Thakur, and
Rubio-GonzálezDeFreez et al2018a]
authorpersonDaniel DeFreez, personAditya
Thakur, and personCindy Rubio-González.
Poster: Path-Based Function Embeddings. In
booktitle2018 IEEE/ACM 40th International Conference on
Software Engineering: Companion (seriesICSE-Companion
'18). IEEE, pages430–431.

[DeFreez, Thakur, and
Rubio-GonzálezDeFreez et al2018b]
authorpersonDaniel DeFreez, personAditya V
Thakur, and personCindy Rubio-González.
Path-based function embedding and its application
to error-handling specification mining. In
booktitleProceedings of the 2018 26th ACM Joint Meeting on
European Software Engineering Conference and Symposium on the Foundations of
Software Engineering (seriesESEC/FSE '18).

[Dinella, Dai, Li, Naik, Song, and
WangDinella et al2019]
authorpersonElizabeth Dinella, personHanjun
Dai, personZiyang Li, personMayur Naik,
personLe Song, and personKe Wang.
Hoppity: Learning Graph Transformations to Detect
and Fix Bugs in Programs. In booktitleInternational
Conference on Learning Representations (seriesICLR '19).

[Feng, Guo, Tang, Duan, Feng, Gong, Shou, Qin,
Liu, Jiang, and ZhouFeng et al2020]
authorpersonZhangyin Feng, personDaya Guo,
personDuyu Tang, personNan Duan,
personXiaocheng Feng, personMing Gong,
personLinjun Shou, personBing Qin,
personTing Liu, personDaxin Jiang, and
personMing Zhou. year2020.
CodeBERT: A Pre-Trained Model for Programming
and Natural Languages. In booktitleFindings of the
Association for Computational Linguistics: EMNLP 2020.
publisherAssociation for Computational Linguistics,
addressOnline, pages1536–1547.

[Fernandes, Allamanis, and
BrockschmidtFernandes et al2019]
authorpersonPatrick Fernandes,
personMiltiadis Allamanis, and personMarc
Brockschmidt. year2019.
Structured Neural Summarization. In
booktitleInternational Conference on Learning
Representations (seriesICLR '19).

[Glorot and BengioGlorot and Bengio2010]
authorpersonXavier Glorot and personYoshua
Bengio. year2010.
Understanding the difficulty of training deep
feedforward neural networks. In booktitleProceedings of the
Thirteenth International Conference on Artificial Intelligence and
Statistics (seriesProceedings of Machine Learning
Research), editorpersonYee Whye Teh and
personMike Titterington (Eds.), Vol. volume9.
publisherPMLR, addressChia Laguna Resort, Sardinia,
Italy, pages249–256.

[Hooker, Erhan, Kindermans, and KimHooker
et al2019]
authorpersonSara Hooker, personDumitru
Erhan, personPieter-Jan Kindermans, and personBeen
Kim. year2019.
A Benchmark for Interpretability Methods in Deep
Neural Networks. In booktitleProceedings of the 33rd
International Conference on Neural Information Processing Systems.
publisherCurran Associates Inc., addressRed Hook, NY,
USA, Article articleno873, numpages12 pages.

[Husain, Wu, Gazit, Allamanis, and
BrockschmidtHusain et al2019]
authorpersonHamel Husain, personHo-Hsiang
Wu, personTiferet Gazit, personMiltiadis Allamanis,
and personMarc Brockschmidt. year2019.
CodeSearchNet challenge: Evaluating the state of
semantic code search.
journalarXiv preprint arXiv:1909.09436

[John Philip and WestJohn Philip and
authorpersonD'Angelo John Philip and
personDouglas Brent West. year1997.
booktitleMathematical thinking: problem-solving and

[Lundberg and LeeLundberg and Lee2017]
authorpersonScott M Lundberg and
personSu-In Lee. year2017.
A Unified Approach to Interpreting Model
In booktitleAdvances in Neural Information
Processing Systems 30, editorpersonI. Guyon,
personU. V. Luxburg, personS. Bengio,
personH. Wallach, personR. Fergus,
personS. Vishwanathan, and personR. Garnett
(Eds.). publisherCurran Associates, Inc.,

[Misherghi and SuMisherghi and Su2006]
authorpersonGhassan Misherghi and
personZhendong Su. year2006.
HDD: Hierarchical Delta Debugging. In
booktitleProceedings of the 28th International Conference on
Software Engineering (seriesICSE ’06).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages142–151.

[Rabin, Bui, Wang, Yu, Jiang, and
AlipourRabin et al2021a]
authorpersonMd Rafiqul Islam Rabin,
personNghi D.Q. Bui, personKe Wang,
personYijun Yu, personLingxiao Jiang, and
personMohammad Amin Alipour. year2021a.
On the generalizability of Neural Program Models
with respect to semantic-preserving program transformations.
journalInformation and Software Technology
volume135 (year2021), pages106552.

[Rabin, Hellendoorn, and AlipourRabin
et al2021b]
authorpersonMd Rafiqul Islam Rabin,
personVincent J Hellendoorn, and personMohammad Amin
Alipour. year2021b.
Understanding Neural Code Intelligence Through
Program Simplification.
journalarXiv preprint arXiv:2106.03353

[Ribeiro, Singh, and GuestrinRibeiro
et al2016]
authorpersonMarco Tulio Ribeiro,
personSameer Singh, and personCarlos Guestrin.
"Why Should I Trust You?": Explaining the
Predictions of Any Classifier. In booktitleProceedings of
the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining (San Francisco, California, USA) (seriesKDD '16).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages1135–1144.

[Sakkas, Endres, Cosman, Weimer, and
JhalaSakkas et al2020]
authorpersonGeorgios Sakkas, personMadeline
Endres, personBenjamin Cosman, personWestley Weimer,
and personRanjit Jhala. year2020.
Type Error Feedback via Analytic Program Repair.
In booktitleProceedings of the 41st ACM SIGPLAN Conference
on Programming Language Design and Implementation (London, UK)
(seriesPLDI '20). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Shrikumar, Greenside, and KundajeShrikumar
et al2017a]
authorpersonAvanti Shrikumar, personPeyton
Greenside, and personAnshul Kundaje.
Learning Important Features Through Propagating
Activation Differences. In booktitleProceedings of the 34th
International Conference on Machine Learning
(seriesProceedings of Machine Learning Research),
editorpersonDoina Precup and
personYee Whye Teh (Eds.), Vol. volume70.
publisherPMLR, pages3145–3153.

[Shrikumar, Greenside, and KundajeShrikumar
et al2017b]
authorpersonAvanti Shrikumar, personPeyton
Greenside, and personAnshul Kundaje.
Learning Important Features through Propagating
Activation Differences. In booktitleProceedings of the 34th
International Conference on Machine Learning - Volume 70 (Sydney, NSW,
Australia) (seriesICML '17).
publisherJMLR.org, pages3145–3153.

[Shrikumar, Greenside, Shcherbina, and
KundajeShrikumar et al2016]
authorpersonAvanti Shrikumar, personPeyton
Greenside, personAnna Shcherbina, and personAnshul
Kundaje. year2016.
Not just a black box: Learning important features
through propagating activation differences.
journalarXiv preprint arXiv:1605.01713

[Si, Dai, Raghothaman, Naik, and SongSi
et al2018]
authorpersonXujie Si, personHanjun Dai,
personMukund Raghothaman, personMayur Naik, and
personLe Song. year2018.
Learning Loop Invariants for Program Verification.
In booktitleProceedings of the 32nd International Conference
on Neural Information Processing Systems (Montréal, Canada)
(seriesNIPS '18). pages7762–7773.

[Simonyan, Vedaldi, and ZissermanSimonyan
et al2014]
authorpersonKaren Simonyan, personAndrea
Vedaldi, and personAndrew Zisserman.
Deep inside convolutional networks: Visualising
image classification models and saliency maps. In
booktitleIn Workshop at International Conference on Learning

[Sundararajan, Taly, and YanSundararajan
et al2017]
authorpersonMukund Sundararajan, personAnkur
Taly, and personQiqi Yan. year2017.
Axiomatic Attribution for Deep Networks. In
booktitleProceedings of the 34th International Conference on
Machine Learning - Volume 70 (Sydney, NSW, Australia)
(seriesICML '17). publisherJMLR.org,

[Wang, Singh, and SuWang
et al2018]
authorpersonKe Wang, personRishabh Singh,
and personZhendong Su. year2018.
Dynamic Neural Program Embedding for Program
Repair. In booktitleInternational Conference on Learning
Representations (seriesICLR '18).

[Wang and SuWang and Su2020]
authorpersonKe Wang and personZhendong
Su. year2020.
Blended, Precise Semantic Program Embeddings. In
booktitleProceedings of the 41st ACM SIGPLAN International
Conference on Programming Language Design and Implementation
(seriesPLDI '20).

[Wang, Wang, Gao, and WangWang
et al2020]
authorpersonYu Wang, personKe Wang,
personFengjuan Gao, and personLinzhang Wang.
Learning Semantic Program Embeddings with Graph
Interval Neural Network.
journalProceedings of the ACM on Programming
Languages volume4, numberOOPSLA, Article
articleno137 (dateNov. year2020),
numpages27 pages.

[Wei, Goyal, Durrett, and DilligWei
et al2019]
authorpersonJiayi Wei, personMaruth Goyal,
personGreg Durrett, and personIsil Dillig.
LambdaNet: Probabilistic Type Inference using Graph
Neural Networks. In booktitleInternational Conference on
Learning Representations (seriesICLR '19).

[Yao, Ryan, Wong, Jana, and GuYao
et al2020]
authorpersonJianan Yao, personGabriel Ryan,
personJustin Wong, personSuman Jana, and
personRonghui Gu. year2020.
Learning Nonlinear Loop Invariants with Gated
Continuous Logic Networks. In booktitleProceedings of the
41st ACM SIGPLAN Conference on Programming Language Design and
Implementation (London, UK) (seriesPLDI '20).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages106–120.

[Zeiler, Taylor, and FergusZeiler
et al2011]
authorpersonMatthew D Zeiler, personGraham W
Taylor, and personRob Fergus.
Adaptive deconvolutional networks for mid and high
level feature learning. In booktitle2011 International
Conference on Computer Vision. IEEE, pages2018–2025.

authorpersonAndreas Zeller.
Yesterday, my program worked. Today, it does not.
journalACM SIGSOFT Software engineering notes
volume24, number6 (year1999),

[Zeller and HildebrandtZeller and
authorpersonAndreas Zeller and personRalf
Hildebrandt. year2002.
Simplifying and isolating failure-inducing input.
journalIEEE Transactions on Software Engineering
volume28, number2 (year2002),

[Zintgraf, Cohen, Adel, and WellingZintgraf
et al2017]
authorpersonLuisa M Zintgraf, personTaco S
Cohen, personTameem Adel, and personMax Welling.
Visualizing Deep Neural Network Decisions:
Prediction Difference Analysis. In booktitleInternational
Conference on Learning Representations (seriesICLR '17).

§ DEFINITION OF SUBSEQUENCE

A subsequence of <$a$> is a sequence <$b$> defined by $b_k=a_{n_k}$, where $n_1<n_2<...$ is an increasing sequence of indices <cit.>.

For example, if $a_n = 2n - 1$ and $n_k = k^2$, then $b_k = 2k^2 - 1$ <cit.>.

$n$     1     2     3     4     5     6     7     8     9

$a_n$     1     3     5     7     9     11     13     15     17

$k$     1               2                          3

$b_k$     1               7                          17

§ THE EXISTENCE OF

Given a prediction $L$ that $M$ makes for an input program $P$, the $\tilde{P}$ that models use to predict the label of $P$ always exists.

Assume otherwise, so that the $\tilde{P}$ does not exist for $P$. Because the body of $P$, $B_P$, satisfies constituent, sufficient, and necessary requirement in Definition 2.1. It has to be the minimum requirement that $B_P$ violates, meaning, there exists a set of statements/expressions $P^\prime$ that also satisfies all but the minimum requirement, and $\lvert (t_{n}^{P^\prime})_{n\in\mathbb{N}} \rvert < \lvert(t_{n}^{B_P})_{n\in\mathbb{N}}\rvert$. Since $P^\prime$ is not the either, we can infer that $P^\prime$ is also not minimum.Because the domain that contains all sets of statements/expressions whose token sequence is a subsequence of $P$'s is finite, and the size of the candidate programs will monotonically decreases (,
$\lvert (t_{n}^{P^\prime})_{n\in\mathbb{N}} \rvert < \lvert(t_{n}^{B_P})_{n\in\mathbb{N}}\rvert$,
$\lvert (t_{n}^{P^{\prime\prime}})_{n\in\mathbb{N}} \rvert < \lvert(t_{n}^{P^{\prime}})_{n\in\mathbb{N}}\rvert$, and so on), there will be a global minimum set of statements/expressions $\tilde{P}$ that satisfies all requirements in Definition <ref>, which implies that $\tilde{P}$ is the for $P$. This contradicts the assumption that $\tilde{P}$ does not exist for $P$.

§  EXAMPLES OF DELTA DEBUGGING

The motivating example includes nineteen tokens. At the first step, we split the program into two partitions: the first partition ($\Delta_1$) contains the first nine tokens () and the second one ($\Delta_2$) has the last ten tokens (, , , , ,  , , ). We proceed with $\Delta_2$ since it satisfies the sufficient and necessary requirement. Then, we split $\Delta_2$ into two partitions, and demonstrate the subsequent steps in Table <ref>.

An example from sequence GNN model without the monotonicity. $\Delta_i$ denotes partitions and $\nabla_i$ is the complement of $\Delta_i$. For simplicity, we use tokens to represent programs that are tested against the sufficient and necessary requirement at each step. The last column shows the requirements that partitions do not satisfy, but pass means the partitions satisfy both requirements.

max width=

2*cStep     2*cPartition     9c|Tokens     2*cResults

size       return      mItems      add      position      genItem      log      "add item"      position
1     $\Delta_3$      $\checkmark$      $\checkmark$      $\checkmark$     $\checkmark$      $\checkmark$                      Pass
2     $\Delta_4$                         $\checkmark$     $\checkmark$      $\checkmark$     $\checkmark$       Necessary
3     $\Delta_5$  = $\nabla_6$     $\checkmark$      $\checkmark$     $\checkmark$                                Both
4     $\Delta_6$  = $\nabla_5$                   $\checkmark$     $\checkmark$                          Both
5     $\Delta_7$      $\checkmark$                                            Both
6     $\Delta_8$            $\checkmark$                                      Both
7     $\Delta_9$                 $\checkmark$                                 Both
8     $\Delta_{10}$                        $\checkmark$     $\checkmark$                       Both
9     $\nabla_7$             $\checkmark$       $\checkmark$      $\checkmark$     $\checkmark$                       Sufficient
10     $\nabla_8$       $\checkmark$             $\checkmark$      $\checkmark$     $\checkmark$                       Sufficient
11     $\nabla_9$       $\checkmark$        $\checkmark$           $\checkmark$     $\checkmark$                       Sufficient
12     $\nabla_{10}$        $\checkmark$      $\checkmark$      $\checkmark$                                Sufficient
13     $\Delta_{11}$      $\checkmark$                                            Both
14     $\Delta_{12}$            $\checkmark$                                      Both
15     $\Delta_{13}$                 $\checkmark$                                 Both
16     $\Delta_{14}$                        $\checkmark$                           Both
17     $\Delta_{15}$                             $\checkmark$                       Both
18     $\nabla_{11}$             $\checkmark$       $\checkmark$      $\checkmark$     $\checkmark$                       Sufficient
19     $\nabla_{12}$       $\checkmark$             $\checkmark$      $\checkmark$     $\checkmark$                       Sufficient
20     $\nabla_{13}$       $\checkmark$        $\checkmark$           $\checkmark$     $\checkmark$                       Sufficient
21     $\nabla_{14}$        $\checkmark$      $\checkmark$      $\checkmark$          $\checkmark$                       Sufficient
22     $\nabla_{15}$        $\checkmark$      $\checkmark$      $\checkmark$       $\checkmark$                            Sufficient

§ AN EXAMPLE OF THE SUBTRACTION OPERATION IN THE MUTATE STEP

Figure <ref> gives a detailed illustration for subtracting  from the original program.

A illustration of the four-step process of subtracting  from our example program. (1) Figure (app-fig:subtraction1) presents the AST of the running example, and the AST of  in the bottom left corner. For brevity, the ASTs are simplified. (2) Figure (app-fig:subtraction2) highlights the overlapping nodes between the two ASTs. (3) Figure (fig:subtraction3) emphasizes the resultant AST after the overlapping nodes are removed, as a result,  and  become dangling nodes. (4) Figure (app-fig:subtraction4) connects  and  to the body of the method.

§ THE FUNCTIONALITY OF  AND

Algorithm <ref> gives a detailed illustration for  and  functions.
In  the  function, we first try removing the node, which comes from its first parameter, then check whether the resultant program satisfies both the sufficient and necessary requirement (Line <ref>). If it satisfies, we update the current program to the new one whose node is deleted (Line <ref>).
Similarly, in the   function, we will mutate the node into one with an out-of-vocabulary value (Line <ref>) and update the program if the resultant program satisfies the two requirements (Lines <ref> and <ref>).
Both  and  functions invoke   the  function, which constructs two programs for checking against the sufficient and necessary requirements, respectively. The function returns True only when the resultant program satisfy both requirements, otherwise it returns False.

[Foreach]ForeachEndForeach[1]foreach #1 doend foreach

Delete and mutate AST nodes.

[1]

$\Ne, \Rt, \OMT, \Ml$

new_root_del $\gets$ .Delete ()  remove node
new_root_del , , ,

Update (, new_root_del) update to the new program

$\Ne, \Rt, \OMT, \Ml$

new_root_mut $\gets$  .Replace (, ) replace node with oov
new_root_mut , , ,
Update (, new_root_mut)

$\Ne, \Rt, \OMT, \Ml$

program_suff $\gets$ Serialize ()checking against the sufficient requirement

.Predict (program_suff) != .Predict ()
False		does not satisfy the sufficient requirement
program_necc $\gets$ Subtract (, )checking against the necessary requirement

.Predict (program_necc) ==.Predict ()
False		does not satisfy the necessary requirement

§ PERFORMANCE OF RE-IMPLEMENTED MODELS

We have re-implemented code2vec, Sequence GNN, GGNN and
Table <ref>, <ref>, and <ref> show the performance of all re-implemented models is either comparable or superior to the originals.

Compare reimplementations (bolded) to originals for code2vec and Seq-GNN.

max width=

2*cModels     3c|Java-small     3c|Java-med     3cJava-large

Precision     Recall     F1     Precision     Recall     F1     Precision     Recall     F1
code2vec        18.51     18.74     18.62     38.12     28.31    32.49     48.15     38.40     42.73
code2vec    19.23     17.72     18.44     40.32     28.89    33.66     48.90     37.26     42.29

Seq-GNN        —    —    51.4     —    —   —    —    —    —
Seq-GNN    49.94     47.35     48.61     58.46     45.73    51.32     61.82     50.32     55.48

Compare reimplementations (bolded) to originals for GGNN.

2*Models       C# Datasets
GGNN      78.2
GGNN    78.0

Compare reimplementations (bolded) to originals for CodeBERT.

2*Models      CodeSearchNet
Smoothed BLEU score
CodeBERT     17.65
CodeBERT     17.66

§ ADDITION EDGES USED IN FERNANDES

Below we give the list of edges <cit.> incorporate into ASTs.

* NextToken connects each terminal node (syntax token) to its successor.

* LastRead connects a terminal node of a variable to all elements of the set of terminal nodes at which the variable could have been read last.

* LastWrite connects a terminal node of a variable to all elements of the set of syntax tokens at which the variable was could have been last written to.

* ComputedFrom connects a terminal node of a variable $v$ to all variable tokens occurring in $expr$ when $expr$ is assigned to $v$.

* LastLexicalUse chains all uses of the same variable.

* ReturnsTo connects  tokens to the method declaration.

* FormalArgName connects arguments in method calls to the formal parameters that they are matched to.

* GuardedBy connects every token corresponding to a variable (in the true branch of a  statement) to the enclosing guard expression that uses the variable.

* GuardedByNegation connects every token corresponding to a variable (in the false branch of a  statement) to the enclosing guard expression that uses the variable.

We exclude NextToken and ReturnsTo since they do not represent any semantic properties.

§ PERFORMANCE OF THE RE-TRAINED MODELS ON THE AUGMENTED DATASETS.

We have re-trained code2vec, Sequence GNN, GGNN and
CodeBERT on the manually labeled datasets.
Table <ref>, <ref>, and <ref> show the performance of all re-trained models is negligibly higher than  original models.

Compare code2vec and Seq-GNN before and after the retraining (bolded numbers denotes the results of retrained models).

max width=

2*cModels     3c|Java-small     3cJava-med

Precision     Recall     F1     Precision     Recall     F1
code2vec    19.23     17.72     18.44     40.32     28.89    33.66
code2vec    19.33     18.01     18.74     40.38     28.97    33.96
Seq-GNN    49.94     47.35     48.61     58.46     45.73    51.32
Seq-GNN    50.12     48.39     48.62     58.51     46.09    52.00

Compare GGNN before and after the retraining (bolded numbers denotes the results of the retrained model).

2*Models       C# Datasets
GGNN      78.0
GGNN    78.8

Compare CodeBERT before and after the retraining (bolded numbers denotes the results of the retrained model).

2*Models      CodeSearchNet
Smoothed BLEU score
CodeBERT     17.66
CodeBERT     17.91