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