[sanitizer/coverage] Add AFL-style coverage counters (search heuristic for fuzzing).
Introduce -mllvm -sanitizer-coverage-8bit-counters=1
which adds imprecise thread-unfriendly 8-bit coverage counters.
The run-time library maps these 8-bit counters to 8-bit bitsets in the same way
AFL (http://lcamtuf.coredump.cx/afl/technical_details.txt) does:
counter values are divided into 8 ranges and based on the counter
value one of the bits in the bitset is set.
The AFL ranges are used here: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+.
These counters provide a search heuristic for single-threaded
coverage-guided fuzzers, we do not expect them to be useful for other purposes.
Depending on the value of -fsanitize-coverage=[123] flag,
these counters will be added to the function entry blocks (=1),
every basic block (=2), or every edge (=3).
Use these counters as an optional search heuristic in the Fuzzer library.
Add a test where this heuristic is critical.
llvm-svn: 231166
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_coverage_libcdep.cc b/compiler-rt/lib/sanitizer_common/sanitizer_coverage_libcdep.cc
index 49887b1..7197b4c 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_coverage_libcdep.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_coverage_libcdep.cc
@@ -83,7 +83,10 @@
void InitializeGuardArray(s32 *guards);
void InitializeGuards(s32 *guards, uptr n, const char *module_name);
+ void InitializeCounters(u8 *counters, uptr n);
void ReinitializeGuards();
+ uptr GetNumberOf8bitCounters();
+ uptr Update8bitCounterBitsetAndClearCounters(u8 *bitset);
uptr *data();
uptr size();
@@ -113,6 +116,14 @@
// Vector of module (compilation unit) names.
InternalMmapVectorNoCtor<const char*> comp_unit_name_vec;
+ struct CounterAndSize {
+ u8 *counters;
+ uptr n;
+ };
+
+ InternalMmapVectorNoCtor<CounterAndSize> counters_vec;
+ uptr num_8bit_counters;
+
// Caller-Callee (cc) array, size and current index.
static const uptr kCcArrayMaxSize = FIRST_32_SECOND_64(1 << 18, 1 << 24);
uptr **cc_array;
@@ -184,6 +195,8 @@
GetMmapGranularity());
tr_event_array_size = kTrEventArrayMaxSize;
tr_event_pointer = tr_event_array;
+
+ num_8bit_counters = 0;
}
void CoverageData::InitializeGuardArray(s32 *guards) {
@@ -289,6 +302,15 @@
atomic_store(&pc_array_size, size, memory_order_release);
}
+void CoverageData::InitializeCounters(u8 *counters, uptr n) {
+ if (!counters) return;
+ CHECK_EQ(reinterpret_cast<uptr>(counters) % 16, 0);
+ n = RoundUpTo(n, 16); // The compiler must ensure that counters is 16-aligned.
+ SpinMutexLock l(&mu);
+ counters_vec.push_back({counters, n});
+ num_8bit_counters += n;
+}
+
void CoverageData::InitializeGuards(s32 *guards, uptr n,
const char *module_name) {
// The array 'guards' has n+1 elements, we use the element zero
@@ -354,6 +376,64 @@
}
}
+uptr CoverageData::GetNumberOf8bitCounters() {
+ return num_8bit_counters;
+}
+
+// Map every 8bit counter to a 8-bit bitset and clear the counter.
+uptr CoverageData::Update8bitCounterBitsetAndClearCounters(u8 *bitset) {
+ uptr num_new_bits = 0;
+ uptr cur = 0;
+ // For better speed we map 8 counters to 8 bytes of bitset at once.
+ static const uptr kBatchSize = 8;
+ CHECK_EQ(reinterpret_cast<uptr>(bitset) % kBatchSize, 0);
+ for (uptr i = 0, len = counters_vec.size(); i < len; i++) {
+ u8 *c = counters_vec[i].counters;
+ uptr n = counters_vec[i].n;
+ CHECK_EQ(n % 16, 0);
+ CHECK_EQ(cur % kBatchSize, 0);
+ CHECK_EQ(reinterpret_cast<uptr>(c) % kBatchSize, 0);
+ if (!bitset) {
+ internal_bzero_aligned16(c, n);
+ cur += n;
+ continue;
+ }
+ for (uptr j = 0; j < n; j += kBatchSize, cur += kBatchSize) {
+ CHECK_LT(cur, num_8bit_counters);
+ u64 *pc64 = reinterpret_cast<u64*>(c + j);
+ u64 *pb64 = reinterpret_cast<u64*>(bitset + cur);
+ u64 c64 = *pc64;
+ u64 old_bits_64 = *pb64;
+ u64 new_bits_64 = old_bits_64;
+ if (c64) {
+ *pc64 = 0;
+ for (uptr k = 0; k < kBatchSize; k++) {
+ u64 x = (c64 >> (8 * k)) & 0xff;
+ if (x) {
+ u64 bit = 0;
+ /**/ if (x >= 128) bit = 128;
+ else if (x >= 32) bit = 64;
+ else if (x >= 16) bit = 32;
+ else if (x >= 8) bit = 16;
+ else if (x >= 4) bit = 8;
+ else if (x >= 3) bit = 4;
+ else if (x >= 2) bit = 2;
+ else if (x >= 1) bit = 1;
+ u64 mask = bit << (8 * k);
+ if (!(new_bits_64 & mask)) {
+ num_new_bits++;
+ new_bits_64 |= mask;
+ }
+ }
+ }
+ *pb64 = new_bits_64;
+ }
+ }
+ }
+ CHECK_EQ(cur, num_8bit_counters);
+ return num_new_bits;
+}
+
uptr *CoverageData::data() {
return pc_array;
}
@@ -689,8 +769,10 @@
}
SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov_dump() { CovDump(); }
SANITIZER_INTERFACE_ATTRIBUTE void
-__sanitizer_cov_module_init(s32 *guards, uptr npcs, const char *module_name) {
+__sanitizer_cov_module_init(s32 *guards, uptr npcs, u8 *counters,
+ const char *module_name) {
coverage_data.InitializeGuards(guards, npcs, module_name);
+ coverage_data.InitializeCounters(counters, npcs);
if (!common_flags()->coverage_direct) return;
if (SANITIZER_ANDROID && coverage_enabled) {
// dlopen/dlclose interceptors do not work on Android, so we rely on
@@ -728,4 +810,14 @@
*data = coverage_data.data();
return coverage_data.size();
}
+
+SANITIZER_INTERFACE_ATTRIBUTE
+uptr __sanitizer_get_number_of_counters() {
+ return coverage_data.GetNumberOf8bitCounters();
+}
+
+SANITIZER_INTERFACE_ATTRIBUTE
+uptr __sanitizer_update_counter_bitset_and_clear_counters(u8 *bitset) {
+ return coverage_data.Update8bitCounterBitsetAndClearCounters(bitset);
+}
} // extern "C"