1 //===- 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
12 #include <cstring>
13
14 #include "FuzzerInternal.h"
15
16
17 namespace fuzzer {
18
19 const size_t Dictionary::kMaxDictSize;
20
MutationDispatcher(Random & Rand,const FuzzingOptions & Options)21 MutationDispatcher::MutationDispatcher(Random &Rand,
22 const FuzzingOptions &Options)
23 : Rand(Rand), Options(Options) {
24 DefaultMutators.insert(
25 DefaultMutators.begin(),
26 {
27 {&MutationDispatcher::Mutate_EraseByte, "EraseByte"},
28 {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
29 {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
30 {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
31 {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
32 {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
33 {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
34 {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
35 "AddFromManualDict"},
36 {&MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary,
37 "AddFromTempAutoDict"},
38 {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
39 "AddFromPersAutoDict"},
40 });
41
42 if (EF->LLVMFuzzerCustomMutator)
43 Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
44 else
45 Mutators = DefaultMutators;
46
47 if (EF->LLVMFuzzerCustomCrossOver)
48 Mutators.push_back(
49 {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
50 }
51
FlipRandomBit(char X,Random & Rand)52 static char FlipRandomBit(char X, Random &Rand) {
53 int Bit = Rand(8);
54 char Mask = 1 << Bit;
55 char R;
56 if (X & (1 << Bit))
57 R = X & ~Mask;
58 else
59 R = X | Mask;
60 assert(R != X);
61 return R;
62 }
63
RandCh(Random & Rand)64 static char RandCh(Random &Rand) {
65 if (Rand.RandBool()) return Rand(256);
66 const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~.";
67 return Special[Rand(sizeof(Special) - 1)];
68 }
69
Mutate_Custom(uint8_t * Data,size_t Size,size_t MaxSize)70 size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size,
71 size_t MaxSize) {
72 return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, Rand.Rand());
73 }
74
Mutate_CustomCrossOver(uint8_t * Data,size_t Size,size_t MaxSize)75 size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size,
76 size_t MaxSize) {
77 if (!Corpus || Corpus->size() < 2 || Size == 0)
78 return 0;
79 size_t Idx = Rand(Corpus->size());
80 const Unit &Other = (*Corpus)[Idx];
81 if (Other.empty())
82 return 0;
83 MutateInPlaceHere.resize(MaxSize);
84 auto &U = MutateInPlaceHere;
85 size_t NewSize = EF->LLVMFuzzerCustomCrossOver(
86 Data, Size, Other.data(), Other.size(), U.data(), U.size(), Rand.Rand());
87 if (!NewSize)
88 return 0;
89 assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit");
90 memcpy(Data, U.data(), NewSize);
91 return NewSize;
92 }
93
Mutate_ShuffleBytes(uint8_t * Data,size_t Size,size_t MaxSize)94 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
95 size_t MaxSize) {
96 assert(Size);
97 size_t ShuffleAmount =
98 Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
99 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
Mutate_EraseByte(uint8_t * Data,size_t Size,size_t MaxSize)106 size_t MutationDispatcher::Mutate_EraseByte(uint8_t *Data, size_t Size,
107 size_t MaxSize) {
108 assert(Size);
109 if (Size == 1) return 0;
110 size_t Idx = Rand(Size);
111 // Erase Data[Idx].
112 memmove(Data + Idx, Data + Idx + 1, Size - Idx - 1);
113 return Size - 1;
114 }
115
Mutate_InsertByte(uint8_t * Data,size_t Size,size_t MaxSize)116 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
117 size_t MaxSize) {
118 if (Size == MaxSize) return 0;
119 size_t Idx = Rand(Size + 1);
120 // Insert new value at Data[Idx].
121 memmove(Data + Idx + 1, Data + Idx, Size - Idx);
122 Data[Idx] = RandCh(Rand);
123 return Size + 1;
124 }
125
Mutate_ChangeByte(uint8_t * Data,size_t Size,size_t MaxSize)126 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
127 size_t MaxSize) {
128 size_t Idx = Rand(Size);
129 Data[Idx] = RandCh(Rand);
130 return Size;
131 }
132
Mutate_ChangeBit(uint8_t * Data,size_t Size,size_t MaxSize)133 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
134 size_t MaxSize) {
135 size_t Idx = Rand(Size);
136 Data[Idx] = FlipRandomBit(Data[Idx], Rand);
137 return Size;
138 }
139
Mutate_AddWordFromManualDictionary(uint8_t * Data,size_t Size,size_t MaxSize)140 size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
141 size_t Size,
142 size_t MaxSize) {
143 return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
144 }
145
Mutate_AddWordFromTemporaryAutoDictionary(uint8_t * Data,size_t Size,size_t MaxSize)146 size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary(
147 uint8_t *Data, size_t Size, size_t MaxSize) {
148 return AddWordFromDictionary(TempAutoDictionary, Data, Size, MaxSize);
149 }
150
Mutate_AddWordFromPersistentAutoDictionary(uint8_t * Data,size_t Size,size_t MaxSize)151 size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
152 uint8_t *Data, size_t Size, size_t MaxSize) {
153 return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
154 }
155
AddWordFromDictionary(Dictionary & D,uint8_t * Data,size_t Size,size_t MaxSize)156 size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
157 size_t Size, size_t MaxSize) {
158 if (D.empty()) return 0;
159 DictionaryEntry &DE = D[Rand(D.size())];
160 const Word &W = DE.GetW();
161 bool UsePositionHint = DE.HasPositionHint() &&
162 DE.GetPositionHint() + W.size() < Size && Rand.RandBool();
163 if (Rand.RandBool()) { // Insert W.
164 if (Size + W.size() > MaxSize) return 0;
165 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
166 memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
167 memcpy(Data + Idx, W.data(), W.size());
168 Size += W.size();
169 } else { // Overwrite some bytes with W.
170 if (W.size() > Size) return 0;
171 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size());
172 memcpy(Data + Idx, W.data(), W.size());
173 }
174 DE.IncUseCount();
175 CurrentDictionaryEntrySequence.push_back(&DE);
176 return Size;
177 }
178
Mutate_ChangeASCIIInteger(uint8_t * Data,size_t Size,size_t MaxSize)179 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
180 size_t MaxSize) {
181 size_t B = Rand(Size);
182 while (B < Size && !isdigit(Data[B])) B++;
183 if (B == Size) return 0;
184 size_t E = B;
185 while (E < Size && isdigit(Data[E])) E++;
186 assert(B < E);
187 // now we have digits in [B, E).
188 // strtol and friends don't accept non-zero-teminated data, parse it manually.
189 uint64_t Val = Data[B] - '0';
190 for (size_t i = B + 1; i < E; i++)
191 Val = Val * 10 + Data[i] - '0';
192
193 // Mutate the integer value.
194 switch(Rand(5)) {
195 case 0: Val++; break;
196 case 1: Val--; break;
197 case 2: Val /= 2; break;
198 case 3: Val *= 2; break;
199 case 4: Val = Rand(Val * Val); break;
200 default: assert(0);
201 }
202 // Just replace the bytes with the new ones, don't bother moving bytes.
203 for (size_t i = B; i < E; i++) {
204 size_t Idx = E + B - i - 1;
205 assert(Idx >= B && Idx < E);
206 Data[Idx] = (Val % 10) + '0';
207 Val /= 10;
208 }
209 return Size;
210 }
211
Mutate_CrossOver(uint8_t * Data,size_t Size,size_t MaxSize)212 size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
213 size_t MaxSize) {
214 if (!Corpus || Corpus->size() < 2 || Size == 0) return 0;
215 size_t Idx = Rand(Corpus->size());
216 const Unit &Other = (*Corpus)[Idx];
217 if (Other.empty()) return 0;
218 MutateInPlaceHere.resize(MaxSize);
219 auto &U = MutateInPlaceHere;
220 size_t NewSize =
221 CrossOver(Data, Size, Other.data(), Other.size(), U.data(), U.size());
222 assert(NewSize > 0 && "CrossOver returned empty unit");
223 assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
224 memcpy(Data, U.data(), NewSize);
225 return NewSize;
226 }
227
StartMutationSequence()228 void MutationDispatcher::StartMutationSequence() {
229 CurrentMutatorSequence.clear();
230 CurrentDictionaryEntrySequence.clear();
231 }
232
233 // Copy successful dictionary entries to PersistentAutoDictionary.
RecordSuccessfulMutationSequence()234 void MutationDispatcher::RecordSuccessfulMutationSequence() {
235 for (auto DE : CurrentDictionaryEntrySequence) {
236 // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
237 DE->IncSuccessCount();
238 // Linear search is fine here as this happens seldom.
239 if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
240 PersistentAutoDictionary.push_back({DE->GetW(), 1});
241 }
242 }
243
PrintRecommendedDictionary()244 void MutationDispatcher::PrintRecommendedDictionary() {
245 std::vector<DictionaryEntry> V;
246 for (auto &DE : PersistentAutoDictionary)
247 if (!ManualDictionary.ContainsWord(DE.GetW()))
248 V.push_back(DE);
249 if (V.empty()) return;
250 Printf("###### Recommended dictionary. ######\n");
251 for (auto &DE: V) {
252 Printf("\"");
253 PrintASCII(DE.GetW(), "\"");
254 Printf(" # Uses: %zd\n", DE.GetUseCount());
255 }
256 Printf("###### End of recommended dictionary. ######\n");
257 }
258
PrintMutationSequence()259 void MutationDispatcher::PrintMutationSequence() {
260 Printf("MS: %zd ", CurrentMutatorSequence.size());
261 for (auto M : CurrentMutatorSequence)
262 Printf("%s-", M.Name);
263 if (!CurrentDictionaryEntrySequence.empty()) {
264 Printf(" DE: ");
265 for (auto DE : CurrentDictionaryEntrySequence) {
266 Printf("\"");
267 PrintASCII(DE->GetW(), "\"-");
268 }
269 }
270 }
271
Mutate(uint8_t * Data,size_t Size,size_t MaxSize)272 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
273 return MutateImpl(Data, Size, MaxSize, Mutators);
274 }
275
DefaultMutate(uint8_t * Data,size_t Size,size_t MaxSize)276 size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
277 size_t MaxSize) {
278 return MutateImpl(Data, Size, MaxSize, DefaultMutators);
279 }
280
281 // Mutates Data in place, returns new size.
MutateImpl(uint8_t * Data,size_t Size,size_t MaxSize,const std::vector<Mutator> & Mutators)282 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
283 size_t MaxSize,
284 const std::vector<Mutator> &Mutators) {
285 assert(MaxSize > 0);
286 assert(Size <= MaxSize);
287 if (Size == 0) {
288 for (size_t i = 0; i < MaxSize; i++)
289 Data[i] = RandCh(Rand);
290 if (Options.OnlyASCII)
291 ToASCII(Data, MaxSize);
292 return MaxSize;
293 }
294 assert(Size > 0);
295 // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
296 // in which case they will return 0.
297 // Try several times before returning un-mutated data.
298 for (int Iter = 0; Iter < 10; Iter++) {
299 auto M = Mutators[Rand(Mutators.size())];
300 size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
301 if (NewSize) {
302 if (Options.OnlyASCII)
303 ToASCII(Data, NewSize);
304 CurrentMutatorSequence.push_back(M);
305 return NewSize;
306 }
307 }
308 return Size;
309 }
310
AddWordToManualDictionary(const Word & W)311 void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
312 ManualDictionary.push_back(
313 {W, std::numeric_limits<size_t>::max()});
314 }
315
AddWordToAutoDictionary(const Word & W,size_t PositionHint)316 void MutationDispatcher::AddWordToAutoDictionary(const Word &W,
317 size_t PositionHint) {
318 static const size_t kMaxAutoDictSize = 1 << 14;
319 if (TempAutoDictionary.size() >= kMaxAutoDictSize) return;
320 TempAutoDictionary.push_back({W, PositionHint});
321 }
322
ClearAutoDictionary()323 void MutationDispatcher::ClearAutoDictionary() {
324 TempAutoDictionary.clear();
325 }
326
327 } // namespace fuzzer
328