TL;DR
This paper introduces a novel approach to regression testing that specifically targets "change interaction errors" (CIEs) – subtle bugs arising from the complex interplay of multiple code changes. By constructing a "change sequence graph" (CSG) and using directed symbolic execution, they significantly improve the detection of these hard-to-find errors, even in well-tested software.
What Problem Does This Paper Address?
Software evolution, through feature additions and bug fixes, inevitably introduces errors. While traditional regression testing aims to catch these, a significant class of bugs, termed "change interaction errors" (CIEs), remain elusive. These errors don't stem from a single faulty change but from how multiple, seemingly independent changes interact in unexpected ways. The authors highlight that in the GNU Coreutils project, a substantial portion of long-standing regressions (taking over two years to fix) are CIEs, despite extensive testing. Existing regression testing methods often focus on individual changes or general code coverage, failing to adequately stress the complex dependencies that lead to CIEs.
Methods
The core of the paper's contribution lies in its novel test generation technique.
- Change Sequence Graph (CSG): The authors first identify changed statements between two program versions using
diff. They then construct a CSG, which is a graph that captures: - Control-flow: How execution can flow between changed statements.
- Potential Interaction Locations: Points in the code where multiple changed statements can semantically influence the outcome. These are identified using program dependency graphs (PDGs) and backward slices.
- Directed Symbolic Execution: The CSG serves as a guide for a modified symbolic execution engine (Otter). Instead of exploring arbitrary paths or aiming for simple coverage, the symbolic execution is directed by the CSG. This means the engine specifically targets sequences of changed statements and potential interaction locations identified in the graph. The goal is to generate test inputs that exercise these critical sequences, thereby exposing CIEs.
Datasets
The primary dataset used for evaluation is the GNU Coreutils project. The authors analyzed its version history, focusing on pairs of versions that introduced differential errors. They specifically selected regressions involving multiple changed statements to align with their focus on change interactions. They also mention using the cut utility as a running example to illustrate their concepts.
Key Insights and Ideas
- CIEs are Pervasive and Undetected: The study on GNU Coreutils reveals that a significant fraction of regressions are CIEs, and they persist for years despite robust testing. This underscores the inadequacy of current regression testing approaches for this specific error class.
- Interactions, Not Just Changes, Matter: The paper strongly argues that treating changes in isolation is insufficient. The interplay between changes is the critical factor in exposing CIEs.
- CSG as a Roadmap for Bugs: The CSG provides a structured way to represent potential CIE-inducing execution paths, guiding test generation towards the most likely error-prone sequences.
- Symbolic Execution Needs Direction: Standard symbolic execution can be inefficient. Directing it with a CSG dramatically improves its ability to find specific, hard-to-reach bugs like CIEs.
- Critical Sequences are Rare but Potent: While test cases exercising critical sequences are infrequent (around 21.7% on average), they are significantly more likely (15.6 times) to expose an error compared to non-critical sequences.
Key Results
- High CIE Prevalence: Two-thirds of the analyzed differential errors were classified as change interaction errors.
- Improved Detection Rate: The CSG-guided approach exposed 100% of the change interaction errors in their experiments, whereas testing changes in isolation only exposed about 57%.
- Efficiency: On average, the CSG-guided approach generated 227 test cases per version pair, with every fourth test case revealing a difference and every fifth revealing a differential error.
- Novel Errors Found: The authors successfully identified five previously unknown regression errors in the GNU Coreutils utilities.
- Critical Sequences are Highly Effective: Test cases exercising critical sequences were 15.6 times more likely to expose an error than those exercising non-critical sequences.
Limitations and Future Work
- Threats to Validity:
- External Validity: The generalization of results might be limited by the specific nature of the GNU Coreutils project and the focus on deterministic behavior. Some errors might be environment-dependent, which was not modeled.
- Internal Validity: The effectiveness of the search strategy used in symbolic execution could influence results. Additionally, the practical absence of explicit assertions in some code (like buffer overflows) can hinder symbolic execution's ability to detect errors without specific instrumentation.
- Future Work: The authors suggest exploring more sophisticated search strategies for symbolic execution and incorporating environmental modeling. They also acknowledge the need for better ways to handle non-determinism and the potential for more precise definitions of change interaction.
Summary updated