1 //===- FuzzerTraceState.cpp - Trace-based fuzzer mutator ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
9 // This file implements a mutation algorithm based on instruction traces and
10 // on taint analysis feedback from DFSan.
12 // Instruction traces are special hooks inserted by the compiler around
13 // interesting instructions. Currently supported traces:
14 // * __sanitizer_cov_trace_cmp -- inserted before every ICMP instruction,
15 // receives the type, size and arguments of ICMP.
17 // Every time a traced event is intercepted we analyse the data involved
18 // in the event and suggest a mutation for future executions.
19 // For example if 4 bytes of data that derive from input bytes {4,5,6,7}
20 // are compared with a constant 12345,
21 // we try to insert 12345, 12344, 12346 into bytes
22 // {4,5,6,7} of the next fuzzed inputs.
24 // The fuzzer can work only with the traces, or with both traces and DFSan.
26 // DataFlowSanitizer (DFSan) is a tool for
27 // generalised dynamic data flow (taint) analysis:
28 // http://clang.llvm.org/docs/DataFlowSanitizer.html .
30 // The approach with DFSan-based fuzzing has some similarity to
31 // "Taint-based Directed Whitebox Fuzzing"
32 // by Vijay Ganesh & Tim Leek & Martin Rinard:
33 // http://dspace.mit.edu/openaccess-disseminate/1721.1/59320,
34 // but it uses a full blown LLVM IR taint analysis and separate instrumentation
35 // to analyze all of the "attack points" at once.
37 // Workflow with DFSan:
38 // * lib/Fuzzer/Fuzzer*.cpp is compiled w/o any instrumentation.
39 // * The code under test is compiled with DFSan *and* with instruction traces.
40 // * Every call to HOOK(a,b) is replaced by DFSan with
41 // __dfsw_HOOK(a, b, label(a), label(b)) so that __dfsw_HOOK
42 // gets all the taint labels for the arguments.
43 // * At the Fuzzer startup we assign a unique DFSan label
44 // to every byte of the input string (Fuzzer::CurrentUnit) so that for any
45 // chunk of data we know which input bytes it has derived from.
46 // * The __dfsw_* functions (implemented in this file) record the
47 // parameters (i.e. the application data and the corresponding taint labels)
49 // * Fuzzer::ApplyTraceBasedMutation() tries to use the data recorded
50 // by __dfsw_* hooks to guide the fuzzing towards new application states.
52 // Parts of this code will not function when DFSan is not linked in.
53 // Instead of using ifdefs and thus requiring a separate build of lib/Fuzzer
54 // we redeclare the dfsan_* interface functions as weak and check if they
55 // are nullptr before calling.
56 // If this approach proves to be useful we may add attribute(weak) to the
57 // dfsan declarations in dfsan_interface.h
59 // This module is in the "proof of concept" stage.
60 // It is capable of solving only the simplest puzzles
61 // like test/dfsan/DFSanSimpleCmpTest.cpp.
62 //===----------------------------------------------------------------------===//
64 /* Example of manual usage (-fsanitize=dataflow is optional):
67 clang -fPIC -c -g -O2 -std=c++11 Fuzzer*.cpp
68 clang++ -O0 -std=c++11 -fsanitize-coverage=edge,trace-cmp \
70 test/SimpleCmpTest.cpp Fuzzer*.o
75 #include "FuzzerDFSan.h"
76 #include "FuzzerInternal.h"
81 #include <unordered_map>
83 #if !LLVM_FUZZER_SUPPORTS_DFSAN
84 // Stubs for dfsan for platforms where dfsan does not exist and weak
85 // functions don't work.
87 dfsan_label dfsan_create_label(const char *desc, void *userdata) { return 0; }
88 void dfsan_set_label(dfsan_label label, void *addr, size_t size) {}
89 void dfsan_add_label(dfsan_label label, void *addr, size_t size) {}
90 const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
93 dfsan_label dfsan_read_label(const void *addr, size_t size) { return 0; }
95 #endif // !LLVM_FUZZER_SUPPORTS_DFSAN
99 // These values are copied from include/llvm/IR/InstrTypes.h.
100 // We do not include the LLVM headers here to remain independent.
101 // If these values ever change, an assertion in ComputeCmp will fail.
103 ICMP_EQ = 32, ///< equal
104 ICMP_NE = 33, ///< not equal
105 ICMP_UGT = 34, ///< unsigned greater than
106 ICMP_UGE = 35, ///< unsigned greater or equal
107 ICMP_ULT = 36, ///< unsigned less than
108 ICMP_ULE = 37, ///< unsigned less or equal
109 ICMP_SGT = 38, ///< signed greater than
110 ICMP_SGE = 39, ///< signed greater or equal
111 ICMP_SLT = 40, ///< signed less than
112 ICMP_SLE = 41, ///< signed less or equal
115 template <class U, class S>
116 bool ComputeCmp(size_t CmpType, U Arg1, U Arg2) {
118 case ICMP_EQ : return Arg1 == Arg2;
119 case ICMP_NE : return Arg1 != Arg2;
120 case ICMP_UGT: return Arg1 > Arg2;
121 case ICMP_UGE: return Arg1 >= Arg2;
122 case ICMP_ULT: return Arg1 < Arg2;
123 case ICMP_ULE: return Arg1 <= Arg2;
124 case ICMP_SGT: return (S)Arg1 > (S)Arg2;
125 case ICMP_SGE: return (S)Arg1 >= (S)Arg2;
126 case ICMP_SLT: return (S)Arg1 < (S)Arg2;
127 case ICMP_SLE: return (S)Arg1 <= (S)Arg2;
128 default: assert(0 && "unsupported CmpType");
133 static bool ComputeCmp(size_t CmpSize, size_t CmpType, uint64_t Arg1,
135 if (CmpSize == 8) return ComputeCmp<uint64_t, int64_t>(CmpType, Arg1, Arg2);
136 if (CmpSize == 4) return ComputeCmp<uint32_t, int32_t>(CmpType, Arg1, Arg2);
137 if (CmpSize == 2) return ComputeCmp<uint16_t, int16_t>(CmpType, Arg1, Arg2);
138 if (CmpSize == 1) return ComputeCmp<uint8_t, int8_t>(CmpType, Arg1, Arg2);
140 if (CmpType == ICMP_EQ) return Arg1 == Arg2;
141 // assert(0 && "unsupported cmp and type size combination");
145 // As a simplification we use the range of input bytes instead of a set of input
148 uint16_t Beg, End; // Range is [Beg, End), thus Beg==End is an empty range.
150 LabelRange(uint16_t Beg = 0, uint16_t End = 0) : Beg(Beg), End(End) {}
152 static LabelRange Join(LabelRange LR1, LabelRange LR2) {
153 if (LR1.Beg == LR1.End) return LR2;
154 if (LR2.Beg == LR2.End) return LR1;
155 return {std::min(LR1.Beg, LR2.Beg), std::max(LR1.End, LR2.End)};
157 LabelRange &Join(LabelRange LR) {
158 return *this = Join(*this, LR);
160 static LabelRange Singleton(const dfsan_label_info *LI) {
161 uint16_t Idx = (uint16_t)(uintptr_t)LI->userdata;
163 return {(uint16_t)(Idx - 1), Idx};
167 // For now, very simple: put Size bytes of Data at position Pos.
168 struct TraceBasedMutation {
169 static const size_t kMaxSize = 28;
172 uint8_t Data[kMaxSize];
177 TraceState(const Fuzzer::FuzzingOptions &Options, const Unit &CurrentUnit)
178 : Options(Options), CurrentUnit(CurrentUnit) {
179 // Current trace collection is not thread-friendly and it probably
180 // does not have to be such, but at least we should not crash in presence
181 // of threads. So, just ignore all traces coming from all threads but one.
185 LabelRange GetLabelRange(dfsan_label L);
186 void DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
187 uint64_t Arg1, uint64_t Arg2, dfsan_label L1,
189 void DFSanSwitchCallback(uint64_t PC, size_t ValSizeInBits, uint64_t Val,
190 size_t NumCases, uint64_t *Cases, dfsan_label L);
191 void TraceCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
192 uint64_t Arg1, uint64_t Arg2);
194 void TraceSwitchCallback(uintptr_t PC, size_t ValSizeInBits, uint64_t Val,
195 size_t NumCases, uint64_t *Cases);
196 int TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData,
199 void StartTraceRecording() {
200 if (!Options.UseTraces) return;
201 RecordingTraces = true;
205 size_t StopTraceRecording(FuzzerRandomBase &Rand) {
206 RecordingTraces = false;
210 void ApplyTraceBasedMutation(size_t Idx, fuzzer::Unit *U);
212 void AddMutation(uint32_t Pos, uint32_t Size, uint64_t Data) {
213 if (NumMutations >= kMaxMutations) return;
214 auto &M = Mutations[NumMutations++];
217 memcpy(M.Data, &Data, sizeof(Data));
221 bool IsTwoByteData(uint64_t Data) {
222 int64_t Signed = static_cast<int64_t>(Data);
224 return Signed == 0 || Signed == -1L;
226 bool RecordingTraces = false;
227 static const size_t kMaxMutations = 1 << 16;
229 TraceBasedMutation Mutations[kMaxMutations];
230 LabelRange LabelRanges[1 << (sizeof(dfsan_label) * 8)];
231 const Fuzzer::FuzzingOptions &Options;
232 const Unit &CurrentUnit;
233 static thread_local bool IsMyThread;
236 thread_local bool TraceState::IsMyThread;
238 LabelRange TraceState::GetLabelRange(dfsan_label L) {
239 LabelRange &LR = LabelRanges[L];
240 if (LR.Beg < LR.End || L == 0)
242 const dfsan_label_info *LI = dfsan_get_label_info(L);
243 if (LI->l1 || LI->l2)
244 return LR = LabelRange::Join(GetLabelRange(LI->l1), GetLabelRange(LI->l2));
245 return LR = LabelRange::Singleton(LI);
248 void TraceState::ApplyTraceBasedMutation(size_t Idx, fuzzer::Unit *U) {
249 assert(Idx < NumMutations);
250 auto &M = Mutations[Idx];
251 if (Options.Verbosity >= 3) {
252 Printf("TBM Pos %u Size %u ", M.Pos, M.Size);
253 for (uint32_t i = 0; i < M.Size; i++)
254 Printf("%02x", M.Data[i]);
257 if (M.Pos + M.Size > U->size()) return;
258 memcpy(U->data() + M.Pos, &M.Data[0], M.Size);
261 void TraceState::DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
262 uint64_t Arg1, uint64_t Arg2, dfsan_label L1,
264 assert(ReallyHaveDFSan());
265 if (!RecordingTraces || !IsMyThread) return;
266 if (L1 == 0 && L2 == 0)
267 return; // Not actionable.
268 if (L1 != 0 && L2 != 0)
269 return; // Probably still actionable.
270 bool Res = ComputeCmp(CmpSize, CmpType, Arg1, Arg2);
271 uint64_t Data = L1 ? Arg2 : Arg1;
272 LabelRange LR = L1 ? GetLabelRange(L1) : GetLabelRange(L2);
274 for (size_t Pos = LR.Beg; Pos + CmpSize <= LR.End; Pos++) {
275 AddMutation(Pos, CmpSize, Data);
276 AddMutation(Pos, CmpSize, Data + 1);
277 AddMutation(Pos, CmpSize, Data - 1);
280 if (CmpSize > LR.End - LR.Beg)
281 AddMutation(LR.Beg, (unsigned)(LR.End - LR.Beg), Data);
284 if (Options.Verbosity >= 3)
285 Printf("DFSanCmpCallback: PC %lx S %zd T %zd A1 %llx A2 %llx R %d L1 %d L2 "
287 PC, CmpSize, CmpType, Arg1, Arg2, Res, L1, L2, NumMutations);
290 void TraceState::DFSanSwitchCallback(uint64_t PC, size_t ValSizeInBits,
291 uint64_t Val, size_t NumCases,
292 uint64_t *Cases, dfsan_label L) {
293 assert(ReallyHaveDFSan());
294 if (!RecordingTraces || !IsMyThread) return;
295 if (!L) return; // Not actionable.
296 LabelRange LR = GetLabelRange(L);
297 size_t ValSize = ValSizeInBits / 8;
298 bool TryShort = IsTwoByteData(Val);
299 for (size_t i = 0; i < NumCases; i++)
300 TryShort &= IsTwoByteData(Cases[i]);
302 for (size_t Pos = LR.Beg; Pos + ValSize <= LR.End; Pos++)
303 for (size_t i = 0; i < NumCases; i++)
304 AddMutation(Pos, ValSize, Cases[i]);
307 for (size_t Pos = LR.Beg; Pos + 2 <= LR.End; Pos++)
308 for (size_t i = 0; i < NumCases; i++)
309 AddMutation(Pos, 2, Cases[i]);
311 if (Options.Verbosity >= 3)
312 Printf("DFSanSwitchCallback: PC %lx Val %zd SZ %zd # %zd L %d: {%d, %d} "
314 PC, Val, ValSize, NumCases, L, LR.Beg, LR.End, TryShort);
317 int TraceState::TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData,
320 const uint8_t *Beg = CurrentUnit.data();
321 const uint8_t *End = Beg + CurrentUnit.size();
322 for (const uint8_t *Cur = Beg; Cur < End; Cur++) {
323 Cur = (uint8_t *)memmem(Cur, End - Cur, &PresentData, DataSize);
326 size_t Pos = Cur - Beg;
327 assert(Pos < CurrentUnit.size());
328 AddMutation(Pos, DataSize, DesiredData);
329 AddMutation(Pos, DataSize, DesiredData + 1);
330 AddMutation(Pos, DataSize, DesiredData - 1);
336 void TraceState::TraceCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
337 uint64_t Arg1, uint64_t Arg2) {
338 if (!RecordingTraces || !IsMyThread) return;
340 if (Options.Verbosity >= 3)
341 Printf("TraceCmp %zd/%zd: %p %zd %zd\n", CmpSize, CmpType, PC, Arg1, Arg2);
342 Added += TryToAddDesiredData(Arg1, Arg2, CmpSize);
343 Added += TryToAddDesiredData(Arg2, Arg1, CmpSize);
344 if (!Added && CmpSize == 4 && IsTwoByteData(Arg1) && IsTwoByteData(Arg2)) {
345 Added += TryToAddDesiredData(Arg1, Arg2, 2);
346 Added += TryToAddDesiredData(Arg2, Arg1, 2);
350 void TraceState::TraceSwitchCallback(uintptr_t PC, size_t ValSizeInBits,
351 uint64_t Val, size_t NumCases,
353 if (!RecordingTraces || !IsMyThread) return;
354 size_t ValSize = ValSizeInBits / 8;
355 bool TryShort = IsTwoByteData(Val);
356 for (size_t i = 0; i < NumCases; i++)
357 TryShort &= IsTwoByteData(Cases[i]);
359 if (Options.Verbosity >= 3)
360 Printf("TraceSwitch: %p %zd # %zd; TryShort %d\n", PC, Val, NumCases,
363 for (size_t i = 0; i < NumCases; i++) {
364 TryToAddDesiredData(Val, Cases[i], ValSize);
366 TryToAddDesiredData(Val, Cases[i], 2);
370 static TraceState *TS;
372 void Fuzzer::StartTraceRecording() {
374 if (ReallyHaveDFSan())
375 for (size_t i = 0; i < static_cast<size_t>(Options.MaxLen); i++)
376 dfsan_set_label(i + 1, &CurrentUnit[i], 1);
377 TS->StartTraceRecording();
380 size_t Fuzzer::StopTraceRecording() {
382 return TS->StopTraceRecording(USF.GetRand());
385 void Fuzzer::ApplyTraceBasedMutation(size_t Idx, Unit *U) {
387 TS->ApplyTraceBasedMutation(Idx, U);
390 void Fuzzer::InitializeTraceState() {
391 if (!Options.UseTraces) return;
392 TS = new TraceState(Options, CurrentUnit);
393 CurrentUnit.resize(Options.MaxLen);
394 // The rest really requires DFSan.
395 if (!ReallyHaveDFSan()) return;
396 for (size_t i = 0; i < static_cast<size_t>(Options.MaxLen); i++) {
397 dfsan_label L = dfsan_create_label("input", (void*)(i + 1));
398 // We assume that no one else has called dfsan_create_label before.
400 Printf("DFSan labels are not starting from 1, exiting\n");
406 static size_t InternalStrnlen(const char *S, size_t MaxLen) {
408 for (; Len < MaxLen && S[Len]; Len++) {}
412 } // namespace fuzzer
417 void __dfsw___sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1,
418 uint64_t Arg2, dfsan_label L0,
419 dfsan_label L1, dfsan_label L2) {
422 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
423 uint64_t CmpSize = (SizeAndType >> 32) / 8;
424 uint64_t Type = (SizeAndType << 32) >> 32;
425 TS->DFSanCmpCallback(PC, CmpSize, Type, Arg1, Arg2, L1, L2);
428 void __dfsw___sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases,
429 dfsan_label L1, dfsan_label L2) {
431 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
432 TS->DFSanSwitchCallback(PC, Cases[1], Val, Cases[0], Cases+2, L1);
435 void dfsan_weak_hook_memcmp(void *caller_pc, const void *s1, const void *s2,
436 size_t n, dfsan_label s1_label,
437 dfsan_label s2_label, dfsan_label n_label) {
439 uintptr_t PC = reinterpret_cast<uintptr_t>(caller_pc);
440 uint64_t S1 = 0, S2 = 0;
441 // Simplification: handle only first 8 bytes.
442 memcpy(&S1, s1, std::min(n, sizeof(S1)));
443 memcpy(&S2, s2, std::min(n, sizeof(S2)));
444 dfsan_label L1 = dfsan_read_label(s1, n);
445 dfsan_label L2 = dfsan_read_label(s2, n);
446 TS->DFSanCmpCallback(PC, n, fuzzer::ICMP_EQ, S1, S2, L1, L2);
449 void dfsan_weak_hook_strncmp(void *caller_pc, const char *s1, const char *s2,
450 size_t n, dfsan_label s1_label,
451 dfsan_label s2_label, dfsan_label n_label) {
453 uintptr_t PC = reinterpret_cast<uintptr_t>(caller_pc);
454 uint64_t S1 = 0, S2 = 0;
455 n = std::min(n, fuzzer::InternalStrnlen(s1, n));
456 n = std::min(n, fuzzer::InternalStrnlen(s2, n));
457 // Simplification: handle only first 8 bytes.
458 memcpy(&S1, s1, std::min(n, sizeof(S1)));
459 memcpy(&S2, s2, std::min(n, sizeof(S2)));
460 dfsan_label L1 = dfsan_read_label(s1, n);
461 dfsan_label L2 = dfsan_read_label(s2, n);
462 TS->DFSanCmpCallback(PC, n, fuzzer::ICMP_EQ, S1, S2, L1, L2);
465 void dfsan_weak_hook_strcmp(void *caller_pc, const char *s1, const char *s2,
466 dfsan_label s1_label, dfsan_label s2_label) {
468 uintptr_t PC = reinterpret_cast<uintptr_t>(caller_pc);
469 uint64_t S1 = 0, S2 = 0;
470 size_t Len1 = strlen(s1);
471 size_t Len2 = strlen(s2);
472 size_t N = std::min(Len1, Len2);
473 if (N <= 1) return; // Not interesting.
474 // Simplification: handle only first 8 bytes.
475 memcpy(&S1, s1, std::min(N, sizeof(S1)));
476 memcpy(&S2, s2, std::min(N, sizeof(S2)));
477 dfsan_label L1 = dfsan_read_label(s1, Len1);
478 dfsan_label L2 = dfsan_read_label(s2, Len2);
479 TS->DFSanCmpCallback(PC, N, fuzzer::ICMP_EQ, S1, S2, L1, L2);
482 void __sanitizer_weak_hook_memcmp(void *caller_pc, const void *s1,
483 const void *s2, size_t n) {
485 uintptr_t PC = reinterpret_cast<uintptr_t>(caller_pc);
486 uint64_t S1 = 0, S2 = 0;
487 // Simplification: handle only first 8 bytes.
488 memcpy(&S1, s1, std::min(n, sizeof(S1)));
489 memcpy(&S2, s2, std::min(n, sizeof(S2)));
490 TS->TraceCmpCallback(PC, n, fuzzer::ICMP_EQ, S1, S2);
493 void __sanitizer_weak_hook_strncmp(void *caller_pc, const char *s1,
494 const char *s2, size_t n) {
496 uintptr_t PC = reinterpret_cast<uintptr_t>(caller_pc);
497 uint64_t S1 = 0, S2 = 0;
498 size_t Len1 = fuzzer::InternalStrnlen(s1, n);
499 size_t Len2 = fuzzer::InternalStrnlen(s2, n);
500 n = std::min(n, Len1);
501 n = std::min(n, Len2);
502 if (n <= 1) return; // Not interesting.
503 // Simplification: handle only first 8 bytes.
504 memcpy(&S1, s1, std::min(n, sizeof(S1)));
505 memcpy(&S2, s2, std::min(n, sizeof(S2)));
506 TS->TraceCmpCallback(PC, n, fuzzer::ICMP_EQ, S1, S2);
509 void __sanitizer_weak_hook_strcmp(void *caller_pc, const char *s1,
512 uintptr_t PC = reinterpret_cast<uintptr_t>(caller_pc);
513 uint64_t S1 = 0, S2 = 0;
514 size_t Len1 = strlen(s1);
515 size_t Len2 = strlen(s2);
516 size_t N = std::min(Len1, Len2);
517 if (N <= 1) return; // Not interesting.
518 // Simplification: handle only first 8 bytes.
519 memcpy(&S1, s1, std::min(N, sizeof(S1)));
520 memcpy(&S2, s2, std::min(N, sizeof(S2)));
521 TS->TraceCmpCallback(PC, N, fuzzer::ICMP_EQ, S1, S2);
524 __attribute__((visibility("default")))
525 void __sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1,
528 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
529 uint64_t CmpSize = (SizeAndType >> 32) / 8;
530 uint64_t Type = (SizeAndType << 32) >> 32;
531 TS->TraceCmpCallback(PC, CmpSize, Type, Arg1, Arg2);
534 __attribute__((visibility("default")))
535 void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases) {
537 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
538 TS->TraceSwitchCallback(PC, Cases[1], Val, Cases[0], Cases + 2);