Fuzzer

Fuzzer sind Programme die ein automatisiertes Testen ermöglichen. Im Gegensatz zu herkömmlicher Testsoftware, werden beim fuzzen zufällige Testcases generiert. In erster Linie soll damit getesten werden ob Progamme für nichtspezifizierten Input abstürzen oder hängen bleiben.

Einsatzgebiete

Primär wird Fuzzing zum Suchen von Schwachstellen und Sicherheitslücken benützt. Sicherheitslücken entstehen meist daraus, dass Nutzereingaben nicht hinreichend genau überprüft werden. Beispiele sind z.B. Bufferüberläufe, Formatstingattacken, SQL Injections oder Cross Site Scripting. Durch Fuzzing können Eingaben gefunden werden, die das entsprechende Programm zum absturz bringen. Im Falle von Diensten die über das Netzwerk erreichbar sind, kann dies schon ausreichen um Denial of Service Attacken durchzuführen. In schwerwiegenderen Fällen kann die Schwachstelle dafür sorgen, dass Fremde Zugriff auf das System erhalten. Eine prominente Lücke, die lange Zeit nicht entdeckt wurde ist Heartbleed. Diese hätte durch Fuzzing entdeckt werden können. https://blog.hboeck.de/archives/868-How-Heartbleed-couldve-been-found.html

AFL (American Fuzzy Lop)

AFL von Michal Zalewski ist ein offener leicht zu bedienender Fuzzer. Es kann unter http://lcamtuf.coredump.cx/afl/ heruntergeladen werden. Er ermöglicht das Fuzzen von Programmen, die Eingaben über Dateien oder stdin entgegennehmen. Für die Benutzung ist fast keine Konfiguration nötig. Es werden lediglich ein Testcase und das zu Testende Programm benötigt. AFL ändert die gegebenen Testcases zufällig ab (Mutationen) und testet das Programm auf Abstürze und Ausführgeschwindigkeit.

Installation

In einigen Linux Distributionen ist AFL vorkompiliert enthalten und kann direkt über den jeweiligen Paketmanager heruntergeladen werden. Ist AFL nicht vorhanden, so kann es wie folgt leicht selbst kompiliert werden:

  wget http://lcamtuf.coredump.cx/afl/releases/afl-latest.tgz
  tar -xvf afl-latest.tgz 
  cd afl-*
  make

Mit wget wird die letzte Version von afl runtergeladen und dann mit tar entpackt. Dann wird in den afl-* Ordner gewechselt. Hier kann man nun entscheiden ob man afl richtig installiernen möchte (make install) oder die c-Dateien nur übersetzten möchte (make).

Konfiguration

AFL benötigt eigentlich keinerlei Konfiguration. Beim start von afl-fuzz kann es aber sein, dass afl auf Einstellungen im System hinweist, die negativen Einfluss auf afl haben und die dementsprechend umgestellt werden sollten. Hiervon nun zwei Beispiele vorgestellt, die bei uns oft aufgetretten sind.

  [-] Hmm, your system is configured to send core dump notifications to an
      external utility. This will cause issues due to an extended delay
      between the fuzzed binary malfunctioning and this information being
      eventually relayed to the fuzzer via the standard waitpid() API.
  
      To avoid having crashes misinterpreted as hangs, please log in as root
      and temporarily modify /proc/sys/kernel/core_pattern, like so:
  
      echo core >/proc/sys/kernel/core_pattern
  
  [-] PROGRAM ABORT : Pipe at the beginning of 'core_pattern'
           Location : check_crash_handling(), afl-fuzz.c:6926

  [-] Whoops, your system uses on-demand CPU frequency scaling, adjusted
      between 781 and 3710 MHz. Unfortunately, the scaling algorithm in the
      kernel is imperfect and can miss the short-lived processes spawned by
      afl-fuzz. To keep things moving, run these commands as root:
  
      cd /sys/devices/system/cpu
      echo performance | tee cpu*/cpufreq/scaling_governor
  
      You can later go back to the original state by replacing 'performance' with
      'ondemand'. If you don't want to change the settings, set AFL_SKIP_CPUFREQ
      to make afl-fuzz skip this check - but expect some performance drop.
  
  [-] PROGRAM ABORT : Suboptimal CPU scaling governor
           Location : check_cpu_governor(), afl-fuzz.c:6988

