cc/testing/stochastic_tester_test.cc

//
// Copyright 2019 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.
//

#include "testing/stochastic_tester.h"

#include <memory>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/random/distributions.h"
#include "absl/status/statusor.h"
#include "algorithms/algorithm.h"
#include "algorithms/bounded-sum.h"
#include "algorithms/count.h"
#include "algorithms/numerical-mechanisms-testing.h"
#include "algorithms/numerical-mechanisms.h"
#include "algorithms/util.h"
#include "testing/sequence.h"

namespace differential_privacy {
namespace testing {
namespace {

// Trivial non-DP sum that returns the exact value determinisitically.
template <typename T,
          typename std::enable_if<std::is_integral<T>::value ||
                                  std::is_floating_point<T>::value>::type* =
              nullptr>
class NonDpSum : public Algorithm<T> {
 public:
  NonDpSum() : Algorithm<T>(1), result_(0) {}
  void AddEntry(const T& t) override { result_ += t; }

  absl::StatusOr<Output> GenerateResult(
      double /*noise_interval_level*/) override {
    return MakeOutput<T>(result_);
  }
  void ResetState() override { result_ = 0; }

  Summary Serialize() const override { return Summary(); }
  absl::Status Merge(const Summary& summary) override {
    return absl::OkStatus();
  }
  int64_t MemoryUsed() override { return sizeof(NonDpSum<T>); };

 private:
  T result_;
};

// Trivial non-DP count that returns the exact value determinisitically.
template <typename T>
class NonDpCount : public Algorithm<T> {
 public:
  NonDpCount() : Algorithm<T>(1), result_(0) {}
  void AddEntry(const T& t) override { ++result_; }

  absl::StatusOr<Output> GenerateResult(
      double /*noise_interval_level*/) override {
    return MakeOutput<int64_t>(result_);
  }
  void ResetState() override { result_ = 0; }

  Summary Serialize() const override { return Summary(); }
  absl::Status Merge(const Summary& summary) override {
    return absl::OkStatus();
  }
  int64_t MemoryUsed() override { return sizeof(NonDpCount<T>); };

 private:
  int64_t result_;
};

// A version of BoundedSum where Epsilon() is overridden to report half of the
// actual epsilon value, so we have an algorithm that claims stronger privacy
// guarantees than it actually provides.
template <typename T,
          typename std::enable_if<std::is_integral<T>::value ||
                                  std::is_floating_point<T>::value>::type* =
              nullptr>
class BoundedSumWithInsufficientNoise : public BoundedSumWithFixedBounds<T> {
 public:
  BoundedSumWithInsufficientNoise(
      const double epsilon, const double delta, const T lower, const T upper,
      std::unique_ptr<NumericalMechanismBuilder> mechanism_builder)
      : BoundedSumWithFixedBounds<T>(
            epsilon, 0, lower, upper,
            BoundedSum<T>::BuildMechanism(std::move(mechanism_builder), epsilon,
                                          delta, 1, 1, lower, upper)
                .value()) {}
  double GetEpsilon() const override { return Algorithm<T>::GetEpsilon() / 2; }
};

// BoundedSum but it returns a error status with a fixed probability.
template <typename T,
          typename std::enable_if<std::is_integral<T>::value ||
                                  std::is_floating_point<T>::value>::type* =
              nullptr>
class BoundedSumWithError : public BoundedSumWithFixedBounds<T> {
 public:
  BoundedSumWithError(
      const double epsilon, const double delta, const T lower, const T upper,
      std::unique_ptr<NumericalMechanismBuilder> mechanism_builder)
      : BoundedSumWithFixedBounds<T>(
            epsilon, delta, lower, upper,
            BoundedSum<T>::BuildMechanism(mechanism_builder->Clone(), epsilon,
                                          delta, 1, 1, lower, upper)
                .value()) {}

  absl::StatusOr<Output> GenerateResult(double noise_interval_level) override {
    if (UniformDouble() < 0.25) {
      return absl::InvalidArgumentError("BoundedSumWithError returns error.");
    }
    return BoundedSumWithFixedBounds<T>::GenerateResult(noise_interval_level);
  }
};

// Count but returns error without dp for some results.
template <typename T>
class CountNoDpError : public Count<T> {
 public:
  explicit CountNoDpError(double epsilon,
                          std::unique_ptr<NumericalMechanism> laplace_mechanism)
      : Count<T>(epsilon, 0, std::move(laplace_mechanism)) {}

