Short Title]Demystifying What Code Summarization Models Learned

Yu Wang

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

Ke Wang

Security, Cryptography, and Blockchain
Visa Research

Palo Alto

Study patterns that models have learned has long been a focus of pattern recognition research. Explaining what patterns are discovered from training data, and how patterns are generalized to unseen data are instrumental to understanding and advancing the pattern recognition methods. Unfortunately, the vast majority of the application domains deal with continuous data (statistical in nature) out of which extracted patterns can not be formally defined. For example, in image classification, there does not exist a principle definition for a label of cat or dog. Even in natural language, the meaning of a word can vary with the context it is surrounded by. Unlike the aforementioned data format, programs are a unique data structure with a well-defined syntax and semantics, which creates a golden opportunity to formalize what models have learned from source code. This paper presents the first formal definition of patterns discovered by code summarization models (models that predict the name of a method given its body), and gives a sound algorithm to infer a context-free grammar (CFG) that formally describes the learned patterns.

We realize our approach in which produces CFGs for summarizing the patterns discovered by code summarization models. In particular, we pick two prominent instances, code2vec and code2seq, to evaluate . shows that the patterns extracted by each model are heavily restricted to local, and syntactic code structures with little to none semantic implication. Based on these findings, we present two example uses of the formal definition of patterns: a new method for evaluating the robustness and a new technique for improving the accuracy of code summarization models.

Our work opens up this exciting, new direction of studying what models have learned from source code.

§ INTRODUCTION

Riding on the major breakthroughs in deep learning together with the ever-increasing public datasets and computation power, machine learning models have enabled state-of-the-art solutions to a wide range of problems including image classification <cit.>, machine translation <cit.>, and game playing <cit.>.

The success of the learning-based approaches can be largely attributed to their capability of discovering patterns exhibited in a large amount of data. An influential subfield within machine learning has been dedicated to explaining, visualizing patterns that models have learned from data. Moreover, the field has been receiving growing attention for its leading role in tackling some of the most imminent challenges in Artificial Intelligence (AI). For example, explainability is likely to be a central goal of the next-generation AI technology.

Revealing what models have learned is a crucial first step to designing such explainable AI systems.

In addition, from a scientific standpoint, dissecting the internal operation and behavior of complex models is necessary. Because without a clear understanding of how and why machine learning models work, the development of better models is reduced to trial-and-error.

For a few notable efforts, <cit.> present a context-sensitive grammar to model

the wide variations in object configurations via composite graphical templates.

A strength of their approach is the ability to explain what patterns are recognized from test data during the inference time, in the case of cloth modeling discussed  in <cit.>, predictions are made using templates representing shoes, hands, faces,  <cit.> introduce a visualization technique that gives insights into the function of individual feature layers and the end-to-end operation of a convolutional network, one class of Deep Neural Network (DNN) commonly applied in image classification. As a diagnostic tool, the visualization technique allows them to find model architectures that outperform AlexNet <cit.>, the then state-of-the-art model on ImageNet <cit.>. We defer a detailed survey of related work to Section <ref>.

Despite the significant stride, formalizing patterns that models have learned remains to be an exceedingly challenging task. This is in large part due to the nature of the problem domain to which learning-based approaches are applied. Models almost exclusively deal with continuous data out of which learning formal patterns is difficult if not impossible. For example, no machine learning models known to this day set out to learn principle definitions for labels in ImageNet (panda, ostrich, goldfish, ).

Even in the area of natural language processing, learning formal patterns is a tricky task since the meaning of words can be ambiguous.

When programming seems to have become yet another popular domain for machine learning models (exemplified by the DNNs), it is vitally important to recognize that program is a fundamentally different data structure. Specifically, it is discrete in nature with a well-defined syntax and semantics. Syntactically, programs are written in a way that satisfies the recursive rules (production rules) defined in a context-free grammar. Semantically, the behavior of a program satisfies the inference rules defined in the small-step semantics <cit.>. All of the above lead to the insight of our work, that is, patterns learned by models from source code can be formalized. However, we face an important challenge: how to efficiently navigate through an enormous search space of

diverse program properties ranging from syntax to semantics?

Our solution is based on a key and rather unexpected observation we made about the behavior of many prominent models of code. Built on the work of  <cit.>, which finds syntactically trivial and semantically preserving code edits frequently cause models to alter their predictions, we observe an even more surprising phenomenon. That is when models are given a program to predict, almost always the program can be reduced to very few statements ($\leq$ 2) for which models make the same prediction as they do for the original program. This is a significant finding in two ways. First, (1) it indicates a small, local window of code sufficiently covers the patterns that models look for to predict the properties of the entire program.

Therefore, the space for searching the pattern definitions is orders of magnitude smaller than one would have anticipated. Second, (2) for such simple patterns which are often semantically meaningless, predicates of semantic properties can be safely ignored, which further restricts the search space to predicates of syntactic properties. Based on (1) and (2), a natural idea for defining a pattern emerges: synthesizing rules based on syntactic properties of the key statements in the original program. However, there is a caveat: can the key statements alone always preserve the label models predicted for the original program regardless of the surrounding context? To address this issue, we find the set of valid programs in which the key statements do preserve the original predicted label from which we define the pattern that models learned.

At the technical level, we propose "Abstract, Mutate, Concertize, and Summarize", a novel method for pattern formalization. First, given a set of programs $\mathcal{P}$ all with a label $L$ predicted by a model $M$, we abstract away the statements on each program in $\mathcal{P}$ that do not cause $M$ to alter its prediction. We call each remaining code snippet a seed,

captures the essence of the prediction made by $M$ for the label $L$. Second, since machine learning models have been known for their generalization capability, we conjecture programs that resemble a seed are likely to be predicted with the same label $L$. Therefore, we mutate each seed to obtain additional code snippets, which we call mutants.

Third, we synthesize full-fledged programs by inserting statements into each seed and mutant.

In particular, we enumerate a diverse set of statements and expressions using the grammar of the language $\mathcal{P}$ are written in. Later, we pass each synthesized program to the model to get a label. Finally, we infer a context-free grammar that describes all synthesized programs for which $M$ predicts the label $L$

as the principle definition of a pattern learned by the model $M$ the label $L$.

We develop a tool, , as an implementation of the method "Abstract, Mutate, Concertize, and Summarize", which automatically formalizes the patterns learned by two code summarization models: code2vec <cit.> and code2seq <cit.>. Code summarization refers to a task in which models aim to infer the name of a method given its body. Figure <ref> shows an example. The correct prediction for this method is . We target code summarization models due to the tremendous impact they have made to the programming language community. Since the publication of code2vec in Principles of Programming Languages (POPL) two years ago, it has not only gathered many citations (130+) but also led to several interesting follow-up works (code2seq, sequence GNN <cit.>, and LiGER <cit.>).

[linewidth=6.8cm,morekeywords=var, public, String]code/method.cs

An example method extracted from <cit.> whose name is stripped out for models to predict. The top-4 prediction made by code2vec is shown on the right.

Through the context-free grammars that inferred, we find that the patterns learned by both evaluated models are simple all labels included in all Java-small, Java-med, and Java-large <cit.>, three public, large-scale, cross-projects datasets used in many code summarization works. The average number of tokens presented in a seed is computed to be 15.59.

For almost all the methods, the vast majority of the statements in their body can be removed, and the resulted seeds consist of less than two statements.

In addition, there is little constraint on the synthesis of full-fledge programs given the presence of seed statements, many constructs we insert into seeds do not even remotely resemble the semantics of the non-seed statements. Nevertheless, models display a strong tendency to keep the predictions they made for the original programs. Our finding

indicates that neither code2vec nor code2seq tries to learn a global, semantic representation for a given method, instead, they use local, syntactic program features as a proxy to simplify their memorization of the method.

Based on our findings in what code summarization models have learned, we present two example uses of our context-free grammar-based pattern formalization. First, we propose a new method to evaluate the robustness of code summarization models. In particular, we construct attacks to expose their vulnerabilities to small perturbations to the input programs. Our intuition is to concentrate changes on the seed statements, the part of a method on which models predominately based their predictions, to sway the predictions models made for the original programs. In addition, we introduce four semantically-preserving program transformations which enable us to find very small perturbations ($\leq$ 2 tree-edit distance between the ASTs of perturbed and unperturbed programs) for every correctly-predicted test method in Java-small, Java-med and Java-large.

Second, we propose a new technique to improve the generalizability of code summarization models. In the spirit of adversarial training <cit.>, we opt to include programs synthesized to address a particular weakness of code summarization models to re-train the models. Technically, after collecting the training programs for which models made the incorrect predictions, we inject their seeds to other programs to synthesize additional training data. Specifically, by assigning the label of the hosting program to the synthesized program, we guide models to shift their attention to different syntactic structures than they previously attended to, which paves the way for them to connect to the ground truth. After undergoing such a re-training process, both code2vec and code2seq have become more accurate, especially code2seq which achieves the state-of-the-art results on Java-med, and Java-large.

This paper makes the following contributions:

* A formal definition of patterns learned by code summarization models.

* A sound algorithm for formalizing patterns that code summarization models learned. Assuming the monotonicity property (Definition <ref>), the algorithm is also complete.

