[LibFuzzer] Fix `CounterToFeature()` so that it doesn't ignore the 6th bit.

[delcypher]

Summary

[LibFuzzer] Fix bug where each bit in a user supplied counter was not treated
as a distinct feature.

The CounterToFeature() function seems to ignore the 6th bit (i.e. bit
with value 64) and treats the input value of 3 specially.

Changing CounterToFeature() breaks existing tests so to avoid that
just handle user supplied counters differently.

[delcypher]

Turns out my original change to CounterToFeature() broke an existing test. To work around that I'm just changing how user supplied counters are handled instead.

[kcc]

Why do you think this is a bug?
The user-provided counter is a counter, not a bit set.

[delcypher]

In D40376#935496, @kcc wrote:

Why do you think this is a bug?
The user-provided counter is a counter, not a bit set.

I thought this was a bug because initially I thought the counters were supposed to be bit set. I realised much later when I ran into the TableLookupTest.cpp test that it was not your intention was for "__libfuzzer_extra_counters to be a bit set.
However questions still remain and I thought illustrating my thoughts with a patch might be easier to understand.

• Why is CounterToFeature() implemented the way it currently is? The obvious implementation is the one I sketch in the patch that treats each bit in the 8-bit counter as a "new feature". With that implementation we would record new features when the counter hits values [1, 2, 4, 8, 16, 32, 64, 128] (i.e. a bit set). In the current implementation we record new features when the counter hits values [1, 2, 3, 4, 8, 16, 32, 128]. It is not obvious why you've done this so I think it would be good to provide an explanation and put that in comments for the CounterToFeature() function. My guess is that you wanted events occurring a very small number (<=4) of times to be treated as features, hence the initially linear behaviour of CounterToFeature() that then becomes (sort of) exponential after 4 events have occurred.

• On a semi-related note why is the entire __libfuzzer_extra_counters section implicitly zero-ed on every call to LLVMFuzzerTestOneInput? In my case I don't actually want this because persisting the counters across calls to LLVMFuzzerTestOneInput is not a problem so I'm just wasting time by zero-ing the counters before every call to LLVMFuzzerTestOneInput. I can certainly see use cases where you would want to zero the counters before every call to LLVMFuzzerTestOneInput, however shouldn't the user just do this themselves if this is the behaviour they want?

[kcc]

In D40376#935532, @delcypher wrote:

In D40376#935496, @kcc wrote:

Why do you think this is a bug?
The user-provided counter is a counter, not a bit set.

I thought this was a bug because initially I thought the counters were supposed to be bit set. I realised much later when I ran into the TableLookupTest.cpp test that it was not your intention was for "__libfuzzer_extra_counters to be a bit set.
However questions still remain and I thought illustrating my thoughts with a patch might be easier to understand.

• Why is CounterToFeature() implemented the way it currently is? The obvious implementation is the one I sketch in the patch that treats each bit in the 8-bit counter as a "new feature". With that implementation we would record new features when the counter hits values [1, 2, 4, 8, 16, 32, 64, 128] (i.e. a bit set). In the current implementation we record new features when the counter hits values [1, 2, 3, 4, 8, 16, 32, 128]. It is not obvious why you've done this so I think it would be good to provide an explanation and put that in comments for the CounterToFeature() function. My guess is that you wanted events occurring a very small number (<=4) of times to be treated as features, hence the initially linear behaviour of CounterToFeature() that then becomes (sort of) exponential after 4 events have occurred.

Yes, just as you describe.
This is a heuristic stolen from AFL: http://lcamtuf.coredump.cx/afl/technical_details.txt (search for 128)
Once I have a proper A/B testing for libFuzzer, it may change. Please treat it as an implementation detail.

• On a semi-related note why is the entire __libfuzzer_extra_counters section implicitly zero-ed on every call to LLVMFuzzerTestOneInput? In my case I don't actually want this because persisting the counters across calls to LLVMFuzzerTestOneInput is not a problem so I'm just wasting time by zero-ing the counters before every call to LLVMFuzzerTestOneInput. I can certainly see use cases where you would want to zero the counters before every call to LLVMFuzzerTestOneInput, however shouldn't the user just do this themselves if this is the behaviour they want?

Because the coverage signal should be stable between runs.
(please prefer [e-mail] for discussions like this)

[delcypher]

In D40376#936577, @kcc wrote:

In D40376#935532, @delcypher wrote:

In D40376#935496, @kcc wrote:

Why do you think this is a bug?
The user-provided counter is a counter, not a bit set.

I thought this was a bug because initially I thought the counters were supposed to be bit set. I realised much later when I ran into the TableLookupTest.cpp test that it was not your intention was for "__libfuzzer_extra_counters to be a bit set.
However questions still remain and I thought illustrating my thoughts with a patch might be easier to understand.

