Metamorphic Testing hat 147 bestätigte Bugs in GCC und LLVM gefunden, Defekte in kommerziellen ADAS-Simulatoren, die von Automobil-OEMs genutzt werden, sowie einen fatalen Fehler im Wahrnehmungssystem eines selbstfahrenden Autos acht Tage, bevor es einen Fußgänger tötete. Die Technik klingt akademisch, aber die Bugs sind es nicht.

Das Problem ist das Orakel-Problem. Bei vielen Programmen können Sie Eingaben ausführen, aber nicht unabhängig überprüfen, ob die Ausgaben korrekt sind. Was ist der exakt kürzeste Pfad durch ein Straßennetz mit 10.000 nodes? Bewahrt diese Compiler-Optimierung die Semantik? Ist die Klassifizierung dieses ML-Modells tatsächlich richtig? Sie wissen es nicht. Traditionelles Unit Testing bricht hier zusammen, weil Sie kein assertEquals(expected, actual) schreiben können, wenn Sie keine Ahnung haben, was expected sein sollte.

Metamorphic Testing umgeht dies, indem es die Ausgaben überhaupt nicht prüft. Es prüft Beziehungen zwischen Ausgaben.

Was ist Metamorphic Testing?

Metamorphic Testing ist eine Technik, bei der Sie eine Eingabe in eine verwandte Eingabe transformieren, beide durch Ihr Programm laufen lassen und prüfen, dass die beiden Ausgaben eine bekannte mathematische oder logische Beziehung einhalten. Die Beziehung wird als metamorphic relation bezeichnet.

Wenn Ihr Programm den Durchschnitt einer Zahlenliste berechnet, müssen Sie nicht den exakten Durchschnitt von [4.2, 1.7, 9.3, 2.1] kennen, um ihn zu testen. Sie müssen nur wissen, dass das Mischen der Liste dasselbe Ergebnis liefern sollte oder dass das Verdoppeln jedes Elements den Durchschnitt verdoppeln sollte. Das sind metamorphic relations.

Die erste Eingabe ist der Quell-Testfall. Die transformierte Eingabe ist der Folge-Testfall. Das Orakel ist die Beziehung selbst.

Hier ist ein konkretes Beispiel in Python:

import random

def compute_average(numbers):
    """Returns the arithmetic mean of a list of numbers."""
    if not numbers:
        raise ValueError("empty list")
    return sum(numbers) / len(numbers)

def test_average_permutation_invariant():
    """MR-1: Shuffling the input should not change the average."""
    source = [4.2, 1.7, 9.3, 2.1, 5.6]
    follow_up = source.copy()
    random.shuffle(follow_up)

    source_out = compute_average(source)
    follow_up_out = compute_average(follow_up)

    assert source_out == follow_up_out, (
        f"Permutation MR failed: {source_out} != {follow_up_out}"
    )

def test_average_scaling():
    """MR-2: Doubling every element should double the average."""
    source = [3.0, 6.0, 9.0]
    follow_up = [x * 2 for x in source]

    source_out = compute_average(source)
    follow_up_out = compute_average(follow_up)

    assert follow_up_out == source_out * 2, (
        f"Scaling MR failed: {follow_up_out} != {source_out * 2}"
    )

def test_average_inclusion():
    """MR-3: Appending the average itself should not decrease the average."""
    source = [10.0, 20.0, 30.0]
    source_out = compute_average(source)
    follow_up = source + [source_out]
    follow_up_out = compute_average(follow_up)

    assert follow_up_out == source_out, (
        f"Inclusion MR failed: {follow_up_out} != {source_out}"
    )

if __name__ == "__main__":
    test_average_permutation_invariant()
    test_average_scaling()
    test_average_inclusion()
    print("All metamorphic relations passed.")

Wenn eine dieser Beziehungen fehlschlägt, haben Sie einen Bug gefunden, ohne jemals den erwarteten Durchschnitt von Hand berechnet zu haben. Das ist die Kernidee.

Echte Bugs, die in Produktionssystemen gefunden wurden

Die Technik ist nicht theoretisch. Hier sind dokumentierte Fälle, in denen Metamorphic Testing echte Bugs in Produktionssoftware gefunden hat.

147 Bugs in GCC und LLVM

