From d4c94dacf666d5ad26d334b2a48d0d63ee31b972 Mon Sep 17 00:00:00 2001 From: Ivan Lozano Date: Mon, 16 Nov 2020 10:56:18 -0500 Subject: Import libfuzzer-sys Rust Crate Bug: 147140513 Test: N/A Change-Id: I3be474604ebb26642b8f7f536ee3e77bd8ce2469 --- libfuzzer/dataflow/DataFlow.cpp | 205 +++++++++++++++++++++++++++++++ libfuzzer/dataflow/DataFlow.h | 32 +++++ libfuzzer/dataflow/DataFlowCallbacks.cpp | 86 +++++++++++++ 3 files changed, 323 insertions(+) create mode 100644 libfuzzer/dataflow/DataFlow.cpp create mode 100644 libfuzzer/dataflow/DataFlow.h create mode 100644 libfuzzer/dataflow/DataFlowCallbacks.cpp (limited to 'libfuzzer/dataflow') diff --git a/libfuzzer/dataflow/DataFlow.cpp b/libfuzzer/dataflow/DataFlow.cpp new file mode 100644 index 0000000..8bf4e25 --- /dev/null +++ b/libfuzzer/dataflow/DataFlow.cpp @@ -0,0 +1,205 @@ +/*===- DataFlow.cpp - a standalone DataFlow tracer -------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// An experimental data-flow tracer for fuzz targets. +// It is based on DFSan and SanitizerCoverage. +// https://clang.llvm.org/docs/DataFlowSanitizer.html +// https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow +// +// It executes the fuzz target on the given input while monitoring the +// data flow for every instrumented comparison instruction. +// +// The output shows which functions depend on which bytes of the input, +// and also provides basic-block coverage for every input. +// +// Build: +// 1. Compile this file (DataFlow.cpp) with -fsanitize=dataflow and -O2. +// 2. Compile DataFlowCallbacks.cpp with -O2 -fPIC. +// 3. Build the fuzz target with -g -fsanitize=dataflow +// -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp +// 4. Link those together with -fsanitize=dataflow +// +// -fsanitize-coverage=trace-cmp inserts callbacks around every comparison +// instruction, DFSan modifies the calls to pass the data flow labels. +// The callbacks update the data flow label for the current function. +// See e.g. __dfsw___sanitizer_cov_trace_cmp1 below. +// +// -fsanitize-coverage=trace-pc-guard,pc-table,bb instruments function +// entries so that the comparison callback knows that current function. +// -fsanitize-coverage=...,bb also allows to collect basic block coverage. +// +// +// Run: +// # Collect data flow and coverage for INPUT_FILE +// # write to OUTPUT_FILE (default: stdout) +// export DFSAN_OPTIONS=fast16labels=1:warn_unimplemented=0 +// ./a.out INPUT_FILE [OUTPUT_FILE] +// +// # Print all instrumented functions. llvm-symbolizer must be present in PATH +// ./a.out +// +// Example output: +// =============== +// F0 11111111111111 +// F1 10000000000000 +// C0 1 2 3 4 5 +// C1 8 +// =============== +// "FN xxxxxxxxxx": tells what bytes of the input does the function N depend on. +// "CN X Y Z T": tells that a function N has basic blocks X, Y, and Z covered +// in addition to the function's entry block, out of T total instrumented +// blocks. +// +//===----------------------------------------------------------------------===*/ + +#include +#include +#include +#include +#include + +#include // backtrace_symbols_fd + +#include "DataFlow.h" + +extern "C" { +extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size); +__attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv); +} // extern "C" + +CallbackData __dft; +static size_t InputLen; +static size_t NumIterations; +static dfsan_label **FuncLabelsPerIter; // NumIterations x NumFuncs; + +static inline bool BlockIsEntry(size_t BlockIdx) { + return __dft.PCsBeg[BlockIdx * 2 + 1] & PCFLAG_FUNC_ENTRY; +} + +const int kNumLabels = 16; + +// Prints all instrumented functions. +static int PrintFunctions() { + // We don't have the symbolizer integrated with dfsan yet. + // So use backtrace_symbols_fd and pipe it through llvm-symbolizer. + // TODO(kcc): this is pretty ugly and may break in lots of ways. + // We'll need to make a proper in-process symbolizer work with DFSan. + FILE *Pipe = popen("sed 's/(+/ /g; s/).*//g' " + "| llvm-symbolizer " + "| grep 'dfs\\$' " + "| sed 's/dfs\\$//g' " + "| c++filt", + "w"); + for (size_t I = 0; I < __dft.NumGuards; I++) { + uintptr_t PC = __dft.PCsBeg[I * 2]; + if (!BlockIsEntry(I)) continue; + void *const Buf[1] = {(void*)PC}; + backtrace_symbols_fd(Buf, 1, fileno(Pipe)); + } + pclose(Pipe); + return 0; +} + +static void PrintBinary(FILE *Out, dfsan_label L, size_t Len) { + char buf[kNumLabels + 1]; + assert(Len <= kNumLabels); + for (int i = 0; i < kNumLabels; i++) + buf[i] = (L & (1 << i)) ? '1' : '0'; + buf[Len] = 0; + fprintf(Out, "%s", buf); +} + +static void PrintDataFlow(FILE *Out) { + for (size_t Func = 0; Func < __dft.NumFuncs; Func++) { + bool HasAny = false; + for (size_t Iter = 0; Iter < NumIterations; Iter++) + if (FuncLabelsPerIter[Iter][Func]) + HasAny = true; + if (!HasAny) + continue; + fprintf(Out, "F%zd ", Func); + size_t LenOfLastIteration = kNumLabels; + if (auto Tail = InputLen % kNumLabels) + LenOfLastIteration = Tail; + for (size_t Iter = 0; Iter < NumIterations; Iter++) + PrintBinary(Out, FuncLabelsPerIter[Iter][Func], + Iter == NumIterations - 1 ? LenOfLastIteration : kNumLabels); + fprintf(Out, "\n"); + } +} + +static void PrintCoverage(FILE *Out) { + ssize_t CurrentFuncGuard = -1; + ssize_t CurrentFuncNum = -1; + ssize_t NumBlocksInCurrentFunc = -1; + for (size_t FuncBeg = 0; FuncBeg < __dft.NumGuards;) { + CurrentFuncNum++; + assert(BlockIsEntry(FuncBeg)); + size_t FuncEnd = FuncBeg + 1; + for (; FuncEnd < __dft.NumGuards && !BlockIsEntry(FuncEnd); FuncEnd++) + ; + if (__dft.BBExecuted[FuncBeg]) { + fprintf(Out, "C%zd", CurrentFuncNum); + for (size_t I = FuncBeg + 1; I < FuncEnd; I++) + if (__dft.BBExecuted[I]) + fprintf(Out, " %zd", I - FuncBeg); + fprintf(Out, " %zd\n", FuncEnd - FuncBeg); + } + FuncBeg = FuncEnd; + } +} + +int main(int argc, char **argv) { + if (LLVMFuzzerInitialize) + LLVMFuzzerInitialize(&argc, &argv); + if (argc == 1) + return PrintFunctions(); + assert(argc == 2 || argc == 3); + + const char *Input = argv[1]; + fprintf(stderr, "INFO: reading '%s'\n", Input); + FILE *In = fopen(Input, "r"); + assert(In); + fseek(In, 0, SEEK_END); + InputLen = ftell(In); + fseek(In, 0, SEEK_SET); + unsigned char *Buf = (unsigned char*)malloc(InputLen); + size_t NumBytesRead = fread(Buf, 1, InputLen, In); + assert(NumBytesRead == InputLen); + fclose(In); + + NumIterations = (NumBytesRead + kNumLabels - 1) / kNumLabels; + FuncLabelsPerIter = + (dfsan_label **)calloc(NumIterations, sizeof(dfsan_label *)); + for (size_t Iter = 0; Iter < NumIterations; Iter++) + FuncLabelsPerIter[Iter] = + (dfsan_label *)calloc(__dft.NumFuncs, sizeof(dfsan_label)); + + for (size_t Iter = 0; Iter < NumIterations; Iter++) { + fprintf(stderr, "INFO: running '%s' %zd/%zd\n", Input, Iter, NumIterations); + dfsan_flush(); + dfsan_set_label(0, Buf, InputLen); + __dft.FuncLabels = FuncLabelsPerIter[Iter]; + + size_t BaseIdx = Iter * kNumLabels; + size_t LastIdx = BaseIdx + kNumLabels < NumBytesRead ? BaseIdx + kNumLabels + : NumBytesRead; + assert(BaseIdx < LastIdx); + for (size_t Idx = BaseIdx; Idx < LastIdx; Idx++) + dfsan_set_label(1 << (Idx - BaseIdx), Buf + Idx, 1); + LLVMFuzzerTestOneInput(Buf, InputLen); + } + free(Buf); + + bool OutIsStdout = argc == 2; + fprintf(stderr, "INFO: writing dataflow to %s\n", + OutIsStdout ? "" : argv[2]); + FILE *Out = OutIsStdout ? stdout : fopen(argv[2], "w"); + PrintDataFlow(Out); + PrintCoverage(Out); + if (!OutIsStdout) fclose(Out); +} diff --git a/libfuzzer/dataflow/DataFlow.h b/libfuzzer/dataflow/DataFlow.h new file mode 100644 index 0000000..35849fd --- /dev/null +++ b/libfuzzer/dataflow/DataFlow.h @@ -0,0 +1,32 @@ +/*===- DataFlow.h - a standalone DataFlow trace -------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Internal header file to connect DataFlow.cpp and DataFlowCallbacks.cpp. +//===----------------------------------------------------------------------===*/ + +#ifndef __LIBFUZZER_DATAFLOW_H +#define __LIBFUZZER_DATAFLOW_H + +#include +#include +#include + +// This data is shared between DataFlowCallbacks.cpp and DataFlow.cpp. +struct CallbackData { + size_t NumFuncs, NumGuards; + const uintptr_t *PCsBeg, *PCsEnd; + dfsan_label *FuncLabels; // Array of NumFuncs elements. + bool *BBExecuted; // Array of NumGuards elements. +}; + +extern CallbackData __dft; + +enum { + PCFLAG_FUNC_ENTRY = 1, +}; + +#endif // __LIBFUZZER_DATAFLOW_H diff --git a/libfuzzer/dataflow/DataFlowCallbacks.cpp b/libfuzzer/dataflow/DataFlowCallbacks.cpp new file mode 100644 index 0000000..170b4d8 --- /dev/null +++ b/libfuzzer/dataflow/DataFlowCallbacks.cpp @@ -0,0 +1,86 @@ +/*===- DataFlowCallbacks.cpp - a standalone DataFlow trace -------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Instrumentation callbacks for DataFlow.cpp. +// These functions should not be instrumented by DFSan, so we +// keep them in a separate file and compile it w/o DFSan. +//===----------------------------------------------------------------------===*/ +#include "DataFlow.h" + +#include +#include +#include + +static __thread size_t CurrentFunc; +static uint32_t *GuardsBeg, *GuardsEnd; +static inline bool BlockIsEntry(size_t BlockIdx) { + return __dft.PCsBeg[BlockIdx * 2 + 1] & PCFLAG_FUNC_ENTRY; +} + +extern "C" { + +void __sanitizer_cov_trace_pc_guard_init(uint32_t *start, + uint32_t *stop) { + assert(__dft.NumFuncs == 0 && "This tool does not support DSOs"); + assert(start < stop && "The code is not instrumented for coverage"); + if (start == stop || *start) return; // Initialize only once. + GuardsBeg = start; + GuardsEnd = stop; +} + +void __sanitizer_cov_pcs_init(const uintptr_t *pcs_beg, + const uintptr_t *pcs_end) { + if (__dft.NumGuards) return; // Initialize only once. + __dft.NumGuards = GuardsEnd - GuardsBeg; + __dft.PCsBeg = pcs_beg; + __dft.PCsEnd = pcs_end; + assert(__dft.NumGuards == (__dft.PCsEnd - __dft.PCsBeg) / 2); + for (size_t i = 0; i < __dft.NumGuards; i++) { + if (BlockIsEntry(i)) { + __dft.NumFuncs++; + GuardsBeg[i] = __dft.NumFuncs; + } + } + __dft.BBExecuted = (bool*)calloc(__dft.NumGuards, sizeof(bool)); + fprintf(stderr, "INFO: %zd instrumented function(s) observed " + "and %zd basic blocks\n", __dft.NumFuncs, __dft.NumGuards); +} + +void __sanitizer_cov_trace_pc_indir(uint64_t x){} // unused. + +void __sanitizer_cov_trace_pc_guard(uint32_t *guard) { + size_t GuardIdx = guard - GuardsBeg; + // assert(GuardIdx < __dft.NumGuards); + __dft.BBExecuted[GuardIdx] = true; + if (!*guard) return; // not a function entry. + uint32_t FuncNum = *guard - 1; // Guards start from 1. + // assert(FuncNum < __dft.NumFuncs); + CurrentFunc = FuncNum; +} + +void __dfsw___sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases, + dfsan_label L1, dfsan_label UnusedL) { + assert(CurrentFunc < __dft.NumFuncs); + __dft.FuncLabels[CurrentFunc] |= L1; +} + +#define HOOK(Name, Type) \ + void Name(Type Arg1, Type Arg2, dfsan_label L1, dfsan_label L2) { \ + __dft.FuncLabels[CurrentFunc] |= L1 | L2; \ + } + //assert(CurrentFunc < __dft.NumFuncs); + +HOOK(__dfsw___sanitizer_cov_trace_const_cmp1, uint8_t) +HOOK(__dfsw___sanitizer_cov_trace_const_cmp2, uint16_t) +HOOK(__dfsw___sanitizer_cov_trace_const_cmp4, uint32_t) +HOOK(__dfsw___sanitizer_cov_trace_const_cmp8, uint64_t) +HOOK(__dfsw___sanitizer_cov_trace_cmp1, uint8_t) +HOOK(__dfsw___sanitizer_cov_trace_cmp2, uint16_t) +HOOK(__dfsw___sanitizer_cov_trace_cmp4, uint32_t) +HOOK(__dfsw___sanitizer_cov_trace_cmp8, uint64_t) + +} // extern "C" -- cgit v1.2.3