Metamorphe Tests: Warum weiß fast niemand etwas über diese vielversprechende Technik?

Ich muss zugeben: Ich lese das ACM Magazine . Es macht mich zu einem „Nerd“, selbst nach den Maßstäben von Programmierern. Unter anderem habe ich aus dieser Zeitschrift etwas über „metamorphe Tests“ gelernt. Ich hatte noch nie von ihm gehört, wie alle Leute, die ich gefragt habe. Die wissenschaftliche Literatur zu diesem Thema ist jedoch überraschend umfangreich: Es gibt viele unglaublich erfolgreiche Beispiele für ihre Anwendung in völlig unterschiedlichen Forschungsbereichen. Warum haben wir noch nie von ihm gehört? Es gibt nur einen Artikel für Personen außerhalb der wissenschaftlichen Gemeinschaft. Nun sollen es zwei sein.

Kurzer Hintergrund

Die meisten schriftlichen Tests verwenden Orakel . Das heißt, Sie kennen die Antwort und prüfen explizit, ob die Berechnungen die richtige Antwort liefern.

def test_dist(): p1 = (0, 3) p2 = (4, 0) assert dist(p1, p2) == 5 

Neben Orakeltests gibt es auch manuelle Tests. Der Tester setzt sich an den Computer und vergleicht die Eingabedaten mit den Ergebnissen. Da Systeme immer komplexer werden, werden manuelle Tests immer weniger nützlich. Jeder von ihnen überprüft nur einen Punkt in einem viel größeren Zustandsraum, und wir brauchen etwas, das den gesamten Zustandsraum erforscht.

Dies führt uns zu generativen Tests : Schreiben von Tests, die eine zufällige Menge in einem Zustandsraum abdecken. Die beliebteste Art des generativen Testens ist das eigenschaftsbasierte Testen (PBT). Wir finden die "Eigenschaft" der Funktion, generieren dann die Eingabewerte und prüfen, ob die Ausgabewerte mit dieser Eigenschaft übereinstimmen.

 def test_dist(): p1 = random_point() p2 = random_point() assert dist(p1, p2) >= 0 

Der Vorteil von PBT ist, dass es mehr Platz abdeckt. Ihr Nachteil ist der Verlust der Spezifität. Dies ist kein Orakeltest mehr ! Wir wissen nicht, wie die Antwort lauten soll, und die Funktion kann fehlerhaft sein, aber auf eine Weise, die dieselbe Eigenschaft hat. Hier setzen wir auf Heuristiken.

Ein ernstes Problem bei PBT ist das Finden guter Eigenschaften. Die meisten Funktionen haben einfache, allgemeine Eigenschaften und komplexe, spezifische Eigenschaften. Allgemeine Eigenschaften können auf eine große Anzahl von Funktionen angewendet werden, geben uns jedoch nicht viele Informationen. Spezifischere Eigenschaften geben mehr Informationen, sind jedoch schwieriger zu finden und nur in Bereichen mit begrenzten Aufgaben anwendbar. Wenn Sie eine Funktion haben, die bestimmt, ob ein Graph azyklisch ist, welche Eigenschaftstests werden Sie dann schreiben? Werden sie Ihnen das Vertrauen geben, dass die Funktion korrekt ist?

Motivation

Betrachten Sie nun eine komplexere Aufgabe. Stellen Sie sich vor, Sie möchten einen Sprach-Text-Konverter (STT) für Englisch schreiben. Es empfängt eine Audiodatei und zeigt den Text an. Wie würden Sie es testen?

Der einfachste Weg, ein Handorakel zu benutzen. Diktieren Sie den Satz und prüfen Sie, ob der Ausgabetext mit ihm übereinstimmt. Aber das ist noch nicht mal nah genug! Die Bandbreite der menschlichen Sprache ist riesig . Es wäre besser, 1.000 oder sogar 10.000 verschiedene Sounddateien zu testen. Handorakel mit Transkription wären zu teuer. Dies bedeutet, dass wir stattdessen eigenschaftsbasierte Tests verwenden müssen.

