💻 computer science

MR-Scout: Automated Synthesis of Metamorphic Relations from Existing Test Cases

This paper presents MR-Scout, an automated approach that synthesizes high-quality metamorphic relations from existing developer-written test cases in open-source projects to alleviate the oracle problem and significantly enhance test coverage and mutation scores.

Original authors: Congying Xu, Valerio Terragni, Hengcheng Zhu, Jiarong Wu, Shing-Chi Cheung

Published 2026-04-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Congying Xu, Valerio Terragni, Hengcheng Zhu, Jiarong Wu, Shing-Chi Cheung

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to teach a robot how to cook. You want the robot to taste a dish and say, "This is delicious!" But there's a problem: the robot doesn't have a human palate. It doesn't know what "delicious" tastes like. This is the "Oracle Problem" in software testing: how do you know if a computer program is working correctly if you don't know what the right answer should be?

Enter Metamorphic Testing (MT). Instead of asking, "Is this specific cake perfect?", MT asks, "If I double the sugar, does the cake get sweeter?" It checks for relationships between inputs and outputs. If you add sugar and the cake doesn't get sweeter, something is wrong. These relationships are called Metamorphic Relations (MRs).

The problem? Designing these relationships is hard. It requires deep knowledge of the specific domain (like knowing exactly how sugar affects baking). This is why many companies don't use this powerful testing method.

Enter MR-Scout: The "Recipe Detective"

The researchers behind this paper, MR-Scout, had a brilliant idea: The answers are already hiding in the code.

Think of software developers as chefs who have already written thousands of recipes (test cases). Even if they didn't write them specifically to teach the robot about relationships, their recipes often contain those relationships implicitly.

Example: A developer writes a test to check if a text font gets wider when you make it bold. They don't explicitly say, "Bold text must be wider." But by writing the code to check it, they have encoded that rule.

MR-Scout is a tool that acts like a super-smart detective. It scans thousands of open-source software projects, finds these hidden "relationship recipes," and turns them into a universal language that robots can use to test any similar program.

Here is how MR-Scout works, broken down into three simple steps:

1. The Detective Work (Discovery)

MR-Scout scans through millions of lines of code looking for specific patterns. It's like looking for a specific type of clue in a haystack.

The Clue: It looks for test cases that do two things:
1. They run a function twice with different inputs (e.g., "Text A" and "Bold Text A").
2. They check if there is a logical connection between the results (e.g., "Is the width of Bold Text A greater than Text A?").
The Result: It found over 11,000 of these hidden relationship clues in 701 different software projects!

2. The Translator (Synthesis)

Just finding the clue isn't enough; the robot needs to understand it. The original code is often messy and tied to specific variables (like the word "wow").

The Magic: MR-Scout takes that messy code and "codifies" it. It strips away the specific details and turns it into a parameterized method (a reusable template).
The Analogy: Imagine taking a specific recipe for "Grandma's Apple Pie" and turning it into a generic "Apple Pie Generator." Now, you can feed it any apples, and it will tell you if the result makes sense.
The Output: It creates a "Codified MR"—a clean, reusable rule that says, "If you do X, then Y must happen," which can be applied to new, random inputs.

3. The Quality Control (Filtering)

Not every rule found is perfect. Some might be too specific or break when you try to use them with new data.

The Test: MR-Scout takes these new rules and throws thousands of random inputs at them (using a tool called EvoSuite).
The Filter: If a rule works 95% of the time, it's a keeper. If it breaks too often, it's thrown out. This ensures only the high-quality, reliable rules make it to the final list.

Why Does This Matter? (The Results)

The researchers tested MR-Scout and found some amazing things:

It's Accurate: 97% of the rules it found were actually correct relationships.
It's Useful: When they used these new rules to test software, they found 13.5% more bugs (in terms of code coverage) and 9.4% more errors (mutation score) than the developers' original tests alone.
It's Understandable: When human developers looked at these synthesized rules, about 60-75% of them said, "Oh, I get that! That makes sense."

The Big Picture

Think of MR-Scout as a time machine for software quality.

Before: Developers had to manually invent complex rules for every new program, which was slow and error-prone.
Now: MR-Scout looks at what developers have already built, extracts the hidden wisdom, and repackages it so that automated tools can find bugs faster and more effectively.

It turns the "implicit knowledge" of millions of developers into an "explicit superpower" for automated testing, making software safer and more reliable without requiring humans to write every single rule from scratch.

1. Problem Statement

The Oracle Problem in Automated Testing:
Automated test input generation has advanced significantly, but constructing test oracles (mechanisms to determine if a test passes or fails) remains a major bottleneck. Without a clear expected output, automated testing cannot verify correctness.

Limitations of Metamorphic Testing (MT):
Metamorphic Testing (MT) addresses the oracle problem by defining Metamorphic Relations (MRs). An MR is a property relating multiple inputs and their corresponding outputs (e.g., if input $x$ is transformed to $x'$ , then output $f(x)$ and $f(x')$ must satisfy a specific relation).

