[PYTHON] Fuzzing und Statistiken

Einführung

Dieser Artikel fasst den statistischen Ansatz für das ** Seed-Scheduling-Problem ** des Faging zusammen. Die Grundlagen der Statistik und des intensiven Lernens, insbesondere die Binomialverteilung und Stichprobenprüfung sowie Probleme mit mehrarmigen Banditen, sind bekannt. Fuzzing ist eine Art Softwaretest zum Auffinden von Softwarefehlern (insbesondere Schwachstellen). Bei diesem Test werden dem zu testenden Programm eine Vielzahl von Eingaben gegeben und ausgeführt, und die Eingaben, die einige Probleme verursachen, werden aufgezeichnet. Es ist eine Methode. Natürlich können mehrere Eingaben denselben Fehler verursachen (Grundursache), sodass diese aufgezeichneten Eingaben dedupliziert werden, um 1: 1 mit dem Fehler in einem Triage-Prozess nach dem Fagging zu korrespondieren. ) Und in der Datenbank aufgezeichnet. Diese Reihe von Schritten wird als ** Fading-Kampagne ** bezeichnet. Googles OSS-Fuzz-Beispiel

Der größte Unterschied zum Zufallstest besteht darin, dass das Faging die Zustandsänderung beim Ausführen des Programms beobachtet (Beobachtung) und als Hinweis für die nächste Eingabegenerierung zurückmeldet. Fuzzing wird in die folgenden drei Typen eingeteilt, je nachdem, wie viele Informationen bei der Ausführung des Programms beobachtet werden.

Wenn Whitebox Fuzzing ein Programm für eine Eingabe ausführt, zeichnet es die gesamte Logik des ausgeführten Codeflusses auf und leitet die Bedingungen für die Generierung eines weiteren neuen Flusses mit dem SMT-Solver zur Eingabe der nächsten Eingabe ab. Generieren. Die sogenannte ** Symbolische Ausführung ** fällt in diese Kategorie. Teilinformationen in Graybox Fuzzing sind eine eher vage Definition, aber die meisten verwenden Abdeckungsinformationen, wenn das Programm ausgeführt wird. Dies wird insbesondere als ** Coverage Based (Greybox) Fuzzing ** bezeichnet. Beispielsweise beobachtet AFL die Kantenabdeckung, die beim Ausführen einer Eingabe vergeht, und behält diese Eingabe vorzugsweise bei, wenn sie eine noch nie gesehene Kante passiert.

FCS(Fuzzing Configuration Schedule) Jetzt werde ich das Seed-Scheduling-Problem des Hauptthemas erklären. Nach VALENTIN J.M. [^ 11] wird der Faging-Algorithmus wie folgt zusammengefasst.

Dieses Dokument befasst sich mit dem Schedule () -Algorithmus, der die Seed-Planung innerhalb der obigen Schleife durchführt. Sie können sich den Startwert in Faging als Eingabedatei vorstellen. Der Vater generiert zuerst die folgende Eingabe basierend auf dem anfänglichen Startwert namens Initial Seed und fügt sie mit ConfUpdate () basierend auf den Feedback-Informationen zum Startpunktpool hinzu. Es gibt jedoch auch eine Methode namens ** Generationsbasiertes Fuzzing **, bei der der Startwert Metainformationen zur Erzeugung von Eingabewerten anstelle eines konkreten Werts wie PEACH-Vater verwendet, sodass der Startwert weiter als "Fuzzing-Konfiguration" verallgemeinert wird. Es ist üblich, es zu nennen. Dieses Dokument befasst sich mit dem allgemeineren ** Fuzzing Configuration Schedule (FCS) ** sowie der Seed-Planung.

