
\section*{Acknowledgement}
This study has been done as coursework in the Department of Computer Science at the University of Houston (Course: COSC 6321 - Research Methods in Computer Science; Instructor: Omprakash D Gnawali). We organized an in-class conference (\href{https://sites.google.com/view/rq21}{\color{blue}{Research Quest 2021}}) and submitted our posters/papers as homework to the conference.

\section{Conclusion}
\label{sec:conclusion}

In this paper, we apply the syntax-guided program reduction technique, \textsc{Perses}\xspace, for reducing an input program while preserving the same prediction of the CI model.
The goal is to extract label-specific key input features of target labels for CI models from syntax-guided reduced programs.
We evaluate \textsc{Perses}\xspace on two popular CI models across four types of input programs for the method name prediction task.
Our results suggest that the syntax-guided program reduction technique (\textsc{Perses}\xspace) significantly outperforms the syntax-unaware program reduction technique (Delta-Debugging\xspace) in reducing different input programs.
Moreover, we extract key input features that CI models learn for a target label, by reducing some input programs of that label using \textsc{Perses}\xspace. The result shows that \textsc{Perses}\xspace mostly keeps label-specific key input features in its syntax-guided reduced programs than in Delta-Debugging\xspace's syntax-unaware reduced programs.
We also observe that the syntax-guided candidate programs are more vulnerable to adversarial transformation when renaming the key tokens in programs.
By identifying those key input features, we can better understand the learned behaviors of CI models from multiple explanations, which may improve the trustworthiness of models to correct prediction.

\section{Introduction}
\label{sec:introduction}

Deep neural networks have exaggerated their capability to reduce the burden of feature engineering in complex domains, including code intelligence \cite{allamanis2018survey, sharma2021survey}. While the performance of neural models for intelligent code analysis continues to improve, our understanding of what relevant features they learn for correct classification is largely unknown. Therefore, in this paper, we aim to extract key input features that code intelligence models learn for the target label.


A neural code intelligence (CI) model is a deep neural network that takes a program as input and predicts certain properties of that program as output, for example, predicting method name \cite{allamanis2015suggesting}, variable name \cite{allamanis2018ggnn}, or type \cite{hellendoorn2018type} from a program body.
Recent studies have shown that state-of-the-art CI models do not always generalizable to other experiments \cite{kang2019generalizability, rabin2020evaluation}, heavily rely on specific tokens \cite{compton2020obfuscation, rabin2021sivand, suneja2021probing} or structures \cite{rabin2021code2snapshot}, can learn noisy data points \cite{allamanis2019duplication, rabin2021memorization}, and are often vulnerable to semantic-preserving adversarial examples \cite{yefet2020adversarial, rabin2021generalizability}.
Therefore, it is important to know what input features those CI models learn for making correct predictions. The lack of understanding would hinder the trustworthiness to correct classification given by CI models.
Hence, researchers are interested to extract relevant input features that CI models learn for the target label. Such transparency about learned input features is key for wider adoption and application in critical settings such as vulnerability detection or auto-fix suggestion.


Models usually represent an input program as continuous distributed vectors that are computed after training on a large volume of programs. From that, understanding what input features a black-box model has learned is very challenging. For example, code2vec model \cite{alon2019code2vec} learns to represent an input program as a single fixed-length high dimensional embeddings, however, the meaning or characteristics of each dimension are not defined.
An attention-based approach can be used to enhance important code elements in a program. For example, \citet{bui2019autofocus} identify relevant code elements by perturbing statements of the program and combining corresponded attention and confidence scores. However, the attention-based approach poorly correlates with key elements and suffers from a lack of explainability. Recent studies \cite{suneja2021probing, rabin2021sivand, wang2021demystifying} show that the reduction-based approach can extract relevant input features in programs with offering a better explainability.


Several works have already been conducted by researchers for finding relevant input features in models' inference. \citet{allamanis2015suggesting} use a set of hard-coded features from source code and show that extracting relevant features is essential for learning effective code context. \citet{rabin2020demystifying} attempt to find key input features of a label by manually inspecting some input programs of that label. However, the manual inspection cannot be applied to a large dataset due to the vast number of target labels. \citet{suneja2021probing} and \citet{rabin2021sivand} apply a syntax-unaware program reduction technique, Delta-Debugging\xspace \cite{zeller2002dd}, to reduce the size of input programs in order to find the minimal snippet that a model needs to maintain its prediction. However, this approach creates a large number of invalid and unnatural programs as it does not follow the syntax of programs during the reduction, which adds significant overhead to the explainability of models. While state-of-the-art approaches use a manual inspection or syntax-unaware program reduction technique, we focus on applying the syntax-guided program reduction technique. In particular, we adopt \textsc{Perses}\xspace \cite{sun2018perses}, a syntax-guided program reduction technique, to reduce the size of an input program.


In this paper, we apply a syntax-guided reduction technique, rather than syntax-unaware reduction technique, to remove irrelevant parts from an input program and keep the minimal snippet that the CI model needs to maintain its prediction.
Given a model and an input program, our approach adopts \textsc{Perses}\xspace \cite{sun2018perses}, a syntax-guided reduction technique, to reduce the size of an input program. The approach continues reducing the input program as long as the model maintains the same prediction on the reduced program as on the original program.
The main insight is that, by reducing some input programs of a label, we may better extract key input features of that target label.
As the syntax-guided technique follows the syntax of input programs, it will always generate valid input programs. Therefore, the approach is more likely to reach the minimal snippet in a smaller number of reduction steps, which will decrease the total reduction time. Moreover, following a syntax-guided technique, the approach can reveal more realistic key input features for the target label.
However, for supporting a programming language data, the syntax-guided technique needs to leverage knowledge about program syntax for avoiding generating syntactically invalid programs.


An experiment with two CI models and four types of input programs reveals that the syntax-guided \textsc{Perses}\xspace performs very well compared to the syntax-unaware Delta-Debugging\xspace. While \textsc{Perses}\xspace can generate $100\%$ valid programs, Delta-Debugging\xspace generates around $10\%$ valid programs only. On average, \textsc{Perses}\xspace removes $20\%$ more tokens, takes $70\%$ fewer reduction steps, and spends $2x$ less reduction time than Delta-Debugging\xspace for reducing an input program.
Furthermore, our results show that we can find label-specific key input features by reducing input programs using \textsc{Perses}\xspace, which can provide additional explanation for a prediction and highlight the importance of key input features in programs by triggering $10\%$ more misprediction with $50\%$ fewer adversarial examples.

\noindent\textbf{Contributions.}
This paper makes the following contributions.
\begin{itemize}
    \item We apply a syntax-guided program reduction technique for reducing an input program while preserving the same prediction of the CI model.
    \item We provide a systematic comparison between the syntax-guided program reduction and the syntax-unaware program reduction techniques.
    \item Our results suggest that the syntax-guided program reduction technique significantly outperforms the syntax-unaware program reduction technique.
    \item We highlight key input features that CI models learn for the target label using syntax-guided program reduction.
    \item We show that different program reduction techniques may provide additional explanations for a specific prediction.
\end{itemize}


\section{Design and Implementation}
\label{sec:design}

\input{resources/workflow}

This section describes our approach of extracting input features for code intelligence (CI) models by syntax-guided program reduction. We use \textsc{Perses}\xspace \cite{sun2018perses} as the syntax-guided program reduction technique in our study. We first provide an overview of how \textsc{Perses}\xspace works and then describe how we adopt it in the workflow of our approach.

\medskip
\Part{\textsc{Perses}\xspace.}
\citet{sun2018perses} have proposed the framework for syntax-guided program reduction called \textsc{Perses}\xspace. 
Given an input program, the grammar of that programming language, and the output criteria, \textsc{Perses}\xspace reduces the input program with respect to the grammar while preserving the output criteria. It mainly follows the below steps.
\begin{itemize
    \item It first parses the input program into a parse tree by normalizing the definition of grammar. 
    \item Then it traverses the tree and determines whether a tree node is deletable (such as follows the grammar and preserves the output criteria). If yes, it prunes the sub-tree from that node and generates a valid reduced program, else it ignores that node and avoids generating invalid programs. Thus, in each iteration of reduction, it ensures generating syntactically valid program variants that preserves the same output criteria. 
    \item Next, the deletion of one node may enable the deletion of another node. Therefore, \textsc{Perses}\xspace is repeatedly applied to the reduced program until no more tree nodes can be removed, which is known as fixpoint mode reduction.
    \item The final reduced program is called 1-tree-minimal, and any further attempts to reduce the program would generate an invalid program or change the output criteria.
\end{itemize}
We integrate the \textsc{Perses}\xspace as a black-box framework in our approach for extracting input features of CI models.

\medskip
\Part{Workflow.}
Figure~\ref{fig:approach} depicts a high-level view of the workflow in our proposed methodology.
Given a set of input programs, our approach reduces each input program using \textsc{Perses}\xspace while preserving the same prediction by the CI model. 
The approach removes irrelevant parts from an input program and keeps the minimal code snippet that the CI model needs to maintain its prediction. 
The main insight is that, by reducing some input programs of a target label, we can identify key input features of the CI model for that target label.
Our approach follows the below steps.
\begin{itemize
    \item Given an input program $P$ and a CI model $M$, our approach first record the prediction $y$ (i.e. predicted method name) given by the CI model $M$ on the input program $P$, such as $y = M(P)$.
    \item Using \textsc{Perses}\xspace, we then generate a candidate reduced program $R'$ by removing some nodes from the tree of the input program $P$, such as $R' = \textsc{Perses}\xspace(P)$.
    \item If the candidate reduced program $R'$ does not hold the same prediction $y$ by the CI model $M$ (i.e. $y \neq M(R')$), we reject this candidate program and create another candidate program by removing some other nodes from the tree of the input program.
    \item If the candidate reduced program $R'$ preserves the same prediction $y$ by the CI model $M$ (i.e. $y = M(R')$), we continue reduction and iteratively search for the final reduced program $R$ that produces the same prediction $y$.
    \item The final reduced program is 1-tree-minimal, which contains the key input features that the CI model must need for making the correct prediction $y$.
