Learning to Infer Run-Time Invariants from Source code
Authors: Vincent Josua Hellendoorn
Premkumar Devanbu
Alex Polozov
Mark Marron
Venue:  (2021)
Keywords: Invariants
Software Engineering
Programming Languages

Abstract: Source code is notably different from natural language in that it is meant to be executed. Experienced developers infer complex "invariants" about run-time state while reading code, which helps them to constrain and predict program behavior. Knowing these invariants can be helpful; yet developers rarely encode these explicitly, so machine-learning methods don't have much aligned data to learn from. We propose an approach that adapts cues within existing if-statements  regarding explicit run-time expectations to generate aligned datasets of code and implicit invariants. We also propose a contrastive loss to inhibit generation of illogical invariants. Our model learns to infer a wide vocabulary of invariants for arbitrary code, which can be used to detect and repair real bugs. This is entirely complementary to established approaches, which either use logical engines that scale poorly, or run-time traces that are expensive to obtain; when present, that data can complement our tool, as we demonstrate in conjunction with Daikon, an existing tool. Our results show that neural models can derive useful representations of run-time behavior directly from source code.

Under review as a conference paper at ICLR 2021
LEARNING TO INFER RUN-TIME INVARIANTS FROM SOURCE CODE
Anonymous authors Paper under double-blind review
ABSTRACT
Source code is notably different from natural language in that it is meant to be executed. Experienced developers infer complex "invariants" about run-time state while reading code, which helps them to constrain and predict program behavior. Knowing these invariants can be helpful; yet developers rarely encode these ex- plicitly, so machine-learning methods don't 't have much aligned data to learn from. We propose an approach that adapts cues within existing if-statements regarding explicit run-time expectations to generate aligned datasets of code and implicit invariants. We also propose a contrastive loss to inhibit generation of illogical invariants. Our model learns to infer wide vocabulary of invariants for arbitrary code, which can be used to detect and repair real bugs. This is entirely com- plementary established approaches, which either logical engines that scale poorly, or run-time traces that are expensive to obtain; when present, that data can complement our tool, as we demonstrate in conjunction with Daikon, an existing tool. Our results show that neural models can derive useful representations of run-time behavior directly from source code.
INTRODUCTION
Software maintenance requires reading a lot of code. Experienced developers adept this, garnering rich semantics just from this "static" (viz, without running the code) inspection to find complex bugs, predict function's outputs from its inputs, and learn new coding patterns. They strongly rely on generic assumptions about the program's 's run-time behavior; e.g., that a list index never escapes the list bounds and strictly increases. Such "invariants" capture general, yet relevant constraints on the program's 's expected run run-time behavior.
Automatically inferring invariants can help both developers and tools: first, they can be used to detect bugs where explicit assumptions are incorrect or implicit ones ought to be explicit; second, invariants can guide myriad other tools, such as test-case generators (Artzi al.) (2066). However, inferring invariants is not tractable in general and sound approximations don't it scale beyond very small programs. Instead, popular tools either use dynamic trace data from real executions (esp. Daikon (Ernst et al. 2007)), which requires costly instrumentation, or focuses on highly constrained cases such as loops (Sharma et al. 2013a Padhi et al. 2016).
public void onTargetFound(.))
public void onTargetFound(.)
int time = calculateTime(); (time 8)
int time calculateTime(); uetien.updatee-dk, -dy, time, interpolator);
t'me 0
vetiin.update(-dk, -dy, time, interpolator);
Figure 1: snippet that demonstrates how explicitly guarded code is often equivalent code with salient implicit, invariant-like conditions. The code on the right was real (bug) that was patched by adding the conditional check on the left. We synthesize such samples to train our model by selectively removing if-statements. Our model correctly predicted this repair.

---

