Ich dachte, wir könnten heute über randomisiertes Testen, auch Fuzzing genannt, sprechen. Das ist eine wirklich effektive Technik, um Fehler in Software zu finden. Wo genau das Fuzzing seinen Ursprung hat, ist tatsächlich etwas umstritten. Das ist eine dieser Techniken, die ziemlich offensichtlich sind. Man hat also eine Software, und wenn wir als Programmierer Software entwerfen, denken wir normalerweise darüber nach, was die Software leisten soll , wie die Leute sie benutzen sollen und welche Fehler sie dabei natürlicherweise machen würden. Wir denken nicht oft über absolut verrückte Möglichkeiten nach, die Software einzusetzen. Wenn Sie beispielsweise eine Textverarbeitungsanwendung hätten , würden Sie über das Layout nachdenken, über die Funktionen, die sie unterstützen sollte, und über Dinge wie den Fall, dass der Benutzer versucht, eine nicht existierende Datei zu öffnen. Aber man denkt vielleicht nicht unbedingt an Fälle, in denen sie ein Dokument erstellen, in das sie alle möglichen verrückten Inhalte einfügen, oder man denkt vielleicht nicht daran, dass sie beispielsweise versuchen, eine Videodatei mit dem Textverarbeitungsprogramm zu öffnen, und was dann passieren würde. Softwarefehler treten häufig aufgrund unerwarteter Eingaben auf, an die der Programmierer nicht gedacht hat. Randomisierte Tests sind eine hervorragende Methode, um solche unerwarteten Eingaben zu finden. Fuzzing ist im Internetzeitalter immer wichtiger geworden, denn wenn man an Systeme wie Webbrowser wie Chrome, Safari und Firefox denkt, die von Milliarden von Nutzern weltweit verwendet werden, handelt es sich um völlig offene Systeme. Bei einem Phishing-Angriff, bei dem man jemanden dazu verleitet, auf eine Webseite zu klicken, die ihn dann auf eine zufällige, bösartige Webseite weiterleitet, kann diese Webseite beliebigen Inhalt haben. Daher muss der Webbrowser auch gegenüber völlig beliebigem HTML robust sein. Es muss nicht unbedingt etwas Sinnvolles für das HTML gerendert werden, aber es darf nicht der Fall sein, dass zufälliges HTML oder JavaScript eine Sicherheitslücke im Webbrowser aufdeckt. Und angesichts der jüngsten Nachrichten über Dinge wie Claude Mythos, Sie wissen schon, das große Sprachmodell, über das es einige Bedenken gibt, wenn von Sicherheitslücken die Rede ist, geht es um Dinge wie Eingaben, die dazu führen könnten, dass sich ein offenes System wie ein Webbrowser nicht nur falsch verhält, sondern tatsächlich den Einstiegspunkt für beispielsweise einen Remote-Execution- Angriff bietet. Das ist genau die Art von Dingen, die den Leuten Sorgen bereiten . Und Fuzzing ist eine wirklich gute Methode, um sich gegen solche Probleme zu verteidigen, denn durch das Testen eines Systems mit zufälligen Eingaben kann man möglicherweise zufällig auf einige dieser Hintertüren stoßen. Es gibt im Grunde zwei Extreme, was die Leute mit Fuzzing erreichen wollen. Im einen Extremfall möchte man Software stichprobenartig mit verstümmelten, bösartigen Eingaben testen, die eigentlich nicht in die Software gelangen sollten, mit dem Ziel, Schwachstellen in der Software zu finden. Am anderen Ende des Spektrums möchte man die Software vielleicht mit sehr sorgfältig ausgearbeiteten, wohlgeformten, aber extrem komplizierten Eingaben testen und tatsächlich herausfinden, ob die Software bei solchen Eingaben das Richtige getan hat. Und die Forscher sind an fortschrittlichen Techniken an beiden Enden des Spektrums interessiert. Vielleicht beginne ich damit, über die verschiedenen Möglichkeiten zu sprechen, wie man Fuzzing, auch bekannt als randomisiertes Testen, zum Testen komplexer Systeme einsetzen kann, um sicherzustellen, dass sie tatsächlich korrekt funktionieren . Ein wirklich gutes Beispiel hierfür sind Compiler. Compiler wie GCC oder Clang für C oder Java C für Java. Und es gibt sehr viele Programmiersprachen mit oft mehreren Compilern pro Sprache. Und ein Compiler kann, wie jedes Programm, abstürzen, wenn man ihm eine erwartete oder unerwartete Eingabe gibt. Möglicherweise liegt ein Fehler vor, der schlichtweg zum Absturz des Compilers führt . Bei einem Compiler gibt es jedoch eine noch schlimmere Art von Fehler, die als Fehlkompilierung bekannt ist. Dabei übergibt man dem Compiler Quellcode, und der Compiler wandelt diesen ohne Beanstandung in Binärcode um. Es wandelt den Code in ausführbaren Objektcode um und gibt dabei keinen Hinweis darauf, dass etwas schiefgelaufen ist. Die Übersetzung des Quellcodes in den ausführbaren Binärcode hat jedoch die Bedeutung des Programms nicht korrekt wiedergegeben. Die Semantik des Quellprogramms wurde nicht beachtet. Um ein unrealistisch einfaches Beispiel zu nennen: Wenn das Programm x + y ausgibt und der Compiler dies in eine Multiplikationsanweisung übersetzt, die x mit y multipliziert, dann wäre das eine Fehlkompilierung. Wir hoffen natürlich, dass einem Compiler niemals ein so drastischer Fehler unterläuft, aber Compiler führen bei der Übersetzung von Quellcode in Assembler wirklich ausgeklügelte Optimierungen durch, und diese Optimierungen können Randfälle aufweisen, an die der Compiler-Entwickler nicht gedacht hat, und sie funktionieren möglicherweise nicht in allen Umgebungen. Sie sollten, aber vielleicht tun sie es nicht. Ein wirklich interessanter Arbeitszweig, bei dem Fuzzing zum Testen von Compilern eingesetzt wird, besteht darin, einen Fuzzer zu erstellen, einen Zufallsgenerator, der zufällig Programme in einer gegebenen Programmiersprache erzeugt, die eigentlich wohlgeformte Programme sein sollten. Sie würden nichts Sinnvolles tun, sondern lediglich die Besonderheiten der Sprache auf alle möglichen seltsamen und wunderbaren Arten nutzen. Sie sollen nicht etwa keinen gewünschten Effekt erzielen, sondern lediglich sicherstellen, dass beim Ausführen eines dieser zufällig generierten Programme eine Ausgabe entsteht. Vielleicht würde es einfach eine ganze Zahl ausgeben. Welche ganze Zahl das wäre, hinge vollständig von der zufälligen Struktur des Programms ab. Die Herausforderung besteht jedoch darin, Programme zu generieren, die bei ihrer Ausführung ein deterministisches ganzzahliges Ergebnis liefern. Dann können Sie beispielsweise, wenn Sie zwei Compiler zu testen haben, sagen wir der Einfachheit halber GCC, den GNU C- Compiler, und Clang, einen weiteren sehr bekannten Open-Source-Compiler für C und C++ . Wenn Sie einen Fuzzer haben, also eine Software, die Programme generiert, dann wird der Fuzzer ein Programm generieren. Der Inhalt dieses Programms wird also vom Fuzzer zufällig bestimmt. Das Programm wird jedoch ein vollständig deterministisches Programm sein. Wir können dieses Programm an GCC oder Clang übergeben, und diese kompilieren es dann zu ausführbaren Dateien. Nennen wir sie also 1.exe und 2.exe. Wenn wir nun diese ausführbaren Dateien mit derselben Eingabe ausführen, sagen wir, wir geben ihnen eine Eingabe I und geben ihnen beiden dieselbe Eingabe I, dann liefert uns dieses Programm eine Ausgabe O1. Und dieses Programm liefert uns einen Ausgang O2. Dann sollten diese Ausgaben gleich sein. Der Fuzzer hat ein Programm generiert. Wir haben dieses Programm beiden Compilern übergeben. Wir haben das Programm kompiliert, um zwei ausführbare Dateien zu erhalten. Diese ausführbaren Dateien könnten sich stark voneinander unterscheiden, da die Compiler möglicherweise unterschiedliche Entscheidungen hinsichtlich der Codeoptimierung getroffen haben. Sie werden also unterschiedliche Methoden zur Erzeugung einer Binärdarstellung des Quellcodes verwenden, aber diese Binärdarstellungen sollten dasselbe kodieren. Beide sollten die Semantik dieses Programms kodieren. Wenn wir sie dann mit der gleichen Eingabe ausführen, sollten wir erwarten, die gleiche Ausgabe zu erhalten. Und wenn das nicht der Fall ist, deutet das darauf hin, dass bei der Kompilierung etwas schiefgelaufen ist . Irgendwo in einem dieser Compiler muss ein Fehler vorliegen. Hierbei sind jedoch einige wichtige Einschränkungen zu beachten. Für Ihre Zuschauer, die sich mit C und C++ auskennen: Diese Sprachen sind voller undefiniertem Verhalten. Und wenn dieses Programm undefiniertem Verhalten unterliegt, könnte es sein, dass diese ausführbaren Dateien aufgrund des undefinierten Verhaltens tatsächlich unterschiedliche Ergebnisse liefern. Die eigentliche Herausforderung besteht also darin, sicherzustellen, dass es in diesem Programm kein undefiniertes Verhalten, kein UB gibt . Ist das dann ein Beispiel für undefiniertes Verhalten? In C ist ein Beispiel für undefiniertes Verhalten die Division durch Null. Okay. Das führt also häufig zum Absturz des Programms , aber das ist nicht garantiert. Der Programmcode besagt nicht, dass eine Division durch Null zum Absturz des Programms führt. Es ist tatsächlich undefiniert. Ein weiteres Beispiel ist das Lesen aus einem Array außerhalb seiner Grenzen, also ein Array- Überlauf oder ein Array-Unterlauf. Und es gibt tatsächlich eine große Anzahl von Beispielen für undefiniertes Verhalten in der Sprache. Das ist ein Beispiel für randomisiertes Testen im Bereich der Compiler. Und es gibt ein Tool namens Csmith, das ursprünglich von der University of Utah stammt. Also, weil es eine Sammlung von C-Programmen ist. Und Csmith ist der Fuzzer, der diese randomisierten C- Programme erzeugt. Die entscheidende Innovation dieses Csmith-Projekts besteht genau darin, Programme zu entwickeln, die dieses undefinierte Verhalten nicht aufweisen. Okay. Dies ist also ein Beispiel für Fuzzing, um tiefgreifende funktionale Fehler in einem komplizierten Softwareprodukt, einem Compiler, aufzuspüren. Es geht nicht darum, Sicherheitslücken zu finden, bei denen der Compiler abstürzt und eine ausnutzbare Schwachstelle entsteht, wenn man ihm unverständlichen Code zuführt. Das ist nicht der Zweck dieser Unschärfe. Es geht eigentlich darum, tiefgreifende Probleme zu finden, bei denen der Compiler ein Programm tatsächlich falsch optimiert. Das Programm enthält einen echten Fehler. Okay. Und kommt man an einen Punkt, an dem man ein Problem damit kategorisch beweisen kann , oder ist es ein bisschen wie in jeder Wissenschaft, wo man es tausendmal testen kann und alle Tests scheinbar in Ordnung sind, und man deshalb trotzdem nicht beweisen kann, dass es in Ordnung ist, weil der eintausendunderste Test ein Fehler sein könnte? Genau. Generell geht es bei Softwaretests jeglicher Art also darum, das Vorhandensein von Fehlern aufzuzeigen, nicht darum, die Abwesenheit von Fehlern zu beweisen. Man kann also nicht mit Tests nachweisen, dass Software korrekt ist. Man kann es nur verwenden, um zu zeigen, dass die Software fehlerhaft ist. Doch der Prozess, bei dem wiederholt gezeigt wird, dass die Software fehlerhaft ist, diese Fehler behoben werden und es dann immer schwieriger wird, Fehler in der Software zu finden, beweist, dass die Software immer zuverlässiger wird. Ein sehr schwieriges Problem, an dem einige Akademiker interessiert sind – ich finde es interessant, aber es ist nichts, worüber ich mir Sorgen mache –, ist die Frage: Woher weiß man, dass man alle Fehler gefunden hat? Meine praktische Erfahrung aus meiner Zeit in verschiedenen Unternehmen lässt mich vermuten, dass man das nie tut. Man findet nie alle Fehler. Es sei denn, Sie arbeiten an sicherheitskritischer Software mit hohen Anforderungen an die Sicherheit, wo Sie tatsächlich formale Verifikation einsetzen, um die Korrektheit der Software nachzuweisen. Wenn Sie nicht in diesem Bereich arbeiten, dann enthält jede Software Fehler. Ja . Und dann stellt sich die sehr relevante Frage: Welche Fehler sind Ihnen wichtig? Interessieren Sie sich also für all diese Fehler, die Fuzzer finden können? Fuzzer finden also manchmal Probleme, die eigentlich Bugs sind, aber ob jemals jemand auf eine Datei mit einem dieser Bugs stoßen würde, ist fraglich, und das ist an sich schon eine interessante Frage. Das Problem bei all dem ist, dass wir mit den Systemen, die wir heute verwenden, natürlich – ich meine, ich muss da an den XKCD-Comic „ The Nebraska“ denken. Das Nebraska-Modell mit dem winzigen, wissen Sie, man kann sich ansehen, was man da sieht, aber es könnte auf so vielen anderen möglichen Frameworks und Plattformen aufbauen. Das ist richtig. Diese Techniken müssen also unter Berücksichtigung des jeweiligen Kontextes eingesetzt werden. Ich denke, Sie wissen, dass es bei dieser Arbeit an diesen Unix- Dienstprogrammen darum geht, dass diese Dienstprogramme, obwohl einige davon sehr einfache Werkzeuge sind, von einer großen Anzahl von Menschen benutzt werden, ohne dass man wirklich weiß, wofür sie sie verwenden – für alle möglichen Dinge. Es gibt also gute Gründe dafür, sie besonders zuverlässig zu machen. Compiler – wir wissen, dass viele Unternehmen auf Compiler wie GCC und Clang angewiesen sind. Sie gehören zu den besten Beispielen für Open-Source- Projekte, die wir haben. Es gibt also ein sehr starkes Argument dafür, sie so fehlerfrei wie möglich zu gestalten. Aber mal ehrlich, spielt es wirklich eine Rolle, ob GCC abstürzt, wenn man ihm eine Datei voller nicht druckbarer Zeichen gibt? Wenn es nicht kompiliert, wenn es einfach mit einem schwerwiegenden Fehler abstürzt, anstatt beispielsweise einen Syntaxfehler anzuzeigen, spielt das dann wirklich eine Rolle? Ist das ein Fehler, der tatsächlich von Bedeutung ist? Ich würde sagen: Nein. Wissen Sie, selbst bei etwas so Wichtigem wie GCC ist nicht jeder Fehler in GCC von Bedeutung. Und ich möchte über Coverage-Guided Fuzzing sprechen, das durch ein Tool namens AFL ( American Fuzzy Lop) bekannt wurde. Dieses Tool stammt von einem Entwickler bei Google und hat vor einiger Zeit den Weg für eine Vielzahl praktischer Arbeiten und Forschungen im Bereich Fuzzing geebnet. Nehmen wir an, wir haben ein System, das wir testen wollen, SUT, System unter Test. Wenn wir uns die Funktionsweise des Systems wie ein Labyrinth vorstellen, dann gibt es alle möglichen Orte, an die man in diesem System gelangen kann. Wenn Sie dann eine Art zufällige Eingabe an dieses System senden, beispielsweise zufällige Bytes, dann kann es sein, dass diese in Teile der Software gelangen. Und dann wird ein weiterer Eingang ausgelöst, der in einen anderen Teil des Systems gelangt. Und dann gelangt ein weiterer Eingang in einen etwas anderen Teil des Systems. Es könnte aber sein, dass ein Eingabefeld bestimmte Merkmale aufweisen muss, um überhaupt weiter in das System gelangen zu können . Zum Beispiel kann es sein, dass man einem Linux- Dienstprogramm gültige Befehlszeilenargumente übergeben muss, um einen Großteil seines Verhaltens freizuschalten. Bei vielen Dienstprogrammen muss man beim Ausführen zahlreiche Argumente in der Befehlszeile angeben. Und wenn Sie ein bestimmtes Argument angeben, wird die Eingabe auf eine bestimmte Weise behandelt. Es kann also sein, dass Sie ganze Bereiche des Systems nie erreichen werden, es sei denn, Sie liefern das richtige Argument. Dieser Ansatz mag zwar einige pathologische Fälle aufdecken, in denen ein System abstürzt, aber es ist unwahrscheinlich, dass er Eingaben findet, die das System in wirklich tiefgreifende und interessante Zustände versetzen. Eine Technik, die dieses Problem überwindet, ist das sogenannte Coverage Guided Fuzzing. Bekannt wurde es durch ein Tool namens AFL ( American Fuzzy Lop), das vor einiger Zeit von einem Google-Ingenieur entwickelt wurde und zu zahlreichen Folgeprojekten in der Praxis sowie zu vielen akademischen Forschungsarbeiten und verschiedenen anderen Fuzzern wie beispielsweise Googles Libfuzzer geführt hat, der ein Fuzzer im AFL-Stil ist. Wenn wir uns unser zu testendes System noch einmal als labyrinthisch vorstellen, besteht die Idee des Coverage Guided Fuzzing darin, dass wir über einen Korpus von Eingaben verfügen, die während des Testprozesses verwendet werden . Anfangs könnte dieser Korpus einige Beispiele für reale Eingaben für das System enthalten. Wenn es sich bei dem System beispielsweise um eine PDF-Engine handeln würde, könnten wir eine Auswahl an Beispiel-PDFs haben, die bereits eine gewisse Abdeckung des Systems bieten. Die Idee besteht darin, Eingaben zu finden, die tiefer in das System hineinreichen, tiefer in das Labyrinth vorzudringen, in der Hoffnung, Fehler zu finden. Nehmen wir also an, dass sich irgendwo in diesem Labyrinth ein Fehler versteckt. Die Idee ist, dass wir nicht wissen, wo dieser Fehler liegt, aber durch die Erkundung des Labyrinths hoffen wir, einen oder mehrere dieser Fehler zu finden, die behoben werden können, um das System zuverlässiger zu machen. Die Idee des abdeckungsbasierten Fuzzings ist folgende: Angenommen, dieser Korpus enthält eine Reihe von Eingaben, aber anfänglich enthält er vielleicht eine Eingabe A. Und hier meine ich nicht wörtlich das Zeichen A. Ich bezeichne A einfach als die Eingabe. A könnte beispielsweise eine PDF-Datei sein. Der Fuzzer wird dann den Input A aus dem Korpus extrahieren. Und dann wird A zufällig mutiert, um eine mutierte Eingabe zu erhalten. Nennen wir es eine Primzahl. Die Mutationen, die durchgeführt werden, um von einer Eingabe A zu A prime zu gelangen, werden zufällig angewendet und können beispielsweise das Umdrehen eines Bits, das Ersetzen einer Bytefolge durch eine andere Bytefolge, das Löschen einiger Bytes aus der Eingabe oder das Zusammenfügen zweier Eingaben umfassen. Nun wird also diese A-Prime dem zu testenden System zugeführt. Und A Prime wird eine gewisse Abdeckung des Systems erreichen, was wir als einen gewissen Fortschritt in diesem Labyrinth betrachten können. Wenn also dieser Fortschritt durch das Labyrinth, den A prime gemacht hat, bedeutet, dass wir zu Teilen des Labyrinths, Teilen der Software gelangen, die beim Fuzzing noch nie zuvor erreicht wurden , dann wird diese Eingabe A prime als eine interessante Eingabe angesehen, die für weitere Überlegungen nützlich sein könnte . Also wird es wieder in den Korpus aufgenommen. Nennen wir es eine Primzahl. Ich bin hier etwas uneinheitlich mit den Farben. Das ist inOrdnung. Wir haben es verstanden. Wir haben es verstanden. Okay. Nehmen wir also an , es gäbe noch eine weitere Eingabe in diesem Korpus. Nennen wir es B. Und der Fuzzer hat B herausgezogen und eine Mutation darauf angewendet, um B' zu erhalten . Und dann wird B' an das SUT, das zu testende System, angelegt. Nehmen wir an, B' wiederholt einen Teil des Weges, den A' gegangen ist. Es erreicht also einen Teil der Abdeckung, vielleicht sogar die gesamte Abdeckung, die A Prime erreicht hat, aber keine größere Abdeckung. Dann wird B prime als uninteressant angesehen. Es ging nicht weiter. Von B prime haben wir nichts Neues gesehen . Es wird also nicht wieder in den Korpus aufgenommen, um weiteren Mutationen ausgesetzt zu werden. Nehmen wir aber an, dass A prime vom Fuzzer erneut ausgewählt und in eine Form A prime prime mutiert wird. Und wenn wir dies dem Fuzzer übergeben, dringt dieser tatsächlich ein Stück weiter in das zu testende System ein. Das ist ja toll. Ein absolutes Highlight ist es, Orte zu erreichen, die wir noch nie zuvor gesehen haben. Das ist interessant. Und es wird wieder in den Korpus aufgenommen, um in Zukunft berücksichtigt zu werden. Die Idee besteht darin, diesen Prozess schnell durchzuführen, idealerweise tausend- oder zehntausendmal pro Sekunde, und die Eingaben anhand der Abdeckung zu verändern. Neue Abdeckung ist also interessant, um sie immer ausgefeilter zu gestalten und tiefer in das System einzudringen. Und wenn wir Glück haben, ist es vielleicht das dritte Mal, dass wir diese Eingabe verändern. Wir gehen also von A prime prime aus. Nennen wir es A prim prim prim . Wenn wir dies dem System geben, könnte es sein, dass dies nun noch mehr Verbreitung findet und – zack! – dieser Fehler auftritt. Das System stürzt ab. Das ist ausgezeichnet. Wir haben eine Eingabe gefunden: Eine Primzahl, die zum Systemabsturz führt. Und nun kann unser Entwickler nachsehen, was falsch läuft und den Fehler beheben. Das ist also abdeckungsgesteuertes Fuzzing. Dies können wir als Beispiel für einen evolutionären Algorithmus betrachten. Wir haben eine Population, den Korpus, und wir haben das Konzept der zufälligen Mutation von Eingaben, also zufällige Mutationen in der Population. Ich erwähnte auch, dass eine der Mutationen darin besteht, mehrere Eingangssignale zu nehmen und sie miteinander zu verbinden, also Eingangssignale zu neuen Eingangssignalen zu verpaaren. Und wir haben eine Fitnessfunktion, sodass diese Eingaben nur dann überleben, nur dann wieder in den Korpus aufgenommen werden, wenn sie fit sind, was bedeutet, dass sie eine neue Abdeckung erhalten. Bei diesem Fuzzing- Ansatz geht es also darum, einen Korpus von Eingaben in immer komplexere Eingaben zu verwandeln, die immer tiefer in das zu testende System eindringen, um Fehler auszulösen. Nehmen wir an, wir haben ein Hilfsprogramm, das Befehlszeilenoptionen akzeptiert , zum Beispiel {dash} {dash}. Die Wahrscheinlichkeit, dass eine Eingabe mit einem Bindestrich am Anfang beginnt, ist ziemlich hoch. Es gibt nicht so viele Zeichen, und nach vielen Iterationen werden wir wahrscheinlich einen {Dash} finden, und es wird Code geben, der Befehlszeileneingaben verarbeitet, und dieser Code wird etwas tiefer, wenn wir einen {Dash} angeben. Wenn das nächste Zeichen aber kein Bindestrich ist, dann haben wir nicht {Bindestrich} {Bindestrich}, was den Beginn einer Eingabe darstellt. Da wir aber einen Bindestrich gefunden haben, wird dieser wieder in den Korpus aufgenommen. In Zukunft ist es recht wahrscheinlich, dass eine Mutation einen zweiten Bindestrich hinzufügt, und später werden wir beispielsweise den Buchstaben O und dann N usw. erhalten. Nach vielen, vielen, vielen Iterationen – aber nicht astronomisch vielen – wird der Fuzzer implizit das erwartete Eingabeformat erkennen und tiefer in das System eindringen. Wenn ich das Ganze nun umdrehe und der gesamte zweite Thread vor dem gesamten ersten Thread ausgeführt würde, hätte ich die symmetrische Situation, in der A gleich eins und B gleich null wäre. Die Frage ist, hätte ich auch beobachten können, dass A null und B null ist?