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.
PrintFunctions()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"
SetBytesForLabel(dfsan_label L,char * Bytes)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
GetPrintableStringForLabel(dfsan_label L)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
PrintDataFlow(FILE * Out)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
main(int argc,char ** argv)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
__sanitizer_cov_trace_pc_guard_init(uint32_t * start,uint32_t * stop)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
__sanitizer_cov_pcs_init(const uintptr_t * pcs_beg,const uintptr_t * pcs_end)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
__sanitizer_cov_trace_pc_indir(uint64_t x)187 void __sanitizer_cov_trace_pc_indir(uint64_t x){} // unused.
188
__sanitizer_cov_trace_pc_guard(uint32_t * guard)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
__dfsw___sanitizer_cov_trace_switch(uint64_t Val,uint64_t * Cases,dfsan_label L1,dfsan_label UnusedL)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