Perfect is the enemy of test oracle

Ali Reza Ibrahimzada, Yigit Varli, Dilara Tekinoglu, Reyhaneh Jabbarvand

TL;DR

This paper introduces SEER, a novel deep learning approach that acts as an automated test oracle for Java unit tests. Instead of requiring explicit assertions or knowledge of correct program behavior, SEER learns to distinguish between passing and failing tests by embedding unit tests and their corresponding code into a shared vector space, achieving high accuracy and efficiency.

What Problem Does This Paper Address?

Automating software testing is a major goal, but a significant bottleneck is the "test oracle problem." A test oracle determines if a test passes or fails by comparing the actual output to an expected "ground truth." Traditionally, this ground truth comes from explicit assertions in the test code or requires deep knowledge of the program's correct behavior. This is challenging because:

  • Explicit assertions are brittle: They need to be manually written and maintained, often requiring developers to know the exact expected output.
  • Knowing the "correct" behavior is hard: For complex programs, defining the exact expected output for every possible input is often undecidable or impractical.

This paper tackles the challenge of building effective test oracles without needing explicit assertions or a perfect understanding of the "correct" program behavior. They argue that it's sufficient to learn how tests differentially correlate with program behavior when they pass versus when they fail.

Methods

SEER employs a deep learning-based approach with two main phases:

  1. Joint Embedding (Phase 1):
    • SEER takes pairs of unit tests (ti) and their corresponding Method Under Test (MUT) implementations (mi).
  2. It uses a novel domain-specific joint embedding technique to map both ti and mi into a shared d-dimensional vector space.
  3. The key idea is to train the embedding such that the vector representation of a test (Dt_i) is similar to the MUT it passes on (Dm_i+) and dissimilar to the MUT it fails on (Dm_i-). This is achieved by minimizing a margin ranking loss.
  4. This phase effectively learns to semantically separate representations of correct and buggy code based on test outcomes.
  5. Classification (Phase 2):
    • The learned embeddings from Phase 1 are concatenated to form a feature representation for the <ti, mi> pair.
  6. This combined feature vector is fed into a classifier (e.g., fully connected layers with softmax) trained using Weighted Cross-Entropy Loss.
  7. This classifier acts as the final test oracle, predicting a "pass" or "fail" label for a given test and MUT.

SEER also includes components for:

  • Method Extractor: Extracts MUT implementations from test code using lightweight static analysis.
  • Dataset Augmentor: Mutates existing passing test cases to generate higher-order mutants, creating more diverse failing scenarios.
  • Interpreter: Analyzes the model's attention mechanisms and embedding space to understand why it makes certain predictions, ensuring trustworthiness and potentially aiding bug localization.

Datasets

  • Defects4J: The primary source for initial training data, providing reproducible bugs and associated tests for widely-used Java projects.
  • Augmented Dataset: SEER augments the Defects4J dataset by:
  • Removing explicit assert statements from developer-written and automatically generated tests to prevent bias.
  • Generating higher-order mutants (HOMs) of MUTs to create more diverse and complex failure scenarios.
  • Incorporating automatically generated tests (e.g., from Randoop) to increase test coverage.

The final augmented dataset contains over 100,000 passing and failing <ti, mi> pairs.

Key Insights and Ideas

  • "Perfect is the enemy of good": The core insight is that you don't need to know the exact correct behavior to build a useful test oracle. It's sufficient to learn the differences in how tests correlate with code when they pass versus when they fail.
  • Joint embedding for semantic separation: By mapping tests and code into a shared space and enforcing similarity for passing pairs and dissimilarity for failing pairs, the model learns to distinguish between correct and buggy code behavior from the perspective of test outcomes.
  • Interpretable deep learning for trust: SEER doesn't treat the DL model as a black box. By analyzing attention weights and embedding distributions, the authors validate that the model learns from relevant code tokens and effectively separates buggy from correct code representations.
  • Augmentation for robustness: Generating higher-order mutants is crucial for creating a diverse set of failure cases, which helps the model generalize better to real-world bugs.

Key Results

  • Effectiveness: SEER achieves high performance on predicting test labels, with an overall accuracy of 93%, precision of 86%, recall of 94%, and F1 score of 90%.
  • Generalization: The model shows good generalization capabilities, with only a minor performance drop (around 9%) when tested on projects not seen during training.
  • Efficiency: Once trained, SEER can predict a test verdict in an average of just 6.5 milliseconds.
  • Interpretability: Attention analysis shows that SEER focuses on relevant code tokens and statements when making predictions, and embedding analysis confirms the separation of buggy and correct code representations.

Limitations and Future Work

  • Dataset Bias: SEER's performance can be affected by the contribution of projects to the training dataset. Projects with very few instances (e.g., Collections) showed larger performance variations.
  • Bug Type: The model performs better on higher-order mutants than on real bugs from Defects4J, potentially due to the limited nature of mutation operators compared to real-world bug complexity. The authors suggest including more real bugs in the training data.
  • Out-of-Distribution (OOD) Problem: Performance drops on unseen projects are attributed to OOD issues, particularly when project vocabularies have low overlap.
  • Future Work:
    • Applying SEER's learned representations to other software analysis tasks like vulnerability detection, bug localization, and program repair.
  • Extending SEER to handle system tests, which are more complex than unit tests, potentially requiring architectures like Graph Neural Networks (GNNs).

Summary updated

Abstract

Automation of test oracles is one of the most challenging facets of software testing, but remains comparatively less addressed compared to automated test input generation. Test oracles rely on a ground-truth that can distinguish between the correct and buggy behavior to determine whether a test fails (detects a bug) or passes. What makes the oracle problem challenging and undecidable is the assumption that the ground-truth should know the exact expected, correct, or buggy behavior. However, we argue that one can still build an accurate oracle without knowing the exact correct or buggy behavior, but how these two might differ. This paper presents , a learning-based approach that in the absence of test assertions or other types of oracle, can determine whether a unit test passes or fails on a given method under test (MUT). To build the ground-truth, jointly embeds unit tests and the implementation of MUTs into a unified vector space, in such a way that the neural representation of tests are similar to that of MUTs they pass on them, but dissimilar to MUTs they fail on them. The classifier built on top of this vector representation serves as the oracle to generate “fail” labels, when test inputs detect a bug in MUT or “pass” labels, otherwise. Our extensive experiments on applying to more than 5K unit tests from a diverse set of open-source Java projects show that the produced oracle is (1) effective in predicting the fail or pass labels, achieving an overall accuracy, precision, recall, and F1 measure of 93%, 86%, 94%, and 90%, (2) generalizable, predicting the labels for the unit test of projects that were not in training or validation set with negligible performance drop, and (3) efficient, detecting the existence of bugs in only 6.5 milliseconds on average. Moreover, by interpreting the neural model and looking at it beyond a closed-box solution, we confirm that the oracle is valid, i.e., it predicts the labels through learning relevant features.
BibTeX
@inproceedings{ibrahimzada2022perfect,
  author = {Ali Reza Ibrahimzada and Yigit Varli and Dilara Tekinoglu and Reyhaneh Jabbarvand},
  title = {{Perfect is the enemy of test oracle}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2022},
  url = {https://openreview.net/forum?id=KH8Pqth8WD},
}
Figure