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#include <algorithm>
17
18namespace fuzzer {
19
20struct Mutator {
21  size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
22  const char *Name;
23};
24
25struct MutationDispatcher::Impl {
26  std::vector<Unit> Dictionary;
27  std::vector<Mutator> Mutators;
28  std::vector<Mutator> CurrentMutatorSequence;
29  const std::vector<Unit> *Corpus = nullptr;
30
31  void Add(Mutator M) { Mutators.push_back(M); }
32  Impl() {
33    Add({&MutationDispatcher::Mutate_EraseByte, "EraseByte"});
34    Add({&MutationDispatcher::Mutate_InsertByte, "InsertByte"});
35    Add({&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"});
36    Add({&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"});
37    Add({&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"});
38    Add({&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"});
39    Add({&MutationDispatcher::Mutate_CrossOver, "CrossOver"});
40  }
41  void AddWordToDictionary(const uint8_t *Word, size_t Size) {
42    if (Dictionary.empty()) {
43      Add({&MutationDispatcher::Mutate_AddWordFromDictionary, "AddFromDict"});
44    }
45    Dictionary.push_back(Unit(Word, Word + Size));
46  }
47  void SetCorpus(const std::vector<Unit> *Corpus) { this->Corpus = Corpus; }
48};
49
50static char FlipRandomBit(char X, FuzzerRandomBase &Rand) {
51  int Bit = Rand(8);
52  char Mask = 1 << Bit;
53  char R;
54  if (X & (1 << Bit))
55    R = X & ~Mask;
56  else
57    R = X | Mask;
58  assert(R != X);
59  return R;
60}
61
62static char RandCh(FuzzerRandomBase &Rand) {
63  if (Rand.RandBool()) return Rand(256);
64  const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~.";
65  return Special[Rand(sizeof(Special) - 1)];
66}
67
68size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
69                                               size_t MaxSize) {
70  assert(Size);
71  size_t ShuffleAmount = Rand(std::min(Size, (size_t)8)) + 1;  // [1,8] and <= Size.
72  size_t ShuffleStart = Rand(Size - ShuffleAmount);
73  assert(ShuffleStart + ShuffleAmount <= Size);
74  std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount,
75                      Rand);
76  return Size;
77}
78
79size_t MutationDispatcher::Mutate_EraseByte(uint8_t *Data, size_t Size,
80                                            size_t MaxSize) {
81  assert(Size);
82  if (Size == 1) return 0;
83  size_t Idx = Rand(Size);
84  // Erase Data[Idx].
85  memmove(Data + Idx, Data + Idx + 1, Size - Idx - 1);
86  return Size - 1;
87}
88
89size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
90                                             size_t MaxSize) {
91  if (Size == MaxSize) return 0;
92  size_t Idx = Rand(Size + 1);
93  // Insert new value at Data[Idx].
94  memmove(Data + Idx + 1, Data + Idx, Size - Idx);
95  Data[Idx] = RandCh(Rand);
96  return Size + 1;
97}
98
99size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
100                                             size_t MaxSize) {
101  size_t Idx = Rand(Size);
102  Data[Idx] = RandCh(Rand);
103  return Size;
104}
105
106size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
107                                            size_t MaxSize) {
108  size_t Idx = Rand(Size);
109  Data[Idx] = FlipRandomBit(Data[Idx], Rand);
110  return Size;
111}
112
113size_t MutationDispatcher::Mutate_AddWordFromDictionary(uint8_t *Data,
114                                                        size_t Size,
115                                                        size_t MaxSize) {
116  auto &D = MDImpl->Dictionary;
117  assert(!D.empty());
118  if (D.empty()) return 0;
119  const Unit &Word = D[Rand(D.size())];
120  if (Size + Word.size() > MaxSize) return 0;
121  size_t Idx = Rand(Size + 1);
122  memmove(Data + Idx + Word.size(), Data + Idx, Size - Idx);
123  memcpy(Data + Idx, Word.data(), Word.size());
124  return Size + Word.size();
125}
126
127size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
128                                                     size_t MaxSize) {
129  size_t B = Rand(Size);
130  while (B < Size && !isdigit(Data[B])) B++;
131  if (B == Size) return 0;
132  size_t E = B;
133  while (E < Size && isdigit(Data[E])) E++;
134  assert(B < E);
135  // now we have digits in [B, E).
136  // strtol and friends don't accept non-zero-teminated data, parse it manually.
137  uint64_t Val = Data[B] - '0';
138  for (size_t i = B + 1; i < E; i++)
139    Val = Val * 10 + Data[i] - '0';
140
141  // Mutate the integer value.
142  switch(Rand(5)) {
143    case 0: Val++; break;
144    case 1: Val--; break;
145    case 2: Val /= 2; break;
146    case 3: Val *= 2; break;
147    case 4: Val = Rand(Val * Val); break;
148    default: assert(0);
149  }
150  // Just replace the bytes with the new ones, don't bother moving bytes.
151  for (size_t i = B; i < E; i++) {
152    size_t Idx = E + B - i - 1;
153    assert(Idx >= B && Idx < E);
154    Data[Idx] = (Val % 10) + '0';
155    Val /= 10;
156  }
157  return Size;
158}
159
160size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
161                                            size_t MaxSize) {
162  auto Corpus = MDImpl->Corpus;
163  if (!Corpus || Corpus->size() < 2 || Size == 0) return 0;
164  size_t Idx = Rand(Corpus->size());
165  const Unit &Other = (*Corpus)[Idx];
166  if (Other.empty()) return 0;
167  Unit U(MaxSize);
168  size_t NewSize =
169      CrossOver(Data, Size, Other.data(), Other.size(), U.data(), U.size());
170  assert(NewSize > 0 && "CrossOver returned empty unit");
171  assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
172  memcpy(Data, U.data(), NewSize);
173  return NewSize;
174}
175
176void MutationDispatcher::StartMutationSequence() {
177  MDImpl->CurrentMutatorSequence.clear();
178}
179
180void MutationDispatcher::PrintMutationSequence() {
181  Printf("MS: %zd ", MDImpl->CurrentMutatorSequence.size());
182  for (auto M : MDImpl->CurrentMutatorSequence)
183    Printf("%s-", M.Name);
184}
185
186// Mutates Data in place, returns new size.
187size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
188  assert(MaxSize > 0);
189  assert(Size <= MaxSize);
190  if (Size == 0) {
191    for (size_t i = 0; i < MaxSize; i++)
192      Data[i] = RandCh(Rand);
193    return MaxSize;
194  }
195  assert(Size > 0);
196  // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
197  // in which case they will return 0.
198  // Try several times before returning un-mutated data.
199  for (int Iter = 0; Iter < 10; Iter++) {
200    size_t MutatorIdx = Rand(MDImpl->Mutators.size());
201    auto M = MDImpl->Mutators[MutatorIdx];
202    size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
203    if (NewSize) {
204      MDImpl->CurrentMutatorSequence.push_back(M);
205      return NewSize;
206    }
207  }
208  return Size;
209}
210
211void MutationDispatcher::SetCorpus(const std::vector<Unit> *Corpus) {
212  MDImpl->SetCorpus(Corpus);
213}
214
215void MutationDispatcher::AddWordToDictionary(const uint8_t *Word, size_t Size) {
216  MDImpl->AddWordToDictionary(Word, Size);
217}
218
219MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {
220  MDImpl = new Impl;
221}
222
223MutationDispatcher::~MutationDispatcher() { delete MDImpl; }
224
225}  // namespace fuzzer
226