Forscher haben Metamorphic Testing auf C-Compiler-Optimierungspipelines angewendet und 147 bestätigte Bugs in GCC und LLVM gefunden. Das waren keine Spielzeugprogramme. Es waren echte Fehlkompilierungs-Bugs, bei denen ein korrektes C-Programm, das durch einen optimierenden Compiler lief, falschen Maschinencode produzierte. Einige dieser Bugs hatten jahrelang existiert. Die metamorphic relations waren einfach: Wenn Sie eine Funktion von Hand inlinen, sollte die optimierte Ausgabe sich genauso verhalten wie das Original. Wenn Sie unabhängige Anweisungen permutieren, sollte sich das Ergebnis nicht ändern. Die Compiler-Entwickler bestätigten und behebten diese Bugs.

Vulkan-Shader-Compiler bei Google

Das GraphicsFuzz-Team von Google setzte randomisiertes Metamorphic Testing in Produktion für die Khronos Vulkan Conformance Test Suite ein. Es generierte zufällige Fragment-Shader, wendete semantikerhaltende Transformationen an (wie das Einwickeln von Ausdrücken in Identitätsfunktionen oder das Hinzufügen von totem Code) und verglich gerenderte Bilder über verschiedene Compiler und GPUs hinweg. Wenn zwei angeblich äquivalente Shader unterschiedliche Pixel produzierten, hatten sie einen Compiler-Bug gefunden. Das Team baute eine ganze Pipeline namens gfauto, um diese Fälle zu reduzieren, zu deduplizieren und zu melden. Es fand Bugs im Ökosystem der Tools, die Vulkan-Shader transformieren, optimieren und validieren, einschließlich Produktionstreibern, die an Endnutzer ausgeliefert wurden.

ADAS-Simulatoren, die von Automobil-OEMs genutzt werden

Ein Team testete drei populäre ADAS-Simulationsplattformen – Simulink, CarMaker und 51Sim-One Cloud – mit Fokus auf deren Lane Keeping Assist Systems. Normale Testfälle bestanden auf allen drei Plattformen. Überhaupt keine Probleme. Dann wandte das Team geometrische metamorphic relations an: das Straßenszenario horizontal spiegeln, die Fahrzeugposition rotieren, affine Transformationen auf die Fahrbahnmarkierungen anwenden. Die Ausgaben sollten sich vorhersagbar transformieren. Taten sie nicht. Bugs wurden auf allen drei Plattformen aufgedeckt. MathWorks und IPG Automotive bestätigten die Probleme später. Das sind dieselben Plattformen, die verwendet werden, um Software zu validieren, bevor sie in Fahrzeuge geht.

Der Defekt im self-driving car in derselben Klasse

In einem der erschütterndsten Fälle wendeten Forscher Metamorphic Testing auf ein Objekterkennungssystem für autonome Fahrzeuge an und fanden einen Bug in der Wahrnehmungspipeline. Das System versagte bei der korrekten Klassifizierung von Fußgängern unter bestimmten transformierten Eingaben. Sie meldeten ihn. Der Bug, den sie gefunden hatten, gehörte derselben Defektklasse an, die bei tödlichen self-driving car-Fußgängerzusammenstößen eine Rolle gespielt hat.

Der Trade-off: Relations sind domänenspezifisch

Metamorphic Testing ist mächtig, aber nicht kostenlos. Der schwierige Teil ist das Identifizieren guter metamorphic relations. Eine schlechte Beziehung gibt Ihnen falsche Sicherheit. Eine Beziehung, die zu schwach ist, wird keine Bugs finden. Eine Beziehung, die zu stark ist, wird bei korrektem Verhalten aufgrund von Floating-Point-Rauschen oder Nichtdeterminismus fehlschlagen.

Das Entwerfen von Beziehungen erfordert Domänenwissen. Für einen Kürzeste-Pfad-Algorithmus gehören gute Beziehungen dazu: Die Pfadkosten A->B sollten in einem ungerichteten Graphen B->A entsprechen; das Addieren einer Konstante zu jedem Kantengewicht sollte diese Konstante multipliziert mit der Anzahl der Kanten zu den Gesamtpfadgetkosten addieren. Für einen Sortieralgorithmus: Wenn man eine sortierte Liste umkehrt und sortiert, sollte das die Umkehrung der ursprünglich sortierten Liste ergeben; jedes Element in der Ausgabe sollte in der Eingabe mit derselben Häufigkeit vorkommen.

Sie können dieselben Beziehungen nicht über unverbundene Systeme hinweg wiederverwenden. Das ist der Preis.

Gleitkomma-Arithmetik ist eine weitere Falle. Viele Beziehungen setzen exakte Gleichheit voraus, aber 0.1 + 0.2 != 0.3 in IEEE 754. Sie benötigen Toleranz-basierte Vergleiche, und die Wahl der richtigen Toleranz ist ein eigenes Problem. Zu eng und Sie erhalten Falschpositive. Zu locker und Sie übersehen echte Bugs.

