compiler-rt/lib/fuzzer/dataflow/DataFlow.cpp

   1 /*===- DataFlow.cpp - a standalone DataFlow tracer                  -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // An experimental data-flow tracer for fuzz targets.
   9 // It is based on DFSan and SanitizerCoverage.
  10 // https://clang.llvm.org/docs/DataFlowSanitizer.html
  11 // https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow
  12 //
  13 // It executes the fuzz target on the given input while monitoring the
  14 // data flow for every instrumented comparison instruction.
  15 //
  16 // The output shows which functions depend on which bytes of the input,
  17 // and also provides basic-block coverage for every input.
  18 //
  19 // Build:
  20 //   1. Compile this file (DataFlow.cpp) with -fsanitize=dataflow and -O2.
  21 //   2. Compile DataFlowCallbacks.cpp with -O2 -fPIC.
  22 //   3. Build the fuzz target with -g -fsanitize=dataflow
  23 //       -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp
  24 //   4. Link those together with -fsanitize=dataflow
  25 //
  26 //  -fsanitize-coverage=trace-cmp inserts callbacks around every comparison
  27 //  instruction, DFSan modifies the calls to pass the data flow labels.
  28 //  The callbacks update the data flow label for the current function.
  29 //  See e.g. __dfsw___sanitizer_cov_trace_cmp1 below.
  30 //
  31 //  -fsanitize-coverage=trace-pc-guard,pc-table,bb instruments function
  32 //  entries so that the comparison callback knows that current function.
  33 //  -fsanitize-coverage=...,bb also allows to collect basic block coverage.
  34 //
  35 //
  36 // Run:
  37 //   # Collect data flow and coverage for INPUT_FILE
  38 //   # write to OUTPUT_FILE (default: stdout)
  39 //   export DFSAN_OPTIONS=warn_unimplemented=0
  40 //   ./a.out INPUT_FILE [OUTPUT_FILE]
  41 //
  42 //   # Print all instrumented functions. llvm-symbolizer must be present in PATH
  43 //   ./a.out
  44 //
  45 // Example output:
  46 // ===============
  47 //  F0 11111111111111
  48 //  F1 10000000000000
  49 //  C0 1 2 3 4 5
  50 //  C1 8
  51 //  ===============
  52 // "FN xxxxxxxxxx": tells what bytes of the input does the function N depend on.
  53 // "CN X Y Z T": tells that a function N has basic blocks X, Y, and Z covered
  54 //    in addition to the function's entry block, out of T total instrumented
  55 //    blocks.
  56 //
  57 //===----------------------------------------------------------------------===*/
  58
  59 #include <assert.h>
  60 #include <stdio.h>
  61 #include <stdlib.h>
  62 #include <stdint.h>
  63 #include <string.h>
  64
  65 #include <execinfo.h>  // backtrace_symbols_fd
  66
  67 #include "DataFlow.h"
  68
  69 extern "C" {
  70 extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size);
  71 __attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv);
  72 } // extern "C"
  73
  74 CallbackData __dft;
  75 static size_t InputLen;
  76 static size_t NumIterations;
  77 static dfsan_label **FuncLabelsPerIter;  // NumIterations x NumFuncs;
  78
  79 static inline bool BlockIsEntry(size_t BlockIdx) {
  80   return __dft.PCsBeg[BlockIdx * 2 + 1] & PCFLAG_FUNC_ENTRY;
  81 }
  82
  83 const int kNumLabels = 8;
  84
  85 // Prints all instrumented functions.
  86 static int PrintFunctions() {
  87   // We don't have the symbolizer integrated with dfsan yet.
  88   // So use backtrace_symbols_fd and pipe it through llvm-symbolizer.
  89   // TODO(kcc): this is pretty ugly and may break in lots of ways.
  90   //      We'll need to make a proper in-process symbolizer work with DFSan.
  91   FILE *Pipe = popen("sed 's/(+/ /g; s/).*//g' "
  92                      "| llvm-symbolizer "
  93                      "| grep '\\.dfsan' "
  94                      "| sed 's/\\.dfsan//g' "
  95                      "| c++filt",
  96                      "w");
  97   for (size_t I = 0; I < __dft.NumGuards; I++) {
  98     uintptr_t PC = __dft.PCsBeg[I * 2];
  99     if (!BlockIsEntry(I)) continue;
 100     void *const Buf[1] = {(void*)PC};
 101     backtrace_symbols_fd(Buf, 1, fileno(Pipe));
 102   }
 103   pclose(Pipe);
 104   return 0;
 105 }
 106
 107 static void PrintBinary(FILE *Out, dfsan_label L, size_t Len) {
 108   char buf[kNumLabels + 1];
 109   assert(Len <= kNumLabels);
 110   for (int i = 0; i < kNumLabels; i++)
 111     buf[i] = (L & (1 << i)) ? '1' : '0';
 112   buf[Len] = 0;
 113   fprintf(Out, "%s", buf);
 114 }
 115
 116 static void PrintDataFlow(FILE *Out) {
 117   for (size_t Func = 0; Func < __dft.NumFuncs; Func++) {
 118     bool HasAny = false;
 119     for (size_t Iter = 0; Iter < NumIterations; Iter++)
 120       if (FuncLabelsPerIter[Iter][Func])
 121         HasAny = true;
 122     if (!HasAny)
 123       continue;
 124     fprintf(Out, "F%zd ", Func);
 125     size_t LenOfLastIteration = kNumLabels;
 126     if (auto Tail = InputLen % kNumLabels)
 127         LenOfLastIteration = Tail;
 128     for (size_t Iter = 0; Iter < NumIterations; Iter++)
 129       PrintBinary(Out, FuncLabelsPerIter[Iter][Func],
 130                   Iter == NumIterations - 1 ? LenOfLastIteration : kNumLabels);
 131     fprintf(Out, "\n");
 132   }
 133 }
 134
 135 static void PrintCoverage(FILE *Out) {
 136   ssize_t CurrentFuncGuard = -1;
 137   ssize_t CurrentFuncNum = -1;
 138   ssize_t NumBlocksInCurrentFunc = -1;
 139   for (size_t FuncBeg = 0; FuncBeg < __dft.NumGuards;) {
 140     CurrentFuncNum++;
 141     assert(BlockIsEntry(FuncBeg));
 142     size_t FuncEnd = FuncBeg + 1;
 143     for (; FuncEnd < __dft.NumGuards && !BlockIsEntry(FuncEnd); FuncEnd++)
 144       ;
 145     if (__dft.BBExecuted[FuncBeg]) {
 146       fprintf(Out, "C%zd", CurrentFuncNum);
 147       for (size_t I = FuncBeg + 1; I < FuncEnd; I++)
 148         if (__dft.BBExecuted[I])
 149           fprintf(Out, " %zd", I - FuncBeg);
 150       fprintf(Out, " %zd\n", FuncEnd - FuncBeg);
 151     }
 152     FuncBeg = FuncEnd;
 153   }
 154 }
 155
 156 int main(int argc, char **argv) {
 157   if (LLVMFuzzerInitialize)
 158     LLVMFuzzerInitialize(&argc, &argv);
 159   if (argc == 1)
 160     return PrintFunctions();
 161   assert(argc == 2 || argc == 3);
 162
 163   const char *Input = argv[1];
 164   fprintf(stderr, "INFO: reading '%s'\n", Input);
 165   FILE *In = fopen(Input, "r");
 166   assert(In);
 167   fseek(In, 0, SEEK_END);
 168   InputLen = ftell(In);
 169   fseek(In, 0, SEEK_SET);
 170   unsigned char *Buf = (unsigned char*)malloc(InputLen);
 171   size_t NumBytesRead = fread(Buf, 1, InputLen, In);
 172   assert(NumBytesRead == InputLen);
 173   fclose(In);
 174
 175   NumIterations = (NumBytesRead + kNumLabels - 1) / kNumLabels;
 176   FuncLabelsPerIter =
 177       (dfsan_label **)calloc(NumIterations, sizeof(dfsan_label *));
 178   for (size_t Iter = 0; Iter < NumIterations; Iter++)
 179     FuncLabelsPerIter[Iter] =
 180         (dfsan_label *)calloc(__dft.NumFuncs, sizeof(dfsan_label));
 181
 182   for (size_t Iter = 0; Iter < NumIterations; Iter++) {
 183     fprintf(stderr, "INFO: running '%s' %zd/%zd\n", Input, Iter, NumIterations);
 184     dfsan_flush();
 185     dfsan_set_label(0, Buf, InputLen);
 186     __dft.FuncLabels = FuncLabelsPerIter[Iter];
 187
 188     size_t BaseIdx = Iter * kNumLabels;
 189     size_t LastIdx = BaseIdx + kNumLabels < NumBytesRead ? BaseIdx + kNumLabels
 190                                                          : NumBytesRead;
 191     assert(BaseIdx < LastIdx);
 192     for (size_t Idx = BaseIdx; Idx < LastIdx; Idx++)
 193       dfsan_set_label(1 << (Idx - BaseIdx), Buf + Idx, 1);
 194     LLVMFuzzerTestOneInput(Buf, InputLen);
 195   }
 196   free(Buf);
 197
 198   bool OutIsStdout = argc == 2;
 199   fprintf(stderr, "INFO: writing dataflow to %s\n",
 200           OutIsStdout ? "<stdout>" : argv[2]);
 201   FILE *Out = OutIsStdout ? stdout : fopen(argv[2], "w");
 202   PrintDataFlow(Out);
 203   PrintCoverage(Out);
 204   if (!OutIsStdout) fclose(Out);
 205 }