Note on libFuzzer Source Code

Brief Intro

libFuzzer is a util for fuzzing different C/C++ library. It’s quite handy to begin, we only need to define:

int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size);

Then, we pass the data to the library API. Here is an example from fuzzer test suite:

SSL_CTX *Init() {
  SSL_library_init();
  SSL_load_error_strings();
  ERR_load_BIO_strings();
  OpenSSL_add_all_algorithms();
  SSL_CTX *sctx;
  assert (sctx = SSL_CTX_new(TLSv1_method()));
  /* These two file were created with this command:
      openssl req -x509 -newkey rsa:512 -keyout server.key \
     -out server.pem -days 9999 -nodes -subj /CN=a/
  */
  assert(SSL_CTX_use_certificate_file(sctx, CERT_PATH "server.pem",
                                      SSL_FILETYPE_PEM));
  assert(SSL_CTX_use_PrivateKey_file(sctx, CERT_PATH "server.key",
                                     SSL_FILETYPE_PEM));
  return sctx;
}

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
  static SSL_CTX *sctx = Init();
  SSL *server = SSL_new(sctx);
  BIO *sinbio = BIO_new(BIO_s_mem());
  BIO *soutbio = BIO_new(BIO_s_mem());
  SSL_set_bio(server, sinbio, soutbio);
  SSL_set_accept_state(server);
  BIO_write(sinbio, data, size);
  SSL_do_handshake(server);
  SSL_free(server);
  return 0;
}

Initialization

User Defined Functions

FuzzerDriver initialized the whole fuzzer. It collects all the external functions to global variable EF:

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
  using namespace fuzzer;
  assert(argc && argv && "Argument pointers cannot be nullptr");
  std::string Argv0((*argv)[0]);
  EF = new ExternalFunctions();

Some have been defined in FuzzerInterface at the beginning:

// Mandatory user-provided target function.
// Executes the code under test with [Data, Data+Size) as the input.
// libFuzzer will invoke this function *many* times with different inputs.
// Must return 0.
FUZZER_INTERFACE_VISIBILITY int
LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size);

// Optional user-provided initialization function.
// If provided, this function will be called by libFuzzer once at startup.
// It may read and modify argc/argv.
// Must return 0.
FUZZER_INTERFACE_VISIBILITY int LLVMFuzzerInitialize(int *argc, char ***argv);

// Optional user-provided custom mutator.
// Mutates raw data in [Data, Data+Size) inplace.
// Returns the new size, which is not greater than MaxSize.
// Given the same Seed produces the same mutation.
FUZZER_INTERFACE_VISIBILITY size_t
LLVMFuzzerCustomMutator(uint8_t *Data, size_t Size, size_t MaxSize,
                        unsigned int Seed);

// Optional user-provided custom cross-over function.
// Combines pieces of Data1 & Data2 together into Out.
// Returns the new size, which is not greater than MaxOutSize.
// Should produce the same mutation given the same Seed.
FUZZER_INTERFACE_VISIBILITY size_t
LLVMFuzzerCustomCrossOver(const uint8_t *Data1, size_t Size1,
                          const uint8_t *Data2, size_t Size2, uint8_t *Out,
                          size_t MaxOutSize, unsigned int Seed);

// Experimental, may go away in future.
// libFuzzer-provided function to be used inside LLVMFuzzerCustomMutator.
// Mutates raw data in [Data, Data+Size) inplace.
// Returns the new size, which is not greater than MaxSize.
FUZZER_INTERFACE_VISIBILITY size_t
LLVMFuzzerMutate(uint8_t *Data, size_t Size, size_t MaxSize);

As the comment suggests, user needs to implement these functions to interact with libFuzzer. Despite interface functions, it also collect functions provided by other sanitizer:

// Sanitizer functions
EXT_FUNC(__lsan_enable, void, (), false);
EXT_FUNC(__lsan_disable, void, (), false);
EXT_FUNC(__lsan_do_recoverable_leak_check, int, (), false);
EXT_FUNC(__sanitizer_acquire_crash_state, int, (), true);
EXT_FUNC(__sanitizer_install_malloc_and_free_hooks, int,
         (void (*malloc_hook)(const volatile void *, size_t),
          void (*free_hook)(const volatile void *)),
         false);
EXT_FUNC(__sanitizer_log_write, void, (const char *buf, size_t len), false);
EXT_FUNC(__sanitizer_purge_allocator, void, (), false);
EXT_FUNC(__sanitizer_print_memory_profile, void, (size_t, size_t), false);
EXT_FUNC(__sanitizer_print_stack_trace, void, (), true);
EXT_FUNC(__sanitizer_symbolize_pc, void,
         (void *, const char *fmt, char *out_buf, size_t out_buf_size), false);
EXT_FUNC(__sanitizer_get_module_and_offset_for_pc, int,
         (void *pc, char *module_path,
         size_t module_path_len,void **pc_offset), false);
EXT_FUNC(__sanitizer_set_death_callback, void, (void (*)(void)), true);
EXT_FUNC(__sanitizer_set_report_fd, void, (void*), false);
EXT_FUNC(__msan_scoped_disable_interceptor_checks, void, (), false);
EXT_FUNC(__msan_scoped_enable_interceptor_checks, void, (), false);
EXT_FUNC(__msan_unpoison, void, (const volatile void *, size_t size), false);
EXT_FUNC(__msan_unpoison_param, void, (size_t n), false);

