Solve empty and non-performing seed case

[ackdav]

Sorry in advance, this is a bit longer...(instructions to reproduce at the end)
TLDR: If every seed has perf_score==0, AFLFast (default) will stop fuzzing and only cycle through seeds.

Longer version:
Why
I ran some experiments with AFLFast (default schedule) with the empty seed, as described in the paper. While this works with several targets just fine (e.g. binutils), it implodes on targets that are "a bit harder to explore", due to an edge case in the performance_score calculation.
By "imploding" I mean:
AFLFast runs for a few thousand iterations fine (depending on the target ~5-10k total execs), then suddenly exec speed drops to 0/sec, and cycles done explodes into millions.

As of now I've hit this problem with 2/8 targets (tcpdump and djpeg are causing issues).

Problem
I believe the problem lies in the performance calculation:
Here are the relevant code snippets:

inside calculate_score():

case FAST:
      if (q->fuzz_level < 16) {
         factor = ((u32) (1 << q->fuzz_level)) / (fuzz == 0 ? 1 : fuzz);
      } else {
        factor = MAX_FACTOR / (fuzz == 0 ? 1 : next_p2 (fuzz));
      }
break;

  if (factor > MAX_FACTOR)
    factor = MAX_FACTOR;
  perf_score *= factor / POWER_BETA;

using calculate_score()

  orig_perf = perf_score = calculate_score(queue_cur);

  if (perf_score == 0) goto abandon_entry;

• Scenario 1:

If we happen to find something with our empty seed, new paths will be scheduled, q->fuzz_level remains fairly small and factor is most likely > 0. Even if factor==0 and therefore resulting perf_score==0, we have no problem, as we simply skip to another seed.

• Scenario 2:

If we happen not to find any new seeds, q->fuzz_level steadily increases and as soon as q->fuzz_level >=16 we go in the else statement:

• factor = MAX_FACTOR / (fuzz == 0 ? 1 : next_p2 (fuzz)); //will almost always be 0, as fuzz is already high
• perf_score *= factor / POWER_BETA; //will then always be 0
• if (perf_score == 0) goto abandon_entry //will then always be true

this means we are constantly skipping to the next seed, but as we only have 1 empty seed, we will constantly skip to the same one. This will explode in cycles and always skip fuzzing altogether.

This could be solved in 2 ways:

1. either patch performance score above, e.g. set factor = MAX_FACTOR
2. or implement a check, so we don't skip a seed, if we don't have anything to skip to, which is what this PR is for. We could do either of the following:
   2.1 Check whether all seeds have performance_score==0, and if so, don't skip. This is probably expensive
   2.2 Check for queued_paths, and only skip if we have a few. To be accurate: this doesn't completely solve the edge case. If every seed has a performance score of 0, this still occurs. However, with this fix the chances of it occurring should be much lower, and additionally, the changes to the original implementation are minimal. This is the suggestion of this PR.
   2.3 Similar checks are implemented https://github.com/derdav3/aflfast/blob/master/afl-fuzz.c#L5045, so another solution would be to check for pending_favorites, but I didnt investigate this further.

With the suggested code change, all my targets run just fine.

Reproduction

• Target:

sudo apt-get install libpcap-dev

wget https://www.tcpdump.org/release/tcpdump-4.9.2.tar.gz
tar -xf tcpdump-4.9.2
cd tcpdump-4.9.2

CC=~/afl/afl-clang-fast CXX=~/afl/afl-clang-fast++ LD=~/afl/afl-clang-fast ./configure
make -j $(nproc)

• Seed
  echo "" > empty
• Fuzzing
  ~/aflfast/afl-fuzz -i ./empty/ -o ./out -- ./tcpdump -nr @@

PS: Depending on your clang/llvm version, you might need [https://github.com/derdav3/aflfast/commit/2793c0920f3db51fb9bcb80301018d7e032fafc5](this patch) to compile aflfast.

[mboehme]

Wow. Thanks, David, for your explanation and your patch! Sorry for the late response.

LGTM. Merging.

[vanhauser-thc]

@mboehme @derdav3
we have something similar in afl++:

 afl-fuzz-one.c:  if (unlikely(perf_score <= 0)) { goto abandon_entry; }

does this need to be updated as well?

[ackdav]

@mboehme @derdav3
we have something similar in afl++:

 afl-fuzz-one.c:  if (unlikely(perf_score <= 0)) { goto abandon_entry; }

does this need to be updated as well?

I quickly tried to reproduce the behavior with afl++ and was not able to. However, it seems it's constantly cycling through the same behavior (havoc stage with the same amount of execs -> 1175), which is possibly not ideal. Unfortunately I'm not at all familiar with afl++, so I can't give you any more insights.

[vanhauser-thc]

Already put in a fix, thanks :)