Aber wie generieren wir Input? Zum Beispiel können wir zufällige Zeilen erstellen, sie durch einen Text-zu-Sprache-Konverter (Text-zu-Sprache, TTS) leiten und dann sicherstellen, dass unser STT denselben Text erzeugt. Aber dies gibt uns wieder einen sehr begrenzten Bereich menschlicher Stimme. Kann TTS Änderungen in der Intonation hervorrufen, Wörter „schlucken“ und einen starken Akzent imitieren? Wenn wir nicht mit ihnen umgehen können, ist die STT dann besonders nützlich? Es ist besser, beliebige Texte zu verwenden, z. B. Aufnahmen aus dem Radio, aus Podcasts und Online-Videos.

Nun entsteht ein neues Problem. Bei der Verwendung von TTS haben wir mit geschriebenem Text begonnen. Bei beliebigen Audiodateien haben wir diese nicht und möchten sie gleichzeitig nicht manuell transkribieren. Stattdessen beschränken wir uns auf die Verwendung von Eigenschaften. Welche Eigenschaften müssen wir testen? Beispiele für die einfachsten Eigenschaften: „Das Programm stürzt nicht mit eingehenden Daten ab“ (eine gute Eigenschaft) oder „Konvertiert akustische Musik nicht in Wörter“ (möglicherweise?). Diese Eigenschaften decken die Überprüfung der Hauptaufgabe des Programms nicht sehr gut ab und erhöhen das Vertrauen in seine Qualität geringfügig.

Wir haben also zwei Aufgaben. Erstens brauchen wir eine große Menge an Eingaben in Form von Sprache. Zweitens müssen wir verstehen, wie man sie in nützliche Tests umwandelt, ohne lange Stunden damit zu verbringen, Stimmen manuell in Orakel zu transkribieren.

Metamorphe Tests

Für all dies wird die Ausgabe separat betrachtet. Was ist, wenn wir sie in einen breiteren Kontext einbetten? Wenn zum Beispiel ein Soundclip in den Out-Ausgang transkribiert wird, sollten wir immer rauskommen mit:

• Doppelte Lautstärke
• Zunehmende Frequenz
• Tempo erhöhen
• Hintergrundgeräusche hinzufügen
• Fahrzeuggeräusche hinzufügen
• Beliebige Kombination der oben genannten.

Dies sind alles „einfache“ Transformationen, die wir leicht testen können. Zum Beispiel können wir für einen Test mit „Fahrzeuggeräuschen“ 10 Proben von Fahrzeuggeräuschen nehmen, sie auf einen Soundclip setzen und prüfen, ob die Erkennungsergebnisse aller 11 Versionen übereinstimmen. Wir können die Lautstärke verdoppeln oder erhöhen, indem wir 11 Versionen in 33 Versionen verwandeln und dann das Tempo verdoppeln, um 66 Versionen zu erhalten. Dieses Prinzip kann auf jeden Soundclip in unserer Datenbank angewendet werden, wodurch der Speicherplatz für eingehende Daten erheblich erweitert wird.

Das Vorhandensein von 66 Versionen zum Vergleich ist sehr praktisch. Aber das ist noch nicht alles: Wir müssen immer noch nicht wissen, wie die Ausgabe aussehen soll. Wenn alle 66 Conversions zurückgegeben out , wurde der Test erfolgreich bestanden. Wenn mindestens eine etwas anderes zurückgibt, ist der Test fehlgeschlagen. Zu keinem Zeitpunkt müssen wir überprüfen, was in out . Das ist extrem wichtig. Daher vergrößern wir den Testraum mit sehr wenig menschlicher Beteiligung erheblich. Zum Beispiel können wir eine Episode der Serie herunterladen, Konvertierungen durchführen und prüfen, ob alle Ergebnisse ihrer Konvertierung in Text ¹ übereinstimmen. Wir haben nützliche Tests erhalten, ohne den Sprachclip anzuhören . Jetzt können wir komplexe und tiefe Tests erstellen, ohne ein Orakel zu verwenden!

Zwei Sätze von Eingabedaten sowie deren Ausgabedaten sind miteinander verbunden. Eine solche Eigenschaft, die sich auf den Satz eingehender / ausgehender Daten bezieht, wird als metamorphe Verbindung ^{2 bezeichnet} . Tests, die diese Eigenschaft anwenden, werden als metamorphe Tests bezeichnet . In komplexen Systemen können interessante metamorphe Beziehungen leichter gefunden werden als interessante Eigenschaften einzelner eingehender / ausgehender Daten.

