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)
50 // Parts of this code will not function when DFSan is not linked in.
51 // Instead of using ifdefs and thus requiring a separate build of lib/Fuzzer
52 // we redeclare the dfsan_* interface functions as weak and check if they
53 // are nullptr before calling.
54 // If this approach proves to be useful we may add attribute(weak) to the
55 // dfsan declarations in dfsan_interface.h
57 // This module is in the "proof of concept" stage.
58 // It is capable of solving only the simplest puzzles
59 // like test/dfsan/DFSanSimpleCmpTest.cpp.
60 //===----------------------------------------------------------------------===//
62 /* Example of manual usage (-fsanitize=dataflow is optional):
65 clang -fPIC -c -g -O2 -std=c++11 Fuzzer*.cpp
66 clang++ -O0 -std=c++11 -fsanitize-coverage=edge,trace-cmp \
68 test/SimpleCmpTest.cpp Fuzzer*.o
73 #include "FuzzerDFSan.h"
74 #include "FuzzerInternal.h"
79 #include <unordered_map>
81 #if !LLVM_FUZZER_SUPPORTS_DFSAN
82 // Stubs for dfsan for platforms where dfsan does not exist and weak
83 // functions don't work.
85 dfsan_label dfsan_create_label(const char *desc, void *userdata) { return 0; }
86 void dfsan_set_label(dfsan_label label, void *addr, size_t size) {}
87 void dfsan_add_label(dfsan_label label, void *addr, size_t size) {}
88 const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
91 dfsan_label dfsan_read_label(const void *addr, size_t size) { return 0; }
93 #endif // !LLVM_FUZZER_SUPPORTS_DFSAN
97 // These values are copied from include/llvm/IR/InstrTypes.h.
98 // We do not include the LLVM headers here to remain independent.
99 // If these values ever change, an assertion in ComputeCmp will fail.
101 ICMP_EQ = 32, ///< equal
102 ICMP_NE = 33, ///< not equal
103 ICMP_UGT = 34, ///< unsigned greater than
104 ICMP_UGE = 35, ///< unsigned greater or equal
105 ICMP_ULT = 36, ///< unsigned less than
106 ICMP_ULE = 37, ///< unsigned less or equal
107 ICMP_SGT = 38, ///< signed greater than
108 ICMP_SGE = 39, ///< signed greater or equal
109 ICMP_SLT = 40, ///< signed less than
110 ICMP_SLE = 41, ///< signed less or equal
113 template <class U, class S>
114 bool ComputeCmp(size_t CmpType, U Arg1, U Arg2) {
116 case ICMP_EQ : return Arg1 == Arg2;
117 case ICMP_NE : return Arg1 != Arg2;
118 case ICMP_UGT: return Arg1 > Arg2;
119 case ICMP_UGE: return Arg1 >= Arg2;
120 case ICMP_ULT: return Arg1 < Arg2;
121 case ICMP_ULE: return Arg1 <= Arg2;
122 case ICMP_SGT: return (S)Arg1 > (S)Arg2;
123 case ICMP_SGE: return (S)Arg1 >= (S)Arg2;
124 case ICMP_SLT: return (S)Arg1 < (S)Arg2;
125 case ICMP_SLE: return (S)Arg1 <= (S)Arg2;
126 default: assert(0 && "unsupported CmpType");
131 static bool ComputeCmp(size_t CmpSize, size_t CmpType, uint64_t Arg1,
133 if (CmpSize == 8) return ComputeCmp<uint64_t, int64_t>(CmpType, Arg1, Arg2);
134 if (CmpSize == 4) return ComputeCmp<uint32_t, int32_t>(CmpType, Arg1, Arg2);
135 if (CmpSize == 2) return ComputeCmp<uint16_t, int16_t>(CmpType, Arg1, Arg2);
136 if (CmpSize == 1) return ComputeCmp<uint8_t, int8_t>(CmpType, Arg1, Arg2);
138 if (CmpType == ICMP_EQ) return Arg1 == Arg2;
139 // assert(0 && "unsupported cmp and type size combination");
143 // As a simplification we use the range of input bytes instead of a set of input
146 uint16_t Beg, End; // Range is [Beg, End), thus Beg==End is an empty range.
148 LabelRange(uint16_t Beg = 0, uint16_t End = 0) : Beg(Beg), End(End) {}
150 static LabelRange Join(LabelRange LR1, LabelRange LR2) {
151 if (LR1.Beg == LR1.End) return LR2;
152 if (LR2.Beg == LR2.End) return LR1;
153 return {std::min(LR1.Beg, LR2.Beg), std::max(LR1.End, LR2.End)};
155 LabelRange &Join(LabelRange LR) {
156 return *this = Join(*this, LR);
158 static LabelRange Singleton(const dfsan_label_info *LI) {
159 uint16_t Idx = (uint16_t)(uintptr_t)LI->userdata;
161 return {(uint16_t)(Idx - 1), Idx};
165 // For now, very simple: put Size bytes of Data at position Pos.
166 struct TraceBasedMutation {
167 static const size_t kMaxSize = 28;
170 uint8_t Data[kMaxSize];
173 const size_t TraceBasedMutation::kMaxSize;
177 TraceState(UserSuppliedFuzzer &USF,
178 const Fuzzer::FuzzingOptions &Options, const Unit &CurrentUnit)
179 : USF(USF), Options(Options), CurrentUnit(CurrentUnit) {
180 // Current trace collection is not thread-friendly and it probably
181 // does not have to be such, but at least we should not crash in presence
182 // of threads. So, just ignore all traces coming from all threads but one.
186 LabelRange GetLabelRange(dfsan_label L);
187 void DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
188 uint64_t Arg1, uint64_t Arg2, dfsan_label L1,
190 void DFSanMemcmpCallback(size_t CmpSize, const uint8_t *Data1,
191 const uint8_t *Data2, dfsan_label L1,
193 void DFSanSwitchCallback(uint64_t PC, size_t ValSizeInBits, uint64_t Val,
194 size_t NumCases, uint64_t *Cases, dfsan_label L);
195 void TraceCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
196 uint64_t Arg1, uint64_t Arg2);
197 void TraceMemcmpCallback(size_t CmpSize, const uint8_t *Data1,
198 const uint8_t *Data2);
200 void TraceSwitchCallback(uintptr_t PC, size_t ValSizeInBits, uint64_t Val,
201 size_t NumCases, uint64_t *Cases);
202 int TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData,
204 int TryToAddDesiredData(const uint8_t *PresentData,
205 const uint8_t *DesiredData, size_t DataSize);
207 void StartTraceRecording() {
208 if (!Options.UseTraces) return;
209 RecordingTraces = true;
211 USF.GetMD().ClearAutoDictionary();
214 void StopTraceRecording() {
215 if (!RecordingTraces) return;
216 RecordingTraces = false;
217 for (size_t i = 0; i < NumMutations; i++) {
218 auto &M = Mutations[i];
219 USF.GetMD().AddWordToAutoDictionary(Unit(M.Data, M.Data + M.Size), M.Pos);
223 void AddMutation(uint32_t Pos, uint32_t Size, const uint8_t *Data) {
224 if (NumMutations >= kMaxMutations) return;
225 assert(Size <= TraceBasedMutation::kMaxSize);
226 auto &M = Mutations[NumMutations++];
229 memcpy(M.Data, Data, Size);
232 void AddMutation(uint32_t Pos, uint32_t Size, uint64_t Data) {
233 assert(Size <= sizeof(Data));
234 AddMutation(Pos, Size, reinterpret_cast<uint8_t*>(&Data));
238 bool IsTwoByteData(uint64_t Data) {
239 int64_t Signed = static_cast<int64_t>(Data);
241 return Signed == 0 || Signed == -1L;
243 bool RecordingTraces = false;
244 static const size_t kMaxMutations = 1 << 16;
246 TraceBasedMutation Mutations[kMaxMutations];
247 LabelRange LabelRanges[1 << (sizeof(dfsan_label) * 8)];
248 UserSuppliedFuzzer &USF;
249 const Fuzzer::FuzzingOptions &Options;
250 const Unit &CurrentUnit;
251 static thread_local bool IsMyThread;
254 thread_local bool TraceState::IsMyThread;
256 LabelRange TraceState::GetLabelRange(dfsan_label L) {
257 LabelRange &LR = LabelRanges[L];
258 if (LR.Beg < LR.End || L == 0)
260 const dfsan_label_info *LI = dfsan_get_label_info(L);
261 if (LI->l1 || LI->l2)
262 return LR = LabelRange::Join(GetLabelRange(LI->l1), GetLabelRange(LI->l2));
263 return LR = LabelRange::Singleton(LI);
266 void TraceState::DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
267 uint64_t Arg1, uint64_t Arg2, dfsan_label L1,
269 assert(ReallyHaveDFSan());
270 if (!RecordingTraces || !IsMyThread) return;
271 if (L1 == 0 && L2 == 0)
272 return; // Not actionable.
273 if (L1 != 0 && L2 != 0)
274 return; // Probably still actionable.
275 bool Res = ComputeCmp(CmpSize, CmpType, Arg1, Arg2);
276 uint64_t Data = L1 ? Arg2 : Arg1;
277 LabelRange LR = L1 ? GetLabelRange(L1) : GetLabelRange(L2);
279 for (size_t Pos = LR.Beg; Pos + CmpSize <= LR.End; Pos++) {
280 AddMutation(Pos, CmpSize, Data);
281 AddMutation(Pos, CmpSize, Data + 1);
282 AddMutation(Pos, CmpSize, Data - 1);
285 if (CmpSize > LR.End - LR.Beg)
286 AddMutation(LR.Beg, (unsigned)(LR.End - LR.Beg), Data);
289 if (Options.Verbosity >= 3)
290 Printf("DFSanCmpCallback: PC %lx S %zd T %zd A1 %llx A2 %llx R %d L1 %d L2 "
292 PC, CmpSize, CmpType, Arg1, Arg2, Res, L1, L2, NumMutations);
295 void TraceState::DFSanMemcmpCallback(size_t CmpSize, const uint8_t *Data1,
296 const uint8_t *Data2, dfsan_label L1,
299 assert(ReallyHaveDFSan());
300 if (!RecordingTraces || !IsMyThread) return;
301 if (L1 == 0 && L2 == 0)
302 return; // Not actionable.
303 if (L1 != 0 && L2 != 0)
304 return; // Probably still actionable.
306 const uint8_t *Data = L1 ? Data2 : Data1;
307 LabelRange LR = L1 ? GetLabelRange(L1) : GetLabelRange(L2);
308 for (size_t Pos = LR.Beg; Pos + CmpSize <= LR.End; Pos++) {
309 AddMutation(Pos, CmpSize, Data);
310 if (Options.Verbosity >= 3)
311 Printf("DFSanMemcmpCallback: Pos %d Size %d\n", Pos, CmpSize);
315 void TraceState::DFSanSwitchCallback(uint64_t PC, size_t ValSizeInBits,
316 uint64_t Val, size_t NumCases,
317 uint64_t *Cases, dfsan_label L) {
318 assert(ReallyHaveDFSan());
319 if (!RecordingTraces || !IsMyThread) return;
320 if (!L) return; // Not actionable.
321 LabelRange LR = GetLabelRange(L);
322 size_t ValSize = ValSizeInBits / 8;
323 bool TryShort = IsTwoByteData(Val);
324 for (size_t i = 0; i < NumCases; i++)
325 TryShort &= IsTwoByteData(Cases[i]);
327 for (size_t Pos = LR.Beg; Pos + ValSize <= LR.End; Pos++)
328 for (size_t i = 0; i < NumCases; i++)
329 AddMutation(Pos, ValSize, Cases[i]);
332 for (size_t Pos = LR.Beg; Pos + 2 <= LR.End; Pos++)
333 for (size_t i = 0; i < NumCases; i++)
334 AddMutation(Pos, 2, Cases[i]);
336 if (Options.Verbosity >= 3)
337 Printf("DFSanSwitchCallback: PC %lx Val %zd SZ %zd # %zd L %d: {%d, %d} "
339 PC, Val, ValSize, NumCases, L, LR.Beg, LR.End, TryShort);
342 int TraceState::TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData,
345 const uint8_t *Beg = CurrentUnit.data();
346 const uint8_t *End = Beg + CurrentUnit.size();
347 for (const uint8_t *Cur = Beg; Cur < End; Cur++) {
348 Cur = (uint8_t *)memmem(Cur, End - Cur, &PresentData, DataSize);
351 size_t Pos = Cur - Beg;
352 assert(Pos < CurrentUnit.size());
353 AddMutation(Pos, DataSize, DesiredData);
354 AddMutation(Pos, DataSize, DesiredData + 1);
355 AddMutation(Pos, DataSize, DesiredData - 1);
361 int TraceState::TryToAddDesiredData(const uint8_t *PresentData,
362 const uint8_t *DesiredData,
365 const uint8_t *Beg = CurrentUnit.data();
366 const uint8_t *End = Beg + CurrentUnit.size();
367 for (const uint8_t *Cur = Beg; Cur < End; Cur++) {
368 Cur = (uint8_t *)memmem(Cur, End - Cur, PresentData, DataSize);
371 size_t Pos = Cur - Beg;
372 assert(Pos < CurrentUnit.size());
373 AddMutation(Pos, DataSize, DesiredData);
379 void TraceState::TraceCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
380 uint64_t Arg1, uint64_t Arg2) {
381 if (!RecordingTraces || !IsMyThread) return;
383 if (Options.Verbosity >= 3)
384 Printf("TraceCmp %zd/%zd: %p %zd %zd\n", CmpSize, CmpType, PC, Arg1, Arg2);
385 Added += TryToAddDesiredData(Arg1, Arg2, CmpSize);
386 Added += TryToAddDesiredData(Arg2, Arg1, CmpSize);
387 if (!Added && CmpSize == 4 && IsTwoByteData(Arg1) && IsTwoByteData(Arg2)) {
388 Added += TryToAddDesiredData(Arg1, Arg2, 2);
389 Added += TryToAddDesiredData(Arg2, Arg1, 2);
393 void TraceState::TraceMemcmpCallback(size_t CmpSize, const uint8_t *Data1,
394 const uint8_t *Data2) {
395 if (!RecordingTraces || !IsMyThread) return;
396 CmpSize = std::min(CmpSize, TraceBasedMutation::kMaxSize);
397 TryToAddDesiredData(Data1, Data2, CmpSize);
398 TryToAddDesiredData(Data2, Data1, CmpSize);
401 void TraceState::TraceSwitchCallback(uintptr_t PC, size_t ValSizeInBits,
402 uint64_t Val, size_t NumCases,
404 if (!RecordingTraces || !IsMyThread) return;
405 size_t ValSize = ValSizeInBits / 8;
406 bool TryShort = IsTwoByteData(Val);
407 for (size_t i = 0; i < NumCases; i++)
408 TryShort &= IsTwoByteData(Cases[i]);
410 if (Options.Verbosity >= 3)
411 Printf("TraceSwitch: %p %zd # %zd; TryShort %d\n", PC, Val, NumCases,
414 for (size_t i = 0; i < NumCases; i++) {
415 TryToAddDesiredData(Val, Cases[i], ValSize);
417 TryToAddDesiredData(Val, Cases[i], 2);
421 static TraceState *TS;
423 void Fuzzer::StartTraceRecording() {
425 if (ReallyHaveDFSan())
426 for (size_t i = 0; i < static_cast<size_t>(Options.MaxLen); i++)
427 dfsan_set_label(i + 1, &CurrentUnit[i], 1);
428 TS->StartTraceRecording();
431 void Fuzzer::StopTraceRecording() {
433 TS->StopTraceRecording();
436 void Fuzzer::InitializeTraceState() {
437 if (!Options.UseTraces) return;
438 TS = new TraceState(USF, Options, CurrentUnit);
439 CurrentUnit.resize(Options.MaxLen);
440 // The rest really requires DFSan.
441 if (!ReallyHaveDFSan()) return;
442 for (size_t i = 0; i < static_cast<size_t>(Options.MaxLen); i++) {
443 dfsan_label L = dfsan_create_label("input", (void*)(i + 1));
444 // We assume that no one else has called dfsan_create_label before.
446 Printf("DFSan labels are not starting from 1, exiting\n");
452 static size_t InternalStrnlen(const char *S, size_t MaxLen) {
454 for (; Len < MaxLen && S[Len]; Len++) {}
458 } // namespace fuzzer
463 void __dfsw___sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1,
464 uint64_t Arg2, dfsan_label L0,
465 dfsan_label L1, dfsan_label L2) {
468 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
469 uint64_t CmpSize = (SizeAndType >> 32) / 8;
470 uint64_t Type = (SizeAndType << 32) >> 32;
471 TS->DFSanCmpCallback(PC, CmpSize, Type, Arg1, Arg2, L1, L2);
474 void __dfsw___sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases,
475 dfsan_label L1, dfsan_label L2) {
477 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
478 TS->DFSanSwitchCallback(PC, Cases[1], Val, Cases[0], Cases+2, L1);
481 void dfsan_weak_hook_memcmp(void *caller_pc, const void *s1, const void *s2,
482 size_t n, dfsan_label s1_label,
483 dfsan_label s2_label, dfsan_label n_label) {
485 dfsan_label L1 = dfsan_read_label(s1, n);
486 dfsan_label L2 = dfsan_read_label(s2, n);
487 TS->DFSanMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
488 reinterpret_cast<const uint8_t *>(s2), L1, L2);
491 void dfsan_weak_hook_strncmp(void *caller_pc, const char *s1, const char *s2,
492 size_t n, dfsan_label s1_label,
493 dfsan_label s2_label, dfsan_label n_label) {
495 n = std::min(n, fuzzer::InternalStrnlen(s1, n));
496 n = std::min(n, fuzzer::InternalStrnlen(s2, n));
497 dfsan_label L1 = dfsan_read_label(s1, n);
498 dfsan_label L2 = dfsan_read_label(s2, n);
499 TS->DFSanMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
500 reinterpret_cast<const uint8_t *>(s2), L1, L2);
503 void dfsan_weak_hook_strcmp(void *caller_pc, const char *s1, const char *s2,
504 dfsan_label s1_label, dfsan_label s2_label) {
506 size_t Len1 = strlen(s1);
507 size_t Len2 = strlen(s2);
508 size_t N = std::min(Len1, Len2);
509 if (N <= 1) return; // Not interesting.
510 dfsan_label L1 = dfsan_read_label(s1, Len1);
511 dfsan_label L2 = dfsan_read_label(s2, Len2);
512 TS->DFSanMemcmpCallback(N, reinterpret_cast<const uint8_t *>(s1),
513 reinterpret_cast<const uint8_t *>(s2), L1, L2);
516 void __sanitizer_weak_hook_memcmp(void *caller_pc, const void *s1,
517 const void *s2, size_t n) {
519 if (n <= 1) return; // Not interesting.
520 TS->TraceMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
521 reinterpret_cast<const uint8_t *>(s2));
524 void __sanitizer_weak_hook_strncmp(void *caller_pc, const char *s1,
525 const char *s2, size_t n) {
527 size_t Len1 = fuzzer::InternalStrnlen(s1, n);
528 size_t Len2 = fuzzer::InternalStrnlen(s2, n);
529 n = std::min(n, Len1);
530 n = std::min(n, Len2);
531 if (n <= 1) return; // Not interesting.
532 TS->TraceMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
533 reinterpret_cast<const uint8_t *>(s2));
536 void __sanitizer_weak_hook_strcmp(void *caller_pc, const char *s1,
539 size_t Len1 = strlen(s1);
540 size_t Len2 = strlen(s2);
541 size_t N = std::min(Len1, Len2);
542 if (N <= 1) return; // Not interesting.
543 TS->TraceMemcmpCallback(N, reinterpret_cast<const uint8_t *>(s1),
544 reinterpret_cast<const uint8_t *>(s2));
547 __attribute__((visibility("default")))
548 void __sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1,
551 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
552 uint64_t CmpSize = (SizeAndType >> 32) / 8;
553 uint64_t Type = (SizeAndType << 32) >> 32;
554 TS->TraceCmpCallback(PC, CmpSize, Type, Arg1, Arg2);
557 __attribute__((visibility("default")))
558 void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases) {
560 uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
561 TS->TraceSwitchCallback(PC, Cases[1], Val, Cases[0], Cases + 2);