Unlike AFL, which implements all utilities itself, libFuzzer relies on LLVM sanitizers. Sanitizers allow libFuzzer to track coverage, bugs, and printing in a user-friendly format.

Half of your CPUs are used by default: Flags.workers = std::min(NumberOfCpuCores() / 2, Flags.jobs);.

After initializing different flags trivially, we reach:

...
auto *MD = new MutationDispatcher(Rand, Options);
auto *Corpus = new InputCorpus(Options.OutputCorpus);
auto *F = new Fuzzer(Callback, *Corpus, *MD, Options);
...

Mutation Dispatcher

The first one is MutationDispatcher. The utility class provide different mutation methods. All strategies are inserted to DefaultMutator. The mutation function does exactly as the name indicates. We won’t step further on those functions. Basically, we can group them into byte operations, cross-over, and loading dictionary. If user customizes mutation methods, libFuzzer only uses user-provided functions (and no more default mutations). Eventually customized cross-over function is pushed to the set once implemented:

...
DefaultMutators.insert
    DefaultMutators.begin(),
    {
        {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
        {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
        {&MutationDispatcher::Mutate_InsertRepeatedBytes,
        "InsertRepeatedBytes"},
        {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
        {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
        {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
        {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
        {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
        {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
        {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
        {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
        "ManualDict"},
        {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
        "PersAutoDict"},
    });
if(Options.UseCmp)
  DefaultMutators.push_back(
    {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"});

if (EF->LLVMFuzzerCustomMutator)
  Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
else
  Mutators = DefaultMutators;

if (EF->LLVMFuzzerCustomCrossOver)
  Mutators.push_back(
    {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
...

InputCorpus and Fuzzer

InputCorpus collects the generated input. The constructor initializes data in InputSizesPerFeature and SmallestElementPerFeature for storing COVs.

Fuzzer and CallBack function (the call back function is LLVMFuzzerTestOneInput actually) are assigned to variable F with some trivial loadings:

Fuzzer::Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
               FuzzingOptions Options)
    : CB(CB), Corpus(Corpus), MD(MD), Options(Options) {
  if (EF->__sanitizer_set_death_callback)
    EF->__sanitizer_set_death_callback(StaticDeathCallback);
  assert(!F);
  F = this;
  // clean up the coverage counter
  TPC.ResetMaps();
  IsMyThread = true;
  if (Options.DetectLeaks && EF->__sanitizer_install_malloc_and_free_hooks)
    EF->__sanitizer_install_malloc_and_free_hooks(MallocHook, FreeHook);
  TPC.SetUseCounters(Options.UseCounters);
  TPC.SetUseValueProfileMask(Options.UseValueProfile);

  if (Options.Verbosity)
    TPC.PrintModuleInfo();
  if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec)
    EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus);
  MaxInputLen = MaxMutationLen = Options.MaxLen;
  TmpMaxMutationLen = 0;  // Will be set once we load the corpus.
  AllocateCurrentUnitData();
  CurrentUnitSize = 0;
  memset(BaseSha1, 0, sizeof(BaseSha1));
}

After loading flags and some varaible, libFuzzer will enter different modes depending on command arguments. Let’s analyze one by one.

Multi-Processes Mode

In FuzzerDriver, libFuzzer checks workers and jobs flags:

  if (Flags.workers > 0 && Flags.jobs > 0)
    return RunInMultipleProcesses(Args, Flags.workers, Flags.jobs);

Then, it will create a number of threads according to workers number:

static int RunInMultipleProcesses(const Vector<std::string> &Args,
                                  unsigned NumWorkers, unsigned NumJobs) {
...
  for (unsigned i = 0; i < NumWorkers; i++)
    V.push_back(std::thread(WorkerThread, std::ref(Cmd), &Counter, NumJobs, &HasErrors));
  for (auto &T : V)
    T.join();
...
}

WorkerThread will run for NumJobs times and derive fuzzing commands without providing worker and job parameter. Then use system() functions to run the new command:

static void WorkerThread(const Command &BaseCmd, std::atomic<unsigned> *Counter,
                         unsigned NumJobs, std::atomic<bool> *HasErrors) {
  while (true) {
    unsigned C = (*Counter)++;
    if (C >= NumJobs) break;
    std::string Log = "fuzz-" + std::to_string(C) + ".log";
    Command Cmd(BaseCmd);
    Cmd.setOutputFile(Log);
    Cmd.combineOutAndErr();
...
    int ExitCode = ExecuteCommand(Cmd);
...
  }
}

TracePC Class

Before diving to fuzzer mode, we should take a look at TracePC. This module implements trace_pc_guard to collect features (similar to coverage) from a process in runtime. PC refers to program counter here. We can see the hooks from FuzzerTracePc.cpp (The source code is too long to paste here, but I recommend you to read them from the bottom of FuzzerTracePc.cpp). You can also find definitions of trace-pc-guard here

A program counter records the execution of instructions, it increase 1 by every execution

Tracing the Execution

Let’s see initialization first. TracePC finds the path of a program by inserting counter at the end of each edge. After executing each edge, HandleInline8bitCountersInit is invoked. The start address and stop address (refer to the begin and end of pc guard address which stores execution times of corresponding segment) will be rounded.

To avoid counting cycles, libFuzzer checks if current start address equals to the previous one. The function is terminated once in redundant cycles. Otherwise libFuzzer inserts a new module, with regions from start address to stop address sliced by page size (4096 by default).

void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) {
  if (Start == Stop) return;
  if (NumModules &&
      Modules[NumModules - 1].Start() == Start)
    return;
  assert(NumModules <
         sizeof(Modules) / sizeof(Modules[0]));
  auto &M = Modules[NumModules++];
  uint8_t *AlignedStart = RoundUpByPage(Start);
  uint8_t *AlignedStop  = RoundDownByPage(Stop);
  size_t NumFullPages = AlignedStop > AlignedStart ?
                        (AlignedStop - AlignedStart) / PageSize() : 0;
  bool NeedFirst = Start < AlignedStart || !NumFullPages;
  bool NeedLast  = Stop > AlignedStop && AlignedStop >= AlignedStart;
  M.NumRegions = NumFullPages + NeedFirst + NeedLast;;
  assert(M.NumRegions > 0);
  M.Regions = new Module::Region[M.NumRegions];
  assert(M.Regions);
  size_t R = 0;
  if (NeedFirst)
    M.Regions[R++] = {Start, std::min(Stop, AlignedStart), true, false};
  for (uint8_t *P = AlignedStart; P < AlignedStop; P += PageSize())
    M.Regions[R++] = {P, P + PageSize(), true, true};
  if (NeedLast)
    M.Regions[R++] = {AlignedStop, Stop, true, false};
  assert(R == M.NumRegions);
  assert(M.Size() == (size_t)(Stop - Start));
  assert(M.Stop() == Stop);
  assert(M.Start() == Start);
  NumInline8bitCounters += M.Size();
}

...

// compiler will insert inline counter increments on every edge
ATTRIBUTE_INTERFACE
void __sanitizer_cov_8bit_counters_init(uint8_t *Start, uint8_t *Stop) {
  fuzzer::TPC.HandleInline8bitCountersInit(Start, Stop);
}

Region has four attributes - start/stop address and two boolean indicating wether the page is enabled or a full page. The two boolean are false by default because of previous clean up operation TRC.ReseMaps() in Fuzzer constructor:

struct Region {
  uint8_t *Start, *Stop;
  bool Enabled;
  bool OneFullPage;
};

Each element in Modules has a corresponding ModulePCTable (match by index). HandlePCsInit records all instrumented PCs information, including instrumented PC address and PCFlags for determining entry point:

void TracePC::HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop) {
  const PCTableEntry *B = reinterpret_cast<const PCTableEntry *>(Start);
  const PCTableEntry *E = reinterpret_cast<const PCTableEntry *>(Stop);
  if (NumPCTables && ModulePCTable[NumPCTables - 1].Start == B) return;
  assert(NumPCTables < sizeof(ModulePCTable) / sizeof(ModulePCTable[0]));
  ModulePCTable[NumPCTables++] = {B, E};
  NumPCsInPCTables += E - B;
}

...

// With -fsanitize-coverage=pc-table the compiler will create a table of instrumented PCs
ATTRIBUTE_INTERFACE
void __sanitizer_cov_pcs_init(const uintptr_t *pcs_beg,
                              const uintptr_t *pcs_end) {
  fuzzer::TPC.HandlePCsInit(pcs_beg, pcs_end);
}

Program Features

At the end of FuzzerTrace.cpp, you can find following implementation for trace-pc sanitizer. It turns out that libFuzzer hooks comparison function (including string and memory comparison), switch, and cmp instructions. Arguments from functions/instructions are passed to HandleCmp and AddValueForMemcmp. libFuzzer stores them because comparisons are more likely to affect control flow

extern "C" {
ATTRIBUTE_INTERFACE
void __sanitizer_cov_8bit_counters_init(uint8_t *Start, uint8_t *Stop) {
  fuzzer::TPC.HandleInline8bitCountersInit(Start, Stop);
}

ATTRIBUTE_INTERFACE
void __sanitizer_cov_pcs_init(const uintptr_t *pcs_beg,
                              const uintptr_t *pcs_end) {
  fuzzer::TPC.HandlePCsInit(pcs_beg, pcs_end);
}

ATTRIBUTE_INTERFACE
ATTRIBUTE_NO_SANITIZE_ALL
void __sanitizer_cov_trace_pc_indir(uintptr_t Callee) {
  uintptr_t PC = reinterpret_cast<uintptr_t>(GET_CALLER_PC());
  fuzzer::TPC.HandleCallerCallee(PC, Callee);
}

ATTRIBUTE_INTERFACE
ATTRIBUTE_NO_SANITIZE_ALL
ATTRIBUTE_TARGET_POPCNT
void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2) {
  uintptr_t PC = reinterpret_cast<uintptr_t>(GET_CALLER_PC());
  fuzzer::TPC.HandleCmp(PC, Arg1, Arg2);
}

... // ignore many functions with identical usage

ATTRIBUTE_INTERFACE ATTRIBUTE_NO_SANITIZE_MEMORY
void __sanitizer_weak_hook_memmem(void *called_pc, const void *s1, size_t len1,
                                  const void *s2, size_t len2, void *result) {
  if (!fuzzer::RunningUserCallback) return;
  fuzzer::TPC.MMT.Add(reinterpret_cast<const uint8_t *>(s2), len2);
}
}  // extern "C"

HandleCmp converts two argument to a hash, then uses the hash as index for storing in TableOfRecentCompares, which is a bis-set based hash map. Similar to HandleCmp, AddValueForMemcmp computes hash of two strings and add it to the table. Every new bit is represented as a new coverage:

ATTRIBUTE_NO_SANITIZE_ALL
void TracePC::AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
                                size_t n, bool StopAtZero) {
  if (!n) return;
  size_t Len = std::min(n, Word::GetMaxSize());
  const uint8_t *A1 = reinterpret_cast<const uint8_t *>(s1);
  const uint8_t *A2 = reinterpret_cast<const uint8_t *>(s2);
  uint8_t B1[Word::kMaxSize];
  uint8_t B2[Word::kMaxSize];
  // Copy the data into locals in this non-msan-instrumented function
  // to avoid msan complaining further.
  size_t Hash = 0;  // Compute some simple hash of both strings.
  for (size_t i = 0; i < Len; i++) {
    B1[i] = A1[i];
    B2[i] = A2[i];
    size_t T = B1[i];
    Hash ^= (T << 8) | B2[i];
  }
  size_t I = 0;
  uint8_t HammingDistance = 0;
  for (; I < Len; I++) {
    if (B1[I] != B2[I] || (StopAtZero && B1[I] == 0)) {
      HammingDistance = Popcountll(B1[I] ^ B2[I]);
      break;
    }
  }
  size_t PC = reinterpret_cast<size_t>(caller_pc);
  size_t Idx = (PC & 4095) | (I << 12);
  Idx += HammingDistance;
  ValueProfileMap.AddValue(Idx);
  TORCW.Insert(Idx ^ Hash, Word(B1, Len), Word(B2, Len));
}

template <class T>
ATTRIBUTE_TARGET_POPCNT ALWAYS_INLINE
ATTRIBUTE_NO_SANITIZE_ALL
void TracePC::HandleCmp(uintptr_t PC, T Arg1, T Arg2) {
  uint64_t ArgXor = Arg1 ^ Arg2;
  if (sizeof(T) == 4)
      TORC4.Insert(ArgXor, Arg1, Arg2);
  else if (sizeof(T) == 8)
      TORC8.Insert(ArgXor, Arg1, Arg2);
  uint64_t HammingDistance = Popcountll(ArgXor);  // [0,64]
  uint64_t AbsoluteDistance = (Arg1 == Arg2 ? 0 : Clzll(Arg1 - Arg2) + 1);
  ValueProfileMap.AddValue(PC * 128 + HammingDistance);
  ValueProfileMap.AddValue(PC * 128 + 64 + AbsoluteDistance);
}

The ValueProfileMap is used in TracePC::CollectFeatures for counting, which will be discussed in the fuzzer part.

Fuzzer

The core part of libFuzzer. The driver function calls F->loop at very last to start fuzzing:

void Fuzzer::Loop(Vector<SizedFile> &CorporaFiles) {
  auto FocusFunctionOrAuto = Options.FocusFunction;
  DFT.Init(Options.DataFlowTrace, &FocusFunctionOrAuto, CorporaFiles,
           MD.GetRand());
  TPC.SetFocusFunction(FocusFunctionOrAuto);
  ReadAndExecuteSeedCorpora(CorporaFiles);
  DFT.Clear();  // No need for DFT any more.
  TPC.SetPrintNewPCs(Options.PrintNewCovPcs);
  TPC.SetPrintNewFuncs(Options.PrintNewCovFuncs);
  system_clock::time_point LastCorpusReload = system_clock::now();

  TmpMaxMutationLen =
      Min(MaxMutationLen, Max(size_t(4), Corpus.MaxInputSize()));

  while (true) {
    auto Now = system_clock::now();
    if (!Options.StopFile.empty() &&
        !FileToVector(Options.StopFile, 1, false).empty())
      break;
    if (duration_cast<seconds>(Now - LastCorpusReload).count() >=
        Options.ReloadIntervalSec) {
      RereadOutputCorpus(MaxInputLen);
      LastCorpusReload = system_clock::now();
    }
    if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
      break;
    if (TimedOut())
      break;

    // Update TmpMaxMutationLen
    if (Options.LenControl) {
      if (TmpMaxMutationLen < MaxMutationLen &&
          TotalNumberOfRuns - LastCorpusUpdateRun >
              Options.LenControl * Log(TmpMaxMutationLen)) {
        TmpMaxMutationLen =
            Min(MaxMutationLen, TmpMaxMutationLen + Log(TmpMaxMutationLen));
        LastCorpusUpdateRun = TotalNumberOfRuns;
      }
    } else {
      TmpMaxMutationLen = MaxMutationLen;
    }

    // Perform several mutations and runs.
    MutateAndTestOne();

    PurgeAllocator();
  }

  PrintStats("DONE  ", "\n");
  MD.PrintRecommendedDictionary();
}

The function will first initialize DataFlowTrace and TracePC, then do mutation and execution.

DataFlowTrace

If you provide data flow trace file, the following steps will be invoked. To be short, necessary arguments are passed to DataFlowTrace, a class for reading and handling data-flow traces.

The Loop will start DataFlowTrace.Init() first. All the function names will be pushed to a vector and mapped to corresponding index. Then a focused index FocusFuncIdx is chosen by some statistics distribution:

bool DataFlowTrace::Init(const std::string &DirPath, std::string *FocusFunction, Vector<SizedFile> &CorporaFiles, Random &Rand) {
  if (DirPath.empty()) return false;
  ...
  // Read functions.txt
  std::ifstream IF(DirPlusFile(DirPath, kFunctionsTxt));
  size_t NumFunctions = 0;
  while (std::getline(IF, L, '\n')) {
    FunctionNames.push_back(L);
    NumFunctions++;
    if (*FocusFunction == L)
      FocusFuncIdx = NumFunctions - 1;
  }
  if (!NumFunctions)
    return false;
  ...

Finally, it will rank the weights of functions, and get a focus function:

  ...
  if (*FocusFunction == "auto") {
    // AUTOFOCUS works like this:
    // * reads the coverage data from the DFT files.
    // * assigns weights to functions based on coverage.
    // * chooses a random function according to the weights.
    ReadCoverage(DirPath);
    auto Weights = Coverage.FunctionWeights(NumFunctions);
    Vector<double> Intervals(NumFunctions + 1);
    std::iota(Intervals.begin(), Intervals.end(), 0);
    auto Distribution = std::piecewise_constant_distribution<double>(
        Intervals.begin(), Intervals.end(), Weights.begin());
    FocusFuncIdx = static_cast<size_t>(Distribution(Rand));
    *FocusFunction = FunctionNames[FocusFuncIdx];
    assert(FocusFuncIdx < NumFunctions);
    Printf("INFO: AUTOFOCUS: %zd %s\n", FocusFuncIdx,
            FunctionNames[FocusFuncIdx].c_str());
    for (size_t i = 0; i < NumFunctions; i++) {
      if (!Weights[i]) continue;
      Printf("  [%zd] W %g\tBB-tot %u\tBB-cov %u\tEntryFreq %u:\t%s\n", i,
              Weights[i], Coverage.GetNumberOfBlocks(i),
              Coverage.GetNumberOfCoveredBlocks(i), Coverage.GetCounter(i, 0),
              FunctionNames[i].c_str());
    }
  }
  ...

FunctionWeights weights based on uncovered blocks and execute frequency. Either higher uncovered blocks or lower execute frequency leads to a higher weight. However, uncovered functions merely have 0 weight.

By the way, the order of *FocusFunction = FunctionNames[FocusFuncIdx]; and assert(FocusFuncIdx < NumFunctions); is weird. Is it supposed to assert before the index operation?

Eventually, the focused function will be aded to Traces:

  ...
  size_t NumTraceFiles = 0;
  size_t NumTracesWithFocusFunction = 0;
  for (auto &SF : Files) {
    auto Name = Basename(SF.File);
    if (Name == kFunctionsTxt) continue;
    if (!CorporaHashes.count(Name)) continue;  // not in the corpus.
    NumTraceFiles++;
    // Printf("=== %s\n", Name.c_str());
    std::ifstream IF(SF.File);
    while (std::getline(IF, L, '\n')) {
      size_t FunctionNum = 0;
      std::string DFTString;
      if (ParseDFTLine(L, &FunctionNum, &DFTString) &&
          FunctionNum == FocusFuncIdx) {
        NumTracesWithFocusFunction++;

        if (FunctionNum >= NumFunctions)
          return ParseError("N is greater than the number of functions", L);
        Traces[Name] = DFTStringToVector(DFTString);
        // Print just a few small traces.
        if (NumTracesWithFocusFunction <= 3 && DFTString.size() <= 16)
          Printf("%s => |%s|\n", Name.c_str(), std::string(DFTString).c_str());
        break; // No need to parse the following lines.
      }
    }
  }
  ...

Creating and running Corpus

Subsequently, the program start reading seed file in ReadAndExecuteSeedCorpora(CorporaFiles), a function for initializing corpus. libFuzzer tries empty input first, then iterate all the provided corpus files. \n will be used as default seed when we don’t provide any seed:

void Fuzzer::ReadAndExecuteSeedCorpora(Vector<SizedFile> &CorporaFiles) {
...
  // Test the callback with empty input and never try it again.
  uint8_t dummy = 0;
  ExecuteCallback(&dummy, 0);
...
  if (CorporaFiles.empty()) {
    Printf("INFO: A corpus is not provided, starting from an empty corpus\n");
    Unit U({'\n'}); // Valid ASCII input.
    RunOne(U.data(), U.size());
  } else {
    Printf("INFO: seed corpus: files: %zd min: %zdb max: %zdb total: %zdb"
           " rss: %zdMb\n",
           CorporaFiles.size(), MinSize, MaxSize, TotalSize, GetPeakRSSMb());
    if (Options.ShuffleAtStartUp)
      std::shuffle(CorporaFiles.begin(), CorporaFiles.end(), MD.GetRand());

    if (Options.PreferSmall) {
      std::stable_sort(CorporaFiles.begin(), CorporaFiles.end());
      assert(CorporaFiles.front().Size <= CorporaFiles.back().Size);
    }

    // Load and execute inputs one by one.
    for (auto &SF : CorporaFiles) {
      auto U = FileToVector(SF.File, MaxInputLen, /*ExitOnError=*/false);
      assert(U.size() <= MaxInputLen);
      RunOne(U.data(), U.size());
      CheckExitOnSrcPosOrItem();
      TryDetectingAMemoryLeak(U.data(), U.size(),
                              /*DuringInitialCorpusExecution*/ true);
    }
  }
...
}

Mutation in Depth

After running user-provided corpus in ReadAndExecuteSeedCorpora(CorporaFiles) (if provided), the Loop will eventually go to an infinity loop until a crash occurs, MutateAndTestOne is invoked here for mutation and running:

void Fuzzer::MutateAndTestOne() {
  MD.StartMutationSequence();

  auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
  if (Options.DoCrossOver)
    MD.SetCrossOverWith(&Corpus.ChooseUnitToMutate(MD.GetRand()).U);
  const auto &U = II.U;
  memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
  assert(CurrentUnitData);
  size_t Size = U.size();
  assert(Size <= MaxInputLen && "Oversized Unit");
  memcpy(CurrentUnitData, U.data(), Size);

  assert(MaxMutationLen > 0);

  size_t CurrentMaxMutationLen =
      Min(MaxMutationLen, Max(U.size(), TmpMaxMutationLen));
  assert(CurrentMaxMutationLen > 0);

  for (int i = 0; i < Options.MutateDepth; i++) {
    if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
      break;
    MaybeExitGracefully();
    size_t NewSize = 0;
    if (II.HasFocusFunction && !II.DataFlowTraceForFocusFunction.empty() &&
        Size <= CurrentMaxMutationLen)
      NewSize = MD.MutateWithMask(CurrentUnitData, Size, Size,
                                  II.DataFlowTraceForFocusFunction);

    // If MutateWithMask either failed or wasn't called, call default Mutate.
    if (!NewSize)
      NewSize = MD.Mutate(CurrentUnitData, Size, CurrentMaxMutationLen);
    assert(NewSize > 0 && "Mutator returned empty unit");
    assert(NewSize <= CurrentMaxMutationLen && "Mutator return oversized unit");
    Size = NewSize;
    II.NumExecutedMutations++;

    bool FoundUniqFeatures = false;
    bool NewCov = RunOne(CurrentUnitData, Size, /*MayDeleteFile=*/true, &II,
                         &FoundUniqFeatures);
    TryDetectingAMemoryLeak(CurrentUnitData, Size,
                            /*DuringInitialCorpusExecution*/ false);
    if (NewCov) {
      ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
      break;  // We will mutate this input more in the next rounds.
    }
    if (Options.ReduceDepth && !FoundUniqFeatures)
      break;
  }
}

At the beginning, the function will choose two random input. One as a mutation target, another one as a cross-over target.

Fuzzer then mutates the input several times according to Options.MutateDepth. We have two mutating methods here, MD.mutate and MD.MutateWithMask.

MutateWithMaske

MD.MutateWithMask only mutates bytes marked in Mask (which has been defined as the focused function). After copying then to a temporary array T. The function uses the normal Md.mutate to convert data and eventually copy back to original array:

// Mask represents the set of Data bytes that are worth mutating.
size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
                                          size_t MaxSize,
                                          const Vector<uint8_t> &Mask) {
  size_t MaskedSize = std::min(Size, Mask.size());
  // * Copy the worthy bytes into a temporary array T
  // * Mutate T
  // * Copy T back.
  // This is totally unoptimized.
  auto &T = MutateWithMaskTemp;
  if (T.size() < Size)
    T.resize(Size);
  size_t OneBits = 0;
  for (size_t I = 0; I < MaskedSize; I++)
    if (Mask[I])
      T[OneBits++] = Data[I];

  if (!OneBits) return 0;
  assert(!T.empty());
  size_t NewSize = Mutate(T.data(), OneBits, OneBits);
  assert(NewSize <= OneBits);
  (void)NewSize;
  // Even if NewSize < OneBits we still use all OneBits bytes.
  for (size_t I = 0, J = 0; I < MaskedSize; I++)
    if (Mask[I])
      Data[I] = T[J++];
  return Size;
}

The general mutate

Md.mutate, on the other hand, uses one randomly selected mutation algorithm in each iteration until the cycle is over or current size exceeds max size. The implementation is in MutateImpl:

size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
                                      size_t MaxSize,
                                      Vector<Mutator> &Mutators) {
  assert(MaxSize > 0);
  // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
  // in which case they will return 0.
  // Try several times before returning un-mutated data.
  for (int Iter = 0; Iter < 100; Iter++) {
    auto M = Mutators[Rand(Mutators.size())];
    size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
    if (NewSize && NewSize <= MaxSize) {
      if (Options.OnlyASCII)
        ToASCII(Data, NewSize);
      CurrentMutatorSequence.push_back(M);
      return NewSize;
    }
  }
  *Data = ' ';
  return 1;   // Fallback, should not happen frequently.
}

RunOne

RunOne is an additional wrapper function mainly for processing coverages after executing the program:

bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                    InputInfo *II, bool *FoundUniqFeatures) {
  if (!Size)
    return false;

  ExecuteCallback(Data, Size);

  UniqFeatureSetTmp.clear();
  size_t FoundUniqFeaturesOfII = 0;
  size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
  TPC.CollectFeatures([&](size_t Feature) {
    if (Corpus.AddFeature(Feature, Size, Options.Shrink))
      UniqFeatureSetTmp.push_back(Feature);
    if (Options.ReduceInputs && II)
      if (std::binary_search(II->UniqFeatureSet.begin(),
                             II->UniqFeatureSet.end(), Feature))
        FoundUniqFeaturesOfII++;
  });
  if (FoundUniqFeatures)
    *FoundUniqFeatures = FoundUniqFeaturesOfII;
  // This function print current execution stauts to screen
  PrintPulseAndReportSlowInput(Data, Size);
  size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
  if (NumNewFeatures) {
    TPC.UpdateObservedPCs();
    auto NewII = Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures,
                                    MayDeleteFile, TPC.ObservedFocusFunction(),
                                    UniqFeatureSetTmp, DFT, II);
    WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1),
                          NewII->UniqFeatureSet);
    return true;
  }
  if (II && FoundUniqFeaturesOfII &&
      II->DataFlowTraceForFocusFunction.empty() &&
      FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
      II->U.size() > Size) {
    auto OldFeaturesFile = Sha1ToString(II->Sha1);
    Corpus.Replace(II, {Data, Data + Size});
    RenameFeatureSetFile(Options.FeaturesDir, OldFeaturesFile,
                         Sha1ToString(II->Sha1));
    return true;
  }
  return false;
}

