[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

 }
 
 // Given a non-zero Counters returns a number in [0,7].
 template<class T>
 unsigned CounterToFeature(T Counter) {
     assert(Counter);
     unsigned Bit = 0;
     /**/ if (Counter >= 128) Bit = 7;
-    else if (Counter >= 32) Bit = 6;
-    else if (Counter >= 16) Bit = 5;
-    else if (Counter >= 8) Bit = 4;
-    else if (Counter >= 4) Bit = 3;
-    else if (Counter >= 3) Bit = 2;
+    else if (Counter >= 64) Bit = 6;
+    else if (Counter >= 32) Bit = 5;
+    else if (Counter >= 16) Bit = 4;
+    else if (Counter >= 8) Bit = 3;
+    else if (Counter >= 4) Bit = 2;
     else if (Counter >= 2) Bit = 1;
     return Bit;
 }
 
 template <class Callback>  // void Callback(size_t Feature)
 ATTRIBUTE_NO_SANITIZE_ADDRESS
 __attribute__((noinline))
 void TracePC::CollectFeatures(Callback HandleFeature) const {