Die Fehlermeldungen sind selbsterklärend und können mit den angegebenen Hinweisen leicht behoben werden. Die Einstellungen sind nur temporär und müssen nach einem neustart des Systems wiederholt werden.

Funktionsweise

Folgender Programmablaufplan zeigt oberfläschlich die Funktionsweise von AFL

Naiver Programmablaufplan von AFL.

AFL mutiert zunächst seinen aktuellen Testcase und benutzt diesen dann als Eingabe für das Testprogramm. Stürzt das Programm ab oder bleibt es hängen, so wird die Eingabe für spätere Tests abgespeichert. Anschließend wird die Eingabe weiter mutiert und der Ablauf beginnt von vorne. Das Ende des Programmablaufes ist von AFL selbst nicht vorgesehen und muss durch den Nutzer erfolgen.

Mit afl-fuzz wird AFL gestartet. afl-fuzz benötigt zwingend einen Eingabeordner, der mindestens einen Testcase in form einer Datei enthällt und einen Ausgabeordner, in dem es seine Ergebnisse und temporäre Dateien abspeichern kann. Dies sieht wie folgt aus:

  afl-fuzz -i [Eingabeordner] -o [Ausgabeordner] [Testprogramm]

Testbeispiele

Beispiel1.c:

  #include <stdio.h>
  #include <string.h>
  
  int main (int argc, char **argv) {
    char test[10];
    gets(test);
    printf("Eingabe: %s\n",test);
    return 0;
  }

Beispiel1.c hat ein offensichtliches Problem mit Buffer Overflows. Dies soll der Fuzzer für uns herausfinden. Erstmal übersetzten wir Beispiel1.c mit "gcc -o Beispiel1 Beispiel1.c". Dann setzten wir den Fuzzer auf Beispiel1 an mit: "afl-fuzz -n -i testcases/other/text/ -o out Beispiel1". Mit -n läuft afl als "dumb" fuzzer. Das heißt er hat keine nähere Informationen über die interne Strucktur und den internen Aufbau von Beispiel1 und kann diese somit auch nicht nutzen. Mit -i wird ein Ordner angegeben der die Testcases enthält die als Input für das Programm verwendet werden sollen. In testcases/other/text/ ist nur die hello_world.txt von hello drin steht. Das heißt mit dem Word hello fängt der fuzzer als eingabe an und verändert dies danach auf unterschiedliche weise. Der Ausgabeordner wo die Ergebnisse und anderes gespeichert werden wird mit -o angegeben und muss gegebenenfalls erst erstellt werden. Beispiel1 ist unser Programm was wir fuzzen wollen. Die Eingaben die zu einen Crash oder Hang geführt haben werden im Ausgabeordner unter Crashes oder Hangs gespeichert. Crashes sind mit hoher Warscheinlichkeit richtige Crashes. Bei Hangs muss man durchprüfen ob die Eingaben wirklich zu einen Hang geführt haben, hier gibt es viele False Positives. Also zählen letztendlich nur Crashes. Testen können wir diese mit "cat out/crashes/id:000000* | Beispiel1". Mit "cat out/.cur_input" kann man sich die gerade genutzte Eingabe ansehen.

Beispiel2.c:

  #include <stdio.h>
  #include <stdlib.h>
  
  int main (int argc, char **argv) {
    char buf [128];
    fgets(buf,128,stdin);
    printf(buf);
    printf("Hello\n");
    return 0;
  }

Beispiel2.c hat ein offensichtliches Problem mit Formatstringangriffen. Dies soll der Fuzzer für uns herausfinden. Erstmal übersetzten wir Beispiel2.c mit "gcc -o Beispiel2 Beispiel2.c". Zusätzlich fügen wir einen weiteren testcase unter testcases/other/text/ hinzu, indem wir eine Datei formatstring.txt erzeugen und dort %s reinschreiben. Um von hello mittels Mutation auf irgendetwas mit %s%s%s zu kommen, benötigt der Fuzzer circa eine Stunde. Gibt man aber einen zusätlichen testcase an, der %s enthält, dauert dies nur wenige Minuten. Dann setzten wir den Fuzzer auf Beispiel2 an mit: "afl-fuzz -n -i testcases/other/text/ -o out Beispiel2".

Diese Art des Fuzzens mit -n (dumb Fuzzer) sollte aber inbedingt vermieden werden. Da es intelligentere und damit wesentlich effizientere Arten des Fuzzens gibt. Für die oben gezeigten Minibeispiele reicht es noch aus, aber längere Codebeispiele sollte man damit nicht fuzzen.