ExecuteCallBack

ExecuteCallBack copies data and executes the LLVMInputOneTest. Meanwhile, libFuzzer begins to trace the stack, heap, and program counters:

void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
  TPC.RecordInitialStack();
  TotalNumberOfRuns++;
  assert(InFuzzingThread());
  // We copy the contents of Unit into a separate heap buffer
  // so that we reliably find buffer overflows in it.
  uint8_t *DataCopy = new uint8_t[Size];
  memcpy(DataCopy, Data, Size);
  if (EF->__msan_unpoison)
    EF->__msan_unpoison(DataCopy, Size);
  if (EF->__msan_unpoison_param)
    EF->__msan_unpoison_param(2);
  if (CurrentUnitData && CurrentUnitData != Data)
    memcpy(CurrentUnitData, Data, Size);
  CurrentUnitSize = Size;
  {
    ScopedEnableMsanInterceptorChecks S;
    AllocTracer.Start(Options.TraceMalloc);
    UnitStartTime = system_clock::now();
    TPC.ResetMaps();
    RunningUserCallback = true;

    // the real execution
    int Res = CB(DataCopy, Size);
    
    RunningUserCallback = false;
    UnitStopTime = system_clock::now();
    (void)Res;
    assert(Res == 0);
    HasMoreMallocsThanFrees = AllocTracer.Stop();
  }
  if (!LooseMemeq(DataCopy, Data, Size))
    CrashOnOverwrittenData();
  CurrentUnitSize = 0;
  delete[] DataCopy;
}