Challenge: Designing MRs requires deep domain-specific knowledge and manual effort, hindering the widespread adoption of MT.
Gap: Existing approaches to infer MRs (e.g., from specifications or using ML) often lack automation, rely on specific domains (like numerical programs), or require pre-defined patterns.
Observation: Developers often write test cases that implicitly encode domain knowledge and MRs, even if they are not explicitly designed for MT. These "MR-encoded test cases" (MTCs) are currently underutilized.

2. Methodology: MR-Scout

The authors propose MR-Scout, an automated approach to discover, synthesize, and filter MRs from existing open-source software (OSS) test cases. The process consists of three phases:

Phase 1: MTC Discovery

MR-Scout statically analyzes test cases to identify those that implicitly encode MRs. It relies on two derived properties:

P1 (Method Invocations): The test case must contain at least two invocations of methods from the same class (the Class Under Test) with distinct inputs.
P2 (Relation Assertion): The test case must contain at least one assertion that validates a relation between the inputs and/or outputs of these invocations.

Mechanism: The tool filters out external library calls, identifies internal classes with $\ge$ 2 method calls, and scans for assertions matching specific patterns (e.g., assertTrue with numerical operators, assertEquals comparing outputs).
Output: A set of MR-encoded Test Cases (MTCs).

Phase 2: MR Synthesis

Once MTCs are identified, MR-Scout synthesizes them into Codified MRs (parameterized methods) suitable for automated test generation.

Deduction: It identifies the Source Input, Follow-up Input, Input Transformation (how the follow-up input is derived from the source), and the Output Relation.
Codification: The tool transforms the specific test case into a generic, parameterized method.
- Hard-coded source inputs are replaced with parameters.
- Irrelevant assertions (specific to original values) are removed.
- The resulting method encapsulates the input transformation, execution of source/follow-up inputs, and the output relation check.
Constraint: This phase focuses on MR instances involving exactly two method invocations with an explicit input transformation.

Phase 3: MR Filtering

To ensure the synthesized MRs are practical, MR-Scout filters out low-quality candidates.

Process: It uses EvoSuite to generate new, random test inputs for the codified MRs.
Criterion: An MR is considered "high quality" if it passes (does not trigger a false alarm) on at least 95% of valid generated inputs.
Validity Check: An input is deemed valid if it does not trigger exceptions during the input transformation or method execution.
Output: A final set of high-quality, applicable Codified MRs.

3. Key Contributions

MR-Scout Tool: The first approach to automatically synthesize MRs from existing developer-written test cases in OSS projects.
Large-Scale Dataset: Discovery and release of over 11,000 MTCs from 701 OSS projects, serving as a resource for future research in MR discovery and automated testing.
Comprehensive Evaluation: Extensive experiments evaluating the precision of discovery, the quality of synthesized MRs, their usefulness in improving test adequacy, and their comprehensibility to developers.
Open Source: Release of the tool, datasets, and experimental artifacts to facilitate reproducibility.

4. Experimental Results

The authors evaluated MR-Scout using 701 Java projects (4,068 projects with tests, 701 containing MTCs).

RQ1: Precision of Discovery:
- MR-Scout discovered 11,350 MTCs.
- Manual validation of 164 random samples showed a 97% precision rate (True Positives). False positives were primarily due to complex variable re-assignments confusing the static analysis.
RQ2: Quality of Synthesized MRs:
- After filtering, 97.18% of the synthesized Codified MRs were of high quality (applicable to new inputs without false alarms).
- This demonstrates the effectiveness of the filtering phase in removing brittle relations.
RQ3: Usefulness (Test Adequacy):
- Codified MRs were integrated with developer-written and EvoSuite-generated test suites.
- Line Coverage: Increased by 13.52% over developer-written tests.
- Mutation Score: Increased by 9.42% over developer-written tests and 82.8% over EvoSuite-generated tests alone.
- This proves that synthesized MRs effectively complement existing tests by providing high-quality oracles for diverse inputs.
RQ4: Comprehensibility:
- A qualitative study with 5 expert developers showed that 55.76% to 76.92% of the synthesized MRs were rated as "easy" or "very easy" to understand.
- This suggests the synthesized MRs are practical for test maintenance and migration.

5. Significance and Impact

Bridging the Gap: MR-Scout bridges the gap between the theoretical power of Metamorphic Testing and the practical difficulty of defining MRs. It leverages the "latent" domain knowledge already present in existing codebases.
Automation: It significantly reduces the manual effort required to define oracles, enabling more effective automated test generation.
Enhanced Testing: By combining the diverse inputs of automated generators (like EvoSuite) with the high-quality oracles of synthesized MRs, it significantly improves fault detection capabilities (mutation score) and code coverage.
Resource Creation: The release of a massive dataset of 11,000+ MTCs provides a foundational resource for the research community to further explore MR inference and automated testing strategies.

Limitations Noted:

Currently limited to MRs with exactly two method invocations.
Relies on static analysis, which can be imprecise with complex control flows or dynamic features.
Filtering depends on the ability of EvoSuite to generate valid complex objects, which can be a bottleneck for highly constrained classes.