Instrumentation

Um effektiv zu funktionieren, benötigt AFL Informationen über den Programmablauf des zu testenden Programms. AFL kann somit die Eingaben geschickter variieren um neue Pfade im Programm zu finden. Im naiven Ansatz ist es AFL nicht möglich herauszufinden ob das Programm immer an der selben Stelle terminiert. Durch die Instrumentation kann die Codeabdeckung analysiert werden. Generell ist es wahrscheinlicher einen Fehler zu finden, je mehr Code des Testprogramms durchlaufen wird.

Für die Instrumentation bieten sich dem Anwender zwei verschiedene Möglichkeiten:

1. Compilieren des Testprogramms: Hierfür wird der Quellcode des Programms benötigt. AFL liefert die nötigen Compiler afl-gcc, afl-g++ und afl-clang mit. Diese Vorgehensweise bietet die beste Performance. Die Compiler fügen bei bedingten Sprüngen zusätzliche Sprungbefehle in AFL Bibliotheken ein. Dadurch erhällt AFL die nötigen Informationen über den Programmablauf.
2. Benutzung des Emulators QEMU: QEMU emuliert den Programmablauf und kann somit die nötigen Informationen über den Ablauf an AFL weiterleiten. Der Vorteil von QEMU ist die einfache Benutzung, es wird beim Start von afl-fuzz mit -Q aktiviert. Das Testprogramm muss vorher nicht compiliert werden, was eine Analyse von Programmen ermöglicht, deren Quellcode nicht offen liegt. Weiterhin können auch Systemfremde Binaries getestet werden (Bsp: ARM auf x86). Nachteil ist die schlechte Performance. Die Geschwindigkeit erhöht sich um den Faktor 2 bis 5. Desweiteren wird darauf hingewiesen, dass es einige Bugs geben kann, die durch die Benutzung von QEMU auftreten.

Nutzung der Compiler

Das Testprogramm für den Test zu compilieren ist der schwierigste Schritt um den Test durchzuführen. In einigen Fällen, wie z.B. lame, reicht es aus den Compiler auszutauschen.

  ./configure
  ./make CC=afl-gcc

In anderen Fällen müssen die Buildscripte per Hand angepasst werden. Es muss darauf geachtet werden, dass angeschlossene Bibliotheken, die für die verarbeitung der Testeingaben zuständig sind auch mit den AFL Compilern compiliert werden. Besser ist es abhängige Bibliotheken statisch in das Programm zu linken. Richtig Mühevoll wird es dann, wenn das eigentliche Programm nicht für einen Test mit AFL kompatibel ist. Dies sind z.B. Bibliotheken oder GUI- und Netzwerkprogramme die den Code für den Parser von Dateien und Nachrichten im Programmcode verflochten haben. Hier ist es nötig den entsprechenden Code aus den Quellen zu kopieren und einen Wrapper zu programmieren damit der Code mit AFL testbar wird. An dieser Stelle ist zusätzlich Vorsicht geboten keine zusätzlichen Fehler einzubauen.

Eine genaue Anleitung zu geben ist hier nicht möglich. Der Leser wird dazu angehalten, sich das nötige Wissen über Buildscripte, Compiler und Wrappercode aus anderen Quellen zu besorgen.

Pfade

Ziel der Instrumentation ist die Analyse der Pfade, die das Testprogramm beim abarbeiten der Eingabe nimmt. Genau genommen ist hier aber nicht der komplette Pfad interessant, sondern die Übergänge von einem Codeblock zum nächsten. Im folgenden werden Codeblöcke mit Großbuchstaben bezeichnet. Findet ein bedingter Sprung statt, so markiert ein Pfeil den Übergang zum nächsten Codeblock.

  A -> B -> C -> D -> E
  A -> B -> C -> A -> E

Der zweite Pfad ist neu, da er neue Tupel CA und AE enthällt. Ein Pfad wie:

  A -> B -> C -> A -> B

ist nicht neu, da er keine neuen Tupel enthällt.