Counting new COVs

When execution ends, libFuzzer collects features (those comparisons we mentioned earlier) via a lambda:

...
  UniqFeatureSetTmp.clear();
  size_t FoundUniqFeaturesOfII = 0;
  size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
  TPC.CollectFeatures([&](size_t Feature) {
    // add feature to corpus set
    if (Corpus.AddFeature(Feature, Size, Options.Shrink))
      UniqFeatureSetTmp.push_back(Feature);
    // check whether the feature has already existed
    if (Options.ReduceInputs && II)
      if (std::binary_search(II->UniqFeatureSet.begin(),
                             II->UniqFeatureSet.end(), Feature))
        FoundUniqFeaturesOfII++;
  });
...

And the following is the internal for CollectFeatures. To conclude, it finds the features for every regions by execution paths. Then add it to the corpus. The feature is unique once adding successfully. When UseValueProfileMask flag is true, comparisons are counted as features as well. Moreover, the stack depth is converted by log operation for additional feature calculation:

template <class Callback>  // void Callback(size_t Feature)
ATTRIBUTE_NO_SANITIZE_ADDRESS
ATTRIBUTE_NOINLINE
void TracePC::CollectFeatures(Callback HandleFeature) const {
  auto Handle8bitCounter = [&](size_t FirstFeature,
                               size_t Idx, uint8_t Counter) {
    // if we do not use counters, it only converts address to features
    if (UseCounters)
      HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
    else
      HandleFeature(FirstFeature + Idx);
  };

  size_t FirstFeature = 0;

  // iterating all edge path, then put the result of each execution to the feature set
  for (size_t i = 0; i < NumModules; i++) {
    for (size_t r = 0; r < Modules[i].NumRegions; r++) {
      if (!Modules[i].Regions[r].Enabled) continue;
      // iterate each byte
      FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start,
                                             Modules[i].Regions[r].Stop,
                                             FirstFeature, Handle8bitCounter);
    }
  }

  FirstFeature +=
      8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(),
                             FirstFeature, Handle8bitCounter);

  // add comparsions to feature set
  if (UseValueProfileMask) {
    ValueProfileMap.ForEach([&](size_t Idx) {
      HandleFeature(FirstFeature + Idx);
    });
    FirstFeature += ValueProfileMap.SizeInBits();
  }

  // add stack depth to feature set
  // Step function, grows similar to 8 * Log_2(A).
  auto StackDepthStepFunction = [](uint32_t A) -> uint32_t {
    if (!A) return A;
    uint32_t Log2 = Log(A);
    if (Log2 < 3) return A;
    Log2 -= 3;
    return (Log2 + 1) * 8 + ((A >> Log2) & 7);
  };
  assert(StackDepthStepFunction(1024) == 64);
  assert(StackDepthStepFunction(1024 * 4) == 80);
  assert(StackDepthStepFunction(1024 * 1024) == 144);

  if (auto MaxStackOffset = GetMaxStackOffset())
    HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
}