\end{itemize}
After reducing a set of input programs of a target label, we extract the node type and token value from the abstract syntax tree (AST) of each reduced program.
Every extracted element from reduced programs is considered as a \textit{candidate} input feature.
The most common elements are identified as label-specific \textit{key} input features and other uncommon elements are identified as input-specific \textit{sparse} features.


\medskip
\Part{Implementation.}
Our approach is model-agnostic and can be applied for various tasks and programming datasets.
In this paper, for experimentation of our approach, we study two well-known code intelligence models (\textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace), a popular code intelligence task (\textsc{MethodName}\xspace) and one commonly used programming language dataset (\textsc{Java-Large}\xspace) with different types of input programs. This section outlines all of these.


\subsubsection{Task}
We use the method name prediction (\textsc{MethodName}\xspace \cite{allamanis2015suggesting}) task in this study. 
This task is commonly used by researchers in the code intelligence domain for various applications such as code summarization \cite{allamanis2015suggesting,allamanis2016summarization}, representation learning \cite{alon2019code2vec,alon2019code2seq}, neural testing \cite{kang2019generalizability,yefet2020adversarial,rabin2021generalizability}, feature extraction \cite{rabin2021sivand,wang2021demystifying}, and so on \cite{allamanis2018survey,sharma2021survey}.
In the \textsc{MethodName}\xspace task, a model attempts to predict the name of a method from its body. \Cref{fig:example} shows an example of \textsc{MethodName}\xspace task, where given the following code snippet: ``\texttt{void f(int a, int b) \{int temp = a; a = b; b = temp;\}}'', the \textsc{Code2Vec}\xspace model correctly predicts the method's name as ``\texttt{swap}''.