Entdeckt AFL eine Eingabe, die einen neuen Tupel aufweist, so wird diese Eingabe zu einem Testcase von dem aus Mutationen stattfinden. AFL hällt eine Queue für alle interessanten Testcases. Beim Start werden die Testcases aus dem Eingabeordner der Queue hinzugefügt. Für jeden Testcase finden eine reihe von Mutationen statt. Wird nach einer Mutation ein neuer Tupel entdeckt so wird die Eingabe als neuer Testcase der Queue hinzugefügt. Der Nutzer kann in der GUI von AFL sehen wann dies zuletzt stattgefunden hat. Hierfür gibt es einen Timer der anzeigt wann zuletzt ein neuer Pfad gefunden wurde. Wenn alle Testcases in der Queue abgearbeitet sind ist ein Cycle vorbei. AFL füllt die Queue dann wieder mit allen zuvor gefundenen Testcases und beginnt von vorne.

Dictionaries

Dictionaries sind mit den Testcases die einzige Möglichkeit auf den Ablauf von AFL einfluss zu nehmen. Dies sind einfache Textdateien mit Key-Value Paaren.

Auszug eines Dictionary für HTML:

  tag_a="<a>"
  tag_abbr=""
  tag_acronym="<acronym>"
  tag_address="<address>"
  tag_annotation_xml="<annotation-xml>"
  tag_applet="<applet>"
  tag_area="<area>"
  tag_article="<article>"
  tag_aside="<aside>"
  tag_audio="<audio>"
  tag_base="<base>"
  tag_basefont="<basefont>"
  tag_bdi=""
  tag_bdo=""
  ...

Dictionaries ermöglichen es Wörter anzugeben die häufig in dem Input für das Testprogramm vorkommen. Allein durch zufällige Mutation würde es sonst zu lange dauern, bis der Input die bekannten Schlüsselwörter enthällt oder die erwartete Syntax aufweist. AFL liefert einige Dictionaries für bekannte Dateiformate wie HTML, XML, PNG, JPEG, PDF, SQL, JavaScript usw. mit.

Erwartet das Testprogramm Input in dem feste Wörter vorkommen empfiehlt es sich vorher eine solche Datei zu erstellen und diese beim Start des Fuzzers mit -x [pfad] anzugeben.

Syntax

AFL bietet keine Unterstützung für Syntaxtemplates. Erwartet das Testprogramm Input mit einer bestimmten Syntax so bieten Dictionaries die einzige Möglichkeit diese zu konstruieren. Die Syntax wird dabei nicht explizit angegeben, sonder ergibt sich implizit aus den angegebenen Wörtern und dem Feedback, welches AFL durch die Instrumentation erhällt.

Mutationen

Im folgenden werden die einzelnen Schritte erläutert, die AFL durchführt um einen gegebenen Testcase zu mutieren:

• Calibration: Tested die Ausführungsgeschwindigkeit des Testprogramms um später evaluiren zu können ob das Programm hängen geblieben ist.
• Trim: Der Testcase wird gekürzt. Anhand des Pfades den das Testprogramm für den Testcase nimmt können unnötige Zeichen detektiert werden.
• Bit flips: Es werden einzelne oder ketten von Bits im Testcase umgedreht.
• Arithmetics: Teile des Testcases werden als 8, 16 oder 32 Bit Integer interpretiert und kleine Werte werden addiert und subtrahiert.
• Interest: Wie Arithmetics, allerdings werden Extremfälle wie 0, max und min int eingesetzt.
• Extras: Der TEstcase wird mit Wörtern aus der Dictionary gefüllt.
• Havoc: Der TEstcase wird mit Wörtern aus der Dictionary gefüllt.
• Splice: Zwei Testcases werden an einer zufälligen Stelle zerschnitten und vertauscht wieder zusammen gesetzt.
• Sync: Synchronisationsschritt, der bei benutzung der Parallelisierung ausgeführt wird.

Address Sanitizer

Address Sanitizer ist ein Werkzeug mit dem der benutzte Speicher überwacht werden kann. Es bietet den Vorteil, dass unbeabsichtige Schreib- und Lesezugriffe auf den Speicher leichter entdeckt werden können. Das Testprogramm muss hierbei nicht zwangsläufig abstürzen um den Fehler zu entdecken und einige ungewollte Lesezugriffe führen nicht zu einem Programmabsturz. Die Rate der entdeckten Fehler kann somit mit dem Einsatz von Address Sanitizer gesteigert werden.

