PaperlayerView exact revision on arXiv

Source-linked AI summary

Static Prediction of Runtime Errors by Learning to Execute Programs with External Resource Descriptions

David Bieber, Rishab Goel, Daniel Zheng, Hugo Larochelle, Daniel Tarlow

arXiv:2203.03771v1cs.LGcs.PL

TL;DR

Programs rely on external resources, making runtime errors difficult to predict from source code when execution is unavailable. The paper introduces a real-world task and dataset and adapts interpreter-inspired models to execute with resource descriptions and handle exceptions. These models outperform standard alternatives and can localize errors without location supervision, though they require many execution steps.

  • Problem

    Program behavior depends on external resources unavailable from source code alone, raising the question of whether runtime errors can be predicted without executing programs.

    Source: §1 · p. 1

  • Method

    The paper extends IPA-GNNs to model exception handling and incorporate natural-language descriptions of external resources into their learned executions.

    Source: §1 · p. 2, §4.2 · p. 6

  • Results

    Interpreter-inspired models outperform standard alternatives like Transformers, and can localize errors despite training only on error presence and kind.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The runtime-error task and dataset offer a practical challenge for studying program execution in code models.

    Source: §1 · p. 1, §6 · p. 9

    Current IPA-GNN models require up to 174 execution steps on this dataset.

    Source: §6 · p. 9

Abstract

from arXiv · show

The execution behavior of a program often depends on external resources, such as program inputs or file contents, and so cannot be run in isolation. Nevertheless, software developers benefit from fast iteration loops where automated tools identify errors as early as possible, even before programs can be compiled and run. This presents an interesting machine learning challenge: can we predict runtime errors in a "static" setting, where program execution is not possible? Here, we introduce a real-world dataset and task for predicting runtime errors, which we show is difficult for generic models like Transformers. We approach this task by developing an interpreter-inspired architecture with an inductive bias towards mimicking program executions, which models exception handling and "learns to execute" descriptions of the contents of external resources. Surprisingly, we show that the model can also predict the location of the error, despite being trained only on labels indicating the presence/absence and kind of error. In total, we present a practical and difficult-yet-approachable challenge problem related to learning program execution and we demonstrate promising new capabilities of interpreter-inspired machine learning models for code.

1 INTRODUCTION

The paper frames static runtime-error prediction as a practical challenge because program behavior depends on external resources that source code alone does not capture. It introduces a large Python dataset and adapts interpreter-inspired models to use resource descriptions and model exception handling, reporting improved prediction and error localization without location labels.

1 INTRODUCTION

  • Programs often depend on external resources, so their execution behavior cannot be fully determined from source code alone.The task asks whether runtime errors can be predicted before program execution is possible.Source: §1 · p. 1
  • Generic models such as Transformers find runtime-error prediction challenging, motivating it as a challenge problem for learning about program execution.The paper situates this difficulty alongside prior reports of challenges in execution-focused code tasks.Source: §1 · p. 1
  • The task and dataset are presented as a practical, difficult-yet-approachable challenge with immediate value for software developers.The authors also make the task, dataset, and considered models available for further research.Source: §1 · pp. 1–2
  • The Python Runtime Errors dataset contains 2.4 million Python 3 programs labeled with 26 runtime-error classes, including no error.Programs are paired with natural-language descriptions of stdin behavior.Source: §1 · p. 2
  • The combined IPA-GNN improvements increase runtime-error prediction accuracy over standard alternatives and support error localization without location supervision.The model is trained on error presence and kind, not error location.Source: §1 · p. 2
  • The work scales IPA-GNNs to real-world code, adds execution conditioned on external-resource descriptions, and models exception handling.The architecture considers up to 174 execution steps on this dataset.Source: §1 · p. 2

2 RELATED WORK

Prior work spans static and dynamic program analysis, machine-learning approaches to code errors, and interpreter-inspired architectures. The paper distinguishes its task by requiring execution reasoning on real programs and by localizing errors without location supervision.

2 RELATED WORK

  • Static analyses detect defects without executing code, while dynamic analyses examine programs at runtime.Linters and type checkers are cited as popular static-analysis tools.Source: §2 · p. 2
  • Many prior machine-learning code tasks do not require execution reasoning, or use synthetic data or step-by-step trace supervision.The paper contrasts its task with these settings and with large models that struggle on program execution.Source: §2 · p. 2
  • Prior error-localization approaches use localization supervision, whereas this work predicts locations without it.Interpreter-inspired models related to this work emphasize control flow and exception handling rather than memory allocation or function-call stacks.Source: §2 · pp. 2–3