Sagen wir es etwas formeller: Wenn wir x und f(x) , können wir einige Transformationen von x , um x2 und f(x2) . Im Fall von STT überprüfen wir nur f(x) = f(x2) , können jedoch beliebige Beziehungen zwischen den beiden Datensätzen verwenden. Es kann metamorphe Beziehungen wie f(x2) > f(x) oder "ist f(x2)/f(x) ein ganzzahliger Wert" geben. In ähnlicher Weise kann dieses Prinzip unter Verwendung von f(x) und f(x3) auf mehrere Sätze von Eingabedaten erweitert werden. Ein Beispiel hierfür ist der Vergleich der Ergebnisse einer Suchmaschine ohne Filter mit den Ergebnissen einer Suchmaschine mit einem oder zwei Filtern. In den meisten Beschreibungen von Anwendungsfällen, die ich lese, werden nur zwei Sätze von Eingabedaten verwendet, da selbst diese ausreichen, um verrückte Fehler zu finden.

Anwendungsbeispiele

Apropos Anwendungsfälle: Wie effektiv sind metamorphe Tests in der Praxis? Es ist eine Sache, abstrakt über eine Technik zu sprechen oder künstliche Beispiele zu nennen. Fallstudien sind aus drei Gründen nützlich. Zunächst wird angezeigt, ob die Methode tatsächlich funktioniert. Zweitens können Sie von ihnen die möglichen Schwierigkeiten bei der Verwendung von MT kennenlernen. Drittens zeigen uns die Beispiele, wie wir die Technik anwenden können. Jede im Anwendungsbeispiel verwendete metamorphe Verbindung kann versucht werden, sich an die Lösung unserer Probleme anzupassen.

Metamorphes Testen: Ein Überblick über Herausforderungen und Chancen bietet eine Liste vieler Studien, aber alle sind wissenschaftliche Artikel. Unten sind die interessantesten. Mit (pdf) gekennzeichnete Artikel sind, wie Sie vielleicht erraten haben, als PDF angelegt.

• METTEL: Ein metamorpher Testansatz zur Validierung unbeaufsichtigter Methoden des maschinellen Lernens (pdf). Hier werden 11 verschiedene metamorphe Beziehungen beschrieben, um unkontrolliertes Clustering zu testen. Beispiel: "Erhalten wir das gleiche Ergebnis, wenn wir die Eingabedaten mischen?" und "gehören die zusätzlichen Eingabedaten an den Rändern der Cluster zu diesen Clustern?" Unterschiedliche Modelle variieren mit unterschiedlichen Beziehungen. Beispielsweise weisen etwa 5% der getesteten k-means-Modelle mit einer Mischung in der Reihenfolge der eingehenden Punkte einen durchschnittlichen Clusterfehler von 20% auf
• DeepTest: Automatisiertes Testen von autonomen Autos mit Deep-Neural-Netzwerk-Antrieb (pdf). Das Thema des Artikels sind die Bildverarbeitungssysteme von Autopiloten in Autos. Beispiele für metamorphe Beziehungen (MS): „Hinzufügen eines Regenfilters“ oder „leichte Neigung des Bildes“. Die Autoren haben die Ergebnisse der Probenahme hier veröffentlicht : Fast alle von ihnen getesteten Systeme haben ihre Funktionen beim Wechsel der MS nicht erfüllt.
• Automatisiertes Testen von Graphics Shader Compilern (pdf). Injektionen des "toten" Codes und der Laufzeitkonstanten in den Shadern führten dazu, dass Objekte in den Bildern verschwanden oder in Rauschen umgewandelt wurden. Auf der Grundlage ihrer Arbeit recherchiert, entstand ein Startup GraphicsFuzz , das von Google gekauft wurde, und die Website ist geschlossen.
• Metamorphes Testen von RESTful-Web-APIs (pdf). Werden wir die gleichen Elemente erhalten, wenn sich die Paginierung ändert? Was ist, wenn Sie sie nach Datum sortieren? Dieser Artikel listet eine Reihe von Fehlern in Spotify und Youtube auf.
• Ein innovativer Ansatz zum Testen von Bioinformatikprogrammen mit metamorphen Tests (früher pdf, jetzt aber nicht). Suchen Sie nach Fehlern in Bioinformationsdaten. Ich bin mit Bioinformatik schlecht vertraut, aber der Artikel zeigt, dass MS auch in speziellen Bereichen nützlich sind.

Das Problem

