Automatic identification of common and special object-oriented unit tests

Tao XieOOPSLA Companion 2004 · DOI

TL;DR

This paper introduces a novel method for automatically identifying "special" and "common" unit tests from automatically generated test suites, without requiring explicit specifications. By inferring statistical algebraic abstractions of program behavior, the approach helps developers pinpoint critical test cases that exercise unusual or typical program execution paths, aiding in debugging and understanding.

What Problem Does This Paper Address?

Writing comprehensive unit tests for software is crucial for ensuring quality, but it's a challenging task. Programmers often overlook edge cases or boundary conditions, leading to incomplete test suites. While automatic test generation tools can create a large number of tests, manually inspecting and verifying the outputs of these tests to identify important ones is impractical. Existing approaches often rely on formal specifications, which are rarely available in practice. This paper addresses the gap of automatically identifying meaningful unit tests (both those that exercise typical behavior and those that probe unusual or boundary conditions) from automatically generated tests, without needing pre-existing specifications.

Methods

The core of the paper's approach lies in inferring "statistical algebraic abstractions." These are essentially equations that describe program runtime behavior, inspired by axioms in algebraic specifications. Unlike traditional abstractions that must hold universally, these statistical abstractions are associated with counts of satisfying and violating instances observed during test executions.

The process involves:

  1. Test Generation: Generating a diverse set of test inputs for the class under test.
  2. Method-Call Composition: Monitoring and composing sequences of method calls to capture program interactions.
  3. Statistical Inference: Instantiating predefined "abstraction templates" with these method call sequences and checking them against the templates. This step identifies potential common or universal properties.
  4. Test Identification: Classifying properties as "common" (mostly satisfying instances) or "universal" (all satisfying instances). Special tests are then identified as violating instances of common properties, while common tests are satisfying instances of either common or universal properties. The approach then samples representative special and common tests for each identified property.

Datasets

The paper evaluates its approach on several complex data structure benchmarks from the Java Collections Framework, including BinSearchTree, BinomialHeap, FibonacciHeap, HashMap, HashSet, LinkedList, SortedList, TreeMap, IntStack, and UBStack. These benchmarks were previously used for evaluating redundant-test detection techniques.

Key Insights and Ideas

  • Bridging the Specification Gap: The most significant insight is the ability to identify meaningful tests without formal specifications, a common hurdle in practical software development.
  • Statistical vs. Universal Properties: Differentiating between "common" and "universal" properties provides a nuanced understanding of program behavior, allowing for the identification of both typical and exceptional execution paths.
  • Sampling for Inspectability: Instead of overwhelming developers with all generated tests, the approach intelligently samples representative special and common tests associated with specific inferred properties, making inspection more manageable.
  • Conditional Properties: The identification of conditional universal properties highlights specific interaction patterns that are important but only under certain conditions, offering deeper insights into program logic.

Key Results

The evaluation on various Java data structures demonstrated the effectiveness of the approach. For instance, on the LinkedList benchmark, the approach automatically generated 6777 tests and identified 29 special tests and 79 common tests, associated with 43 universal and 45 common properties. The number of identified special and common tests remained relatively manageable even for large benchmarks. The authors observed that increasing the maximum iteration number (leading to more tests) could falsify universal properties but also increase or decrease conditional and common properties, indicating the dynamic nature of inferred abstractions.

Limitations and Future Work

The authors acknowledge that it's still unclear how well the identified tests can detect faults. Future work includes:

  • Assessing the fault-detection capability of the identified tests by comparing them against all generated tests or tests selected by other methods.
  • Using universal or conditional universal properties to guide the generation of a more focused set of tests, rather than relying on a bounded exhaustive set.

Summary updated

BibTeX
@inproceedings{xie2004automatic,
  author = {Tao Xie},
  title = {{Automatic identification of common and special object-oriented unit tests}},
  booktitle = {OOPSLA Companion},
  year = {2004},
  doi = {10.1145/1028664.1028785},
}
Figure