Provably Lossless Acceleration of DNN Mutation Testing via Memoization

Stellen Sie sich vor, Sie versuchen einem Roboter beizubringen, Katzen zu erkennen. Sie bauen ein riesiges, komplexes Gehirn aus Schichten winziger Schalter (Neuronen), das aus Tausenden von Bildern lernt. Aber woher wissen Sie, ob Ihr Roboter wirklich intelligent ist oder nur Glück hatte? In der Welt des Softwaretestens gibt es einen cleveren Trick namens „Mutation Testing“. Es ist wie ein Spiel von „Such das Bild“, bei dem Sie das Gehirn des Roboters absichtlich auf winzige, zufällige Weise kaputt machen – einen Schalter hier umlegen, ein Kabel dort verdrehen – um zu sehen, ob Ihre Testbilder gut genug sind, um den Fehler zu entdecken. Wenn Ihr Roboter immer noch denkt, dass ein Hund eine Katze ist, nachdem Sie ihn manipuliert haben, dann erfüllen Ihre Tests ihre Aufgabe nicht.

Das Problem ist, dass dieses Spiel unglaublich langsam und teuer ist. Um das Gehirn eines modernen Roboters zu testen, müssen Sie das Gehirn vielleicht tausendfach beschädigen und es jedes Mal durch Millionen von Bildern laufen lassen. Es ist, als würde man versuchen, eine Nadel im Heuhaufen zu finden, indem man den gesamten Heuhaufen immer wieder neu aufbaut, ein winziges Stück Stroh bricht und dann das gesamte Ganze erneut überprüft – immer und immer wieder. Die meisten Menschen, die versuchen, dies zu beschleunigen, haben ein wenig geschummelt und Abkürzungen genutzt, die Ergebnisse erraten. Aber in der Wissenschaft zu raten ist riskant; wenn Sie falsch raten, glauben Sie vielleicht, Ihr Roboter sei sicher, obwohl er eigentlich defekt ist. Dieses Paper stellt eine neue Art und Weise vor, das Spiel zu spielen, die schnell ist, aber sich weigert zu schummeln.

Die „Copy-Paste“-Abkürzung für Robotergehirne

Lernen Sie Mure kennen (ausgesprochen wie „moo-ray“), ein neues Werkzeug, das von den Forschern Ali Ghanbari, Ben Greenman, Sasan Tavakkol und Shibbir Ahmed entwickelt wurde. Stellen Sie sich ein Deep Neural Network (das Gehirn des Roboters) wie ein langes Fließband in einer Fabrik vor. Rohmaterialien (die Bilder) treten am Anfang ein, passieren viele Stationen (Layer) und kommen als fertiges Produkt (die Antwort) heraus.

Wenn Sie die Fabrik testen wollen, indem Sie eine Maschine ganz am Ende der Linie kaputt machen, müssen Sie nicht jedes Mal die gesamte Fabrik von Grund auf neu aufbauen. Sie müssen nur die kaputte Maschine und die wenigen Stationen danach reparieren bzw. anpassen. Die Stationen vor dem Bruch sind exakt dieselben wie in der ursprünglichen Fabrik.

Mure verwendet eine Technik namens Memoization, was ein schickes Wort für „sich merken, was man bereits getan hat“ ist. So funktioniert es in der realen Welt:

1. Das Fließband: Stellen Sie sich vor, Sie haben eine Fabrik, die 100 leicht unterschiedliche Versionen eines Spielzeugautos herstellt. Bei 99 davon sind die ersten 10 Schritte der Montagelinie identisch. Nur die letzten 2 Schritte sind unterschiedlich.
2. Die alte Methode (Vanilla Testing): Die alte Methode würde für jede einzelne Version das gesamte Auto von Grund auf neu bauen. Sie würde die ersten 10 Schritte durchlaufen, dann die letzten 2, dann wieder von vorne beginnen, die ersten 10 Schritte erneut durchlaufen, dann die letzten 2, und so weiter. Das ist viel verschwendete Energie.
3. Der Mure-Weg: Mure sagt: „Moment mal! Die ersten 10 Schritte sind für alle gleich.“ Also führt es die ersten 10 Schritte einmal aus und speichert das Ergebnis in einer „Memo-Tabelle“ (wie ein Klebezettel an der Wand). Dann greift es für jedes einzelne mutierte Auto einfach auf den Klebezettel zu, überspringt die ersten 10 Schritte und baut nur noch die letzten 2 Schritte fertig.

