domain_tests/container_test.cc

// Copyright 2022 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Tests of domain ContainerOf, and various shorthands such as VectorOf.

#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/random/random.h"
#include "./fuzztest/domain_core.h"
#include "./domain_tests/domain_testing.h"
#include "./fuzztest/internal/domains/traversal_context.h"
#include "./fuzztest/internal/table_of_recent_compares.h"

namespace fuzztest {
namespace {

using ::testing::Contains;
using ::testing::Gt;
using ::testing::Not;
using ::testing::SizeIs;
using ::testing::UnorderedElementsAre;

template <typename T>
class ContainerTest : public testing::Test {};

using ContainerTypes = testing::Types<
    // Simple types
    std::string, std::vector<int>, std::deque<int>, std::vector<std::byte>,
    // Nested types
    std::vector<std::string>, std::list<std::vector<int>>,
    // Sets
    std::set<int>, std::unordered_set<std::string>, absl::flat_hash_set<int>,
    // Maps
    std::map<int, int>, std::unordered_map<int, int>,
    absl::flat_hash_map<std::string, int>>;

TYPED_TEST_SUITE(ContainerTest, ContainerTypes, );

TYPED_TEST(ContainerTest, Arbitrary) {
  using T = TypeParam;
  Domain<T> domain = Arbitrary<T>();

  auto values = GenerateValues(domain);
  VerifyRoundTripThroughConversion(values, domain);

  // Since we are randomly generating values, we might miss the checks every now
  // and then. In those cases, just make more values.
  for (;; values.merge(GenerateValues(domain))) {
    // Basic checks to make sure we have a few sizes and values.
    // TODO: Check these values in a more principled way.
    absl::flat_hash_map<size_t, size_t> size_distribution;
    absl::flat_hash_map<typename T::value_type, size_t> value_distribution;
    for (const auto& s : values) {
      ++size_distribution[s.user_value.size()];
      for (const auto& v : s.user_value) ++value_distribution[v];
    }
    if (size_distribution.size() <= 10) {
      fprintf(stderr, "Size distribution not met, retrying: %s\n",
              testing::PrintToString(size_distribution).c_str());
      continue;
    }

    if (value_distribution.size() <= 100) {
      fprintf(stderr, "Value distribution not met, retrying: %s\n",
              testing::PrintToString(value_distribution).c_str());
      continue;
    }

    break;
  }

  TestShrink(domain, values, TowardsZero<T>);
}

template <typename Domain>
void TestMinMaxContainerSize(Domain domain, size_t min_size, size_t max_size) {
  absl::BitGen bitgen;

  absl::flat_hash_set<size_t> sizes;

  for (int i = 0; i < 100; ++i) {
    Value v(domain, bitgen);
    auto size_match = SizeIs(IsInClosedRange(min_size, max_size));

    ASSERT_THAT(v.user_value, size_match);
    sizes.insert(v.user_value.size());
    v.Mutate(domain, bitgen, {}, false);
    ASSERT_THAT(v.user_value, size_match);

    // Mutating the value can reach the max, but only for small max sizes
    // because it would otherwise take too long.
    if (max_size <= 10) {
      auto max_v = v;
      while (max_v.user_value.size() < max_size) {
        v.Mutate(domain, bitgen, {}, false);
        if (v.user_value.size() > max_v.user_value.size()) {
          max_v = v;
        } else if (v.user_value.size() < max_v.user_value.size()) {
          // Keep the maximum on `v` to speed up reaching max_size.
          v = max_v;
        }
      }
    }

    // Shinking the value will reach the min.
    while (v.user_value.size() > min_size) {
      v.Mutate(domain, bitgen, {}, true);
    }
    // Mutating again won't go below.
    v.Mutate(domain, bitgen, {}, true);
    ASSERT_THAT(v.user_value, SizeIs(min_size));
  }
  // Check that there is some in between.
  if (min_size == max_size) {
    EXPECT_THAT(sizes, UnorderedElementsAre(min_size));
  } else {
    EXPECT_THAT(sizes, SizeIs(Gt(1)));
  }
}

TYPED_TEST(ContainerTest, SettingSizesLimitsOutput) {
  using T = TypeParam;

  TestMinMaxContainerSize(Arbitrary<T>().WithSize(7), 7, 7);
  TestMinMaxContainerSize(Arbitrary<T>().WithMinSize(7), 7, ~size_t{});
  TestMinMaxContainerSize(Arbitrary<T>().WithMaxSize(7), 0, 7);
  TestMinMaxContainerSize(Arbitrary<T>().WithMinSize(3).WithMaxSize(7), 3, 7);

  auto inner = Arbitrary<typename T::value_type>();

  TestMinMaxContainerSize(ContainerOf<T>(inner).WithSize(7), 7, 7);
  TestMinMaxContainerSize(ContainerOf<T>(inner).WithMinSize(7), 7, ~size_t{});
  TestMinMaxContainerSize(ContainerOf<T>(inner).WithMaxSize(7), 0, 7);
  TestMinMaxContainerSize(ContainerOf<T>(inner).WithMinSize(3).WithMaxSize(7),
                          3, 7);
  TestMinMaxContainerSize(NonEmpty(ContainerOf<T>(inner)), 1, ~size_t{});
}

TYPED_TEST(ContainerTest, GenearatesDifferentValuesWithFixedSize) {
  GenerateValues(Arbitrary<TypeParam>().WithSize(7));
}

TYPED_TEST(ContainerTest, InitGeneratesSeeds) {
  auto domain = Arbitrary<TypeParam>();
  absl::BitGen bitgen;
  auto seed = Value(domain, bitgen);
  seed.RandomizeByRepeatedMutation(domain, bitgen);
  domain.WithSeeds({seed.user_value});

  EXPECT_THAT(GenerateInitialValues(domain, 1000), Contains(seed));
}

TEST(StringTest, GetRandomValueYieldsSeedsAndOtherValues) {
  Domain<std::string> domain = Arbitrary<std::string>().WithSeeds({"seed"});

  absl::BitGen prng;
  bool seed_seen = false;
  bool other_seen = false;
  // To hit the seed, we need to first hit an initial value (p=1/1000) and
  // then hit the actual seed (p=1/2).
  static constexpr double kHitSeedProbability = 1.0 / 1000 * 1.0 / 2;
  for (int i = 0; !(seed_seen && other_seen) &&
                  i < IterationsToHitAll(/*num_cases=*/1, kHitSeedProbability);
       ++i) {
    auto val = domain.GetRandomValue(prng);
    if (val == "seed") {
      seed_seen = true;
    } else {
      other_seen = true;
    }
  }

  EXPECT_TRUE(seed_seen && other_seen);
}

TEST(Container, ValidationRejectsInvalidSize) {
  absl::BitGen bitgen;

  auto domain_a = Arbitrary<std::vector<int>>().WithSize(2);
  auto domain_b = Arbitrary<std::vector<int>>().WithSize(3);

  Value value_a(domain_a, bitgen);
  Value value_b(domain_b, bitgen);

  ASSERT_OK(domain_a.ValidateCorpusValue(value_a.corpus_value));
  ASSERT_OK(domain_b.ValidateCorpusValue(value_b.corpus_value));

  EXPECT_THAT(domain_a.ValidateCorpusValue(value_b.corpus_value),
              IsInvalid("Invalid size: 3. Max size: 2"));
  EXPECT_THAT(domain_b.ValidateCorpusValue(value_a.corpus_value),
              IsInvalid("Invalid size: 2. Min size: 3"));
}

TEST(Container, CorpusValidationSucceedsWhenSizeExceedsSoftMaxSize) {
  auto domain_soft = Arbitrary<std::vector<int>>().WithSoftMaxSize(2);
  auto domain_hard = Arbitrary<std::vector<int>>().WithMaxSize(2);

  std::vector<int> value = {1, 2, 3};
  auto corpus_val_soft = domain_soft.FromValue(value);
  ASSERT_TRUE(corpus_val_soft.has_value());
  EXPECT_TRUE(domain_soft.ValidateCorpusValue(*corpus_val_soft).ok());

  auto corpus_val_hard = domain_hard.FromValue(value);
  ASSERT_TRUE(corpus_val_hard.has_value());
  EXPECT_FALSE(domain_hard.ValidateCorpusValue(*corpus_val_hard).ok());
}

TEST(Container, MaxSizeAndSoftMaxSizeOverwriteEachOther) {
  auto domain_hard =
      Arbitrary<std::vector<int>>().WithSoftMaxSize(2).WithMaxSize(2);
  auto domain_soft =
      Arbitrary<std::vector<int>>().WithMaxSize(2).WithSoftMaxSize(2);

  std::vector<int> value = {1, 2, 3};

  auto corpus_val_hard = domain_hard.FromValue(value);
  ASSERT_TRUE(corpus_val_hard.has_value());
  EXPECT_FALSE(domain_hard.ValidateCorpusValue(*corpus_val_hard).ok());

  auto corpus_val_soft = domain_soft.FromValue(value);
  ASSERT_TRUE(corpus_val_soft.has_value());
  EXPECT_TRUE(domain_soft.ValidateCorpusValue(*corpus_val_soft).ok());
}

TEST(ContainerDeathTest, MutationAbortsWhenSizeExceedsMaxSize) {
  auto domain_hard = Arbitrary<std::vector<int>>().WithMaxSize(2);
  std::vector<int> value = {1, 2, 3};
  Value val(domain_hard, value);
  absl::BitGen bitgen;

  EXPECT_DEATH(
      val.Mutate(domain_hard, bitgen, /*metadata=*/{}, /*only_shrink=*/false),
      "Size 3 is not between 0 and 2");
}

TEST(ContainerTest, WithSoftMaxSizeMutationDoesNotGrowIfSizeExceedsLimit) {
  auto domain_soft = Arbitrary<std::vector<int>>().WithSoftMaxSize(2);
  std::vector<int> value = {1, 2, 3};
  Value val(domain_soft, value);
  absl::BitGen bitgen;

  for (int i = 0; i < 100; ++i) {
    val.Mutate(domain_soft, bitgen, /*metadata=*/{}, /*only_shrink=*/false);
    EXPECT_LE(val.user_value.size(), 3);
  }
}

TEST(Container, ValidationRejectsInvalidElements) {
  absl::BitGen bitgen;

  auto domain_a = VectorOf(InRange(0, 9)).WithMinSize(1);
  auto domain_b = VectorOf(InRange(10, 12)).WithMinSize(1);

  Value value_a(domain_a, bitgen);
  Value value_b(domain_b, bitgen);

  ASSERT_OK(domain_a.ValidateCorpusValue(value_a.corpus_value));
  ASSERT_OK(domain_b.ValidateCorpusValue(value_b.corpus_value));

  EXPECT_THAT(
      domain_a.ValidateCorpusValue(value_b.corpus_value),
      IsInvalid(testing::MatchesRegex(
          R"(Invalid value in container at index 0 >> The value .+ is not InRange\(0, 9\))")));
  EXPECT_THAT(
      domain_b.ValidateCorpusValue(value_a.corpus_value),
      IsInvalid(testing::MatchesRegex(
          R"(Invalid value in container at index 0 >> The value .+ is not InRange\(10, 12\))")));
}

// This should apply to all container types with memory dictionary mutation
// enabled, but we test on strings for simplification.
TEST(Container, MemoryDictionaryMutationMutatesEveryPossibleMatch) {
  auto domain = Arbitrary<std::string>();
  internal::TablesOfRecentCompares cmp_tables;
  cmp_tables.GetMutable<0>().Insert(reinterpret_cast<const uint8_t*>("abcd"),
                                    reinterpret_cast<const uint8_t*>("1234"),
                                    4);

  absl::BitGen bitgen;
  std::vector<std::string> mutants;
  for (int i = 0; i < 1000000; ++i) {
    std::string mutant = "abcdabcdabcdabcd";
    domain.Mutate(mutant, bitgen, {/*cmp_tables=*/&cmp_tables}, false);
    mutants.push_back(std::move(mutant));
  }

  EXPECT_THAT(mutants, testing::IsSupersetOf(std::vector<std::string>{
                           "1234abcdabcdabcd",
                           "abcd1234abcdabcd",
                           "abcdabcd1234abcd",
                           "abcdabcdabcd1234",
                       }));
}

TEST(Container, MatchesDictionaryWithSwappedByteOrder) {
  auto domain = Arbitrary<std::string>();
  internal::TablesOfRecentCompares cmp_tables(/*compact=*/true);
  cmp_tables.GetMutable<4>().Insert(uint32_t{0x12345678}, uint32_t{0x60708090});

  absl::BitGen bitgen;
  std::vector<std::string> mutants;
  for (int i = 0; i < 1000; ++i) {
    std::string mutant = "\x12\x34\x56\x78\x78\x56\x34\x12";
    domain.Mutate(mutant, bitgen, {/*cmp_tables=*/&cmp_tables}, false);
    mutants.push_back(std::move(mutant));
  }

  EXPECT_THAT(mutants, testing::Contains("\x12\x34\x56\x78\x90\x80\x70\x60"));
  EXPECT_THAT(mutants, testing::Contains("\x60\x70\x80\x90\x78\x56\x34\x12"));
}

TEST(Container, ValidatesMemoryDictionaryMutationForInnerDomain) {
  auto domain = VectorOf(InRange<uint8_t>(10, 128));
  internal::TablesOfRecentCompares cmp_tables;
  std::vector<std::vector<uint8_t>> cmp_entries = {{10, 11, 12, 13},
                                                   {129, 129, 129, 129},
                                                   {10, 11, 12, 13},
                                                   {17, 31, 113, 71}};
  // Fill the table with the same entries repeatly.
  for (int i = 0; i < cmp_tables.GetMutable<0>().kTableSize; ++i) {
    cmp_tables.GetMutable<0>().Insert(cmp_entries[0].data(),
                                      cmp_entries[1].data(), 4);
    cmp_tables.GetMutable<0>().Insert(cmp_entries[2].data(),
                                      cmp_entries[3].data(), 4);
  }

  absl::BitGen bitgen;
  std::vector<std::vector<uint8_t>> mutants;
  const double hit_probability =  //
      1.0 / 4                     // to use dictionaries
      * 1.0 / 4                   // to use cmp tables
      * 1.0 / 2                   // to pick the memcmp table
      * 1.0 / 2                   // to pick one of the entries
      * 1.0 / 2;                  // to apply replacement
  for (int i = 0; i < 1 * IterationsToHitAll(/*num_cases=*/2, hit_probability);
       ++i) {
    std::vector<uint8_t> mutant = {10, 11, 12, 13};
    domain.Mutate(mutant, bitgen, {/*cmp_tables=*/&cmp_tables}, false);
    mutants.push_back(std::move(mutant));
  }

  EXPECT_THAT(mutants, Contains(std::vector<uint8_t>{17, 31, 113, 71}));
  EXPECT_THAT(mutants, Not(Contains(std::vector<uint8_t>{129, 129, 129, 129})));
}

TEST(ContainerTest,
     SequenceInitWithTraversalCtxDepthExhaustedWithMinSizeFails) {
  auto domain = VectorOf(Arbitrary<int>()).WithMinSize(3);

  absl::BitGen prng;
  domain_implementor::TraversalState state;
  state.depth_budget = 0;

  const auto val =
      Value<decltype(domain)>::BuildWithTraversalCtx(domain, prng, state);

  EXPECT_FALSE(val.ok());
  EXPECT_FALSE(state.status.ok());
  EXPECT_THAT(state.status.message(),
              testing::HasSubstr("Traversal budget exceeded"));
}

TEST(ContainerTest,
     SequenceInitWithTraversalCtxDepthExhaustedNoMinSizeSucceeds) {
  auto domain = VectorOf(Arbitrary<int>());

  absl::BitGen prng;
  domain_implementor::TraversalState state;
  state.depth_budget = 0;

  const auto val =
      Value<decltype(domain)>::BuildWithTraversalCtx(domain, prng, state);

  ASSERT_OK(val.status());
  EXPECT_TRUE(val->user_value.empty());
  EXPECT_TRUE(state.status.ok());
}

TEST(ContainerTest, SequenceInitWithTraversalCtxUpdatesInitBudget) {
  auto domain = VectorOf(Arbitrary<int>()).WithSize(3);

  absl::BitGen prng;
  domain_implementor::TraversalState state;
  state.init_budget = 10;

  const auto val =
      Value<decltype(domain)>::BuildWithTraversalCtx(domain, prng, state);

  ASSERT_OK(val.status());
  EXPECT_EQ(val->user_value.size(), 3);
  // 1 (root) + 3 (elements) = 4 decrements
  EXPECT_EQ(state.init_budget, 6);
}

TEST(ContainerTest,
     SequenceInitWithTraversalCtxInitBudgetExhaustedWithMinSizeFails) {
  auto domain = VectorOf(Arbitrary<int>()).WithMinSize(3);

  absl::BitGen prng;
  domain_implementor::TraversalState state;
  state.init_budget = 0;  // Enter() will decrement to -1

  const auto val =
      Value<decltype(domain)>::BuildWithTraversalCtx(domain, prng, state);

  EXPECT_FALSE(val.ok());
  EXPECT_FALSE(state.status.ok());
}

TEST(ContainerTest,
     SequenceInitWithTraversalCtxInitBudgetExhaustedNoMinSizeSucceeds) {
  auto domain = VectorOf(Arbitrary<int>());

  absl::BitGen prng;
  domain_implementor::TraversalState state;
  state.init_budget = 0;

  const auto val =
      Value<decltype(domain)>::BuildWithTraversalCtx(domain, prng, state);

  ASSERT_OK(val.status());
  EXPECT_TRUE(val->user_value.empty());
  EXPECT_TRUE(state.status.ok());
}

TEST(ContainerTest,
     SequenceInitWithTraversalCtxPropagatesFailureFromInnerExhaustion) {
  // Both the parent and inner vectors must not be empty.
  auto domain =
      VectorOf(VectorOf(Arbitrary<int>()).WithMinSize(1)).WithMinSize(1);

  absl::BitGen prng;
  domain_implementor::TraversalState state;
  // The parent init decrements to 0 and the inner init decrements to -1
  // and fails due to the min size constraint.
  state.depth_budget = 1;

  const auto val =
      Value<decltype(domain)>::BuildWithTraversalCtx(domain, prng, state);

  EXPECT_FALSE(val.ok());
  EXPECT_FALSE(state.status.ok());
  EXPECT_THAT(state.status.message(),
              testing::HasSubstr("Traversal budget exceeded"));
}

}  // namespace
}  // namespace fuzztest