Metamorphic testing¶

Metamorphic testing checks a program without knowing the right answer, by changing the input in a way whose effect on the output is predictable. That predictable effect is a metamorphic relation: sort(shuffle(x)) == sort(x), decode(encode(x)) == x, and f(2 * x) == 2 * f(x) for any linear f. The relation supplies the oracle, which is how the test reaches a verdict on code whose correct output nobody can compute — the oracle problem that classical example-based testing assumes away. Computing that output from scratch would replicate the system under test.

Formally, a metamorphic relation is a necessary property of the target algorithm over a sequence of two or more inputs ⟨x₁, …, xₙ⟩ (n ≥ 2) and their corresponding outputs (Chen et al. 2018)¹. The two or more is the crux: the relation holds across separate runs, which is what separates it from a single-run invariant that checks one output on its own.

What it catches¶

Round-trip violations. Encoder/decoder pairs that fail to preserve the input on a round trip. The single most-used metamorphic relation in practice; near-free when the implementation has a symmetric pair.
Optimization regressions. A SQL planner that returns different results from an equivalent query. SQLancer's PQS, NoREC, and TLP oracles are exactly this pattern.
Numerical regressions. Scale-invariance, linearity, monotonicity, symmetry checks for numerical code; the operator family where exact oracles are hardest to write.
ML model invariances. A face-recognition model whose accuracy shifts when inputs are rotated, translated, or recolored has a metamorphic violation. Such relations are a standard pseudo-oracle in testing ML systems.
Security invariants stated relationally. "Adding an unrelated field to the request must not change the authorization decision."

Metamorphic testing misses bugs where the relation is also wrong, and bugs that affect both sides of the comparison equally.

A catalog of metamorphic relations¶

Most metamorphic tests in practice specialize one of these families, grouped by what the relation says; many concrete tests combine two or three.

Identity and self-relations¶

Identity element — there exists e such that f(x, e) == x:

concat(xs, []) == xs
merge(d, {}) == d
x + 0 == x, x * 1 == x

Idempotence — applying twice equals applying once:

normalize(normalize(x)) == normalize(x)
dedup(dedup(xs)) == dedup(xs)
abs(abs(n)) == abs(n)

Determinism — f(x) == f(x) on a second call. Trivial to state, but it catches hidden non-determinism (clocks, random number generators, hash-table iteration order, garbage-collector interleavings):

serialize(x) == serialize(x)
query(db, q) == query(db, q) for a read-only q

Invariance under irrelevant change¶

Invariance — output should not change under the transformation:

sort(x) == sort(shuffle(x))
render(data) == render(copy(data))
auth(req) == auth(req + irrelevant_header)
compile(src) == compile(reformat(src)) for whitespace-equivalent reformat

Symmetry and order¶

Commutativity / permutation invariance — order doesn't matter:

f(a, b) == f(b, a)
sum(xs) == sum(reverse(xs))
union(s1, s2) == union(s2, s1)

Associativity — grouping doesn't matter:

(a * b) * c == a * (b * c) for any associative operation
concat(concat(a, b), c) == concat(a, concat(b, c))
max(max(a, b), c) == max(a, max(b, c))

Composition and inverses¶

Round-trip / inverse — encoder/decoder pairs and serializers:

decode(encode(x)) == x
parse(format(x)) == x
decompress(compress(x)) == x
decrypt(encrypt(x, k), k) == x

Composition — composing operations equals one combined operation:

interpret(optimize(p)) == interpret(p) an optimizer must preserve meaning
resize(resize(img, w/2), w/2) == resize(img, w/4) for ideal resampling

Arithmetic and algebraic¶

Scaling / linearity — applies to numerical and statistical code:

f(2 * x) == 2 * f(x) for any linear f
mean(c * xs) == c * mean(xs)
area(scale(shape, k)) == k * k * area(shape)

Distributivity — one operation distributes over another:

f(a + b) == f(a) + f(b) homomorphism over addition
(a + b) * c == a * c + b * c
set_of(concat(xs, ys)) == union(set_of(xs), set_of(ys))

Bounds (not metamorphic). Single-run output ranges (0 <= probability(x) <= 1, min(xs) <= mean(xs) <= max(xs), |x| <= sqrt(dot(x, x))) are invariants, not metamorphic relations: they judge one execution's output on its own (one input, n = 1), with no second related run to compare against. A bound across runs — price(items + more) >= price(items) — is metamorphic.

Triangle inequality — for any distance metric d:

d(a, c) <= d(a, b) + d(b, c)
levenshtein(a, c) <= levenshtein(a, b) + levenshtein(b, c)

Ordering¶

Monotonicity — output changes in a predictable direction:

