[libFuzzer] more mutations

llvm-svn: 278950

3 files changed, 124 insertions, 18 deletions

diff --git a/llvm/lib/Fuzzer/FuzzerInternal.h b/llvm/lib/Fuzzer/FuzzerInternal.h
index 940d8365f34..6ffaaf29236 100644
--- a/llvm/lib/Fuzzer/FuzzerInternal.h
+++ b/llvm/lib/Fuzzer/FuzzerInternal.h
@@ -272,6 +272,8 @@ public:
   size_t Mutate_ChangeByte(uint8_t *Data, size_t Size, size_t MaxSize);
   /// Mutates data by chanding one bit.
   size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by copying/inserting a part of data into a different place.
+  size_t Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize);
 
   /// Mutates data by adding a word from the manual dictionary.
   size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size,
@@ -324,6 +326,11 @@ private:
   size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize,
                     const std::vector<Mutator> &Mutators);
 
+  size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
+                      size_t ToSize, size_t MaxToSize);
+  size_t CopyPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
+                    size_t ToSize);
+
   Random &Rand;
   const FuzzingOptions Options;
 
diff --git a/llvm/lib/Fuzzer/FuzzerMutate.cpp b/llvm/lib/Fuzzer/FuzzerMutate.cpp
index 05ea39d9f39..d3eaac086c7 100644
--- a/llvm/lib/Fuzzer/FuzzerMutate.cpp
+++ b/llvm/lib/Fuzzer/FuzzerMutate.cpp
@@ -32,6 +32,7 @@ MutationDispatcher::MutationDispatcher(Random &Rand,
           {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
           {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
           {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
+          {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
           {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
           {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
            "AddFromManualDict"},
@@ -51,21 +52,9 @@ MutationDispatcher::MutationDispatcher(Random &Rand,
         {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
 }
 
-static char FlipRandomBit(char X, Random &Rand) {
-  int Bit = Rand(8);
-  char Mask = 1 << Bit;
-  char R;
-  if (X & (1 << Bit))
-    R = X & ~Mask;
-  else
-    R = X | Mask;
-  assert(R != X);
-  return R;
-}
-
 static char RandCh(Random &Rand) {
   if (Rand.RandBool()) return Rand(256);
-  const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~.";
+  const char *Special = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
   return Special[Rand(sizeof(Special) - 1)];
 }
 
@@ -155,7 +144,7 @@ size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
                                             size_t MaxSize) {
   size_t Idx = Rand(Size);
-  Data[Idx] = FlipRandomBit(Data[Idx], Rand);
+  Data[Idx] ^= 1 << Rand(8);
   return Size;
 }
 
@@ -198,6 +187,55 @@ size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
   return Size;
 }
 
+// Overwrites part of To[0,ToSize) with a part of From[0,FromSize).
+// Returns ToSize.
+size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize,
+                                      uint8_t *To, size_t ToSize) {
+  // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize).
+  size_t ToBeg = Rand(ToSize);
+  size_t CopySize = Rand(ToSize - ToBeg) + 1;
+  assert(ToBeg + CopySize <= ToSize);
+  CopySize = std::min(CopySize, FromSize);
+  size_t FromBeg = Rand(FromSize - CopySize + 1);
+  assert(FromBeg + CopySize <= FromSize);
+  memmove(To + ToBeg, From + FromBeg, CopySize);
+  return ToSize;
+}
+
+// Inserts part of From[0,ToSize) into To.
+// Returns new size of To on success or 0 on failure.
+size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize,
+                                        uint8_t *To, size_t ToSize,
+                                        size_t MaxToSize) {
+  if (ToSize >= MaxToSize) return 0;
+  size_t AvailableSpace = MaxToSize - ToSize;
+  size_t MaxCopySize = std::min(AvailableSpace, FromSize);
+  size_t CopySize = Rand(MaxCopySize) + 1;
+  size_t FromBeg = Rand(FromSize - CopySize + 1);
+  assert(FromBeg + CopySize <= FromSize);
+  size_t ToInsertPos = Rand(ToSize + 1);
+  assert(ToInsertPos + CopySize <= MaxToSize);
+  size_t TailSize = ToSize - ToInsertPos;
+  if (To == From) {
+    MutateInPlaceHere.resize(MaxToSize);
+    memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize);
+    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
+    memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize);
+  } else {
+    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
+    memmove(To + ToInsertPos, From + FromBeg, CopySize);
+  }
+  return ToSize + CopySize;
+}
+
+size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size,
+                                           size_t MaxSize) {
+  if (Rand.RandBool())
+    return CopyPartOf(Data, Size, Data, Size);
+  else
+    return InsertPartOf(Data, Size, Data, Size, MaxSize);
+}
+
 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
                                                      size_t MaxSize) {
   size_t B = Rand(Size);
@@ -235,12 +273,25 @@ size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
                                             size_t MaxSize) {
   if (!Corpus || Corpus->size() < 2 || Size == 0) return 0;
   size_t Idx = Rand(Corpus->size());
-  const Unit &Other = (*Corpus)[Idx];
-  if (Other.empty()) return 0;
+  const Unit &O = (*Corpus)[Idx];
+  if (O.empty()) return 0;
   MutateInPlaceHere.resize(MaxSize);
   auto &U = MutateInPlaceHere;
-  size_t NewSize =
-      CrossOver(Data, Size, Other.data(), Other.size(), U.data(), U.size());
+  size_t NewSize;
+  switch(Rand(3)) {
+    case 0:
+      NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size());
+      break;
+    case 1:
+      NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize);
+      if (NewSize)
+        break;
+      // Fallthrough
+    case 2:
+      NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size());
+      break;
+    default: assert(0);
+  }
   assert(NewSize > 0 && "CrossOver returned empty unit");
   assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
   memcpy(Data, U.data(), NewSize);
