TL;DR
This paper introduces RETEST, a novel, safe regression test selection technique specifically designed for Java. It addresses the challenge of efficiently selecting relevant test cases for modified Java software, even when dealing with incomplete programs and external libraries, by employing a sophisticated graph representation and traversal algorithm.
What Problem Does This Paper Address?
When software is modified, regression testing is crucial to ensure that the changes haven't introduced new bugs or broken existing functionality. However, rerunning the entire test suite can be prohibitively time-consuming and expensive. Regression test selection aims to mitigate this by identifying a subset of test cases that are likely to detect faults in the modified software. The challenge lies in developing safe selection techniques that guarantee no faults will be missed, while still achieving significant reductions in the test suite size. Existing techniques often struggle with the complexities of object-oriented languages like Java, particularly features like polymorphism, dynamic binding, and exception handling, and may require analysis of external libraries, which is often impractical. This paper tackles the problem of creating a safe, precise, and efficient regression test selection technique for Java that can handle these complexities and work with incomplete programs.
Methods
The core of this paper is the Java Interclass Graph (JIG), a novel graph representation designed to capture Java's object-oriented features. Unlike simpler control-flow graphs (CFGs), the JIG incorporates:
- Variable and object type information: Pushing type information down to where variables are used for more precise analysis.
- Internal and external methods: Differentiating between code analyzed and code treated as a black box (like libraries).
- Interprocedural interactions: Modeling calls between methods, including virtual calls and exception handling.
- Globally-qualified class names: Encoding class hierarchies to precisely track changes.
- Exception handling: Representing try-catch-finally blocks and the flow of exceptions.
The technique then uses a graph traversal algorithm (similar to Rothermel and Harrold's but adapted for the JIG) to compare the JIGs of the original and modified programs. This traversal identifies "dangerous edges" – program constructs that, if changed, could lead to different behavior. A test case is selected if and only if it covers at least one of these dangerous edges.
The system, RETEST, implements this technique and includes:
- A Profiler to gather dynamic coverage information (e.g., method calls, class instantiations).
- A static analysis component (DejaVOO) that builds JIGs and identifies dangerous edges.
- An Adaptor to map dangerous edges to the coverage information collected by the profiler.
- A SelectTests component to choose the final test cases.
Datasets
The empirical studies were conducted on four Java software subjects:
- SIENA: An Internet-based event notification system.
- JEDIT: A text editor.
- JMETER: A web application testing tool.
- REGEXP: A regular-expression library.
These subjects represent a range of application types and sizes. The paper notes that for SIENA, they added test cases to increase method coverage.
Key Insights and Ideas
- JIG is key for Java: The paper demonstrates that a specialized graph representation is essential to accurately model Java's object-oriented features, which simpler CFGs cannot capture effectively.
- Handling incomplete programs is practical: The ability to treat external libraries as black boxes (using collapsed CFGs) is a significant advantage, as analyzing all dependencies is often infeasible in real-world Java development.
- Precision matters for reduction: While method-level selection is simpler, edge-level selection can offer further reductions in test suite size, especially when dangerous edges are not reached by all paths within a method.
- Safety is paramount: The technique is designed to be "safe," meaning it guarantees that no fault-revealing test cases are omitted, providing confidence in the regression testing process.
Key Results
The empirical studies using RETEST showed that the regression test selection technique can be effective in reducing the size of the test suite.
- Significant reduction: For the four subjects, the percentage of test cases selected varied widely, but often resulted in substantial savings. For example, some versions of SIENA required less than 2% of the original test cases, while others required up to 90%. JEDIT also showed significant variation, with some versions needing over 90% of tests and others less than 15%.
- Granularity impact: A study comparing method-level and edge-level selection for SIENA indicated that edge-level selection can lead to further reductions in test cases selected, though the benefit varies. For many versions, the results were similar, but for some, the difference was significant.
Limitations and Future Work
- Reflection: The technique assumes that reflection is not used within internal classes or components, as reflection can make static analysis more complex and less precise.
- Nondeterministic behavior: The assumption of deterministic test runs is crucial. For multithreaded programs with nondeterministic interactions, special execution environments are needed.
- Profiler limitations: The current RETEST profiler has limitations in capturing fine-grained coverage (e.g., statement-level, exception throws/catches), leading to potential imprecision in test selection.
- Future Work: The authors plan to:
- Investigate using the Java Virtual Machine Debug Interface (JVMDI) for more detailed profiling.
- Explore bytecode instrumentation tools (BIT, Soot, BCEL) for finer-grained coverage.
- Conduct studies with more diverse subjects to identify trends.
- Further evaluate the trade-offs between granularity, precision, and efficiency.
- Assess the technique's efficiency in practice.
Summary updated