From 7bcc4cdbdd7d6cd22d023e284c635152edb77c15 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Thu, 22 Oct 2015 23:55:39 +0000 Subject: [PATCH] [libFuzzer] use the indirect caller-callee counter as an independent search heuristic git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251078 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerDriver.cpp | 1 + lib/Fuzzer/FuzzerFlags.def | 1 + lib/Fuzzer/FuzzerInternal.h | 3 ++ lib/Fuzzer/FuzzerLoop.cpp | 15 +++++++- lib/Fuzzer/test/CMakeLists.txt | 1 + lib/Fuzzer/test/CallerCalleeTest.cpp | 56 ++++++++++++++++++++++++++++ lib/Fuzzer/test/fuzzer.test | 3 ++ 7 files changed, 79 insertions(+), 1 deletion(-) create mode 100644 lib/Fuzzer/test/CallerCalleeTest.cpp diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 4543d81cb1e..f9cb28a6e51 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -234,6 +234,7 @@ int FuzzerDriver(const std::vector &Args, Options.MutateDepth = Flags.mutate_depth; Options.ExitOnFirst = Flags.exit_on_first; Options.UseCounters = Flags.use_counters; + Options.UseIndirCalls = Flags.use_indir_calls; Options.UseTraces = Flags.use_traces; Options.ShuffleAtStartUp = Flags.shuffle; Options.PreferSmallDuringInitialShuffle = diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index 0ae567af1d9..cea28e3bf04 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -37,6 +37,7 @@ FUZZER_FLAG_INT( "If 1, the minimized corpus is saved into the first input directory. " "Example: ./fuzzer -save_minimized_corpus=1 NEW_EMPTY_DIR OLD_CORPUS") FUZZER_FLAG_INT(use_counters, 1, "Use coverage counters") +FUZZER_FLAG_INT(use_indir_calls, 1, "Use indirect caller-callee counters") FUZZER_FLAG_INT(use_traces, 0, "Experimental: use instruction traces") FUZZER_FLAG_INT(jobs, 0, "Number of jobs to run. If jobs >= 1 we spawn" " this number of jobs in separate worker processes" diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 919516a703c..7a90ce1ac65 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -79,6 +79,7 @@ class Fuzzer { int MutateDepth = 5; bool ExitOnFirst = false; bool UseCounters = false; + bool UseIndirCalls = true; bool UseTraces = false; bool UseFullCoverageSet = false; bool Reload = true; @@ -134,6 +135,7 @@ class Fuzzer { void SyncCorpus(); size_t RecordBlockCoverage(); + size_t RecordCallerCalleeCoverage(); void PrepareCoverageBeforeRun(); bool CheckCoverageAfterRun(); @@ -176,6 +178,7 @@ class Fuzzer { long TimeOfLongestUnitInSeconds = 0; long EpochOfLastReadOfOutputCorpus = 0; size_t LastRecordedBlockCoverage = 0; + size_t LastRecordedCallerCalleeCoverage = 0; }; class SimpleUserSuppliedFuzzer: public UserSuppliedFuzzer { diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 6ac8997df78..4f0d9988131 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -92,6 +92,8 @@ void Fuzzer::PrintStats(const char *Where, const char *End) { Printf(" cov: %zd", LastRecordedBlockCoverage); if (auto TB = TotalBits()) Printf(" bits: %zd", TB); + if (LastRecordedCallerCalleeCoverage) + Printf(" indir: %zd", LastRecordedCallerCalleeCoverage); Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec); if (TotalNumberOfExecutedTraceBasedMutations) Printf(" tbm: %zd", TotalNumberOfExecutedTraceBasedMutations); @@ -202,6 +204,13 @@ size_t Fuzzer::RecordBlockCoverage() { return LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage(); } +size_t Fuzzer::RecordCallerCalleeCoverage() { + if (!Options.UseIndirCalls) + return 0; + return LastRecordedCallerCalleeCoverage = + __sanitizer_get_total_unique_caller_callee_pairs(); +} + void Fuzzer::PrepareCoverageBeforeRun() { if (Options.UseCounters) { size_t NumCounters = __sanitizer_get_number_of_counters(); @@ -209,16 +218,20 @@ void Fuzzer::PrepareCoverageBeforeRun() { __sanitizer_update_counter_bitset_and_clear_counters(0); } RecordBlockCoverage(); + RecordCallerCalleeCoverage(); } bool Fuzzer::CheckCoverageAfterRun() { size_t OldCoverage = LastRecordedBlockCoverage; size_t NewCoverage = RecordBlockCoverage(); + size_t OldCallerCalleeCoverage = LastRecordedCallerCalleeCoverage; + size_t NewCallerCalleeCoverage = RecordCallerCalleeCoverage(); size_t NumNewBits = 0; if (Options.UseCounters) NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters( CounterBitmap.data()); - return NewCoverage > OldCoverage || NumNewBits; + return NewCoverage > OldCoverage || + NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits; } void Fuzzer::WriteToOutputCorpus(const Unit &U) { diff --git a/lib/Fuzzer/test/CMakeLists.txt b/lib/Fuzzer/test/CMakeLists.txt index a9024f809ba..bb70e7e01ae 100644 --- a/lib/Fuzzer/test/CMakeLists.txt +++ b/lib/Fuzzer/test/CMakeLists.txt @@ -13,6 +13,7 @@ set(DFSanTests ) set(Tests + CallerCalleeTest CounterTest FourIndependentBranchesTest FullCoverageSetTest diff --git a/lib/Fuzzer/test/CallerCalleeTest.cpp b/lib/Fuzzer/test/CallerCalleeTest.cpp new file mode 100644 index 00000000000..150b2fc0405 --- /dev/null +++ b/lib/Fuzzer/test/CallerCalleeTest.cpp @@ -0,0 +1,56 @@ +// Simple test for a fuzzer. +// Try to find the target using the indirect caller-callee pairs. +#include +#include +#include +#include +#include + +typedef void (*F)(); +static F t[256]; + +void f34() { + std::cerr << "BINGO\n"; + exit(1); +} +void f23() { t[(unsigned)'d'] = f34;} +void f12() { t[(unsigned)'c'] = f23;} +void f01() { t[(unsigned)'b'] = f12;} +void f00() {} + +static F t0[256] = { + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, + f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, f00, +}; + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size < 4) return 0; + // Spoof the counters. + for (int i = 0; i < 200; i++) { + f23(); + f12(); + f01(); + } + memcpy(t, t0, sizeof(t)); + t[(unsigned)'a'] = f01; + t[Data[0]](); + t[Data[1]](); + t[Data[2]](); + t[Data[3]](); + return 0; +} + diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test index 8530bcc61b7..94db0fe4ce0 100644 --- a/lib/Fuzzer/test/fuzzer.test +++ b/lib/Fuzzer/test/fuzzer.test @@ -35,6 +35,9 @@ NullDerefTestPrefix: Test unit written to ZZZcrash- RUN: not LLVMFuzzer-CounterTest -use_counters=1 -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s +RUN: not LLVMFuzzer-CallerCalleeTest -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s +RUN: LLVMFuzzer-CallerCalleeTest -use_indir_calls=0 -max_len=6 -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 + RUN: not LLVMFuzzer-SimpleCmpTest -use_traces=1 -seed=1 -runs=1000000 -timeout=5 2>&1 | FileCheck %s RUN: not LLVMFuzzer-UserSuppliedFuzzerTest -seed=1 -timeout=15 2>&1 | FileCheck %s -- 2.34.1