| 1 |
//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===// |
| 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 |
// Mutate a test input. |
| 9 |
//===----------------------------------------------------------------------===// |
| 10 |
|
| 11 |
#include "FuzzerDefs.h" |
| 12 |
#include "FuzzerExtFunctions.h" |
| 13 |
#include "FuzzerIO.h" |
| 14 |
#include "FuzzerMutate.h" |
| 15 |
#include "FuzzerOptions.h" |
| 16 |
#include "FuzzerTracePC.h" |
| 17 |
|
| 18 |
namespace fuzzer { |
| 19 |
|
| 20 |
const size_t Dictionary::kMaxDictSize; |
| 21 |
static const size_t kMaxMutationsToPrint = 10; |
| 22 |
|
| 23 |
static void PrintASCII(const Word &W, const char *PrintAfter) { |
| 24 |
PrintASCII(W.data(), W.size(), PrintAfter); |
| 25 |
} |
| 26 |
|
| 27 |
MutationDispatcher::MutationDispatcher(Random &Rand, |
| 28 |
const FuzzingOptions &Options) |
| 29 |
: Rand(Rand), Options(Options) { |
| 30 |
DefaultMutators.insert( |
| 31 |
DefaultMutators.begin(), |
| 32 |
{ |
| 33 |
{&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, |
| 34 |
{&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, |
| 35 |
{&MutationDispatcher::Mutate_InsertRepeatedBytes, |
| 36 |
"InsertRepeatedBytes"}, |
| 37 |
{&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, |
| 38 |
{&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, |
| 39 |
{&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, |
| 40 |
{&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, |
| 41 |
{&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, |
| 42 |
{&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, |
| 43 |
{&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, |
| 44 |
{&MutationDispatcher::Mutate_AddWordFromManualDictionary, |
| 45 |
"ManualDict"}, |
| 46 |
{&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, |
| 47 |
"PersAutoDict"}, |
| 48 |
}); |
| 49 |
if(Options.UseCmp) |
| 50 |
DefaultMutators.push_back( |
| 51 |
{&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"}); |
| 52 |
|
| 53 |
if (EF->LLVMFuzzerCustomMutator) |
| 54 |
Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); |
| 55 |
else |
| 56 |
Mutators = DefaultMutators; |
| 57 |
|
| 58 |
if (EF->LLVMFuzzerCustomCrossOver) |
| 59 |
Mutators.push_back( |
| 60 |
{&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); |
| 61 |
} |
| 62 |
|
| 63 |
static char RandCh(Random &Rand) { |
| 64 |
if (Rand.RandBool()) |
| 65 |
return static_cast<char>(Rand(256)); |
| 66 |
const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; |
| 67 |
return Special[Rand(sizeof(Special) - 1)]; |
| 68 |
} |
| 69 |
|
| 70 |
size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, |
| 71 |
size_t MaxSize) { |
| 72 |
if (EF->__msan_unpoison) |
| 73 |
EF->__msan_unpoison(Data, Size); |
| 74 |
if (EF->__msan_unpoison_param) |
| 75 |
EF->__msan_unpoison_param(4); |
| 76 |
return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, |
| 77 |
Rand.Rand<unsigned int>()); |
| 78 |
} |
| 79 |
|
| 80 |
size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, |
| 81 |
size_t MaxSize) { |
| 82 |
if (Size == 0) |
| 83 |
return 0; |
| 84 |
if (!CrossOverWith) return 0; |
| 85 |
const Unit &Other = *CrossOverWith; |
| 86 |
if (Other.empty()) |
| 87 |
return 0; |
| 88 |
CustomCrossOverInPlaceHere.resize(MaxSize); |
| 89 |
auto &U = CustomCrossOverInPlaceHere; |
| 90 |
|
| 91 |
if (EF->__msan_unpoison) { |
| 92 |
EF->__msan_unpoison(Data, Size); |
| 93 |
EF->__msan_unpoison(Other.data(), Other.size()); |
| 94 |
EF->__msan_unpoison(U.data(), U.size()); |
| 95 |
} |
| 96 |
if (EF->__msan_unpoison_param) |
| 97 |
EF->__msan_unpoison_param(7); |
| 98 |
size_t NewSize = EF->LLVMFuzzerCustomCrossOver( |
| 99 |
Data, Size, Other.data(), Other.size(), U.data(), U.size(), |
| 100 |
Rand.Rand<unsigned int>()); |
| 101 |
|
| 102 |
if (!NewSize) |
| 103 |
return 0; |
| 104 |
assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); |
| 105 |
memcpy(Data, U.data(), NewSize); |
| 106 |
return NewSize; |
| 107 |
} |
| 108 |
|
| 109 |
size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, |
| 110 |
size_t MaxSize) { |
| 111 |
if (Size > MaxSize || Size == 0) return 0; |
| 112 |
size_t ShuffleAmount = |
| 113 |
Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. |
| 114 |
size_t ShuffleStart = Rand(Size - ShuffleAmount); |
| 115 |
assert(ShuffleStart + ShuffleAmount <= Size); |
| 116 |
std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); |
| 117 |
return Size; |
| 118 |
} |
| 119 |
|
| 120 |
size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, |
| 121 |
size_t MaxSize) { |
| 122 |
if (Size <= 1) return 0; |
| 123 |
size_t N = Rand(Size / 2) + 1; |
| 124 |
assert(N < Size); |
| 125 |
size_t Idx = Rand(Size - N + 1); |
| 126 |
// Erase Data[Idx:Idx+N]. |
| 127 |
memmove(Data + Idx, Data + Idx + N, Size - Idx - N); |
| 128 |
// Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); |
| 129 |
return Size - N; |
| 130 |
} |
| 131 |
|
| 132 |
size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, |
| 133 |
size_t MaxSize) { |
| 134 |
if (Size >= MaxSize) return 0; |
| 135 |
size_t Idx = Rand(Size + 1); |
| 136 |
// Insert new value at Data[Idx]. |
| 137 |
memmove(Data + Idx + 1, Data + Idx, Size - Idx); |
| 138 |
Data[Idx] = RandCh(Rand); |
| 139 |
return Size + 1; |
| 140 |
} |
| 141 |
|
| 142 |
size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, |
| 143 |
size_t Size, |
| 144 |
size_t MaxSize) { |
| 145 |
const size_t kMinBytesToInsert = 3; |
| 146 |
if (Size + kMinBytesToInsert >= MaxSize) return 0; |
| 147 |
size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); |
| 148 |
size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; |
| 149 |
assert(Size + N <= MaxSize && N); |
| 150 |
size_t Idx = Rand(Size + 1); |
| 151 |
// Insert new values at Data[Idx]. |
| 152 |
memmove(Data + Idx + N, Data + Idx, Size - Idx); |
| 153 |
// Give preference to 0x00 and 0xff. |
| 154 |
uint8_t Byte = static_cast<uint8_t>( |
| 155 |
Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255)); |
| 156 |
for (size_t i = 0; i < N; i++) |
| 157 |
Data[Idx + i] = Byte; |
| 158 |
return Size + N; |
| 159 |
} |
| 160 |
|
| 161 |
size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, |
| 162 |
size_t MaxSize) { |
| 163 |
if (Size > MaxSize) return 0; |
| 164 |
size_t Idx = Rand(Size); |
| 165 |
Data[Idx] = RandCh(Rand); |
| 166 |
return Size; |
| 167 |
} |
| 168 |
|
| 169 |
size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, |
| 170 |
size_t MaxSize) { |
| 171 |
if (Size > MaxSize) return 0; |
| 172 |
size_t Idx = Rand(Size); |
| 173 |
Data[Idx] ^= 1 << Rand(8); |
| 174 |
return Size; |
| 175 |
} |
| 176 |
|
| 177 |
size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, |
| 178 |
size_t Size, |
| 179 |
size_t MaxSize) { |
| 180 |
return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); |
| 181 |
} |
| 182 |
|
| 183 |
size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, |
| 184 |
size_t MaxSize, |
| 185 |
DictionaryEntry &DE) { |
| 186 |
const Word &W = DE.GetW(); |
| 187 |
bool UsePositionHint = DE.HasPositionHint() && |
| 188 |
DE.GetPositionHint() + W.size() < Size && |
| 189 |
Rand.RandBool(); |
| 190 |
if (Rand.RandBool()) { // Insert W. |
| 191 |
if (Size + W.size() > MaxSize) return 0; |
| 192 |
size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); |
| 193 |
memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); |
| 194 |
memcpy(Data + Idx, W.data(), W.size()); |
| 195 |
Size += W.size(); |
| 196 |
} else { // Overwrite some bytes with W. |
| 197 |
if (W.size() > Size) return 0; |
| 198 |
size_t Idx = |
| 199 |
UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size()); |
| 200 |
memcpy(Data + Idx, W.data(), W.size()); |
| 201 |
} |
| 202 |
return Size; |
| 203 |
} |
| 204 |
|
| 205 |
// Somewhere in the past we have observed a comparison instructions |
| 206 |
// with arguments Arg1 Arg2. This function tries to guess a dictionary |
| 207 |
// entry that will satisfy that comparison. |
| 208 |
// It first tries to find one of the arguments (possibly swapped) in the |
| 209 |
// input and if it succeeds it creates a DE with a position hint. |
| 210 |
// Otherwise it creates a DE with one of the arguments w/o a position hint. |
| 211 |
DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( |
| 212 |
const void *Arg1, const void *Arg2, |
| 213 |
const void *Arg1Mutation, const void *Arg2Mutation, |
| 214 |
size_t ArgSize, const uint8_t *Data, |
| 215 |
size_t Size) { |
| 216 |
bool HandleFirst = Rand.RandBool(); |
| 217 |
const void *ExistingBytes, *DesiredBytes; |
| 218 |
Word W; |
| 219 |
const uint8_t *End = Data + Size; |
| 220 |
for (int Arg = 0; Arg < 2; Arg++) { |
| 221 |
ExistingBytes = HandleFirst ? Arg1 : Arg2; |
| 222 |
DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; |
| 223 |
HandleFirst = !HandleFirst; |
| 224 |
W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize); |
| 225 |
const size_t kMaxNumPositions = 8; |
| 226 |
size_t Positions[kMaxNumPositions]; |
| 227 |
size_t NumPositions = 0; |
| 228 |
for (const uint8_t *Cur = Data; |
| 229 |
Cur < End && NumPositions < kMaxNumPositions; Cur++) { |
| 230 |
Cur = |
| 231 |
(const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); |
| 232 |
if (!Cur) break; |
| 233 |
Positions[NumPositions++] = Cur - Data; |
| 234 |
} |
| 235 |
if (!NumPositions) continue; |
| 236 |
return DictionaryEntry(W, Positions[Rand(NumPositions)]); |
| 237 |
} |
| 238 |
DictionaryEntry DE(W); |
| 239 |
return DE; |
| 240 |
} |
| 241 |
|
| 242 |
|
| 243 |
template <class T> |
| 244 |
DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( |
| 245 |
T Arg1, T Arg2, const uint8_t *Data, size_t Size) { |
| 246 |
if (Rand.RandBool()) Arg1 = Bswap(Arg1); |
| 247 |
if (Rand.RandBool()) Arg2 = Bswap(Arg2); |
| 248 |
T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1)); |
| 249 |
T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1)); |
| 250 |
return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, |
| 251 |
sizeof(Arg1), Data, Size); |
| 252 |
} |
| 253 |
|
| 254 |
DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( |
| 255 |
const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { |
| 256 |
return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), |
| 257 |
Arg2.data(), Arg1.size(), Data, Size); |
| 258 |
} |
| 259 |
|
| 260 |
size_t MutationDispatcher::Mutate_AddWordFromTORC( |
| 261 |
uint8_t *Data, size_t Size, size_t MaxSize) { |
| 262 |
Word W; |
| 263 |
DictionaryEntry DE; |
| 264 |
switch (Rand(4)) { |
| 265 |
case 0: { |
| 266 |
auto X = TPC.TORC8.Get(Rand.Rand<size_t>()); |
| 267 |
DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); |
| 268 |
} break; |
| 269 |
case 1: { |
| 270 |
auto X = TPC.TORC4.Get(Rand.Rand<size_t>()); |
| 271 |
if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) |
| 272 |
DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); |
| 273 |
else |
| 274 |
DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); |
| 275 |
} break; |
| 276 |
case 2: { |
| 277 |
auto X = TPC.TORCW.Get(Rand.Rand<size_t>()); |
| 278 |
DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); |
| 279 |
} break; |
| 280 |
case 3: if (Options.UseMemmem) { |
| 281 |
auto X = TPC.MMT.Get(Rand.Rand<size_t>()); |
| 282 |
DE = DictionaryEntry(X); |
| 283 |
} break; |
| 284 |
default: |
| 285 |
assert(0); |
| 286 |
} |
| 287 |
if (!DE.GetW().size()) return 0; |
| 288 |
Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); |
| 289 |
if (!Size) return 0; |
| 290 |
DictionaryEntry &DERef = |
| 291 |
CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % |
| 292 |
kCmpDictionaryEntriesDequeSize]; |
| 293 |
DERef = DE; |
| 294 |
CurrentDictionaryEntrySequence.push_back(&DERef); |
| 295 |
return Size; |
| 296 |
} |
| 297 |
|
| 298 |
size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( |
| 299 |
uint8_t *Data, size_t Size, size_t MaxSize) { |
| 300 |
return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); |
| 301 |
} |
| 302 |
|
| 303 |
size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, |
| 304 |
size_t Size, size_t MaxSize) { |
| 305 |
if (Size > MaxSize) return 0; |
| 306 |
if (D.empty()) return 0; |
| 307 |
DictionaryEntry &DE = D[Rand(D.size())]; |
| 308 |
Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); |
| 309 |
if (!Size) return 0; |
| 310 |
DE.IncUseCount(); |
| 311 |
CurrentDictionaryEntrySequence.push_back(&DE); |
| 312 |
return Size; |
| 313 |
} |
| 314 |
|
| 315 |
// Overwrites part of To[0,ToSize) with a part of From[0,FromSize). |
| 316 |
// Returns ToSize. |
| 317 |
size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, |
| 318 |
uint8_t *To, size_t ToSize) { |
| 319 |
// Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). |
| 320 |
size_t ToBeg = Rand(ToSize); |
| 321 |
size_t CopySize = Rand(ToSize - ToBeg) + 1; |
| 322 |
assert(ToBeg + CopySize <= ToSize); |
| 323 |
CopySize = std::min(CopySize, FromSize); |
| 324 |
size_t FromBeg = Rand(FromSize - CopySize + 1); |
| 325 |
assert(FromBeg + CopySize <= FromSize); |
| 326 |
memmove(To + ToBeg, From + FromBeg, CopySize); |
| 327 |
return ToSize; |
| 328 |
} |
| 329 |
|
| 330 |
// Inserts part of From[0,ToSize) into To. |
| 331 |
// Returns new size of To on success or 0 on failure. |
| 332 |
size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, |
| 333 |
uint8_t *To, size_t ToSize, |
| 334 |
size_t MaxToSize) { |
| 335 |
if (ToSize >= MaxToSize) return 0; |
| 336 |
size_t AvailableSpace = MaxToSize - ToSize; |
| 337 |
size_t MaxCopySize = std::min(AvailableSpace, FromSize); |
| 338 |
size_t CopySize = Rand(MaxCopySize) + 1; |
| 339 |
size_t FromBeg = Rand(FromSize - CopySize + 1); |
| 340 |
assert(FromBeg + CopySize <= FromSize); |
| 341 |
size_t ToInsertPos = Rand(ToSize + 1); |
| 342 |
assert(ToInsertPos + CopySize <= MaxToSize); |
| 343 |
size_t TailSize = ToSize - ToInsertPos; |
| 344 |
if (To == From) { |
| 345 |
MutateInPlaceHere.resize(MaxToSize); |
| 346 |
memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); |
| 347 |
memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); |
| 348 |
memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); |
| 349 |
} else { |
| 350 |
memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); |
| 351 |
memmove(To + ToInsertPos, From + FromBeg, CopySize); |
| 352 |
} |
| 353 |
return ToSize + CopySize; |
| 354 |
} |
| 355 |
|
| 356 |
size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, |
| 357 |
size_t MaxSize) { |
| 358 |
if (Size > MaxSize || Size == 0) return 0; |
| 359 |
// If Size == MaxSize, `InsertPartOf(...)` will |
| 360 |
// fail so there's no point using it in this case. |
| 361 |
if (Size == MaxSize || Rand.RandBool()) |
| 362 |
return CopyPartOf(Data, Size, Data, Size); |
| 363 |
else |
| 364 |
return InsertPartOf(Data, Size, Data, Size, MaxSize); |
| 365 |
} |
| 366 |
|
| 367 |
size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, |
| 368 |
size_t MaxSize) { |
| 369 |
if (Size > MaxSize) return 0; |
| 370 |
size_t B = Rand(Size); |
| 371 |
while (B < Size && !isdigit(Data[B])) B++; |
| 372 |
if (B == Size) return 0; |
| 373 |
size_t E = B; |
| 374 |
while (E < Size && isdigit(Data[E])) E++; |
| 375 |
assert(B < E); |
| 376 |
// now we have digits in [B, E). |
| 377 |
// strtol and friends don't accept non-zero-teminated data, parse it manually. |
| 378 |
uint64_t Val = Data[B] - '0'; |
| 379 |
for (size_t i = B + 1; i < E; i++) |
| 380 |
Val = Val * 10 + Data[i] - '0'; |
| 381 |
|
| 382 |
// Mutate the integer value. |
| 383 |
switch(Rand(5)) { |
| 384 |
case 0: Val++; break; |
| 385 |
case 1: Val--; break; |
| 386 |
case 2: Val /= 2; break; |
| 387 |
case 3: Val *= 2; break; |
| 388 |
case 4: Val = Rand(Val * Val); break; |
| 389 |
default: assert(0); |
| 390 |
} |
| 391 |
// Just replace the bytes with the new ones, don't bother moving bytes. |
| 392 |
for (size_t i = B; i < E; i++) { |
| 393 |
size_t Idx = E + B - i - 1; |
| 394 |
assert(Idx >= B && Idx < E); |
| 395 |
Data[Idx] = (Val % 10) + '0'; |
| 396 |
Val /= 10; |
| 397 |
} |
| 398 |
return Size; |
| 399 |
} |
| 400 |
|
| 401 |
template<class T> |
| 402 |
size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { |
| 403 |
if (Size < sizeof(T)) return 0; |
| 404 |
size_t Off = Rand(Size - sizeof(T) + 1); |
| 405 |
assert(Off + sizeof(T) <= Size); |
| 406 |
T Val; |
| 407 |
if (Off < 64 && !Rand(4)) { |
| 408 |
Val = static_cast<T>(Size); |
| 409 |
if (Rand.RandBool()) |
| 410 |
Val = Bswap(Val); |
| 411 |
} else { |
| 412 |
memcpy(&Val, Data + Off, sizeof(Val)); |
| 413 |
T Add = static_cast<T>(Rand(21)); |
| 414 |
Add -= 10; |
| 415 |
if (Rand.RandBool()) |
| 416 |
Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. |
| 417 |
else |
| 418 |
Val = Val + Add; // Add assuming current endiannes. |
| 419 |
if (Add == 0 || Rand.RandBool()) // Maybe negate. |
| 420 |
Val = -Val; |
| 421 |
} |
| 422 |
memcpy(Data + Off, &Val, sizeof(Val)); |
| 423 |
return Size; |
| 424 |
} |
| 425 |
|
| 426 |
size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, |
| 427 |
size_t Size, |
| 428 |
size_t MaxSize) { |
| 429 |
if (Size > MaxSize) return 0; |
| 430 |
switch (Rand(4)) { |
| 431 |
case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand); |
| 432 |
case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand); |
| 433 |
case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand); |
| 434 |
case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand); |
| 435 |
default: assert(0); |
| 436 |
} |
| 437 |
return 0; |
| 438 |
} |
| 439 |
|
| 440 |
size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, |
| 441 |
size_t MaxSize) { |
| 442 |
if (Size > MaxSize) return 0; |
| 443 |
if (Size == 0) return 0; |
| 444 |
if (!CrossOverWith) return 0; |
| 445 |
const Unit &O = *CrossOverWith; |
| 446 |
if (O.empty()) return 0; |
| 447 |
size_t NewSize = 0; |
| 448 |
switch(Rand(3)) { |
| 449 |
case 0: |
| 450 |
MutateInPlaceHere.resize(MaxSize); |
| 451 |
NewSize = CrossOver(Data, Size, O.data(), O.size(), |
| 452 |
MutateInPlaceHere.data(), MaxSize); |
| 453 |
memcpy(Data, MutateInPlaceHere.data(), NewSize); |
| 454 |
break; |
| 455 |
case 1: |
| 456 |
NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize); |
| 457 |
if (!NewSize) |
| 458 |
NewSize = CopyPartOf(O.data(), O.size(), Data, Size); |
| 459 |
break; |
| 460 |
case 2: |
| 461 |
NewSize = CopyPartOf(O.data(), O.size(), Data, Size); |
| 462 |
break; |
| 463 |
default: assert(0); |
| 464 |
} |
| 465 |
assert(NewSize > 0 && "CrossOver returned empty unit"); |
| 466 |
assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); |
| 467 |
return NewSize; |
| 468 |
} |
| 469 |
|
| 470 |
void MutationDispatcher::StartMutationSequence() { |
| 471 |
CurrentMutatorSequence.clear(); |
| 472 |
CurrentDictionaryEntrySequence.clear(); |
| 473 |
} |
| 474 |
|
| 475 |
// Copy successful dictionary entries to PersistentAutoDictionary. |
| 476 |
void MutationDispatcher::RecordSuccessfulMutationSequence() { |
| 477 |
for (auto DE : CurrentDictionaryEntrySequence) { |
| 478 |
// PersistentAutoDictionary.AddWithSuccessCountOne(DE); |
| 479 |
DE->IncSuccessCount(); |
| 480 |
assert(DE->GetW().size()); |
| 481 |
// Linear search is fine here as this happens seldom. |
| 482 |
if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) |
| 483 |
PersistentAutoDictionary.push_back(*DE); |
| 484 |
} |
| 485 |
} |
| 486 |
|
| 487 |
void MutationDispatcher::PrintRecommendedDictionary() { |
| 488 |
std::vector<DictionaryEntry> V; |
| 489 |
for (auto &DE : PersistentAutoDictionary) |
| 490 |
if (!ManualDictionary.ContainsWord(DE.GetW())) |
| 491 |
V.push_back(DE); |
| 492 |
if (V.empty()) return; |
| 493 |
Printf("###### Recommended dictionary. ######\n"); |
| 494 |
for (auto &DE: V) { |
| 495 |
assert(DE.GetW().size()); |
| 496 |
Printf("\""); |
| 497 |
PrintASCII(DE.GetW(), "\""); |
| 498 |
Printf(" # Uses: %zd\n", DE.GetUseCount()); |
| 499 |
} |
| 500 |
Printf("###### End of recommended dictionary. ######\n"); |
| 501 |
} |
| 502 |
|
| 503 |
void MutationDispatcher::PrintMutationSequence(bool Verbose) { |
| 504 |
Printf("MS: %zd ", CurrentMutatorSequence.size()); |
| 505 |
size_t EntriesToPrint = |
| 506 |
Verbose ? CurrentMutatorSequence.size() |
| 507 |
: std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size()); |
| 508 |
for (size_t i = 0; i < EntriesToPrint; i++) |
| 509 |
Printf("%s-", CurrentMutatorSequence[i].Name); |
| 510 |
if (!CurrentDictionaryEntrySequence.empty()) { |
| 511 |
Printf(" DE: "); |
| 512 |
EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size() |
| 513 |
: std::min(kMaxMutationsToPrint, |
| 514 |
CurrentDictionaryEntrySequence.size()); |
| 515 |
for (size_t i = 0; i < EntriesToPrint; i++) { |
| 516 |
Printf("\""); |
| 517 |
PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-"); |
| 518 |
} |
| 519 |
} |
| 520 |
} |
| 521 |
|
| 522 |
std::string MutationDispatcher::MutationSequence() { |
| 523 |
std::string MS; |
| 524 |
for (const auto &M : CurrentMutatorSequence) { |
| 525 |
MS += M.Name; |
| 526 |
MS += "-"; |
| 527 |
} |
| 528 |
return MS; |
| 529 |
} |
| 530 |
|
| 531 |
size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { |
| 532 |
return MutateImpl(Data, Size, MaxSize, Mutators); |
| 533 |
} |
| 534 |
|
| 535 |
size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, |
| 536 |
size_t MaxSize) { |
| 537 |
return MutateImpl(Data, Size, MaxSize, DefaultMutators); |
| 538 |
} |
| 539 |
|
| 540 |
// Mutates Data in place, returns new size. |
| 541 |
size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, |
| 542 |
size_t MaxSize, |
| 543 |
std::vector<Mutator> &Mutators) { |
| 544 |
assert(MaxSize > 0); |
| 545 |
// Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), |
| 546 |
// in which case they will return 0. |
| 547 |
// Try several times before returning un-mutated data. |
| 548 |
for (int Iter = 0; Iter < 100; Iter++) { |
| 549 |
auto M = Mutators[Rand(Mutators.size())]; |
| 550 |
size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); |
| 551 |
if (NewSize && NewSize <= MaxSize) { |
| 552 |
if (Options.OnlyASCII) |
| 553 |
ToASCII(Data, NewSize); |
| 554 |
CurrentMutatorSequence.push_back(M); |
| 555 |
return NewSize; |
| 556 |
} |
| 557 |
} |
| 558 |
*Data = ' '; |
| 559 |
return 1; // Fallback, should not happen frequently. |
| 560 |
} |
| 561 |
|
| 562 |
// Mask represents the set of Data bytes that are worth mutating. |
| 563 |
size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size, |
| 564 |
size_t MaxSize, |
| 565 |
const std::vector<uint8_t> &Mask) { |
| 566 |
size_t MaskedSize = std::min(Size, Mask.size()); |
| 567 |
// * Copy the worthy bytes into a temporary array T |
| 568 |
// * Mutate T |
| 569 |
// * Copy T back. |
| 570 |
// This is totally unoptimized. |
| 571 |
auto &T = MutateWithMaskTemp; |
| 572 |
if (T.size() < Size) |
| 573 |
T.resize(Size); |
| 574 |
size_t OneBits = 0; |
| 575 |
for (size_t I = 0; I < MaskedSize; I++) |
| 576 |
if (Mask[I]) |
| 577 |
T[OneBits++] = Data[I]; |
| 578 |
|
| 579 |
if (!OneBits) return 0; |
| 580 |
assert(!T.empty()); |
| 581 |
size_t NewSize = Mutate(T.data(), OneBits, OneBits); |
| 582 |
assert(NewSize <= OneBits); |
| 583 |
(void)NewSize; |
| 584 |
// Even if NewSize < OneBits we still use all OneBits bytes. |
| 585 |
for (size_t I = 0, J = 0; I < MaskedSize; I++) |
| 586 |
if (Mask[I]) |
| 587 |
Data[I] = T[J++]; |
| 588 |
return Size; |
| 589 |
} |
| 590 |
|
| 591 |
void MutationDispatcher::AddWordToManualDictionary(const Word &W) { |
| 592 |
ManualDictionary.push_back( |
| 593 |
{W, std::numeric_limits<size_t>::max()}); |
| 594 |
} |
| 595 |
|
| 596 |
} // namespace fuzzer |