Back to RunOne. If fuzzer finds any new features, libFuzzer will update TPC and add current input to existing corpus:

// in RunOne function...
  // if we have more features...
  size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
  if (NumNewFeatures) {
    TPC.UpdateObservedPCs();
    auto NewII = Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures,
                                    MayDeleteFile, TPC.ObservedFocusFunction(),
                                    UniqFeatureSetTmp, DFT, II);
    WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1),
                          NewII->UniqFeatureSet);
    return true;
  }

TPC.UpdateObervedPCs() outputs the details to the screen. It iterates and uses two global sets for collecting called functions and pointer counter. If it is a entry point that has never been used, PC is added to CoveredFuncs for printing later:

void TracePC::UpdateObservedPCs() {
  Vector<uintptr_t> CoveredFuncs;
  auto ObservePC = [&](const PCTableEntry *TE) {
    if (ObservedPCs.insert(TE).second && DoPrintNewPCs) {
      PrintPC("\tNEW_PC: %p %F %L", "\tNEW_PC: %p",
              GetNextInstructionPc(TE->PC));
      Printf("\n");
    }
  };

  auto Observe = [&](const PCTableEntry *TE) {
    if (PcIsFuncEntry(TE))
      if (++ObservedFuncs[TE->PC] == 1 && NumPrintNewFuncs)
        CoveredFuncs.push_back(TE->PC);
    ObservePC(TE);
  };

  if (NumPCsInPCTables) {
    if (NumInline8bitCounters == NumPCsInPCTables) {
      for (size_t i = 0; i < NumModules; i++) {
        auto &M = Modules[i];
        assert(M.Size() ==
               (size_t)(ModulePCTable[i].Stop - ModulePCTable[i].Start));
        for (size_t r = 0; r < M.NumRegions; r++) {
          auto &R = M.Regions[r];
          if (!R.Enabled) continue;
          for (uint8_t *P = R.Start; P < R.Stop; P++)
            if (*P)
              Observe(&ModulePCTable[i].Start[M.Idx(P)]);
        }
      }
    }
  }

  for (size_t i = 0, N = Min(CoveredFuncs.size(), NumPrintNewFuncs); i < N;
       i++) {
    Printf("\tNEW_FUNC[%zd/%zd]: ", i + 1, CoveredFuncs.size());
    PrintPC("%p %F %L", "%p", GetNextInstructionPc(CoveredFuncs[i]));
    Printf("\n");
  }
}