\subsubsection{Models}
We use the \textsc{Code2Vec}\xspace~\cite{alon2019code2vec} and \textsc{Code2Seq}\xspace~\cite{alon2019code2seq} code intelligence\xspace models for \textsc{MethodName}\xspace task. Both models use paths from abstract syntax trees (AST) to encode a program. Given a sample expression ``\texttt{a = b;}'', an example of path context in AST is ``\texttt{a, <NameExpr ↑ AssignExpr ↓ IntegerLiteralExpr>, b}''.
\begin{itemize}
    \item \textsc{Code2Vec}\xspace. This model extracts a bag of path-context from the AST of the program where each path-context includes a pair of terminal nodes and the corresponding path between them. The model learns embeddings of these path-contexts during training and uses an attention mechanism to aggregate multiple path-contexts to a single code vector. The code vector is used as a representation of the program for making a prediction.
    \item \textsc{Code2Seq}\xspace. This model also extracts a bag of path-context from the AST of the program but it sub-tokenized each path-context. The \textsc{Code2Seq}\xspace model uses a bi-directional LSTM to encode paths node-by-node, and another LSTM to decode a target sequence one-by-one.
\end{itemize}

\input{resources/methodname}
\subsubsection{Dataset}
For the \textsc{MethodName}\xspace task, we use the \textsc{Java-Large}\xspace dataset \cite{alon2019code2seq}. This dataset contains a total of $9,500$ Java projects from GitHub, where $9,000$ projects are for the training set, $200$ projects for the validation set, and $300$ projects for the test set. Using training set and validation set, we train both the \textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace models.


