Was Differential Testing dir tatsächlich bringt

Du kannst Differential Testing ohne formalen Beweis vertrauen, aber nur, wenn du genau verstehst, wo es zusammenbricht.

Die Schwäche heißt Common-Mode Failure. Wenn jede Implementierung einer Spezifikation dieselbe falsche Annahme trifft, stimmen sie alle überein und dein Test Harness wertet es als bestanden. N-Version Programming schützt dich nicht vor einer schlechten Spezifikation.

Differential Testing funktioniert, indem es mehrere unabhängige Implementierungen derselben Spezifikation mit denselben Eingaben ausführt. Wenn ihre Ausgaben divergieren, ist mindestens eine fehlerhaft. Wenn sie übereinstimmen, bewertest du sie vorläufig als korrekt.

Das ist mächtig, weil es die Notwendigkeit eines Test Oracles eliminiert. Ein Oracle ist eine Quelle der Wahrheit, die die korrekte Antwort für jede Eingabe kennt. Für komplexe Systeme sind Oracles oft schwieriger zu bauen als das System selbst. Eine Steuer-Engine, eine Physik-Simulation oder ein protocol decoder können auf Konsistenz getestet werden, lange bevor du beweisen kannst, was jede Ausgabe sein sollte.

Aber die Vorläufigkeit ist wichtig. Übereinstimmung beweist nur Konsistenz. Sie beweist keine Korrektheit.

Warum Übereinstimmung keine Korrektheit ist

Der Fehlermodus, den jeder theoretisch kennt, aber in der Praxis vergisst, ist der Common-Mode Fault. Wenn der Fehler in der Spezifikation selbst entsteht, oder in einer gemeinsamen Annahme, die alle Implementierungsteams unabhängig voneinander treffen, produziert jede Version dieselbe falsche Antwort.

Die Spezifikation muss nicht auf offensichtliche Weise falsch sein. Sie muss nur an einem Edge Case mehrdeutig sein, den menschliche Gehirne auf dieselbe Weise auflösen.

Stell dir eine Spezifikation für eine Funktion vor, die die Fläche eines einfachen Polygons aus einer Liste von Vertices berechnet. Die Spezifikation liefert die Shoelace-Formel. Sie erwähnt nie die Reihenfolge der Vertices.

Drei Teams implementieren sie. Alle drei gehen von einer gegen den Uhrzeigersinn verlaufenden Reihenfolge aus, weil das Beispieldiagramm so gezeichnet ist. Eingaben im Uhrzeigersinn produzieren im Roh-Formula eine negative Fläche. Alle drei wrappen das Ergebnis stillschweigend mit abs(), weil eine Fläche positiv sein muss. Sie stimmen in jedem Testfall überein.

Aber die Spezifikation hat nie gesagt, dass Uhrzeigersinn ungültig ist. Die Implementierungen sind konsistent und durch Unterlassung falsch. Differential Testing gibt allen grünes Licht.

Drei Implementierungen, eine mehrdeutige Spezifikation

Hier ist ein konkretes Beispiel, das du ausführen kannst. Die Spezifikation lautet: “Parse einen Duration-String und gib die Gesamtanzahl der Sekunden zurück. Eine Duration besteht aus einer oder mehreren Komponenten. Jede Komponente ist eine positive Ganzzahl gefolgt von einem Einheitenbuchstaben: h für Stunden, m für Minuten, s für Sekunden.”

Drei Teams erhalten diese Spezifikation und schreiben ihre eigenen Parser.

import re

def parse_duration_a(s):
    """Team A: regex approach."""
    if not isinstance(s, str):
        raise TypeError("input must be a string")
    m = re.fullmatch(r"(?:(\d+)h)?(?:(\d+)m)?(?:(\d+)s)?", s)
    if not m or not any(m.groups()):
        raise ValueError(f"invalid duration: {s}")
    h, mn, sec = (int(x or 0) for x in m.groups())
    return h * 3600 + mn * 60 + sec

def parse_duration_b(s):
    """Team B: left-to-right scanner."""
    if not isinstance(s, str):
        raise TypeError("input must be a string")
    total = 0
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1
        if j == i:
            raise ValueError(f"expected number at position {i}")
        num = int(s[i:j])
        if j >= len(s):
            raise ValueError(f"missing unit after {num}")
        unit = s[j]
        if unit == 'h':
            total += num * 3600
        elif unit == 'm':
            total += num * 60
        elif unit == 's':
            total += num
        else:
            raise ValueError(f"invalid unit: {unit}")
        i = j + 1
    return total