Even though there might be no feature update, libFuzzer prefers to save corpus with smaller size for optimizing. Then remove the larger corpus:

  if (II && FoundUniqFeaturesOfII &&
      II->DataFlowTraceForFocusFunction.empty() &&
      FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
      II->U.size() > Size) {
    auto OldFeaturesFile = Sha1ToString(II->Sha1);
    Corpus.Replace(II, {Data, Data + Size});
    RenameFeatureSetFile(Options.FeaturesDir, OldFeaturesFile,
                         Sha1ToString(II->Sha1));
    return true;
  }

The function returns false to notify the parent function when unique feature has not been found.

Heap Leaking

A hook will be added for counting malloc and free times. The program will first check malloc==frees. Then it will run again in lsan disabled mode. If they are inequivalent twice, actual LSAN will be executed:

void Fuzzer::TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size,
                                     bool DuringInitialCorpusExecution) {
  if (!HasMoreMallocsThanFrees)
    return; // mallocs==frees, a leak is unlikely.
  if (!Options.DetectLeaks)
    return;
  if (!DuringInitialCorpusExecution &&
      TotalNumberOfRuns >= Options.MaxNumberOfRuns)
    return;
  if (!&(EF->__lsan_enable) || !&(EF->__lsan_disable) ||
      !(EF->__lsan_do_recoverable_leak_check))
    return; // No lsan.
  // Run the target once again, but with lsan disabled so that if there is
  // a real leak we do not report it twice.
  EF->__lsan_disable();
  ExecuteCallback(Data, Size);
  EF->__lsan_enable();
  if (!HasMoreMallocsThanFrees)
    return; // a leak is unlikely.
  if (NumberOfLeakDetectionAttempts++ > 1000) {
    Options.DetectLeaks = false;
    Printf("INFO: libFuzzer disabled leak detection after every mutation.\n"
           "      Most likely the target function accumulates allocated\n"
           "      memory in a global state w/o actually leaking it.\n"
           "      You may try running this binary with -trace_malloc=[12]"
           "      to get a trace of mallocs and frees.\n"
           "      If LeakSanitizer is enabled in this process it will still\n"
           "      run on the process shutdown.\n");
    return;
  }
  // Now perform the actual lsan pass. This is expensive and we must ensure
  // we don't call it too often.
  if (EF->__lsan_do_recoverable_leak_check()) { // Leak is found, report it.
    if (DuringInitialCorpusExecution)
      Printf("\nINFO: a leak has been found in the initial corpus.\n\n");
    Printf("INFO: to ignore leaks on libFuzzer side use -detect_leaks=0.\n\n");
    CurrentUnitSize = Size;
    DumpCurrentUnit("leak-");
    PrintFinalStats();
    _Exit(Options.ErrorExitCode); // not exit() to disable lsan further on.
  }
}

Conclusion

Surprisingly, the architecture of a fuzzer is not (that much) as thoughtful as a static analyzer. But it’s indeed an efficient strategy because of excellent performance.

TODO…

Some analysis for:

  • FuzzerFork for fork mode.
  • libFuzzer merging corpus