Die große Entdeckung: Geschwindigkeit ohne zu schummeln

Die Forscher haben mathematisch bewiesen, dass Mure beweisbar verlustfrei (lossless) ist. Das ist der wichtigste Teil. In der Vergangenheit versuchten andere Tools, die Dinge zu beschleunigen, indem sie Abkürzungen nahmen, die einige Fehler übersehen könnten (sie waren „lossy“ bzw. verlustbehaftet). Sie waren wie ein Koch, der die Suppe probiert, aber die Kontrolle über das Salz auslässt, in der Hoffnung, es sei schon in Ordnung. Mure ist anders; es ist ein Koch, der das Salz exakt so prüft wie das Originalrezept, nur dass er statt jedes Mal abzuwiegen, einen vorgefertigten Messbecher verwendet.

Das Paper beweist, dass Mure exakt dieselben Ergebnisse liefert wie die langsame, langweilige „Alles-von-vorne-erstellen“-Methode. Es übersieht keine defekten Roboter. Es erledigt die Arbeit nur schneller.

Was die Zahlen sagen

Das Team hat Mure an 15 verschiedenen Robotergehirnen aller Formen und Größen getestet, von einfachen bis hin zu massiven, komplexen Systemen mit Millionen von Teilen. Sie führten diese Tests auf Standardcomputern durch (keine speziellen Supercomputer oder Grafikkarten wurden verwendet).

• Der Geschwindigkeitsgewinn: Im Durchschnitt machte Mure den Testprozess um 44,54 % schneller. Das bedeutet, wenn ein Test früher 100 Minuten gedauert hätte, dauert er jetzt etwa 55 Minuten.
• Der Kompromiss: Sie verglichen Mure mit anderen „schummelnden“ Abkürzungen (genannt DM# und BSS). Diese Abkürzungen waren sogar noch schneller (bis zu 88,97 % schneller), aber sie machten Fehler. Sie sagten manchmal, ein Roboter sei in Ordnung, obwohl er eigentlich defekt war, oder umgekehrt. Mure weigerte sich, solche Fehler zu machen.
• Der „Wie viel hast du kaputt gemacht?“-Test: Die Forscher fragten auch: „Was ist, wenn wir mehr vom Roboter kaputt machen?“ Sie testeten das Beschädigen von 1 %, 3 % und 5 % der Neuronen des Roboters. Je mehr Teile sie beschädigten, desto kleiner wurde der Geschwindigkeitsvorteil (da weniger von den „ersten 10 Schritten“ zum Wiederverwenden übrig blieb). Selbst als sie 5 % der Neuronen beschädigten, bot Mure immer noch einen Geschwindigkeitsvorteil von 20 %.

Warum das wichtig ist

Hier geht es nicht nur darum, Zeit zu sparen; es geht um Vertrauen. In sicherheitskritischen Bereichen wie selbstfahrenden Autos oder der medizinischen Diagnose kann man sich keine Vermutungen leisten. Wenn ein Test sagt, ein Auto sei sicher, muss er sich zu 100 % sicher sein. Mure ermöglicht es Ingenieuren, diese schweren, teuren Sicherheitsprüfungen viel schneller durchzuführen, ohne dabei die 100-prozentige Gewissheit aufzugeben.

Die Forscher haben gezeigt, dass man durch einen klugen Umgang damit, welche Teile des Gehirns man wiederverwendet, die Kosten für das Testen fast halbieren kann. Sie haben nicht nur geraten, dass dies funktionieren würde; sie haben das Werkzeug gebaut, die Experimente durchgeführt und die Mathematik bewiesen. Es ist eine Erinnerung daran, dass der beste Weg, schnell zu sein, manchmal nicht darin besteht, härter zu arbeiten, sondern sich zu merken, was man bereits getan hat.