\subsubsection{Input Types}
The dataset from GitHub is often imbalanced and contains different sizes and frequencies of input programs. Therefore, we choose different types of input programs from the \textsc{Java-Large}\xspace test set to evaluate the effectiveness of our approach in terms of reduction and feature extraction.

\begin{itemize}
    \item Frequent Methods: We randomly sample a total of $100$ input programs from the most occurring method names.
    \item Rare Methods: We randomly sample a total of $100$ input programs from the least occurring method names.
    \item Smaller Methods: We randomly sample a total of $100$ input programs that contains less than $10$ lines of code.
    \item Larger Methods: We randomly sample a total of $50$ input programs that has around $100$ lines of code.
\end{itemize}

Moreover, to demonstrate the label-specific key input features, we select correctly predicted input programs from the ten most frequent labels of the \textsc{Java-Large}\xspace test set for feature extraction. Those labels (methods) are: equals, main, setUp, onCreate, toString, run, hashCode, init, execute, and get.

\subsubsection{Syntax-unaware Reduction Technique}
We use the Delta-Debugging\xspace algorithm as the syntax-unaware program reduction technique in this study. \citet{zeller2002dd} have proposed the Delta-Debugging\xspace algorithm to reduce the size of an input program. The algorithm iteratively splits an input program into multiple candidate programs by removing parts of the input program. The algorithm then checks if any resulting candidate program preserves the prediction of the model on the original input program. When the algorithm finds a candidate satisfying the property, it uses the candidate as the new base to be reduced further. Otherwise, the algorithm increases the granularity for splitting, until it determines that the input program cannot be reduced further.

\begin{itemize}
    \item \textit{DD-Token}: In the token level approach, Delta-Debugging\xspace reduces the size of an input program token by token. We mostly use the \textit{DD-Token} as the default baseline for Delta-Debugging\xspace in this study.
    \item \textit{DD-Char}: In the char level approach, Delta-Debugging\xspace reduces the size of an input program char by char. We use the \textit{DD-Char} approach to provide an additional explanation in \Cref{sec:results_explanation} and \Cref{code:explanation_main}.
\end{itemize}

\citet{rabin2021sivand} described more detail on how the Delta-Debugging\xspace technique is adopted in the workflow of reducing input programs for CI models.


\section{Related Work}
\label{sec:related}

There has been some work in the area of code intelligence that focuses on the understanding of what relevant features a black-box model learns for correct predictions.
While some work \cite{compton2020obfuscation, rabin2019tnpa, kang2019generalizability, yefet2020adversarial, rabin2021generalizability, suneja2021probing, rabin2021sivand} studies the reliance of models on specific features, many works \cite{allamanis2015suggesting, bui2019autofocus, rabin2020demystifying, suneja2021probing, rabin2021sivand, wang2021demystifying} focus on finding relevant features for explaining models' prediction.

\subsection{Learning Representation of Source Code}
An input program is usually represented as vector embeddings for processing and analyzing by neural models. \citet{allamanis2014learning} introduced a framework that processed token sequences and abstract syntax trees of code to represent the raw programs. \citet{alon2019code2vec} proposed an attention-based neural model that uses a bag of path-context from abstract syntax tree for representing any arbitrary code snippets. \citet{allamanis2018ggnn} constructed data and control flow graphs from programs to encode a code snippet. \citet{hellendoorn2018type} proposed an RNN-based model using sequence-to-sequence type annotations for type suggestion.
There are some surveys on the taxonomy of models that exploit the source code analysis \cite{allamanis2018survey,sharma2021survey}. \citet{chen2019embeddings} also provide a survey that includes the usage of code embeddings based on different granularities of programs. However, these models are often black-box and do not provide any insight on the meaning or characteristic of learned embeddings. What features or patterns these embeddings represent are largely unknown. In this work, we extract key input features that a model learns for predicting a target label as an explanation of learned embeddings.

