206 lines · 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-exception6//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.html11// https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow12//13// It executes the fuzz target on the given input while monitoring the14// 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=dataflow23// -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp24// 4. Link those together with -fsanitize=dataflow25//26// -fsanitize-coverage=trace-cmp inserts callbacks around every comparison27// 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 function32// 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_FILE38// # write to OUTPUT_FILE (default: stdout)39// export DFSAN_OPTIONS=warn_unimplemented=040// ./a.out INPUT_FILE [OUTPUT_FILE]41//42// # Print all instrumented functions. llvm-symbolizer must be present in PATH43// ./a.out44//45// Example output:46// ===============47// F0 1111111111111148// F1 1000000000000049// C0 1 2 3 4 550// C1 851// ===============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 covered54// in addition to the function's entry block, out of T total instrumented55// 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_fd66 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 + kNumLabels190 : 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