Die Verwendung von Address Sanitizer ist relativ einfach. Beim compilieren des Testprogramms mit den AFL Compilern muss lediglich die Umgebungsvariable AFL_ASAN=1 gesetzt werden. Hierbei wird weiterhin empfohlen auch die Umgebungsvariable AFL_HARDEN=1 zu setzen. Hiermit werden zusätzlich die die Grenzen beim Zugriff auf Arrays überprüft. Wurde das Testprogramm mit ASAN compiliert wird wesentlich mehr Speicher benötigt. Evtl. muss der für das Programm reservierte Speicher vergrößert werden. Dies kann beim Start von afl-fuzz mit -m [Speichergröße] gesteuert werden. Als Richtwert wird hier 800 (MB) empfohlen.

ACHTUNG: Problematisch ist die Verwendung von ASAN auf 64Bit Systemen. Hier benötigt ASAN mehrere Terabyte an Speicher. Da auf den meisten Rechnern nicht so viel Speicher zur verfügung steht, muss das Problem umgangen werden indem das Testprogramm im 32Bit Modus compiliert wird. Hierfür muss zusätzlich das Compilerflag -m32 gesetzt werden.

Vorteile:

• Entdeckt mehr Fehler

Nachteile:

• Beschränkung auf 32Bit Binaries
• Performance sinkt
• Benötigter Speicher steigt

Parallelisierung

Parallelisierung ist möglich und verbessert die Performance, mit der der Test läuft erheblich. Die Parallelisierung des Tests funktioniert dabei aber nicht komplett innerhalb von AFL. Anstatt das ein AFL Prozess mehrere Threads startet muss der Nutzer mehrere Prozesse von AFL starten.

Wird der naive Ansatz mit -n gewählt so können einfach mehrere Prozesse wie gewohnt gestartet werden. Da der Input durch Zufall mutiert wird ist es eher unwahrscheinlich das zwei Prozesse den selben Input generieren.

Wenn die Instrumentation verwendet wird muss der erste AFL Prozess (Master) mit -M [Name] gestartet werden. Nun können beliebig viel weitere Prozesse (Slaves) mit -S [Name] gestarten werden. Der Name kann jeweils frei gewählt werden, sollte jedoch jeden Prozess eindeutig identifizieren. Wichtig beim Starten von Master und Slaves ist es, den selben Ausgabeordner anzugeben. Die Prozesse synchronisieren sich über den Ausgabeordner in regelmäßigen Abständen. Um den Test zu überwachen, wird das Tool afl-whatsup mitgeliefert. Mit afl-whatsup [Pfad zum Ausgabeordner] kann man sich Informationen über die angeschlossenen Prozesse und eine Zusammenfassung ausgeben lassen.

Der Master kümmert sich um alle deterministische Mutationen wie Bitflips, Arithmetics, Extras usw. wärend die Slaves rein zufällige Mutationen (Havoc) testen. Dies erklärt auch die Irrelevanz der Parallelisierung im naiven Modus.

Die Parallelisierung von mehreren Prozessen über den Ausgabeordner scheint zunächst umständlich zu sein. Diese Vorgehensweise bietet dafür aber den Vorteil, dass der Test leicht auf mehrere Rechner in einem Netzwerk parallelisiert werden kann, wenn der Ausgabeordner z.B. mit NFS über die Rechner synchronisiert wird.

Abbruch des Tests

AFL testet beliebig lange und der Abbruch des Tests muss durch den Benutzer erfolgen. Es gibt dabei keinen klaren Anhaltspunk, wann das Programm abgebrochen werden sollte. Generell erhöht sich die Wahrscheinlichkeit einen Fehler zu finden, je länge man testet. Sind keine Fehler im Programm enthalten ist eine Suche allerdings vergebens. Es gibt einige Merkmale an denen man entscheiden kann, den Test abzubrechen.

• Der Test sollte zumindest einen Cycle abarbeiten. Wenn dies geschehen ist, wurden alle leicht zu entdeckenden Pfade durchgetestet und einmal mutiert.
• Der Test kann abgebrochen werden, wenn die gewünschte Pfadabdeckung erreicht ist. Eine Pfadabdeckung von 100% ist unrealistisch, der Anwender muss vorher evaluieren, wieviel Code durch den Test überhaupt erreichbar ist.
• Wurde längere Zeit kein neuer Pfad gefunden kann der Test auch abgebrochen werden. Der Testaufwand liegt dann nicht mehr in Relation zum Fortschritt, den AFL macht.

Anhand von Erfahrungsberichten sollte man sich auf einige Tage Testzeit einrichten.