Title: HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS

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 built upon deep neural networks, our approach targets bugs that are more diverse and complex 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.

1. INTRODUCTION:

The sheer size and complexity of modern codebases makes it impossible for them to be bug-free. As a 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 Tricorder (Sadowski et al., 2015) , Facebook'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 (Allamanis 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 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 are 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 a novel learning-based approach for finding and fixing bugs in Javascript programs automatically. Javascript is a scripting language designed for web application development. It has been the most popular programming language on 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 ability to deal with bugs that are more complex and semantic in nature, namely, bugs that require adding or removing statements from a 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 et al., 2018; Chen 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 our model architecture in a similar vein as a Neural Turing Machine (NTM) (Graves et al., 2014) . It consists of an external memory (a Graph Neural Network) for embedding a buggy program and a central controller (an LSTM) that makes a sequence of primitive actions (e.g., predicting type, generating patch, etc.) to perform a fix. The multi-step decision process is 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 a 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 to the weak, dynamic typing discipline of scripting languages, Javascript supports many peculiar features that do not exist in other languages. For example, it allows a property (i.e., a field) to be added to or removed from an object at runtime. As another example, Javascript did not support block-level scoping until recently, allowing a variable defined in a block structure such as a 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 a large body of legacy code. Finally, Javascript's eval function, which interprets and executes a string as a code fragment, is widely regarded as a major source of bugs and vulnerabilities. All of these aspects make programming in Javascript a frustrating and error-prone experience. (c) copy function should have also been included in the highlighted list. Static analyzers aim to detect common coding errors in Javascript programs by applying logical rulebased 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 1 to illustrate their limitations. Due to the complex nature of client-side web APIs, TAJS and ESLint choose to ignore analyzing built-in libraries for the sake of scalability. As depicted in Figure 1a , when developers mistakenly capitalize the first letter of innerHTML, a property of class Element in DOM (Document Object Model), both analyzers fail to catch 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 a security vulnerability or incur a costly debugging experience. 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 a string using regular expressions. However, the program incorrectly splits the input ' and ' into ['', ' and ', ''] 

GNN GNN No Action:



Global value dictionary:

Global type dictionary the error is simply a mismatch between the developer'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 to human programmers. The criteria they use is very simple: any code snippet that seems to deviate from common code patterns is likely to be buggy. This is precisely the observation that our approach seeks to mimic. In particular, if a model observes a property or 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 a single model to deal with a wide range of bug types, encompassing all previously proposed ones. Compared to past approaches that leverage a 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 1c and 1d . 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 a structured prediction problem on a graph-based representation of programs. Given a graph g bug that represents a buggy program, we wish to predict a graph g f ix that represents the fixed program. Our model aims to capture the structured prediction by a sequence of up to T steps of graph transformations:

EQUATION

The high-level overview of the graph sequence transformation is shown in Figure 2 . Different programs may need a different number of steps T (g bug ) 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 in Sec 3.2. Finally, we summarize and present the full model in Sec 3.3.

3.1. PROGRAM REPRESENTATION:

Programs written in a high-level 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 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 a name-independent strategy for code representation and modification, which we elucidate in the next section. Hereafter, we use g f ix , g bug or g in general to represent either the source code or the corresponding graph structure.

After representing the program as a graph, we use a Graph Neural Network (GNN) (Scarselli et al., 2008) to map the graph into a representation in a fixed dimensional vector space. Specifically, given a graph g = (V, E) with set of nodes V and edges E, we need a function

f (g) → (R d , R |V |×d )

to obtain the d-dimensional representation of graph g (denoted as g), as well as representations of individual nodes v ∈ V (denoted as v). To parameterize f (•), we employ the form in GIN (Xu et al., 2018) , with our adaptation to our multigraph for program representation in the following manner:

EQUATION

where

W l,k 1 ∈ R d×d , W l 2 ∈ R dK×d 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 v = h (L)

v , where L is the total number of propagations in the GNN. N k (v) is the set of neighbors of node v that are connected by edge with type k. Following GIN, the graph representation g is the aggregation of h l v , ∀l ∈ 0, 1, . . . , L. We use max pooling to aggregate h l v for each l, and then take the average of these L + 1 vectors to obtain g.

Initially, we use the node type as one-hot features as a starting value for h (0) v , 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 use features like variable names or 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 as to enable naming-agnostic representation across different programs.

