metamorphic testing

Metamorphic testing is a software testing technique that tests programs using input transformations and expected output relationships — instead of requiring a test oracle that knows the correct output for each input, metamorphic testing checks whether related inputs produce appropriately related outputs, based on metamorphic relations.

The Oracle Problem

Traditional Testing: Requires knowing the expected output for each input — the "oracle problem."
Challenge: For many programs, determining correct output is difficult or impossible.
Example: Search engines — what is the "correct" ranking for a query?
Example: Machine learning models — what is the "correct" prediction?
Example: Scientific simulations — correct output may be unknown.

Metamorphic Testing Solution

Key Idea: Instead of checking absolute correctness, check relationships between inputs and outputs.
Metamorphic Relation (MR): A property that relates multiple executions of the program.
If input is transformed in a certain way, output should transform in a predictable way.
Example: `sin(x) = -sin(-x)` — sine is an odd function.

How Metamorphic Testing Works

1. Identify Metamorphic Relations: Determine properties that should hold for the program.

2. Generate Source Input: Create an initial test input.

3. Execute Program: Run program on source input, get source output.

4. Transform Input: Apply transformation to create follow-up input.

5. Execute Again: Run program on follow-up input, get follow-up output.

6. Check Relation: Verify that source and follow-up outputs satisfy the metamorphic relation.

7. Report Violation: If relation is violated, a bug is detected.

Example: Testing a Search Engine

# Metamorphic Relation: Adding a document containing the query
# should not decrease the number of results.

# Source test:
query = "machine learning"
results1 = search_engine.search(query)
count1 = len(results1)

# Follow-up test:
# Add a new document containing "machine learning"
search_engine.add_document("New ML paper about machine learning")
results2 = search_engine.search(query)
count2 = len(results2)

# Check metamorphic relation:
assert count2 >= count1, "Adding relevant document decreased results!"
# If this fails, bug detected!

Common Metamorphic Relations

Permutation: Changing input order shouldn't affect output (for commutative operations).
`sort([3,1,2]) == sort([1,2,3])`

Addition: Adding elements should increase or maintain output.
`sum([1,2,3,4]) > sum([1,2,3])`

Scaling: Scaling input should scale output proportionally.
`f(2*x) == 2*f(x)` for linear functions

Symmetry: Symmetric transformations should produce symmetric outputs.
`sin(-x) == -sin(x)`

Consistency: Multiple paths to the same result should agree.
`(a + b) + c == a + (b + c)`

Inverse: Applying inverse operation should return to original.
`decrypt(encrypt(x)) == x`

Example: Testing a Sorting Function

def test_sort_metamorphic():
    # Source input:
    source = [5, 2, 8, 1, 9]
    source_output = sort(source)
    
    # MR1: Permutation invariance
    # Shuffling input shouldn't change sorted output
    follow_up1 = [1, 9, 2, 5, 8]  # Same elements, different order
    follow_up_output1 = sort(follow_up1)
    assert source_output == follow_up_output1
    
    # MR2: Adding element
    # Adding an element should result in sorted list containing that element
    follow_up2 = source + [3]
    follow_up_output2 = sort(follow_up2)
    assert 3 in follow_up_output2
    assert len(follow_up_output2) == len(source) + 1
    
    # MR3: Removing element
    # Removing an element should result in sorted list without that element
    follow_up3 = [x for x in source if x != 5]
    follow_up_output3 = sort(follow_up3)
    assert 5 not in follow_up_output3

Applications

Machine Learning: Test ML models without knowing correct predictions.
MR: Slightly perturbing input shouldn't drastically change prediction.
MR: Adding irrelevant features shouldn't change prediction.

Scientific Computing: Test simulations without knowing exact results.
MR: Doubling all masses in physics simulation should produce predictable changes.

Compilers: Test without knowing exact assembly output.
MR: Optimized and unoptimized code should produce same results.

Search Engines: Test without knowing ideal rankings.
MR: Adding relevant documents shouldn't decrease result count.

Image Processing: Test filters and transformations.
MR: Applying filter twice should equal applying stronger filter once (for some filters).

Metamorphic Testing with LLMs

Relation Discovery: LLMs can suggest metamorphic relations for a given program.
Test Generation: LLMs generate source inputs and appropriate transformations.
Violation Analysis: LLMs analyze metamorphic relation violations to identify bugs.
Relation Validation: LLMs verify that proposed metamorphic relations are valid.

Benefits

No Oracle Required: Solves the oracle problem — don't need to know correct outputs.
Applicable to Complex Systems: Works for programs where correct behavior is hard to specify.
Finds Real Bugs: Metamorphic relation violations indicate actual bugs.
Complements Traditional Testing: Can be used alongside oracle-based testing.

Challenges

Identifying Relations: Finding good metamorphic relations requires domain knowledge and creativity.
Weak Relations: Some relations are too weak — satisfied even by buggy programs.
False Positives: Some violations may be due to floating-point precision or acceptable differences.
Computational Cost: Requires multiple executions per test — more expensive than single-execution tests.

Evaluation

Effectiveness: How many bugs does metamorphic testing find?
Efficiency: How many tests are needed to find bugs?
Relation Quality: Are the metamorphic relations strong enough to detect bugs?

Metamorphic testing is a powerful technique for testing programs without test oracles — it enables testing of complex systems like machine learning models, search engines, and scientific simulations where determining correct output is difficult or impossible.

metamorphic testing

Go deeper with CFSGPT