3 RUNTIME ERROR PREDICTION

The task is to predict runtime errors without executing programs, using descriptions of unavailable external resources to make reasoning about execution plausible. The dataset uses filtered competitive-programming submissions, records errors on a single input, and evaluates with problem-separated splits and a balanced test set.

3 RUNTIME ERROR PREDICTION

  • The task asks whether a program is liable to encounter a runtime error despite unavailable execution inputs, using resource descriptions to make execution reasoning plausible.Examples of resources include program inputs, file contents, and the network.Source: §3 · p. 3
  • Framing error prediction as machine learning covers programs lacking unit tests and cases where static analysis may not apply, including Python or natural-language constraints.The task also tests statistical reasoning together with reasoning about program execution.Source: §3 · p. 3

3.1 DATASET: PYTHON RUNTIME ERRORS

  • Programs are assigned a single target class: one error type or the additional no-error class.For programs with errors, the dataset also records the error line for unsupervised localization.Source: §3 · p. 3, §3.1 · p. 3
  • 2.44 million filtered Python submissions form the dataset, with 26 target classes and 93.4% labeled no error.Because each program is run on only one input, labels under-approximate the full set of runtime errors it may encounter.Source: §3.1 · p. 3
  • Problems are split 80:10:10 across train, validation, and test, and the balanced test set samples no-error examples to make up roughly half its examples.Keeping submissions for each problem in one split reduces similarities across splits.Source: §3.1 · p. 3

4 APPROACH: IPA-GNNS AS RELAXATIONS OF INTERPRETERS

The approach treats IPA-GNN as a continuous relaxation of an interpreter, modifying it to handle real-world code, external resource descriptions, and exceptions. It also uses the model’s soft exception decisions to estimate error locations without location supervision.

4 APPROACH: IPA-GNNS AS RELAXATIONS OF INTERPRETERS

  • The IPA-GNN is framed as a continuous relaxation of Interpreter A, with modifications for real-world code and resource descriptions, and added exception handling to form Interpreter B.Figure 1 illustrates the discrete interpreters and a continuous relaxation of Interpreter B on a sample program.Source: §4 · p. 4, §4.1 · p. 4, Figure 1 · p. 5

4.1 EXTENDING THE IPA-GNN TO REAL-WORLD CODE

  • Real-world programs have varied, complex statements, averaging 6.7 tokens, and the IPA-GNN uses up to 174 execution steps under its step-limit heuristic.Rematerialization is applied at each step to reduce memory requirements.Source: §4.1 · pp. 4–5

4.2 EXECUTING WITH RESOURCE DESCRIPTIONS

  • Resource descriptions condition each statement’s execution through modulation of its embedding using the description and current hidden state; docstring injection provides an alternative applicable to any model.The modulation options considered are FiLM and cross-attention.Source: §4.2 · p. 6

4.3 MODELING EXCEPTION HANDLING

  • Exception IPA-GNN adds raise decisions so execution can proceed to an enclosing except block or a global error node, then uses probability mass at exit and error nodes to predict error presence and type.It is trained with cross-entropy on error-class predictions, with “no error” as its own class.Source: §4.3 · p. 6

4.4 UNSUPERVISED LOCALIZATION OF ERRORS

  • Soft exception decisions can estimate error locations despite training only on error presence and kind; programs with try/except frames require tracing exceptions to their original raising statements.For programs without try/except frames, localization estimates exception provenance by summing each node’s contributions to the exception node across time steps.Source: §4.4 · p. 7

5 EXPERIMENTS

The experiments compare interpreter-inspired architectures with standard baselines, test resource-description methods, and assess whether error locations emerge without localization supervision.

5.1 EVALUATION OF IPA-GNN AGAINST BASELINES

  • Baseline comparisons use BPE-tokenized programs; the Transformer processes token sequences directly, while the other models operate on per-node embeddings.The Transformer uses mean pooling; the LSTM baseline and IPA-GNN RNN use two-layer LSTMs.Source: §5.1 · p. 7
  • Interpreter-inspired architectures show significant gains over GGNN, Transformer, and baseline approaches on runtime error prediction.Table 2 reports accuracy, weighted F1, and weighted error F1 on the balanced test set.Source: §5.1 · p. 7, Table 2 · p. 8

