Clarification on "favourites"
350 views
Skip to first unread message
Ben Nagy
Jun 25, 2015, 1:42:16 AM6/25/15
to afl-...@googlegroups.com
Hi,
The tech details implies that "favourites" are "a smaller subset of test cases that still cover every tuple seen so far", however my afl-cmin results are much larger than the favourites stat as reported by the fuzzers.
Also, I have this kind of thing ( stats from the same run, at intervals):
Total execs : 59 million
Pending paths : 91325 faves, 910852 total
Pending per fuzzer : 1943 faves, 19379 total (on average)
Crashes found : 45 locally unique
Total execs : 158 million
Pending paths : 83016 faves, 938138 total
Pending per fuzzer : 1766 faves, 19960 total (on average)
Crashes found : 6163 locally unique
Total execs : 426 million
Pending paths : 33496 faves, 987513 total
Pending per fuzzer : 712 faves, 21010 total (on average)
Crashes found : 27548 locally unique
Where the favourites "condense". My question is more or less "what am I seeing here"? If it's the case that those 712 faves cover all the code then I'm puzzled as to why cmin reduces the queue/ from any of those fuzzers to more like 10k files. Could I extract the 712 instead with minimal-to-no loss of coverage? If it's _not_ the case then what, exactly, are those 712 faves? :)
Cheers!
ben
Michal Zalewski
Jun 25, 2015, 3:06:49 AM6/25/15
to afl-users
> The tech details implies that "favourites" are "a smaller subset of test
> cases that still cover every tuple seen so far", however my afl-cmin results
> are much larger than the favourites stat as reported by the fuzzers.
The internal algorithm used by AFL for giving higher probabilities to
> cases that still cover every tuple seen so far", however my afl-cmin results
> are much larger than the favourites stat as reported by the fuzzers.
some inputs is akin to afl-cmin -e. You generally wouldn't want to run
afl-cmin with -e, though, since in contrast to AFL, it would
completely delete the count-only paths, rather than just
deprioritizing them. So the default mode makes more sense for proper
corpus minimization.
I think this is vaguely alluded to in technical_details.txt, but I
didn't dwell on it because I figured most people wouldn't care.
> Also, I have this kind of thing ( stats from the same run, at intervals):
> Where the favourites "condense". My question is more or less "what am I
> seeing here"?
AFL gives precedence to favorites, so in the "pending" (i.e.,
> seeing here"?
never-fuzzed) tally, that number will shrink a lot faster than the
non-favorite inputs that only get picked up with some modest
probability in every pass.
/mz
Ben Nagy
Jun 25, 2015, 5:26:50 AM6/25/15
to afl-...@googlegroups.com
On Thu, Jun 25, 2015 at 2:06 PM, Michal Zalewski <lca...@gmail.com> wrote:
>> Also, I have this kind of thing ( stats from the same run, at intervals):
>> [...]
>> Where the favourites "condense". My question is more or less "what am I
>> seeing here"?
>
> AFL gives precedence to favorites, so in the "pending" (i.e.,
> never-fuzzed) tally, that number will shrink a lot faster than the
> non-favorite inputs that only get picked up with some modest
> probability in every pass.
I didn't understand "pending" that way, sorry. :( It makes more sense,
>> Also, I have this kind of thing ( stats from the same run, at intervals):
>> [...]
>> Where the favourites "condense". My question is more or less "what am I
>> seeing here"?
>
> AFL gives precedence to favorites, so in the "pending" (i.e.,
> never-fuzzed) tally, that number will shrink a lot faster than the
> non-favorite inputs that only get picked up with some modest
> probability in every pass.
but now I can't reconcile it with this:
cycle 1, lifetime speed 28 execs/sec, path 20169/23016 (87%)
pending 637/21276, coverage 48.37%, crash count 586 (!)
If that fuzzer has done 20k of 23k then how can it have 21k "never
fuzzed"? So, in that case, am I right in thinking that there is no way
(currently) to see the total number of favourites, apart from counting
paths in queue/ and subtracting .redundant_edges/ ?
Cheers,
ben
Michal Zalewski
Jun 25, 2015, 5:36:41 AM6/25/15
to afl-users
> cycle 1, lifetime speed 28 execs/sec, path 20169/23016 (87%)
> pending 637/21276, coverage 48.37%, crash count 586 (!)
>
> If that fuzzer has done 20k of 23k then how can it have 21k "never
> fuzzed"?
Basically, favored paths have a 100% chance of being fuzzed in every
> pending 637/21276, coverage 48.37%, crash count 586 (!)
>
> If that fuzzer has done 20k of 23k then how can it have 21k "never
> fuzzed"?
single pass. Non-favored ones have only a 1-15% chance (see section 4
in technical_details.txt). So probabilistically, many of them will be
skipped in any given pass.
> So, in that case, am I right in thinking that there is no way
> (currently) to see the total number of favourites, apart from counting
> paths in queue/ and subtracting .redundant_edges/ ?
Cheers,
/mz
Ben Nagy
Jun 25, 2015, 5:48:18 AM6/25/15
to afl-...@googlegroups.com
On Thu, Jun 25, 2015 at 4:36 PM, Michal Zalewski <lca...@gmail.com> wrote:
>> cycle 1, lifetime speed 28 execs/sec, path 20169/23016 (87%)
>> pending 637/21276, coverage 48.37%, crash count 586 (!)
>>
>> If that fuzzer has done 20k of 23k then how can it have 21k "never
>> fuzzed"?
>
> Basically, favored paths have a 100% chance of being fuzzed in every
> single pass. Non-favored ones have only a 1-15% chance (see section 4
> in technical_details.txt). So probabilistically, many of them will be
> skipped in any given pass.
Ohh kayy. So, to be sure I understand, I guess that when the next
>> cycle 1, lifetime speed 28 execs/sec, path 20169/23016 (87%)
>> pending 637/21276, coverage 48.37%, crash count 586 (!)
>>
>> If that fuzzer has done 20k of 23k then how can it have 21k "never
>> fuzzed"?
>
> Basically, favored paths have a 100% chance of being fuzzed in every
> single pass. Non-favored ones have only a 1-15% chance (see section 4
> in technical_details.txt). So probabilistically, many of them will be
> skipped in any given pass.
cycle starts, pending faves will go back up to $total_faves and
pending other will stay where it is? Or will it go up to $total_paths
and just not be expected to drop below ~ ($total_paths * 0.9) ? I feel
somehow like there may be a less confusing way to set these stats out,
but maybe my brain is just wired wrong. I'll stick it in the back of
my brain for a while.
>> So, in that case, am I right in thinking that there is no way
>> (currently) to see the total number of favourites, apart from counting
>> paths in queue/ and subtracting .redundant_edges/ ?
>
> It's in the UI, but indeed seems to be missing from fuzzer_stats. Can fix.
Cheers,
ben
Michal Zalewski
Jun 25, 2015, 10:49:00 AM6/25/15
to afl-users
> Ohh kayy. So, to be sure I understand, I guess that when the next
> cycle starts, pending faves will go back up to $total_faves and
> pending other will stay where it is?
Nope, you can read "pending" as "never fuzzed by this instance of afl-fuzz".
> cycle starts, pending faves will go back up to $total_faves and
> pending other will stay where it is?
The first pass ends when 100% of the favored test cases go through one
round of fuzzing (i.e., "pending fav" counter drops to 0). At that
point, the "pending" indicator that counts all non-fuzzed paths may be
still high. After that, AFL tries to fuzz some percentage of pending
cases in every subsequent pass, alongside with re-fuzzing the faves
using random strategies only.
Eventually, after some number of passes, the "pending" counter itself
will also go down to 0. At that point, the "cycles done" indicator
turns green, telling you that you're unlikely to find a whole lot
more.
/mz
Reply all
Reply to author
Forward
0 new messages