price(items + more_items) >= price(items)
|search_results(query + filter)| <= |search_results(query)| ( $\text{results}(q + f) \subseteq \text{results}(q)$ )

Conservation¶

Cardinality preservation — size doesn't change:

|sort(xs)| == |xs|
|map(f, xs)| == |xs|
|reverse(xs)| == |xs|

Sum / mass conservation — partitioning preserves the total:

sum(xs) == sum(filter(p, xs)) + sum(filter(not p, xs))
sum(count_by_partition(xs)) == |xs|
total_debits == total_credits (double-entry accounting)

Laws of a typed abstraction (monoid, functor, monad)¶

Whole law-sets, not single relations: a law-set bundles several of these relations into the named contract a typed abstraction must satisfy. A type that satisfies the whole set implements the abstraction correctly.

Monoid laws — identity + associativity. Verify both for any type with mempty and <> (Haskell), Identity and combine (Scala), etc.
Functor laws — fmap id == id, fmap (f . g) == fmap f . fmap g.
Monad laws — left identity, right identity, associativity of bind.

Heuristic¶

Pick a relation that holds by definition of the operation, not one that holds by accident on the inputs you happen to be using. A failing metamorphic test is much more often a bug in the relation than a bug in the implementation — write the relation the way a domain expert would phrase the invariant, not the way the code does.

Tools¶

Property-based testing frameworks (host the relation as a property)¶

Hypothesis (Python), fast-check (TypeScript), proptest (Rust), QuickCheck (Haskell), PropEr (Erlang/Elixir), jqwik (Java), FsCheck (.NET). Any PBT framework hosts metamorphic relations directly — the test body is "transform the input, transform the expected output, assert they still match."

Database-specific oracles¶

SQLancer (Rigger and Su 2020)² — three named metamorphic oracles:
- PQS (Pivoted Query Synthesis) — pick a row, build a query guaranteed to return it, file a bug if it doesn't.
- NoREC (Non-Optimizing Reference Engine Construction) — rewrite the query to defeat the optimizer; results must match.
- TLP (Ternary Logic Partitioning) — split the result space into TRUE/FALSE/NULL partitions; union must equal the unsplit query.

ML-specific harnesses¶

No dedicated harness exists; published approaches pair Hypothesis-style generators with a domain-specific transformation library (image rotation, audio time-stretch, text paraphrase).

General-purpose¶

AFL++, libFuzzer, Atheris — fuzzers run metamorphic oracles by encoding "the transformation broke the relation" as the crash condition. Common pattern for crypto and parsers.

When to use, when not¶

Use:

You can state a relation but not a closed-form expected output. Image processing, ML inference, scientific simulation, optimization passes.
Encoder/decoder, serializer/parser, compress/decompress, encrypt/decrypt — any symmetric pair.
Query engines, planners, optimizers. SQLancer's track record shows the pattern scales to production databases.
ML systems where ground truth is unavailable. The relation expresses the invariance you expect the model to honor.

Don't:

When the relation is itself unclear or contested. "The model's output for a rotated image should be similar" is a soft target; "should be identical" is testable. Pick relations whose violation is unambiguous.
As your only method. The relation can be wrong; the implementation can satisfy a wrong relation. Compose with example tests for known cases and with differential testing where a reference exists.
For pure logic where an exact oracle is cheap. An exact assertion like assert f(2) == 4 settles the case directly; metamorphic relations are worth writing when the oracle is missing, not when it's available.

Evidence¶

SQLancer turned metamorphic oracles into 123 reported bugs across three mature DBMSs — SQLite, MySQL, and PostgreSQL, 99 of them since fixed or verified (Rigger and Su 2020)².

The published track record is shorter than fuzzing's and concentrated in domains without easy oracles: compilers, databases, ML, scientific computing.

Classification¶

Quality dimensions: Functionality, Security (when the relation expresses a security invariant).
Area: Databases, ML inference, scientific computing, image and signal processing, parsers and serializers.
Guarantee: Empirical.

Referenced by¶

Quality dimensions · Quality dimensions
Contracts as specifications · Methods
Differential testing · Methods
Example tests · Methods
Testing machine-learning systems · Methods
Verifying concurrency · Methods
Verifying numerical code · Methods
Verifying time and date handling · Methods
How AI fits into software quality · AI
Choosing methods · Overview

References¶

Chen, Tsong Yueh, Fei-Ching Kuo, Huai Liu, et al. 2018. "Metamorphic Testing: A Review of Challenges and Opportunities." ACM Computing Surveys 51 (1): 1–27. https://doi.org/10.1145/3143561. ↩↩
Rigger, Manuel, and Zhendong Su. 2020. "Testing Database Engines via Pivoted Query Synthesis." Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20). https://doi.org/10.48550/arXiv.2001.04174. ↩↩