Implement CrossOver using Copy/Clone mutations

4 files changed, 58 insertions, 205 deletions

diff --git a/src/libfuzzer/libfuzzer_macro.cc b/src/libfuzzer/libfuzzer_macro.cc
index f9ecbb3..b2a5302 100644
--- a/src/libfuzzer/libfuzzer_macro.cc
+++ b/src/libfuzzer/libfuzzer_macro.cc
@@ -123,7 +123,8 @@ size_t CrossOverMessages(unsigned int seed, const InputReader& input1,
   GetMutator()->Seed(seed);
   input1.Read(message1);
   input2.Read(message2);
-  GetMutator()->CrossOver(*message2, message1);
+  size_t max_size = GetMaxSize(input1, *output, *message1);
+  GetMutator()->CrossOver(*message2, message1, max_size);
   if (size_t new_size = output->Write(*message1)) {
     assert(new_size <= output->size());
     return new_size;
diff --git a/src/mutator.cc b/src/mutator.cc
index 745037d..63e2b97 100644
--- a/src/mutator.cc
+++ b/src/mutator.cc
@@ -417,7 +417,7 @@ class FieldMutator {
     assert(*message);
     if (GetRandomBool(mutator_->random(), mutator_->random_to_default_ratio_))
       return;
-    mutator_->MutateImpl(source_, message->get(), size_increase_hint_);
+    mutator_->MutateImpl(source_, message->get(), false, size_increase_hint_);
   }
 
  private:
@@ -475,7 +475,7 @@ struct CreateField : public FieldFunction<CreateField> {
 void Mutator::Seed(uint32_t value) { random_.seed(value); }
 
 void Mutator::Mutate(Message* message, size_t max_size_hint) {
-  MutateImpl(*message, message,
+  MutateImpl(*message, message, false,
              static_cast<int>(max_size_hint) -
                  static_cast<int>(message->ByteSizeLong()));
 
@@ -520,59 +520,63 @@ void Mutator::ApplyPostProcessing(Message* message) {
   }
 }
 
-void Mutator::MutateImpl(const Message& source, Message* message,
-                         int size_increase_hint) {
+bool Mutator::MutateImpl(const Message& source, Message* message,
+                         bool copy_clone_only, int size_increase_hint) {
   if (size_increase_hint > 0) size_increase_hint /= 2;
   MutationBitset mutations;
-  if (size_increase_hint <= 16) {
+  if (copy_clone_only) {
+    mutations[static_cast<size_t>(Mutation::Copy)] = true;
+    mutations[static_cast<size_t>(Mutation::Clone)] = true;
+  } else if (size_increase_hint <= 16) {
     mutations[static_cast<size_t>(Mutation::Delete)] = true;
   } else {
     mutations.set();
   }
-  for (;;) {
+  while (mutations.any()) {
     MutationSampler mutation(keep_initialized_, mutations, &random_, message);
+    // Don't try same mutation next time.
+    mutations[static_cast<size_t>(mutation.mutation())] = false;
     switch (mutation.mutation()) {
       case Mutation::None:
-        return;
+        return true;
       case Mutation::Add:
         CreateField()(mutation.field(), size_increase_hint, source, this);
-        return;
+        return true;
       case Mutation::Mutate:
         MutateField()(mutation.field(), size_increase_hint, source, this);
-        return;
+        return true;
       case Mutation::Delete:
         DeleteField()(mutation.field());
-        return;
+        return true;
       case Mutation::Clone: {
-        CreateField()(mutation.field(), size_increase_hint, source, this);
+        CreateDefaultField()(mutation.field());
         DataSourceSampler source_sampler(mutation.field(), &random_,
                                          size_increase_hint, source);
-        if (source_sampler.IsEmpty()) return;  // CreateField is enough.
+        if (source_sampler.IsEmpty()) return true;  // CreateField is enough.
         CopyField()(source_sampler.field(), mutation.field());
-        return;
+        return true;
       }
       case Mutation::Copy: {
         DataSourceSampler source_sampler(mutation.field(), &random_,
                                          size_increase_hint, source);
         if (source_sampler.IsEmpty()) break;
         CopyField()(source_sampler.field(), mutation.field());
-        return;
+        return true;
       }
       default:
         assert(false && "unexpected mutation");
-        return;
+        return false;
     }
   }
+  return false;
 }
 
-void Mutator::CrossOver(const protobuf::Message& message1,
-                        protobuf::Message* message2) {
-  // CrossOver can produce result which still equals to inputs. So we backup
-  // message2 to later comparison. message1 is already constant.
-  std::unique_ptr<protobuf::Message> message2_copy(message2->New());
-  message2_copy->CopyFrom(*message2);
-
-  CrossOverImpl(message1, message2);
+void Mutator::CrossOver(const Message& message1, Message* message2,
+                        size_t max_size_hint) {
+  int size_increase_hint = static_cast<int>(max_size_hint) -
+                           static_cast<int>(message2->ByteSizeLong());
+  MutateImpl(message1, message2, true, size_increase_hint) ||
+      MutateImpl(*message2, message2, true, size_increase_hint);
 
   InitializeAndTrim(message2, kMaxInitializeDepth);
   assert(IsInitialized(*message2));
@@ -580,85 +584,6 @@ void Mutator::CrossOver(const protobuf::Message& message1,
   if (!post_processors_.empty()) {
     ApplyPostProcessing(message2);
   }
-
-  // Can't call mutate from crossover because of a bug in libFuzzer.
-  // if (MessageDifferencer::Equals(*message2_copy, *message2) ||
-  //     MessageDifferencer::Equals(message1, *message2)) {
-  //   Mutate(message2, 0);
-  // }
-}
-
-void Mutator::CrossOverImpl(const protobuf::Message& message1,
-                            protobuf::Message* message2) {
-  const Descriptor* descriptor = message2->GetDescriptor();
-  const Reflection* reflection = message2->GetReflection();
-  assert(message1.GetDescriptor() == descriptor);
-  assert(message1.GetReflection() == reflection);
-
-  for (int i = 0; i < descriptor->field_count(); ++i) {
-    const FieldDescriptor* field = descriptor->field(i);
-
-    if (field->is_repeated()) {
-      const int field_size1 = reflection->FieldSize(message1, field);
-      int field_size2 = reflection->FieldSize(*message2, field);
-      for (int j = 0; j < field_size1; ++j) {
-        ConstFieldInstance source(&message1, field, j);
-        FieldInstance destination(message2, field, field_size2++);
-        AppendField()(source, destination);
-      }
-
-      assert(field_size2 == reflection->FieldSize(*message2, field));
-
-      // Shuffle
-      for (int j = 0; j < field_size2; ++j) {
-        if (int k = GetRandomIndex(&random_, field_size2 - j)) {
-          reflection->SwapElements(message2, field, j, j + k);
-        }
-      }
-
-      int keep = GetRandomIndex(&random_, field_size2 + 1);
-
-      if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
-        int remove = field_size2 - keep;
-        // Cross some message to keep with messages to remove.
-        int cross = GetRandomIndex(&random_, std::min(keep, remove) + 1);
-        for (int j = 0; j < cross; ++j) {
-          int k = GetRandomIndex(&random_, keep);
-          int r = keep + GetRandomIndex(&random_, remove);
-          assert(k != r);
-          CrossOverImpl(reflection->GetRepeatedMessage(*message2, field, r),
-                        reflection->MutableRepeatedMessage(message2, field, k));
-        }
-      }
-
-      for (int j = keep; j < field_size2; ++j)
-        reflection->RemoveLast(message2, field);
-      assert(keep == reflection->FieldSize(*message2, field));
-
-    } else if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
-      if (!reflection->HasField(message1, field)) {
-        if (GetRandomBool(&random_))
-          DeleteField()(FieldInstance(message2, field));
-      } else if (!reflection->HasField(*message2, field)) {
-        if (GetRandomBool(&random_)) {
-          ConstFieldInstance source(&message1, field);
-          CopyField()(source, FieldInstance(message2, field));
-        }
-      } else {
-        CrossOverImpl(reflection->GetMessage(message1, field),
-                      reflection->MutableMessage(message2, field));
-      }
-    } else {
-      if (GetRandomBool(&random_)) {
-        if (reflection->HasField(message1, field)) {
-          ConstFieldInstance source(&message1, field);
-          CopyField()(source, FieldInstance(message2, field));
-        } else {
-          DeleteField()(FieldInstance(message2, field));
-        }
-      }
-    }
-  }
 }
 
 void Mutator::InitializeAndTrim(Message* message, int max_depth) {
diff --git a/src/mutator.h b/src/mutator.h
index 6e69892..0bc2f0b 100644
--- a/src/mutator.h
+++ b/src/mutator.h
@@ -57,8 +57,8 @@ class Mutator {
   // could repeat mutation if result was larger than expected.
   void Mutate(protobuf::Message* message, size_t max_size_hint);
 
-  void CrossOver(const protobuf::Message& message1,
-                 protobuf::Message* message2);
+  void CrossOver(const protobuf::Message& message1, protobuf::Message* message2,
+                 size_t max_size_hint);
 
   // Callback to postprocess mutations.
   // Implementation should use seed to initialize random number generators.
@@ -90,10 +90,8 @@ class Mutator {
   friend class FieldMutator;
   friend class TestMutator;
   void InitializeAndTrim(protobuf::Message* message, int max_depth);
-  void MutateImpl(const protobuf::Message& source, protobuf::Message* message,
-                  int size_increase_hint);
-  void CrossOverImpl(const protobuf::Message& message1,
-                     protobuf::Message* message2);
+  bool MutateImpl(const protobuf::Message& source, protobuf::Message* message,
+                  bool copy_clone_only, int size_increase_hint);
   std::string MutateUtf8String(const std::string& value,
                                int size_increase_hint);
   void ApplyPostProcessing(protobuf::Message* message);
diff --git a/src/mutator_test.cc b/src/mutator_test.cc
index 522d7bc..ee79ada 100644
--- a/src/mutator_test.cc
+++ b/src/mutator_test.cc
@@ -224,12 +224,6 @@ class TestMutator : public Mutator {
     keep_initialized_ = keep_initialized;
   }
 
-  // Avoids dedup logic for some tests.
-  void NoDeDupCrossOver(const protobuf::Message& message1,
-                        protobuf::Message* message2) {
-    CrossOverImpl(message1, message2);
-  }
-
  private:
   RandomEngine random_;
 };
@@ -329,6 +323,20 @@ bool Mutate(const protobuf::Message& from, const protobuf::Message& to) {
   return false;
 }
 
+bool CrossOver(const protobuf::Message& from, const protobuf::Message& with,
+               const protobuf::Message& to) {
+  EXPECT_FALSE(MessageDifferencer::Equals(from, to));
+  ReducedTestMutator mutator;
+  std::unique_ptr<protobuf::Message> message(from.New());
+  EXPECT_FALSE(MessageDifferencer::Equals(from, to));
+  for (int j = 0; j < 1000000; ++j) {
+    message->CopyFrom(from);
+    mutator.CrossOver(with, message.get(), 1000);
+    if (MessageDifferencer::Equals(*message, to)) return true;
+  }
+  return false;
+}
+
 class MutatorTest : public TestWithParam<TestParams> {
  protected:
   void SetUp() override {
@@ -433,6 +441,16 @@ TEST_P(MutatorFieldTest, ChangeField) {
   EXPECT_TRUE(Mutate(*m2_, *m1_));
 }
 
+TEST_P(MutatorFieldTest, CrossOver) {
+  LoadWithoutLine(m1_.get());
+  LoadMessage(m2_.get());
+
+  EXPECT_FALSE(MessageDifferencer::Equals(*m1_, *m2_));
+  TestMutator mutator(false);
+
+  EXPECT_TRUE(CrossOver(*m1_, *m2_, *m2_));
+}
+
 template <class Msg>
 void MutatorFieldTest::TestCopyField() {
   LoadWithChangedLine(m1_.get(), 7);
@@ -461,43 +479,6 @@ TEST_P(MutatorFieldTest, CopyField) {
 }
 
 class MutatorSingleFieldTest : public MutatorTest {};
-INSTANTIATE_TEST_SUITE_P(Proto2, MutatorSingleFieldTest,
-                         ValuesIn(GetFieldTestParams<Msg>({
-                             kRequiredFields,
-                             kOptionalFields,
-                             kRequiredNestedFields,
-                             kOptionalNestedFields,
-                         })));
-INSTANTIATE_TEST_SUITE_P(Proto3, MutatorSingleFieldTest,
-                         ValuesIn(GetFieldTestParams<Msg3>({
-                             kOptionalFields,
-                             kOptionalNestedFields,
-                         })));
-
-TEST_P(MutatorSingleFieldTest, CrossOver) {
-  LoadWithoutLine(m1_.get());
-  LoadMessage(m2_.get());
-
-  EXPECT_FALSE(MessageDifferencer::Equals(*m1_, *m2_));
-  TestMutator mutator(false);
-
-  int match_m1_ = 0;
-  int match_m2_ = 0;
-  int iterations = 1000;
-  std::unique_ptr<protobuf::Message> message(m1_->New());
-  for (int j = 0; j < iterations; ++j) {
-    message->CopyFrom(*m1_);
-    mutator.NoDeDupCrossOver(*m2_, message.get());
-    if (MessageDifferencer::Equals(*message, *m2_)) ++match_m2_;
-    if (MessageDifferencer::Equals(*message, *m1_)) ++match_m1_;
-  }
-
-  EXPECT_LT(iterations * .4, match_m1_);
-  EXPECT_GE(iterations * .6, match_m1_);
-  EXPECT_LT(iterations * .4, match_m2_);
-  EXPECT_GE(iterations * .6, match_m2_);
-}
-
 template <typename T>
 class MutatorTypedTest : public ::testing::Test {
  public:
@@ -507,58 +488,6 @@ class MutatorTypedTest : public ::testing::Test {
 using MutatorTypedTestTypes = testing::Types<Msg, Msg3>;
 TYPED_TEST_SUITE(MutatorTypedTest, MutatorTypedTestTypes);
 
-TYPED_TEST(MutatorTypedTest, CrossOverRepeated) {
-  typename TestFixture::Message m1;
-  m1.add_repeated_int32(1);
-  m1.add_repeated_int32(2);
-  m1.add_repeated_int32(3);
-
-  typename TestFixture::Message m2;
-  m2.add_repeated_int32(4);
-  m2.add_repeated_int32(5);
-  m2.add_repeated_int32(6);
-
-  int iterations = 10000;
-  std::set<std::set<int>> sets;
-  TestMutator mutator(false);
-  for (int j = 0; j < iterations; ++j) {
-    typename TestFixture::Message message;
-    message.CopyFrom(m1);
-    mutator.NoDeDupCrossOver(m2, &message);
-    sets.insert(
-        {message.repeated_int32().begin(), message.repeated_int32().end()});
-  }
-
-  EXPECT_EQ(1u << 6, sets.size());
-}
-
-TYPED_TEST(MutatorTypedTest, CrossOverRepeatedMessages) {
-  typename TestFixture::Message m1;
-  auto* rm1 = m1.add_repeated_msg();
-  rm1->add_repeated_int32(1);
-  rm1->add_repeated_int32(2);
-
-  typename TestFixture::Message m2;
-  auto* rm2 = m2.add_repeated_msg();
-  rm2->add_repeated_int32(3);
-  rm2->add_repeated_int32(4);
-  rm2->add_repeated_int32(5);
-  rm2->add_repeated_int32(6);
-
-  int iterations = 10000;
-  std::set<std::set<int>> sets;
-  TestMutator mutator(false);
-  for (int j = 0; j < iterations; ++j) {
-    typename TestFixture::Message message;
-    message.CopyFrom(m1);
-    mutator.NoDeDupCrossOver(m2, &message);
-    for (const auto& msg : message.repeated_msg())
-      sets.insert({msg.repeated_int32().begin(), msg.repeated_int32().end()});
-  }
-
-  EXPECT_EQ(1u << 6, sets.size());
-}
-
 TYPED_TEST(MutatorTypedTest, FailedMutations) {
   TestMutator mutator(false);
   size_t crossovers = 0;
@@ -575,7 +504,7 @@ TYPED_TEST(MutatorTypedTest, FailedMutations) {
     }
 
     tmp.CopyFrom(messages[1]);
-    mutator.CrossOver(messages[0], &tmp);
+    mutator.CrossOver(messages[0], &tmp, 1000);
     if (MessageDifferencer::Equals(tmp, messages[1]) ||
         MessageDifferencer::Equals(tmp, messages[0]))
       ++crossovers;