* An implementation, , which automatically generates definitions of patterns discovered by code summarization models in the form of context-free grammars.

* An empirical evaluation of on two prominent code summarization models: code2vec, and code2seq. Through the context-free grammars that inferred, we find the patterns neither model learned precisely capture the properties of programs with the predicted label.

* A new method for evaluating the robustness of a model, which finds adversarial examples with smaller perturbations and within far few attempts than prior approaches.

* A new technique for improving the accuracy of code summarization models, which enables code2seq to achieve the state-of-the-art results on Java-med, and Java-large.

§ OVERVIEW

In this section, we present an overview of our approach to formalizing patterns learned by code summarization models.

§.§ An Illustrative Example

First, we introduce a code summarization model and two input methods as our running example for illustrating the key idea and high-level steps of our approach.

Model.  We use code2seq, the state-of-the-art code summarization model on Java-med and Java-large. Like many other DNN-based models, code2seq strives for learning precise vectorial representations for source code. Such vectors, commonly known as program embeddings, capture the semantics of a program through their numerical components such that programs denoting similar semantics will be located in close proximity to one another in the vector space. At high level, code2seq adopts a generative approach for method name prediction. It employs a standard encoder-decoder architecture <cit.> in which the encoder first embeds the ASTs of input methods into vectors, then the decoder uses the vectors to generate method names as sequences of words (, and  as a prediction in Figure <ref>).

[linewidth=6.4cm,morekeywords=var, public, String]code/savebit1.cs

[linewidth=7.25cm,morekeywords=var, public, String]code/savebit2.cs

Two methods with the name .

Input Methods.  Figure <ref> and <ref> depict two Java methods with the name , which are extracted from the training set of Java-large. The distinguishing feature of this label is the  API under the  class, which both methods have highlighted in the shadow box.

Worth noting that neither code2vec nor code2seq requires input programs to compile so long as they satisfy the syntactic grammar of the language they are written in. Also, both code2vec and code2seq only take individual methods as input. When another method is invoked in the body of the input method, no inter-procedure analysis is performed, neither is inlining. Given the methods in Figure <ref> and <ref>, code2seq gives the correct predictions for both of them. Hereinafter, when referring to the inputs of code2vec or code2seq, we use programs and methods interchangeably.

§.§ Overview of “Abstract, Mutate, Concretize, and Summarize”

We now give an overview of our technique which consists of four major steps: abstract, mutate, concretize, and summarize.

§.§.§ Abstract

While DNN-based models have been gaining increasing popularity in the programming domain, <cit.> cautioned they are notably unstable with their predictions. Simple, natural, semantically-preserving transformations frequently cause models to change their predictions. Figure <ref> depicts an example in which the original method (<ref>) is correctly predicted to be  by code2vec, and the transformed method (<ref>), albeit semantically equivalent, is totally mishandled. None of the top-5 predictions even remotely resembles the ground truth considering that we only swapped the operands of the multiplication.

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

Prediction for the original method.

[linewidth=3.2cm,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-1 prediction is even higher on the transformed method.

Their finding suggests that models don't evenly distribute their attention across the entire structure of the method, instead, they focus on a small, local window of code for making predictions. To validate this hypothesis, we aim to find the window of code which models predominately based their predictions on. A simple idea is to exhaust all subsets of the statements in a given method to find

the minimal subset for which models make the same prediction as they do for the original program. However, a challenge arises: since the number of subsets to be traversed grows exponentially with the size of the method, how does it effectively scale to methods which consist of a large number of statements. We defer a detailed discussion on how to overcome this challenge in Section <ref>.

Figure <ref> depicts the minimal programs we discovered for the methods in Figure <ref> and <ref>. Three points we intend to emphasize. First, (1) no statement in either seed reflects the name of the methods, , albeit indicating a high probability of file operations, do not represent “  ”, neither does it connect to “”. The rest are the log/display APIs which are completely irrelevant. The reason that code2seq still predicts the label  for both methods is the parameters provided in the method headers since changing the class name  to  leads code2seq to predict a different label for both methods. Second, (2) the distinguishing features ( API under the  class) are absent in both seeds, casting serious doubts on code2seq about what it has learned. Finally, (3) Despite their irrelevance, all statements in both seeds are necessary in keeping code2seq's prediction. This suggests that code2seq takes into account the syntactic structure of methods — two consecutive method invocations in the case of Figure <ref> — to make prediction.

[linewidth=5.6cm,morekeywords=var, public, String]code/savebit1seed.cs

[linewidth=6.3cm,morekeywords=var, public, String]code/savebit2seed.cs

(fig:exasavebitseed)/(fig:newsavebitseed) depicts the seeds for the method in Figure <ref>/<ref>.

§.§.§ Mutate

It is well-known that machine learning models don't just create a mapping from input data to predicted labels through rote memorization but rather they discover patterns from data which generalize to that of similar characteristics. Based on this knowledge, we intend to find additional programs that are similar to the seeds which otherwise can't be obtained through a pure program abstraction approach.

When mutating a seed, we modify its AST with the standard tree-edit operations (node insertion, deletion and renaming), and ensure the resulted mutants also abide by the syntactic grammar of the language.

Figure <ref> shows two mutants among many we have discovered which also preserve the predictions code2seq made for the original programs.

[linewidth=6.7cm,morekeywords=var, public, String]code/savebit1mutant.cs

6.3cm,morekeywords=var, public, String]code/savebit2mutant.cs

Two mutants we discovered among many which also preserve the predicted label .

We convey two takeaways. First, the value of individual tokens has a heavy influence on code2seq, in both mutants, the two string constants have to be present for code2seq to predict .

Second, as explained above, code2seq cares about the syntactic structure that methods exhibit. For example, in Figure <ref>, even with the presence of , the major part of the pattern code2seq looks for, it has to be passed as a parameter into a method call. Any other operation on the string ()

will lead code2seq to predict a different label.

§.§.§ Concretize

Directly using seeds and mutants as the definition of the pattern that code2seq learned for the label  is a faulty approach despite their dominance in the predictions that code2seq makes.

Because no formal guarantees can be given that warrant the predicted label  when the seed or mutant statements are surrounded by any context of code. Therefore, we first explore the space of all full-fledged programs that are valid concretizations based on seeds and mutants, then use valid concretizations to define the pattern that code2seq learned for the label . We call a concretized program valid when it preserves the predictions models made for the original program.

To synthesize a full-fledged program, one can simply enumerate all possible statements to insert into a seed or a mutant. However, such an approach is likely to be infeasible. Because the space of programs can be enumerated by a grammar of any programming language is infinite. We show how to overcome this feasibility challenge while looking for valid concretizations in Section <ref>. Figure <ref> depicts two valid concretizations based on the mutants (Figure <ref> and <ref>) whose statements are highlighted in the shadow box. Apparently, both programs are written in drastically different syntax and even control flow constructs, and they do not denote the semantics of the original methods in any way, shape or form. code2seq keeps its original predictions purely because of the presence of mutant statements. The examples are convincing evidence that code2seq does not learn to represent the semantics of a method, instead, it attends to local, small syntactic features to memorize a method name.

[linewidth=5.4cm,morekeywords=var, public, String]code/savebit1Concre.cs

[linewidth=6.5cm,morekeywords=var, public, String]code/savebit2Concre.cs

Two concretized programs for which code2seq predicts .

<seed declaration> ::= <method header>  { <seed block statements>? }

<method header> ::= <method modifiers>? <result type> <method declarator> <throws>?

<result type> ::=  boolean | byte | short | int | long | char | float | double | void

<method modifiers> ::= <method modifier> | <method modifiers> <method modifier>

<method modifier> ::= public | protected | private | static

<method declarator> ::= <identifier> ( <seed parameter> )

<seed parameter>  ::= Bitmap bmp, 	File file
String file,  Bitmap bitmap, View container, boolean isShare

<seed block statements> ::=	<block statements> <seed core>  <block statements>

<seed core> ::= <seed1 core>  | <seed2 core>

<seed1 core>  ::= <identifier>(); <block statements> <seed1 statement>

<seed1 statement> ::=  <ambiguous name>(‘‘failed to save frame’’);
<type> <identifier> = <ambiguous name>(‘‘failed to save frame’’);

<seed2 core>  ::= <ambiguous name>( <identifier>, ‘‘save to file succeeded’’);
<ambiguous name>( <identifier>, ‘‘save to file failed’’);

<ambiguous name> ::= <identifier> | <identifier>.<identifier>

<block statements> ::= <block statement> | <block statements> <block statement>

<block statement> ::= <local variable declaration statement> | <statement>

The context-free grammar inferred that defines the pattern code2seq learned for .

§.§.§ Summarize

Finally, to define the pattern code2seq learned for the label , we infer a context-free grammar to describe all valid concretizations produced in the previous step. This in fact is a grammar inference problem <cit.> where much of the success is still limited to inferring regular grammars <cit.>. Fortunately, our problem setting is considerably simpler. That is the program to be dealt with already abide by the context-free grammar of the language they are written in, in other words, we don't need to generate production rules from the scratch but to recycle those a compiler would have used for parsing every concretized method.

Specifically, we take the union of the grammars that describe each concretized method as the definition of the pattern code2seq learned for the label .

