# 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)[^chen2018]. The *two or more* is the crux:
the relation holds across **separate runs**, which is what separates it
from a single-run [invariant](https://quality.stereobooster.com/oracle.md) 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](https://quality.stereobooster.com/numbers.md); 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](https://quality.stereobooster.com/testing-ml-systems.md).
- **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](https://hypothesis.readthedocs.io/)** (Python), **[fast-check](https://fast-check.dev/)** (TypeScript), **[proptest](https://github.com/proptest-rs/proptest)**
  (Rust), **[QuickCheck](https://hackage.haskell.org/package/QuickCheck)** (Haskell), **[PropEr](https://proper-testing.github.io/)** (Erlang/Elixir),
  **[jqwik](https://jqwik.net/)** (Java), **[FsCheck](https://fscheck.github.io/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](https://github.com/sqlancer/sqlancer)** (Rigger and Su 2020)[^rigger2020] — 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++](https://github.com/AFLplusplus/AFLplusplus)**, **[libFuzzer](https://llvm.org/docs/LibFuzzer.html)**, **[Atheris](https://github.com/google/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](https://quality.stereobooster.com/differential-testing.md) 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)[^rigger2020].

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

## Further reading

- **A survey** of the metamorphic-testing literature spans
  scientific computing, ML, search engines, and simulation
  (Chen et al. 2018)[^chen2018].

## Related

**Generative testing**

These methods blur together because they all run the code and check the result
without a hand-written expected value. Two roles pull them apart, and a single test
picks one of each.

**Input generators** choose the input, and differ by the steering signal (the
Generative subtree of the [input axis](https://quality.stereobooster.com/input.md)):

- Random: [property-based testing](https://quality.stereobooster.com/property-based-testing.md) samples
  from a generator or schema.
- Coverage feedback: [fuzzing](https://quality.stereobooster.com/fuzzing.md) mutates inputs steered by
  coverage (raw bytes); [automated test generation](https://quality.stereobooster.com/automated-test-generation.md)
  runs the same feedback loop as a fitness-guided search over structured call sequences.
- Solver: [symbolic execution](https://quality.stereobooster.com/symbolic-execution.md) derives an input
  that reaches a chosen path.
- Systematic: [combinatorial testing](https://quality.stereobooster.com/combinatorial-testing.md) builds a
  covering array over every t-way combination.

**Oracle suppliers** provide the verdict when no expected value is written:

- Metamorphic testing checks a relation between
  the outputs of two related inputs.
- [Differential testing](https://quality.stereobooster.com/differential-testing.md) compares against a
  trusted second implementation.

Pick one generator and one oracle: they compose. A coverage-guided fuzzer that checks a
metamorphic relation is fuzzing and metamorphic at once. (The written-answer end, where
the author picks rows and answers by hand, is [example / parameterized
tests](https://quality.stereobooster.com/example-tests.md).)

## 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](https://quality.stereobooster.com/quality-dimensions.md) · Quality dimensions
- [Contracts as specifications](https://quality.stereobooster.com/contracts-as-specifications.md) · Methods
- [Differential testing](https://quality.stereobooster.com/differential-testing.md) · Methods
- [Example tests](https://quality.stereobooster.com/example-tests.md) · Methods
- [Testing machine-learning systems](https://quality.stereobooster.com/testing-ml-systems.md) · Methods
- [Verifying concurrency](https://quality.stereobooster.com/concurrency.md) · Methods
- [Verifying numerical code](https://quality.stereobooster.com/numbers.md) · Methods
- [Verifying time and date handling](https://quality.stereobooster.com/time-and-date.md) · Methods
- [How AI fits into software quality](https://quality.stereobooster.com/ai.md) · AI
- [Choosing methods](https://quality.stereobooster.com/choosing.md) · Overview

## References

[^chen2018]: Chen, Tsong Yueh, Fei-Ching Kuo, Huai Liu, et al. 2018. "[Metamorphic Testing: A Review of Challenges and Opportunities](https://www.cs.hku.hk/data/techreps/document/TR-2017-04.pdf)." *ACM Computing Surveys* 51 (1): 1–27. <https://doi.org/10.1145/3143561>.
[^rigger2020]: Rigger, Manuel, and Zhendong Su. 2020. "[Testing Database Engines via Pivoted Query Synthesis](https://www.usenix.org/system/files/osdi20-rigger.pdf)." *Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20)*. <https://doi.org/10.48550/arXiv.2001.04174>.

## Acronyms

- PBT — property-based testing
- PQS — Pivoted Query Synthesis (a SQLancer metamorphic technique)
- TLP — Ternary Logic Partitioning (a SQLancer metamorphic technique)