Under review as a conference paper at ICLR 2021
Yet this scalability obstacle may be largely artificial. Practical programs rarely take exponen- tial range of values (c.g., integers tend to come in a bounded range), and developers seem able to make such inferences without undertaking project-scale analysis. Rather, they reliably extract them from a local context, using their past experience and cues from the code itself. Consider the snippet in Figure [ the program the right uses time variable, returned from one method and passed to another. Not only is 'time' generally non-negative, in this particular case we should not update a position (using moments dx, dyy if no time has passed either. This inference, and many more, can quickly be made from reading just these lines of code. Other times, such implicit inferences should be made explicit: this snippet was later repaired by adding the guard on the left.
Based on this observed symmetry between explicitly guarded code and implicit run-time assump- tions about code, we propose model that learns invariants directly from static code. As developers rarely "assert" invariants in their code, we train this model using a proxy, by automatically convert- ing explicitly guarded code to its implicitly guarded counterpart across millions of functions. The generated programs are constrained to be similar to real functions and used to train large model with a new loss function that is aware of logical constraints.
Our model, BODYGUARD predicts rich vocabulary of conditions about arbitrary code from new projects, and can be used to find & fix real bessing-guard bugs, such as the one in Figure [I] with over 69% (repair) precision at 10% inspection cost. It also predicts more than two-thirds of Daikon's invariants that could previously only be inferred with run-time data, and some entirely new ones that can be validated automatically with trace data. Our work presents significant next step in learned static analysis, being the first to reliably produce natural invariants from arbitrary code alone. More broadly, we show that learned models can implicitly represent behavioral semanties, just from code.
2 OVERVIEW
Inferring invariants for arbitrary programs is NP-hard. Sound approaches using theorem proofers are therefore constrained to restricted settings, such as simple loops (Sharma et al.) 2013a), or ones with known inputs (Pham et al. 2017). Such approaches generally don't scale: needing SMT solvers limits tools to the few program points where invariants can be proven, and ground-truth inputs typically need be constructed by hand. An alternative is to use execution traces (Ernst et al.) 2007|: when realistic workloads are available (e.g. from test suites). they generally span entire systems. However, genuinely representative workloads are rare, so trace-based tools often generate poor invariants (Kim & Petersen). A key concern is that none of these have a notion of relevance, or naturalness of the actual statements (Hellendoorn et al. 2019a).
To address these gaps, we propose a learned invariant generator that predicts directly from code, trained with realistic examples. Our central claim is that the natural distribution of programs includes many groups of similar functions, some of which assert run-time assumptions explicitly, and with much detail, while others vary along these dimensions. As Figure T highlights, it is common for code not to state salient conditions (time while other times (c.g. in a later revision, on the left), such conditions are explicitly checked. If this distributional assumption holds in general, then we can use explicis conditional checks that guard blocks in functions to teach our models about the implicit invariants of unguarded blocks in similar functions. Furthermore, we conjecture that in such comparable samples, the condition is both salient (since it is checked explicitly) and natural (since it is written by humans). Learning from such examples is thus a very appropriate training signal for inferring practically useful invariants.
the right) that developers may naturally intuit,
Figure 2 iillustrates our data generation: we find explicitly guarded blocks in functions that can be removed without substantially perverting the program, and convert these checked cases to implicit ones (Section B.T) We garner large aligned dataset to learn to predict the reverse of this mapping, training a Transformer-sty cal conditions (Section (.2). This model, nick-named GODYGUARD, works on any (Java) function, quickly adapting to the local vocabulary and semantics, and has a natural inclination to generate realistic, salient invariants that are often valid (Section 4). This result fits in a long line of observa- tions that programming is remarkably predictable, including in its syntax (Hinlle et al.] 2012) and execution values (Tsipporlaas et al. 2020), likely by developers' design, to control the complexity of the task (Casalnuovo et 2019). Yet none of these relate code and its execution directly, as we do through translating the former into general, intuitively meaningful statements about the latter.
model for code, augmented with a loss that encourages sampling logi-
2

---

Under review as a conference paper at ICLR 2021
Training
Usage
Condition
Targets
New method
ane.length
1x
Jength
int hightst(int(] 4) [
Inputs
Condition inverter
1x
>- 55
1x
ann Jength
if [a[e] > 2[all])
getIndex(arr, el);
return alol:
return insert (arn, 18, el);
Predicted FF- lant
length-111
BodyGuard
int fx getIndex(arr, el)s return arrlixl;
Predicted else-invariant
Mark whole body as region of interest pre-conditions.
Marked target regions
Produce somples
Compute losses
BodyGuard
Methods
Predicted if-invariant
Int ix gotIndex (ann, et); if arn-length) return (arr, 18, el)s
|| Dx be ane. Jength
les
BR 1xr ann, Jength
X
Cross- entropy
Lainge
a a. Longth > 1
Predicted else invardant
a[0] > a[1] II
else {
arr[ix];
1x 0 1x >- ann. Jengthh
Eniagr
a[a.tength-1] a[1]
1x >> 55 1x
ann. ann.length
Figure 2: An overview of our learning approach. We extract samples from if statements in Java methods by removing the guard and assigning (or its negation, for the else block) as the target invariant of the vyviousll-guurrde block (if and else blocks separately, if both present) for trans- lator. We train using the cross-entropy of the predictions given the target, as well as the contrast of this entropy to that of predicting the logical inversion (per sample) in hinge loss, which encourages BODYGUARD to distinguish between syntactically similar, but logically distinct invariants.
APPROACH
Training and evaluating this approach required a substantial experimental setup: we collect three datasets for three types of evaluations and introduce an improved loss function. This section de- scribes the data collection, evaluation, and modeling setup generally; Appendices an. vide additional details on our datasets and modeling architecture, respectively. Our benchmark link]
datasets, code, and models are available at
3.1 DATASETS
To train BODYGUARD, we generate ca. 2.5 million aligned invariant/funccion samples from methods with if-statements. We extract these from top-starred Java projects from Github, which we split at the organization level into training (920 projects), held-out (19 projects), and test data (61 projects). Each file was parsed to extract all its methods, from which we generate one sample for each (side- effect frree) if- (or Jettteetttttement by removing said guard and storing its condition. This produces an equivalent code fragment in which the statement's 's condition is presumed to either be always true (if its body is kept) or false (otherwise). Correspondingly. the omitted condition (or its negation) becomes invariant the remaining code. The resultant sample contains the entire method (minus conditional check) as context, with the range of tokens where the invariant condition applies indicated.
We train our model to generate run-time conditions for any indicated segment of code in Java func- tions. We evaluate its ability to do so in two settings: 1. identifying and repairing missing explicit if if-guards, collected from real bug reports, and 2. measuring the validity of our predicted invariants using trace data, collected with Daikon (Ernst et al.) 2007). For the first, we collect a dataset of real missing if-condition bugs from across the history of TOK Java projects by parsing all the revisions in these projects' histories and selecting for changes that a) introduce single if-statement to guard previously un- un-guarded code, and b) are described details). We find ca. three thousand of these. For the second evaluation, we use Daikon to collect execution trace data from smaller set of eight projects that manually instrumented. We then compare our predictions to both those generated by Daikon, to measure overlap, and to the collected traces directly, to assess the validity of the invariants that uniquely generate. This helps us under- stand the inference gap between static and dynamic information; i.c., is run-tin an-time data (when present) strictly more useful than code, are the two information sources orthogonal?
bug-fixing change (see Appendix A.133 for
3

---

Under review as a conference paper at ICLR 2021
Transformer loyer
Diensformr wordjonward NN
Feedforword NN
Input
Rolotional Attenttnnn
Masked Solf Attendion
Transformer
Transformer loyer
Feedforward
Feedforword
Biosed Input Attention
Relational Self-Attenticn
Mosked Self Attention
time calculateTine(); mrrrionnupdate(-ce -dy, time, interpolator);
time > 0
Relations: parent, frrputed-fron, def-use, next-use, next-token
Figure 3: Schematic overview of our model. Both encoder and decoder use 8 Transformer layers. In- put is provided BPE tokens (not shown) augmented with program-graph edge information, which the encoder uses through relational self-attention from (Hellendoorn et al. (2020). The decoder uses both masked self-attention and input attention biased towards the target scope (bold and underlined).
3.2 MODEL SETUP
Discovering invariants is non-trivial even for experienced developers, so we both equip our models with substantial capacity and training time, and design prioritize precision over recall. Figure shows an overview of the architecture, inputs and outputs of our model.
3.2. ARCHITECTURE
We base our architecture on the Transformer Vaswani et al. 2017), amplified with the relation attention mechanism from Hellendoorn are quite useful for code, Allamanis et al. (2018) and others have shown that utilizing syntatic & semantic information such the AST, or control/data- relations, outperforms text-only models. Hellendoorn et al. (2020) propose a Transformer-bee based architecture that handles such relations but is faster train and more powerful than graph neural networks (Allamanis al., 2018). Their model relies on an added attention bias by., injected into the query-key comparison of the Transformer's
2020). While standard (lexical) language models
conventional scaled dot-product attention: eij = (qi bi, )kj / T/VN. This bias is sensitive to known relations between tokens and j (if any, and summed together if than one), allowing the model to selectively sharpen (or dampen) the significance of each relation. We adopt this model for our work, specifically with 12-dimensional hidden states, 64-dimensional relational embeddings, attention heads, and 8 layers, totaling ca. 67M parameters.
bry))
Our model uses relational information in the form of program graphs. program graph extractor has been released for C# code (Allamanis et al. 2018), but not yet for Java, so we created our own. Specifically, we extract 5 commonly used edge types, all bi-directional, reflecting common lexi- cal, syntactic, and semantic relations in programs (detailed in Appendix [I. We use the same "leaves-only" representation as Hellendoorn et al. (2020) to limit size of our inputs by not includ- ing non-terminal AST nodes, but instead rerouting edges that connect such nodes representative syntax token (c.g. from an if-statement node to its "if" token in the code). Finally, to ensure that our decoder is aware of the specified range of code tokens where the invariant applies, also leverage the relational mechanism between the decoder and encoder, using a simple unary relation (i.e., that token is part of the invariant's range) between the generated tokens and input tokens.
3.2.2 DECODING LOGICAL STATEMENTS
We synthesize training data using proxy for invariants, which necessarily introduces some bias towards characteristics of if-conditions (and the code they guard) that is incompatible with true invariants. Most notably, in code, small syntactic differences lead to drastic changes in run-time
4

---