Oh, also alle diese Quellen sind in PDF.

Es dauerte mehrere Stunden, um alle diese Artikel zu finden. Und dieses Problem ist mit dem größten Hindernis für die Entwicklung von MT verbunden: Alle oben genannten Links sind Vorabdrucke oder erste Entwürfe zukünftiger wissenschaftlicher Artikel. Wenn ich anfange, wenig bekannte Techniken zu verstehen, stelle ich mir zunächst die Frage: "Warum sind sie wenig bekannt?" Manchmal ist der Grund offensichtlich, manchmal ist es eine komplexe Reihe kleiner Gründe, manchmal ist das Problem einfach, dass die Methodik „kein Glück“ hat.

Im Fall von MT ist das Problem offensichtlich. Fast alle Informationen sind hinter der wissenschaftlichen Paywall verborgen. Wenn Sie MT studieren möchten, benötigen Sie entweder Zugriff auf das Tagebuch oder Sie müssen mehrere Stunden damit verbringen, nach Preprints ^{3 zu} suchen.

Weitere Studie

Der Erfinder von MT ist Ty Chen . Er wurde die treibende Kraft vieler Studien. Andere Forscher auf diesem Gebiet sind Zhi Quan Zhou und Sergio Segura ; Beide haben alle Preprints im Internet veröffentlicht. Der größte Teil der Forschungsarbeit wird von einer dieser Personen geleistet.

Der wahrscheinlich beste Ausgangspunkt ist das metamorphe Testen: Ein Überblick über Herausforderungen und Chancen sowie eine Umfrage zum metamorphen Testen . Obwohl dieser Artikel über metamorphe Tests geschrieben wurde , wendeten die Forscher metamorphe Beziehungen im Allgemeinen auch auf eine Vielzahl anderer Disziplinen an, beispielsweise die formale Codeüberprüfung und das Debuggen. Ich habe diese Anwendungsbereiche der Technik noch nicht im Detail untersucht, aber es lohnt sich wahrscheinlich, sie auch zu betrachten.

Unter dem Gesichtspunkt der Anwendbarkeit kann es theoretisch möglich sein, die meisten PBT-Bibliotheken anzupassen, um metamorphe Eigenschaften zu verifizieren. Tatsächlich ist das erste Beispiel in Quickcheck das Testen von MS, und in diesem Aufsatz über PBT wird MS indirekt angewendet. Im Allgemeinen scheint es mir, dass sich die meisten PBT-Untersuchungen darauf konzentrieren, eingehende Daten effizient zu generieren und zu kürzen, und die MT-Forschung konzentriert sich hauptsächlich darauf, zu bestimmen, was wir wirklich testen müssen. Folglich ergänzen sich diese Techniken wahrscheinlich.

Vielen Dank an Brian Ng für die Unterstützung bei der Recherche.

Nachtrag: Anfrage

Tatsächlich ist es nicht verwunderlich, dass ich noch nie von dieser Technik gehört habe. Es gibt viele wirklich interessante und nützliche Techniken, die ihre winzige Blase nicht verlassen konnten. Ich habe eher durch Glück als durch aktive Suche von MTs erfahren.

Wenn Sie etwas wissen, das es wert ist, weit verbreitet zu sein, schreiben Sie mir bitte .

---

1. Nun, es kann offensichtliche Probleme geben: Es kann Musik im Podcast geben, Sprachfragmente in anderen Sprachen usw. Die Theorie ist jedoch zuverlässig: Wenn wir Sprachproben erhalten können, können wir sie als Teil der Tests ohne vorläufige manuelle Transkription / Markup verwenden.
2. In Spezifikationen ist die entsprechende Idee Hypereigenschaften - Eigenschaften von Verhaltenssätzen und nicht einzelne Verhaltensweisen. Die meisten hyperspezifischen Studien beziehen sich auf die HS-Sicherheit. So wie ich es verstehe, sind seine HS eine Obermenge von MS.
3. Ich hatte eine zweite, jetzt widerlegte Hypothese: Da die meisten Hauptforscher aus China und Hongkong diese Technik vielleicht besser in Gemeinschaften von Programmierern kennen, die auf Mandarin kommunizieren, als auf Englisch. Brian Eun testete diese Hypothese für mich, fand jedoch keine signifikanten Anzeichen für die Anwendung der Technik durch die Chinesen.