[libFuzzer] actually make the dictionaries work (+docs)
authorKostya Serebryany <kcc@google.com>
Fri, 4 Sep 2015 00:12:11 +0000 (00:12 +0000)
committerKostya Serebryany <kcc@google.com>
Fri, 4 Sep 2015 00:12:11 +0000 (00:12 +0000)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@246825 91177308-0d34-0410-b5e6-96231b3b80d8

docs/LibFuzzer.rst
lib/Fuzzer/FuzzerDriver.cpp
lib/Fuzzer/FuzzerInterface.h
lib/Fuzzer/FuzzerLoop.cpp
lib/Fuzzer/FuzzerMutate.cpp
lib/Fuzzer/test/CMakeLists.txt
lib/Fuzzer/test/FuzzerUnittest.cpp
lib/Fuzzer/test/SimpleDictionaryTest.cpp [new file with mode: 0644]
lib/Fuzzer/test/dict1.txt [new file with mode: 0644]
lib/Fuzzer/test/fuzzer.test

index dfcf06d..519c651 100644 (file)
@@ -256,6 +256,26 @@ Voila::
 Advanced features
 =================
 
+Dictionaries
+------------
+*EXPERIMENTAL*.
+LibFuzzer supports user-supplied dictionaries with input language keywords
+or other interesting byte sequences (e.g. multi-byte magic values).
+Use ``-dict=DICTIONARY_FILE``. For some input languages using a dictionary
+may significantly improve the search speed.
+The dictionary syntax is similar to that used by AFL_ for its ``-x`` option::
+
+  # Lines starting with '#' and empty lines are ignored.
+
+  # Adds "blah" (w/o quotes) to the dictionary.
+  kw1="blah"
+  # Use \\ for backslash and \" for quotes.
+  kw2="\"ac\\dc\""
+  # Use \xAB for hex values
+  kw3="\xF7\xF8"
+  # the name of the keyword followed by '=' may be omitted:
+  "foo\x0Abar"
+
 Data-flow-guided fuzzing
 ------------------------
 
index 7cb4f3d..8506fb4 100644 (file)
@@ -251,18 +251,17 @@ int FuzzerDriver(int argc, char **argv, UserSuppliedFuzzer &USF) {
     Options.SyncCommand = Flags.sync_command;
   Options.SyncTimeout = Flags.sync_timeout;
   Options.ReportSlowUnits = Flags.report_slow_units;
-  Fuzzer F(USF, Options);
-
-  if (Flags.apply_tokens)
-    return ApplyTokens(F, Flags.apply_tokens);
-
   if (Flags.dict)
     if (!ParseDictionaryFile(FileToString(Flags.dict), &Options.Dictionary))
       return 1;
-
   if (Flags.verbosity > 0 && !Options.Dictionary.empty())
     Printf("Dictionary: %zd entries\n", Options.Dictionary.size());
 
+  Fuzzer F(USF, Options);
+
+  if (Flags.apply_tokens)
+    return ApplyTokens(F, Flags.apply_tokens);
+
   unsigned Seed = Flags.seed;
   // Initialize Seed.
   if (Seed == 0)
index d3843a4..8798b65 100644 (file)
@@ -64,7 +64,8 @@ class FuzzerRandomLibc : public FuzzerRandomBase {
 
 class MutationDispatcher {
  public:
-  MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {}
+  MutationDispatcher(FuzzerRandomBase &Rand);
+  ~MutationDispatcher();
   /// Mutates data by shuffling bytes.
   size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize);
   /// Mutates data by erasing a byte.
@@ -76,6 +77,10 @@ class MutationDispatcher {
   /// Mutates data by chanding one bit.
   size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize);
 
+  /// Mutates data by adding a word from the dictionary.
+  size_t Mutate_AddWordFromDictionary(uint8_t *Data, size_t Size,
+                                      size_t MaxSize);
+
   /// Applies one of the above mutations.
   /// Returns the new size of data which could be up to MaxSize.
   size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize);
@@ -84,8 +89,12 @@ class MutationDispatcher {
   size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2,
                    size_t Size2, uint8_t *Out, size_t MaxOutSize);
 
+  void AddWordToDictionary(const uint8_t *Word, size_t Size);
+
  private:
   FuzzerRandomBase &Rand;
+  struct Impl;
+  Impl *MDImpl;
 };
 
 // For backward compatibility only, deprecated.
