TL;DR
This paper explores a novel approach to assess the quality of software test suites by inferring a model from the test suite and comparing it to the system under test. They found that this model-based approach can correlate with traditional mutation testing, suggesting a potential for more efficient test suite evaluation.
What Problem Does This Paper Address?
Determining when a software test suite is "good enough" is a fundamental challenge in software engineering. Traditional methods like mutation testing, while effective, can be computationally expensive. This paper investigates an alternative: using machine learning to build a model of the system under test (SUT) from the test suite itself. The core idea is that if the inferred model closely matches the SUT's behavior, the test suite likely covers the SUT adequately, implying it's good at finding bugs. The authors aim to quantify this relationship by comparing this model-inference-based adequacy measure with the well-established mutation score.
Methods
The authors propose a model inference-based adequacy assessment. They take a test suite and split it into two parts: one for inferring a model (TSdt) and another for evaluating the inferred model's similarity to the SUT (TSequiv). They use decision trees, specifically the C4.5 algorithm, to learn a model from TSdt. The similarity between the inferred model and the SUT is then measured using the Root Mean Squared Error (RMSE) between their outputs when run on TSequiv. A lower RMSE indicates higher similarity and thus better test suite adequacy.
To evaluate this approach, they compare the RMSE with the mutation score, a standard metric where a higher score means the test suite kills more "mutants" (faulty versions of the SUT). They use the Pearson Correlation coefficient to quantify the linear relationship between these two metrics.
Datasets
The authors evaluated their approach on six Java programs:
- TCAS: A traffic collision avoidance system.
- BMI: A body mass index calculator.
- Triangle: A program to classify triangles.
- POP3: A state machine example.
- CAS: A car alarm system state machine.
- UTF8: A part of Google's Guava library for UTF8 encoding validation.
For these examples, they used existing test suites and mutants where available, and generated new test cases and mutants for others. They created 100 random subsets of test suites (TSdt) for each program to perform their evaluation.
Key Insights and Ideas
- Model Inference as a Proxy for Adequacy: The core idea that a learned model's fidelity to the SUT can indicate test suite quality is a significant departure from traditional coverage or mutation-based methods.
- Input Type Matters: The correlation between mutation score and model inference adequacy appears to be heavily influenced by the type of input the SUT handles. Continuous input types led to weaker correlations, while enumerated input types (especially when combined with state information) showed stronger correlations.
- State Information is Crucial: For stateful systems (like POP3 and CAS), including information about the system's state and previous outputs in the test cases significantly improved the correlation. This suggests that model inference is more effective when it can capture the dynamic behavior of a system.
Key Results
The study found varying degrees of correlation between mutation score and the model inference-based adequacy assessment across the different examples:
- Weak Correlation: TCAS, Triangle, BMI, and UTF8 exhibited weak correlations (Pearson r values around 0.2-0.3). This suggests that for systems with continuous inputs and without explicit state information in test cases, model inference alone might not be a reliable substitute for mutation score.
- Strong Correlation: POP3 showed a strong negative correlation (r = -0.632), and CAS showed a very strong negative correlation (r = -0.871). This indicates that for these stateful systems with enumerated inputs, the model inference approach aligns well with mutation testing. The negative correlation is expected, as a higher mutation score (better test suite) should correspond to a lower RMSE (better model fit).
Limitations and Future Work
The authors acknowledge that the correlation is not universally strong across all examples. They attribute this to the nature of the input types (continuous vs. enumerated) and the availability of state information in the test cases.
Future work includes:
- Investigating real-world examples to further validate the approach.
- Exploring linear correlations with various coverage assessment methods.
- Applying different machine learning methods for model inference and other similarity measures.
- Understanding when model inference methods (input/output based) are preferable to source-code modification-based methods.
Summary updated