3.2. ONE-STEP GRAPH EDIT:

There are five types of operators to choose from for a single step graph edit, namely, adding a node (ADD), deleting a node (DEL), replacing a node value (REP_VAL), replacing a node type (REP_TYPE) and stop (NO_OP). When combined with multi-step edits, these operators suffice to capture a 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 as c ∈ R d . 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.

Location The location primitive locates a 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 a node selection step. As different programs have different numbers of nodes, we employ a pointer network (Vinyals et al., 2015) into the graph structure. Specifically, after obtaining the node embeddings { v} v∈V , we select the node via loc( c, g) = arg max v∈V v c for simplicity.

Value The value primitive assigns a value for a leaf node in the AST. Instead of predicting the replacement value using a language generative model (Chen et al., 2018) or GNN score function (Allamanis 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 D val be the global dictionary of commonly used leaf-node values in the language, where each item i v ∈ D val is associated with a vector representation i v ∈ R d . The local value table is denoted as V val which is a subset of the nodes in current graph. Then, the value is predicted via val( c, g) = argmax t∈D val ∪V val 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 a given language, the type prediction is simply a multiclass 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 OPERATORS:

The t-th round of edit starts with the current graph g t-1 , the corresponding graph embedding, and the 'macro-context' embedding -→ c M t-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 is invoked to determine the node to target. Then the edit type e that is feasible at this location v is predicted out of the five operators. A 'micro-context' embedding -→ c mt is obtained from the macro embedding updated by two LSTM calls with location node embedding v and operator embedding e. To summarize:

-

EQUATION

The micro-context embedding is used as the controller throughout the process of each operator. In the following content, we 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, we 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-SuccToken, ValueLink, 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 in the order of:

c m1 = LSTM( ----→ v sibling | c m ), c m2 = LSTM(val( c m1 , g)| c m1 ) and c m3 = LSTM(type( c m2 , g)| c m2 ).

In the end, c ADD = c m3 summarizes the process. DEL This operator deletes a node and corresponding edges in the graph. If it is a 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 ValueLink 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 g bug as g 0 for simplicity. Then, for the t-th graph edit, the following steps are performed:

Algorithm 1 Transformation inference of p(g f ix |g bug ) 1: Input g bug ∼ D and model parameters θ. 2: Obtain g 0 , { v v∈g bug } = f 0 (g bug ), let c M0 be null. 3: for t = 1 to T do 4: Obtain --→ c Mt = LSTM( --→ g t-1 | ---→ c Mt-1

).

5::

Choose location v t , then edit type e t ;

6:

if e t = NO_OP then 7:

set g T = g t-1 and exit the loop.

8:

end if 9:

Perform operator e t with -→ c mt obtained by Eq 3. This process repeats until it reaches the maximum steps T 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 a 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.

4. LEARNING:

Given the dataset D = {(g

EQUATION

f ix )} |D| i=1 which consists of pairs of buggy code and the fixed code, the learning objective max θ E (g bug ,g f ix )∼D p(g f ix |g bug ; θ) maximizes the likelihood of fixes.

Since the probability is factorized according to Eq 1 where a sequence of transformations is performed, we parse the source code using the SHIFT AST format, and utilize a JSON diff toolbox to compile the code differences into a 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 t (•)} T t=1 , each of the operator module and the controller module which is parameterized by LSTM. We use the Adam optimizer with β 1 = 0.9, β 2 = 0.99 and initial learning rate of 10 -3 . Due to the large size of each sample, we use a 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 in the combinatorial space: arg max g f ix p(g f ix |g bug ; θ). Since the search space is very large, however, we use beam-search to approximately find the fixes with highest probabilities. Specifically, we maintain a pool of partially fixed programs {g}, which starts with simply the single buggy program g bug . The pool size is limited by the beam-search size B. For each g, we propose the top B locations to be modified, top B operators or 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 our 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 is based on PyTorch with customized GPU kernels to enable efficient inference on GPUs.

6. EXPERIMENTS:

Dataset Our model is trained and evaluated on a corpus of nearly half a million data points. We have created a robust system to continuously collect small changes in Javascript programs from Github. Given a commit, we download the Javascript file before and after the change: (src buggy , src f ixed ). Commits can contain many types of changes such as feature additions, refactorings, bug fixes, etc. In an attempt to filter our dataset to only include bug fixes, we use a heuristic based on the number of changes to the AST. Our insight is that a commit with a smaller number of AST differences is more likely to be a bug fix than a commit containing large changes. Thus for the experiments, we use three different datasets: OneDiff with precisely one edit; ZeroOneDiff with zero and one edit and ZeroOneTwoDiff 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.

6.1. EVALUATION:

We train the model for 3 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 2 shows the evaluation results of our model on a held out test set consisting of samples from our OneDiff dataset. Additional experiments on ZeroOneDiff and ZeroOneTwoDiff 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 a complete discrete graph edit operation step. For example consider Figure 1a , in which we edit an object property name with the REP_VAL operation. If the model incorrectly predicts the edit operation to 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 is 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_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 on the OneDiff dataset as most of the baselines target repair of a single bug. Note that for all comparisons we provide equal amounts of information to HOPPITY and the baseline without retraining our model. 2018), uses Gated Graph Neural Networks (GGNN) for two specific bug repair tasks: VARMISUSE, in which the model learns to 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 to compare with HOPPITY on the REP_TYPE and REP_VAL tasks. Specifically, for REP_TYPE prediction we have

• GGNN-Rep: we adopt VARMISUSE to replace with candidate node type and modify the graph structure correspondingly; we use their proposed max-margin formulation for training. • GGNN-Cls: we perform multi-class classification using the target node and graph embedding.

For REP_VAL prediction, we also made two versions of adaptations:

• GGNN-Rep: similar to 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 in this limited case GGNN-Cls 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 on graph is more effective. We found when the space of decisions is large, it 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 it 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.

SequenceR: The model proposed by Chen et al. (2018) is a translation based model that predicts a fixed sequence of tokens when given a buggy line in the source code. We compare with our model by providing location information to both approaches.

Table 5 summarizes the total accuracy for fixing a single bug. In order to provide a fair comparison, we allow SequenceR to predict the same information as our model (i.e., predict op, value etc.in a sequential way), rather than an 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.