\subsection{Reliance on Specific Features}
Models often learn irrelevant features, simple shortcuts, or even noise for achieving target performance.
\citet{compton2020obfuscation} show that the code2vec embeddings highly rely on variable names and cannot embed an entire class rather than an individual method. They investigate the effect of obfuscation on improving code2vec embeddings that better preserves code semantics. They retrain the code2vec model with obfuscated variables to forcing it on the structure of code rather than variable names and aggregate the embeddings of all methods from a class.
Following the generalizability of word embeddings, \citet{kang2019generalizability} assess the generalizability of code embeddings in various software engineering tasks and demonstrate that the learned embeddings by code2vec do not always generalizable to other tasks beyond the example task it has been trained for.
\citet{rabin2021generalizability} and \citet{yefet2020adversarial} demonstrate that the models of code often suffer from a lack of robustness and be vulnerable to adversarial examples. They mainly introduce small perturbations in code for generating adversarial examples that do not change any semantics and find that the simple renaming, adding or removing tokens changes model's predictions.
\citet{suneja2021probing} uncover the model’s reliance on incorrect signals by checking whether the vulnerability in the original code is missing in the reduced minimal snippet. They find that model captures noises instead of actual signals from the dataset for achieving high predictions. \citet{rabin2021sivand} demonstrates that models often use just a few simple syntactic shortcuts for making prediction. \citet{rabin2021memorization} also show that models can fit noisy training data with excessive parameter capacity. 
As models often learn noise or irrelevant features for achieving high prediction performance, the lack of understanding of what input features models learn would hinder the trustworthiness to correct classification. Such opacity is substantially more problematic in critical applications such as vulnerability detection or auto-fix suggestion. In this work, we extract key input features for CI models in order to provide better transparency and explaining the predictions.

\subsection{Extracting Relevant Input Features}
Several kinds of research have been done in finding relevant input features for models of source code.
\citet{allamanis2015suggesting} exhibit that extracting relevant features is essential for learning effective code context. They use a set of hard-coded features from source code that integrate non-local information beyond local information and train a neural probabilistic language model for automatically suggesting names. However, extracting hard-coded features from source code may not be available for arbitrary code snippets and in dynamically typed languages.
\citet{bui2019autofocus} propose a code perturbation approach for interpreting attention-based models of source code. It measures the importance of a statement in code by deleting it from the original code and analyzing the effect on predicted outputs. However, the attention-based approach often poorly correlates with key elements and suffers from a lack of explainability.
\citet{rabin2020demystifying} attempt to find key input features of a label by manually inspecting some input programs of that label. They extract handcrafted features for each label and train simple binary SVM classification models that achieves highly comparable results to the higher dimensional code2vec embeddings for the method naming task. However, the manual inspection cannot be applied to a large dataset.
\citet{wang2021demystifying} propose a mutate-reduce approach to find key features in the code summarization models.
\citet{suneja2021probing} and \citet{rabin2021sivand} apply a syntax-unaware program reduction technique, Delta Debugging \cite{zeller2002dd}, to find minimal snippet which a model needs to maintain its prediction. By removing irrelevant parts to a prediction from the input programs, the authors aim to better understand important features in the model inference. 
However, the syntax-unaware approach creates a large number of invalid and unnatural programs during the reduction as it does not follow the syntax of programs, thus increases the total steps and time of reduction. In this work, we apply a syntax-guided program reduction technique that overcomes the overhead raised by the syntax-unaware technique.




\section{Results}
\label{sec:results}

In this section, we present the average result of our experiments on the \textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace models and the \textsc{Java-Large}\xspace dataset for different input types.

\input{results/comparison}
\subsection{Comparative Analysis}
Here, we provide a systematic comparison between the syntax-guided program reduction technique and the syntax-unaware program reduction technique.
In particular, we compare the syntax-guided \textsc{Perses}\xspace and the syntax-unaware Delta-Debugging\xspace in terms of token reduction, valid candidates, reduction steps and reduction time.

\subsubsection{Token Reduction}
\label{sec:results_reduction}
The goal of \textsc{Perses}\xspace and Delta-Debugging\xspace is to remove irrelevant tokens from an input program as much as possible while preserving the same prediction of the CI model. 
\Cref{fig:reduction} shows their such ability in reducing the size of the original input programs for different input types. We can see that, for all input types, \textsc{Perses}\xspace reduces more tokens from an input program than Delta-Debugging\xspace. On average, \textsc{Perses}\xspace removes $20\%$ more tokens from an input program than Delta-Debugging\xspace. The difference is most significant (around $30\%$) in \textsc{Large}\xspace input types and less significant (around $5\%$) in \textsc{Rare}\xspace input types.
This result suggests that \textsc{Perses}\xspace is more powerful than Delta-Debugging\xspace in reducing the size of an input program.

