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 // LEN:    5
44 // LABELS: 10
45 // L7 1 6
46 // L8 2 7
47 // L9 3 8
48 // L10 4 9
49 // F1 10
50 // F2 5
51 //  ===============
52 // "LEN:" indicates the number of bytes in the input.
53 // "LABELS:" indicates the number of DFSan labels created while running the input.
54 //   * The labels [1,LEN] correspond to the bytes of the input
55 //     (label 1 corresponds to byte 0, and so on)
56 //   * The label LEN+1 corresponds to the input size.
57 //   * The labels [LEN+2,LABELS] correspond to DFSan's union labels.
58 // "Li j k": describes the label 'i' as a union of labels 'j' and 'k'.
59 // "Ff l": tells that the function 'f' depends on the label 'l'.
60 //===----------------------------------------------------------------------===*/
61 
62 #include <assert.h>
63 #include <stdio.h>
64 #include <stdlib.h>
65 #include <stdint.h>
66 #include <string.h>
67 
68 #include <execinfo.h>  // backtrace_symbols_fd
69 
70 #include <sanitizer/dfsan_interface.h>
71 
72 extern "C" {
73 extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size);
74 __attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv);
75 } // extern "C"
76 
77 static size_t InputLen;
78 static size_t NumFuncs;
79 static const uintptr_t *FuncsBeg;
80 static __thread size_t CurrentFunc;
81 static dfsan_label *FuncLabels;  // Array of NumFuncs elements.
82 
83 // Prints all instrumented functions.
84 int PrintFunctions() {
85   // We don't have the symbolizer integrated with dfsan yet.
86   // So use backtrace_symbols_fd and pipe it through llvm-symbolizer.
87   // TODO(kcc): this is pretty ugly and may break in lots of ways.
88   //      We'll need to make a proper in-process symbolizer work with DFSan.
89   FILE *Pipe = popen("sed 's/(+/ /g; s/).*//g' "
90                      "| llvm-symbolizer "
91                      "| grep 'dfs\\$' "
92                      "| sed 's/dfs\\$//g'", "w");
93   for (size_t I = 0; I < NumFuncs; I++) {
94     uintptr_t PC = FuncsBeg[I * 2];
95     void *const Buf[1] = {(void*)PC};
96     backtrace_symbols_fd(Buf, 1, fileno(Pipe));
97   }
98   pclose(Pipe);
99   return 0;
100 }
101 
102 void PrintDataFlow(FILE *Out) {
103   fprintf(Out, "LEN:    %zd\n", InputLen);
104   fprintf(Out, "LABELS: %zd\n", dfsan_get_label_count());
105   for (dfsan_label L = InputLen + 2; L <= dfsan_get_label_count(); L++) {
106     auto *DLI = dfsan_get_label_info(L);
107     fprintf(Out, "L%d %d %d\n", L, DLI->l1, DLI->l2);
108   }
109   for (size_t I = 0; I < NumFuncs; I++)
110     if (FuncLabels[I])
111       fprintf(Out, "F%zd %d\n", I, FuncLabels[I]);
112 }
113 
114 int main(int argc, char **argv) {
115   if (LLVMFuzzerInitialize)
116     LLVMFuzzerInitialize(&argc, &argv);
117   if (argc == 1)
118     return PrintFunctions();
119   assert(argc == 2 || argc == 3);
120 
121   const char *Input = argv[1];
122   fprintf(stderr, "INFO: reading '%s'\n", Input);
123   FILE *In = fopen(Input, "r");
124   assert(In);
125   fseek(In, 0, SEEK_END);
126   InputLen = ftell(In);
127   fseek(In, 0, SEEK_SET);
128   unsigned char *Buf = (unsigned char*)malloc(InputLen);
129   size_t NumBytesRead = fread(Buf, 1, InputLen, In);
130   assert(NumBytesRead == InputLen);
131   fclose(In);
132 
133   fprintf(stderr, "INFO: running '%s'\n", Input);
134   for (size_t I = 1; I <= InputLen; I++) {
135     dfsan_label L = dfsan_create_label("", nullptr);
136     assert(L == I);
137     dfsan_set_label(L, Buf + I - 1, 1);
138   }
139   dfsan_label SizeL = dfsan_create_label("", nullptr);
140   assert(SizeL == InputLen + 1);
141   dfsan_set_label(SizeL, &InputLen, sizeof(InputLen));
142 
143   LLVMFuzzerTestOneInput(Buf, InputLen);
144   free(Buf);
145 
146   bool OutIsStdout = argc == 2;
147   fprintf(stderr, "INFO: writing dataflow to %s\n",
148           OutIsStdout ? "<stdout>" : argv[2]);
149   FILE *Out = OutIsStdout ? stdout : fopen(argv[2], "w");
150   PrintDataFlow(Out);
151   if (!OutIsStdout) fclose(Out);
152 }
153 
154 extern "C" {
155 
156 void __sanitizer_cov_trace_pc_guard_init(uint32_t *start,
157                                          uint32_t *stop) {
158   assert(NumFuncs == 0 && "This tool does not support DSOs");
159   assert(start < stop && "The code is not instrumented for coverage");
160   if (start == stop || *start) return;  // Initialize only once.
161   for (uint32_t *x = start; x < stop; x++)
162     *x = ++NumFuncs;  // The first index is 1.
163   FuncLabels = (dfsan_label*)calloc(NumFuncs, sizeof(dfsan_label));
164   fprintf(stderr, "INFO: %zd instrumented function(s) observed\n", NumFuncs);
165 }
166 
167 void __sanitizer_cov_pcs_init(const uintptr_t *pcs_beg,
168                               const uintptr_t *pcs_end) {
169   assert(NumFuncs == (pcs_end - pcs_beg) / 2);
170   FuncsBeg = pcs_beg;
171 }
172 
173 void __sanitizer_cov_trace_pc_indir(uint64_t x){}  // unused.
174 
175 void __sanitizer_cov_trace_pc_guard(uint32_t *guard){
176   uint32_t FuncNum = *guard - 1;  // Guards start from 1.
177   assert(FuncNum < NumFuncs);
178   CurrentFunc = FuncNum;
179 }
180 
181 void __dfsw___sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases,
182                                          dfsan_label L1, dfsan_label UnusedL) {
183   assert(CurrentFunc < NumFuncs);
184   FuncLabels[CurrentFunc] = dfsan_union(FuncLabels[CurrentFunc], L1);
185 }
186 
187 #define HOOK(Name, Type)                                                       \
188   void Name(Type Arg1, Type Arg2, dfsan_label L1, dfsan_label L2) {            \
189     assert(CurrentFunc < NumFuncs);                                            \
190     FuncLabels[CurrentFunc] =                                                  \
191         dfsan_union(FuncLabels[CurrentFunc], dfsan_union(L1, L2));             \
192   }
193 
194 HOOK(__dfsw___sanitizer_cov_trace_const_cmp1, uint8_t)
195 HOOK(__dfsw___sanitizer_cov_trace_const_cmp2, uint16_t)
196 HOOK(__dfsw___sanitizer_cov_trace_const_cmp4, uint32_t)
197 HOOK(__dfsw___sanitizer_cov_trace_const_cmp8, uint64_t)
198 HOOK(__dfsw___sanitizer_cov_trace_cmp1, uint8_t)
199 HOOK(__dfsw___sanitizer_cov_trace_cmp2, uint16_t)
200 HOOK(__dfsw___sanitizer_cov_trace_cmp4, uint32_t)
201 HOOK(__dfsw___sanitizer_cov_trace_cmp8, uint64_t)
202 
203 } // extern "C"
204