TL;DR
This paper introduces Metamorphic Runtime Checking (MRC), a novel technique for testing software that lacks traditional test oracles. By automatically checking metamorphic properties of individual functions during program execution, MRC significantly improves defect detection compared to previous system-level metamorphic testing approaches, with minimal performance overhead.
What Problem Does This Paper Address?
Many software applications, particularly in fields like scientific computing, optimization, and machine learning, are notoriously difficult to test because they lack "test oracles." A test oracle is essentially a known correct answer for a given input, allowing us to verify if the program's output is right. When such oracles are unavailable or impractical to create, ensuring software quality becomes a major challenge. Traditional testing methods fall short, leaving a gap in our ability to guarantee the reliability of these "non-testable programs."
Methods
The core innovation is Metamorphic Runtime Checking (MRC). Unlike previous metamorphic testing approaches that focused on the entire application, MRC targets individual functions. Here's how it works:
- Metamorphic Properties: These are relationships between inputs and outputs that should hold true for a function. For example, if a function calculates the standard deviation of a list, permuting the list's elements shouldn't change the output.
- Runtime Execution: MRC instruments the code so that when a function is called with an input
xproducing outputf(x), a corresponding metamorphic test is triggered. - Transformation and Prediction: The test uses a predefined metamorphic property to transform the input
xinto a new inputt(x). Based onf(x), the test can then predict whatf(t(x))should be. - Sandbox Execution: To avoid affecting the main program's state or user experience, the metamorphic tests run in a separate, isolated "sandbox" process. This ensures that any modifications made by the test are not visible to the original application.
- Columbus Framework: The authors developed a framework called Columbus to support MRC. It handles test creation, instrumentation, and runtime execution, ensuring minimal performance impact and seamless integration into the deployment environment.
Datasets
The empirical studies used four real-world "non-testable programs" from the machine learning domain:
- Support Vector Machines (SVM): Implemented in Weka.
- C4.5: A decision tree algorithm.
- MartiRank: A ranking algorithm for predicting electrical device failures.
- PAYL: An anomaly-based intrusion detection system.
These applications were subjected to mutation testing to systematically introduce defects. The "gold standard" for comparison was the original, defect-free version of each application.
Key Insights and Ideas
- Function-Level vs. System-Level Testing: The most significant insight is that testing individual functions using metamorphic properties is substantially more effective than testing the entire system's properties. This is because function-level tests can pinpoint defects more precisely and can even detect issues that manifest as invalid states affecting other parts of the system.
- Detecting "Invisible" Defects: MRC can uncover defects that are not directly within the tested function but rather in other parts of the system that create an invalid state. These invalid states can cause metamorphic properties of otherwise correct functions to be violated, thus revealing the underlying issue.
- Real-World Testing: The ability to run tests in the deployment environment using actual user inputs provides a much more realistic and comprehensive testing scenario than lab-based testing.
- Pseudo-Oracle Power: Metamorphic properties act as built-in pseudo-oracles, eliminating the need for external, pre-defined correct outputs.
Key Results
- 30% Improvement in Defect Detection: Across the tested applications, MRC detected 189 out of 222 defects, a 30% improvement over the previous system-level metamorphic testing approach (which detected 145 defects).
- No Missed Defects: All defects detected by the system-level approach were also detected by MRC.
- Minimal Performance Overhead: The performance overhead was measured to be around 5.5ms per test for Java applications and 1.5ms per test for C applications. This overhead is largely attributed to the sandbox creation and process forking.
- PAYL Success: MRC showed a dramatic improvement in detecting defects in PAYL, going from 2 defects detected by system-level testing to 29 defects detected by MRC. This was attributed to the ability to test properties involving data manipulation within the application, which was restricted in the system-level approach.
Limitations and Future Work
- External State: The current sandbox implementation does not fully isolate external states like database tables or network I/O. Future work involves integrating with OS virtualization layers to address this.
- Test Function Timing: Tests are executed after the original function call. This could potentially lead to false positives if the original function call alters the system state in a way that invalidates the metamorphic property by the time the test runs.
- Function Granularity: Testing very large functions can be challenging due to the complexity of defining and checking their metamorphic properties. Future work may explore instrumenting code at arbitrary points, not just function entry.
- Automatic Property Discovery: The authors suggest future research into automatically discovering metamorphic properties, which would further enhance the technique's usability.
- Non-Determinism: The current framework is primarily for deterministic applications. Incorporating techniques for non-deterministic systems is a future direction.
Summary updated