@@ -140,6 +149,8 @@ class UserSuppliedFuzzer {
 
   FuzzerRandomBase &GetRand() { return *Rand; }
 
+  MutationDispatcher &GetMD() { return MD; }
+
  private:
   bool OwnRand = false;
   FuzzerRandomBase *Rand;
index dd81616..e65bd33 100644 (file)
@@ -328,6 +328,9 @@ void Fuzzer::MutateAndTestOne(Unit *U) {
 }
 
 void Fuzzer::Loop(size_t NumIterations) {
+  for (auto &U: Options.Dictionary)
+    USF.GetMD().AddWordToDictionary(U.data(), U.size());
+
   for (size_t i = 1; i <= NumIterations; i++) {
     for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
       SyncCorpus();
index 82cee64..70fa88d 100644 (file)
 
 namespace fuzzer {
 
+typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size,
+                                              size_t Max);
+
+struct MutationDispatcher::Impl {
+  std::vector<Unit> Dictionary;
+  std::vector<Mutator> Mutators;
+  Impl() {
+    Mutators.push_back(&MutationDispatcher::Mutate_EraseByte);
+    Mutators.push_back(&MutationDispatcher::Mutate_InsertByte);
+    Mutators.push_back(&MutationDispatcher::Mutate_ChangeByte);
+    Mutators.push_back(&MutationDispatcher::Mutate_ChangeBit);
+    Mutators.push_back(&MutationDispatcher::Mutate_ShuffleBytes);
+  }
+  void AddWordToDictionary(const uint8_t *Word, size_t Size) {
+    if (Dictionary.empty()) {
+      Mutators.push_back(&MutationDispatcher::Mutate_AddWordFromDictionary);
+    }
+    Dictionary.push_back(Unit(Word, Word + Size));
+  }
+};
+
+
 static char FlipRandomBit(char X, FuzzerRandomBase &Rand) {
   int Bit = Rand(8);
   char Mask = 1 << Bit;
@@ -80,6 +102,19 @@ size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
   return Size;
 }
 
+size_t MutationDispatcher::Mutate_AddWordFromDictionary(uint8_t *Data,
+                                                        size_t Size,
+                                                        size_t MaxSize) {
+  auto &D = MDImpl->Dictionary;
+  if (D.empty()) return Size;  // FIXME: indicate failure.
+  const Unit &Word = D[Rand(D.size())];
+  if (Size + Word.size() > MaxSize) return Size;
+  size_t Idx = Rand(Size + 1);
+  memmove(Data + Idx + Word.size(), Data + Idx, Size - Idx);
+  memcpy(Data + Idx, Word.data(), Word.size());
+  return Size + Word.size();
+}
+
 // Mutates Data in place, returns new size.
 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
   assert(MaxSize > 0);
@@ -90,15 +125,20 @@ size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
     return MaxSize;
   }
   assert(Size > 0);
-  switch (Rand(5)) {
-  case 0: Size = Mutate_EraseByte(Data, Size, MaxSize); break;
-  case 1: Size = Mutate_InsertByte(Data, Size, MaxSize); break;
-  case 2: Size = Mutate_ChangeByte(Data, Size, MaxSize); break;
-  case 3: Size = Mutate_ChangeBit(Data, Size, MaxSize); break;
-  case 4: Size = Mutate_ShuffleBytes(Data, Size, MaxSize); break;
-  }
+  size_t MutatorIdx = Rand(MDImpl->Mutators.size());
+  Size = (this->*(MDImpl->Mutators[MutatorIdx]))(Data, Size, MaxSize);
   assert(Size > 0);
   return Size;
 }
 
+void MutationDispatcher::AddWordToDictionary(const uint8_t *Word, size_t Size) {
+  MDImpl->AddWordToDictionary(Word, Size);
+}
+
+MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {
+  MDImpl = new Impl;
+}
+
+MutationDispatcher::~MutationDispatcher() { delete MDImpl; }
+
 }  // namespace fuzzer
