1 /*===- DataFlow.cpp - a standalone DataFlow tracer -------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // An experimental data-flow tracer for fuzz targets. 10 // It is based on DFSan and SanitizerCoverage. 11 // https://clang.llvm.org/docs/DataFlowSanitizer.html 12 // https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow 13 // 14 // It executes the fuzz target on the given input while monitoring the 15 // data flow for every instrumented comparison instruction. 16 // 17 // The output shows which functions depend on which bytes of the input. 18 // 19 // Build: 20 // 1. Compile this file with -fsanitize=dataflow 21 // 2. Build the fuzz target with -g -fsanitize=dataflow 22 // -fsanitize-coverage=trace-pc-guard,pc-table,func,trace-cmp 23 // 3. Link those together with -fsanitize=dataflow 24 // 25 // -fsanitize-coverage=trace-cmp inserts callbacks around every comparison 26 // instruction, DFSan modifies the calls to pass the data flow labels. 27 // The callbacks update the data flow label for the current function. 28 // See e.g. __dfsw___sanitizer_cov_trace_cmp1 below. 29 // 30 // -fsanitize-coverage=trace-pc-guard,pc-table,func instruments function 31 // entries so that the comparison callback knows that current function. 32 // 33 // 34 // Run: 35 // # Collect data flow for INPUT_FILE, write to OUTPUT_FILE (default: stdout) 36 // ./a.out INPUT_FILE [OUTPUT_FILE] 37 // 38 // # Print all instrumented functions. llvm-symbolizer must be present in PATH 39 // ./a.out 40 // 41 // Example output: 42 // =============== 43 // F0 11111111111111 44 // F1 10000000000000 45 // =============== 46 // "FN xxxxxxxxxx": tells what bytes of the input does the function N depend on. 47 // The byte string is LEN+1 bytes. The last byte is set if the function 48 // depends on the input length. 49 //===----------------------------------------------------------------------===*/ 50 51 #include <assert.h> 52 #include <stdio.h> 53 #include <stdlib.h> 54 #include <stdint.h> 55 #include <string.h> 56 57 #include <execinfo.h> // backtrace_symbols_fd 58 59 #include <sanitizer/dfsan_interface.h> 60 61 extern "C" { 62 extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size); 63 __attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv); 64 } // extern "C" 65 66 static size_t InputLen; 67 static size_t NumFuncs; 68 static const uintptr_t *FuncsBeg; 69 static __thread size_t CurrentFunc; 70 static dfsan_label *FuncLabels; // Array of NumFuncs elements. 71 static char *PrintableStringForLabel; // InputLen + 2 bytes. 72 static bool LabelSeen[1 << 8 * sizeof(dfsan_label)]; 73 74 // Prints all instrumented functions. 75 static int PrintFunctions() { 76 // We don't have the symbolizer integrated with dfsan yet. 77 // So use backtrace_symbols_fd and pipe it through llvm-symbolizer. 78 // TODO(kcc): this is pretty ugly and may break in lots of ways. 79 // We'll need to make a proper in-process symbolizer work with DFSan. 80 FILE *Pipe = popen("sed 's/(+/ /g; s/).*//g' " 81 "| llvm-symbolizer " 82 "| grep 'dfs\\$' " 83 "| sed 's/dfs\\$//g'", "w"); 84 for (size_t I = 0; I < NumFuncs; I++) { 85 uintptr_t PC = FuncsBeg[I * 2]; 86 void *const Buf[1] = {(void*)PC}; 87 backtrace_symbols_fd(Buf, 1, fileno(Pipe)); 88 } 89 pclose(Pipe); 90 return 0; 91 } 92 93 extern "C" 94 void SetBytesForLabel(dfsan_label L, char *Bytes) { 95 if (LabelSeen[L]) 96 return; 97 LabelSeen[L] = true; 98 assert(L); 99 if (L <= InputLen + 1) { 100 Bytes[L - 1] = '1'; 101 } else { 102 auto *DLI = dfsan_get_label_info(L); 103 SetBytesForLabel(DLI->l1, Bytes); 104 SetBytesForLabel(DLI->l2, Bytes); 105 } 106 } 107 108 static char *GetPrintableStringForLabel(dfsan_label L) { 109 memset(PrintableStringForLabel, '0', InputLen + 1); 110 PrintableStringForLabel[InputLen + 1] = 0; 111 memset(LabelSeen, 0, sizeof(LabelSeen)); 112 SetBytesForLabel(L, PrintableStringForLabel); 113 return PrintableStringForLabel; 114 } 115 116 static void PrintDataFlow(FILE *Out) { 117 for (size_t I = 0; I < NumFuncs; I++) 118 if (FuncLabels[I]) 119 fprintf(Out, "F%zd %s\n", I, GetPrintableStringForLabel(FuncLabels[I])); 120 } 121 122 int main(int argc, char **argv) { 123 if (LLVMFuzzerInitialize) 124 LLVMFuzzerInitialize(&argc, &argv); 125 if (argc == 1) 126 return PrintFunctions(); 127 assert(argc == 4 || argc == 5); 128 size_t Beg = atoi(argv[1]); 129 size_t End = atoi(argv[2]); 130 assert(Beg < End); 131 132 const char *Input = argv[3]; 133 fprintf(stderr, "INFO: reading '%s'\n", Input); 134 FILE *In = fopen(Input, "r"); 135 assert(In); 136 fseek(In, 0, SEEK_END); 137 InputLen = ftell(In); 138 fseek(In, 0, SEEK_SET); 139 unsigned char *Buf = (unsigned char*)malloc(InputLen); 140 size_t NumBytesRead = fread(Buf, 1, InputLen, In); 141 assert(NumBytesRead == InputLen); 142 PrintableStringForLabel = (char*)malloc(InputLen + 2); 143 fclose(In); 144 145 fprintf(stderr, "INFO: running '%s'\n", Input); 146 for (size_t I = 1; I <= InputLen; I++) { 147 dfsan_label L = dfsan_create_label("", nullptr); 148 assert(L == I); 149 size_t Idx = I - 1; 150 if (Idx >= Beg && Idx < End) 151 dfsan_set_label(L, Buf + Idx, 1); 152 } 153 dfsan_label SizeL = dfsan_create_label("", nullptr); 154 assert(SizeL == InputLen + 1); 155 dfsan_set_label(SizeL, &InputLen, sizeof(InputLen)); 156 157 LLVMFuzzerTestOneInput(Buf, InputLen); 158 free(Buf); 159 160 bool OutIsStdout = argc == 4; 161 fprintf(stderr, "INFO: writing dataflow to %s\n", 162 OutIsStdout ? "<stdout>" : argv[4]); 163 FILE *Out = OutIsStdout ? stdout : fopen(argv[4], "w"); 164 PrintDataFlow(Out); 165 if (!OutIsStdout) fclose(Out); 166 } 167 168 extern "C" { 169 170 void __sanitizer_cov_trace_pc_guard_init(uint32_t *start, 171 uint32_t *stop) { 172 assert(NumFuncs == 0 && "This tool does not support DSOs"); 173 assert(start < stop && "The code is not instrumented for coverage"); 174 if (start == stop || *start) return; // Initialize only once. 175 for (uint32_t *x = start; x < stop; x++) 176 *x = ++NumFuncs; // The first index is 1. 177 FuncLabels = (dfsan_label*)calloc(NumFuncs, sizeof(dfsan_label)); 178 fprintf(stderr, "INFO: %zd instrumented function(s) observed\n", NumFuncs); 179 } 180 181 void __sanitizer_cov_pcs_init(const uintptr_t *pcs_beg, 182 const uintptr_t *pcs_end) { 183 assert(NumFuncs == (pcs_end - pcs_beg) / 2); 184 FuncsBeg = pcs_beg; 185 } 186 187 void __sanitizer_cov_trace_pc_indir(uint64_t x){} // unused. 188 189 void __sanitizer_cov_trace_pc_guard(uint32_t *guard){ 190 uint32_t FuncNum = *guard - 1; // Guards start from 1. 191 assert(FuncNum < NumFuncs); 192 CurrentFunc = FuncNum; 193 } 194 195 void __dfsw___sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases, 196 dfsan_label L1, dfsan_label UnusedL) { 197 assert(CurrentFunc < NumFuncs); 198 FuncLabels[CurrentFunc] = dfsan_union(FuncLabels[CurrentFunc], L1); 199 } 200 201 #define HOOK(Name, Type) \ 202 void Name(Type Arg1, Type Arg2, dfsan_label L1, dfsan_label L2) { \ 203 assert(CurrentFunc < NumFuncs); \ 204 FuncLabels[CurrentFunc] = \ 205 dfsan_union(FuncLabels[CurrentFunc], dfsan_union(L1, L2)); \ 206 } 207 208 HOOK(__dfsw___sanitizer_cov_trace_const_cmp1, uint8_t) 209 HOOK(__dfsw___sanitizer_cov_trace_const_cmp2, uint16_t) 210 HOOK(__dfsw___sanitizer_cov_trace_const_cmp4, uint32_t) 211 HOOK(__dfsw___sanitizer_cov_trace_const_cmp8, uint64_t) 212 HOOK(__dfsw___sanitizer_cov_trace_cmp1, uint8_t) 213 HOOK(__dfsw___sanitizer_cov_trace_cmp2, uint16_t) 214 HOOK(__dfsw___sanitizer_cov_trace_cmp4, uint32_t) 215 HOOK(__dfsw___sanitizer_cov_trace_cmp8, uint64_t) 216 217 } // extern "C" 218