[libFuzzer] implement crash-resistant merge (https://github.com/google/sanitizers/issues/722). This is a first experimental variant that needs some more testing, thus not yet adding a lit test (but there are unit tests).

llvm-svn: 289166

1 files changed, 135 insertions, 0 deletions

diff --git a/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp b/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
index 79b8c2865f6..aab326229a8 100644
--- a/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
+++ b/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
@@ -8,6 +8,7 @@
 #include "FuzzerCorpus.h"
 #include "FuzzerInternal.h"
 #include "FuzzerDictionary.h"
+#include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
 #include "gtest/gtest.h"
@@ -598,3 +599,137 @@ TEST(Corpus, Distribution) {
     EXPECT_GT(Hist[i], TriesPerUnit / N / 3);
   }
 }
+
+TEST(Merge, Bad) {
+  const char *kInvalidInputs[] = {
+    "",
+    "x",
+    "3\nx",
+    "2\n3",
+    "2\n2",
+    "2\n2\nA\n",
+    "2\n2\nA\nB\nC\n",
+    "0\n0\n",
+    "1\n1\nA\nDONE 0",
+    "1\n1\nA\nSTARTED 1",
+  };
+  Merger M;
+  for (auto S : kInvalidInputs) {
+    // fprintf(stderr, "TESTING:\n%s\n", S);
+    EXPECT_FALSE(M.Parse(S, false));
+  }
+}
+
+void EQ(const std::set<size_t> &A, const std::set<size_t> &B) {
+  EXPECT_EQ(A, B);
+}
+
+void EQ(const std::vector<std::string> &A, const std::vector<std::string> &B) {
+  std::set<std::string> a(A.begin(), A.end());
+  std::set<std::string> b(B.begin(), B.end());
+  EXPECT_EQ(a, b);
+}
+
+static void Merge(const std::string &Input,
+                  const std::vector<std::string> Result,
+                  size_t NumNewFeatures) {
+  Merger M;
+  std::vector<std::string> NewFiles;
+  EXPECT_TRUE(M.Parse(Input, true));
+  EXPECT_EQ(NumNewFeatures, M.Merge(&NewFiles));
+  EQ(NewFiles, Result);
+}
+
+TEST(Merge, Good) {
+  Merger M;
+
+  EXPECT_TRUE(M.Parse("1\n0\nAA\n", false));
+  EXPECT_EQ(M.Files.size(), 1U);
+  EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
+  EXPECT_EQ(M.Files[0].Name, "AA");
+  EXPECT_TRUE(M.LastFailure.empty());
+  EXPECT_EQ(M.FirstNotProcessedFile, 0U);
+
+  EXPECT_TRUE(M.Parse("2\n1\nAA\nBB\nSTARTED 0 42\n", false));
+  EXPECT_EQ(M.Files.size(), 2U);
+  EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
+  EXPECT_EQ(M.Files[0].Name, "AA");
+  EXPECT_EQ(M.Files[1].Name, "BB");
+  EXPECT_EQ(M.LastFailure, "AA");
+  EXPECT_EQ(M.FirstNotProcessedFile, 1U);
+
+  EXPECT_TRUE(M.Parse("3\n1\nAA\nBB\nC\n"
+                        "STARTED 0 1000\n"
+                        "DONE 0 1 2 3\n"
+                        "STARTED 1 1001\n"
+                        "DONE 1 4 5 6 \n"
+                        "STARTED 2 1002\n"
+                        "", true));
+  EXPECT_EQ(M.Files.size(), 3U);
+  EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
+  EXPECT_EQ(M.Files[0].Name, "AA");
+  EXPECT_EQ(M.Files[0].Size, 1000U);
+  EXPECT_EQ(M.Files[1].Name, "BB");
+  EXPECT_EQ(M.Files[1].Size, 1001U);
+  EXPECT_EQ(M.Files[2].Name, "C");
+  EXPECT_EQ(M.Files[2].Size, 1002U);
+  EXPECT_EQ(M.LastFailure, "C");
+  EXPECT_EQ(M.FirstNotProcessedFile, 3U);
+  EQ(M.Files[0].Features, {1, 2, 3});
+  EQ(M.Files[1].Features, {4, 5, 6});
+
+
+  std::vector<std::string> NewFiles;
+
+  EXPECT_TRUE(M.Parse("3\n2\nAA\nBB\nC\n"
+                        "STARTED 0 1000\nDONE 0 1 2 3\n"
+                        "STARTED 1 1001\nDONE 1 4 5 6 \n"
+                        "STARTED 2 1002\nDONE 2 6 1 3 \n"
+                        "", true));
+  EXPECT_EQ(M.Files.size(), 3U);
+  EXPECT_EQ(M.NumFilesInFirstCorpus, 2U);
+  EXPECT_TRUE(M.LastFailure.empty());
+  EXPECT_EQ(M.FirstNotProcessedFile, 3U);
+  EQ(M.Files[0].Features, {1, 2, 3});
+  EQ(M.Files[1].Features, {4, 5, 6});
+  EQ(M.Files[2].Features, {1, 3, 6});
+  EXPECT_EQ(0U, M.Merge(&NewFiles));
+  EQ(NewFiles, {});
+
+  EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
+                        "STARTED 0 1000\nDONE 0 1 2 3\n"
+                        "STARTED 1 1001\nDONE 1 4 5 6 \n"
+                        "STARTED 2 1002\nDONE 2 6 1 3 \n"
+                        "", true));
+  EXPECT_EQ(3U, M.Merge(&NewFiles));
+  EQ(NewFiles, {"B"});
+}
+
+TEST(Merge, Merge) {
+
+  Merge("3\n1\nA\nB\nC\n"
+        "STARTED 0 1000\nDONE 0 1 2 3\n"
+        "STARTED 1 1001\nDONE 1 4 5 6 \n"
+        "STARTED 2 1002\nDONE 2 6 1 3 \n",
+        {"B"}, 3);
+
+  Merge("3\n0\nA\nB\nC\n"
+        "STARTED 0 2000\nDONE 0 1 2 3\n"
+        "STARTED 1 1001\nDONE 1 4 5 6 \n"
+        "STARTED 2 1002\nDONE 2 6 1 3 \n",
+        {"A", "B", "C"}, 6);
+
+  Merge("4\n0\nA\nB\nC\nD\n"
+        "STARTED 0 2000\nDONE 0 1 2 3\n"
+        "STARTED 1 1101\nDONE 1 4 5 6 \n"
+        "STARTED 2 1102\nDONE 2 6 1 3 100 \n"
+        "STARTED 3 1000\nDONE 3 1  \n",
+        {"A", "B", "C", "D"}, 7);
+
+  Merge("4\n1\nA\nB\nC\nD\n"
+        "STARTED 0 2000\nDONE 0 4 5 6 7 8\n"
+        "STARTED 1 1100\nDONE 1 1 2 3 \n"
+        "STARTED 2 1100\nDONE 2 2 3 \n"
+        "STARTED 3 1000\nDONE 3 1  \n",
+        {"B", "D"}, 3);
+}