  absl::StatusOr<Output> GenerateResult(double noise_interval_level) override {
    if (Count<T>::GetCount() == 0) {
      return absl::InvalidArgumentError("CountNoDpError returns error.");
    }
    return Count<T>::GenerateResult(noise_interval_level);
  }
};

// Trivial class that only returns error.
template <typename T,
          typename std::enable_if<std::is_integral<T>::value ||
                                  std::is_floating_point<T>::value>::type* =
              nullptr>
class AlwaysError : public Algorithm<T> {
 public:
  AlwaysError() : Algorithm<T>(1), result_(0) {}
  void AddEntry(const T& t) override {}

  absl::StatusOr<Output> GenerateResult(
      double /*noise_interval_level*/) override {
    return absl::InvalidArgumentError("AlwaysError returns error.");
  }
  void ResetState() override {}

  Summary Serialize() const override { return Summary(); }
  absl::Status Merge(const Summary& summary) override {
    return absl::OkStatus();
  }
  int64_t MemoryUsed() override { return sizeof(AlwaysError<T>); };

 private:
  T result_;
};

TEST(StochasticTesterTest, SingleDatasetBoundedSumTest) {
  auto sequence = std::make_unique<HaltonSequence<double>>(
      DefaultDatasetSize(), true /* sorted_only */, DefaultDataScale(),
      DefaultDataOffset());
  absl::StatusOr<std::unique_ptr<BoundedSum<double>>> algorithm =
      BoundedSum<double>::Builder()
          .SetLaplaceMechanism(
              std::make_unique<test_utils::SeededLaplaceMechanism::Builder>())
          .SetEpsilon(std::log(3))
          .SetLower(sequence->RangeMin())
          .SetUpper(sequence->RangeMax())
          .Build();
  ASSERT_TRUE(algorithm.ok());
  StochasticTester<double> tester(std::move(*algorithm), std::move(sequence),
                                  /*num_datasets=*/1,
                                  DefaultNumSamplesPerHistogram());
  EXPECT_TRUE(tester.Run());
}

TEST(StochasticTesterTest, SingleDatasetNonDpSumTest) {
  auto sequence = std::make_unique<HaltonSequence<double>>(
      DefaultDatasetSize(), true /* sorted_only */, DefaultDataScale(),
      DefaultDataOffset());
  auto algorithm = std::make_unique<NonDpSum<double>>();
  StochasticTester<double> tester(std::move(algorithm), std::move(sequence),
                                  /*num_datasets=*/1,
                                  DefaultNumSamplesPerHistogram());
  EXPECT_FALSE(tester.Run());
}

TEST(StochasticTesterTest, EmptySamplesCountTest) {
  std::vector<std::vector<double>> datasets({{1.0}});
  auto sequence = std::make_unique<StoredSequence<double>>(datasets);
  absl::StatusOr<std::unique_ptr<Count<double>>> algorithm =
      Count<double>::Builder()
          .SetLaplaceMechanism(
              std::make_unique<test_utils::SeededLaplaceMechanism::Builder>())
          .SetEpsilon(std::log(3))
          .Build();
  ASSERT_TRUE(algorithm.ok());
  StochasticTester<double, int64_t> tester(
      std::move(*algorithm), std::move(sequence),
      /*num_datasets=*/1, /*num_samples_per_histogram=*/0);
  EXPECT_TRUE(tester.Run());
}

TEST(StochasticTesterTest, SingleDatasetCountTest) {
  std::vector<std::vector<double>> datasets({{1.0, 2.0, 3.0}});
  auto sequence = std::make_unique<StoredSequence<double>>(datasets);
  absl::StatusOr<std::unique_ptr<Count<double>>> algorithm =
      Count<double>::Builder()
          .SetLaplaceMechanism(
              std::make_unique<test_utils::SeededLaplaceMechanism::Builder>())
          .SetEpsilon(std::log(3))
          .Build();
  ASSERT_TRUE(algorithm.ok());
  StochasticTester<double, int64_t> tester(
      std::move(*algorithm), std::move(sequence),
      /*num_datasets=*/1, DefaultNumSamplesPerHistogram());
  EXPECT_TRUE(tester.Run());
}

TEST(StochasticTesterTest, SingleDatasetNonDpCountTest) {
  std::vector<std::vector<double>> datasets({{1.0, 2.0, 3.0}});
  auto sequence = std::make_unique<StoredSequence<double>>(datasets);
  auto algorithm = std::make_unique<NonDpCount<double>>();
  StochasticTester<double, int64_t> tester(
      std::move(algorithm), std::move(sequence),
      /*num_datasets=*/1, DefaultNumSamplesPerHistogram());
  EXPECT_FALSE(tester.Run());
}

TEST(StochasticTesterTest, SingleDatasetCountNoBranchingTest) {
  std::vector<std::vector<double>> datasets({{1.0, 2.0, 3.0}});
  auto sequence = std::make_unique<StoredSequence<double>>(datasets);
  absl::StatusOr<std::unique_ptr<Count<double>>> algorithm =
      Count<double>::Builder()
          .SetLaplaceMechanism(
              std::make_unique<test_utils::SeededLaplaceMechanism::Builder>())
          .SetEpsilon(std::log(3))
          .Build();
  ASSERT_TRUE(algorithm.ok());
  StochasticTester<double, int64_t> tester(
      std::move(*algorithm), std::move(sequence),
      /*num_datasets=*/1, DefaultNumSamplesPerHistogram(),
      /*disable_search_branching=*/true);
  EXPECT_TRUE(tester.Run());
}

TEST(StochasticTesterTest, SingleDatasetNonDpCountNoBranchingTest) {
  std::vector<std::vector<double>> datasets({{1.0, 2.0, 3.0}});
  auto sequence = std::make_unique<StoredSequence<double>>(datasets);
  auto algorithm = std::make_unique<NonDpCount<double>>();
  StochasticTester<double, int64_t> tester(
      std::move(algorithm), std::move(sequence),
      /*num_datasets=*/1, DefaultNumSamplesPerHistogram(),
      /*disable_search_branching=*/true);
  EXPECT_FALSE(tester.Run());
}

TEST(StochasticTesterTest, MultipleDatasetBoundedSumTest) {
  auto sequence = std::make_unique<HaltonSequence<double>>(
      DefaultDatasetSize(), /*sorted_only=*/true, DefaultDataScale(),
      DefaultDataOffset());
  absl::StatusOr<std::unique_ptr<BoundedSum<double>>> algorithm =
      BoundedSum<double>::Builder()
          .SetLaplaceMechanism(
              std::make_unique<test_utils::SeededLaplaceMechanism::Builder>())
          .SetEpsilon(std::log(3))
          .SetLower(sequence->RangeMin())
          .SetUpper(sequence->RangeMax())
          .Build();
  ASSERT_TRUE(algorithm.ok());
  StochasticTester<double, int64_t> tester(std::move(*algorithm),
                                         std::move(sequence));
  EXPECT_TRUE(tester.Run());
}

TEST(StochasticTesterTest, MultipleDatasetBoundedSumWithInsufficientNoiseTest) {
  auto sequence = std::make_unique<HaltonSequence<double>>(
      DefaultDatasetSize(), /*sorted_only=*/true, DefaultDataScale(),
      DefaultDataOffset());
  auto mechanism_builder =
      std::make_unique<test_utils::SeededLaplaceMechanism::Builder>();
  auto algorithm = std::make_unique<BoundedSumWithInsufficientNoise<double>>(
      std::log(3), 0, sequence->RangeMin(), sequence->RangeMax(),
      std::move(mechanism_builder));
  StochasticTester<double> tester(std::move(algorithm), std::move(sequence));
  EXPECT_FALSE(tester.Run());
}

TEST(StochasticTesterTest, ReplaceErrorWithValue) {
  auto sequence = std::make_unique<HaltonSequence<double>>(
      DefaultDatasetSize(), /*sorted_only=*/true, DefaultDataScale(),
      DefaultDataOffset());
  auto mechanism_builder =
      std::make_unique<test_utils::SeededLaplaceMechanism::Builder>();
  auto algorithm = std::make_unique<BoundedSumWithError<double>>(
      std::log(3), 0, sequence->RangeMin(), sequence->RangeMax(),
      std::move(mechanism_builder));
  StochasticTester<double> tester(std::move(algorithm), std::move(sequence));
  EXPECT_TRUE(tester.Run());
}

// Test an algorithm that throws error deterministically.
TEST(StochasticTesterTest, ErrorStatusWithoutDP) {
  const double epsilon = std::log(3);
  auto sequence = std::make_unique<HaltonSequence<int64_t>>(
      DefaultDatasetSize(), /*sorted_only=*/true, DefaultDataScale(),
      DefaultDataOffset());
  auto mechanism = LaplaceMechanism::Builder().SetEpsilon(epsilon).Build();
  ASSERT_TRUE(mechanism.ok());
  auto algorithm =
      std::make_unique<CountNoDpError<int64_t>>(epsilon, std::move(*mechanism));
  StochasticTester<int64_t> tester(std::move(algorithm), std::move(sequence));
  EXPECT_FALSE(tester.Run());
}

// Test a class that always determines error.
TEST(StochasticTesterTest, AllError) {
  auto sequence = std::make_unique<HaltonSequence<double>>(
      DefaultDatasetSize(), /*sorted_only=*/true, DefaultDataScale(),
      DefaultDataOffset());
  auto algorithm = std::make_unique<AlwaysError<double>>();
  StochasticTester<double> tester(std::move(algorithm), std::move(sequence));
  EXPECT_TRUE(tester.Run());
}

}  // namespace
}  // namespace testing
}  // namespace differential_privacy