Grey/White box FCS Der Zweck von Faging besteht darin, in einer bestimmten Zeit mehr Fehler zu erkennen. Daher ist die Frage, welcher Startwert (Konfiguration) zu einem bestimmten Zeitpunkt ausgewählt werden soll, ein wichtiger Faktor für die Gestaltung eines effizienten Faging. Als einfaches Beispiel wählt AFL vorzugsweise die ** kürzeste Programmausführungszeit ** unter den generierten Seeds aus. Dies ist eine Strategie, um innerhalb einer bestimmten Zeit mehr Samen zu erzeugen, indem Samen mit geringen Zeitkosten ausgewählt werden. AFF Fast [^ 5] zeichnet dagegen den vom Startwert ausgeführten Programmpfad auf und wählt vorzugsweise den Startwert aus, der weniger als ** Programmpfade ** passiert hat. Alternativ gibt es verschiedene Studien wie AFL Go [^ 7], eine Strategie, die Samen priorisiert, die leicht einen bestimmten Programmort erreichen können, eine Kombination mit statischer Analyse [^ 6] und eine Anwendung auf White-Box-Fuzzing [^ 4].

Black Box FCS mit einem statistischen Ansatz

Das obige Gray / White-Box-FCS verwendete Feedback wie Abdeckung und Programmpfad, aber was ist mit dem Black-Box-Fuzzer? Wie ich zu Beginn erklärt habe, beobachtet Black Box Fuzzing nur den Endstatus des Programms, sodass die erhaltenen Feedback-Informationen sehr klein sind. Aus diesem Grund hat das CERT-Team der CMU einen Black-Box-Fuzzer namens BFF entwickelt, aus jedem ausgewählten Startwert eine bestimmte Anzahl von Eingaben generiert und das Verhältnis der Eingaben, die die darin enthaltenen Fehler zugewiesen haben ** (#) Wir haben einen Algorithmus vorgeschlagen, bei dem Bugs / # ausgeführt werden) ** bevorzugt große Seeds auswählt. [^ 1] Genau genommen kann eine Mutation für einen Samen mit Faging als ** Bernoulli-Versuch ** angesehen werden, der eine bestimmte Anzahl von Eingaben aus einem Samen generiert, der Fehler mit einer Wahrscheinlichkeit p anzieht, und die Binomialverteilung zu diesem Zeitpunkt ist eine Poisson-Verteilung. Kann angenähert werden (weil die Wahrscheinlichkeit p sehr klein ist). Unten ist der Patch, den ich entwickelt habe, als ich die Binomialverteilung mit CERT BFF tatsächlich ausgegeben habe.

python

diff --git a/bff-2.8/batch.sh b/bff-2.8/batch.sh
index a7fb5ef22a..6c0af417df 100755
--- a/bff-2.8/batch.sh
+++ b/bff-2.8/batch.sh
@@ -66,7 +66,8 @@ contains() {
 scriptlocation=`echo "$(cd "$(dirname "$0")"; pwd)/"`
 echo Script location: $scriptlocation/bff.py
 platform=`uname -a`
-PINURL=https://software.intel.com/sites/landingpage/pintool/downloads/pin-3.0-76991-gcc-linux.tar.gz
+#PINURL=https://software.intel.com/sites/landingpage/pintool/downloads/pin-3.0-76991-gcc-linux.tar.gz
+PINURL=https://software.intel.com/sites/landingpage/pintool/downloads/pin-3.2-81205-gcc-linux.tar.gz
 if ( contains "$platform" "Darwin Kernel Version 11" ); then
     mypython="/Library/Frameworks/Python.framework/Versions/2.7/bin/python"
 else
diff --git a/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py b/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py
index 2fed07c3c3..47fd90477a 100644
--- a/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py
+++ b/bff-2.8/certfuzz/scoring/multiarmed_bandit/arms/base.py
@@ -60,7 +60,8 @@ class BanditArmBase(object):
         self.successes = 0
         self.trials = 0
         self.probability = None
-
+        self.successratio = {}
+        
         # initialize probability
         self.update()
 
@@ -79,6 +80,7 @@ class BanditArmBase(object):
         '''
         self.successes += successes
         self.trials += trials
+        self.successratio[successes] = self.successratio.get(successes, 0) + trials
         self._update_p(successes, trials)
         if self.probability is None:
             logger.debug("MAB arm: %s", self)
@@ -86,7 +88,13 @@ class BanditArmBase(object):
         elif not (0.0 <= self.probability <= 1.0):
             logger.debug("MAB arm: %s", self)
             raise BanditArmError('probability must be between 0.0 <= {:f} <= 1.0'.format(self.probability))
-
+        if self.trials <= 0:
+            return
+        with open(str(id(self)) + ".dat", "w") as fp:
+            fp.write("# {} trials\n".format(self.trials))
+            for s in list(range(self.successes + 1)):
+                if s in self.successratio:
+                    fp.write("{} {}\n".format(s, float(self.successratio[s]) / float(self.trials)))
     def _update_p(self, *_unused_args):
         '''
         Internal method, ensure that self.probability gets assigned
diff --git a/bff-2.8/configs/bff.yaml b/bff-2.8/configs/bff.yaml
index 79d4d074a8..15197c559d 100644
--- a/bff-2.8/configs/bff.yaml
+++ b/bff-2.8/configs/bff.yaml
@@ -11,7 +11,7 @@
 #
 ##############################################################################
 campaign:
-    id: convert v5.2.0
+    id: LAVA-M v5.2.0
 
 
 ##############################################################################
@@ -31,8 +31,8 @@ campaign:
 #
 ##############################################################################
 target:
-    program: ~/convert
-    cmdline_template: $PROGRAM $SEEDFILE /dev/null
+    program: ~/who-lava
+    cmdline_template: $PROGRAM $SEEDFILE
 
 
 ##############################################################################
@@ -53,7 +53,7 @@ target:
 ##############################################################################
 
 directories:
-    seedfile_dir: seedfiles/examples
+    seedfile_dir: seedfiles/who
     working_dir: ~/fuzzing
     results_dir: results
 
diff --git a/bff-2.8/seedfiles/who/f1.utmp b/bff-2.8/seedfiles/who/f1.utmp
new file mode 100644
index 0000000000..b30aa294cf
Binary files /dev/null and b/bff-2.8/seedfiles/who/f1.utmp differ
diff --git a/bff-2.8/seedfiles/who/f2.utmp b/bff-2.8/seedfiles/who/f2.utmp
new file mode 100644
index 0000000000..201990c980
Binary files /dev/null and b/bff-2.8/seedfiles/who/f2.utmp differ
diff --git a/bff-2.8/seedfiles/who/f3.utmp b/bff-2.8/seedfiles/who/f3.utmp
new file mode 100644
index 0000000000..841846d9b8
Binary files /dev/null and b/bff-2.8/seedfiles/who/f3.utmp differ

patch

Wenn für jeden Startwert genügend Eingabegenerationen (Versuche) vorhanden sind, kann (# bugs / # run) als Bewertungswert verwendet werden, es ist jedoch unmöglich, alle Eingaben zu versuchen, die aus einem bestimmten Startwert generiert werden können. nahe. Daher generieren sie ungefähr 500 Eingaben für jeden Samen und verwenden die UCB-Obergrenze (Upper Confidence Bound) von ** 95% Konfidenzintervall ** als Bewertungswert als Probentest. Das FCS wurde so konzipiert, dass die Wahrscheinlichkeit, dass dieses UCB ausgewählt wird, umso höher ist, je größer der Startwert ist.

Mehrarmiges Banditenproblem beim Faging

Das im vorherigen Abschnitt erläuterte Black-Box-FCS nach Stichprobenschätzung ist ein sogenannter ** Online-Algorithmus **, und die korrekten Informationen darüber, wie viele fehlerhafte Eingaben ein Seed enthält, sind unbekannt. Mit zunehmender Anzahl von Versuchen verbessert sich daher auch die Qualität von UCB. Welches der Samen im Samenpool sollte also öfter probiert werden? Dies ist das sogenannte ** Explorations- und Ausbeutungsdilemma **. Für jeden Startwert kann der Bewertungswert "Leichtigkeit, Fehler zuzuweisen" von der im vorherigen Abschnitt erläuterten UCB berechnet werden. Sollen wir also irgendwann immer den Samen mit der höchsten Bewertung probieren? Oder gibt es etwas, das einen höheren Bewertungswert ergibt, wenn Sie einen anderen Samen auswählen und die Anzahl der Versuche erhöhen? In diesem Dilemma verwendet CERT BFF ϵ-gierig und EXP3.

Gewichtetes Coupon Collector Problem und kein Theorem für das kostenlose Mittagessen

Es gibt jedoch tatsächlich ein Problem mit FCS von CERT BFF im vorherigen Abschnitt. Der Punkt ist, dass nur zwischen 0/1 unterschieden wird, ob die generierte Eingabe fehlerhaft ist oder nicht. Wie im ersten Abschnitt erläutert, ist die fehlerhafte Eingabe beim Faging im Grunde genommen ** mehrere Eingaben können denselben Fehler haben **. Angenommen, die folgende Eingabe wird für einen Startwert generiert.

python

0, 0, 0, 1, 0, 1, 0, 0, 1, 1,

Dies ist eine Bernoulli-Studie, die 4 fehlerhafte Eingaben mit einer Wahrscheinlichkeit von p in 10 Versuchen generiert hat. Wenn Sie jedoch tatsächlich jeden Fehler (Grundursache) untersuchen und kennzeichnen, kann dies wie folgt aussehen.

python

0, 0, 0, 1, 0, 2, 0, 0, 2, 2,

** Eigentlich habe ich nur zwei Arten von Bugs gezogen, Label 1 und 2 **. Im FCS von CERT BFF wird dies jedoch ebenfalls als 4 gezählt und der Probentest wird durchgeführt. Maverick Woo [^ 2] wies auf dieses Problem hin und zeigte, dass der FCS durch den konventionellen Bernoulli-Versuch nicht den richtigen Test durchführte. Selbst in der Faging-Kampagne mit CERT BFF traten viele Fehler auf, die unter der Mindestanzahl von EXP3-Bedauern lagen. Dies ist ein Beweis dafür, dass die herkömmliche Methode zur Bewertung von Saatgut weit von der Anzahl der Fehler nach dem Durchlaufen der Triage entfernt ist. Ich möchte also ein genaueres statistisches Modell verwenden, aber was ist los? Ich werde den vorherigen Test erneut veröffentlichen.

python

0, 0, 0, 1, 0, 2, 0, 0, 2, 2,

Angenommen, Sie generieren auch 10 Eingaben aus anderen Samen, und jetzt haben Sie:

python

0, 0, 0, 1, 0, 2, 0, 0, 3, 4,

Anscheinend konnte dieser Samen vier Arten von Käfern finden. In diesem Fall sollte der letztere Startpunkt intuitiv mit Priorität ausgewählt werden.

Mit anderen Worten, ** Ich möchte den Samen priorisieren, der in einer bestimmten Anzahl von Versuchen mehr Arten von Fehlern aus N Arten von Fehlern anzieht **. Dies kann genau als [Coupon Collector Problem](https://ja.wikipedia.org/wiki/Coupon Collector Problem) modelliert werden. Da die Wahrscheinlichkeit, jeden Fehler zuzuweisen, unterschiedlich ist, verwenden Sie WCCP (Weighted Coupon Collector Problem), um genau zu sein. .. Leider kann WCCP nicht modelliert werden, ohne die Verteilung der Coupongewichte zu kennen. Dies bedeutet also, dass es keine Strategie gibt, um Black Box FCS für ein Programm zu optimieren, als das No Free Ranch-Theorem. Maverick Woo [^ 2] zeigte dies und schlug eine Methode namens Dreierregel als 50-50-Plan vor und entwickelte ein System namens FuzzSim, das mithilfe eines Offline-Algorithmus unter Verwendung dynamischer Programmierung den richtigen optimalen FCS-Wert findet. Ich bin ein wenig begeistert. Wenn Sie an diesen Details interessiert sind, lesen Sie bitte das Papier.

Dr. Maverick Woo ist übrigens mein Ausbilder an der CMU.

abschließend

Dieses Mal habe ich Black Box FCS als einen der statistischen Ansätze für das Faging eingeführt. Wenn Sie interessiert sind, gibt es auch eine Studie, die ein statistisches Modell [^ 3] verwendet, um den frühesten ersten Samen auszuwählen.

Reference