• Why is CounterToFeature() implemented the way it currently is? The obvious implementation is the one I sketch in the patch that treats each bit in the 8-bit counter as a "new feature". With that implementation we would record new features when the counter hits values [1, 2, 4, 8, 16, 32, 64, 128] (i.e. a bit set). In the current implementation we record new features when the counter hits values [1, 2, 3, 4, 8, 16, 32, 128]. It is not obvious why you've done this so I think it would be good to provide an explanation and put that in comments for the CounterToFeature() function. My guess is that you wanted events occurring a very small number (<=4) of times to be treated as features, hence the initially linear behaviour of CounterToFeature() that then becomes (sort of) exponential after 4 events have occurred.

Yes, just as you describe.
This is a heuristic stolen from AFL: http://lcamtuf.coredump.cx/afl/technical_details.txt (search for 128)
Once I have a proper A/B testing for libFuzzer, it may change. Please treat it as an implementation detail.

Okay. I've created https://reviews.llvm.org/D40565 to try and improve the comments here so it is clearer to others why
the current implementation is used.

• On a semi-related note why is the entire __libfuzzer_extra_counters section implicitly zero-ed on every call to LLVMFuzzerTestOneInput? In my case I don't actually want this because persisting the counters across calls to LLVMFuzzerTestOneInput is not a problem so I'm just wasting time by zero-ing the counters before every call to LLVMFuzzerTestOneInput. I can certainly see use cases where you would want to zero the counters before every call to LLVMFuzzerTestOneInput, however shouldn't the user just do this themselves if this is the behaviour they want?

Because the coverage signal should be stable between runs.
(please prefer [e-mail] for discussions like this)

Okay. I'll do that in the future.

[delcypher]

Abandoning this patch in favour of https://reviews.llvm.org/D40565 .

lib/fuzzer/FuzzerTracePC.h

if (size_t NumClangCounters = ClangCountersEnd() - ClangCountersBegin()) {
     auto P = ClangCountersBegin();
     for (size_t Idx = 0; Idx < NumClangCounters; Idx++)
       if (auto Cnt = P[Idx])
         HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Cnt));
     FirstFeature += NumClangCounters;
   }
 
   ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), FirstFeature,
-                     Handle8bitCounter);
+                     [&](size_t FirstFeature, size_t Idx, uint8_t Counter) {
+    assert(Counter);
+    // Convert to Counter to a Feature. This is similar to the
+    // `CounterToFeature()` function but here each bit in the counter
+    // is treated as a distinct feature.
+    unsigned int MSBit = sizeof(unsigned int) * 8 - __builtin_clz(Counter);
+    assert(MSBit >=0 && MSBit < 8);
+    size_t Feature = MSBit -1;
+    HandleFeature(FirstFeature + Idx * 8 + Feature);
+  });
   FirstFeature += (ExtraCountersEnd() - ExtraCountersBegin()) * 8;
 
   if (UseValueProfile) {
     ValueProfileMap.ForEach([&](size_t Idx) {
       HandleFeature(FirstFeature + Idx);
     });
     FirstFeature += ValueProfileMap.SizeInBits();
   }

test/fuzzer/SingleExtraCounterTest.cpp

+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+#include <cassert>
+#include <cstdint>
+#include <cstdio>
+
+#ifdef __linux__
+__attribute__((section("__libfuzzer_extra_counters")))
+#endif
+    static uint8_t Counters[1];
+
+// This tests that every bit inside a counter is used as a signal
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  static int RunCount = 0;
+  fprintf(stderr, "Doing run: #%d\n", RunCount);
+  // FIXME: The is fragile, why two runs before init is done?
+  // The first two runs of this function are for LibFuzzers init so
+  // don't modify counters until after they are done.
+  if (RunCount < 2) {
+    ++RunCount;
+    return 0;
+  }
+  int BitToSet = RunCount - 2;
+  assert(BitToSet >= 0 & BitToSet <= 7);
+  // LibFuzzer should reset this for every call
+  assert(Counters[0] == 0);
+  fprintf(stderr, "Setting bit: %d\n", BitToSet);
+  Counters[0] = (1 << BitToSet);
+  ++RunCount;
+  return 0;
+}

test/fuzzer/single-extra-counter.test

+REQUIRES: linux
+RUN: %cpp_compiler %S/SingleExtraCounterTest.cpp -o %t-SingleExtraCounterTest
+RUN: %t-SingleExtraCounterTest -max_len=1 -seed=0 -runs=10 -print_final_stats=1 2>&1 | FileCheck %s
+
+CHECK: Setting bit: 0
+CHECK-NEXT: #3 {{ *}}NEW
+CHECK: Setting bit: 1
+CHECK-NEXT: #4 {{ *}}NEW
+CHECK: Setting bit: 2
+CHECK-NEXT: #5 {{ *}}NEW
+CHECK: Setting bit: 3
+CHECK-NEXT: #6 {{ *}}NEW
+CHECK: Setting bit: 4
+CHECK-NEXT: #7 {{ *}}NEW
+CHECK: Setting bit: 5
+CHECK-NEXT: #8 {{ *}}NEW
+CHECK: Setting bit: 6
+CHECK-NEXT: #9 {{ *}}NEW
+CHECK: Setting bit: 7
+CHECK-NEXT: #10 {{ *}}NEW
+
+CHECK: number_of_executed_units:{{ *}}10
+CHECK: new_units_added:{{ *}}8