| // |
| // 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 "algorithms/util.h" |
| |
| #include <limits> |
| |
| #include "gtest/gtest.h" |
| #include "base/status.h" |
| #include "algorithms/distributions.h" |
| #include "algorithms/numerical-mechanisms-testing.h" |
| |
| namespace differential_privacy { |
| namespace { |
| |
| const char kSeedString[] = "ABCDEFGHIJKLMNOP"; |
| constexpr int64_t kStatsSize = 50000; |
| constexpr double kTolerance = 1e-5; |
| |
| TEST(XorStringsTest, XorsSameLength) { |
| std::string first = "foo"; |
| std::string second = "bar"; |
| |
| std::string result = XorStrings(first, second); |
| |
| EXPECT_EQ('f' ^ 'b', result[0]); |
| EXPECT_EQ('o' ^ 'a', result[1]); |
| EXPECT_EQ('o' ^ 'r', result[2]); |
| } |
| |
| TEST(XorStringsTest, ShorterStringRepeated) { |
| std::string first = "foobar"; |
| std::string second = "baz"; |
| |
| std::string result = XorStrings(first, second); |
| |
| EXPECT_EQ('b' ^ 'b', result[3]); |
| EXPECT_EQ('a' ^ 'a', result[4]); |
| EXPECT_EQ('z' ^ 'r', result[5]); |
| } |
| |
| TEST(XorStringsTest, EmptyStringReturnsUnchanged) { |
| std::string first = "foo"; |
| std::string second = ""; |
| |
| std::string result = XorStrings(first, second); |
| |
| EXPECT_EQ(result, "foo"); |
| } |
| |
| TEST(XorStringsTest, DoubleEmptyString) { |
| std::string first = ""; |
| std::string second = ""; |
| |
| std::string result = XorStrings(first, second); |
| |
| EXPECT_EQ(result, ""); |
| } |
| |
| TEST(EpsilonRiskValuesTest, DefaultEpsilon) { |
| EXPECT_EQ(DefaultEpsilon(), std::log(3)); |
| } |
| |
| TEST(NextPowerTest, PositivesPowers) { |
| EXPECT_NEAR(GetNextPowerOfTwo(3.0), 4.0, kTolerance); |
| EXPECT_NEAR(GetNextPowerOfTwo(5.0), 8.0, kTolerance); |
| EXPECT_NEAR(GetNextPowerOfTwo(7.9), 8.0, kTolerance); |
| } |
| |
| TEST(NextPowerTest, ExactPositivePowers) { |
| EXPECT_NEAR(GetNextPowerOfTwo(2.0), 2.0, kTolerance); |
| EXPECT_NEAR(GetNextPowerOfTwo(8.0), 8.0, kTolerance); |
| } |
| |
| TEST(NextPowerTest, One) { |
| EXPECT_NEAR(GetNextPowerOfTwo(1.0), 1.0, kTolerance); |
| } |
| |
| TEST(NextPowerTest, NegativePowers) { |
| EXPECT_NEAR(GetNextPowerOfTwo(0.4), 0.5, kTolerance); |
| EXPECT_NEAR(GetNextPowerOfTwo(0.2), 0.25, kTolerance); |
| } |
| |
| TEST(NextPowerTest, ExactNegativePowers) { |
| EXPECT_NEAR(GetNextPowerOfTwo(0.5), 0.5, kTolerance); |
| EXPECT_NEAR(GetNextPowerOfTwo(0.125), 0.125, kTolerance); |
| } |
| |
| TEST(InverseErrorTest, ProperResults) { |
| // true values are pre-calculated |
| EXPECT_NEAR(InverseErrorFunction(0.24), 0.216, 0.001); |
| EXPECT_NEAR(InverseErrorFunction(0.9999), 2.751, 0.001); |
| EXPECT_NEAR(InverseErrorFunction(0.0012), 0.001, 0.001); |
| EXPECT_NEAR(InverseErrorFunction(0.5), 0.476, 0.001); |
| EXPECT_NEAR(InverseErrorFunction(0.39), 0.360, 0.001); |
| EXPECT_NEAR(InverseErrorFunction(0.0067), 0.0059, 0.001); |
| |
| double max = 1; |
| double min = -1; |
| for (int i = 0; i < 1000; i++) { |
| double n = (max - min) * ((double)rand() / RAND_MAX) + min; |
| EXPECT_NEAR(std::erf(InverseErrorFunction(n)), n, 0.001); |
| } |
| } |
| |
| TEST(InverseErrorTest, EdgeCases) { |
| EXPECT_EQ(InverseErrorFunction(-1), |
| -1 * std::numeric_limits<double>::infinity()); |
| EXPECT_EQ(InverseErrorFunction(1), std::numeric_limits<double>::infinity()); |
| EXPECT_EQ(InverseErrorFunction(0), 0); |
| } |
| |
| // In RoundToNearestMultiple tests exact comparison of double is used, because |
| // for rounding to multiple of power of 2 RoundToNearestMultiple should provide |
| // exact value. |
| TEST(RoundTest, PositiveNoTies) { |
| EXPECT_EQ(RoundToNearestMultiple(4.9, 2.0), 4.0); |
| EXPECT_EQ(RoundToNearestMultiple(5.1, 2.0), 6.0); |
| } |
| |
| TEST(RoundTest, NegativesNoTies) { |
| EXPECT_EQ(RoundToNearestMultiple(-4.9, 2.0), -4.0); |
| EXPECT_EQ(RoundToNearestMultiple(-5.1, 2.0), -6.0); |
| } |
| |
| TEST(RoundTest, PositiveTies) { |
| EXPECT_EQ(RoundToNearestMultiple(5.0, 2.0), 6.0); |
| } |
| |
| TEST(RoundTest, NegativeTies) { |
| EXPECT_EQ(RoundToNearestMultiple(-5.0, 2.0), -4.0); |
| } |
| |
| TEST(RoundTest, NegativePowerOf2) { |
| EXPECT_EQ(RoundToNearestMultiple(0.2078795763, 0.25), 0.25); |
| EXPECT_EQ(RoundToNearestMultiple(0.1, 1.0 / (1 << 10)), 0.099609375); |
| EXPECT_EQ(RoundToNearestMultiple(0.3, 1.0 / (1 << 30)), |
| 322122547.0 / (1 << 30)); |
| } |
| |
| TEST(QnormTest, InvalidProbability) { |
| EXPECT_EQ(Qnorm(-0.1).status().code(), base::StatusCode::kInvalidArgument); |
| EXPECT_EQ(Qnorm(0).status().code(), base::StatusCode::kInvalidArgument); |
| EXPECT_EQ(Qnorm(1).status().code(), base::StatusCode::kInvalidArgument); |
| EXPECT_EQ(Qnorm(2).status().code(), base::StatusCode::kInvalidArgument); |
| } |
| TEST(QnormTest, Accuracy) { |
| double theoretical_accuracy = 4.5 * std::pow(10, -4); |
| std::vector<double> p = {0.0000001, 0.00001, 0.001, 0.05, 0.15, 0.25, |
| 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, |
| 0.95, 0.999, 0.99999, 0.9999999}; |
| std::vector<double> exact = { |
| -5.199337582187471, -4.264890793922602, -3.090232306167813, |
| -1.6448536269514729, -1.0364333894937896, -0.6744897501960817, |
| -0.38532046640756773, -0.12566134685507402, 0.12566134685507402, |
| 0.38532046640756773, 0.6744897501960817, 1.0364333894937896, |
| 1.6448536269514729, 3.090232306167813, 4.264890793922602, |
| 5.199337582187471}; |
| for (int i = 0; i < p.size(); ++i) { |
| EXPECT_LE(std::abs(exact[i] - Qnorm(p[i]).ValueOrDie()), |
| theoretical_accuracy); |
| } |
| } |
| |
| TEST(ClampTest, DefaultTest) { |
| EXPECT_EQ(Clamp(1, 3, 2), 2); |
| EXPECT_EQ(Clamp(1.0, 3.0, 4.0), 3); |
| EXPECT_EQ(Clamp(1.0, 3.0, -2.0), 1); |
| } |
| |
| TEST(SafeOperationsTest, SafeAddInt) { |
| int64_t int_result; |
| EXPECT_TRUE(SafeAdd<int64_t>(10, 20, &int_result)); |
| EXPECT_EQ(int_result, 30); |
| EXPECT_TRUE(SafeAdd<int64_t>(std::numeric_limits<int64_t>::max(), |
| std::numeric_limits<int64_t>::lowest(), |
| &int_result)); |
| EXPECT_EQ(int_result, -1); |
| EXPECT_FALSE( |
| SafeAdd<int64_t>(std::numeric_limits<int64_t>::max(), 1, &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::max()); |
| EXPECT_FALSE( |
| SafeAdd<int64_t>(std::numeric_limits<int64_t>::lowest(), -1, &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| EXPECT_TRUE( |
| SafeAdd<int64_t>(std::numeric_limits<int64_t>::lowest(), 0, &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| } |
| |
| TEST(SafeOperationsTest, SafeAddDouble) { |
| double double_result; |
| EXPECT_TRUE(SafeAdd<double>(10, 20, &double_result)); |
| EXPECT_EQ(double_result, 30); |
| EXPECT_TRUE(SafeAdd<double>(std::numeric_limits<double>::max(), |
| std::numeric_limits<double>::lowest(), |
| &double_result)); |
| EXPECT_FLOAT_EQ(double_result, 0); |
| EXPECT_TRUE( |
| SafeAdd<double>(std::numeric_limits<double>::max(), 1.0, &double_result)); |
| EXPECT_FLOAT_EQ(double_result, std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeAdd<double>(std::numeric_limits<double>::lowest(), -1.0, |
| &double_result)); |
| EXPECT_FLOAT_EQ(double_result, -std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeAdd<double>(std::numeric_limits<double>::lowest(), 0.0, |
| &double_result)); |
| EXPECT_EQ(double_result, std::numeric_limits<double>::lowest()); |
| } |
| |
| TEST(SafeOperationsTest, SafeSubtractInt) { |
| int64_t int_result; |
| EXPECT_TRUE(SafeSubtract<int64_t>(10, 20, &int_result)); |
| EXPECT_EQ(int_result, -10); |
| EXPECT_FALSE(SafeSubtract<int64_t>(1, std::numeric_limits<int64_t>::lowest(), |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| EXPECT_TRUE(SafeSubtract<int64_t>(-1, std::numeric_limits<int64_t>::lowest(), |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::max()); |
| EXPECT_TRUE(SafeSubtract<int64_t>(std::numeric_limits<int64_t>::lowest(), |
| std::numeric_limits<int64_t>::lowest(), |
| &int_result)); |
| EXPECT_EQ(int_result, 0); |
| |
| uint64_t uint_result; |
| EXPECT_TRUE(SafeSubtract<uint64_t>(1, std::numeric_limits<uint64_t>::lowest(), |
| &uint_result)); |
| EXPECT_EQ(uint_result, 1); |
| } |
| |
| TEST(SafeOperationsTest, SafeSubtractDouble) { |
| double double_result; |
| EXPECT_TRUE(SafeSubtract<double>(10.0, 20.0, &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, -10.0); |
| EXPECT_TRUE(SafeSubtract<double>(1.0, std::numeric_limits<double>::lowest(), |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeSubtract<double>(-1.0, std::numeric_limits<double>::lowest(), |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeSubtract<double>(std::numeric_limits<double>::lowest(), |
| std::numeric_limits<double>::lowest(), |
| &double_result)); |
| EXPECT_EQ(double_result, 0); |
| } |
| |
| TEST(SafeOperationsTest, SafeMultiplyInt) { |
| int64_t int_result; |
| |
| EXPECT_TRUE(SafeMultiply<int64_t>(1, 1, &int_result)); |
| EXPECT_EQ(int_result, 1); |
| EXPECT_TRUE(SafeMultiply<int64_t>(-1, 1, &int_result)); |
| EXPECT_EQ(int_result, -1); |
| EXPECT_TRUE(SafeMultiply<int64_t>(1, -1, &int_result)); |
| EXPECT_EQ(int_result, -1); |
| EXPECT_TRUE(SafeMultiply<int64_t>(-1, -1, &int_result)); |
| EXPECT_EQ(int_result, 1); |
| EXPECT_TRUE(SafeMultiply<int64_t>(10, -20, &int_result)); |
| EXPECT_EQ(int_result, -200); |
| |
| EXPECT_FALSE(SafeMultiply<int64_t>(std::numeric_limits<int64_t>::max(), |
| std::numeric_limits<int64_t>::lowest(), |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| EXPECT_FALSE(SafeMultiply<int64_t>(std::numeric_limits<int64_t>::lowest(), |
| std::numeric_limits<int64_t>::max(), |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| |
| EXPECT_FALSE( |
| SafeMultiply<int64_t>(std::numeric_limits<int64_t>::max(), 2, &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::max()); |
| EXPECT_FALSE(SafeMultiply<int64_t>(std::numeric_limits<int64_t>::lowest(), -2, |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::max()); |
| |
| EXPECT_FALSE( |
| SafeMultiply<int64_t>(std::numeric_limits<int64_t>::max(), -2, &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| EXPECT_FALSE( |
| SafeMultiply<int64_t>(-2, std::numeric_limits<int64_t>::max(), &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| |
| EXPECT_FALSE(SafeMultiply<int64_t>(std::numeric_limits<int64_t>::lowest(), 2, |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| EXPECT_FALSE(SafeMultiply<int64_t>(2, std::numeric_limits<int64_t>::lowest(), |
| &int_result)); |
| EXPECT_EQ(int_result, std::numeric_limits<int64_t>::lowest()); |
| |
| EXPECT_TRUE(SafeMultiply<int64_t>(std::numeric_limits<int64_t>::lowest(), 0, |
| &int_result)); |
| EXPECT_EQ(int_result, 0); |
| EXPECT_TRUE( |
| SafeMultiply<int64_t>(0, std::numeric_limits<int64_t>::max(), &int_result)); |
| EXPECT_EQ(int_result, 0); |
| } |
| |
| TEST(SafeOperationsTest, SafeMultiplyDouble) { |
| double double_result; |
| EXPECT_TRUE(SafeMultiply<double>(1.0, 1.0, &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, 1.0); |
| EXPECT_TRUE(SafeMultiply<double>(-1.0, 1.0, &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, -1.0); |
| EXPECT_TRUE(SafeMultiply<double>(1.0, -1.0, &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, -1.0); |
| EXPECT_TRUE(SafeMultiply<double>(-1.0, -1.0, &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, 1.0); |
| EXPECT_TRUE(SafeMultiply<double>(10.0, -20.0, &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, -200.0); |
| EXPECT_TRUE(SafeMultiply<double>(std::numeric_limits<double>::max(), |
| std::numeric_limits<double>::lowest(), |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, std::numeric_limits<double>::max() * |
| std::numeric_limits<double>::lowest()); |
| EXPECT_TRUE(SafeMultiply<double>(std::numeric_limits<double>::max(), 2.0, |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeMultiply<double>(std::numeric_limits<double>::max(), -2.0, |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, -std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeMultiply<double>(std::numeric_limits<double>::lowest(), -2.0, |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeMultiply<double>(std::numeric_limits<double>::lowest(), 2.0, |
| &double_result)); |
| EXPECT_DOUBLE_EQ(double_result, -std::numeric_limits<double>::infinity()); |
| EXPECT_TRUE(SafeMultiply<double>(std::numeric_limits<double>::lowest(), 0.0, |
| &double_result)); |
| EXPECT_EQ(double_result, 0); |
| EXPECT_TRUE(SafeMultiply<double>(0.0, std::numeric_limits<double>::max(), |
| &double_result)); |
| EXPECT_EQ(double_result, 0); |
| } |
| |
| TEST(SafeOperationsTest, SafeSquare) { |
| int64_t int_result; |
| EXPECT_TRUE(SafeSquare<int64_t>(-9, &int_result)); |
| EXPECT_EQ(int_result, 81); |
| EXPECT_FALSE( |
| SafeSquare<int64_t>(std::numeric_limits<int64_t>::max() - 1, &int_result)); |
| EXPECT_FALSE( |
| SafeSquare<int64_t>(std::numeric_limits<int64_t>::lowest() + 1, &int_result)); |
| EXPECT_FALSE( |
| SafeSquare<int64_t>(std::numeric_limits<int64_t>::lowest(), &int_result)); |
| |
| uint64_t uint_result; |
| EXPECT_TRUE( |
| SafeSquare<uint64_t>(std::numeric_limits<uint64_t>::lowest(), &uint_result)); |
| } |
| |
| TEST(StatisticsTest, VectorStatistics) { |
| std::vector<double> a = {1, 5, 7, 9, 13}; |
| EXPECT_EQ(Mean(a), 7); |
| EXPECT_EQ(Variance(a), 16); |
| EXPECT_EQ(StandardDev(a), 4); |
| EXPECT_EQ(OrderStatistic(.60, a), 8); |
| EXPECT_EQ(OrderStatistic(0, a), 1); |
| EXPECT_EQ(OrderStatistic(1, a), 13); |
| } |
| |
| TEST(VectorUtilTest, VectorFilter) { |
| std::vector<double> v = {1, 2, 2, 3}; |
| std::vector<bool> selection = {false, true, true, false}; |
| std::vector<double> expected = {2, 2}; |
| EXPECT_THAT(VectorFilter(v, selection), testing::ContainerEq(expected)); |
| } |
| |
| TEST(VectorUtilTest, VectorToString) { |
| std::vector<double> v = {1, 2, 2, 3}; |
| EXPECT_EQ(VectorToString(v), "[1, 2, 2, 3]"); |
| } |
| |
| TEST(SafeCastFromDoubleTest, Converts20ToIntegral) { |
| int64_t integral = 345; |
| EXPECT_TRUE(SafeCastFromDouble(20.0, integral)); |
| EXPECT_EQ(integral, 20); |
| } |
| |
| TEST(SafeCastFromDoubleTest, ConvertsHighValueToMaxIntegral) { |
| int64_t integral = 345; |
| EXPECT_TRUE(SafeCastFromDouble(1.0e200, integral)); |
| EXPECT_EQ(integral, std::numeric_limits<int64_t>::max()); |
| } |
| |
| TEST(SafeCastFromDoubleTest, ConvertsLowValueToLowestIntegral) { |
| int64_t integral = 345; |
| EXPECT_TRUE(SafeCastFromDouble(-1.0e200, integral)); |
| EXPECT_EQ(integral, std::numeric_limits<int64_t>::lowest()); |
| } |
| |
| TEST(SafeCastFromDoubleTest, ReturnsFalseOnNanForIntegrals) { |
| int64_t integral = 345; |
| EXPECT_FALSE(SafeCastFromDouble(NAN, integral)); |
| EXPECT_EQ(integral, 345); |
| } |
| |
| // Combine all tests for float outputs. Should be nothing unexpected here since |
| // this is just a cast from double to float. |
| TEST(SafeCastFromDoubleTest, ForFloat) { |
| float floating_point; |
| |
| // Normal case. |
| EXPECT_TRUE(SafeCastFromDouble(0.5, floating_point)); |
| EXPECT_EQ(floating_point, 0.5); |
| |
| // NaN double should convert into NaN float. |
| EXPECT_TRUE(SafeCastFromDouble(NAN, floating_point)); |
| EXPECT_TRUE(std::isnan(floating_point)); |
| |
| // High double should convert into infinite float. |
| EXPECT_TRUE(SafeCastFromDouble(1.0e200, floating_point)); |
| EXPECT_TRUE(std::isinf(floating_point)); |
| } |
| |
| } // namespace |
| } // namespace differential_privacy |
