From ae0620c4e9be8e4be0ff3d7afad260f569742659 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Tue, 3 Mar 2015 23:27:02 +0000 Subject: [PATCH] [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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231166 91177308-0d34-0410-b5e6-96231b3b80d8 --- cmake/modules/HandleLLVMOptions.cmake | 2 +- lib/Fuzzer/FuzzerDriver.cpp | 1 + lib/Fuzzer/FuzzerFlags.def | 1 + lib/Fuzzer/FuzzerInternal.h | 10 +++ lib/Fuzzer/FuzzerLoop.cpp | 14 ++++- lib/Fuzzer/test/CMakeLists.txt | 1 + lib/Fuzzer/test/CounterTest.cpp | 14 +++++ lib/Fuzzer/test/fuzzer.test | 3 + .../Instrumentation/SanitizerCoverage.cpp | 62 ++++++++++++++++--- .../SanitizerCoverage/coverage.ll | 22 ++++++- 10 files changed, 118 insertions(+), 12 deletions(-) create mode 100644 lib/Fuzzer/test/CounterTest.cpp diff --git a/cmake/modules/HandleLLVMOptions.cmake b/cmake/modules/HandleLLVMOptions.cmake index fdc4ea0b4ac..45b4d3278cb 100644 --- a/cmake/modules/HandleLLVMOptions.cmake +++ b/cmake/modules/HandleLLVMOptions.cmake @@ -424,7 +424,7 @@ if(LLVM_USE_SANITIZER) message(WARNING "LLVM_USE_SANITIZER is not supported on this platform.") endif() if (LLVM_USE_SANITIZE_COVERAGE) - append("-fsanitize-coverage=4" CMAKE_C_FLAGS CMAKE_CXX_FLAGS) + append("-fsanitize-coverage=4 -mllvm -sanitizer-coverage-8bit-counters=1" CMAKE_C_FLAGS CMAKE_CXX_FLAGS) endif() endif() diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 1746afd822d..9ccd744c28d 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -158,6 +158,7 @@ int FuzzerDriver(int argc, char **argv, UserCallback Callback) { Options.DoCrossOver = Flags.cross_over; Options.MutateDepth = Flags.mutate_depth; Options.ExitOnFirst = Flags.exit_on_first; + Options.UseCounters = Flags.use_counters; Options.UseFullCoverageSet = Flags.use_full_coverage_set; Options.UseCoveragePairs = Flags.use_coverage_pairs; Options.PreferSmallDuringInitialShuffle = diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index 068f2451b6b..08176af1169 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -32,6 +32,7 @@ FUZZER_FLAG(int, help, 0, "Print help.") FUZZER_FLAG( int, save_minimized_corpus, 0, "If 1, the minimized corpus is saved into the first input directory") +FUZZER_FLAG(int, use_counters, 0, "Use coverage counters") FUZZER_FLAG(int, use_full_coverage_set, 0, "Experimental: Maximize the number of different full" " coverage sets as opposed to maximizing the total coverage." diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 980b00ec17b..e4e5eb7fd05 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -48,6 +48,7 @@ class Fuzzer { bool DoCrossOver = true; int MutateDepth = 5; bool ExitOnFirst = false; + bool UseCounters = false; bool UseFullCoverageSet = false; bool UseCoveragePairs = false; int PreferSmallDuringInitialShuffle = -1; @@ -95,6 +96,15 @@ class Fuzzer { std::vector Corpus; std::unordered_set FullCoverageSets; std::unordered_set CoveragePairs; + + // For UseCounters + std::vector CounterBitmap; + size_t TotalBits() { // Slow. Call it only for printing stats. + size_t Res = 0; + for (auto x : CounterBitmap) Res += __builtin_popcount(x); + return Res; + } + UserCallback Callback; FuzzingOptions Options; system_clock::time_point ProcessStartTime = system_clock::now(); diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 70b63eb618a..563fbf4c30d 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -138,17 +138,28 @@ size_t Fuzzer::RunOneMaximizeFullCoverageSet(const Unit &U) { } size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) { + size_t NumCounters = __sanitizer_get_number_of_counters(); + if (Options.UseCounters) { + CounterBitmap.resize(NumCounters); + __sanitizer_update_counter_bitset_and_clear_counters(0); + } size_t OldCoverage = __sanitizer_get_total_unique_coverage(); Callback(U.data(), U.size()); size_t NewCoverage = __sanitizer_get_total_unique_coverage(); + size_t NumNewBits = 0; + if (Options.UseCounters) + NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters( + CounterBitmap.data()); + if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) { size_t Seconds = secondsSinceProcessStartUp(); std::cerr << "#" << TotalNumberOfRuns << "\tcov: " << NewCoverage + << "\tbits: " << TotalBits() << "\texec/s: " << (Seconds ? TotalNumberOfRuns / Seconds : 0) << "\n"; } - if (NewCoverage > OldCoverage) + if (NewCoverage > OldCoverage || NumNewBits) return NewCoverage; return 0; } @@ -189,6 +200,7 @@ size_t Fuzzer::MutateAndTestOne(Unit *U) { if (Options.Verbosity) { std::cerr << "#" << TotalNumberOfRuns << "\tNEW: " << NewCoverage + << " B: " << TotalBits() << " L: " << U->size() << " S: " << Corpus.size() << " I: " << i diff --git a/lib/Fuzzer/test/CMakeLists.txt b/lib/Fuzzer/test/CMakeLists.txt index bed9cd89ec9..08130c6f7da 100644 --- a/lib/Fuzzer/test/CMakeLists.txt +++ b/lib/Fuzzer/test/CMakeLists.txt @@ -5,6 +5,7 @@ set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O0 -fsanitize-coverage=4") set(Tests + CounterTest FourIndependentBranchesTest FullCoverageSetTest InfiniteTest diff --git a/lib/Fuzzer/test/CounterTest.cpp b/lib/Fuzzer/test/CounterTest.cpp new file mode 100644 index 00000000000..332ccfe7b02 --- /dev/null +++ b/lib/Fuzzer/test/CounterTest.cpp @@ -0,0 +1,14 @@ +// Test for a fuzzer: must find the case where a particular basic block is +// executed many times. +#include + +extern "C" void TestOneInput(const uint8_t *Data, size_t Size) { + int Num = 0; + for (size_t i = 0; i < Size; i++) + if (Data[i] == 'A' + i) + Num++; + if (Num >= 4) { + std::cerr << "BINGO!\n"; + exit(1); + } +} diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test index 1e42e7249da..45691f5651d 100644 --- a/lib/Fuzzer/test/fuzzer.test +++ b/lib/Fuzzer/test/fuzzer.test @@ -17,3 +17,6 @@ FullCoverageSetTest: BINGO RUN: not ./LLVMFuzzer-FourIndependentBranchesTest -timeout=15 -seed=1 -use_coverage_pairs=1 2>&1 | FileCheck %s --check-prefix=FourIndependentBranchesTest FourIndependentBranchesTest: BINGO + +RUN: not ./LLVMFuzzer-CounterTest -use_counters=1 -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s --check-prefix=CounterTest +CounterTest: BINGO diff --git a/lib/Transforms/Instrumentation/SanitizerCoverage.cpp b/lib/Transforms/Instrumentation/SanitizerCoverage.cpp index 8c56e8709e2..8f0bb460502 100644 --- a/lib/Transforms/Instrumentation/SanitizerCoverage.cpp +++ b/lib/Transforms/Instrumentation/SanitizerCoverage.cpp @@ -80,6 +80,16 @@ static cl::opt "callbacks at every basic block"), cl::Hidden, cl::init(false)); +// Experimental 8-bit counters used as an additional search heuristic during +// coverage-guided fuzzing. +// The counters are not thread-friendly: +// - contention on these counters may cause significant slowdown; +// - the counter updates are racy and the results may be inaccurate. +// They are also inaccurate due to 8-bit integer overflow. +static cl::opt ClUse8bitCounters("sanitizer-coverage-8bit-counters", + cl::desc("Experimental 8-bit counters"), + cl::Hidden, cl::init(false)); + namespace { class SanitizerCoverageModule : public ModulePass { @@ -114,6 +124,7 @@ class SanitizerCoverageModule : public ModulePass { LLVMContext *C; GlobalVariable *GuardArray; + GlobalVariable *EightBitCounterArray; int CoverageLevel; }; @@ -152,9 +163,9 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { M.getOrInsertFunction(kSanCovWithCheckName, VoidTy, Int32PtrTy, nullptr)); SanCovIndirCallFunction = checkInterfaceFunction(M.getOrInsertFunction( kSanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, nullptr)); - SanCovModuleInit = checkInterfaceFunction( - M.getOrInsertFunction(kSanCovModuleInitName, Type::getVoidTy(*C), - Int32PtrTy, IntptrTy, Int8PtrTy, nullptr)); + SanCovModuleInit = checkInterfaceFunction(M.getOrInsertFunction( + kSanCovModuleInitName, Type::getVoidTy(*C), Int32PtrTy, IntptrTy, + Int8PtrTy, Int8PtrTy, nullptr)); SanCovModuleInit->setLinkage(Function::ExternalLinkage); // We insert an empty inline asm after cov callbacks to avoid callback merge. EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), @@ -171,9 +182,15 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { // At this point we create a dummy array of guards because we don't // know how many elements we will need. Type *Int32Ty = IRB.getInt32Ty(); + Type *Int8Ty = IRB.getInt8Ty(); + GuardArray = new GlobalVariable(M, Int32Ty, false, GlobalValue::ExternalLinkage, nullptr, "__sancov_gen_cov_tmp"); + if (ClUse8bitCounters) + EightBitCounterArray = + new GlobalVariable(M, Int8Ty, false, GlobalVariable::ExternalLinkage, + nullptr, "__sancov_gen_cov_tmp"); for (auto &F : M) runOnFunction(F); @@ -186,11 +203,28 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { M, Int32ArrayNTy, false, GlobalValue::PrivateLinkage, Constant::getNullValue(Int32ArrayNTy), "__sancov_gen_cov"); + // Replace the dummy array with the real one. GuardArray->replaceAllUsesWith( IRB.CreatePointerCast(RealGuardArray, Int32PtrTy)); GuardArray->eraseFromParent(); + GlobalVariable *RealEightBitCounterArray; + if (ClUse8bitCounters) { + // Make sure the array is 16-aligned. + static const int kCounterAlignment = 16; + Type *Int8ArrayNTy = + ArrayType::get(Int8Ty, RoundUpToAlignment(SanCovFunction->getNumUses(), + kCounterAlignment)); + RealEightBitCounterArray = new GlobalVariable( + M, Int8ArrayNTy, false, GlobalValue::PrivateLinkage, + Constant::getNullValue(Int8ArrayNTy), "__sancov_gen_cov_counter"); + RealEightBitCounterArray->setAlignment(kCounterAlignment); + EightBitCounterArray->replaceAllUsesWith( + IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy)); + EightBitCounterArray->eraseFromParent(); + } + // Create variable for module (compilation unit) name Constant *ModNameStrConst = ConstantDataArray::getString(M.getContext(), M.getName(), true); @@ -200,10 +234,13 @@ bool SanitizerCoverageModule::runOnModule(Module &M) { // Call __sanitizer_cov_module_init IRB.SetInsertPoint(CtorFunc->getEntryBlock().getTerminator()); - IRB.CreateCall3(SanCovModuleInit, - IRB.CreatePointerCast(RealGuardArray, Int32PtrTy), - ConstantInt::get(IntptrTy, SanCovFunction->getNumUses()), - IRB.CreatePointerCast(ModuleName, Int8PtrTy)); + IRB.CreateCall4( + SanCovModuleInit, IRB.CreatePointerCast(RealGuardArray, Int32PtrTy), + ConstantInt::get(IntptrTy, SanCovFunction->getNumUses()), + ClUse8bitCounters + ? IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy) + : Constant::getNullValue(Int8PtrTy), + IRB.CreatePointerCast(ModuleName, Int8PtrTy)); return true; } @@ -314,6 +351,17 @@ void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, IRB.CreateCall(EmptyAsm); // Avoids callback merge. } + if(ClUse8bitCounters) { + IRB.SetInsertPoint(IP); + Value *P = IRB.CreateAdd( + IRB.CreatePointerCast(EightBitCounterArray, IntptrTy), + ConstantInt::get(IntptrTy, SanCovFunction->getNumUses() - 1)); + P = IRB.CreateIntToPtr(P, IRB.getInt8PtrTy()); + Value *LI = IRB.CreateLoad(P); + Value *Inc = IRB.CreateAdd(LI, ConstantInt::get(IRB.getInt8Ty(), 1)); + IRB.CreateStore(Inc, P); + } + if (ClExperimentalTracing) { // Experimental support for tracing. // Insert a callback with the same guard variable as used for coverage. diff --git a/test/Instrumentation/SanitizerCoverage/coverage.ll b/test/Instrumentation/SanitizerCoverage/coverage.ll index dd6b8d8dd7c..6c0f31e72e7 100644 --- a/test/Instrumentation/SanitizerCoverage/coverage.ll +++ b/test/Instrumentation/SanitizerCoverage/coverage.ll @@ -5,10 +5,8 @@ ; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=1 -S | FileCheck %s --check-prefix=CHECK_WITH_CHECK ; RUN: opt < %s -sancov -sanitizer-coverage-level=3 -sanitizer-coverage-block-threshold=10 -S | FileCheck %s --check-prefix=CHECK3 ; RUN: opt < %s -sancov -sanitizer-coverage-level=4 -S | FileCheck %s --check-prefix=CHECK4 +; RUN: opt < %s -sancov -sanitizer-coverage-level=3 -sanitizer-coverage-8bit-counters=1 -S | FileCheck %s --check-prefix=CHECK-8BIT -; RUN: opt < %s -sancov -sanitizer-coverage-level=0 -S | FileCheck %s --check-prefix=CHECK0 -; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -S | FileCheck %s --check-prefix=CHECK1 -; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -S | FileCheck %s --check-prefix=CHECK2 ; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=10 \ ; RUN: -S | FileCheck %s --check-prefix=CHECK2 ; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=1 \ @@ -78,6 +76,24 @@ entry: ; CHECK3-NOT: call void @__sanitizer_cov ; CHECK3: ret void +; test -sanitizer-coverage-8bit-counters=1 +; CHECK-8BIT-LABEL: define void @foo + +; CHECK-8BIT: [[V11:%[0-9]*]] = load i8 +; CHECK-8BIT: [[V12:%[0-9]*]] = add i8 [[V11]], 1 +; CHECK-8BIT: store i8 [[V12]] +; CHECK-8BIT: [[V21:%[0-9]*]] = load i8 +; CHECK-8BIT: [[V22:%[0-9]*]] = add i8 [[V21]], 1 +; CHECK-8BIT: store i8 [[V22]] +; CHECK-8BIT: [[V31:%[0-9]*]] = load i8 +; CHECK-8BIT: [[V32:%[0-9]*]] = add i8 [[V31]], 1 +; CHECK-8BIT: store i8 [[V32]] +; CHECK-8BIT: [[V41:%[0-9]*]] = load i8 +; CHECK-8BIT: [[V42:%[0-9]*]] = add i8 [[V41]], 1 +; CHECK-8BIT: store i8 [[V42]] + +; CHECK-8BIT: ret void + %struct.StructWithVptr = type { i32 (...)** } -- 2.34.1