Fuzzing et statistiques
introduction
Cet article résume l'approche statistique du ** problème d'ordonnancement des semences ** de la faging. Les bases des statistiques et de l'apprentissage intensif, en particulier la distribution binomiale et les tests d'échantillons et les problèmes de bandits multi-armés, sont connus.
Le fuzzing est un type de test logiciel permettant de découvrir des bogues logiciels (en particulier des vulnérabilités). Il s'agit d'un test dans lequel une grande variété d'entrées sont données au programme testé et exécuté, et les entrées qui causent certains problèmes sont enregistrées. C'est une méthode. Bien sûr, plusieurs entrées peuvent être à l'origine de la même cause fondamentale, de sorte que ces entrées enregistrées sont dédupliquées pour correspondre 1: 1 avec le bogue dans un processus de triage post-fagging. ) Et enregistré dans la base de données. Cette série d'étapes est appelée ** campagne de décoloration **.
Exemple OSS-Fuzz de Google
La plus grande différence avec le test aléatoire est que faging observe le changement d'état lorsque le programme est exécuté (Observation) et le renvoie comme un indice pour la prochaine génération d'entrée. Le fuzzing est classé dans les trois types suivants en fonction de la quantité d'informations observées lors de l'exécution du programme.
| Blackbox Fuzzing | Observer uniquement l'état de fin du programme |
| Whitebox Fuzzing | Observez même la sémantique du programme |
| Greybox Fuzzing | Observer des informations partielles sur le programme |
Lorsque Whitebox Fuzzing exécute un programme pour une entrée, il enregistre toute la logique sur le flux de code exécuté et dérive les conditions pour générer un autre nouveau flux avec le solveur SMT pour entrer l'entrée suivante. Produire. La soi-disant ** exécution symbolique ** entre dans cette catégorie. Les informations partielles dans Graybox Fuzzing sont une définition assez vague, mais la plupart utilisent des informations de couverture lorsque le programme est exécuté. Ceci est particulièrement appelé ** Fuzzing basé sur la couverture (Greybox) **. Par exemple, AFL observe la couverture de bord qui passe lorsqu'une entrée est exécutée, et conserve de préférence cette entrée lorsqu'elle passe par un bord qui n'a jamais été vu auparavant.
FCS(Fuzzing Configuration Schedule)
Maintenant, je vais expliquer le problème de planification des semences du sujet principal.
Selon VALENTIN J.M [^ 11], l'algorithme de faging se résume comme suit.
Cet article traite de l'algorithme Schedule () qui effectue la planification d'amorçage dans la boucle ci-dessus. Vous pouvez considérer la graine de faging comme le fichier d'entrée. Le père génère d'abord l'entrée suivante basée sur la graine initiale appelée Initial Seed, et l'ajoute au pool d'amorçage avec ConfUpdate () en fonction des informations de retour. Cependant, il existe également une méthode appelée ** Fuzzing basé sur la génération ** dans laquelle la graine utilise des méta-informations pour la génération de la valeur d'entrée au lieu d'une valeur concrète, telle que PEACH père, de sorte que la graine est généralisée à "Fuzzing Configuraion". Il est courant de l'appeler. Cet article traite du ** Fuzzing Configuration Schedule (FCS) ** plus généralisé ainsi que de l'ordonnancement d'amorçage.
Grey/White box FCS Le but de la faging est de détecter plus de bogues dans un laps de temps donné. Par conséquent, la question de savoir quelle graine (configuration) sélectionner à un certain stade est un facteur important dans la conception d'une mise en cage efficace. À titre d'exemple simple, AFL sélectionne préférentiellement le ** temps d'exécution du programme le plus court ** parmi les graines générées. Il s'agit d'une stratégie pour générer plus de graines dans un délai donné en choisissant des graines à faible coût en temps. AFF Fast [^ 5], d'autre part, enregistre le chemin du programme exécuté par la graine et sélectionne préférentiellement la graine qui a passé moins de ** chemins de programme **. Alternativement, il existe diverses études telles que AFL Go [^ 7], une stratégie qui donne la priorité aux graines qui peuvent facilement atteindre un emplacement de programme spécifique, une combinaison avec une analyse statique [^ 6] et une application à la boîte blanche Fuzzing [^ 4].
Boîte noire FCS avec une approche statistique
La boîte grise / blanche FCS ci-dessus utilisait des commentaires tels que la couverture et le chemin du programme, mais qu'en est-il du Black Box Fuzzer? Comme je l'ai expliqué au début, Black Box Fuzzing n'observe que l'état de fin du programme, donc les informations de retour obtenues sont très petites. Par conséquent, l'équipe CERT de la CMU a développé un Black Box Fuzzer appelé BFF, généré un certain nombre d'entrées à partir de chaque graine sélectionnée, et le ratio d'entrées qui a affecté les bogues qu'il contient ** (#) Nous avons proposé un algorithme dans lequel bugs / # runs) ** sélectionne préférentiellement les grosses graines. [^ 1] À proprement parler, une mutation pour une graine avec faging peut être considérée comme un ** essai de Bernoulli ** qui génère un certain nombre d'entrées à partir d'une graine qui attire des bogues avec une probabilité p, et la distribution binomiale à ce moment est une distribution de Poisson. Peut être approximé (car la probabilité p est très faible). Vous trouverez ci-dessous le patch que j'ai développé lorsque j'ai effectivement vidé la distribution binomiale en utilisant CERT BFF.
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
S'il y a suffisamment de générations d'entrée (essais) pour chaque graine, (# bugs / # runs) peut être utilisé comme valeur d'évaluation telle quelle, mais il est impossible d'essayer toutes les entrées qui peuvent être générées à partir d'une certaine graine. près. Par conséquent, ils génèrent environ 500 entrées pour chaque graine et utilisent la limite supérieure UCB (Upper Confidence Bound) de ** intervalle de confiance à 95% ** comme valeur d'évaluation comme test d'échantillon. Le FCS a été conçu de telle sorte que plus la graine est grande, plus la probabilité que cet UCB soit sélectionné est élevée.
Problème de bandit multi-armé en faging
Maintenant, l'estimation de la boîte noire FCS par échantillon expliquée dans la section précédente est un soi-disant ** algorithme en ligne **, et les informations correctes sur le nombre d'entrées boguées qu'une graine contient sont inconnues. Par conséquent, à mesure que le nombre d'essais augmente, la qualité d'UCB s'améliore également. Alors, laquelle des graines du pool de graines doit être essayée plus souvent? C'est le soi-disant ** dilemme de l'exploration et de l'exploitation **. Pour chaque graine, la valeur d'évaluation de la "facilité d'attribution des bogues" peut être calculée par l'UCB expliqué dans la section précédente. Devrions-nous donc toujours essayer la graine avec la note la plus élevée à un moment donné? Ou peut-être y a-t-il quelque chose qui donne une valeur d'évaluation plus élevée si vous sélectionnez une autre graine et augmentez le nombre d'essais? Pour ce dilemme, CERT BFF utilise ϵ-gourmand et EXP3.
Problème de collecteur de coupons pondérés et pas de théorème de déjeuner gratuit
Cependant, il y a en fait un problème avec FCS by CERT BFF dans la section précédente. Le fait est qu'il ne distingue que 0/1 si l'entrée générée est boguée ou non. Comme expliqué dans la première section, une entrée boguée dans faging est ** plusieurs entrées peuvent avoir le même bogue **. Par exemple, supposons que l'entrée suivante soit générée pour une valeur de départ.
python
0, 0, 0, 1, 0, 1, 0, 0, 1, 1,
Il s'agit d'un essai de Bernoulli qui a généré 4 entrées de buggy avec une probabilité de p dans 10 essais. Cependant, si vous triez et étiquetez réellement chaque bogue (cause principale), cela peut être comme suit.
python
0, 0, 0, 1, 0, 2, 0, 0, 2, 2,
** En fait, je ne tirais que deux types de bogues, les étiquettes 1 et 2 **. Cependant, dans le FCS de CERT BFF, cela est également compté pour 4 et le test d'échantillon est effectué. Maverick Woo [^ 2] a souligné ce problème et a montré que le FCS de l'essai de Bernoulli conventionnel n'a pas effectué le test correct. En fait, même dans la campagne de faging utilisant CERT BFF, de nombreux bugs sont apparus en dessous du nombre minimum de regrets d'EXP3. C'est une preuve que la méthode conventionnelle d'évaluation des semences est loin du nombre de bogues après le triage. Je souhaite donc utiliser un modèle statistique plus précis, mais quel est le problème? Je publierai à nouveau l'essai précédent.
python
0, 0, 0, 1, 0, 2, 0, 0, 2, 2,
Supposons que vous génériez également 10 entrées à partir d'autres graines, et cette fois vous obtenez:
python
0, 0, 0, 1, 0, 2, 0, 0, 3, 4,
Apparemment, cette graine a pu trouver quatre types de bogues. Dans ce cas, cette dernière graine doit être sélectionnée avec priorité de manière intuitive.
En d'autres termes, ** je veux donner la priorité à la graine qui attire plus de types de bogues parmi N types de bogues dans un certain nombre d'essais **. Cela peut être modélisé exactement comme le [problème du collecteur de coupons](https://ja.wikipedia.org/wiki/Coupon Collector Problem). La probabilité d'attribution de chaque bogue étant différente, utilisez Weighted Coupon Collector Problem (WCCP) pour être exact. .. Malheureusement, le WCCP ne peut pas être modélisé sans connaître la distribution des poids des coupons. Donc, ce que cela signifie, c'est que ** il n'y a pas de stratégie pour optimiser Black Box FCS pour un programme que le théorème No Free Ranch **. En plus de montrer cela, Maverick Woo [^ 2] a proposé une méthode appelée Rule of Three comme une proposition 50-50, et a développé un système appelé FuzzSim qui trouve la valeur FCS optimale correcte par un algorithme hors ligne utilisant la planification dynamique. Je suis un peu maniaque, donc si vous êtes intéressé par ces détails, veuillez consulter l'article.
Au fait, le Dr Maverick Woo est mon instructeur à la CMU.
en conclusion
Cette fois, j'ai présenté Black Box FCS comme l'une des approches statistiques de la mise en scène. Si vous êtes intéressé, il existe également une étude utilisant un modèle statistique [^ 3] pour sélectionner la première graine initiale.
Reference
Recommended Posts