For the sake of clarity and simplicity, Figure <ref> depicts the context-free grammar that is inferred from only the concretizations of the two mutants in Figure <ref>. We use Backus–Naur form style of notation and add an extra quantifier, “?”, which denotes zero or one occurrence of the quantified terminal or non-terminal. The key of the grammar is the production rule that describes how the non-terminal    can be replaced. Below, the replacement of non-terminal nodes   and   point to the specific concretization the two seeds. In particular, each production rule

describes how the  , defined in the later rules, can be inserted into each seed without altering the code2seq's prediction. For the non-terminal nodes whose replacement is not defined in Figure <ref>, we reuse their production rules defined in the syntactic grammar of Java, the default input programming language of code2seq.

§ METHODOLOGY

In this section, we give a detailed presentation of our approach to formalizing patterns learned by code summarization models. In particular, we describe our method “Abstract, Mutate, Concretize, and Summarize”.

§.§ Problem Definition

Given a model $M$, a set of programs $\mathcal{P}$ (from the training set of $M$) for which $M$ predicts the label $L$. In this work, we aim to formalize the patterns $M$ learned from $P$.

In other words, our formalization should define the common properties of $\mathcal{P}$ which $M$ regards as a “trademark” for any program it predicts the label $L$. We emphasize two points: (1) $\mathcal{P}$ is extracted from $M$'s training set, the only part of a dataset from which a model learns. During inference, models only attempt to match the learned patterns in test data, therefore we don't consider the non-training programs for studying what models have learned.

(2) the label $L$ that $M$ predicts can be incorrect for some (or even all) programs in $M$,

regardless, $M$ has learned a pattern that can be formalized. In fact, we propose an example use of the pattern definitions based on the incorrect predictions $M$ made to improve its accuracy.

At a high-level, the way we define a pattern that code summarization models learned is to generalize about all programs that exhibit the pattern using context-free grammar (Definition <ref>).

For the remainder of this section, we illustrate how to infer such a context-free grammar given a model and its training set.

To assist our exposition, we use the notations introduced above throughout this section.

Let $M$ be a model trained on a dataset $\mathcal{D}$. Let $\mathcal{P}$ ($\mathcal{P} \subsetneq \mathcal{D}$) be a set of programs for which $M$ predicts the label $L$. The patterns $M$ learned from $\mathcal{P}$ for predicting the label $L$ is a context-free grammar $G=<\!\!V,\Sigma,S,R\!\!>$ with non-terminals $V$, terminals $\Sigma$, a start symbol $S$, and production rules $R$, which specifies the common properties of the programs for which $M$ predicts the label $L$.

§.§ The Abstract, Mutate, Concretize, and Summarize Algorithm

This section presents our pattern formalization algorithm. In particular, it describes the four key functional components: abstract, mutate, concretize and summarize.

§.§.§ Abstract

The goal of this step is to identify a fragment of each method $P$ in $\mathcal{P}$ that captures the essence of the prediction a model made for $P$. We name such fragments seeds (Definition <ref>) which satisfy the sufficient and necessary properties.