def parse_duration_c(s):
    """Team C: state machine with duplicate detection."""
    if not isinstance(s, str):
        raise TypeError("input must be a string")
    total = 0
    seen = set()
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1
        if j == i:
            raise ValueError("expected number")
        num = int(s[i:j])
        if j >= len(s):
            raise ValueError("missing unit")
        unit = s[j]
        if unit in seen:
            raise ValueError(f"duplicate unit: {unit}")
        seen.add(unit)
        i = j + 1
        if unit == 'h':
            total += num * 3600
        elif unit == 'm':
            total += num * 60
        elif unit == 's':
            total += num
        else:
            raise ValueError(f"invalid unit: {unit}")
    return total

Jetzt führen wir ein Differential Test Harness aus, das allen dreien dieselben Eingaben füttert und Divergenzen markiert.

def differential_test(implementations, inputs):
    for case in inputs:
        results = []
        errors = []
        for impl in implementations:
            try:
                results.append(impl(case))
            except Exception as e:
                errors.append(type(e).__name__)
        if errors:
            if len(errors) == len(implementations) and len(set(errors)) == 1:
                print(f"ALL ERROR on {case!r}: {errors[0]}")
            else:
                print(f"MIXED on {case!r}: results={results}, errors={errors}")
        else:
            if len(set(results)) == 1:
                print(f"AGREE on {case!r}: {results[0]}")
            else:
                print(f"DISAGREE on {case!r}: {results}")

IMPLS = [parse_duration_a, parse_duration_b, parse_duration_c]

CASES = [
    "1h30m",      # normal
    "90m",        # single unit
    "30m1h",      # out of order
    "1h2h",       # duplicate unit
    "0h",         # zero is not positive
    "1.5h",       # decimal
    "1H",         # wrong case
]

differential_test(IMPLS, CASES)

Die Ausführung produziert:

AGREE on '1h30m': 5400
AGREE on '90m': 5400
MIXED on '30m1h': results=[5400, 5400], errors=['ValueError']
MIXED on '1h2h': results=[10800], errors=['ValueError', 'ValueError']
AGREE on '0h': 0
ALL ERROR on '1.5h': ValueError
ALL ERROR on '1H': ValueError

Das Harness findet echte Probleme. Bei 30m1h lehnt Team A’s Regex die unsortierte Eingabe ab, während Teams B und C sie akzeptieren. Bei 1h2h addiert Team B’s Scanner stillschweigend beide Stunden, während Team C’s Duplicate Detection einen Fehler wirft. Das sind genau die Bugs, die Differential Testing finden soll.

Aber schau auf 0h. Die Spezifikation sagte “positive Ganzzahl”. Null ist nicht positiv. Alle drei Implementierungen akzeptieren sie, weil keines der Teams eine Validierung für eine Anforderung geschrieben hat, die offensichtlich klang, aber nicht erzwungen wurde. Sie stimmen überein, also besteht der Test. Das ist ein Common-Mode Failure, der sich in aller Deutlichkeit verbirgt.

Dasselbe passiert bei 1H. Alle drei lehnen sie ab, weil die Spezifikation Kleinbuchstaben für die Einheiten zeigte. Aber wenn die Spezifikation Case-Insensitive Matching gemeint hat, ist jede Implementierung falsch und sie sind zusammen falsch.

Wie man Differential Testing weniger falsch macht

Du kannst Common-Mode Failures nicht vollständig eliminieren, ohne einen formalen Beweis. Aber du kannst ihre Wahrscheinlichkeit verringern.

Diversifiziere Implementierungsstrategien, nicht nur das Personal. Wenn jedes Team denselben Algorithmus aus demselben Lehrbuch verwendet, hast du keine Diversität aufgebaut. Du hast Latenz aufgebaut. Zwinge ein Team, eine State Machine zu verwenden, ein anderes einen Parser Generator, ein drittes Rekursion. Unterschiedliche Algorithmen scheitern bei unterschiedlichen Eingaben.

Verwende unterschiedliche Programmiersprachen. Geteilte Standard-Library-Bugs sind ein klassischer Common-Mode Failure. Wenn jede Implementierung denselben JSON-Parser oder dieselbe Floating-Point-Math-Library verwendet, teilen sie sich dessen Bugs.

