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 tests assume 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 relation costs almost nothing to write when the implementation has a symmetric pair.
Optimization regressions. A SQL planner that returns different results from an equivalent query. SQLancer's NoREC and TLP oracles are this pattern.
Numerical regressions. Scale-invariance, linearity, monotonicity and symmetry checks catch regressions in numerical code, where exact oracles are hard 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, owed by any type with mempty and <> (Haskell) or empty and combine (Scala's Cats).
Functor laws — fmap id == id, fmap (f . g) == fmap f . fmap g.
Monad laws — left identity, right identity, associativity of bind.

Heuristic¶

A useful relation holds by definition of the operation, not by accident on the inputs a test happens to use. A failing metamorphic test can be a bug in the relation rather than in the implementation, and a relation phrased the way a domain expert would state the invariant, not the way the code computes it, does not share the code's mistakes.

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 transforms the generated input, runs the code on both inputs, and asserts the relation between the two outputs.

Database-specific oracles¶

SQLancer (Rigger and Su 2020)² — two metamorphic oracles, beside a containment oracle outside the metamorphic family:
- NoREC (Non-Optimizing Reference Engine Construction) — rewrites the query into one the optimizer cannot optimize and reports a bug when the two result sets differ.
- TLP (Ternary Logic Partitioning) — splits the query into TRUE/FALSE/NULL partitioning queries whose combined result must equal the original query's.
- PQS (Pivoted Query Synthesis) — the containment oracle: it picks a row, builds a query guaranteed to return it, and reports a bug if the engine does not.

ML-specific harnesses¶

No dedicated harness is required: a Hypothesis-style generator paired with a domain-specific transformation library (image rotation, audio time-stretch, text paraphrase) hosts the relation.

General-purpose¶

AFL++, libFuzzer, Atheris — fuzzers run metamorphic oracles by encoding "the transformation broke the relation" as the crash condition.

When to use, when not¶

Use:

Where a relation can be stated but a closed-form expected output cannot: image processing, ML inference, scientific simulation, optimization passes.
Query engines, planners, optimizers. SQLancer's metamorphic oracles have found bugs in production database engines.

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.
As the only method. The relation can be wrong, and an implementation can satisfy a wrong relation; example tests pin known cases, and differential testing checks against a reference where one 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's metamorphic oracle NoREC found 52.7% of the bugs detected by PQS, the tool's non-metamorphic containment oracle, a gap its authors expect from NoREC's narrower scope (Rigger and Su 2020)².
Both metamorphic oracles found bugs in production database engines. NoREC found 159 in SQLite, MariaDB, PostgreSQL and CockroachDB, 141 of them since fixed (Rigger and Su 2020a)³. TLP found 175 previously unknown bugs in database systems including MySQL, TiDB, SQLite and CockroachDB, 125 of them since fixed (Rigger and Su 2020b)⁴.

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. ↩↩
Rigger, Manuel, and Zhendong Su. 2020a. "Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction." Proceedings of the 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2020). https://doi.org/10.1145/3368089.3409710. ↩
Rigger, Manuel, and Zhendong Su. 2020b. "Finding Bugs in Database Systems via Query Partitioning." Proceedings of the ACM on Programming Languages 4 (OOPSLA). https://doi.org/10.1145/3428279. ↩