\subsubsection{Valid Candidates}
\label{sec:results_valid}
In each reduction step, \textsc{Perses}\xspace and Delta-Debugging\xspace create a candidate program after removing some irrelevant tokens from an input program, and continue for further reduction. 
\Cref{fig:valid} shows their effectiveness in generating valid candidate programs during reduction. For all input types, \textsc{Perses}\xspace always reduces to a valid candidate program (thus, $100\%$ valid candidates) as it follows the syntax of programs during reduction. However, in most cases, Delta-Debugging\xspace reduces to an invalid candidate program (only around $10\%$ valid candidates) as it does not follow the syntax of programs. Therefore, after each invalid step, Delta-Debugging\xspace backtracks to the previous step and generates another candidate program by removing tokens from some other parts of the program, which increases the overhead in total reduction steps and reduction time.

\subsubsection{Reduction Steps}
\label{sec:results_steps}
The reduction is applied repeatedly to an input program until finding the final minimal program, from where no more tokens can be removed. 
From \Cref{fig:steps}, we can see that \textsc{Perses}\xspace on average can reach the final minimal program within $5$ reduction steps. However, Delta-Debugging\xspace makes around $20$ reductions in \textsc{Frequent}\xspace-\textsc{Rare}\xspace-\textsc{Small}\xspace input types and more than $50$ reductions in \textsc{Large}\xspace input type, to reach the final minimal program. The Delta-Debugging\xspace reduces an input program by a sequence of tokens where \textsc{Perses}\xspace can prune an entire sub-tree from AST. Thus, \textsc{Perses}\xspace takes a much lower number of reduction steps than Delta-Debugging\xspace to reach the final minimal program.

\subsubsection{Reduction Time}
\label{sec:results_time}
We now compare the average time taken by \textsc{Perses}\xspace and Delta-Debugging\xspace for reducing an input program. As Delta-Debugging\xspace takes excessive invalid steps, \textsc{Perses}\xspace is expected to spend less time for program reduction.
\Cref{fig:time} shows that, for all input types, \textsc{Perses}\xspace reduces an input program faster than Delta-Debugging\xspace, specially in \textsc{Large}\xspace input type. In \textsc{Frequent}\xspace-\textsc{Rare}\xspace-\textsc{Small}\xspace input types, both \textsc{Perses}\xspace and Delta-Debugging\xspace spend less than $2$ minutes to reduce an input program and comparatively \textsc{Perses}\xspace takes $30$ seconds less time than Delta-Debugging\xspace. In \textsc{Large}\xspace input types, Delta-Debugging\xspace spends around $17$ minutes for the reduction of a large program but \textsc{Perses}\xspace takes only $8$ minutes, which is around $50\%$ less than Delta-Debugging\xspace.

\observation{\textsc{Perses}\xspace allows more token removal than Delta-Debugging\xspace and always creates valid candidate programs. Compared to Delta-Debugging\xspace,  \textsc{Perses}\xspace is more likely to reach the final minimal program in a smaller number of reduction steps, which decreases the total reduction time.}

\input{results/feature_summary}
\input{results/feature_list}
\subsection{Label-Specific Key Input Features}
\label{sec:results_features}

Here, we provide the summary of extracted input features that CI models learn for predicting the target method name. In our experiment, we consider all tokens in reduced programs as \textit{candidate} tokens. A label-specific \textit{key} input feature is a candidate token that appears in at least $50\%$ of reduced programs, where other infrequent tokens are input-specific \textit{sparse} features. 
For brevity and page limit, we only show the Top-10 most frequent methods in \Cref{table:feature_summary} and \Cref{table:feature_list}.

From \Cref{table:feature_summary}, considering both \textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace models, we can see that both \textsc{Perses}\xspace and Delta-Debugging\xspace identify around $50$ tokens, in total, as label-specific key input features in Top-10 methods.
However, Delta-Debugging\xspace contains a total of $324$ candidate tokens in reduced programs, which is $1.36$x time higher than \textsc{Perses}\xspace that contains a total of $238$ candidate tokens.
In some methods, i.e. `equals' and `setUp', the total number of candidate tokens in Delta-Debugging\xspace reduced programs is almost $2$x time higher than the candidate tokens in \textsc{Perses}\xspace reduced programs. This shows that the tokens found from the reduced programs of Delta-Debugging\xspace are more input-specific while the tokens found from the reduced programs of \textsc{Perses}\xspace are more label-specific.

Furthermore, \Cref{table:feature_list} shows the label-specific key input features (sorted by their frequency) extracted by Delta-Debugging\xspace and \textsc{Perses}\xspace from its reduced programs. These label-specific key input features can help to understand the prediction of the CI model for a target label. For example, Delta-Debugging\xspace and \textsc{Perses}\xspace reveal that ``\texttt{void, args, String, Exception}'' are key features for the `main' method. It highlights that a sample input program containing those tokens is more likely to be predicted as the `main' method by CI models.