5.2 INCORPORATING RESOURCE DESCRIPTIONS

  • Across architectures, using any external resource description improves runtime error prediction, while direct integration into IPA-GNN execution yields inconsistent additional gains.Cross-attention IPA-GNN was best by validation selection, but Exception IPA-GNN performed better on test.Source: §5.2 · p. 8, Table 3 · p. 8
  • With a stdin description, the model recognizes that input() calls read beyond the end of the stream, unlike the model without that description.The dataset’s stdin descriptions can also provide types, numeric ranges, and input formatting details.Source: §5.2 · p. 8

5.3 INTERPRETABILITY AND LOCALIZATION

  • Localization models receive only error-kind and presence supervision, and localization accuracy measures the percent of erroneous test examples with the correct error line predicted.The Exception IPA-GNN’s instruction-pointer mass resembles plausible executions and supports unsupervised localization.Source: §5.3 · p. 9, Table 4 · p. 9
  • Exception IPA-GNN’s unsupervised localization capabilities far exceed those of baseline approaches.The comparison reports localization accuracy for MIL Transformers and Exception IPA-GNN on the balanced test split.Source: §5.3 · p. 9, Table 4 · p. 9

6 DISCUSSION

The paper extends interpreter-inspired models for runtime-error prediction with external-resource descriptions and exception handling, and reports that they outperform standard alternatives. It also highlights unsupervised error localization while noting the models’ execution-step cost.

6 DISCUSSION

  • The resulting interpreter-inspired models outperform standard alternatives like Transformers and support unsupervised error localization.Their inductive bias allows internal execution-like behavior to help identify error locations.Source: §6 · p. 9
  • Current IPA-GNN models require up to 174 execution steps on this dataset; proposed future directions include reducing steps and extending interpreter features.The authors also identify support for multi-file programs and multiple user-defined functions as future work.Source: §6 · p. 9
  • In Table 5, R.D. correctly predicts EOFERROR with 0.988 confidence and localizes it at line 3 (n = 3), while BASELINE incorrectly predicts NO ERROR with 0.708 confidence.The input description shows that the program has more input() calls than the number of expected inputs (one).Source: Table 5 · p. 10
  • Figure 2 shows baseline instruction-pointer mass mostly ending at nexit, while the resource-description model concentrates mass on nerror from node 2.The figure plots timesteps against nodes, with nexit and nerror as the last two rows.Source: Figure 2 · p. 10
  • The work presents a challenging problem and advances interpreter-inspired models as ingredients toward progress on learning execution behavior.The discussion notes that execution becomes challenging as programs grow and depend on external resources whose contents are absent from code.Source: §6 · p. 10

A PYTHON RUNTIME ERROR DATASET DETAILS

The Python Runtime Errors dataset is constructed from Project CodeNet submissions by filtering and executing Python programs, and by extracting input descriptions and constraints from problem statements.

A PYTHON RUNTIME ERROR DATASET DETAILS

  • The dataset construction partitions problems into train, validation, and test splits at 80:10:10, keeping submissions to the same problem together to mitigate leakage from similar submissions.The source contains more than 14 million submissions across 4,053 problems and over 50 languages; the construction focuses on Python submissions.Source: A PYTHON RUNTIME ERROR DATASET DETAILS · p. 14

A.1 SYNTACTIC FILTERING

  • Syntactic filtering removes Python 2 submissions, programs that fail to parse or run, and six programs for which the control-flow-graph library fails.The removals include 76,888 Python 2 programs, 59,813 syntax-error programs, and 2,011 parsing-time runtime errors.Source: §A.1 · p. 14

A.2 PROGRAM EXECUTION

  • Programs run in a sandbox with sample input and a one-second limit; exception names become target classes, singleton error types map to Other, and successful runs map to no error.Timeouts are also assigned an error class.Source: §A.2 · p. 14
  • The dataset records each runtime error’s line number as ground truth for the unsupervised error-localization task.Source: §A.2 · p. 14

A.3 PARSING INPUT SPACE INFORMATION FROM PROBLEM STATEMENTS

  • Input descriptions are formed from available problem-statement input and constraint sections, with support for English and Japanese statements.Experiments prepend the descriptions as docstrings or process them using cross-attention or FiLM.Source: §A.3 · p. 14

A.4 VOCABULARY CONSTRUCTION AND COMPLEXITY FILTERING

The dataset uses BPE tokenization and complexity filters to bound program size, while excluding submissions that call user-defined functions.