Füge ein adversariales Oracle hinzu. Beauftrage jemanden damit, Eingaben zu finden, bei denen die Spezifikation mehrdeutig ist. Ihre Aufgabe ist es, die Implementierungen zum Divergieren zu bringen. Die Eingaben, die sie spalten, sind die wertvollsten Tests, die du schreiben wirst.

Fuzze aggressiv. Übereinstimmung bei einer Handvoll handverlesener Beispiele ist schwache Evidenz. Übereinstimmung bei einer Million zufällig generierter Eingaben ist stärker. Fuzzing entdeckt die Ecken des Input Spaces, die keines der Teams bedacht hat.

Teste die Spezifikation selbst. Schreibe explizite Negative Tests für Anforderungen wie “positive Ganzzahl” und prüfe, dass mindestens eine Implementierung sie ablehnt. Wenn alle drei eine ungültige Eingabe akzeptieren, braucht deine Spezifikation eine Verschärfung, nicht dein Code.

Wann Differential Testing ausreicht

Differential Testing ist kein Ersatz für formale Verifikation. Es ist ein Filter. Es findet Implementierungs-Bugs billig und früh, bevor du in einen Beweis investiert hast.

Die Frage ist nicht, ob du ihm vertrauen kannst. Die Frage ist, wofür du ihm vertrauen kannst. Du kannst ihm vertrauen, Divergenzen zu finden. Du kannst ihm nicht vertrauen, universelle Übereinstimmung bei einer schlechten Spezifikation zu finden.

Wenn du Safety-Critical Software baust, ist Differential Testing ein vorläufiger Schritt. Führe es aus, behebe die Divergenzen, unterziehe dann die Spezifikation einem Model Checker oder einem Proof Assistant. Wenn du einen Web Service baust, ist Differential Testing möglicherweise das gesamte Vertrauen, das du für einen Feature Branch brauchst. Der Beweis ist proportional zu den Risiken.

Wenn du heute eine N-Version Test Suite betreibst, füge einen weiteren Testfall hinzu. Finde eine Eingabe, die die Spezifikation nicht eindeutig definiert. Führe sie durch deine Implementierungen. Wenn sie alle übereinstimmen, hast du keinen guten Test gefunden. Du hast ein Spezifikationsloch gefunden.

Die Bugs, die dich umbringen, sind nicht diejenigen, bei denen deine Implementierungen divergieren. Es sind diejenigen, bei denen sie aus dem falschen Grund übereinstimmen.

Häufig gestellte Fragen

Was ist Differential Testing?

Differential Testing ist eine Technik, bei der mehrere unabhängige Implementierungen derselben Spezifikation mit identischen Eingaben ausgeführt werden. Ihre Ausgaben werden verglichen. Divergenzen decken Bugs auf, ohne eine bereits existierende Quelle der Wahrheit für jede Eingabe zu erfordern.

Was ist ein Common-Mode Failure in Software?

Ein Common-Mode Failure tritt auf, wenn mehrere unabhängige Komponenten bei derselben Eingabe aus demselben zugrundeliegenden Grund fehlschlagen. Bei N-Version Programming passiert das normalerweise, wenn die Spezifikation mehrdeutig ist und jedes Team die Mehrdeutigkeit auf dieselbe Weise auflöst.

Worin unterscheidet sich Differential Testing vom Property-Based Testing?

Property-Based Testing prüft, dass Ausgaben allgemeine Regeln erfüllen, wie zum Beispiel “das Sortieren einer Liste ändert nie ihre Länge”. Differential Testing prüft, dass mehrere Implementierungen dieselbe Ausgabe produzieren. Die beiden Techniken ergänzen einander. Property-Based Testing findet Logikfehler. Differential Testing findet Inkonsistenzen.

Kann ich LLMs verwenden, um diverse Implementierungen für Differential Testing zu generieren?

Das kannst du, aber sei vorsichtig. Modelle, die auf überlappenden Corpora trainiert wurden, neigen dazu, Code mit korrelierten Failure Modes zu produzieren. Neuere Forschung deutet auf Co-Error-Raten zwischen 15 % und 30 % für KI-generierte Komponenten hin. Wenn du LLMs verwendest, fordere in Prompts echt unterschiedliche Algorithmen und Sprachen an. Eine Sammlung semantisch identischer Rewrites ist keine Diversität.