\observation{\textsc{Perses}\xspace reveals more label-specific key input features in its syntax-guided reduced programs, while Delta-Debugging\xspace contains more input-specific sparse features in its syntax-unaware reduced programs.}

\input{results/ex_explanation_main}
\subsection{Multiple Explanation for a Specific Prediction}
\label{sec:results_explanation}

Different program simplification approaches, i.e., Delta-Debugging\xspace and \textsc{Perses}\xspace, provide a different set of key features for a target label by a CI model (\Cref{table:feature_list}). Those different features can help us to find multiple explanations for a specific prediction. 
For instance, the \textsc{Code2Seq}\xspace predicts the code snippet in \Cref{code:explanation_main}a as the \texttt{main} method. 
The Delta-Debugging\xspace with char-based program reduction (DD-Char) gives the minimal program in \Cref{code:explanation_main}b, that \textsc{Code2Seq}\xspace can predict as \texttt{main}. We can see the presence of the \texttt{Main} identifier in the method body of \Cref{code:explanation_main}b which is one of the important tokens for the target prediction. On the other hand, the Delta-Debugging\xspace with token-based program reduction (DD-Token) gives the minimal program in \Cref{code:explanation_main}c, which suggests the argument \texttt{args} has an important role in the target prediction. However, with the AST-based program reduction (\textsc{Perses}\xspace), the minimal program is \Cref{code:explanation_main}d that highlights the signature of the method, for which \textsc{Code2Seq}\xspace still can predict the same target label. Having these multiple explanations can improve the transparency of models inference.

\observation{Different program reduction techniques may provide additional explanations for better transparency of a specific prediction.}

\input{results/key_adversarial}
\subsection{Key Targeted Adversarial Attacks on Models}
\label{sec:results_adverserial}

Here, we highlight the importance of key input features in programs by evaluating the adversarial generalizability \cite{rabin2021generalizability} or robustness \cite{yefet2020adversarial} of CI models in terms of the extracted key input features. We generate adversarial examples by applying semantic-preserving variable renaming transformation on programs, similar to \cite{rabin2021generalizability}, where we separately change each variable and all of its occurrences in the program with token \texttt{var}. We particularly compare the prediction of CI models before and after the variable renaming. In this experiment, we generate three types of adversarial sets: actual set, key set, and reduced set. First, in actual set, we target the actual initial programs and generate candidate transformed programs by considering all variables. Second, in key set, we also target the actual initial programs but generate candidate transformed programs by considering variables that occur in the key feature list. Third, in reduced set, we directly target the reduced programs for generating candidate transformed programs. 
The results of change in prediction (misprediction) for variable renaming transformation are shown in \Cref{table:key_adversarial}. 

According to \Cref{table:key_adversarial}, on average, the number of generated candidate transformed programs from the actual set are around $3x$ times higher than the initial programs, however, only $12\%$ of them trigger misprediction. Next, the number of generated candidate transformed programs from the key set are around $1.5x$ times higher than the initial programs and trigger $22\%$ misprediction. Although the key adversarial set contains $50\%$ less candidate transformed programs than the actual adversarial set, they trigger $10\%$ more misprediction. On the other hand, the reduced programs are the minimal program that CI models keep for preserving their target prediction. Therefore, the number of generated candidates transformed programs from the reduced set are the lowest as there are fewer tokens to apply transformations. However, the transformation on reduced programs is more powerful and triggers the highest percentage of misprediction. Moreover, comparing between Delta-Debugging\xspace and \textsc{Perses}\xspace, in most cases, \textsc{Perses}\xspace generated candidates transformed programs shows a higher rate of misprediction than Delta-Debugging\xspace. 

\observation{The adversarial programs based on key input features trigger $10\%$ more misprediction with $50\%$ fewer candidates. The \textsc{Perses}\xspace generated candidate programs are more vulnerable to adversarial transformation than Delta-Debugging\xspace, thus, highlighting the importance of key input features in programs.}






\section{Implementation}

To implement and evaluate our approach, we study two well-known code intelligence models (\textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace), a popular code intelligence task (\textsc{MethodName}\xspace) and one commonly used programming language dataset (\textsc{Java-Large}\xspace) with different type input programs. However, our approach can be applicable to other models, tasks, and programming languages.


