HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS
Authors: Elizabeth Dinella
Hanjun Dai
Ziyang Li
Mayur Naik
Le Song
Ke Wang
Venue:  (2020)
Keywords: Bug Detection
Program Repair
Graph Neural Network
Graph Transformation

Abstract: We present a learning-based approach to detect and fix a broad range of bugs in Javascript programs. We frame the problem in terms of learning a sequence of graph transformations: given a buggy program modeled by a graph structure, our model makes a sequence of predictions including the position of bug nodes and corresponding graph edits to produce a fix. Unlike previous works that use deep neural networks, our approach targets bugs that are more complex and semantic in nature (i.e.~bugs that require adding or deleting statements to fix). We have realized our approach in a tool called HOPPITY. By training on 290,715 Javascript code change commits on Github, HOPPITY correctly detects and fixes bugs in 9,490 out of 36,361 programs in an end-to-end fashion. Given the bug location and type of the fix, HOPPITY also outperforms the baseline approach by a wide margin.

Published as a conference paper at ICLR 2020
HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS
Elizabeth Dinella" University of Pennsylvania
Hanjun Dai
Ziyang Li University of Pennsylvania
Google Brain
Mayur Naik University of Pennsylvania
Le Song Georgia Tech
Ke Wang Visa Research
ABSTRACT
We present learning- based approach to detect and fix broad range of bugs in Javascript programs. We frame the problem in terms of learning a sequence of graph transformations: given a buggy program modeled by a graph structure, our model makes a sequence of predictions including the position of bug nodes and corresponding graph edits to produce a fix. Unlike previous works built upon deep neural networks, our approach targets bugs that are more diverse and complex in nature (i.c. bugs that require adding or deleting statements to fix). We have realized approach in tool called HOPPITY. By training 290,715 Javascript code change commits on Github, HOPPITY correctly detects and fixes bugs in 9,490 out of 36,361 programs in end-to-end fashion. Given the bug location and type of the fix, HOPPITY also outperforms the baseline approach by a wide margin.
INTRODUCTION
The sheer size and complexity of modern codebases makes it impossible for them to be bug-free. As result, a more reasonable and effective strategy has emerged, which aims to prevent bugs in production by applying automated tools to detect and even fix them early in the development process.
This trend has gained increasing popularity in recent years. Examples include Google's 's Tricorder (Sad- owski et al., 2015), Facebook's 's Getafix (Scott et al., 2019) and Zoncolan, and Microsoft's Visual Studio IntelliCode. The techniques underlying these tools can be classified into broadly two categories: logical, rule-based techniques (Sadowski et al., 2015) and statistical, data-driven techniques (Alla- manis et al., 2018: Pradel Sen, 2018; Vasic et al., 2019). The former uses manually written rules capturing undesirable code patterns and scans the entire codebase for these classes of bugs. The latter learns to detect abnormal code from a large code corpus using deep neural networks. Despite great strides, however, both kinds of tools are limited in generality because they target error patterns in specific codebases or they target specific bug types. For instance, Zoncolan's 's rules are designed to be specifically applicable to Facebook's codebases, and deep learning models target specialized bugs in variable naming (Allamanis et al., 2018) or binary expressions (Pradel & Sen, 2018). Moreover, the patterns relatively syntactic, allowing them to be specified by human experts using logical rules or learnt from a corpus of programs.
In this paper, we propose novel learning- based approach for finding and fixing bugs in Javascript programs automatically. Javascript is a scripting language designed for web application development. has been the most popular programming language GitHub since 2014 (Github, 2019). Repairing Javascript code presents a unique challenge as bugs manifest in diverse forms due to unusual language features and the lack of tooling support. Therefore, the primary goal of our approach is generality since it must be effective against a board spectrum of programming errors, such as using wrong operators or identifiers, accessing undefined properties, mishandling variable scopes, triggering type incompatibilites, among many others. Another important novel aspect concerns our approach's 's ability to deal with bugs that are more complex and semantic in nature, namely, bugs that require adding or removing statements from program, which are not considered by prior works. Finally, compared to automated program repair techniques (Le Goues et al., 2019; Scott et al., 2019; Hua al., 2018; Chen
"The first authors contributed equally this work.

---

Published as a conference paper at ICLR 2020
et al., 2018) which require knowledge of bug location, this paper presents an end-to-end approach including localizing bugs, predicting the types of fixes, and generating patches.
We design model architecture in similar vein Neural Turing Machine (NTM) (Graves et al., 2014). consists of an external memory (a Graph Neural Network) for embedding buggy program and central controller (an LSTM) that makes sequence of primitive actions (e.g.. predicting type, generating patch, etc.) to perform a fix. The multi-step decision process implemented by an autoregressive model. Crucially, our model differs from the standard NTM in how the memory is manipulated: apart from the common read and write operations, the controller can also expand or shrink the memory when adding or deleting nodes in the original graph.
We have realized our approach in a tool called HOPPITY. By training on 290.715 Javascript code change commits collected from Github, HOPPITY correctly detects and fixes bugs in 9,490 out of 36,361 programs using beam size of three.
2 MOTIVATING EXAMPLES
Javascript is quite different compared to traditional object-oriented languages (e.g. C++, Java, or C#). In addition the weak, dynamic typing discipline of scripting languages, Javascript supports many peculiar features that do not exist in other languages. For example, it allows property (i.e., field) be added to or removed from an object at runtime. As another example, Javascript did not support block-level scoping until recently, allowing variable defined in a block structure such as for loop to be exposed to the entire function in which the loop occurs. While the latest ES6 language standard incorporates block-level scoping, developers have been programming without it for decades, resulting in large body of legacy code. Finally, Javascript's s eval function, which interprets and executes a string as code fragment, is widely regarded major source of bugs and vulnerabilities. All of these aspects make programming in Javascript a frustrating and error-prone experience.
function claateappooyeiisssstoamniiti docunent queryšelector ("a") addeeventLLssemee (tt.:lorrooor.......ddeeeo...o. ("olick",
1f (matcches) return
function (event)
Number (matches. groupe egiisode),
docunent quexyyeleecoo ("ul") EnperHING
"*)
bosts: matches. catec.gpuusp aplit (/181, 4]+| Naa//a/d////// map (el => B(ei).trim() .s)
(a) InnerHTML should have been inaerHTиI.
(b) Highlighted parentheses should have been removed.
module. exports function (gcunt)) |
expport default {
grunt. initConfig [I
computed: Level
execute: copy:
checktoxtdomain: (...)
up up_ceadre__ to markdown: t...ly makepot: (...))
zeburn dictMap akillleval]
pazseint ([tbis. value wan 0
this. vaiis.vlle)/20// 1200
grunt. registerTack( defoult', readne to. narkdown
(c) copy function should have also heen included in (d) parse Int should have been removed hecause the highlighted list.
implies this. value is an integer.
Figure 1:
Example programs that illustrate limitations of existing approaches inculding both rule- based static analyzers and neural-based bug predictors.
Static analyzers aim to detect common coding errors in Javascript programs by applying logical rule- based reasoning on source code. TAJS (Jensen et al., 2009) and ESLint (Zakas, 2013) are prominent examples. These tools face important challenges to be effective. We present several examples in Figure to illustrate their limitations. Due to the complex nature of client-side web APIs, TAJS and ESLint choose ignore analyzing built-in libraries for the sake of scalability. As depicted in property of class
Figure la, when developers mistakenly capitalize the first letter of inner Element in DOM (Document Object Model), both analyzers fail to eatch the error. Javascript will then silently allow developers to set the previously non-existent property InnerHTML. to the empty string. Later, when developers attempt to access the intended property, innerHTML, the program will crash and potentially cause security vulnerability Additionally, static analyzers can never deal with functional bugs (i.e., errors that violate the program specification and yet conform to the coding rules). Figure 1b shows one such example. The goal is to split string using regular expressions. However, the program incorrectly splits the input and into (',, and ''I instead of ['', ''J, which is what the developer intended. Since
incur costly debugging experience.
2

---

Published as a conference paper at ICLR 2020
tpged eliwway (Paes Wepderr ArREDoo Collbat
TMe Fasts Ricin, dusile
RBC
Frt
tigloc
body
Editr
function add(e)
function addla, b) ( by Adtromaaacca Fanction add bl { return by
Figure 2:
Code repair as graph transformation. Each step the source code graph is edited via one of the operator module until STOP is triggered by controller.
the error simply a mismatch between the developer's 's implicit specification and implementation. static analyzers are incapable of catching it.
The bugs that static analyzers missed in both cases are in hindsight quite obvious human program- mers. The criteria they use is very simple: any code snippet that seems to deviate from common code patterns likely to be buggy. This is precisely the observation that our approach seeks to mimic. In particular, if' model observes a property an unusual way of splitting strings that never appeared in the training data, it is likely to recognize those abnormal code fragments as potential bugs. The main advantage of our approach over existing neural-based bug detectors (Allamanis et al., 2018; Pradel & Sen, 2018; Vasic et al., 2019) is its generality. Unlike prior works that target specific classes of bugs (e.g., variable naming issues or binary expression bugs), we train single model to deal with wide range of bug types, encompassing all previously proposed ones. Compared to past approaches that leverage graph-based neural network model (Allamanis et al., 2018), our model is capable of more sophisticated transformations such as adding or removing nodes, as shown in Figure Ic and dd. Finally, our model not only locates but also fixes bugs, whereas program repair (Le Goues et al., 2019; Scott et al., 2019; Hua et al., 2018; Chen et al., 2018) or bug localization (Ball et al., 2003; Jose & Majumdar, 2011; Wang et al., 2019) techniques only solve a single task.
3 MODEL
We model the problem of detecting and repairing bugs in programs as structured prediction problem on a graph-based representation of programs. Given a graph Gouy that represents buggy program, we wish to predict graph ffir that represents the fixed program. Our model aims to capture the structured prediction by a sequence of up to T steps of graph transformations:
Ibugi linlggi 0) = p(g1 19hug:
91: pttpee/gii.......pg.rbrrrr.::::.
(1)
The high-level overview of the graph sequence transformation is shown in Figure 2. Different programs may need different number of steps T (gbbg) which is also determined by the model.
We first introduce our representation module for programs in Sec 3.1. We then elucidate each step of the above transformation Sec 3.2. Finally, we summarize and present the full model in Sec 3.3.
3.1 PROGRAM REPRESENTATION
Programs written in ligh- language have rich structure. Researchers have proposed graph-based representations to capture this structure (Allamanis et al., 2018). We start with this approach of representing programs using graphs with certain modifications for our task.
As shown in the left part of Figure 2, we first parse the program's 's source code into an abstract syntax tree (AST) form that captures the program's syntactic structure. We then connect the leaf nodes with SuccToken edges. Unlike previous approaches, we additionally add value nodes that store the actual content of the leaf nodes, with special Valuelink edges connecting them together. The purpose of introducing this additional set of nodes is to provide representation and modification, which we elucidate in the next section. Hereafter, we use fftrs Goug or g in general to represent either the source code or the corresponding graph structure.
indeeennddn strategy for code
After representing the program as a graph, we use a Graph Neural Network (GNN) (Scarselli et al., 2008) to map the graph into representation in fixed dimensional vector space. Specifically, given
3

---

Published as a conference paper at ICLR 2020
Locition
Value
Type
addia) Irsturt k:
Beact
Folmer Intestareee gioaa vilan
Typepadicion
teramu
dxcaeet.coo (ww.eee.oooll1ooo Jeae
PEW Teclusie: Tirires
Pastill
Iedy
Tire
PE WACC San: ood guza lal
2013
BeccTion fax() Ieturt
jar Gedattattaalli wwalee salual
Figure 3: Graph edit operators with low-Ievel primitives.
a graph g = E) with set of nodes V and edges E, we need a function f(g) + (Rd (e R ) to obtain the d-dimensional representation of graph (denoted as g). as well as representations of individual nodes a E V (denoted as úT) To parameterize f(),, we employ the form GIN (Xu et al., 2018), with our adaptation to our multigraph for program representation in the following manner:
he (1+1).k = =((EEN wi (1) Ak E {1,2.... (1,2....,K)
A = = oWW(h A((1))2 ....,A K + nQ())
())
where Wi*k E Rdxd W E BRdk xd are model parameters and (-) is tanh in this implementation. K is the total number of edge types in this multi-graph representation. In the end, the node embedding is Ø (, where I. is the total number of propagations in the GNN. (²) is the set of neighbors of node v that are connected by edge with type k. Following GIN, the graph representation I is the aggregation of fi, V/ E 0, 1,...,,, L. We use max pooling to aggregate hi, for each I, and then take the average of these L +1 1 vectors to obtain g.
Initially, we use the node type one-hot features as a starting value for h where the types are either obtained from the AST representation, or from the local value table as shown in Figure 2. Note that we don't 't use features like variable names function names in this graph representation, as different programs may follow different naming conventions. Instead, we focus on the syntactic structure of the source code, so enable naming-agnostic representation across different programs.
3.2
ONE-STEP GRAPH EDIT
There are five types of operators to choose from for single step graph edit, namely, adding node (ADD), deleting node (DEL), replacing a node value (REP_VAL), replacing node type (REP_ SEP_) and stop (NO_OP) When combined with multi-step edits, these operators suffice to capture rich variety of code modifications. These operators share some common low-level primitives, such as finding the location, predicting value, etc. We first introduce the individual low-level primitives and then present how to assemble these for each type of graph edit operator.
3.2.1 LOW-LEVEL PRIMITIVES
Our low-level primitives contain location, type, and value prediction. These primitives can be combined for different operators later on. In this section, we assume the availability of a controller, represented ह E IRd. It keeps track of the global state, including the original source code, as well as the edits made so far. We will elaborate this when we assemble different primitives together.
The location primitive locates specific position in the source code. While it corresponds to region selection in the original text representation, with the graph representation, we can easily treat it as node selection step. As different programs have different numbers of nodes, we employ pointer network (Vinyals et al., 2015) into the graph structure. Specifically, after obtaining the node embeddings {7) (ovve,, select the node via loc(ć, g) arg max,gv T' for simplicity.
Location
Value The value primitive assigns a value for a leaf node in the AST. Instead of predicting the replace- ment value using language generative model (Chen al., 2018) or GNN score function (Allamanis
4

---

Published as a conference paper at ICLR 2020
et al., 2018), we adopt the attention mechanism to let the model to choose from either the values appearing in the current file (local value table), or a collection of global values that are common for the specific language. Let Deal be the global dictionary of commonly used leaf-node values in the language, where each item i Deal is associated with vector representation ig IR The local value table is denoted as V which is a subset of the nodes in current graph. Then, the value is predicted via val(E, g) = argmax, D...U. t c. Again we use inner product simply for efficiency, while more expressive score functions can also be used.
Type The type primitive assigns the type for non-terminal nodes in an AST, As the total possible number of types is finite and fixed for given language, the type prediction is simply a multi- class classification problem. However, we can utilize the AST grammar checker with contextual information to prune the output space. To predict the type of a given non-terminal node, we can obtain its parent node and current children. Then, by looping over the valid production rules at the current location, we can obtain a list of all valid types. The final type is only chosen from this set.
3.2.2 GRAPH EDIT ATORS
The t-th round of edit starts with the current graph 9t-1, the corresponding graph embedding, and the 'macro-context" embedding cMt-1 that captures the edit history so far. Every type of edit operation (excluding NO_OP), requires prediction of the buggy location. So, in each round, the location primitive invoked to determine the node to target. Then the edit type e that is feasible at this location is predicted out of the five operators. A 'micro-context" embedding Cm, is obtained from the macro embedding updated by two LSTM calls with location node embedding T and operator embedding ē. To summarize:
CM: LSTMM (l Cmi LSTM (cMM))
(3)
The micro-context embedding is used as the controller throughout the process of each operator. In the following content, present these operators in detail.
ADD This operation adds a new node to the graph. Unlike in Li et al. (2018) where the node and corresponding edges are added in separate stages, which would introduce extra complexity, introduce a simple mechanism that can uniquely add a node and corresponding edges. As is shown in Figure 3, this process invokes one location primitive, one value primitive, and one type primitive. The location primitive invoked before the edit (i.e., node v) determines the parent of the node to be added, while the location primitive called during the edit chooses the left sibling of the node. In a special case where the parent node does not have any children, then such left sibling node is set to the parent node itself. With this information, we can uniquely determine the position to insert into the AST. Finally, the corresponding edges-Succe -ScccTo o ken,, ValueLink, ink and AST edges- can automatically be inferred with the location of new node to be added.
As this process is autoregressive, the micro-context embedding is kept updated with all the primitive calls. For this specific operator, the context is updated the order of: Gn1 = I.STM (S (m). cm2 = LSTM(vvl((C)) summarizes the process.
g) (cmi) and cm3 LSTM(type(Cm2 e.))) In the end, ČADD Cm3
DEL This operator deletes node and corresponding edges in the graph. if is non-terminal node in the AST, then the corresponding subtree is removed as well. The micro-context embedding is updated by the LSTM via the embedding of the node being deleted.
REP VAL This operator replaces the value of a leaf (terminal) node in the AST. This procedure requires the prediction the value. The leaf node is linked to the new value node in the internal value table via a Val belink nk edge. Also, the micro-context embedding is updated by the LSTM via the embedding of the corresponding node and value.
REP TYPE This operator changes the type of a non-terminal node, which involves type primitive steps. The micro-context embedding is updated by the LSTM via the embedding of the corresponding node and type.
NO OP This op does not change the graph. It simply denotes the end of the sequence of graph edits.
3.3 GRAPH TRANSFORMATION
Our end-to-end model for graph transformation inference is shown in Alg 1. We denote the buggy graph goug as go for simplicity. Then, for the 1-th graph edit, the following steps are performed:
5

---

Published as a conference paper at ICLR 2020
1. Obtain the graph representation 9:-1 and node embeddings. Update the macro-context embedding using 9t-1:
Algorithm 1 T'ransformation inference of plyyiz (9hug)
1: Input gbug ~ DD and model parameters 0.
2: Obtain go: (UrEgbng) So (o(Dbog), let CMo be null.
2. Choose edit location iú by performing location primitive and update the con- text embedding:
3: for f = =1 to do
4: Obtain CM. LSTM iim, (..
5: Choose location v. then edit type exi
3. Pick the graph edit operator e, that is compatible with ny; Use both i and e to obtain the micro-contes embedding.
6:
if e, = _O_ then
7:
set 9r 9t-1 and exit the loop.
8:
end
Perform the edit, obtain the correspond- ing micro-context summary Co and up- date the macro-context embedding.
Perform operator e, with Cmu, obtained by Eq 3.
10: Get new graph It, update CM, with Cee-
11:
end for
5. If the edit is not NO_OP, then go back
12: Return 9T
to step I; otherwise return the graph.
This process repeats until it reaches the maximum steps 7 or the NO_OP operator is selected. Note that our framework can capture the situation when the input program is bug-free. In this case, the NO OP operator is supposed to be triggered at the first step. Also, each edit step is not limited to single node level operation. It can be extended to modify a certain substructure (e.g.. replace a tree node with one of its children). This in turn allows program repair to be performed in fewer edit steps.
LEARNING
22 which consists pairs of buggy code and the fixed code,
Given the dataset D the learning objective maxy E (ggnng ( Wgugg 0) maximizes the likelihood of fixes.
Since the probability is factorized according Eq where sequence of transformations is performed, we parse the source code using the SHIFT AST format, and utilize a ISON diff toolbox to compile the code differences into sequence of AST edits. This serves as the fine-grained supervision mechanism for our graph transformation formulation. Thus, the MLE objective above is realized with the sum of cross entropy loss at each step of graph edits. During training, we jointly optimize the graph representation module {f((-)]? each of the operator module and the controller module which is parameterized by LSTM. We use the Adam optimizer with 31 0.9, 33 = 0.99 and initial learning rate of 10-3, Due to the large size of each sample, we use small batch size of 10 during training. Furthermore, to stabilize the training, we apply the gradient clip with the maximum norm of 5.
5 INFERENCE
The inference procedure involves searching for the maximum the combinatorial space: arg max pigfialbbug; f). Since the search space is very large, however, we use beam-search to approximately find the fixes with highest probabilities.
Ibug;
Specifically, we maintain pool of partially fixed programs {ū), which starts with simply the single buggy program Paug. The pool size is limited by the beam-search size B. For each ÿ. we propose the top B locations to be modified, top B operators top B primitives (location, type, value), depending on the current stage of the edit g. Then the total joint one-step graph transformation solutions are ranked together based on the joint log-likelihood, and the top B solutions with the largest likelihood are kept in the pool for the next round of beam search.
Unlike beam search for language models where the vocabulary size is fixed, in setting, the available choices or even the steps of inference may vary (e.g., the ADD operator has more steps of primitive calls than the DEL operator). Our implementation based PyTorch with customized GPU kemnels to enable efficient inference on GPUs.
6
EXPERIMENTS
Our model is trained and evaluated on corpus of nearly half million data points. We have created robust system to continuously collect small changes in Javascript programs from Github. Given commit, we download the Javaseript file before and after the change: (srCsuggy- srCfixed)- Commits can contain many types of changes such as feature additions, refactorings, bug fixes, etc. In
Dataset

---

Published as a conference paper at ICLR 2020
ADD
REP_
REP_VAL
DEL
total
train
6,473
1,864
251,097
31,281
290,715
validate
790
245
31,357
3,957
36,349
test
796
233
31,387
3,945
36,361
Table 1: Statistic OneDiff dataset. See appendix for more information of other dataset.
Total
Location
Operator
Value
Type
Top-3
Top-1
Top-3
Top-1
Top-1
Top-3
Top-1
Top-3
Top-1
TOTAL
26.1
14.2
35.5
20.4
34.4
52.3
29.1
76.1
66.7
ADD
52.9
39.2
69.6
51.4
70.6
65.7
55.1
76.8
68.5
REP VAL
23.4
11.9
33.3
18.5
31.7
53.0
28.8
REP TYPE
71.7
52.4
73,0
52.8
79.4
74.7
61.0
DEL
39.6
24.8
44.0
27.5
45.8
Random
.08
.07
2.28
1.4
27.7
.01
.01
.27
0
Table 2: Evaluation of model on the OneDi ff dataset: accuracy (%)).
an attempt to filter our dataset only include bug fixes, we use heuristic based the number of changes to the AST. Our insight is that commit with a smaller number of AST differences is more likely be a bug fix than a commit containing large changes. Thus for the experiments. different datasets: OneDi ff with precisely one edit; ZeroOneDi ff with zero and one edit and zeroOne TwoDiff with zero, one or two edits. We additionally filter out data points with ASTs larger than 500 nodes as a parameter in our system. A detailed overview of our corpus crawler is available in Appendix B.
use three
6.1 EVALUATION
We train the model for epochs on the training set until the validation loss converges. We tried different configurations of our model with different number of layers and different graph embedding methods besides the generic one in Eq 2. We report on these ablation studies in Appendix C.
Table shows the evaluation results of model on held out test set consisting of samples from our OneDiff if dataset. Additional experiments on ZeroOneDi ff and ZeroOne TwoDiff datasets are available in Appendix A. We also provide experimental results with respect to different configurations.
Accuracy is shown for each graph edit operation type. Accuracy is measured in complete discrete graph edit operation step. For example consider Figure la, in which we edit an object property name with the REP_VAL operation. If the model incorrectly predicts the edit operation be of type DEL, then it will not go on to predict a value. In this case, the model will be penalized twice in the operation accuracy as well as the value accuracy. A prediction is considered totally correct only if the entire sequence of graph edit primitives is correct. Note that top-1 greedy prediction is not always among top-3 when beam search is used. Additionally, operator prediction only evaluated on the top prediction as the search space only includes four operators.
To demonstrate the magnitude of the search space, we compare HOPPITY to a model that selects uniformly at random, in each step of the graph edit process. The random model performs well at operation type selection since the search space only has four options (ADD, REP REP_VAL, REP_TYPE, DEL.. However, after the operation type is predicted, the random model's accuracy drops, as there are up to 500 nodes in the buggy AST. When it predicts value, the accuracy drops even further as our vocabulary contains 5,000 values. Lastly, type prediction has slightly better accuracy than value prediction because the number of the types of AST nodes in total is smaller than our vocabulary.
6.2 BASELINES
As existing approaches cannot be applied for comparison in Table 7, we adapt the baselines to some restricted settings in this section. We report the results the OneDif iff dataset most of the baselines target repair single bug. Note that for all comparisons we provide equal amounts of information to HOPPITY and the baseline without retraining our model.
7

---

Published as a conference paper at ICLR 2020
Type
GGNN-Rep
GGNN-CIs
HOPPITY
Top-1
Top-3
Top-1 53.2%
99.6% 99.6%
90.0%
HOPPITY SequenceR
67.7% %
73.3 %
Top-3
85.8%
94.8%
64.2%
68.6%
Table 3: REP_ accuracies with location Seaationn+-po.. op.. Table 5: Overall OneDiff accuracy with location.
Bug Type
Amount
TAJS
HOPPTTY
Value
GGNN-Rep GGNN-RNN
HOPPITY
Undefined Property
0
Functional Bug
11
0
3
Top-1
63.8%
60.3%
69.1 1%
Refactoring
12
0
Top-3
67.6%
63.6%
73.4%
Total
30
0
Table REP __L accuracies with location+-op.
Table 6: Comparison with TAJS.
Allamanis et al. (2018), uses Gated Graph Neural Networks (GGNN) for two specific bug repair tasks: VARMISUSE, in which the model learns select the correct variable that should be used at a given location, and VARNAMING, in which the model predicts a variable name based on its usage. We adapt these tasks compare with HOPPITY the REP TYPE and REP VAL tasks. Specifically, for _YPE prediction we have
GGNN:
GGNN-Rep: we adopt VARMISUSE replace with candidate node type and modify the graph
structure correspondingly: we use their proposed max-margin formulation for training. GGNN-CIs: we perform multi-class classification using the target node and graph embedding.
For REP REL_VAL prediction, we also made two versions of adaptations:
GGNN-Rep: similar above, here the candidate set is from values in the current graphs plus the
top-100 frequent values used for repair in the training set.
GGNN-RNN: we adopt VARNAMING approach to predict value directly. Due to the huge vocabulary size, we use char-level language model for predicting the replacement.
Table 3 and 4 show the comparison when buggy node is known. Regarding the type prediction, as the number of types is large, the likelihood formulation with classification objective outperforms the max-margin loss based one (i.e., GGNN-Rep). As this limited case GGNN-CL CCs and HOPPITY are quite similar except for graph representation, the performance is expected to be comparable. As HOPPITY is not trained to predict type fix only, it performs slighly worse than GGNN-Cls. Also for the value prediction, our formulation of pointer graph is more effective. We found when the space of decisions is large, is hard to apply structured prediction method like GGNN- Rep in this setting. Since real-world programs are noisy, the sentences used in different programs vary greatly, making difficult for language models to predict the exact accurate value. A possible extension is to combine the language model with the graph pointer, which we will explore in future work.
The model proposed by Chen et al. (2018) is a translation based model that predicts a fixed sequence of tokens when given buggy line in the source code. We compare with our model by providing location information to both approaches.
SequenceR:
Table 5 summarizes the total accuracy for fixing a single bug. In order to provide fair comparison, we allow SequenceR to predict the same information as our model (i.e., predict op. value etc. in sequential way), rather than entire sequence of raw textual tokens. This experiment shows the benefit of formulating code repair with graphs over text tokens.
With the above two baselines, we can see that in the restricted case our model can still yield comparable or even better performances. Given that our model can go for more edits without location information, we believe this tool is more generic and effective for code repair.
We also compare the bug detection ability of HOPPITY against TAJS (Jensen et al., 2009) which is a well-known static analysis tool for Javascript programs. Automating the comparison for our entire test set proved to be infeasible. For example, TAJS only accepts JavaScript ES5 programs, while the vast majority of current JavaScript projects use ES6 or other variants like React JSX. Another problem is that TAJS does not analyze code that is not invoked, e.g., a library function that is not called by client code. Moreover, determining the right command-ling options of TAJS is non-trivial since it provides many options targeting different JavaScript runtime environments. Due to these issues, we forgo a large-scale comparison, and instead pick random points in our test set to manually analyze using TAJS. Table 6 depicts the results (Appendix D provides further details).
TAJS:
8

---

Published as a conference paper at ICLR 2020
We restrict the chosen test points to satisfy a necessary condition for undefined property bugs since TAJS claims to be proficient in detecting this class of bugs. In the process, we also pick some functional bugs, as well as cases of refactoring modifications. By resolving the numerous issues that prevented us from automating the comparison, we were able to run TAJS manually. TAJS failed to detect any real bugs in the 30 test points. While functional bugs and refactoring modifications beyond TAJS, however, TAJS also raises many unrelated false alarms due to its failures in locating NodeJS libraries, importing JSON files, or recognizing built-in global variables. These warnings are detrimental because TAJS suspends the analysis as soon as it detects what it preceives to be bug, To further aid TAJS, we omitted parts of each program that are unrelated to the bug, in the hope of driving TAJS's analysis as deep possible. After all these measures, TAJS managed to detect two of the undefined property bugs (Bug IDs and Appendix D).
In contrast, HOPPITY is able to correctly detect 5 bug locations of the 30 testing points within our top 3 predictions. Moreover, HOPPITY also produces 4 patches that are identical to the developer's fixes. Our comparison highlights HOPPITY's ' two important strengths compared to TAJS. First, HOPPITY relieves developers from the enormous burden of manual configume onniguration. Second, HOPPITY achieves far better performance in detecting as well as fixing the bugs in Javascript programs.
RELATED WORK
Static analysis for bug detection. Static analyzers such as FindBugs, Error-Prone and Semmle use syntactic mattern-matchin and dataflow analysis to find common bugs. Typically, detecting even single class of bugs can require dozens or even hundreds of patterns. Coverity (Bessey et al., 2010), SonarQube, and Clang Static Analyzer check for semantic inconsistencies in code based on more sophisticated path analyses. Infer (Calcagno et al., 2015) is built upon sound principles and can prove the absence of certain classes of bugs. TAJS belongs to this category as well. Due to the undecidability of the problem. however, approximations are inevitable which voids the guarantees in practice. Compared to all static analysis tools, HOPPITY offers the following advantages: (1) it targets a board range of programming errors; (2) it not only localizes bugs but also fixes them; and (3) it has significantly higher signal-to-noise ratio (i.e., detects more bugs with less false alarms).
Learning-based bug detection. Allamanis et al. (2018) target seriable-misuse errors and present a solution based on a gated graph neural network model to predict the correct variable name given buggy location. Vasic et al. (2019) present a pointer network on top of a RNN which outperforms Al- lamanis al. (2018) on the same task. DeepBugs (Pradel & Sen, 2018) proposes a hame-based bug detection scheme. Their model is trained to predict three classes of bugs: swapped function arguments, wrong binary operator, and wrong operand in a binary operation. Compared to these models, our approach is capable of detecting and fixing a wide range of errors in Javascript. SequenceR (Chen et al., 2018) uses seuvence-to-equenee Getafix (Scott et al., 2019) produces human-like bug fixes by learning from past fixes. It employs a hierarchical clustering algorithm that sorts fix patterns according to their generality. While these approaches are general against different types of bugs, they still need the bug location as input.
model to translate a buggy code segment into correct one;
Graph learning and optimization. Our work is closely related to the literature in graph repre- sentation learning and optimization. Our model uses variant of GNN that is inspired by many representative works (Li et al., 2015; Xu et al., 2018; 8; Si et al., 2018), with the adaptation of local value table and pointer mechanism. Our work is also related to auto-regressive graph modeling Johnson (2016); Li et al. (2018); Brockschmidt et al. (2018); Dai et al. (2018), but with more generic operations such as subtree deletion and attribute modifications. Some other works model the graph modification in latent space (Jin et al., 2018; Yin et al., 2018), but such frameworks lack fine-grained control over the generative process, and thus are not very suitable for performing code repair.
CONCLUSION
We proposed an end-to-end berning-based approach to detect and fix bugs in Javascript programs. We realized the approach in tool HOPPITY and demonstrated that it correctly predicts 9,490 out of 36,361 code changes in real programs on Github. In the future, we plan to expand the targeted bugs to include those that are caused by the interdependence among multiple files or that require multiple steps to fix. We will also deploy HOPPITY in an IDE to further evaluate its accuracy and utility. Finally, we plan to extend our learning framework to support other languages. Due to its anguuage-iddeeendence we believe HOPPITY will benefit developers beyond Javascript as well.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We thank the reviewers for their insightful comments. This research was supported in part by NSF awards #1 1836936 and # #1836822, ONR award #N00014-18-1-205 and Facebook research awards.
REFERENCES
Miltiadis A Allamanis, Marc Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. International Conference on Learning Representations, 2018.
Thomas Ball, Mayur Naik, and Sriram K. Rajamani. From symptom to cause: Localizing errors in counterexample traces. In Proceedings of the 30th ACM SIGPLAN-SIGAC/ Symposium Principles of Programming Languages, 2003.
Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler. A few billion lines of code later: Using static analysis to find bugs in the real world. Communications of the ACM, 53(2), February 2010.
Marc Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXiv preprint 0rXiv:1805.08499 2018.
Cristiano Calcagno, Dino Distefano, Jeremy Dubreil, Dominik Gabi, Pieter Hooimeijer, Martino Luca, Peter O' O'Hearn, Irene Papakonstantinou. Jim Purbrick, and Dulma Rodriguez. Moving fast with software verification. In NASA Formal Method Symposium, 2015.
Zimin Chen, Steve Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. Sequencer: Sequence-to- to-sequence learning for end-to-end program repair. arXiv preprint arXiv:1901.01800 2018.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint arXiv:1806.02377 2018.
Github. State of the Octoverse.
2019.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint
arXiv:1410.5401, 2014.
Jinru Hua, Mengshi Zhang, Kaiyuan Wang, and Sarfraz Khurshid. Sketchfix: tool for automated program repair approach using lazy candidate generation. In Proceedings of the 2018 26th ACM Joint Meeting on Europeun Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2018
Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type analysis for javascript. In Proceedings of the 16th International Symposium on Static Analysis, 2009.
Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecular optimization. arXiv preprint arX1v:1812.01070, 2018.
Daniel D Johnson. Learning graphical state transitions. 2016.
Manu Jose and Rupak Majumdar. Cause clue clauses: Error localization using maximum satisfiability. In Proceedings the 32nd ACM SIGPLAN Conference Programming Language Design and Implementation, 2011.
Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. Automated program repair. Commun. ACM, 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint 15/1v:55 2015.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 0rXiv:1803.03324, 2018.
Michael Pradel and Koushik Sen. Deepbugs: A learning approach to name-baat based bug detection. Proc.
ACM Program. Lang., 2(0OPSLA), 2018.
10

---

Published as a conference paper at ICLR 2020
Caitlin Sadowski, Jeffrey Gogh, Ciera Jaspan, Emma Söderberg, and Collin Winter. Tricorder: Building program analysis ecosystem. In Proceedings of the 37th International Conference on Soffware Engineering, 2015.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Andrew Scott, Johannes Bader, and Satish Chandra. Getafix: Learning to fix bugs automatically. volume 2, 2019.
Xujie Si, Hanjun Dai, Mukund Raghothaman, Mayur Naik, and Le Song. Learning loop invariants for program verification. In Advances in Neural Information Processing Systems, pp. 7751-7762, 2018.
Marko Vasic, Aditya Kanade, Petros Maniatís, David Bieber, and Rishabh Singh. Neural pro- gram repair by jointly learning localize and repair. International Conference on Learning Representations, 2019.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Yu Wang, Fengjuan Gao, Linzhang Wang. and Ke Wang. Learning a static bug finder from data. arXiv preprint arXiv: wrXxv:1907005579 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 1rXiv:1810.00826, 2018.
Pengcheng Yin, Graham Neubig, Miltiadis Allamanis, Mare Brockschmidt, and Alexander L. Gaunt. Learning to represent edits. arXiv preprint arXiv:1810.13337, 2018.
Nicholas C. Zakas. ESLint. https://eslint.org/.200 2013. 2013.

---

Published as a conference paper at ICLR 2020
A
ADDITIONAL EXPERIMENTS
Total
Location
Operator
Value
Type
Top-3
Top-1
Top-3
Top-1
Top-1
Top-3
Top-1
Top-3
Top-1
TereOneTwoDiff
40.8
29.7
18.9
3.9
30.3
35.0
6.5
38.6
ZeroOneDiff 51.6
34.5
27.1
5,5
35.6
45.4
10.4
73.9
58.9
OnsDiff 26.1
14.2
35.5
20.4
34.4
52.3
29.1
76.1
66.7
Random .08
.07
2.28
1.4
27.7
.01
.01
.27
Table 7: Evaluation of models each dataset. The Random model is evaluated on the OneDiff dataset and shown for comparison.
Full experiment results In addition to the evaluation of samples with one edit Table 7, we also evaluate HOPPITY on the following datasets:
ZeroOneDiff Includes samples with labels of zero or one edit
ZeroOneTweD ff Includes samples with labels of zero, one, or two edits.
We trained models each dataset for roughly 12 hours on a single GTX 2080Ti GPU. Accuracy on the ZercOneDiff ff is the highest as predicting that an AST is not buggy does not consist of any low level primitive predictions. This makes a much easier prediction for the model than say, an ADD operation which the parent location, left sibling, value, and type must all be predicted correctly in order to be considered accurate.
TRUE LABEL
BUGGY
NOT BUGGY
ALARM NO ALARM
T0,293 26,517
7,210
PREDICTED
20,605
Table 8: Results true/false predictions.
False positive/negative study An evaluation of false positives and false negatives is available in Table this setting, we treat the problem as a classification problem on our ZeroOneDi ff dataset and model attempts predict if given AST is BUGGY NOT BUGGY. If the model pre- dicts ADD, REP REP_VAL, REP TYPE, or DEL, we consider this a prediction "BUGGY." Accordingly, if the model predicts _O_OP, we consider this to be prediction of "NOT BUGGY."
Accuracy v.s. size of graph To demonstrate the affect of AST size on HOPPITY's prediction accuracy on the of dataset, we include Figure 4. As expected, AST size and accuracy are inversely related.
Beam Size (k)
Top-k Accuracy (%)
14.37%
2
21.10%
3
26.14%
4
30.12%
5
33.58%
Table 9: Accuracy vs beam sizes.
Accuracy v.s. beam search size In Table we compare the performance with different beam sizes on the OneDife ff dataset. As we can see, the top-3 accuracy with beam size 3 is significantly better than t accuracy with just greedy prediction. This is expected, in the decision process there "bottleneck' stages with only a few predictions (c.g., the op prediction). Thus from beam-l I to beam-3 there's huge improvement, but further beyond the performance maxed out.
12

---

Published as a conference paper at ICLR 2020
Size
0.8
0.4
0.0
1000
nodden flowed AST
Figure 4: End-to-end code repair accuracy v.s. size of AST of source code.
B DATA COLLECTION
We have built a robust system to automatically collect millions of bug- sig-fixes in Javascript programs from Github. Our system continuously crawls Github for commits containing Javascript files and creates a label consisting of the change to the AST corresponding to each such file.
Our system consists of three entirely automated parallel steps:
Collect Commits: Our system uses the GH Archive API to easily access Github event data for a specific hour in time. After obtaining all data for the hour, filter this using the Github API to only include commits that consist of edits to Javascript files.
obtaining list of valid commits from step 1, we begin downloading the pair: (STCbuggy: STCfi where SrChugay is the file prior to the commit, and srCfized is the file following the commit that contains the changes made.
2. Download Files: As
3. Create Label: For each Javascript file downloaded, we parse the source code into a JSON format of the AST. Our system uses the SHIFT AST Abstract Syntax Tree representations are designed to naturally and intuitively represent the structure of the source code. Because of this design goal, small changes in the source code can often lead very large changes in the AST. We chose the SHIFT AST representation with consideration to our goal of maximizing the number of commits with only one difference between the ASTs. This component produces a pair ASTs: (ASTomggyy fize). which point a JSON differencing algorithm, fast-jsonn-aatee includes the operation type and node edited for each difference between AST buggy and AST fixed-
is applied to create a label. The label
Each step of this process parallelized in order to grow our corpus as quickly as possible. Our dataset has the advantage that it is continuously growing without human input.
Our system is language independent and highly extensible and modular. For example, it can handle any language so long as it can be parsed into JSON AST.
For each label, we must download two files SrCbuggy and srCfired- Additionally, if source files cannot be parsed into a SHIFT AST, label cannot be created. For our learning corpus, we limit the dataset to only include labels with one AST difference. Additionally, an attempt to limit graph size, we only include data points in which the ASTTuugg and AST fived have less than 500 nodes.
'https///shit-ast..rr//
13

---

Published as a conference paper at ICLR 2020
Total Files Downloaded:
52,719,402
Total Labelled Data Points:
15,225,347
# AST differences:
# data points:
0
3,473,391
1
1,863,193 193
2-10
3,247,437
11-20
2,117,977
21-50
2,047, 998
51-100
358.981
101+
921,754
Table 10: Data collection statisties.
Number of cata points with AST drts
2920000
502000
Figure 5: Distribution of number of edits the entire crawled dataset.
Figure 5 plots the distribution of number of edits that are recorded in Table 10. We the distribution is long tail, with majority of edits as I or 2.
14

---

Published as a conference paper at ICLR 2020
C ABLATION STUDY
We tried different graph representations with corresponding graph embedding methods. The mudti represents the multi-graph defined by different edge types, with the parameterization of message passing function mentioned in Eq 2; the code2inv is the parameterization used in Si al. (2018); the single instead uses single graph with edge types one-hot edge features. We found that more layers does not lead to better generalization in our setting, and it becomes slower terms of convergence. So report the results with 4 layers in main paper.
model
max lv
Total
Operator
Location
Value
Type
multi
20
7.63
30.0
13.1
22.6
54.5
multi
14
11.05
48.0
17.9
38.6
61.6
multi
4
13.33
53.4
36.2
38.6
56.4
code2inv
20
10.3
18.1
25.7
38.8
57.7
code2inv
14
8.92
40.0
18.1
36.0
55.9
code2inv
4
13.29
30.8
18.9
28.2
68.21
single
20
5,00
20.2
10.3
14.2
44.8
single
14
10.69
67.7
18.6
49.6
38.7
single
4
12.88
55.8
20.8
43.2
55.8
Table 11: Ablation study with different graph embedding parameterizations and different number of layers. Full end-to-end repair accuracy as well the accuracies for each primitives are reported. All the numbers are for top-1 prediction.
15

---

Published as a conference paper at ICLR 2020
D 30 RANDOM TESTING POINTS FOR TAJS BASELINE STUDY
29 www.iee.cvvviiaeeeeom.......
30 org www.ciiiimmmmmmmmm civicase
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
ID Gilhub Link Dill
8
2
WishhrdWitthDiiee Database
cryptii
to rest
koot
Mirza-totally-rooe
Talks
simple-cne cemple-caftiigg
WTF- Adventure
zulip
matic.js
graph-js
Craxi
i5-leds
flom--react
iotdb iotdb-monge mongodb
Orca
pandora- validation
AloChat
react -aaive--veeee with-redux react- wotit--aiiiinn-----e 2 b-boilerplate
mackkincinnati/se
ALFACharts
musketeer shop
React- QuizQuuuooneann Component
mn-mitrais-oe mb
E--oomande and evvntts actingg-nnn--- -wt-aaa-t--nvveeeeeeeea onveeents- Jab-y-bbb
MEAN
LetsRoll
js-ajax-hia hitting apis lab--abbbbb lab-v-00b-- v-000 romaZhira
CaseDetailsFFilehhh
help.js
ROT13.J
index,js
before router match.js
Form.
index,js
gather.js
mana js
stream muting.js
point,js
display.js
blink.ji
question.js
count.js
2.js
index,js
Container.js
splash.js
Advisors. js
crosshairs.f
order.js
Quiz PuizQuestion.js
ListAlbums,j
articl es. reseeerrr.rous...ss index,js
routerjj
index convert.js
File
areAvailables
print ()
registerSetting
EestRecipes
origin
SeeckTalkkwnereee getRecips
add add_ messagesseessss.......s.. this s._.... super getBehavicr or
ETHF ETHF aucetAddress
data
game draw ()
Data MataTypes STRING blink
then
erase ()
addAsyneSeton
PropTypes string
COLOR DARK
color prima my
Math. floor
DECIMAL
(obi) (obj).inst:an instinnrtttt ion texts
info. type
app params (elem) Inne-neer InnerETM LFTML
(olom (om) valuu username
login
Buggy Code
printsplit it ( isAllowed
addSett ing
originTrus
get Rect pes
che www.ccCooneettoeeeee.
getMeta
add add_ol messagge thi s. super
dat dat aMana ger ЕTHFAUCET ADDRESS
game run ()
Dat Tytes TEXT strobe.
make
addSSreSSetup exploder ()
PrepTypes ob abject ject
COLOR PANTOME
Math, round color: accent
INTEGER
(obi) ( instruct ion text
info album type
(el (elem) . iinerrt
app paran
use use xName
(cl innerüTML
name
Fixed Code
preference
16

---

Published as a conference paper at ICLR 2020
29
28
27
25
24
23
21
20
19
17
16
15
13
12
ID
9
refactoring
refactoring
refactoring
refactoring
refactoring
refactoring
refactoring
refactoring
refactoring
refactoring
refactoring
functional bug ref refactoring
funetional bug
funetional bag
functional hag functional bag functional bug functional bug functional bog
undefined property undefined property functional bug functional bug functional bug
undefined property
undefined property
undefined property
undefince property
undefined property
Bug Type
Failed importing library
Failed importing library Failed importing library
Failed importing library events
Undefined process
Failed importing library util Undefined process Failed doc get
Failed doc get cm ()
False Alarm
TAJS
experts testRecipes =
this. game draw ()
led. strobe (750)
servi cwwviiderovidee addAsyncSSttupppp (...) (...)
app paraams (*... ."..., ...)
Prediction
HOPPITY
<
Top
Top
Top
17


Reviews:
[{"review_id": "Syg633Qs_H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a graph tranformation-based code repair tool. By representing source code as a graph a network is asked to take a series of simple graph edit operations to edit the code. The authors show that their method better predicts edits from existing code.\n\nOverall, I find the problem interesting and the neural approach of the authors reasonable, principled and interesting. However, the evaluation is either badly written or the authors have not understood the related literature they are comparing to. It is thus unclear how this model compares to alternatives. I believe that this is good work that needs to eventually be published, but it's not ready at this time.\n\n* In 3.2.1 \"Value\" paragraph \"Instead of predicting the replacement value using a language generative model (Chen et al 2018, Allamanis et al 2018), we let the model to choose from either the values appearing in the current file.\" \n  \n   -The Chen et al. (2018) paper is indeed a translation-style model, but thanks to the copying mechanism, the model can also choose from values appearing in the current input.\n   - The Allamanis et al. (2018) is *not* a generative model and it can only select a misused variable for those that exist on within the scope (for the Variable Misuse Task)\n\n* The authors compare to the VARNAMING (Section 6.2) task of Allamanis et al. (2018). This is odd, since to my understanding, this task is about alpha-renaming, i.e. semantics preserving renaming of all identifiers of a variable. This is not comparable with the REP_VAL action which simply replaces the value of a single leaf node from the value table. The VARMISUSE objective (picking one variable directly from the value table) is the closest analogue, although it performs no localization. \n\nThus, it is not surprising that a char-level language model cannot predict the names of the elements in the value table. So, I don't think that we learn anything from the current comparison.\n\n* It's unclear to me why the REP_TYPE action is relevant to VARMISUSE task of Allamanis et al. (2018). This seems to simply be a classification task (among all known/valid types of the tree) given an existing position.\n\n* Given the above two points, it's unclear what the comparison with the baseline (Table 3) means and what one can deduce from the evaluation: The Allamanis et al. (2018) work tries to find the correct variable at a given location; this work tries to pick a location and find a different value from current one. The Allamanis et al. (2018) and Cvitkovic et al. (2018) uses additional semantic information (as edges), importantly data flow and control flow. This work uses none of those. I am not sure that I can see how the comparison here can work.\n\n* In 3.1 \"Unlike previous approaches, we additionally add value nodes that store the actual content of the leaf nodes [...]. The purpose of introducing this additional set of nodes is to provide a name-independent strategy for code representation and modification\". I am not sure what's unlike previous approaches. For example, the Allamanis et al. (2018) and the Cvitkovic et al. (2018) work, connect the same variables with various ways (e.g. data-flow edges) in a way that provides a name-independent strategy for code representation. I would fing it surprising that a principled comparison between Allamanis et al. (2018)/ Cvitkovic et al. (2018) and this work will yield any improvements: all papers use the same model (variations of a graph neural network) and this work uses strictly fewer information (no data flow, control flow edges). A comparison would simply compare how the two graph-extraction methods compare, but nothing valuable otherwise.\n\n* The authors of this work frequently refer to Chen et al. (2018), but never compare with it. I would expect that this model beats the Chen et al. (2018) work, but this needs to be shown. In my opinion this is a much more relevant baseline, compared to the comparison with Allamanis et al. (2018). If the authors insist on comparing with that work, then a \"fair\" comparison needs to be made. Comparing between REP_VAL and VARMISUSE given the location of the node-to-be-repaired, is probably the only reasonable option. Comparing with Vasic et al. (2019) for the REP_VAL/REP_TYPE would also be reasonable.\n\n* The correctness of the NO_OP predictions are never evaluated. Does the model \"know\" when to terminate or does it keep editing? It's unclear what is the overall accuracy (for a full edit).\n\nOther questions:\n\n* The \"ADD\" operation predicts two locations: one for the parent and one for the left sibling of the node. Does this mean that for a given node the \"ADD\" operation will never be able to add a left-most child (since it has no left sibling)?\n\n* It has been recently found that code corpora collected by scraping GitHub may contain a disproportionate amount of duplicates (Lopes et al. 2017, Allamanis 2018). It is unclear if the authors have taken any steps to detect and remove duplicates that would affect their results.\n\n* In Table 2: Does \"Beam-3\" mean \"accuracy in the top 3\" or does it mean \"accuracy of the top prediction when the beam size is 3\"? The difference between \"Beam-1\" and \"Beam-3\" is surprisingly large. Can you explain why?\n\n* In the TAJS comparison, it is unclear if any negative examples are added: it's unclear what's the false positive ratio of HOPPITY vs TAJS.\n\nMinor:\n\n* Abstract: \"Github\" -> \"GitHub\"\n* 3.2 REP_VAL: \"Tthe\"-> \"The\"\n* Sec 7: \"Vasic et al. (2019) present a pointer network...\" It is unclear if this work outperforms the Allamanis et al. (2018) work as the comparison is only partial. Another ICLR submission https://openreview.net/forum?id=B1lnbRNtwr suggests that this is not the case.\n* The citation of Chen et al. (2018) should be capitalized correctly \"Sequencer\"->\"SequenceR\"\n\n\n## References\n\nAllamanis, Miltiadis. \"The Adverse Effects of Code Duplication in Machine Learning Models of Code.\" arXiv preprint arXiv:1812.06469 (2018).\n\nCvitkovic, Milan, Badal Singh, and Anima Anandkumar. \"Open Vocabulary Learning on Source Code with a Graph-Structured Cache.\" arXiv preprint arXiv:1810.08305 (2018).\n\nLopes, Cristina V., et al. \"DéjàVu: a map of code duplicates on GitHub.\" Proceedings of the ACM on Programming Languages 1.OOPSLA (2017): 84.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Hkl8GXDRYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "JavaScript is the standard programming language of the Web; according to the stats it is used on 95% of the (at least) 1.6 billion websites in the world.  Compared to other programming languages, it posses certain unique characteristics which are also responsible for making it so popular for the Web.   In this interesting work the authors aim to provide a novel data-driven system for detecting and automatically fixing bugs in Javascript.  The authors provide motivating examples behind their research. Indeed, Javascript poses unique challenges as described eloquently in Section 2, and there is a lot of space for improvement. Static analyzers have non-trivial limitations, while there is space for improving data-driven approaches. This is what Hoppity aims to achieve by translating the program into a graph, embedding the nodes and the graph as points in a d dimensional space using graph neural networks, and then using a controller that uses LSTMs decide the action to be taken among a predefined set of possible actions or a single step graph edit. These actions are reasonable, and are able to fix many bugs assuming the right sequence of actions is performed. For the purposes of learning, the author(s) use a corpus crawled and preprocessed from Github that contains more than half a million programs. Overall, I found this paper very interesting to read, and with large potential impact in practice. The paper contains a solid engineering effort, starting from the dataset collection and its preprocessing, to using state-of-the-art machinery to develop Hoppity. Therefore, I support its acceptance. However, some things were not clear from the writeup, and I hope the author(s) of the paper can give some insights. \n\n- What is the effect of parameter T, i.e., the number of iterations? How is it set in the experiments? Clearly, the authors have a knowledge of what T should be since they have preferred programs with fewer commits.\n- Following on my previous point, given the sequence of changes/graph transformations you perform, what is the distribution of the 'edit distance' (i.e., number of hops to fix a bug) in the dataset that you have? While the author(s) have \nalready provided a lot of stats in the Appendix, it would be interesting to see such a plot. This distribution could be insightful and serve as a rule of thumb for understanding the effect of T. \n- What is the effect of the beam size? Can you plot  the accuracy  as a function of the beam size? \n- Have you tried points with more than 500 nodes to see how the size of these graphs affect the performance of Hoppity? \n- Can you provide further details on the running times and the GPU specs?   \n- The evaluation does not put enough emphasis on false positives/false negative analysis. Is it the case that bug-free programs are treated as such? \n-  Have you tried Hoppity on other programming language(s)?  Do you expect such an improved performance over baselines for other languages (e.g., C++) as well?\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HkemRjoaKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to learn from bugfixing commits to fix errors in other code. There are several good contributions of the paper, but the main one is to design a language of instructions that fix a program and to formulate the prediction to be a sequence of such instructions. The model, however, is insightful in other ways as well. The lack of naming features or generation of names makes it to point to other identifiers in a program - a major problem for most models for code. Instead, the proposed model only builds embeddings from the structure around the variables.\n\nThe work is also well evaluated, on real dataset and also it attempts to compare to the best available static analysis tools. The kind of bugs addressed by the work was also not considered in previous papers. One thing that comes to the examples of the discovered bugs is that even when the fix is shown, the user would still need detailed explanations on why was it a bug.\n\nSo, I also have questions for the authors:\n1. Do you think it is possible to observe a similar reasoning to the reasoning in your text for why the buggy examples from Figure 1 are wrong, if the activations of the neural network are exposed or with other NN debugging technique.\n2. It seems that a specific sequence of actions is provided in the training data and that sequence is left-to-right edits to apply the fix. In this case, doesn’t it make sense to apply restrictions on the Location primitive similar in spirit to the attention masking (see here: http://jalammar.github.io/illustrated-gpt2/#part-2-illustrated-self-attention )\n\nMinor:\n- NO_OP was used in some places (pages 4 and 5) and STOP in others (figure 2).\n- N_k(v) is not defined.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a learning-based approach to detect and fix bugs in JavaScript programs. By modeling the bug detection and fix as a sequence of graph transformations, the proposed method achieved promising experimental results on a large JavaScript dataset crawled from GitHub.

All the reviews agree to accept the paper for its reasonable and interesting approach to solve the bug problems. The main concerns are about the experimental design, which has been addressed by the authors in the revision. 

Based on the novelty and solid experiments of the proposed method, I agreed to accept the paper as other revises.

Decision: Accept (Spotlight)