Neural Attribution for Semantic Bug-Localization in Student Programs

Rahul Gupta, Aditya Kanade, Shirish K. ShevadeNeurIPS 2019 · OpenReview

Providing effective feedback is a cornerstone of computer science education. In massive open online courses (MOOCs) and large university classes, automated grading systems are heavily relied upon to evaluate programming assignments. While these systems excel at providing real-time feedback on functional correctness—typically by running a test suite and returning pass/fail results—they often leave students stranded when it comes to debugging. Knowing that a program failed is much easier than knowing why or where it failed.

To bridge this gap, researchers introduced NeuralBugLocator (NBL), a deep learning framework designed to pinpoint the exact lines of a faulty program without ever executing the code. By combining a novel tree-based convolutional neural network with advanced "neural attribution" techniques, NBL learns from the collective patterns of thousands of student submissions to identify semantic bugs.

The Limitations of Traditional Debugging

Traditional bug-localization techniques generally fall into two categories, both of which struggle in an educational context:

  1. Spectrum-based localization: This approach requires running the program many times and comparing the execution paths of passing versus failing tests. It is computationally expensive, requires a robust and comprehensive test suite, and relies on dynamic execution traces.
  2. Reference-based static analysis: This method compares a student's code to an instructor's "perfect" reference solution. However, students use wildly different variable names, logic structures, and coding styles. These stylistic differences are often flagged as errors, leading to noisy and unhelpful feedback.

The authors sought a "static" approach that could analyze the code and identify errors without running it, while remaining flexible enough to handle the diverse ways students solve programming problems.

Methodology: How NeuralBugLocator Works

The NBL framework operates in two distinct phases: forward prediction and backward attribution.

Overview of the NeuralBugLocator framework, showing forward prediction and backward attribution.

Phase 1: The Tree Convolutional Neural Network (TCNN)

Programs are not merely strings of text; they possess a strict hierarchical structure represented by an Abstract Syntax Tree (AST). The researchers developed a TCNN that flattens these trees into a 2D matrix representation. This encoding allows the network to utilize standard, highly optimized convolution filters to capture "spatial" relationships within the code—for instance, how a variable declared in an if statement relates to the logic inside the block.

The network is trained to take a program and a specific Test ID as input and predict a binary outcome: Pass (1) or Fail (0).

Phase 2: Neural Attribution via Integrated Gradients

Once the model can accurately predict a test failure, the system must explain why it made that prediction. To do this, the researchers employ Integrated Gradients, a state-of-the-art neural explainability tool. This technique "backtracks" the prediction to identify which specific input features (i.e., which lines of code) contributed most heavily to the "Fail" outcome.

A key innovation in NBL is its baseline selection. Standard attribution techniques compare an input to a "neutral" baseline, like a completely black image in computer vision. For source code, a "blank" program doesn't provide a meaningful comparison. Instead, NBL searches for a correct student program that is syntactically similar to the buggy one and uses that as the baseline. This contextual attribution acts as a filter, allowing the model to ignore the student's unique coding style and isolate the specific logical flaws causing the bug.

Datasets and Evaluation

The researchers trained and evaluated NBL using a massive dataset of C programs written by students across 29 different introductory programming tasks.

  • Training Scale: Approximately 270,000 program-test pairs.
  • Test Suite: 231 instructor-provided tests.
  • Evaluation Set: 2,136 buggy programs where the "ground truth" (the actual location of the bug) was rigorously determined using a combination of diff tools and delta debugging.

Key Results

NBL was evaluated against state-of-the-art spectrum-based tools (Tarantula and Ochiai) and a syntactic diff-based baseline. The results demonstrated that learning from the "crowd" of student submissions yields highly accurate localization.

Bug-localization results comparing NBL to traditional baselines.
  • High Top-10 Accuracy: NBL successfully localized at least one bug within the top 10 suggested lines for over 80% of the evaluated programs (1,164 out of 1,449 programs in the primary evaluation configuration).
  • Superiority in Sparse Data: NBL significantly outperformed traditional tools when only a single failing test was available. For example, in the strict "Top-1" metric (finding the exact buggy line on the very first suggestion), NBL was highly effective, whereas spectrum-based baselines struggled without a large suite of passing and failing tests to compare.
  • Efficiency: Because it is a static, feed-forward approach, NBL takes less than a second to localize bugs in a new program once the model is trained, making it ideal for real-time MOOC environments.

Limitations and Future Directions

While highly effective at localization, the authors noted that the model's raw prediction accuracy (Phase 1) on the specific evaluation set was around 54%, largely because the evaluation set consisted entirely of failures and was distributionally different from the training data. Additionally, the current implementation is tailored to C programs; expanding to languages like Python or Java would require new parsers and similarly large datasets.

Ultimately, NeuralBugLocator proves that static, deep-learning-based attribution can successfully untangle semantic errors in student code. The authors suggest that the next logical step is moving from localization ("where is the bug?") to automated repair ("how do I fix it?"), potentially using generative models to suggest targeted patches based on NBL's precise localization.

Summary updated

Abstract

Providing feedback is an integral part of teaching. Most open online courses on programming make use of automated grading systems to support programming assignments and give real-time feedback. These systems usually rely on test results to quantify the programs' functional correctness. They return failing tests to the students as feedback. However, students may find it difficult to debug their programs if they receive no hints about where the bug is and how to fix it. In this work, we present NeuralBugLocator, a deep learning based technique, that can localize the bugs in a faulty program with respect to a failing test, without even running the program. At the heart of our technique is a novel tree convolutional neural network which is trained to predict whether a program passes or fails a given test. To localize the bugs, we analyze the trained network using a state-of-the-art neural prediction attribution technique and see which lines of the programs make it predict the test outcomes. Our experiments show that NeuralBugLocator is generally more accurate than two state-of-the-art program-spectrum based and one syntactic difference based bug-localization baselines.
BibTeX
@inproceedings{gupta2019neural,
  author = {Rahul Gupta and Aditya Kanade and Shirish K. Shevade},
  title = {{Neural Attribution for Semantic Bug-Localization in Student Programs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=BxTq87xOdeav},
}
Figure