\subsection{Task:}
We use the popular code intelligence task: method name prediction (\textsc{MethodName}\xspace \cite{allamanis2015suggesting}) in this study. This task is commonly used by researchers in the code intelligence domain for various applications such as code summarization \cite{allamanis2015suggesting,allamanis2016summarization}, representation learning \cite{alon2019code2vec,alon2019code2seq}, neural testing \cite{kang2019generalizability,yefet2020adversarial,rabin2021generalizability}, feature extraction \cite{rabin2021sivand,wang2021demystifying}, and so on \cite{allamanis2018bigcode, allamanis2019duplication}.
In this \textsc{MethodName}\xspace task, a model attempts to predict the name of a method from its body. For example, given the following code snippet: ``\texttt{void f(int a, int b) \{int temp = a; a = b; b = temp;\}}'', a model aims to predict the method's name as ``\texttt{swap}''.





\subsection{Model:}
We use two well-known code intelligence\xspace models for \textsc{MethodName}\xspace task: \textsc{Code2Vec}\xspace~\cite{alon2019code2vec} and \textsc{Code2Seq}\xspace~\cite{alon2019code2seq}. Both models use paths from abstract syntax trees (AST) to encode a program.
\begin{itemize}
    \item \textsc{Code2Vec}\xspace. This model extracts a bag of path-context from the AST of the program where each path-context includes a pair of terminal nodes and the corresponding path between them. The model learns embeddings of these path-contexts during training and uses an attention mechanism to aggregate multiple path-contexts to a single code vector. The code vector is used as a representation of the program for making a prediction.
    \item \textsc{Code2Seq}\xspace. This model also extracts a bag of path-context from the AST of the program but it sub-tokenized each path-context. The \textsc{Code2Seq}\xspace model uses a bi-directional LSTM to encode paths node-by-node, and another LSTM to decode a target sequence one-by-one.
\end{itemize}
Using \texttt{JavaExtractor} of \textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace models, we extract and preprocess the bag of path-contexts from Java files. For example, given a sample expression: ``\texttt{tempVar = 0;}'', a path-context by \textsc{Code2Vec}\xspace is: ``\texttt{tempVar, <NameExpr ↑ AssignExpr ↓ IntegerLiteralExpr>, 0}'' and a path-context by \textsc{Code2Seq}\xspace is: ``\texttt{temp|var, NameExpr | AssignExpr | IntegerLiteralExpr, 0}''.

\subsection{Dataset}
For the \textsc{MethodName}\xspace task, we use the \textsc{Java-Large}\xspace dataset \cite{alon2019code2seq}. This dataset contains a total of $9,500$ Java projects from GitHub, where $9,000$ projects are for the training set, $200$ projects for the validation set, and $300$ projects for the test set. Using training set and validation set, we train both the \textsc{Code2Vec}\xspace and \textsc{Code2Seq}\xspace models. Table ? summarizes the performance characteristics of these models.

\subsection{Input Types}
The dataset from GitHub is often imbalanced and contains different sizes and frequencies of input programs. Therefore, to evaluate the effectiveness of our approach, we choose different type of input programs from \textsc{Java-Large}\xspace test set.

\begin{itemize}
    \item Frequent Methods: We randomly sample a total of $100$ input programs from the most occurring method names.
    \item Rare Methods: We randomly sample a total of $100$ input programs from the least occurring method names.
    \item Smaller Methods: We randomly sample a total of $100$ input programs that contains less than $10$ lines of code.
    \item Larger Methods: We randomly sample a total of $100$ input programs that has around $100$ lines of code.
\end{itemize}

\section{Threats to Validity and Future Plan}
\label{sec:results_threats}

\Part{Evaluation}. We evaluated our approach for \textsc{MethodName}\xspace task with two CI models, four input types of randomly selected input programs, and Top-10 most frequent method names. Despite our best effort, it is possible that experiments with different models, tasks, and datasets may produce different results. Our further plan includes a detailed study with a variety of models, tasks, and larger datasets. 

\Part{Challenges}. 
One challenge we have for running \textsc{Perses}\xspace is that it loads the model in each reduction step while Delta-Debugging\xspace loads the model once at the beginning of reduction. For a fair comparison between them, we only consider the program reduction time and ignore the model loading time. We are working on optimizing the model loading time for \textsc{Perses}\xspace.
Another challenge for running Delta-Debugging\xspace, when there are multiple subsets that hold the same target criteria, Delta-Debugging\xspace sometimes gets stuck at that point. To keep the reduction process working, we temporarily used a timer to kill the current step and jump to the next step.

\Part{Artifacts}. We will publicly share the artifacts of this study at \href{https://github.com/mdrafiqulrabin/rm-dd-perses}{\color{blue}{https://github.com/mdrafiqulrabin/rm-dd-perses}}.
