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
69 extern "C" {
70 extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size);
71 __attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv);
72 } // extern "C"
73
74 CallbackData __dft;
75 static size_t InputLen;
76 static size_t NumIterations;
77 static dfsan_label **FuncLabelsPerIter; // NumIterations x NumFuncs;
78
BlockIsEntry(size_t BlockIdx)79 static inline bool BlockIsEntry(size_t BlockIdx) {
80 return __dft.PCsBeg[BlockIdx * 2 + 1] & PCFLAG_FUNC_ENTRY;
81 }
82
83 const int kNumLabels = 8;
84
85 // Prints all instrumented functions.
PrintFunctions()86 static 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
PrintBinary(FILE * Out,dfsan_label L,size_t Len)107 static 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
PrintDataFlow(FILE * Out)116 static 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
PrintCoverage(FILE * Out)135 static 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
main(int argc,char ** argv)156 int 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