TAJS::

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-line 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 30 random points in our test set to manually analyze using TAJS. Table 6 depicts the results (Appendix D provides further details).

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 are 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 a 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 as possible. After all these measures, TAJS managed to detect two of the undefined property bugs (Bug IDs 4 and 6 in 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 configuration. Second, HOPPITY achieves far better performance in detecting as well as fixing the bugs in Javascript programs.

7. RELATED WORK:

Static analysis for bug detection. Static analyzers such as FindBugs, Error-Prone, and Semmle use syntactic pattern-matching and dataflow analysis to find common bugs. Typically, detecting even a 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. (Pradel & Sen, 2018) proposes a name-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 sequence-to-sequence model to translate a buggy code segment into correct one; 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.

Graph learning and optimization. Our work is closely related to the literature in graph representation learning and optimization. Our model uses a variant of GNN that is inspired by many representative works (Li et al., 2015; Xu et al., 2018; 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.

8. CONCLUSION:

We proposed an end-to-end learning-based approach to detect and fix bugs in Javascript programs. We realized the approach in a 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 language-independence, we believe HOPPITY will benefit developers beyond Javascript as well.

A ADDITIONAL EXPERIMENTS 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

• ZeroOneTwoDiff -Includes samples with labels of zero, one, or two edits.

We trained models on each dataset for roughly 12 hours on a single GTX 2080Ti GPU. Accuracy on the ZeroOneDiff is the highest as predicting that an AST is not buggy does not consist of any low level primitive predictions. This makes it 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. 9 we compare the performance with different beam sizes on the OneDiff dataset. As we can see, the top-3 accuracy with beam size 3 is significantly better than top-1 accuracy with just greedy prediction. This is expected, as in the decision process there are 'bottleneck' stages with only a few predictions (e.g., the op prediction). Thus from beam-1 to beam-3 there's huge improvement, but further beyond the performance maxed out. 

B DATA COLLECTION:

We have built a robust system to automatically collect millions of bug-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:

1. 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, we filter this using the Github API to only include commits that consist of edits to Javascript files.

2. Download Files: As we are obtaining a list of valid commits from step 1, we begin downloading the pair: (src buggy , src f ixed ) where src buggy is the file prior to the commit, and src f ixed is the file following the commit that contains the changes made.

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 AST1 . 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 to 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 of ASTs: (AST buggy , AST f ixed ), at which point a JSON differencing algorithm, fast-json-patch2 is applied to create a label. The label includes the operation type and node edited for each difference between AST buggy and AST f ixed .

Each step of this process is 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 a JSON AST.

For each label, we must download two files src buggy and src f ixed . Additionally, if source files cannot be parsed into a SHIFT AST, a label cannot be created. For our learning corpus, we limit the dataset to only include labels with one AST difference. Additionally, in an attempt to limit graph size, we only include data points in which the AST buggy and AST f ixed have less than 500 nodes. Figure 5 plots the distribution of number of edits that are recorded in Table 10 . We can see the distribution is long tail, with majority of edits as 1 or 2.

C ABLATION STUDY:

We tried different graph representations with corresponding graph embedding methods. The multi 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 et al. (2018) ; the single instead uses a single graph with edge types as one-hot edge features. We found that more layers does not lead to better generalization in our setting, and it becomes slower in terms of convergence. So we report the results with 4 layers in our main paper. 

:

https://shift-ast.org/

https://www.npmjs.com/package/fast-json-patch

Figures and Tables:

Figure 1: Example programs that illustrate limitations of existing approaches inculding both rulebased static analyzers and neural-based bug predictors.

instead of ['', ''], which is what the developer intended. Since

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.

Figure 3: Graph edit operators with low-level primitives.

Figure 4: End-to-end code repair accuracy v.s. size of AST of source code.

Figure 5: Distribution of number of edits in the entire crawled dataset.



Table content: <table/>



Table content: <table/>

Pick the graph edit operator e t that is compatible with v t ; Use both v t and e t to obtain the micro-context embedding. 4. Perform the edit, obtain the corresponding micro-context summary -→ c et and update the macro-context embedding. 5. If the edit is not NO_OP, then go back to step 1; otherwise return the graph.

Table content: <table><tr><td>1. Obtain the graph representation --→ g t-1</td><td/></tr><tr><td>and node embeddings. Update the macro-context embedding using --→ g t-1 ;</td><td/></tr><tr><td>2. Choose edit location v t by performing</td><td/></tr><tr><td>location primitive and update the con-</td><td/></tr><tr><td>text embedding;</td><td/></tr><tr><td>3.</td><td/></tr><tr><td>10:</td><td>Get new graph g t , update --→ c Mt with -→ c et .</td></tr><tr><td colspan="2">11: end for</td></tr><tr><td colspan="2">12: Return g T</td></tr></table>

Statistic of OneDiff dataset. See appendix for more information of other dataset.

Table content: <table><tr><td/><td/><td colspan="4">ADD REP_TYPE REP_VAL</td><td>DEL</td><td>total</td><td/><td/></tr><tr><td/><td>train</td><td>6,473</td><td colspan="2">1,864</td><td>251,097</td><td colspan="2">31,281 290,715</td><td/><td/></tr><tr><td/><td>validate</td><td>790</td><td>245</td><td/><td>31,357</td><td>3,957</td><td>36,349</td><td/><td/></tr><tr><td/><td>test</td><td>796</td><td>233</td><td/><td>31,387</td><td>3,945</td><td>36,361</td><td/><td/></tr><tr><td/><td colspan="2">Total</td><td colspan="2">Location</td><td>Operator</td><td colspan="2">Value</td><td colspan="2">Type</td></tr><tr><td/><td colspan="4">Top-3 Top-1 Top-3 Top-1</td><td>Top-1</td><td colspan="4">Top-3 Top-1 Top-3 Top-1</td></tr><tr><td>TOTAL</td><td>26.1</td><td>14.2</td><td>35.5</td><td>20.4</td><td>34.4</td><td>52.3</td><td>29.1</td><td>76.1</td><td>66.7</td></tr><tr><td>ADD</td><td>52.9</td><td>39.2</td><td>69.6</td><td>51.4</td><td>70.6</td><td>65.7</td><td>55.1</td><td>76.8</td><td>68.5</td></tr><tr><td>REP_VAL</td><td>23.4</td><td>11.9</td><td>33.3</td><td>18.5</td><td>31.7</td><td>53.0</td><td>28.8</td><td>-</td><td>-</td></tr><tr><td>REP_TYPE</td><td>71.7</td><td>52.4</td><td>73.0</td><td>52.8</td><td>79.4</td><td>-</td><td>-</td><td>74.7</td><td>61.0</td></tr><tr><td>DEL</td><td>39.6</td><td>24.8</td><td>44.0</td><td>27.5</td><td>45.8</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Random</td><td>.08</td><td>.07</td><td>2.28</td><td>1.4</td><td>27.7</td><td>.01</td><td>.01</td><td>.27</td><td>0</td></tr></table>

Evaluation of model on the OneDiff dataset: accuracy (%).

Table content: <table/>

REP_TYPE accuracies with location+op.

Table content: <table><tr><td colspan="4">Type GGNN-Rep GGNN-Cls HOPPITY</td></tr><tr><td>Top-1</td><td>53.2%</td><td>99.6%</td><td>90.0%</td></tr><tr><td>Top-3</td><td>85.8%</td><td>99.6%</td><td>94.8%</td></tr><tr><td colspan="4">Value GGNN-Rep GGNN-RNN HOPPITY</td></tr><tr><td>Top-1</td><td>63.8%</td><td>60.3%</td><td>69.1%</td></tr><tr><td>Top-3</td><td>67.6%</td><td>63.6%</td><td>73.4%</td></tr></table>

REP_VAL accuracies with location+op.

Table content: <table><tr><td/><td>Top-1</td><td>Top-3</td></tr><tr><td>HOPPITY</td><td colspan="2">67.7% 73.3%</td></tr><tr><td colspan="3">SequenceR 64.2% 68.6%</td></tr></table>

Overall OneDiff accuracy with location.

Table content: <table><tr><td>Bug Type</td><td colspan="3">Amount TAJS HOPPITY</td></tr><tr><td>Undefined Property</td><td>7</td><td>0</td><td>1</td></tr><tr><td>Functional Bug</td><td>11</td><td>0</td><td>3</td></tr><tr><td>Refactoring</td><td>12</td><td>0</td><td>1</td></tr><tr><td>Total</td><td>30</td><td>0</td><td>5</td></tr></table>

Comparison with TAJS.

Table content: <table/>

Allamanis et al. (2018) target variable-misuse errors and present a solution based on a gated graph neural network model to predict the correct variable name given a buggy location.Vasic et al. (2019) present a pointer network on top of a RNN which outperformsAllamanis et al. (2018) on the same task. DeepBugs

Table content: <table/>

Evaluation of models on each dataset. The Random model is evaluated on the OneDiff dataset and is shown for comparison.

Table content: <table><tr><td/><td colspan="2">Total</td><td colspan="2">Location</td><td>Operator</td><td colspan="2">Value</td><td colspan="2">Type</td></tr><tr><td/><td colspan="4">Top-3 Top-1 Top-3 Top-1</td><td>Top-1</td><td colspan="4">Top-3 Top-1 Top-3 Top-1</td></tr><tr><td>ZeroOneTwoDiff</td><td>40.8</td><td>29.7</td><td>18.9</td><td>3.9</td><td>30.3</td><td>35.0</td><td>6.5</td><td>38.6</td><td>3.4</td></tr><tr><td>ZeroOneDiff</td><td>51.6</td><td>34.5</td><td>27.1</td><td>5.5</td><td>35.6</td><td>45.4</td><td>10.4</td><td>73.9</td><td>58.9</td></tr><tr><td>OneDiff</td><td>26.1</td><td>14.2</td><td>35.5</td><td>20.4</td><td>34.4</td><td>52.3</td><td>29.1</td><td>76.1</td><td>66.7</td></tr><tr><td>Random</td><td>.08</td><td>.07</td><td>2.28</td><td>1.4</td><td>27.7</td><td>.01</td><td>.01</td><td>.27</td><td>0</td></tr></table>

Results on true/false predictions.False positive/negative study An evaluation of false positives and false negatives is available in Table8. In this setting, we treat the problem as a classification problem on our ZeroOneDiff dataset and our model attempts to predict if a given AST is BUGGY / NOT BUGGY. If the model predicts ADD, REP_VAL, REP_TYPE, or DEL, we consider this a prediction of "BUGGY." Accordingly, if the model predicts NO_OP, we consider this to be a prediction of "NOT BUGGY." Accuracy v.s. size of graph To demonstrate the affect of AST size on HOPPITY's prediction accuracy on the OneDiff dataset, we include Figure4. As expected, AST size and accuracy are inversely related.

Table content: <table><tr><td/><td/><td colspan="2">TRUE LABEL</td></tr><tr><td/><td/><td colspan="2">BUGGY NOT BUGGY</td></tr><tr><td>PREDICTED</td><td>ALARM NO ALARM</td><td>10,293 26,517</td><td>7,210 20,605</td></tr><tr><td colspan="4">Beam Size (k) Top-k Accuracy (%)</td></tr><tr><td/><td>1</td><td>14.37%</td><td/></tr><tr><td/><td>2</td><td>21.10%</td><td/></tr><tr><td/><td>3</td><td>26.14%</td><td/></tr><tr><td/><td>4</td><td>30.12%</td><td/></tr><tr><td/><td>5</td><td>33.58%</td><td/></tr></table>

Accuracy vs beam sizes.

Table content: <table/>

Data collection statistics.

Table content: <table><tr><td>Published as a conference paper at ICLR 2020</td><td/></tr><tr><td>Total Files Downloaded:</td><td>52,719,402</td></tr><tr><td>Total Labelled Data Points:</td><td>15,225,347</td></tr><tr><td># AST differences:</td><td># data points:</td></tr><tr><td>0</td><td>3,473,391</td></tr><tr><td>1</td><td>1,863,193</td></tr><tr><td>2-10</td><td>3,247,437</td></tr><tr><td>11-20</td><td>2,117,977</td></tr><tr><td>21-50</td><td>2,047,998</td></tr><tr><td>51-100</td><td>858,981</td></tr><tr><td>101+</td><td>921,754</td></tr></table>

Ablation study with different graph embedding parameterizations and different number of layers. Full end-to-end repair accuracy as well as the accuracies for each primitives are reported. All the numbers are for top-1 prediction.D 30 RANDOM TESTING POINTS FOR TAJS BASELINE STUDY

Table content: <table><tr><td>model</td><td colspan="6">max_lv Total Operator Location Value Type</td></tr><tr><td>multi</td><td>20</td><td>7.63</td><td>30.0</td><td>13.1</td><td>22.6</td><td>54.5</td></tr><tr><td>multi</td><td>14</td><td>11.05</td><td>48.0</td><td>17.9</td><td>38.6</td><td>61.6</td></tr><tr><td>multi</td><td>4</td><td>13.33</td><td>53.4</td><td>36.2</td><td>38.6</td><td>56.4</td></tr><tr><td>code2inv</td><td>20</td><td>10.3</td><td>18.1</td><td>25.7</td><td>38.8</td><td>57.7</td></tr><tr><td>code2inv</td><td>14</td><td>8.92</td><td>40.0</td><td>18.1</td><td>36.0</td><td>55.9</td></tr><tr><td>code2inv</td><td>4</td><td>13.29</td><td>30.8</td><td>18.9</td><td colspan="2">28.2 68.21</td></tr><tr><td>single</td><td>20</td><td>5.00</td><td>20.2</td><td>10.3</td><td>14.2</td><td>44.8</td></tr><tr><td>single</td><td>14</td><td>10.69</td><td>67.7</td><td>18.6</td><td>49.6</td><td>38.7</td></tr><tr><td>single</td><td>4</td><td>12.88</td><td>55.8</td><td>20.8</td><td>43.2</td><td>55.8</td></tr></table>

Peer review (iclr2020):
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. Overall, 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. * 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.* -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. - 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) * 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. Thus, 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. * 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. * 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. * 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. * 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. * 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). Other questions: * 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)? * 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. * 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? * 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. Minor: * Abstract: *Github* -> *GitHub* * 3.2 REP_VAL: *Tthe*-> *The* * 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. * The citation of Chen et al. (2018) should be capitalized correctly *Sequencer*->*SequenceR* ## References Allamanis, Miltiadis. *The Adverse Effects of Code Duplication in Machine Learning Models of Code.* arXiv preprint arXiv:1812.06469 (2018). Cvitkovic, Milan, Badal Singh, and Anima Anandkumar. *Open Vocabulary Learning on Source Code with a Graph-Structured Cache.* arXiv preprint arXiv:1810.08305 (2018). Lopes, 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.