index 893274d..a9e6570 100644 (file)
@@ -21,6 +21,7 @@ set(Tests
   MemcmpTest
   NullDerefTest
   SimpleCmpTest
+  SimpleDictionaryTest
   SimpleTest
   StrcmpTest
   StrncmpTest
index f070e4f..1a88aef 100644 (file)
@@ -105,8 +105,12 @@ void TestEraseByte(Mutator M, int NumIter) {
   EXPECT_EQ(FoundMask, 255);
 }
 
-TEST(FuzzerMutate, EraseByte1) { TestEraseByte(&MutationDispatcher::Mutate_EraseByte, 100); }
-TEST(FuzzerMutate, EraseByte2) { TestEraseByte(&MutationDispatcher::Mutate, 1000); }
+TEST(FuzzerMutate, EraseByte1) {
+  TestEraseByte(&MutationDispatcher::Mutate_EraseByte, 100);
+}
+TEST(FuzzerMutate, EraseByte2) {
+  TestEraseByte(&MutationDispatcher::Mutate, 1000);
+}
 
 void TestInsertByte(Mutator M, int NumIter) {
   FuzzerRandomLibc Rand(0);
@@ -135,8 +139,12 @@ void TestInsertByte(Mutator M, int NumIter) {
   EXPECT_EQ(FoundMask, 255);
 }
 
-TEST(FuzzerMutate, InsertByte1) { TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15); }
-TEST(FuzzerMutate, InsertByte2) { TestInsertByte(&MutationDispatcher::Mutate, 1 << 17); }
+TEST(FuzzerMutate, InsertByte1) {
+  TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15);
+}
+TEST(FuzzerMutate, InsertByte2) {
+  TestInsertByte(&MutationDispatcher::Mutate, 1 << 17);
+}
 
 void TestChangeByte(Mutator M, int NumIter) {
   FuzzerRandomLibc Rand(0);
@@ -165,8 +173,12 @@ void TestChangeByte(Mutator M, int NumIter) {
   EXPECT_EQ(FoundMask, 255);
 }
 
-TEST(FuzzerMutate, ChangeByte1) { TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15); }
-TEST(FuzzerMutate, ChangeByte2) { TestChangeByte(&MutationDispatcher::Mutate, 1 << 17); }
+TEST(FuzzerMutate, ChangeByte1) {
+  TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15);
+}
+TEST(FuzzerMutate, ChangeByte2) {
+  TestChangeByte(&MutationDispatcher::Mutate, 1 << 17);
+}
 
 void TestChangeBit(Mutator M, int NumIter) {
   FuzzerRandomLibc Rand(0);
@@ -195,8 +207,12 @@ void TestChangeBit(Mutator M, int NumIter) {
   EXPECT_EQ(FoundMask, 255);
 }
 
-TEST(FuzzerMutate, ChangeBit1) { TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16); }
-TEST(FuzzerMutate, ChangeBit2) { TestChangeBit(&MutationDispatcher::Mutate, 1 << 18); }
+TEST(FuzzerMutate, ChangeBit1) {
+  TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16);
+}
+TEST(FuzzerMutate, ChangeBit2) {
+  TestChangeBit(&MutationDispatcher::Mutate, 1 << 18);
+}
 
 void TestShuffleBytes(Mutator M, int NumIter) {
   FuzzerRandomLibc Rand(0);
@@ -219,8 +235,52 @@ void TestShuffleBytes(Mutator M, int NumIter) {
   EXPECT_EQ(FoundMask, 31);
 }
 
-TEST(FuzzerMutate, ShuffleBytes1) { TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 15); }
-TEST(FuzzerMutate, ShuffleBytes2) { TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 16); }
+TEST(FuzzerMutate, ShuffleBytes1) {
+  TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 15);
+}
+TEST(FuzzerMutate, ShuffleBytes2) {
+  TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 16);
+}
+
+void TestAddWordFromDictionary(Mutator M, int NumIter) {
+  FuzzerRandomLibc Rand(0);
+  MutationDispatcher MD(Rand);
+  uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD};
+  uint8_t Word2[3] = {0xFF, 0xEE, 0xEF};
+  MD.AddWordToDictionary(Word1, sizeof(Word1));
+  MD.AddWordToDictionary(Word2, sizeof(Word2));
+  int FoundMask = 0;
+  uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD};
+  uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22};
+  uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22};
+  uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22};
+  uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF};
+  uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22};
+  uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22};
+  uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22};
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[7] = {0x00, 0x11, 0x22};
+    size_t NewSize = (MD.*M)(T, 3, 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 == 6 && !memcmp(CH4, T, 6)) FoundMask |= 1 << 4;
+    if (NewSize == 6 && !memcmp(CH5, T, 6)) FoundMask |= 1 << 5;
+    if (NewSize == 6 && !memcmp(CH6, T, 6)) FoundMask |= 1 << 6;
+    if (NewSize == 6 && !memcmp(CH7, T, 6)) FoundMask |= 1 << 7;
+  }
+  EXPECT_EQ(FoundMask, 255);
+}
+
+TEST(FuzzerMutate, AddWordFromDictionary1) {
+  TestAddWordFromDictionary(&MutationDispatcher::Mutate_AddWordFromDictionary,
+                            1 << 15);
+}
+
+TEST(FuzzerMutate, AddWordFromDictionary2) {
+  TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15);
+}
 
 TEST(FuzzerDictionary, ParseOneDictionaryEntry) {
   Unit U;
diff --git a/lib/Fuzzer/test/SimpleDictionaryTest.cpp b/lib/Fuzzer/test/SimpleDictionaryTest.cpp
new file mode 100644 (file)
index 0000000..20c8067
--- /dev/null
@@ -0,0 +1,25 @@
+// Simple test for a fuzzer.
+// The fuzzer must find a string based on dictionary words:
+//   "Elvis"
+//   "Presley"
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <cstring>
+#include <iostream>
+
+static volatile int Zero = 0;
+
+extern "C" void LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  const char *Expected = "ElvisPresley";
+  if (Size < strlen(Expected)) return;
+  size_t Match = 0;
+  for (size_t i = 0; Expected[i]; i++)
+    if (Expected[i] + Zero == Data[i])
+      Match++;
+  if (Match == strlen(Expected)) {
+    std::cout << "BINGO; Found the target, exiting\n";
+    exit(1);
+  }
+}
+
diff --git a/lib/Fuzzer/test/dict1.txt b/lib/Fuzzer/test/dict1.txt
new file mode 100644 (file)
index 0000000..520d0cc
--- /dev/null
@@ -0,0 +1,4 @@
+# Dictionary for SimpleDictionaryTest
+
+a="Elvis"
+b="Presley"
index 3b8cf09..d5bd9a3 100644 (file)
@@ -37,3 +37,6 @@ RUN:     LLVMFuzzer-StrcmpTest               -seed=1 -runs=1000000  2>&1 | FileC
 
 RUN: not LLVMFuzzer-SwitchTest -use_traces=1 -seed=1 -runs=1000000  2>&1 | FileCheck %s
 RUN:     LLVMFuzzer-SwitchTest               -seed=1 -runs=1000000  2>&1 | FileCheck %s --check-prefix=Done1000000
+
+RUN: not LLVMFuzzer-SimpleDictionaryTest -dict=%S/dict1.txt -seed=1 -runs=1000000  2>&1 | FileCheck %s
+RUN:     LLVMFuzzer-SimpleDictionaryTest                    -seed=1 -runs=1000000  2>&1 | FileCheck %s --check-prefix=Done1000000