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
69extern "C" {
70extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size);
71__attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv);
72} // extern "C"
73
74CallbackData __dft;
75static size_t InputLen;
76static size_t NumIterations;
77static dfsan_label **FuncLabelsPerIter;  // NumIterations x NumFuncs;
78
79static inline bool BlockIsEntry(size_t BlockIdx) {
80  return __dft.PCsBeg[BlockIdx * 2 + 1] & PCFLAG_FUNC_ENTRY;
81}
82
83const int kNumLabels = 8;
84
85// Prints all instrumented functions.
86static 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
107static 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
116static 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
135static 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
156int 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}
206