Under review as a conference paper at ICLR 2021
30%
100.0%
90.0%
Accuracy (96)
Precision (54)
Model
Model
Base
Hinge-lau linge-lass
Hingo lcss
10%%
70.0%
60.0%
20% (96)
Step
(a) Accuracy on held-out data during training.
(b) Drecision-Reent response the trained models to limits on the entropy of generated invariants.
Model performance during and after training, focusing on the figh-precision/loww recall domain for the second (overall test accuracies: 33.8% base, 34.7% hinge-loss).
Figure 4:
behavior. It is common for if else statements to have quite similar bodies, for which we generate two samples: one with the if-condition an invariant for the if block, and one with its logical negation for the else block. This approach tends to produce very similar code fragments with very similar, but logically opposite (e.g. !!- null' vs. null') conditions.
We supervise our model to encourage its representations for syntactically close but semantically opposite statements to be distinct by introducing contrastive hinge loss term. For every training sample, produce the logical negation of the invariant and require the decoder to produce that negation with a much higher entropy than the original. Concretely, given a statement inu comprised of tokens t; and negating function neg,
the regular cross-entropy loss Loe:
linel
Cce(inu) =
Σ
log prob(t: (.....tt11 contert)
1=1
to compute the entropy distance w.r.t. its negation:
A ine (ce(neg(inu)) (ic(ine)
Chenge (inv) = max (0, Aie - {)²
in which is the minimum desired entropy "distance" in bits. In this work, we set e = 2. For this hinge-loss model, as will call it in the rest of this paper, train with loss equal to Leeg + Chinge-
ANALYSIS
We first assess our model's precision/recall behavior on our automatically collected corpus; then, apply it to promising down-stream task: missing if -frrd repair (and detection), which further helps us assess the models' sensitivity to salient invariants. Finally, we use trace data to get a measure of our invariants' validity and contrast it with execution-based tool.
4.1 CORPUS DATA
We sample our two models' held-out performance every 100,000 samples while training leading to the learning curves shown in Figure 4a The base model saturates earlier than the one employing a contrastive hinge loss, as the latter faces the more challenging task of distinguishing between very similar statements, However, after ca. one week of training, both models converge to approximately the same quality. speaks to the challenge of the task that the models only reach ~30% aceuracy, due in part to the enormously diverse vocabulary of statements that occurs across our corpus, and to the inherent ambiguity of generating a single invariant when multiple valid options are available (as
A full epoch is approximately 2.3M samples for the base model and twice that for the hinge-loss models
5

---

Under review as a conference paper at ICLR 2021
Bug detection and repair results on finding and predicting missing if guards, across two settings: given the correct location, and across all possible locations, further analyzed by aspects of the top prediction.
Table 1:
Top-5 Acc.
Precision @ 10% Recall
Objective
Accuracy
Location given
29.3%
41.9%
69.1% %
All Locations
10.4%
18.8%
39.9%
invariant correct
15.2%
24.2%
48,1 %
position correct
19.4%
43.8%
100.0%
we will study later). This task clearly stretches our current models of code to their limits, making it a promising new task to pursue order improve our models.
We evaluate each model at the step with their highest held-out accuracy on the test data, where we compare the top generated invariant (from beam search, size 25) to the ground truth. Figure (4b shows the precision/recall behavior of the two models in the high precision range, which is generally much more useful to developers than high recall. We rank predictions by their entropy: an invariant that is highly likely to be sampled from its context is likely correct. Both models respond strongly to this entropy threshold, becoming especially far more precise when entropy values drop below 1.0 (around 40% recall), and converging to (near) perfect precision, at commensurate expense of recall. Both break 80% precision at nearly 20% recall, which still accounts for tens of thousands of program points across test projects alone. Going forward, we use the hinge loss model, which has the better precision-recal trade-off, and prioritize precision over recall.
4.2 MISSING IF DETECTION
Using the ~3K real missing if-guard bugs collected from project histories (see Section 3.1 we first measure model's is accuracy and precision predicting this guard from the localized bug in the top row of Table [ This most directly related to its training signal, where we provided our model with the location of the code guarded by the targeted invariant. Our model achieves similar overall accuracy here (ca. 29.3%) as on our general test data and precision at 10% recall is also quite high (69. 1 1)), allowing us to fix 215 out of 311 bugs at that level once located. That these tasks appear to be comparably "hard" is relevant; automatically synthesized training data is often overly easy compared to real tasks, which harms generalization (Hellendoorn et al. 2019b).
We also care about our model's sensitivity to salience: the missing condition in these samples is (arguably) the most important invariant in the entire method, not just the indicated code block. Our model should be able to detect this given how it was trained. This contrasts with tools like Daikon Ernst et al. (2007), which emit all logically valid invariants, many of which irrelevant (Hellendoorn et al. (019a). The next three rows of Table [T show the results of running every contiguous segment (up to blocks) of code in each buggy method, ranking the top invariants across segments for inspection. This is substantially harder than the previous task, redueing the overall accuracy threefold and roughly halving precision. Nevertheless, that is still much better than might be expected if BODYGUAR had no location- -ensiiiiit:ttiiiity we test over 30 blocks per method on average. We also show that the top prediction often matches some aspect of the correct answer, especially the position, and often predicting the correct invariant at another (nearby) block of code.
invariant generator
Finally, we note that the other (low entropy) invariants predicted here are often not at all "incorrect"; from cursory inspection, many are valid, meaningful statements. We study their validity next.
4.3 VALIDITY AND OVERLAP WITH DAIKON
Learning invariants just from code stands in sharp contrast most current approaches in this field, prominently including Daikon (Ernst et al. (207)). which learns invariants from execution trace data instead. Collecting trace data requires instrumenting projects and access to diverse, representative workloads. This makes it much harder to apply to arbitrary code than our approach but has the benefit of offering stronger guarantees of correctness. Comparing our model with Daikon in projects where this information is available thus allows for two useful evaluations. First, can lower-bound
Thhe base model (trained without hinge loss) reached 26.8% accuracy.

---

Under review as a conference paper at ICLR 2021
100.0%
100.0%
90.0%
90.0%
80.0%
80.0%
Precision (96)
70.0%
70.0%
Validity (96)
60.0%
Model
60.0%
Model
50.0%
Pre
50.096
Pre Post
40.0%
Post
40.0%
30.0%
30.0%
20.0%
20.0%
10.0%
10.0%
0.0%
0.0%
1.0%
10.0%
100.0%
1.0%
10.0%
100.0%
Recall (96)
Recall (96)
(a) Overlap between our invariants and Daikon's s, on pre- and post-conditions.
(b) Overall validity in relation to varying entropy thresholds; pre- and post-conditions.
Figure 5: Results of the overlap and validity analysis of our invariants based on trace data. Note the log-scaling on the x-axis.
our tool's true-positive rate by determining how often it replicates Daikon's own invariants, which tentatively deem "safe" because they hold on all observed traces and have passed significance test 3] Second, we can use this trace data directly to determine the validity of (a subset of, see Appendix A.3.2) our invariants that do not overlap with Daikon's.
Figure 5a shows the first result: the frequency with which our invariants overlap with Daikon's. ss again plotted against recall, where the points correspond to entropy threshold ranging from le-4 to 10. Evidently, pre-conditions are easier to predict for our model, likely because it has no real notion of post-conditions (see Appendix A.3.2). Even so, our tool can retrieve more than two-thirds of Daikon's 's invariants at a respectable 10% recall from static code alone, which is quite promising.
We generate 10 invariants per program point using beam search, so even at low entropy threshold we produce many pre- and post-condition that Daikon does not (those either out of its vocabulary, or with too few observations). results. Since Daikon does not provide a means of validating a plain-text invariant, simple logical engine that parses Daikon's 's trace data files and compares a number of categories of invariants against the recorded values, such array length, string equivalence, instanceof checks, etc. Using this approach, we are able to validate ca. 40% (12K) of our emitted invariants, resulting in the validities summarized in Figure 5b) In short, invariants at full recall are valid ca. 60% of the time, and this validity ratio greatly increases as we sharpen the entropy threshold, to over 80%, recall values under 10%.
is reasonable to expect many of these to valid given previous wrote
Many of these validated invariants were not produced by Daikon, implying that static and dynamic data are orthogonal for this task. We collected the 708 pre-conditions that BODY generates at an entropy of <0.1; of these, 540 could be checked automatically with trace data, yielding 449 valid and 91 invalid cases. We manually inspected the 168 remaining cases and found that most (122) were valid, but Daikon's 's tracer simply did not record the information needed to predict these E Overall, this suggests that more than 80% of our invariants at this recall level (3.5% are correct, and more than two-thirds of the invalid remainder could be ruled out using trace data, if available, leaving a false positive rate of just 6.5% (46/708) when execution data available (while also adding about 200 valid invariants to Daikon's 's own predictions). This supports our belief that our tool is largely orthogonal to, and usefully synergistic with, dynamic, trace- based invariant generators.
Though practice it generates a fair number of spurious statements still. 'Some of these were correct statements but not proper pre-conditions, e.g. invariants about variable declared at the first line of the function. This is an artifact of our training setup, which has explicit notion of method-level pre-conditions. We marked these invalíd for this analysis.

---

Under review as a conference paper at ICLR 2021
5
RELATED WORK
Automatically inferring invariants usually approached either in constrained settings where some "checker" (e.g. an SMT solver) or ground-truth is available, or under the assumption that we have access to execution traces from realistic workloads. Among the first, [Sharma al.] (2013b) find algebraic (polynomial) invariants by solving a system of linear equations with an SMT solver and using counterexamples to create new test inputs. [Sharma et al. (20T3a) use PAC-learning to learn integer loop invariants programs with single loop, trained by contrasting passing and failing test cases. Padhi et al. (2016) learn pre-conditions and loop invariants as boolean combinations of arithmetic conditions ( ("features"), ") which they synthesize by generating and testing all features up to a size cutoff. This approach is agnostic to the program structure, as is Pham et al. (017)) who use a fixed set of feature templates over state vectors to learn linear inequalities that classify passing and failing state vectors, requiring both post-conditions and passing and failing tests to be in place. In contrast, our work makes no assumptions about the code other than the availability of a parser. In settings where an SMT solver (or test cases) is available, it could be used to filter invalid invariants generated by BODYGUARD.
Among machine learning based approaches, Si et al. 2018)) use policy-learning to teach a GNN to generate loop invariants cooperation with an SMT solver (Z3), which provides intermediate rewards (through counterexamples) to finesse the sparsity of the eventual reward (the final validity of the invariant). A second reward added to reject "meaningless" and "trivial" predicates such e == e or e < Besides not requiring an SMT solver, our approach learns notions like "relevant" and "natural" directly from real code. Relatedly, Brockschmidtt et al. (2017) also use GNNs to induce invariants over data structures, using similar approach of generating invariants (in separation logic) supervised by data produced from test runs. The production is based on hand-engineered features over the data-structure graphs. Both these approaches may be symbiotic with ours where tests or logical constraints are known, although they consider different classes of invariants.
Daikon (Ernst et al. 2007) belongs to the second class of invariant predictors, leveraging execution traces from realistic inputs to infer a large vocabulary of method pre- and post-conditions. This gen- eral applicability has led to its frequent as basis for other tools, often to generate an initial corpus of invariants for tasks such as automated patching (Perkins et al. 2009) and test generation (Artzi ct al.] 2006 Pacheco & Ernst 2005). However, truly representative inputs are rare, and using in- complete data risks generating many irrelevant or invalid invariants. PPolikarpova et al. (2009) found that the size of the test suite affects the validity of generated invariants on Eiffel programs. Kim & Petersen anecdotally note various issues with Daikon's 's invariants on large, C++ systems, such as a high degree of false positives and few insightful invariants. [ellendoorm et al. (2019a) similarly ob- serve (on hand-annotated C# functions) few relevant and valid invariants based on executions from unit test. Our approach learns directly from natural conditions to generate relevant and generalizable conditions, and when trace data is present, it can be used to filter out invalid invariants.
6 CONCLUSION
We conjectured that typically used invariants are in a sense natural, like many other aspects of pro- grams (Hindle et al., 2012; Barr et al., 20133: Tsimpourlas al., (020). and therefore predictable, intentionally written in standardized ways for ease of reading and writing Casalnuovo et al. (2019). Our results support this claim: both explicit (if-statements) and implicit (invariants) conditions per- taining to code can be predicted precisely, and with high validity from code reading alone, facilitated by our proposed data generation approach and loss function. As a result, we can generate many in- variants that were previously only accessible through trace data (and more), which greatly increases the reach and applicability of invariant inference.
This finding has broad implications: our tool can provide valuable semantic insights both to devel- opers, e.g. to aide debugging efforts or facilitate code understanding, and to other tools, many of which struggle to navigate an exponentially large search space of programs. Our tool can help bias this search space using highly likely assertions, which could greatly improve the range and quality of solutions found by downstream applications. In summary, our novel approach learns to reason about program state by synthesizing training data from if-conditions; this empowers BODYGUARD to reliably generate useful invariants entirely from static code.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Miltiadis Allamanis. The adverse effects of code duplication in machine learning models of code. In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, pp. 143-153, 2019.
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning represent programs with graphs. In International Conference on Learning Representations, 2018. URL https:
//openzeview.
Shay Artzi, Michael D) Ernst, Adam Kiezun, Carlos Pacheco, and Jeff Perkins. Finding the needles in the haystack: Generating legal test inputs for object-oriented programs. 2006.
Earl T Barr, Christian Bird, and Mark Marron. Collecting heap of shapes. In Proceedings of the 2013 International Symposium Software Testing and Analysis, pp. 123-133, 2013.
Earl Barr, David W Binkley, Mark Harman, and Mohamed Nassim Seghir. Sub-turing islands in the wild. arXiv preprint arXiv: 12734, 2019.
Stephen M Blackburn, Robin Garner, Chris Hoffmann, Asjad M Khang, Kathryn McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z Guyer, et al. The dacapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and ap- plications, pp. 169-190, 2006.
Marc Brockschmidt, Yuxin Chen, Pushmeet Kohli, Siddharth Krishna, and Daniel Tarlow. Learning shape analysis. International Static Analysis Symposium, pp. 66-87. Springer, 2017.
bug. Commit for (simplified) example bug repair. https//bbi.ll//TTujjb..
Casey Casalnuovo, Kevin Lee, Hulin Wang, Prem Devanbu, and Emily Morgan. Do people prefer "natural" code? arXiv preprint arXiv: 1910.03704, 2019.
Michael D Ernst, Jeff H Perkins, Philip J Guo, Stephen McCamant, Carlos Pacheco, Matthew Tschantz, and Chen Xiao. The daikon system for dynamic detection of likely invariants. Science of Computer Programming. 69(1-3):35 45, 2007.
Gordon Fraser and Andrea Arcuri. Evosuite: automatic test suite generation for object-oriented soft- ware. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering, pp. 416-419, 2011.
Vincent Hellendoorn and Premkumar Devanbu. Are deep neural networks the best choice for modeling source code? In Proceedings of the 2017 1 11th Joint Meeting on Foundations of Software Engineering, pp. 763-773. ACM, 2017.
Vincent J Hellendoom,, Premkumar T Devanbu, Oleksandr Polozov, and Mark Marron. Are my invariants valid? learning approach. arXiv preprint 1903::009000088 2019a.
Vincent J Hellendoom, Sebastian Proksch, Harald C Gall, and Alberto Bacchelli. When code com- pletion fails: A case study on real-world completions. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pp. 960-970. IEFE, 2019b.
Vincent J Hellendoom, Petros Maniatis, Rishabh Singh, Charles Sutton, and David Bieber. Global relational models of source code. In 2020 8th International Conference on Learning Representa- tions (ICLR), 2020.
Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the natural- of software. In 2012 34th International Conference Software Engineering (ICSE), pp- 837-847. IEEE, 2012.
Rachel-Michael Karampatsis, Hlib Babii, Romain Robbes, Charles Sutton, and Andrea Janes. Big code big vocabulary: Open-vocabulary models for source code. arXiv preprint arXiv:2003.07911 2020.

---

Under review as a conference paper at ICLR 2021
Miryung Kim and Andrew Petersen. An evaluation of daikon: dynamic invariant detector.
Carlos Pacheco and Michael D. Ernst. Eclat: Automatic generation and classification of test inputs.
In Andrew P. Black (ed.), ECOOP 2005 Object-Oriented Programming. pp- 504-527, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. ISBN 978-3-540-31725-8.
Saswat Padhi, Rahul Sharma, and Todd Millstein. Data-driven precondition inference with learned features. ACM SIGPLAN Notices, (1)))422-56, 2016.
Jeff H Perkins, Sunghun Kim, Sam Larsen, Saman Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, et al. Automati- cally patching enrors in deployed software. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles, pp. 87-102. ACM, 2009.
Long H Pham, Ly Ly Tran Thi, and Jun Sun. Assertion generation through active learning. In International Conference Formal Engineering Methods, pp. 174-191. Springer, 2017.
Nadia Polikarpova, Ilinca Ciupa, and Bertrand Meyer. A comparative study of programmer- and automatically inferred contracts. In Proceedings of the eighteenth international symposium on Software testing and analysis, pp. 93-104. ACM, 2009.
Baishakhi Ray. Vincent Hellendoorn, Saheel Godhane, Zhaopeng Tu, Alberto Bacchelli, and Premkumar Devanbu. On the "naturalness" of buggy code. In 2016 IEEE/ACM 38th Interna- tional Conference on Software Engineering (ICSE), pp. 428-434--4 IEEE, 2016.
Rahul Sharma, Saurabh Gupta, Bharath Hariharan, Alex Aiken, and Aditya V Nori. Verification as learning geometric concepts. In International Static Analysis Symposium, pp. 388-418 Springer, 2013a.
Rahul Sharma, Eric Schkufza, Berkeley Churchill, and Alex Aiken. Data-driven equivalence check- ing. In ACM SIGPLAN Notices, volume 48, pp. 391-406. ACM, 2013b.
Xujie Si, Hanjun Dai, Mukund Raghothaman, Mayur Naik, and Le Song. Learning loop invariants for program verification. Advances in Neural Information Processing Systems, pp. 7762-7773,
2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
Matt Staats, Shin Hong, Moonzoo Kim, and Gregg Rothermel. Understanding user understanding: determining conrectness of generated program invariants. In Proceedings of the 2012 Interna- tional Symposium on Software Testing and Analysis, pp. 188-198. ACM, 2012.
Foivos Tsimpourlas, Ajitha Rajan, and Miltiadis Allamanis. Learning to encode and classify test executions. arXiv preprint
2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp.
2017.
A APPENDIX
A. DATA COLLECTION DETAILS
We base our evaluation on a Java dataset consisting of the top 10,000 ststest Java projects on Github, collected March 30th, 2020 using the Github v3 API. Since generating our training data samples is quite expensive, we used just the top 1,000 (most starred) of these projects to automati- cally generate training and evaluation samples for the results described in Section 4.1 This dataset was split between training, held-out and evaluation sets at the organization level to ensure minimal duplication, as projects within the same organization often share many coding patterns (Allamanis, 2019). We allocated 95% of organizations (920 projects) to training data, 2% to held-out data (19 projects), and 3% to test data (61 projects), to assess the final trained models.
10

---

Under review as a conference paper at ICLR 2021
A.1.1 INVARIANT GENERATION
We parse each file using Eclipse's JDT parser and extract all (non-nested) methods from the result- ing parse tree. Within each method, we detect all if-statements, removing all those whose condi- tions contain side-effects (such as assignments, increment/decrement operators, and non-whitelisted methods, Appendix A.1.2). , and those whose body contains control-flow altering statement (e.g. return, throw) unless is the sole statement For the remainder, we generate samples based on the following types of if-statements:
Simple if-statements: these include samples like Figure T which single if-statement guards a simple body with no control-flow altering code.
If-else statements: for these we generate two samples: one in which remove the else block entirely and generate an if-invariant as above, and one in which we negate the condition and generate an invariant for just the else block. Note that else if statements in Java are treated as nested statements and thus handled the same way.
Control-flow altering if-statements: any if-statement whose body prevents the execution of sub- sequent code, by containing just return, break, cont inue, or throw (Exception) statement, is treated declaring an invariant (namely, the negation of the if-condition) for the ensuing code.
In all cases, the surrounding context is the entire method, and the range of tokens to which the condition applies (namely, those that used to be guarded) is stored with the sample. We generate samples for all these conditions, producing a new sample for every if-statement. This ensures that each sample minimally alters the original code, which reduces the risk that we produce unnatural code (which would harm the generalization of our model). As such, a method can produce many samples, so functions with many conditions will be represented proportionally more often. We do not consider that problematic, as 1. long functions tend to have correspondingly more invariants, so the increased emphasis should be beneficial to our model, and 2. we anyways cap our training samples to only modestly large functions (up to 500 sub-tokens, which typically translates to the order of 20 lines), due to memory constraints.
A.1.2 PRODUCING NATURAL FUNCTIONS
Not all -u-rdss can be removed without changing the semantics of the code; conditions can have side-effects. This includes assignments (e.g. if ((x y) != null)) ), certain operators (viz. ++ and --) and method calls with side-effects. To ensure that the converted code is semantically herent, and because invariants should not have side effects anyways, we omit all such cases. Many method calls do not have side effects, to avoid limiting our dataset too much, we heuristically lect a large, but relatively "safe" set of these based on common coding patterns. This includes com- mon "getter" methods, java. lang. Math calls, object equality tests, collection inspection methods, such as inclusion checks (e.g. 'contains', 'has") and size-related methods, and a few miscellaneous others that were common in our training data (e.g. parseInt, name). The regexes used detect these various types of methods are listed in Table
Removing if-statements does not always yield meaningful code, consider:
int foo (int x, int y) if (x > y) { return xi
return yi
'When an if-statement body terminates the current branch of execution only after first executing some other code, generating equivalent unguarded code is complicated: inlining guarded code (minus final statement) would often produce very unnatural code, as it tends to involve some form of error-recovery such as logging or resetting value. Omitting the entire block instead, as we do for simple control flow altering statements may he more appropriate; future work can explore this, and various other, corner cases to generate samples.
11

---

Under review as a conference paper at ICLR 2021
Table 2: Categories of, and Regexes used detect, whitelisted method calls, which are generally assumed not to alter program state and thus allowed in invariants.
Category
Regexes (space separated)
Object comparisons
equals [[-2] . deepEquals match (es)
compare (IA-2].+)) hashCode
Collection methods
Length size capacity depth keySet index0f
"Getter" methods
[con|acns has | / |exists /ts//shoddd can was) ([A-X].*)
+Exists (starts ( With contentEquals toString substring
String methods
tocharArray valucOf charAt to (Jpper) Lower) Case (boolean int fleat double [1ong loyte shert) parse (Boolean Int |Float |Double Long Byte Short)) log Log(10-0 (00(1)))+) abs sqrt pow max min sin ccs tan round ceil floor
Numerical properties
Mathematical calls
Misc. others
peek group (.+NIn) ame child.*
If remove the conditional check, the resulting method is left with just consecutive return statements, which is invalid in Java. This particular case would trigger a compiler error, but not all inappropriate removals do: if the if-body had instead assigned y x + 1; removing it would result in always being assigned x + 1 before returning, making the parameter useless. Not using parameter is not erroneous by definition, since the method foo may be inherited (or overriden in subclass) and other instantiations do make use of it, so Eclipse's parser just emits a warning. Since both these cases result in code that is both unrepresentative of typical Java, and would yield highly predictable invariants, we additionally reparse each resulting function after removal of the targeted if-statement and discard any changes that trigger compilation warnings and errors.
Specifically, Eclipse JDT requires full type resolution to guarantee correct program analysis and stops checking for violations if it finds compile-time errors from missing types. When processing as many projects as we do (many of which cannot be built automatically), we cannot soundly resolve all dependencies for each project. As a close approximation, we instead parse each function in its entire project context to allow as much heuristic type resolution as possible. Then, we look for any increase in warnings and errors between the method before and after removing an if-statement. This reduces the number of collected samples and increases the time generate the dataset (to 200 CPU hours for 1K projects), but also increases its validity by eliminating many inappropriate fragments.
Finally, we limit our functions to those having 500 (sub-)tokens or less to facilitate a reasonable modeling throughput. This does not reduce the dataset by much; most functions tend to fit this limit. In total, we collect ca. 2.34M training samples, 12.1K IK held-out samples and 101K 101K test samples, with approximately 200 aub-tokens per function on average.
A.1.3 COLLECTING "MISSING IF" BUGS
We collect our dataset of missing if-condition bugs from across the history of all the aforementioned 10K projects in our dataset. For each project, we parsed every commit to the main branch, using git's "diff" function to identify cases in which the sole addition was to wrap one or more existing statements in an if-statement. This yielded 32,471 samples from across 144,5555 commits. Al- though all of these may constitute interesting samples, we prioritize bug-detection for now as the most direct application of our model. To ensure that our collected samples are likely bug-related, we focus only the ca. 3.7K cases in which the entire commit introduced just single if-statement in a single Java file and the corresponding commit message contained any of the common bug-related terms such "fix", "bug", and "fault" (Ray al. 2016). We additionally filtered out any commits to projects that were included in our training dataset to avoid the risk of overlap (which need not be present as many commits reflect out-dated code). yielding 3, 146 samples in total.
12

---

Under review as a conference paper at ICLR 2021
Table 3: Statistics of Daikon's 's invariants collected on Dacapo projects.
Project
Methods
Invariants
Batik
6,797
64,298
Eclipse
2,375
41,257
H2
2,169
28,965
lusearch
1,594
81,291
luindex
1,004
9,822
PMD
5,026
274,638
Tomcat
3,983
63,146
Total
22,948
563,417
A.1.4 RUNNING DAIKON
Comparing our tool to Daikon (Ernst et al. 2007 required some adaptations. Daikon requires projects that are fully built, instrumentable, and have representative workloads. Unit tests are often insufficient because they test for both appropriate and inappropriate values (e.g. those triggering an exception), which counter to our purpose [ Scaling Daikon to our aforementioned dataset is not feasible; indeed, to the best of our knowledge there is no large public dataset of Daikon invariants on real programs. Instead, we created a modestly large dataset of our own.
To do so, leveraged the Dacapo benehmark (Blackburn et al. 2006). Originally created to bench- mark program optimizations (e.g. through better compilers), each project in this benchmark comes with set of representative workloads designed execute many of its paths. This is ideal for our case. Practically, although the benchmark comes with a single runner for each project, Daikon could not instrument through the reflective calls that this framework uses. Instead, instrumented and ran projects (details in Table 3) in this suite directly, which, in nearly all cases, involved writing our own "runner" mimic Dacapo's instrumentation while calling the requisite project-code directly. We then applied Daikon as usual, running the code under instrumentation first and then producing invariants from the resulting traces. Table 3 summarizes the resulting invariant counts.
manually
We limited the volume of the collected trace data by exponentially decreasing the number of traces for each program point once it was seen sufficiently often (10 times) and excluding many values from tracing, such as those that are not visible from the program point of interest and any nested values with more than three levels. Even then, Daikon required upwards of 30GB of RAM and nearly an hour of processing for the larger projects much more than our models.
A.2 MODELING DETAILS
A.2.1 PROGRAM GRAPH EXTRACTION FOR JAVA
We used Eclipse's JDT parser with approximate name-binding resolution to extract five edge types across 3 broad categories of information that accessible in source code:
Lexical:
every token is connected its neighbors through next-token edges (and their reverse).
This adds additional sensitivity to lexically local information beyond the positional encoding used in the standard Transformer.
we extract all AST parent-child relations, which provide insight into the hierarchical structure of source code.
Syntactic:
Data-flow: we include three types data-flow edges: next-use edges, which connect lexically sequential uses of the same variable; computed-from edges, which connect any variable usage to the last value was assigned, and def-use edges, which connect every variable usage to its (single) original declaration point.
In addition, every edge type has symmetric, mirrored version (e.g. prev-token), yielding total of 10 distinct edge kinds used by our model.
In addition, Daikon cannot instrument Jnit-tested code since it uses reflection, which effectively makes Java tests limit.
13

---

Under review as a conference paper at ICLR 2021
A.2.2 TRAINING DETAILS
Consistent with recent observations regarding effective modeling of source code vocabulary (Hellen- doorn & Devanbu 2017 Karampatsis et al. (020), we use Byte-Pair Encoding to create a sub-token vocabulary based on the tokens in our training data. Our vocabulary, estimated from the training data, spans 10,000 sub-tokens; both the input function and the predicted invariant are sub-tokenized using this (reversible) dictionary. Transformer models generally scale in memory needs with the square of the size of their inputs. To ensure that our minibatches are sufficiently large to keep the gradients stable, we restrict our inputs to functions with up to 500 (BPE) tokens and our invariants to 50 tokens (although invariants that long are very rare). With these cut-offs, we train batches of up to 12,500 tokens in parallel across two NVidia RTX Titan GPU's with 24GB of VRAM each. By packing similarly sized functions per batch, we minimize the overhead from padding and are able to fit ca. 70 functions per batch on average.
A.3 EVALUATION DETAILS
A.3.1 IF-CONDITION LOCALIZATION & REPAIR METRICS
Since some methods have far more program blocks than others, simply ranking all invariants across method boundaries by entropy would lead to bigger methods being highly disproportionally rep- resented. Rather, we try to balance method and invariant level inspection cost by simulating the inspection of 10% of invariants in dataset from subset of methods. We do so by first ranking methods by the entropy of their top invariant, from low to high, and then inspecting all invariants from these methods in order until we have inspected 10% of all location/invariatt pairs in this dataset (which number 73,738), The 10% inspection (recall) level in Table [ just 0.0233 bits, under which the average method has 55.3 blocks substantially more than the av- erage method overall. Separating out the functions with 32 or fewer program points (the mean), the overall accuracy increases to 16.3% and the 10% recall precision increases to 50.0% the joint task is naturally easier on shorter methods.
correspond to a threshold of
A.3.2 GENERATING PRE- AND POST-CONDITIONS WITH BODYGUARD
The comparison with Daikon invariants comes with important caveat: Daikon only generates method pre- and post-conditions. This means that we cannot perfectly classify the validity of all our invariants. Nevertheless, our experiments on missing conditions show that our models are precise at inferring even very specific missing conditions, which strongly suggests (as our manual analysis has too) that many of its other suggestions are valid as well.
Secondly, our tool produces invariants for any syntactic block of code throughout the method and does not have general mechanism indicate that pre- or post-conditions are required. To imitate these for our tool, the closest approximation is to mark the entire method body as needing an in- variant when a pre-condition is required and the final (zeturn) statement otherwise. To avoid the complexity of having to match multiple return points, or none at all for void methods, we restrict the latter case to methods with a single return statement only. Note that the latter an imper- fect approximation: our tool only learns to predict guards that precede statement. A guard that it predicts for a return statement may not be an appropriate substitution for true post-conditions but rather reason to return at that particular point.
A.3.3 MEASURING OVERLAP WITH DAIKON'S 'S INVARIANTS
We quantify the overlap between our predicted invariants and Daikon's 's using normalized Cumulative Gain. This metric captures the quality of a ranker in terms of how often it returns relevant elements; it is traditionally used in information retrieval, for example to evaluate a web searcher. Although discounted cumulative gain is more commonly used, we refrain from penalizing based on "rank" of predictions, because there is reason to assume that Daikon's 's invariants more salient or relevant than others that we predict. That is, all that matters is that Daikon's s invariants are among our (top 10) predictions.
14

---

Under review as a conference paper at ICLR 2021
A.4 FURTHER RESULTS
A.4.1 CHARACTERISTICS OF MANUALLY INSPECTED INVARIANTS
A large portion of the manually verified invariants in Section corresponded to fairly trivial state- ments, such as instanceof assertions for value being cast the corresponding type. In some cases, our invariants were more general accurate than Daikon's: s; e-g. when BODYGUAR asserts that an object not null whereas Daikon asserts that a member of that object not null. other times, inferred invariants that Daikon missed entirely, likely due to limitations in its internal rules and heuristics. For instance, as pre-condition of:
static ReliableFile getReliable (File file) throws ICException ())
|
if throw new FilleNotPoundixception ("");
return new ReliableFile
BODYGUARD conrectly inferred that !file. isDirectory (,, while Daikon only offered file != null.
In another case, our tool produced a more specific invariant for this PMD snippet:
public int getPriority () {
return pricrity;
Here, Daikon asserts that priority level exactly either 2 3, because those are the only ob- served values in the (evidently unrepresentative) traces off this method. This indicates how Daikon's 's invariants can inaccurate even with available workloads. BODYGUARD more broadly anticipates that priority >= which matches the method's actual specification encoded in its Javadoc documentation (which our tool does not use).
A.4.2 FURTHER EXAMPLES
In the below example badge variable, initialized null, is first assigned value based on program state, and then added to two collections (Local and, conditionally, global). This second segment, after the switch statement, should have been guarded by check that badge since not every case assigns it value. Across all 53 permutations of code blocks (and countless options per block) in this method, BODYGUARD predicts this condition at the correct location at rank 3. Its first prediction was the nonsensical statement gllcbal guard for the entire method body. Possibly, no good prediction was possible for that range, so this option had low entropy by sheer contrast with other possibilities. The second ranked prediction line after the declaration of badge. While this is tautologically valid as a pre-condition for those lines, it highlights the importance of specificity in range it is only truly invariant for some of these lines, specifically, the start of each case and the break statement of the latter two, a range that is currently supported by our approach.
null,
badge
null for every
public static void validatefutoriall ()
Badiee badge null; switch (Dungeon. hero. herohherraaaa hww..herror.ee..e
ass)) {
case WARRIOR:
badge Badge TUTORIAL EUTRIIALLMARROORR
break;
case MAGE:
badge T
break;
ROGUE:
break;
case HUNTRESS:
break;
RReaairdd in 475878 77255228000999333334444303303333
15

---

Under review as a conference paper at ICLR 2021
local. add (badge);
if (lglobal, contains (badge)) )
{
glcbal add (badge);
saveNeeded true;
The following snippe returns default image, generating it on the first call. Even though the doc- umentation of creat eatattBiie eBitMap (int, int, Bitmap. Config I does not specify it, this method can return nul1 rare cireumstances, such as when phone runs out of memory and recovers by aborting this call [o BODYGUARD correctly infers empty != mull as the top invariant, having seen similar calls other Android projects in its training data. Specifically, it predicts this invariant both for the just the line containing empty. eraseColor (rank 1), and for the block including that and the next line (rank 2). The latter is the more correct segment.
private static Bitmap getDefaul Thumbnaail () {
if Inaga == mull) Bitmap empty
(160, 200,
Satmap.Confiie ARCB ARGB_3888))
SnptyyerascColo.o (Color. WHITE)
default = paint (empty);
dmfaultImagg;
A.5 LIMITATIONS
We evaluated our predictions broadly to assess both their salience and validity. Even so, it is hard to automatically assess all of our invariants, especially those inserted in the middle of methods and those whose vocabulary is outside of what Daikon finds. However, the results the task of predicting missing if-statements, (which avoids these evaluation problems) are quite encouraging; believe that this bodes well for the more general settings. Future work may better assess validity of our entire vocabulary of invariants, perhaps by injecting asserts corresponding to our predictions into the source code and executing the tests.
Our second main criterion is salience: our predictions should be particularly relevant to the refer- enced code, contrast to prior work. We chose assess this by using real missing if guards, which would appear to be a good example of particularly salient implicit conditions (as developers chose make them explicit). We did not quantitatively study other types of salience, such as which con- ditions are most informative or intuitively obvious to real developers. This, too, may be fruitful area for future work; human subject studies involving invariants have produced worthwhile insights into developer behavior in the past (Staats et al. 2012)
*Repaired http:///tttth.......aooaaa/aa/t/ 356655555001555224e3333325555533
CreateBi or
"AAs suggested /xssgsalltttss///seeeer/ooo/o//0
16


Reviews:
[{"review_id": "w9OcVw1PQR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 discover likely invariants for code by observing snippets that check for the given conditions and assuming these conditions encode invariants for the code executing before and after the condition check was checked to hold (respectively not hold for negated invariant). This is a novel idea that uses code with correct if conditions to guess the invariants for code that has the conditions missing.\n\nMy main criticism for the paper is that it does not give a compelling reason why one would want to apply this technique. While this is a smart way to obtain the invariants, the paper does not give too much intuition why it could be useful in practice. Even on the examples in the paper, the machine learning algorithm probably learns invariants from identifier names and not from the semantics of  the code around.\n\nThe authors can relate the work to a large corpus of learning invariants for functions based on things like usages of functions, e.g. like done in [1] or [2] and the techniques there find actual bugs in code. For example, if the invariant is non-nullness of x, this may be because x comes from a function that sometimes returns null or because it comes from a function that does not accept null. If I would want to do for example bugfinding, I would want to know contradicting invariants coming from the two functions.\n\nIn terms of execution, the paper is well written and the techniques look state-of-the-art from a machine learning perspective (although there are no baselines given). However, the experiments are insufficient for showing usefulness of the idea. With Daikon overlap in the 70% range and precision also in the same range, it is not clear that the tool gives any new valid invariants on top of Daikon. In terms of bugfinding, the results are also inconclusive that any bugs can be found. If I would put the tool to test 100 methods, where normally less than 10 of them are buggy, I can expect 20 false positives.\n\n\n\nMinor:\ntheorem proofers -> theorem provers\nFigure 5 a talks about overlap, but axis says precision.\n\n[1] Ted Kremenek, Paul Twohey, Godmar Back, Andrew Y. Ng, Dawson R. Engler:\nFrom Uncertainty to Belief: Inferring the Specification Within. OSDI 2006\n[2] Insu Yun, Changwoo Min, Xujie Si, Yeongjin Jang, Taesoo Kim, Mayur Naik: APISan: Sanitizing API Usages through Semantic Cross-Checking\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "o0bFk1Jdus-", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Summary: This paper proposes a novel approach for training a Transformer model to predict program invariant. The model is trained using training data that are synthesized from explicit conditional checks in functions and is used to predict invariants of unguarded blocks in similar functions.     \n\nStrength\n1. The paper addresses the important and challenging problem of program invariant generation from static code in a scalable way. \n2. Real-world “missing if-guard” bugs are detected using the proposed model.\n\nWeakness\n1. The idea of synthesizing training data by automatically converting explicitly guarded code to its implicitly guarded counterpart is interesting. However, the effectiveness of the trained model to infer program invariants in a general way is not clear from the experimental results. The evaluation with real-world bugs focuses on “missing if-guard” bugs. The difficulty of detecting this bug cannot be understood as there is no accuracy results from an existing tool (for example, Daikon) in detecting this real-world \n2. Although a comparative analysis with Daikon is presented, the presented approach focuses on a narrower class of invariants compared to Daikon. Moreover, Daikon relies on execution traces. A comparison with an existing ML based approach using static code (e.g., [1]) would provide more interesting insights about the model’s accuracy. \n3. A contrastive hinge loss is introduced to address the “syntactically close” but “semantically opposite” cases. However, from Figure-4, it seems the performance of the model is not impacted in a significant way by the loss function.\n\n[1] P. Garg, D. Neider, P. Madhusudan, and D. Roth. Learning Invariants using Decision Trees and Implication Counterexamples.\n\nQuestion to author:\nPlease address and clarify the cons above.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gU4Epd_Vxg", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "### Summary ###\nThe paper presents a technique for inference of certain kinds of program invariants directly from the program’s source code. The basic idea is to treat conditional statements as hints for facts about the program state that should hold at a given program point. \n\n\n### Strengths ###\n\n* This is a challenging problem and the paper shows some successful examples. The idea that some useful invariants can be inferred based on local information, while not new, is interesting and can lead to follow up work of practical value.\n\n* The contrastive hinge loss of syntactically close but semantically opposite statements is interesting. \n\n### Weaknesses ###\n\n* The paper falls short on the framing of the invariant inference problem, and on the technical details of what does it mean to infer a meaningful local invariant. Starting from trivialities like the fact that the problem is generally undecidable (and not as stated in Section 2), through the use of incorrect terminology for invariants, guards, pre/post conditions, etc. This just makes the paper hard to follow. \n\n* Fundamentally, beyond simple invariants (array bounds, nullness checks) it is not clear why program invariants would generalize well across different programs. The exception is of course the use of libraries and invariants in library contracts (as learned in [PLDI19a, PLDI19b]). For nullness guards, you should take a look at [https://arxiv.org/pdf/1902.06111.pdf]. I think it would improve the paper if you could focus on a certain kind of invariants, and show that these invariants can in fact generalize across programs. \n\n* As a concrete example, take your own Figure 1. Assuming that these are two different programs, there is no reason to assume that the contract of `calculateTime()` remains the same. Had `calculateTime()` been part of some standard library shared between programs, the case for generalization would have been much stronger. \n\n* There has been so much work on static inference of invariants that it is impossible to list even all the closely related work. Some things that are worth looking into are the work on Scalable static analysis [Scaling], the inference of necessary preconditions [Logozzo], and bug detection that is based on \"belief\" [deviant, belief], which is closely related to your intuition about naturalness and human-written invariants. Also helpful to look at [loopInvariant] and the related work mentioned there. \n\n* Comparison to Daikon. As you correctly point out, Daikon infers likely pre/postconditions. The description of how you compare your invariants to those inferred by Daikon is not clear unless all relevant cases related to (pre)conditions on method parameters. \n\n\n### Questions for Authors ###\n\n* It would be helpful to see more characteristics of the real missing if conditions that you have collected. I am wondering if these are simple conditions of the kind of missing nullness checks or missing array-bound checks. The way in which you have collected these samples is likely to create a bias towards simple missing conditions. How many terms are in these conditions? How many of them are nullness checks? How many are array-bound checks? How many include simple string operations and/or other simple method calls as implied by Table 2? \n\n\n### Improving the Paper ###\n\n1. I liked the idea of removing conditionals to infer likely necessary preconditions. It would help to clarify when what you predict is a guard, a precondition, an invariant, or something else. \n\n2. You are clearly not trying to infer any loop invariants, and it would help clarify that upfront. \n\n\n### References ###\n\n[PLDI19a] Scalable taint specification inference with big code\nhttps://dl.acm.org/doi/10.1145/3314221.3314648\n\n[PLDI19b] Unsupervised learning of API aliasing specifications\nhttps://dl.acm.org/doi/10.1145/3314221.3314640\n\n[Scaling] Scaling static analyses at Facebook\nhttps://dl.acm.org/doi/10.1145/3338112\n\n[Logozzo] Automatic inference of necessary preconditions\nhttps://link.springer.com/chapter/10.1007/978-3-642-35873-9_10\n\n[deviant] Bugs as deviant behavior: a general approach to inferring errors in systems code\nhttps://dl.acm.org/doi/10.1145/502034.502041\n\n[belief] Static error detection using semantic inconsistency inference\nhttps://dl.acm.org/doi/abs/10.1145/1250734.1250784\n\n[loopInvariants] Learning Loop Invariants for Program Verification\nhttp://papers.nips.cc/paper/8001-learning-loop-invariants-forprogram-verification\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KotmMUQKhyV", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 presents a method for statically learning code invariants from source code using a variant of transformers.\n\nStrengths\n----\n- The paper demonstrates that on the synthetic dataset the proposed approach can infer many invariants. \n\nWeaknesses\n----\n- The evaluation with a synthetic dataset seems very weak. “If” checks are not good proxies for useful invariants as in most programs there are many if checks that are simply unreachable or redundant. In practice,  not all invariants are useful for the downstream tasks (code fixing, bug finding, etc.) mentioned by the authors. Without a more direct evaluation, it is very hard to tell how useful the learned invariants actually are for these tasks. The paper will be significantly stronger if the authors can evaluate their tool against existing loop invariant inference datasets with ground truth data like those used in Si et al. (NeuRIPS 2018). \n\n- The transformer-based model seems to be directly reused from Hallendoorn et al. (ICLR 2020). Thus the contribution in terms of model design is limited. \n\n- The authors also did not cite/compare against the current state-of-the-art loop invariant learning work: CLN2INV: Learning Loop Invariants with Continuous Logic Networks. Ryan et al. ICLR 2020", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives a way of constructing a dataset of programs aligned with invariants that the programs satisfy at runtime, and training a model to predict invariants for a given program.

While the overall idea behind the paper is reasonable, the execution (in particular, the experimental evaluation) is problematic. As a result, the paper cannot be accepted in its present form. Please see the reviews for more details.
Decision: Reject