Given a training method $P$ whose body consists of a set of statements $B$, and a model $M$ which predicts the label $L$ for $P$, another method[When processing each method, we do not change its header but the body, therefore we don't explicitly state the requirement that $\epsilon$'s header needs to be the same as $P$'s. The same thing applies to the later definitions and theorems. For simplicity, we consider the body of a method as a set of statements including the non-control flow statements and control flow statements whose bodies are replaced with empty blocks (Section <ref>).] $\!\epsilon$ with a body of statements $\hat{B}$ $\hat{B} \subseteq B$ is said to be a seed of $P$ iff it is sufficient, meaning, $M$ also predicts the label $L$ for $\epsilon$, and necessary, meaning, there does not exist a method $\epsilon^\prime$ with a body $B^\prime$ $B^\prime \subsetneq \hat{B}$;

and $M$ also predicts the label $L$ for $\epsilon^\prime\!$.

The intuition behind the sufficient property is to ensure that statements in a seed

alone lead models to the same prediction they made for the original method.
As for the necessary property, our definition implies no subset of the seed statements possesses the same capability.

In other words, removing any statement in a seed will cause models to alter their predictions.

Definition <ref> does not guarantee the singularity of seeds within a method. When there happen to be multiple sets of statements in the body that satisfy the sufficient and necessary properties, a method will have multiple seeds. In fact, for the program in Figure <ref>/<ref>, we depict another seed of his in Figure <ref>/<ref>.

[linewidth=6.7cm,morekeywords=var, public, String]code/savebit1seedbk.cs

[linewidth=6.6cm,morekeywords=var, public, String]code/savebit2seedbk.cs

Two other seeds of the programs in Figure <ref> and <ref>.

Note that the multiplicity of seeds does not necessarily violate our assertion that models base their predictions on a small, local window of code. A common behavior models display is they feed off the most recognizable statement while receiving enough signals from the remaining statements to arrive at the original prediction. Seeds in Figure <ref> and <ref> are good examples of this behavior. code2seq treats  as the dominant statement for feature representation, however, it still need help from other statements ( in Figure <ref> and the instantiation of a stream class within a  clause in Figure <ref>) to predict the label . In other words, we consider the window models look into as centering around the dominate statement, and extending across a variety of supporting statements. Another case we have found where models look into separate places in a method is when multiple statements render similar program features such as the two seeds in Figure <ref> and <ref> which only differ by a word in a constant string. Therefore, from the perspective of feature representation, models can be deemed as attending to the same window of code within the program.

To identify seeds in a given method, we can adopt a brute-force approach to exhaust all subsets of the statements in the body. The algorithm runs in exponential time, and will incur $2^{n}\!-\!2$ (where $n$ is the number of statements in the method, and we don't need to consider an empty seed or itself, hence “$-2$”) predictions. Although the approach can cope with methods of smaller size, it is hard to scale when the number of statements in the method increases. To address the potential scalability concern,

we present an optimization of the brute-force approach, which runs in quadratic time in average case. The optimization is designed based on the monotonicity property (Definition <ref>) of models.

Before we give the formal definition of monotonicity, we explain our intuition at a high level. Since the weights of models are optimized to fit the training data, they behave differently on the unseen data, the degree to which depends on the distributions from which both datasets are drawn and the capacity of the models themselves. As a concrete piece of evidence, models are always shown to be less accurate on the test set than they are on the training set of any widely-acknowledged, well-established benchmark no matter how powerful the models are or how similar the training data is to the test data.

Since proving the property is out of the scope of this paper, we assume the monotonicity of models to which we have not found a violation through our large-scale experimentation.

Given a model $M$, a method $P_0$ from the training set of $M$, a seed $\epsilon$ of $P_0$, a method $P_n$ outside of the training set of $M$, and the shortest sequence of tree-edit operations $\delta_1,\delta_2,\dots,\delta_n$ that transforms the AST of $P_0$ into that of $P_n$, $M$ is said to be monotonic iff it will make the same prediction for $P_{i}$ (the result of the application of $\delta_i$ on $P_{i-1}$ where $n > i \geq 1$) as it makes for $P_0$ if it makes the same prediction for $P_{j}$ (where $n \geq j > i$) as it makes for $P_0$. Similarly, $M$ will make a different prediction for $P_{i}$ (where $n \geq i > 1$) than it makes for $P_0$ if it makes a different prediction for $P_{j}$ (where $i > j \geq 1$) than it makes for $P_0$.

Sdnew Method(selected_statements, method.head)
Srnew Method(remaining_statements, method.head)

, , ,

, , , ,

$\gets$ .Size ()
$\gets$ 1 to
$\gets$ SelectStatements (, , )

$\gets$ .Predict (, )

$\gets$ $\cap$ { }

`$\setminus$' denotes the set minus
$\gets$ $\setminus$ IsAbsent (Line <ref>-<ref>), a constant time algorithm, checks the absence of additional seeds in the remaining statements
IsAbsent (, , , )

when execution hits this point, more seeds are to be discovered, which is handled in Line <ref>-<ref>
$\gets$ $\mathit{True}$

$\gets$ $\cap$ { }

, , , ,

, , ,

$\gets$ .Predict (, )

Find seed in a given method

Algorithm <ref> shows how to find seeds in a given method. The key is to avoid searching in a set of statements where there does not exist any seed. Whenever the  is found to satisfy the sufficient property, we save it as a seed (Line <ref>), and validate the absence of seeds in the remaining statements in the method (Line <ref>). Thanks to the monotonicity property, the absence of seeds can be validated in constant time. That is, if the entire set of the remaining statements is not capable of leading models to the predictions they make for the original methods, none of its subsets will, hence need not be checked, in which case, the algorithm returns and its output can be accessed through . However, if the remaining statements present more seeds, we break out of the current loop (Line <ref>), and continue to search the additional seeds by recursively calling itself with a new method composed of the remaining statements (Line <ref>-<ref>). To avoid re-attempting the same statements, we save the previous attempts into  (Line <ref>) which will be skipped in our quest for additional seeds in the future (Line <ref>). We do not explicitly check the necessary property because all discovered seeds are by construction minimal. In terms of the running time, Algorithm <ref> is guaranteed to find all seeds by traversing no greater than $\sum_{k=1}^{m} \Mycomb[n]{k}$ sets of statements where $n$ is the number of statements in a given method, $m$ is the number of statements in the largest seed of the method, and $\Mycomb[n]{k}$ denotes the number of combinations for $k$ objects selected out of $n$.  Since the vast majority of seeds consist of no greater than two statements, Algorithm <ref> runs in quadratic time in average case.

§.§.§ Mutate

In this step, we set out to find similar programs to seeds which also exhibit the pattern that $M$ looks for when predicting the label $L$. In particular, we mutate the AST of each seed to produce new programs through the standard tree-edit operations: adding nodes, removing nodes, and renaming nodes. Algorithm <ref> gives the details in computing the set of all mutants according to Definition <ref>. We defer the discussion on the motivation of Definition <ref> to Section <ref>.

Given a training method $P$ (with a body $B$), its seed $\epsilon$ (with a body $\hat{B}$), and a model $M$, a method $\omega$ whose body $\bar{B}$ is a variant of $\hat{B}$ (obtained by modifying the AST of one or more statements in $\hat{B}$ with the tree-edit operations), is said to be a mutant of $\epsilon$ iff $M$ makes the same prediction for $\epsilon$ and $\omega^\prime$ such that $\omega^\prime$'s body is $B \setminus \hat{B} \cup \bar
{B}$. $\omega$ is said to be the weakest mutant iff any change on $\omega$ that causes itself to be even further away from $\epsilon$ will lead $M$ to predict a different label than $M$ predicts for $\epsilon$. In contrast, $\omega$ is said to be the strongest mutant iff it alone keeps the predictions that models made for $\epsilon$ (exemplified by the programs in Figure <ref>).

Algorithm <ref> adopts an iterative approach to find mutants through a set of seeds. In each iteration, we enumerate the minimal edits to transform a mutant discovered in the previous iteration (Line <ref>). By minimality, we mean applying smaller edits to the corresponding mutant results in a syntactically invalid program (the minimal tree-edit operations needed to transform the AST of  into that of  is two). For the very first iteration, we transform the seeds given as input. Note that we only consider modifications when enumerating the edits for each mutant because deletions are guaranteed to yield invalid mutants according to the definition of seed; insertions are by nature not related to seed modification, and will be handled in the next step. We then check the validity of each transformed program according to the definition of mutant (Line <ref>-<ref>), if the transformed program passes the validity check, we save it as a mutant, and prepare it for further modification in the later iterations (Line <ref>-<ref>). On the other hand, if the transformed program failed the check, it will be permanently discarded. Because any further modification of the program will not lead to valid mutants according to the monotonicity property. The iteration stops when none of the transformed programs passes the validity check, in which case we have found all mutants.

Srnew Method(remaining_statements, method.head)

, , ,
, , , , Μ

$\gets$ $\varnothing$

$\gets$ EnumerateMinimalValidEdits ()
$\gets$ $\setminus$
$\gets$ $\cap$

$\gets$ .Predict ()
$\gets$ $\cap$ { }
Μ$\gets$ Μ$\cap$ { }

$!\!=$ $\varnothing$
, , , , Μ

Find mutants through a set of seeds

Changing Identifiers and Constants.

Regarding the renaming operations for terminal nodes of identifiers

(variables, types, or methods names),

they can be changed to any value that respects the lexical grammar (keywords that are reserved for the language can not be used to name variables).

To fully explore the search space, we consider both swapping identifiers within a given method and changing them to

words that do not appear in the given method. As for constants, we apply the same trick without incurring type errors ().

§.§.§ Concretize

Even though the seeds and mutants are mostly responsible for the predictions models make, it is impromptu to take their properties as the definition of a pattern that models have learned. Because statements in the seeds (or mutants) do not guarantee to preserve the predictions models made for the original programs, considering that their surrounding context can be composed of arbitrary code.

Therefore, the goal of this step is to find the space of programs anchored by the seed (or mutant) statements that keeps the predictions that models made for the original program.

Concretize with Seeds.  As discussed in Section <ref>, due to the nature of the mechanism in which models get trained, the discrepancy in their performance on the training and test data is inevitable. The closer an unseen sample is to a training example, the higher probabilities it will get the same predicted label as the training example.

Based on this property, we introduce our technique to concretize a seed below.

We simply restore the removed statements in the original method, and incrementally edit the restored statements (while leaving the seed statements intact) until the resultant method of the edits no longer keeps the prediction that models made for the seed. Our intuition is

to quantify the space of all possible concretizations using a set of closed intervals, each of which measures how far a concretized method is from the original method along a trajectory of edits[Like mutating seeds into mutants in Algorithm <ref>, there are multiple trajectories of edits to change non-seed statements during the concretization of a seed.].

At the higher end of each interval is the closest concretized method (the original method itself),

which yields the widest margin for potential modifications. At the lower end is the furthest concretized method (called threshold method), albeit still underpinned by the seed statements, already exhausted the budget with its accumulated edits to the non-seed statements. In other words, any change that made itself even further from the original method will cause models to alter the prediction they made for the seed. By monotonicity, any program that lies between the two ends of each interval is a valid concretization. Recall the context-free grammar inferred for the illustrative example in Section <ref>, we avoid constraining the recursion depth of the production rule for the clarity of our presentation. In reality, depth of three gives a good approximation of the lower end of each interval regarding the concretization of the seeds and mutants in Figure <ref> and <ref>. Finally, as a verification mechanism, we confirm the validity of each concretized method by passing them to models for their predicted labels. A concretized method will only be kept when it lead models to the prediction they made for the original program.

Technically, when varying the non-seed statements, we first keep the control flow structure of the original method, and only modifies the non-control statements or expressions in the control construct.

Later, when switching to a different control flow structure, we reset the higher end of each interval to be $Q$, a program that is the closest to $P$ among all that employ the new control flow structure $\upsilon$. Formally, we define $Q$ in Equation <ref>:

\begin{equation}\label{equ:ncl}
\begin{split}
Q & = \argmin_{W \in \mathcal{W}} \lvert P - W \rvert^{T} \\
\mathcal{W} & = \{W\, |\, \mathit{CF}(W)=\upsilon, \mathit{NCF}(W) \subseteq \mathit{NCF}(P) \cap \{\varnothing_s\} \}
\end{split}
\end{equation}

where $P$ is the original program from which the seed is derived. CF(W) returns the control flow structure of $W$. NCF(W) returns the set of non-control statements of $W$. The reason we consider $\{\varnothing_s\}$, a set of an empty statement, is to allow control statements with empty bodies when existing non-control statements are running out (number of control statements is greater than the that of non-control statements). Similarly, the margin $Q$ induces will be gradually consumed by the changes we apply to $Q$. Like before, the enumeration terminates when $Q$ no longer preserves the prediction models made for the seed, and we deem programs between the two ends of each interval as the concretization of the seeds with different control flow structures.

Concretize with Mutants.  In the aforementioned approach, seed statements serve as the anchor in the method, and they are kept intact throughout the concretization process. Now we discuss how to handle the situation in which seeds statements are modified. Once a seed is modified, its statements may lose the capability of keeping the original prediction models made even with the facilitation from the non-seed statements in the original method. Figure <ref> gives an example, in which both programs altered code2seq's prediction due to the modification on the seed statements despite the presence of all non-seed statements. For such modified seeds which fail to preserve the original prediction models made even when the non-seed statements are present, we don't consider them for subsequent concretization. Because they do not exhibit any budget for further changes that are required to concretize a modified seed according to the monotonicity property. On the other hand, the modified seeds that remain in the mix are precisely the mutants (Definition <ref>), among which the one with the least budget of change is called the weakest mutant.

[linewidth=6.15cm,morekeywords=var, public, String]code/savebit1change.cs

[linewidth=7.25cm,morekeywords=var, public, String]code/savebit2change.cs

Modifying the seed statements cause code2seq to alter its predictions despite the presence of all non-seed statements. Shallow boxes highlight the changes in the seed statements.

To concretize each mutant into a full-blown method, we follow the same procedure in which we concretize a seed.

That is, we inject to the body of a mutant the non-seed statements in the original method. The resultant method, which has the largest room for potential changes, keeps being modified until models no longer preserve the prediction they made for the seeds.

Similar to the seed concretization, statements in a mutant will never be changed, because mutants themselves already cover all the valid changes. In addition, we also employ the verification mechanism to ensure every concretization based on the mutants is valid.

§.§.§ Summarize

Finally, we infer a context-free grammar to describe precisely all concretized methods produced in the previous step. We declare this grammar to be the definition of the patterns $M$ learned from $\mathcal{P}$ the label $L$. To solve this grammar inference problem, we don't reinvent the wheel but to reuse the syntactic grammar that input programs already employ. That is, we extract the production rules that a compiler would have used for parsing each concretized method before combining them into a unified grammar. Formally, we take the union of the terminals, non-terminals, and production rules extracted from each grammar. Regarding the definition of the patterns that code2seq learned for the label , our inferred grammar describes 13 distinct control flow structures and can be instantiated into hundreds of programs with different syntactic structures. In other words, seeds and mutants are capable of preserving the predicted label $\texttt{saveBitmapToFile}$ most of the time when the enumerated programs are similar in size to the original method. Through the grammar we inferred, we conclude that code2seq has not learned a semantic representation for methods named , instead, they memorize the methods through small, syntactic features.

§.§ Correctness

We show our “abstract, mutate, concretize, and summarize” algorithm is correct Definition <ref> (Patterns). In particular, Theorem <ref> and <ref> gives the soundness and completeness proof for our algorithm.

Given a model $M$ trained from a dataset $\mathcal{D}$,

and a grammar $G$ that the algorithm inferred as the definition of the patterns $M$ learned from $\mathcal{D}$ for predicting a label $L$, the algorithm is said to be sound iff $G$ does not describe any program for which $M$ does not predict the label $L$.

All concretizations of seeds or mutants are verified through $M$'s predictions. The context-free grammar that the algorithm inferred describes precisely all the valid concretizations. Therefore, by construction the theorem holds.

Given a model $M$ trained from a dataset $\mathcal{D}$,

and a grammar $G$ that the algorithm inferred as the definition of the patterns $M$ learned from $\mathcal{D}$ for predicting a label $L$, the algorithm is said to be complete iff $G$ describes any program for which $M$ predicts the label $L$.

Assume otherwise, there exists a program $\sigma$ such that $M$ predicts the label $L$ for $\sigma$ and $G$ does not describe $\sigma$. Regarding $\sigma$'s properties, one of the following conditions has to be met:

* $\sigma$ is from the training set of $M$. Recall the concretize step in our algorithm, which uses every training program with the predicted label $L$ to enumerate the valid concretizations. In other words, all training programs are already included in the concretize step, and will be described by $G$. This contradicts the assumption. Thus, the condition is not met.

* $\sigma$ is not from the training set of $M$.

* $\sigma$ contains the statements in a seed $\epsilon$ derived from a training program $P$. Per our assumption that $G$ does not describe $\sigma$, and thus $\sigma$ is not a valid concretization of $\epsilon$, which means $\sigma$ is not on any trajectory of edits that changes $P$ to a threshold method. By monotonicity, $M$ does not predict the label $L$ for $\sigma$, hence contradicting the assumption.

* $\sigma$ contains the statements in a mutant derived from a seed. With the same strategy as it is adopted in (1), this condition can also be refuted.

* $\sigma$ does not contain the statements in a seed, neither does it contain the statements in a mutant. As discussed in the concretize step, $\sigma$ will not lead $M$ to predict the label $L$. The condition is also false.

Since none of the conditions above can be satisfied, it can be inferred that $\sigma$ does not exist.

§ EXAMPLE USES OF THE PATTERN DEFINITION

In this section, we show the practical implications of our pattern definitions: a new method for evaluating the robustness, and a new technique to improve the accuracy of code summarization models.

§.§ Evaluating Robustness of Code Summarization Models

The robustness of a model refers to the reliability of the predictions it makes, especially on adversarial examples, a
special type of data created by systematically perturbing the model inputs. <cit.> is the first to discover the existence of adversarial examples in the image classification domain: visually indistinguishable perturbations cause models to alter their predictions made for the original image. Existing approaches to evaluating the robustness of a model can be classified into two categories: formally verifying a lower bound $B_l$ <cit.> (predictions are guaranteed to hold on perturbations no greater than $B_l$ some distance metric such as $L_0$, $L_1$ or $L_\infty$), or constructing attacks to demonstrate an upper bound $B_u$ <cit.> (perturbations no smaller than $B_{u}$ are sufficient to make models alter their predictions).

Wang and Christodorescu's method falls into the latter, in which they create adversarial examples by applying semantically-preserving transformations to the original programs. Interested readers are encouraged to consult the supplemental material for examples of their transformations. Despite the significant findings, their approach suffers from two issues. First, since there are many applicable transformations, and each transformation can be applied to multiple places in a given method, blindly attempting all the possibilities is quite an inefficient approach. Furthermore, their transformations often cause a fair amount of changes to the original method, thus tending to find loose bounds that do not accurately reflect the robustness of a model.

To address the weakness of their approach, we leverage the pattern definitions to pinpoint adversarial examples that demonstrate a far tighter bound than Wang and Christodorescu's method. Intuitively, since we aim to minimize the number of changes when perturbing the input methods, we only modify the seed statements, the part of the method models heavily attend to, to create adversarial examples. We introduce four semantically-preserving transformations — variable renaming, operands swapping, API substitution, and statements reordering — that only make minor edits to the seed of the input methods. Figure <ref> depicts an example for each transformation except variable renaming. For each column, the block at the top holds the original method and that at the bottom holds the transformed method. In comparison with Wang and Christodorescu's method, our transformations make smaller edits to the original programs.

[language=C++,showstringspaces=false, morekeywords=String]
int contains(String target,
List<String> Items)
if (Items.indexOf(target)!=-1)

int addChildRequest(long
duration) ...
childDurationsSum =
childHits + duration;

void addItem(List<T> mItems)
log("Item added.");

int contains(String target,
List<String> Items)
if (Items.contains(target))

API substitution

int addChildRequest(long
duration)  ...
childDurationsSum =
duration + childHits;

Operands swapping

void addItem(List<T> mItems)
log("Item added.");

Statements reordering

Three semantically-preserving program transformations. Top row describes the original methods, and bottom row describes the transformed methods.

§.§ Improving Accuracy of Code Summarization Models

We introduce a new technique based on pattern definitions that improves the prediction accuracy of code summarization models. Our technique is built on an important observation we made about the incorrect predictions that models make. When models mistakenly mis-predict a method which has a label $A$ to have a label $B$, more often than not, the seed of the mis-predicted method is similar to the seed of another method with the label $B$, in which case models are incapable of making a clear distinction, resulted in the mis-predictions. Figure <ref> gives an example in which the two methods have similar seeds but distinct names. code2seq mis-predicted the method in Figure <ref> to be , the name of the method in Figure <ref>.

[linewidth=4.4cm,morekeywords=var, public, String]code/mis2.cs

[linewidth=4.5cm,morekeywords=var, public, String]code/mis1.cs

code2seq mis-predicted the name of (fig:mispred1) to be , the name of the method in (fig:mispred2). The reason is the seed statement in (fig:mispred1) is similar to the seed statement in (fig:mispred2). We highlight the seed statements of both programs within the shadow box.

Inspired by this finding, we proposed a new approach, along the line of adversarial training <cit.>, which guides models to attend to a different part of an input method when predicting its label. The hope is the new seed will not clash with any existing seed extracted from the training programs in the entire dataset. At the technical level, we create new training programs by injecting the seed of a mis-predicted method into a variety of methods (with different labels) that are correctly predicted. Each freshly-created program will be assigned with the label of the correctly predicted method which happens to host the seed. Our intention is to neutralize the previous seed, which causes models to mis-predict, to a new seed, which hopefully would lead them to the ground truth.

Figure <ref> depicts an example, in which we drop the seed statements of the mis-predicted program (Figure <ref>) into three methods named , , and  respectively. The resulted methods will keep the name of the hosting methods as highlighted in the Figure. In practice, many such instances will be added to the training set. As a result, models are forced to shift their attention on the mis-predicted program because keep using  as seed will affect their accuracy on the additional training samples despite the higher weight of the hosting methods. Because seed statements, which always emit strong signals to influence models, will not be ignored, and the only way out is to neutralize them, which is the goal of the re-training.

[linewidth=4.4cm,morekeywords=Object String]code/retra1.cs

Additional programs that are created to re-train code summarization models.

To select the mis-predicted programs, we target labels where models display the highest error rates to prevent them from overfitting to a few outliers for an otherwise perfectly-predicted label. Because a poor prediction accuracy on a sizable number of programs with the same label indicates the issue of underfitting, which our new technique addresses.

§ EVALUATION

We have realized our algorithm “abstract, mutate, concretize and summarize” in a tool, called ,

which formalizes the patterns code summarization models learned using context-free grammar. In the first part of the evaluation, we give the details of the pattern definitions that produces. For the example applications of the pattern definitions, we also evaluate the effectiveness of the method for finding adversarial examples, and the new technique for improving the prediction accuracy of code summarization models.

§.§ Evaluation Subjects

Models.  code2vec, code2seq, sequence GNN, LiGER are the most notable code summarization models in the literature. In the ideal case, all of them should be included in our experiments. However, we had significant difficulties in reproducing the results sequence GNN achieves <cit.>. Our reimplementation performed significantly worse (more than 10% in F1) than theirs on the same benchmark used in their experiments. We suspect the discrepancy is caused by the inconsistent extractors which convert a method into the graph representation amendable to the model because the original extractor is the only part in their pipeline that is not open-sourced.[We have made an effort to resolve the issue with the authors of sequence GNN. Unfortunately, we could not work out a solution before the submission deadline. We have attached our email conversations in the supplemental material for reviewers' perusal.] Concerning the validity of our results on an inferior reimplementation, we regrettably exclude sequence GNN from our experiment. We also don't pick LiGER, a model that heavily depends on program executions due to its rather limited applicability and generality. Compared to code2vec and code2seq which does not even require programs to compile, LiGER requires programs to execute. For this reason, LiGER is evaluated on less than 10% of the methods in Java-med and Java-large since the vast majority do not trigger interesting executions for LiGER to learn.

Compare reimplementations to originals for code2vec and code2seq.

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 (reimplementation)    19.23     17.72     18.44     40.32     28.89    33.66     48.90     37.26     42.29
code2seq        50.64     37.40     43.02      61.24     47.07     53.23     64.03     55.02     59.19
code2seq (reimplementation)    48.72     35.46     41.05      61.91     46.38     53.03     63.78     54.41     58.72

Datasets.  We use Java-small, Java-med, and Java-large, three public datasets that many code summarization models used for evaluation. They are proposed by <cit.>, which are collections of Java methods extracted from a large number of projects on GitHub. We have re-trained code2vec and code2seq using their implementations open-sourced on GitHub. Table <ref> shows re-trained models are comparable to the originals <cit.>.

§.§ What Have code2vec and code2seq Learned

Now, we give the details about the pattern definitions produced for code2vec and code2seq.

Finding Seeds.  In general, we follow Algorithm <ref> to identify the seed of a given program. Regarding the control statements, we treat their bodies to be independent of the control predicates. For example, when abstracting a  statement, we either delete the  condition and keep the statements in the body or remove a non-control statement from its body. We apply this method recursively to deal with nested control constructs. Table <ref> depicts the size of the seed in terms of the number of tokens it is composed of for code2vec and code2seq (mean and median). The number in the parenthesis denotes the percentage a seed's tokens makes up of a whole method's. Similarly, Table <ref> gives the statistics of the strongest mutants. Apparently, both models only learned local, syntactic program features as the seeds do not capture the global, semantic properties of input methods.

The size of the seeds.
max width=1

2*Models     2c|Java-small      2c| Java-med      2c Java-large

Mean     Median     Mean     Median     Mean     Median
code2vec    c14.23
(24%)     c10.00
(19%)      c13.13
(18%)     c9.00
(12%)     c14.30
(21%)     c10.00
code2seq     c11.53
(23%)     c9.00
(15%)     c14.95
(21%)      c11.00
(14%)     c18.72
(19%)     c16.00

The size of the strongest mutants.
max width=1

2*Models     2c|Java-small      2c| Java-med      2c Java-large

Mean     Median     Mean     Median     Mean     Median
code2vec    c13.91
(23%)     c10.00
(19%)      c12.21
(17%)     c9.00
(11%)     c13.70
(20%)     c10.00
code2seq     c12.03
(24%)     c9.00
(15%)     c14.32
(21%)      c11.00
(13%)     c17.33
(18%)     c16.00

Concretizing Seeds and Mutants.  At the concretize step, we adopt the same approach to dealing with the identifiers (variable, type, or method names) as we do at the mutate step. In general, concretizations of a seed or a mutant covers a wide spectrum of program structures, many of which do not resemble the semantics of the statements outside of the seed. Figure <ref> gives two more concretizations in addition to those in Figure <ref>.

[linewidth=6.7cm,morekeywords=var, public, String]code/savebit1seedbkConcre.cs

[linewidth=6.6cm,morekeywords=var, public, String]code/savebit2seedbkConcre.cs

Two concretized programs for seed in Figure <ref>.

Table <ref> depicts on the number of distinct control flow structures a concretization includes. Table <ref> gives the same statistics the actual program instances in terms of the syntactic variations. Evidently, both models pay little to none attention to the non-seed statements in input methods as they are regularly substituted with other drastically different statements without altering the predictions models made for the original programs.

The # of distinct control flow structures
max width=1

2*Models     2c|Java-small      2c| Java-med      2c Java-large

Mean     Median     Mean     Median     Mean     Median
code2vec     12.31    10     12.79     10    9.00     8
code2seq     12.22     9     10.43     8     8.49     6

The # of syntactic variations
max width=1.03

2*Models     2c|Java-small      2c| Java-med      2c Java-large

Mean     Median     Mean     Median     Mean     Median
code2vec     246.52     273     248.17     260     336.00     336
code2seq     260.49     275     218.46    230     207.92     225

Both code2vec and code2seq predominately base their predictions on a small fraction of the input methods.

§.§ Evaluating the Robustness of code2vec and code2seq

We construct attacks to code2vec and code2seq based on the pattern definitions produces. Given an input method, we identify its seed statements, on which we apply the aforementioned semantically-preserving transformations to look for the potential adversarial examples. If a transformed program leads a model to a different prediction than it made for the original method, an adversarial example is found, and the robustness of the model can be calculated by averaging the distance between the closest adversarial examples and the original methods that are correctly predicted in a test set. We adopt the tree-edit distance (with node swapping operation) as the metric to measure the distance between programs because others like $L_0$, $L_1$ or $L_\infty$, which typically used in the setting of adversarial learning, are not suitable. Table <ref> and <ref> depict the robustness score for code2vec and code2seq based on programs that compile, which can be deemed as the first line of defense. Table <ref> and <ref> show on average how many attempts two methods take to find the closest adversarial examples. Given multiple applicable transformations, we rank them in ascending order of the distance between the resultant program after the transformation is applied and the original method. For transformations that result in programs of same distance, they will be picked randomly. The baseline refers to Wang and Christodorescu's method, which makes far more attempts than our method to find adversarial examples.

Robustness score for code2vec.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline           3.24     2.95     3.31
1.78     1.26     2.43

Robustness score for code2seq.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline           2.39              3.50     3.14
1.12     1.68     3.02

On average the number of attempts needed to find the closest adversarial example for code2vec.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline           12.1     14.3     15.7
2.1     3.2     2.4

On average the number of attempts needed to find the closest adversarial example for code2seq.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline           15.4              16.9     22.5
2.6     2.4     3.7

We also dive deeper into the robustness scores we obtained, and find that both methods are heavily relying on variable renaming to create adversarial examples. For a fair evaluation of the other program transformations, we exclude variable renaming and repeat the same experiment. Table <ref> and <ref> report the percentage of programs for which adversarial examples can not be created with the other transformations for code2vec and code2seq respectively. Using the remaining programs on which adversarial examples can be created, we report the robustness score of code2vec and code2seq in Table <ref> and <ref>. Results presented in Table <ref>-<ref> suggest that our approach finds adversarial examples not only for far more programs on all datasets but also with significantly smaller edits to the original methods if the variable renaming transformation is not considered.

The Percentage of programs for which adversarial examples can not be created for code2vec.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline      72%     68%     64%
35%     27%     31%

The Percentage of programs for which adversarial examples can not be created for code2seq.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline      68%     64%     67%
28%     29%     33%

Re-evaluate the robustness of code2vec.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline           12.8     9.40     15.1
1.40     1.71     1.88

Re-evaluate the robustness of code2seq.
max width=1

Methods     Java-small      Java-med      Java-large
Baseline           10.3              14.6             13.4
1.69     1.37     2.58

Both code2vec and code2seq are vulnerable to adversarial examples. Perturbing the seed statements in a given method easily causes code2vec and code2seq to alter their predictions.

§.§ Improving the Accuracy of code2vec and code2seq

We propose a new technique to improve the prediction accuracy of code2vec and code2seq by guiding them to correct their own mis-predictions. To prepare code2vec and code2seq for the re-training, Table <ref> and <ref> give the number of labels under which we pick the mis-predicted programs to fix, the average error rate that the model displays on these labels, and the number of generated programs for re-training.

Preparation for the re-training of code2vec.
max width=1

Mis-predictions	    Java-small      Java-med      Java-large
# of labels      73     442     1186
Average error rate      52%     60%     70%
# of generated programs       6,161     37,774     97,061

Preparation for the re-training of code2seq.
max width=1

Mis-predictions     Java-small      Java-med      Java-large
# of labels      118     552     1137
Average error rate      64%     52%     72%
# of generated programs       6,438     39,592     99,566

Table <ref> shows the results of code2vec and code2seq on all three datasets after the re-training. Clearly, Our technique does not just overfit the models to their training set as their accuracy on the test set has also been consistently improved, especially code2seq which now achieves the state-of-the-art results on Java-med and Java-large. On the other hand, we acknowledge the improvement is not substantial, nevertheless, we believe the technique is still a significant contribution from the following aspects.

Results of code2vec and code2seq after the re-training.

max width=

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

Precision     Recall     F1     Precision     Recall     F1     Precision     Recall     F1
Baseline        18.82     17.14     17.94     40.95     28.63     33.70     47.46     37.19     41.70
code2vec        19.23     17.72     18.44     40.32     28.89     33.66     48.90     37.26     42.29
code2vec (re-training)    22.75     18.59     20.46
43.47     31.48    36.51     49.35     38.58     43.31
Baseline        49.16     35.25     41.16      62.24     46.07     52.95     63.08     54.12     58.26
code2seq        48.72     35.46     41.05      61.91     46.38     53.03     63.78     54.41     58.72
code2seq (re-training)    48.05     40.61     42.08      63.24     47.89     54.50     66.49     56.43     61.05

* Reliability: All results presented in Table <ref> are the average over ten separate training instances except those based on code2seq with Java-large, which take more than a week to train, is the average over five. Therefore, the higher accuracy that both models show is not random noise but a reliable improvement.

* Simplicity: As a major selling point, our technique is in nature a data augmentation approach, which does not require one to change the architecture of an existing model. By systemically augmenting the training set based on the previous mis-predictions, the improvement comes with a much lower cost than designing a new model.

* Effectiveness: The baseline in Table <ref> augments the training set with the same amount of additional data that are randomly selected from GitHub. The added data have the same label as the generated programs used for re-training. As shown in the table, randomly augmenting the training set does not always lead models to an improved accuracy as both models display almost the same performance as before. In addition, we give concrete evidence on the effect the re-training makes on code2seq. Given the mis-predicted program (Figure <ref>), code2seq corrects its own mistake by expanding the seed statements (highlighted in Figure <ref>), which enables him to differentiate the method in Figure <ref> from that in Figure <ref>.

[linewidth=4.4cm,morekeywords=var, public, String]code/correct1.cs

[linewidth=4.5cm,morekeywords=var, public, String]code/mis1.cs

Given the more distinct seed statements from (fig:cor2), code2seq correctly predicts the label of (fig:cor1).

The augmentation approach improves the accuracy of both code2vec and code2seq by guiding them to correct their own mis-predictions, in particular, code2seq achieves the state-of-the-art results on Java-med and Java-large on top of its existing architecture.

§.§ Discussion on Threats to Validity

A major threat to the validity of our approach is the assumption we made regarding the monotonicity property of code summarization models. Intuitively, given how machine learning models are trained to fit the training data, monotonicity is a reasonable assumption. In addition, this behavior is certainly backed up by our extensive experiments as no violation has been discovered. Nevertheless, we have not given a principle proof of the property which may not hold for the evaluated models. But even the monotonicity property is proven to be false, we believe the validity of our approach still holds to a great extent.

First of all, the soundness of the approach is not affected since the validity of seeds, mutants, and concretizations are all verified through predictions made by the subject models, which means our primary findings — the patterns that code2vec and code2seq learned for predicting method names — remain to be valid, as a result, our secondary contribution regarding the applications of the pattern definitions — a new method for evaluating the robustness and a new technique for improving the accuracy of code2vec and code2seq — are also valid. The aspect that will be affected is the completeness of our approach, that is, the inferred grammar that defines what models learned for a label could very well miss programs for which models also predict the label. However, given the maintenance of soundness and its implications, we conclude the validity of our approach mostly holds without the monotonicity property.

§ RELATED WORK

In this section, we survey two strands of related work: studying what models have learned and predicting the names of methods given their bodies.

§.§ Patterns Models Have Learned

In computer vision, <cit.> propose an attribute graph grammar for parsing images with man-made objects, such as buildings, hallways, and kitchens. Their algorithm focuses on detecting exclusively the shape of rectangle, and uses six production rules to specify the various spatial relationships among the detected rectangles as the basis for object detection. Later, a similar grammar is applied to the setting of cloth modeling, an important task in human recognition and tracking, to model the wide variations of cloth configurations <cit.>. A particular strength of their approach is the ability to provide insights into what patterns the algorithm recognized based on the activation of the production rules during inference.

<cit.> propose a visualization technique to demystify the function of intermediate feature layers and the operation of convolutional neural networks. Built upon a deconvolutional network <cit.>, their technique reveals the input stimuli that excite individual feature maps at any layer in the model. It also allows one to observe the evolution of features during training and to diagnose potential problems with the model. As another contribution of the technique, they can reveal which parts of the input images are important for classification.

<cit.> present an analytic framework to visualize and understand generative adversarial networks. First, they identify the units in a layer whose featuremaps correspond to the detection of a class of objects (trees). Second, they intervene within the network to switch off (or back on) the detection of the class of objects, (forcing the activation of the identified units to be zero), and quantify the average causal effect of the ablation. Finally, they examine the contextual relationship between these causal object units and the background.

§.§ Code Summarization Models

code2vec is the first code summarization model in a cross-projecting setting. It works by (1) decomposing the Abstract Syntax Tree (AST) of an input method into a collection of AST paths, each of which is a path between nodes in the AST, starting from one terminal, ending in another terminal, and passing through the common ancestor of both terminals; (2) aggregating the embedding learned for each AST path; and (3) predicting a probability distribution over a set of given labels based on the aggregated embedding.

code2vec also employs the attention mechanism <cit.> to assign different weights for AST paths. In other words, the embedding of the method is a weighted sum of the embedding of a path in the AST.

code2seq is another notable code summarization model in the literature. Unlike code2vec, a discriminative model in nature, code2seq adopts an encoder-decoder architecture <cit.> to predict method names as sequences of words. For decoding, code2seq also attends to a set of representations designed to combine each path and token representation to generate the method names. code2seq achieved then the state-of-the-art results on all Java-small, Java-med, and Java-large, three public datasets of Java methods.

In a similar vein to code2seq, sequence GNN also adopts an encoder-decoder architecture to predict method names. To encode a given method, sequence GNN relies on the coordination between a sequence and graph model. That is, recurrent neural network first learns the sequence representation of each token in a program before gated graph neural network computes the state for every node in the AST. Like code2seq, they use another recurrent neural network to generate method names as sequences of words.

LiGER is the first model that incorporates dynamic program features to the learning processing for code summarization. Their insight is that executions, which offer direct, precise, and canonicalized representations of the program behavior, help models to generalize beyond syntactic features. On the other hand, LiGER uses symbolic features learned from source code to reduce the heavy reliance a dynamic model has on program executions since high-coverage executions are not always readily available.

§ CONCLUSION

In this paper, we present the first formal definition of the patterns that code summarization models have learned. Based on this definition, we have developed a sound algorithm for producing such pattern definitions, and a working implementation for formalizing the patterns code2vec and code2seq have learned. We found that both code2vec and code2seq heavily focus on a small, local fraction of input methods to predict their names, indicating the limited generalizability of both models about global, semantic program properties. We also present two example applications of the pattern definitions. For evaluating the robustness of code2vec and code2seq, our method uses smaller perturbations and takes far fewer attempts than prior approaches to find adversarial examples. Regarding improving the accuracy of code2vec and code2seq, the new technique we designed based on adversarial training enables code2seq to achieve the state-of-the-art results on Java-med and Java-large.

* We plan to further refine and deploy our implementation to inform the users of a finer-grained explanation for a predicted label such as which expression in the method is responsible for a particular word in the output so that users can better understand the reasoning models use when making predictions.

* We plan to further diagnose the code summarization models to design a general, systematic framework for improving both the accuracy and robustness of code summarization models.

* We plan to apply our technique to study the patterns that are learned by other models of code for solving different tasks in programming language.

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

[Alon et al(2019a)]
authorpersonUri Alon, personOmer Levy,
and personEran Yahav. year2019a.
code2seq: Generating sequences from structured
representations of code.
journalInternational Conference on Learning
Representations (year2019).

[Alon et al(2019b)]
authorpersonUri Alon, personMeital
Zilberstein, personOmer Levy, and personEran
Yahav. year2019b.
Code2Vec: Learning Distributed Representations of
journalProc. ACM Program. Lang.
numberPOPL (year2019).

[Bahdanau et al(2015)]
authorpersonDzmitry Bahdanau,
personKyunghyun Cho, and personYoshua Bengio.
Neural machine translation by jointly learning to
align and translate.
journalInternational Conference on Learning
Representations (year2015).

[Bau et al(2019)]
authorpersonDavid Bau, personJun-Yan Zhu,
personHendrik Strobelt, personBolei Zhou,
personJoshua B. Tenenbaum, personWilliam T. Freeman,
and personAntonio Torralba. year2019.
Visualizing and Understanding Generative
Adversarial Networks.
journalInternational Conference on Learning
Representations (year2019).

[Biermann and Feldman(1972)]
authorpersonAlan W Biermann and personJA
Feldman. year1972.
A survey of results in grammatical inference.
In booktitleFrontiers of Pattern Recognition.
publisherElsevier, pages31–54.

[Carlini and Wagner(2017)]
authorpersonN. Carlini and personD.
Wagner. year2017.
Towards Evaluating the Robustness of Neural
Networks. In booktitle2017 IEEE Symposium on Security and
Privacy (SP). publisherIEEE Computer Society.

[Chen et al(2006)]
authorpersonHong Chen, personZi Jian Xu,
personZi Qiang Liu, and personSong Chun Zhu.
Composite templates for cloth modeling and
sketching. In booktitle2006 IEEE Computer Society
Conference on Computer Vision and Pattern Recognition (CVPR'06),
Vol. volume1. IEEE, pages943–950.

[Cho et al(2014)]
authorpersonKyunghyun Cho, personBart van
Merriënboer, personCaglar Gulcehre, personDzmitry
Bahdanau, personFethi Bougares, personHolger
Schwenk, and personYoshua Bengio.
Learning Phrase Representations using RNN
Encoder–Decoder for Statistical Machine Translation. In
booktitleProceedings of the 2014 Conference on Empirical
Methods in Natural Language Processing (EMNLP).

[Conneau and Lample(2019)]
authorpersonAlexis Conneau and
personGuillaume Lample. year2019.
Cross-lingual Language Model Pretraining.
In booktitleAdvances in Neural Information
Processing Systems 32. pages7059–7069.

[Deng et al(2009)]
authorpersonJia Deng, personWei Dong,
personRichard Socher, personLi-Jia Li,
personKai Li, and personLi Fei-Fei.
Imagenet: A large-scale hierarchical image
database. In booktitle2009 IEEE conference on computer
vision and pattern recognition. Ieee, pages248–255.

[Devlin et al(2019)]
authorpersonJacob Devlin, personMing-Wei
Chang, personKenton Lee, and personKristina
Toutanova. year2019.
BERT: Pre-training of Deep Bidirectional
Transformers for Language Understanding. In
booktitleProceedings of the 2019 Conference of the North
American Chapter of the Association for Computational Linguistics: Human
Language Technologies, Volume 1 (Long and Short Papers).

[Devlin et al(2014)]
authorpersonJacob Devlin, personRabih Zbib,
personZhongqiang Huang, personThomas Lamar,
personRichard Schwartz, and personJohn Makhoul.
Fast and robust neural network joint models for
statistical machine translation. In booktitleProceedings of
the 52nd Annual Meeting of the Association for Computational Linguistics
(Volume 1: Long Papers).

[Fernandes et al(2019)]
authorpersonPatrick Fernandes,
personMiltiadis Allamanis, and personMarc
Brockschmidt. year2019.
Structured Neural Summarization.
journalInternational Conference on Learning
Representations (year2019).

[Gehr et al(2018)]
authorpersonTimon Gehr, personMatthew
Mirman, personDana Drachsler-Cohen, personPetar
Tsankov, personSwarat Chaudhuri, and personMartin
Vechev. year2018.
Ai2: Safety and robustness certification of neural
networks with abstract interpretation. In booktitle2018
IEEE Symposium on Security and Privacy (SP). IEEE, pages3–18.

[Goodfellow et al(2015)]
authorpersonIan J. Goodfellow,
personJonathon Shlens, and personChristian
Szegedy. year2015.
Explaining and Harnessing Adversarial Examples.
journalInternational Conference on Learning
Representations (year2015).

[Han and Zhu(2008)]
authorpersonFeng Han and personSong-Chun
Zhu. year2008.
Bottom-up/top-down image parsing with attribute
journalIEEE Transactions on Pattern Analysis and
Machine Intelligence (year2008).

[Krizhevsky et al(2012)]
authorpersonAlex Krizhevsky, personIlya
Sutskever, and personGeoffrey E Hinton.
Imagenet classification with deep convolutional
neural networks. In booktitleAdvances in neural information
processing systems. pages1097–1105.

[Oncina and Garcia(1992)]
authorpersonJosé Oncina and
personPedro Garcia. year1992.
Inferring regular languages in polynomial updated
time. In booktitlePattern recognition and image analysis:
selected papers from the IVth Spanish Symposium. pages49–61.

[Plotkin and Kahn(1987)]
authorpersonGordon Plotkin and
personGilles Kahn. year1987.
A structural approach to operational semantics. In
booktitleSTACS'87: Proc. Fourth Annual Symposium on.
Aarhus University, pages22–39.

[Raghunathan et al(2018)]
authorpersonAditi Raghunathan, personJacob
Steinhardt, and personPercy Liang.
Certified Defenses against Adversarial Examples.
journalInternational Conference on Learning
Representations (year2018).

[Silver et al(2016)]
authorpersonDavid Silver, personAja Huang,
personChris J. Maddison, personArthur Guez,
personLaurent Sifre, personGeorge van den Driessche,
personJulian Schrittwieser, personIoannis Antonoglou,
personVeda Panneershelvam, personMarc Lanctot,
personSander Dieleman, personDominik Grewe,
personJohn Nham, personNal Kalchbrenner,
personIlya Sutskever, personTimothy Lillicrap,
personMadeleine Leach, personKoray Kavukcuoglu,
personThore Graepel, and personDemis Hassabis.
Mastering the game of Go with deep neural networks
and tree search.
journalNature (date01 Jan

[Silver et al(2017)]
authorpersonDavid Silver, personJulian
Schrittwieser, personKaren Simonyan, personIoannis
Antonoglou, personAja Huang, personArthur Guez,
personThomas Hubert, personLucas Baker,
personMatthew Lai, personAdrian Bolton,
personYutian Chen, personTimothy Lillicrap,
personFan Hui, personLaurent Sifre,
personGeorge van den Driessche, personThore Graepel,
and personDemis Hassabis. year2017.
Mastering the game of Go without human knowledge.
journalNature (date01 Oct

[Stevenson and Cordy(2014)]
authorpersonAndrew Stevenson and
personJames R Cordy. year2014.
A survey of grammatical inference in software
journalScience of Computer Programming
volume96 (year2014), pages444–459.

[Szegedy et al(2013)]
authorpersonChristian Szegedy,
personWojciech Zaremba, personIlya Sutskever,
personJoan Bruna, personDumitru Erhan,
personIan Goodfellow, and personRob Fergus.
Intriguing properties of neural networks.
journalInternational Conference on Learning
Representations (year2013).

[Touvron et al(2019)]
authorpersonHugo Touvron, personAndrea
Vedaldi, personMatthijs Douze, and personHervé
Jégou. year2019.
Fixing the train-test resolution discrepancy. In
booktitleAdvances in Neural Information Processing
Systems. pages8250–8260.

[Vaswani et al(2017)]
authorpersonAshish Vaswani, personNoam
Shazeer, personNiki Parmar, personJakob Uszkoreit,
personLlion Jones, personAidan N Gomez,
personŁukasz Kaiser, and personIllia
Polosukhin. year2017.
Attention is all you need. In
booktitleAdvances in neural information processing
systems. pages5998–6008.

[Vinyals et al(2019)]
authorpersonOriol Vinyals, personIgor
Babuschkin, personWojciech M. Czarnecki,
personMichaël Mathieu, personAndrew Dudzik,
personJunyoung Chung, personDavid H. Choi,
personRichard Powell, personTimo Ewalds,
personPetko Georgiev, personJunhyuk Oh,
personDan Horgan, personManuel Kroiss,
personIvo Danihelka, personAja Huang,
personLaurent Sifre, personTrevor Cai,
personJohn P. Agapiou, personMax Jaderberg,
personAlexander S. Vezhnevets, personRémi
Leblond, personTobias Pohlen, personValentin
Dalibard, personDavid Budden, personYury Sulsky,
personJames Molloy, personTom L. Paine,
personCaglar Gulcehre, personZiyu Wang,
personTobias Pfaff, personYuhuai Wu,
personRoman Ring, personDani Yogatama,
personDario Wünsch, personKatrina McKinney,
personOliver Smith, personTom Schaul,
personTimothy Lillicrap, personKoray Kavukcuoglu,
personDemis Hassabis, personChris Apps, and
personDavid Silver. year2019.
Grandmaster level in StarCraft II using multi-agent
reinforcement learning.
journalNature (date01 Nov

[Wang and Christodorescu(2019)]
authorpersonKe Wang and personMihai
Christodorescu. year2019.
COSET: A Benchmark for Evaluating Neural Program
journalarXiv preprint arXiv:1905.11445

[Wang and Su(2020)]
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 et al(2018)]
authorpersonShiqi Wang, personKexin Pei,
personJustin Whitehouse, personJunfeng Yang, and
personSuman Jana. year2018.
Formal Security Analysis of Neural Networks Using
Symbolic Intervals. In booktitleProceedings of the 27th
USENIX Conference on Security Symposium
(seriesSEC’18). pages1599–1614.

[Zeiler and Fergus(2014)]
authorpersonMatthew D. Zeiler and
personRob Fergus. year2014.
Visualizing and Understanding Convolutional
Networks. In booktitleComputer Vision – ECCV 2014.

[Zeiler et al(2011)]
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.

§ APPENDIX A

Below we show the transformations adopted in  <cit.> . For each sub-figure the block at the top shows the original method and the block at the bottom shows the transformed method.

[linewidth=5.3cm,morekeywords=var, public, String]code/append-people.java

[linewidth=5.5cm,morekeywords=var, public, String]code/append-pay.java

[linewidth=5.3cm,morekeywords=var, public, String]code/append-people-trans.java
Control flag removal.

[linewidth=5.5cm,morekeywords=var, public, String]code/append-pay-trans.java
Nested condition simplification.

[linewidth=4.4cm,morekeywords=var, public, String]code/arrayF.java

[linewidth=4.5cm,morekeywords=var, public, String]code/simpF.java

[linewidth=4.4cm,morekeywords=var, public, String]code/arrayF-trans.java

[linewidth=4.5cm,morekeywords=var, public, String]code/simpF-trans.java
Dead code elimination.

[linewidth=3.9cm,morekeywords=var, public, String]code/forwhile.java

[linewidth=3.0cm,morekeywords=var, public, String]code/fixvalue.java

[linewidth=4.0cm,morekeywords=var, public, String]code/unroolFor.java

[linewidth=3.9cm,morekeywords=var, public, String]code/forwhile-trans.java
Control statement unification.

[linewidth=3.0cm,morekeywords=var, public, String]code/fixvalue-trans.java
Constant propagation.

[linewidth=4.0cm,morekeywords=var, public, String]code/unroolFor-trans.java
Loop unrolling.

§ APPENDIX B

Emails with the authors of sequence GNN regarding the issues of re-producing their results reported in <cit.>.