diff options
Diffstat (limited to 'docs/power_schedules.txt')
| -rw-r--r-- | docs/power_schedules.txt | 27 |
1 files changed, 11 insertions, 16 deletions
diff --git a/docs/power_schedules.txt b/docs/power_schedules.txt index cb4ca6e7..f5f66bd6 100644 --- a/docs/power_schedules.txt +++ b/docs/power_schedules.txt @@ -1,33 +1,28 @@ -This document was copied and modified from AFLfast at github.com/mboehme/aflfast +afl++'s power schedules based on AFLfast +<a href="https://comp.nus.edu.sg/~mboehme/paper/CCS16.pdf"><img src="https://comp.nus.edu.sg/~mboehme/paper/CCS16.png" align="right" width="250"></a> +Power schedules implemented by Marcel Böhme \<marcel.boehme@acm.org\>. +AFLFast is an extension of AFL which was written by Michal Zalewski \<lcamtuf@google.com\>. -Essentially, we observed that most generated inputs exercise the same few -"high-frequency" paths and developed strategies to gravitate towards -low-frequency paths, to stress significantly more program behavior in the -same amount of time. We devised several **search strategies** that decide -in which order the seeds should be fuzzed and **power schedules** that -smartly regulate the number of inputs generated from a seed (i.e., the -time spent fuzzing a seed). We call the number of inputs generated from a -seed, the seed's **energy**. +AFLfast has helped in the success of Team Codejitsu at the finals of the DARPA Cyber Grand Challenge where their bot Galactica took **2nd place** in terms of #POVs proven (see red bar at https://www.cybergrandchallenge.com/event#results). AFLFast exposed several previously unreported CVEs that could not be exposed by AFL in 24 hours and otherwise exposed vulnerabilities significantly faster than AFL while generating orders of magnitude more unique crashes. -Old AFL used -p exploit which had a too high cost, current AFL uses -p explore. +Essentially, we observed that most generated inputs exercise the same few "high-frequency" paths and developed strategies to gravitate towards low-frequency paths, to stress significantly more program behavior in the same amount of time. We devised several **search strategies** that decide in which order the seeds should be fuzzed and **power schedules** that smartly regulate the number of inputs generated from a seed (i.e., the time spent fuzzing a seed). We call the number of inputs generated from a seed, the seed's **energy**. -AFLfast implemented 4 new power schedules which are highly recommended to run -in parallel. +We find that AFL's exploitation-based constant schedule assigns **too much energy to seeds exercising high-frequency paths** (e.g., paths that reject invalid inputs) and not enough energy to seeds exercising low-frequency paths (e.g., paths that stress interesting behaviors). Technically, we modified the computation of a seed's performance score (`calculate_score`), which seed is marked as favourite (`update_bitmap_score`), and which seed is chosen next from the circular queue (`main`). We implemented the following schedules (in the order of their effectiveness, best first): | AFL flag | Power Schedule | | ------------- | -------------------------- | -| `-p fast` (default)| =\\min\\left(\\frac{\\alpha(i)}{\\beta}\\cdot\\frac{2^{s(i)}}{f(i)},M\\right)) | +| `-p explore` (default)|  | +| `-p fast` | =\\min\\left(\\frac{\\alpha(i)}{\\beta}\\cdot\\frac{2^{s(i)}}{f(i)},M\\right)) | | `-p coe` |  | -| `-p explore` |  | | `-p quad` |  | | `-p lin` |  | | `-p exploit` (AFL) |  | where *α(i)* is the performance score that AFL uses to compute for the seed input *i*, *β(i)>1* is a constant, *s(i)* is the number of times that seed *i* has been chosen from the queue, *f(i)* is the number of generated inputs that exercise the same path as seed *i*, and *μ* is the average number of generated inputs exercising a path. -More details can be found in our paper that was recently accepted at the [23rd ACM Conference on Computer and Communications Security (CCS'16)](https://www.sigsac.org/ccs/CCS2016/accepted-papers/). +More details can be found in the paper that was accepted at the [23rd ACM Conference on Computer and Communications Security (CCS'16)](https://www.sigsac.org/ccs/CCS2016/accepted-papers/). -PS: In parallel mode (several instances with shared queue), we suggest to run the master using the exploit schedule (-p exploit) and the slaves with a combination of cut-off-exponential (-p coe), exponential (-p fast; default), and explore (-p explore) schedules. In single mode, the default settings will do. **EDIT:** In parallel mode, AFLFast seems to perform poorly because the path probability estimates are incorrect for the imported seeds. Pull requests to fix this issue by syncing the estimates across instances are appreciated :) +PS: In parallel mode (several instances with shared queue), we suggest to run the master using the exploit schedule (-p exploit) and the slaves with a combination of cut-off-exponential (-p coe), exponential (-p fast; default), and explore (-p explore) schedules. In single mode, the default settings will do. **EDIT:** In parallel mode, AFLFast seems to perform poorly because the path probability estimates are incorrect for the imported seeds. Pull requests to fix this issue by syncing the estimates accross instances are appreciated :) Copyright 2013, 2014, 2015, 2016 Google Inc. All rights reserved. Released under terms and conditions of Apache License, Version 2.0. |