diff --git a/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp b/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
index bcbd1169a68..7439d822a45 100644
--- a/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
+++ b/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
@@ -324,6 +324,54 @@ TEST(FuzzerMutate, ShuffleBytes2) {
   TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 20);
 }
 
+void TestCopyPart(Mutator M, int NumIter) {
+  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
+  fuzzer::EF = t.get();
+  Random Rand(0);
+  MutationDispatcher MD(Rand, {});
+  int FoundMask = 0;
+  uint8_t CH0[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11};
+  uint8_t CH1[7] = {0x55, 0x66, 0x22, 0x33, 0x44, 0x55, 0x66};
+  uint8_t CH2[7] = {0x00, 0x55, 0x66, 0x33, 0x44, 0x55, 0x66};
+  uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x66};
+  uint8_t CH4[7] = {0x00, 0x11, 0x11, 0x22, 0x33, 0x55, 0x66};
+
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+    size_t NewSize = (MD.*M)(T, 7, 7);
+    if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
+    if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
+    if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
+    if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
+    if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4;
+  }
+
+  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
+  uint8_t CH6[8] = {0x22, 0x33, 0x44, 0x00, 0x11, 0x22, 0x33, 0x44};
+  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x33, 0x44};
+  uint8_t CH8[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x22, 0x33, 0x44};
+  uint8_t CH9[8] = {0x00, 0x11, 0x22, 0x22, 0x33, 0x44, 0x33, 0x44};
+
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+    size_t NewSize = (MD.*M)(T, 5, 8);
+    if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
+    if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
+    if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
+    if (NewSize == 8 && !memcmp(CH8, T, 8)) FoundMask |= 1 << 8;
+    if (NewSize == 8 && !memcmp(CH9, T, 8)) FoundMask |= 1 << 9;
+  }
+
+  EXPECT_EQ(FoundMask, 1023);
+}
+
+TEST(FuzzerMutate, CopyPart1) {
+  TestCopyPart(&MutationDispatcher::Mutate_CopyPart, 1 << 10);
+}
+TEST(FuzzerMutate, CopyPart2) {
+  TestCopyPart(&MutationDispatcher::Mutate, 1 << 13);
+}
+
 void TestAddWordFromDictionary(Mutator M, int NumIter) {
   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
   fuzzer::EF = t.get();