A.4 VOCABULARY CONSTRUCTION AND COMPLEXITY FILTERING

  • The vocabulary uses BPE tokenization, constructed from one million training submissions and training-split input descriptions, with a vocabulary size of 30,000.Source: §A.4 · p. 14
  • Program length, control-flow-graph nodes and edges, and execution steps are capped to trim exceptionally long programs, reducing acceptable examples by less than 1%.The tokenized program limit is 512 tokens, while node and edge counts are capped at 128 and execution steps at 174.Source: §A.4 · pp. 14–15
  • Figure 3 shows program-length distributions in lines, and Figure 4 shows statement-length distributions in tokens, for the training split.Source: Figure 3 · p. 15, Figure 4 · p. 15
  • The dataset excludes submissions that call user-defined functions, removing a further 682,220 submissions.The authors leave modeling user-defined functions to future work.Source: §A.4 · p. 15

A.5 FINAL DATASET DETAILS

After filtering, the dataset contains 2,441,130 examples. The accompanying methods describe resource-input modulation and random-search hyperparameter selection for the model architectures.

A.5 FINAL DATASET DETAILS

  • After syntactic and complexity filtering, the final dataset contains 2,441,130 examples, with mean program length of 14.2 lines and mean statement length of 6.7 tokens.Source: §A.5 · p. 15

B INPUT MODULATION

C HYPERPARAMETER SELECTION

  • Hyperparameters are selected by independent random searches for each architecture; for IPA-GNN variants, T(x) denotes the number of execution steps modeled for program x.Table 6 gives settings for three Transformer sizes.Source: C HYPERPARAMETER SELECTION · p. 16, Table 6 · p. 16

D LOCALIZATION BY MODELING EXCEPTION HANDLING

The Exception IPA-GNN tracks where exception probability originates and propagates, enabling it to predict error locations in programs with or without try/except frames.

D LOCALIZATION BY MODELING EXCEPTION HANDLING

E METRIC VARIANCES

The variance analysis repeats model training with selected hyperparameters and varied seeds; the multiple-instance-learning alternatives aggregate per-statement predictions into program-level outputs while retaining location predictions.

E METRIC VARIANCES

  • Three additional training runs per baseline and docstring Exception IPA-GNN model estimate metric variance, with selected hyperparameters fixed and seeds 0, 1, and 2 varied.Reported ± values are one standard deviation.Source: E METRIC VARIANCES · p. 17, Table 8 · p. 17

F MULTIPLE INSTANCE LEARNING

  • Multiple instance learning turns per-statement node embeddings into unnormalized per-statement class predictions, then aggregates predictions for an overall task output.Source: F MULTIPLE INSTANCE LEARNING · p. 17
  • The three aggregation strategies are logsumexp, max, and mean; logsumexp treats the per-statement predictions as logits.K denotes the set of error classes.Source: F MULTIPLE INSTANCE LEARNING · p. 17
  • MIL models minimize cross-entropy for target-class prediction while still providing predictions over statement locations.Location probabilities are computed from per-statement class probabilities.Source: F MULTIPLE INSTANCE LEARNING · pp. 17–18

G EXAMPLE VISUALIZATIONS

The section shows randomly sampled validation examples with prediction visualizations for the selected BASELINE and DOCSTRING Exception IPA-GNN variants, including cases where their error and location predictions differ.

G EXAMPLE VISUALIZATIONS

  • The visualizations are additional randomly sampled examples from the Python Runtime Error validation split.Source: G EXAMPLE VISUALIZATIONS · p. 18
  • The heatmaps plot timesteps on the x-axis and nodes on the y-axis, with exit and exception nodes in the final two rows.For-loop statements have two control-flow graph spans, so the figures list two indexes and report total error contribution for the line.Source: G EXAMPLE VISUALIZATIONS · p. 18
  • Figure 5 shows BASELINE predicting NO ERROR at confidence 0.808 for an INDEXERROR, while DOCSTRING predicts INDEXERROR at 0.693 but localizes it to line 3 instead of line 5.The BASELINE instruction pointer ends mostly at the exit node; DOCSTRING ends mostly at the exception node.Source: Figure 5 · p. 18
  • Figure 6 shows BASELINE predicting INDEXERROR at confidence 0.319 for a VALUEERROR, while DOCSTRING predicts VALUEERROR at 0.880 on line 2 rather than line 1.Both instruction pointers shift most probability mass to the exception node.Source: Figure 6 · p. 19
  • Figure 7 shows both models correctly predicting NO ERROR: BASELINE at confidence 0.416 and DOCSTRING at 0.823.BASELINE’s instruction pointer ends split between exit and exception nodes; DOCSTRING ends mostly at the exit node.Source: Figure 7 · p. 20
Loading 2203.03771v1…