blob: e3b35d4de81cb81f9a94efb903f8694f9d4d8486 [file] [log] [blame]
Aaron Ballmanef116982015-01-29 16:58:29 +00001//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===//
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// Mutate a test input.
10//===----------------------------------------------------------------------===//
11
Kostya Serebryanyf3424592015-05-22 22:35:31 +000012#include <cstring>
13
Kostya Serebryany556894f2016-09-21 02:05:39 +000014#include "FuzzerCorpus.h"
15#include "FuzzerDefs.h"
16#include "FuzzerExtFunctions.h"
Kostya Serebryany6f5a8042016-09-21 01:50:50 +000017#include "FuzzerMutate.h"
Kostya Serebryany556894f2016-09-21 02:05:39 +000018#include "FuzzerOptions.h"
Kostya Serebryanybf29ff22015-08-06 01:29:13 +000019
Aaron Ballmanef116982015-01-29 16:58:29 +000020namespace fuzzer {
21
Kostya Serebryany2f13f222016-01-21 01:52:14 +000022const size_t Dictionary::kMaxDictSize;
23
Kostya Serebryany6f5a8042016-09-21 01:50:50 +000024static void PrintASCII(const Word &W, const char *PrintAfter) {
25 PrintASCII(W.data(), W.size(), PrintAfter);
26}
27
Mike Aizatskyf0b3e852016-06-23 20:44:48 +000028MutationDispatcher::MutationDispatcher(Random &Rand,
29 const FuzzingOptions &Options)
30 : Rand(Rand), Options(Options) {
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000031 DefaultMutators.insert(
32 DefaultMutators.begin(),
33 {
Kostya Serebryanydfbe59b2016-08-15 17:48:28 +000034 {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000035 {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
Kostya Serebryanydfbe59b2016-08-15 17:48:28 +000036 {&MutationDispatcher::Mutate_InsertRepeatedBytes,
37 "InsertRepeatedBytes"},
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000038 {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
39 {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
40 {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
41 {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
Kostya Serebryany0c537b12016-08-17 21:30:30 +000042 {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
Kostya Serebryanya7398ba2016-08-17 18:10:42 +000043 {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000044 {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
45 {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
46 "AddFromManualDict"},
47 {&MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary,
48 "AddFromTempAutoDict"},
49 {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
50 "AddFromPersAutoDict"},
51 });
52
Dan Liew1873a492016-06-07 23:32:50 +000053 if (EF->LLVMFuzzerCustomMutator)
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000054 Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
55 else
56 Mutators = DefaultMutators;
Mike Aizatsky41d66832016-06-07 20:22:15 +000057
Dan Liew1873a492016-06-07 23:32:50 +000058 if (EF->LLVMFuzzerCustomCrossOver)
Mike Aizatsky41d66832016-06-07 20:22:15 +000059 Mutators.push_back(
60 {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000061}
Kostya Serebryany23194962016-02-13 03:46:26 +000062
Kostya Serebryanya3992212016-02-13 03:00:53 +000063static char RandCh(Random &Rand) {
Kostya Serebryany404c69f2015-07-24 01:06:40 +000064 if (Rand.RandBool()) return Rand(256);
Kostya Serebryanya7398ba2016-08-17 18:10:42 +000065 const char *Special = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
Kostya Serebryany404c69f2015-07-24 01:06:40 +000066 return Special[Rand(sizeof(Special) - 1)];
Aaron Ballmanef116982015-01-29 16:58:29 +000067}
68
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000069size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size,
70 size_t MaxSize) {
Dan Liew1873a492016-06-07 23:32:50 +000071 return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, Rand.Rand());
Mike Aizatsky70fd3e42016-06-03 21:34:29 +000072}
73
Mike Aizatsky41d66832016-06-07 20:22:15 +000074size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size,
75 size_t MaxSize) {
76 if (!Corpus || Corpus->size() < 2 || Size == 0)
77 return 0;
78 size_t Idx = Rand(Corpus->size());
79 const Unit &Other = (*Corpus)[Idx];
80 if (Other.empty())
81 return 0;
82 MutateInPlaceHere.resize(MaxSize);
83 auto &U = MutateInPlaceHere;
Dan Liew1873a492016-06-07 23:32:50 +000084 size_t NewSize = EF->LLVMFuzzerCustomCrossOver(
Mike Aizatsky41d66832016-06-07 20:22:15 +000085 Data, Size, Other.data(), Other.size(), U.data(), U.size(), Rand.Rand());
86 if (!NewSize)
87 return 0;
88 assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit");
89 memcpy(Data, U.data(), NewSize);
90 return NewSize;
91}
92
Kostya Serebryanyec2dcb12015-09-03 21:24:19 +000093size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
94 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +000095 if (Size > MaxSize) return 0;
Kostya Serebryanybf29ff22015-08-06 01:29:13 +000096 assert(Size);
Kostya Serebryany152ac7a2016-01-07 01:49:35 +000097 size_t ShuffleAmount =
98 Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
Kostya Serebryanybf29ff22015-08-06 01:29:13 +000099 size_t ShuffleStart = Rand(Size - ShuffleAmount);
100 assert(ShuffleStart + ShuffleAmount <= Size);
101 std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount,
102 Rand);
103 return Size;
104}
105
Kostya Serebryanydfbe59b2016-08-15 17:48:28 +0000106size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size,
107 size_t MaxSize) {
Kostya Serebryany8ce74242015-08-01 01:42:51 +0000108 assert(Size);
Kostya Serebryanyb2e98972015-09-04 00:40:29 +0000109 if (Size == 1) return 0;
Kostya Serebryanydfbe59b2016-08-15 17:48:28 +0000110 size_t N = Rand(Size / 2) + 1;
111 assert(N < Size);
112 size_t Idx = Rand(Size - N + 1);
113 // Erase Data[Idx:Idx+N].
114 memmove(Data + Idx, Data + Idx + N, Size - Idx - N);
115 // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx);
116 return Size - N;
Kostya Serebryany8ce74242015-08-01 01:42:51 +0000117}
118
Kostya Serebryanyec2dcb12015-09-03 21:24:19 +0000119size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
120 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000121 if (Size >= MaxSize) return 0;
Kostya Serebryany86a5fba2015-08-01 02:23:06 +0000122 size_t Idx = Rand(Size + 1);
123 // Insert new value at Data[Idx].
124 memmove(Data + Idx + 1, Data + Idx, Size - Idx);
125 Data[Idx] = RandCh(Rand);
126 return Size + 1;
127}
128
Kostya Serebryanydfbe59b2016-08-15 17:48:28 +0000129size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data,
130 size_t Size,
131 size_t MaxSize) {
132 const size_t kMinBytesToInsert = 3;
133 if (Size + kMinBytesToInsert >= MaxSize) return 0;
134 size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128);
135 size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert;
136 assert(Size + N <= MaxSize && N);
137 size_t Idx = Rand(Size + 1);
138 // Insert new values at Data[Idx].
139 memmove(Data + Idx + N, Data + Idx, Size - Idx);
Kostya Serebryanye72774d2016-08-17 21:50:54 +0000140 // Give preference to 0x00 and 0xff.
141 uint8_t Byte = Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255);
Kostya Serebryanydfbe59b2016-08-15 17:48:28 +0000142 for (size_t i = 0; i < N; i++)
143 Data[Idx + i] = Byte;
144 return Size + N;
145}
146
Kostya Serebryanyec2dcb12015-09-03 21:24:19 +0000147size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
148 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000149 if (Size > MaxSize) return 0;
Kostya Serebryany86a5fba2015-08-01 02:23:06 +0000150 size_t Idx = Rand(Size);
151 Data[Idx] = RandCh(Rand);
152 return Size;
153}
154
Kostya Serebryanyec2dcb12015-09-03 21:24:19 +0000155size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
156 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000157 if (Size > MaxSize) return 0;
Kostya Serebryany86a5fba2015-08-01 02:23:06 +0000158 size_t Idx = Rand(Size);
Kostya Serebryanya7398ba2016-08-17 18:10:42 +0000159 Data[Idx] ^= 1 << Rand(8);
Kostya Serebryany86a5fba2015-08-01 02:23:06 +0000160 return Size;
161}
162
Kostya Serebryany152ac7a2016-01-07 01:49:35 +0000163size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
164 size_t Size,
165 size_t MaxSize) {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000166 return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
Kostya Serebryany152ac7a2016-01-07 01:49:35 +0000167}
168
Kostya Serebryany4b358742016-01-14 02:36:44 +0000169size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary(
170 uint8_t *Data, size_t Size, size_t MaxSize) {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000171 return AddWordFromDictionary(TempAutoDictionary, Data, Size, MaxSize);
Kostya Serebryany4b358742016-01-14 02:36:44 +0000172}
173
174size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
175 uint8_t *Data, size_t Size, size_t MaxSize) {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000176 return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
Kostya Serebryany152ac7a2016-01-07 01:49:35 +0000177}
178
Kostya Serebryany292cf032016-02-13 03:37:24 +0000179size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
180 size_t Size, size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000181 if (Size > MaxSize) return 0;
Kostya Serebryanyb2e98972015-09-04 00:40:29 +0000182 if (D.empty()) return 0;
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000183 DictionaryEntry &DE = D[Rand(D.size())];
184 const Word &W = DE.GetW();
185 bool UsePositionHint = DE.HasPositionHint() &&
186 DE.GetPositionHint() + W.size() < Size && Rand.RandBool();
Kostya Serebryany476f0ce2016-01-16 03:53:32 +0000187 if (Rand.RandBool()) { // Insert W.
188 if (Size + W.size() > MaxSize) return 0;
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000189 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
Kostya Serebryany476f0ce2016-01-16 03:53:32 +0000190 memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
191 memcpy(Data + Idx, W.data(), W.size());
192 Size += W.size();
193 } else { // Overwrite some bytes with W.
194 if (W.size() > Size) return 0;
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000195 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size());
Kostya Serebryany476f0ce2016-01-16 03:53:32 +0000196 memcpy(Data + Idx, W.data(), W.size());
Kostya Serebryany80eb76a2016-01-06 02:13:04 +0000197 }
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000198 DE.IncUseCount();
199 CurrentDictionaryEntrySequence.push_back(&DE);
Kostya Serebryany41740052016-01-12 02:36:59 +0000200 return Size;
Kostya Serebryany7d211662015-09-04 00:12:11 +0000201}
202
Kostya Serebryanya7398ba2016-08-17 18:10:42 +0000203// Overwrites part of To[0,ToSize) with a part of From[0,FromSize).
204// Returns ToSize.
205size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize,
206 uint8_t *To, size_t ToSize) {
207 // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize).
208 size_t ToBeg = Rand(ToSize);
209 size_t CopySize = Rand(ToSize - ToBeg) + 1;
210 assert(ToBeg + CopySize <= ToSize);
211 CopySize = std::min(CopySize, FromSize);
212 size_t FromBeg = Rand(FromSize - CopySize + 1);
213 assert(FromBeg + CopySize <= FromSize);
214 memmove(To + ToBeg, From + FromBeg, CopySize);
215 return ToSize;
216}
217
218// Inserts part of From[0,ToSize) into To.
219// Returns new size of To on success or 0 on failure.
220size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize,
221 uint8_t *To, size_t ToSize,
222 size_t MaxToSize) {
223 if (ToSize >= MaxToSize) return 0;
224 size_t AvailableSpace = MaxToSize - ToSize;
225 size_t MaxCopySize = std::min(AvailableSpace, FromSize);
226 size_t CopySize = Rand(MaxCopySize) + 1;
227 size_t FromBeg = Rand(FromSize - CopySize + 1);
228 assert(FromBeg + CopySize <= FromSize);
229 size_t ToInsertPos = Rand(ToSize + 1);
230 assert(ToInsertPos + CopySize <= MaxToSize);
231 size_t TailSize = ToSize - ToInsertPos;
232 if (To == From) {
233 MutateInPlaceHere.resize(MaxToSize);
234 memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize);
235 memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
236 memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize);
237 } else {
238 memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
239 memmove(To + ToInsertPos, From + FromBeg, CopySize);
240 }
241 return ToSize + CopySize;
242}
243
244size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size,
245 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000246 if (Size > MaxSize) return 0;
Kostya Serebryanya7398ba2016-08-17 18:10:42 +0000247 if (Rand.RandBool())
248 return CopyPartOf(Data, Size, Data, Size);
249 else
250 return InsertPartOf(Data, Size, Data, Size, MaxSize);
251}
252
Kostya Serebryany25425ad2015-09-08 17:19:31 +0000253size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
254 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000255 if (Size > MaxSize) return 0;
Kostya Serebryany25425ad2015-09-08 17:19:31 +0000256 size_t B = Rand(Size);
257 while (B < Size && !isdigit(Data[B])) B++;
258 if (B == Size) return 0;
259 size_t E = B;
260 while (E < Size && isdigit(Data[E])) E++;
261 assert(B < E);
262 // now we have digits in [B, E).
263 // strtol and friends don't accept non-zero-teminated data, parse it manually.
264 uint64_t Val = Data[B] - '0';
265 for (size_t i = B + 1; i < E; i++)
266 Val = Val * 10 + Data[i] - '0';
267
268 // Mutate the integer value.
269 switch(Rand(5)) {
270 case 0: Val++; break;
271 case 1: Val--; break;
272 case 2: Val /= 2; break;
273 case 3: Val *= 2; break;
274 case 4: Val = Rand(Val * Val); break;
275 default: assert(0);
276 }
277 // Just replace the bytes with the new ones, don't bother moving bytes.
278 for (size_t i = B; i < E; i++) {
279 size_t Idx = E + B - i - 1;
280 assert(Idx >= B && Idx < E);
281 Data[Idx] = (Val % 10) + '0';
282 Val /= 10;
283 }
284 return Size;
285}
286
Kostya Serebryany0c537b12016-08-17 21:30:30 +0000287uint8_t Bswap(uint8_t x) { return x; }
288uint16_t Bswap(uint16_t x) { return __builtin_bswap16(x); }
289uint32_t Bswap(uint32_t x) { return __builtin_bswap32(x); }
290uint64_t Bswap(uint64_t x) { return __builtin_bswap64(x); }
291
292template<class T>
293size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) {
294 if (Size < sizeof(T)) return 0;
295 size_t Off = Rand(Size - sizeof(T) + 1);
296 assert(Off + sizeof(T) <= Size);
297 T Val;
298 memcpy(&Val, Data + Off, sizeof(Val));
299 T Add = Rand(21);
300 Add -= 10;
301 if (Rand.RandBool())
302 Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes.
303 else
304 Val = Val + Add; // Add assuming current endiannes.
305 if (Add == 0 || Rand.RandBool()) // Maybe negate.
306 Val = -Val;
307 memcpy(Data + Off, &Val, sizeof(Val));
308 return Size;
309}
310
311size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data,
312 size_t Size,
313 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000314 if (Size > MaxSize) return 0;
Kostya Serebryany0c537b12016-08-17 21:30:30 +0000315 switch (Rand(4)) {
316 case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand);
317 case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand);
318 case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand);
319 case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand);
320 default: assert(0);
321 }
Kostya Serebryanya533e512016-08-19 20:57:09 +0000322 return 0;
Kostya Serebryany0c537b12016-08-17 21:30:30 +0000323}
324
Kostya Serebryany27ab2d72015-12-19 02:49:09 +0000325size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
326 size_t MaxSize) {
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000327 if (Size > MaxSize) return 0;
Kostya Serebryany27ab2d72015-12-19 02:49:09 +0000328 if (!Corpus || Corpus->size() < 2 || Size == 0) return 0;
329 size_t Idx = Rand(Corpus->size());
Kostya Serebryanya7398ba2016-08-17 18:10:42 +0000330 const Unit &O = (*Corpus)[Idx];
331 if (O.empty()) return 0;
Kostya Serebryany8a5bef02016-02-13 17:56:51 +0000332 MutateInPlaceHere.resize(MaxSize);
333 auto &U = MutateInPlaceHere;
Kostya Serebryanya533e512016-08-19 20:57:09 +0000334 size_t NewSize = 0;
Kostya Serebryanya7398ba2016-08-17 18:10:42 +0000335 switch(Rand(3)) {
336 case 0:
337 NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size());
338 break;
339 case 1:
340 NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize);
341 if (NewSize)
342 break;
Kostya Serebryany0c537b12016-08-17 21:30:30 +0000343 // LLVM_FALLTHROUGH;
Kostya Serebryanya7398ba2016-08-17 18:10:42 +0000344 case 2:
345 NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size());
346 break;
347 default: assert(0);
348 }
Kostya Serebryany27ab2d72015-12-19 02:49:09 +0000349 assert(NewSize > 0 && "CrossOver returned empty unit");
350 assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
351 memcpy(Data, U.data(), NewSize);
352 return NewSize;
353}
354
Kostya Serebryany14c50282015-12-19 01:09:49 +0000355void MutationDispatcher::StartMutationSequence() {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000356 CurrentMutatorSequence.clear();
357 CurrentDictionaryEntrySequence.clear();
Kostya Serebryany14c50282015-12-19 01:09:49 +0000358}
359
Kostya Serebryany4b358742016-01-14 02:36:44 +0000360// Copy successful dictionary entries to PersistentAutoDictionary.
361void MutationDispatcher::RecordSuccessfulMutationSequence() {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000362 for (auto DE : CurrentDictionaryEntrySequence) {
363 // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000364 DE->IncSuccessCount();
Kostya Serebryany4b358742016-01-14 02:36:44 +0000365 // Linear search is fine here as this happens seldom.
Kostya Serebryany292cf032016-02-13 03:37:24 +0000366 if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
367 PersistentAutoDictionary.push_back({DE->GetW(), 1});
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000368 }
Kostya Serebryany4b358742016-01-14 02:36:44 +0000369}
370
371void MutationDispatcher::PrintRecommendedDictionary() {
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000372 std::vector<DictionaryEntry> V;
Kostya Serebryany292cf032016-02-13 03:37:24 +0000373 for (auto &DE : PersistentAutoDictionary)
374 if (!ManualDictionary.ContainsWord(DE.GetW()))
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000375 V.push_back(DE);
Kostya Serebryany4b358742016-01-14 02:36:44 +0000376 if (V.empty()) return;
377 Printf("###### Recommended dictionary. ######\n");
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000378 for (auto &DE: V) {
Kostya Serebryany4b358742016-01-14 02:36:44 +0000379 Printf("\"");
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000380 PrintASCII(DE.GetW(), "\"");
381 Printf(" # Uses: %zd\n", DE.GetUseCount());
Kostya Serebryany4b358742016-01-14 02:36:44 +0000382 }
383 Printf("###### End of recommended dictionary. ######\n");
384}
385
Kostya Serebryany14c50282015-12-19 01:09:49 +0000386void MutationDispatcher::PrintMutationSequence() {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000387 Printf("MS: %zd ", CurrentMutatorSequence.size());
388 for (auto M : CurrentMutatorSequence)
Kostya Serebryany14c50282015-12-19 01:09:49 +0000389 Printf("%s-", M.Name);
Kostya Serebryany292cf032016-02-13 03:37:24 +0000390 if (!CurrentDictionaryEntrySequence.empty()) {
Kostya Serebryany41740052016-01-12 02:36:59 +0000391 Printf(" DE: ");
Kostya Serebryany292cf032016-02-13 03:37:24 +0000392 for (auto DE : CurrentDictionaryEntrySequence) {
Kostya Serebryany41740052016-01-12 02:36:59 +0000393 Printf("\"");
Kostya Serebryany160dcba2016-01-22 23:55:14 +0000394 PrintASCII(DE->GetW(), "\"-");
Kostya Serebryany41740052016-01-12 02:36:59 +0000395 }
396 }
Kostya Serebryany14c50282015-12-19 01:09:49 +0000397}
398
Kostya Serebryanyec2dcb12015-09-03 21:24:19 +0000399size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
Mike Aizatsky70fd3e42016-06-03 21:34:29 +0000400 return MutateImpl(Data, Size, MaxSize, Mutators);
401}
402
403size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
404 size_t MaxSize) {
405 return MutateImpl(Data, Size, MaxSize, DefaultMutators);
406}
407
408// Mutates Data in place, returns new size.
409size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
410 size_t MaxSize,
411 const std::vector<Mutator> &Mutators) {
Kostya Serebryanyf3424592015-05-22 22:35:31 +0000412 assert(MaxSize > 0);
Kostya Serebryanyf3424592015-05-22 22:35:31 +0000413 if (Size == 0) {
414 for (size_t i = 0; i < MaxSize; i++)
Kostya Serebryany404c69f2015-07-24 01:06:40 +0000415 Data[i] = RandCh(Rand);
Mike Aizatskyf0b3e852016-06-23 20:44:48 +0000416 if (Options.OnlyASCII)
417 ToASCII(Data, MaxSize);
Kostya Serebryanyf3424592015-05-22 22:35:31 +0000418 return MaxSize;
Kostya Serebryany5b266a82015-02-04 19:10:20 +0000419 }
Kostya Serebryanyf3424592015-05-22 22:35:31 +0000420 assert(Size > 0);
Kostya Serebryanyb2e98972015-09-04 00:40:29 +0000421 // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
422 // in which case they will return 0.
423 // Try several times before returning un-mutated data.
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000424 for (int Iter = 0; Iter < 100; Iter++) {
Mike Aizatsky70fd3e42016-06-03 21:34:29 +0000425 auto M = Mutators[Rand(Mutators.size())];
Kostya Serebryany14c50282015-12-19 01:09:49 +0000426 size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000427 if (NewSize && NewSize <= MaxSize) {
Mike Aizatskyf0b3e852016-06-23 20:44:48 +0000428 if (Options.OnlyASCII)
429 ToASCII(Data, NewSize);
Kostya Serebryany292cf032016-02-13 03:37:24 +0000430 CurrentMutatorSequence.push_back(M);
Kostya Serebryany14c50282015-12-19 01:09:49 +0000431 return NewSize;
432 }
Kostya Serebryanyb2e98972015-09-04 00:40:29 +0000433 }
Kostya Serebryany624f59f2016-09-22 01:34:58 +0000434 return std::min(Size, MaxSize);
Aaron Ballmanef116982015-01-29 16:58:29 +0000435}
436
Kostya Serebryany476f0ce2016-01-16 03:53:32 +0000437void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000438 ManualDictionary.push_back(
Kostya Serebryany476f0ce2016-01-16 03:53:32 +0000439 {W, std::numeric_limits<size_t>::max()});
Kostya Serebryany152ac7a2016-01-07 01:49:35 +0000440}
441
Kostya Serebryanyc135b552016-07-15 23:27:19 +0000442void MutationDispatcher::AddWordToAutoDictionary(DictionaryEntry DE) {
Kostya Serebryanyb65805a2016-01-09 03:08:58 +0000443 static const size_t kMaxAutoDictSize = 1 << 14;
Kostya Serebryany292cf032016-02-13 03:37:24 +0000444 if (TempAutoDictionary.size() >= kMaxAutoDictSize) return;
Kostya Serebryanyc135b552016-07-15 23:27:19 +0000445 TempAutoDictionary.push_back(DE);
Kostya Serebryany7d211662015-09-04 00:12:11 +0000446}
447
Kostya Serebryanyb65805a2016-01-09 03:08:58 +0000448void MutationDispatcher::ClearAutoDictionary() {
Kostya Serebryany292cf032016-02-13 03:37:24 +0000449 TempAutoDictionary.clear();
Kostya Serebryanyb65805a2016-01-09 03:08:58 +0000450}
451
Aaron Ballmanef116982015-01-29 16:58:29 +0000452} // namespace fuzzer