Wie Sie Metamorphic Testing zu Ihrem Codebase hinzufügen

Sie benötigen kein Framework. Sie benötigen Disziplin.

Beginnen Sie mit den Funktionen in Ihrem Codebase, die kein Orakel haben. ML-Inference, Optimierungsalgorithmen, geometrische Berechnungen, statistische Aggregationen und Simulationscode sind alles Kandidaten. Fragen Sie sich für jede: Was muss über die Ausgabe wahr sein, wenn ich die Eingabe auf eine bestimmte, vorhersagbare Weise ändere?

Schreiben Sie eine metamorphic relation pro Testfunktion. Benennen Sie sie klar. Führen Sie sie in CI neben Ihren Unit-Tests aus. Wenn eine Beziehung fehlschlägt, behandeln Sie sie genau wie jeden anderen Testfehler.

Hier ist ein etwas realistischeres Beispiel, das eine Pfadfindungsfunktion testet:

import math

def shortest_path_cost(graph, start, end):
    """Returns the cost of the shortest path. Assume implemented."""
    pass

def test_shortest_path_undirected_symmetry():
    """MR: In an undirected graph, path cost A->B equals B->A."""
    graph = {
        'A': [('B', 3.0), ('C', 1.0)],
        'B': [('A', 3.0), ('C', 1.0)],
        'C': [('A', 1.0), ('B', 1.0)],
    }
    ab = shortest_path_cost(graph, 'A', 'B')
    ba = shortest_path_cost(graph, 'B', 'A')
    assert math.isclose(ab, ba, rel_tol=1e-9), f"Symmetry failed: {ab} != {ba}"

def test_shortest_path_subpath():
    """MR: The shortest path cost cannot exceed any specific path's cost."""
    graph = {
        'A': [('B', 2.0), ('C', 10.0)],
        'B': [('C', 2.0)],
        'C': [],
    }
    cost = shortest_path_cost(graph, 'A', 'C')
    assert cost <= 10.0, f"Subpath MR failed: {cost} > 10.0"
    assert math.isclose(cost, 4.0, rel_tol=1e-9), f"Expected 4.0, got {cost}"

Sie testen nicht den Algorithmus selbst. Sie testen Ihre Implementierung davon.

FAQ

Ersetzt Metamorphic Testing Unit-Tests?

Nein. Es ergänzt sie. Verwenden Sie Unit-Tests, wenn Sie die erwartete Ausgabe kennen. Verwenden Sie metamorphic tests, wenn Sie sie nicht kennen.

Kann ich das für ML-Modelle verwenden?

Ja, und es ist eines der aktivsten Forschungsgebiete. Beziehungen wie „Das Rotieren eines Katzenbilds sollte es weiterhin als Katze klassifizieren“ sind metamorphic relations. Forscher haben mit diesem Ansatz Probleme bei der Modellzuverlässigkeit und Fairness-Lücken gefunden.

Wie weiß ich, ob meine metamorphic relation korrekt ist?

Sie beweisen sie nicht. Sie argumentieren aus der Spezifikation oder aus mathematischen Eigenschaften der Domäne. Wenn Ihre Beziehung selbst fehlerhaft ist, erhalten Sie Falschpositive. Beginnen Sie mit offensichtlichen Eigenschaften und fügen Sie mehr hinzu, wenn Sie Vertrauen gewinnen.

Was ist mit flaky tests?

Nichtdeterministische Systeme (probabilistische Algorithmen, nebenläufiger Code, Systeme mit Timeouts) machen Metamorphic Testing schwieriger. Sie müssen möglicherweise mehrere Durchläufe ausführen oder statistische Beziehungen anstelle exakter Gleichheit verwenden.

Beginnen Sie mit einer Beziehung

Sie benötigen keinen Doktor, um das zu nutzen. Wählen Sie eine Funktion in Ihrem System, bei der Sie derzeit das Testen überspringen, weil die Überprüfung der Ausgabe zu schwierig ist. Schreiben Sie eine metamorphic relation. Führen Sie sie aus. Wenn Sie tiefer einsteigen möchten, sind die gfauto-Tools des GraphicsFuzz-Teams Open Source, und die ACM-Umfrage von Segura et al. katalogisiert Beziehungen über Dutzende Domänen hinweg.

Die Technik fand 147 Compiler-Bugs, bestätigte Defekte in Automobilsimulationsplattformen und deckte eine Klasse von Wahrnehmungsfehlern in selbstfahrenden Autos auf, bevor sie die Straße erreichten. Die Bugs sind real. Die einzige Frage ist, ob Sie nach ihnen suchen.