entropy_provider_unittest.cc 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/variations/entropy_provider.h"
  5. #include <stddef.h>
  6. #include <stdint.h>
  7. #include <cmath>
  8. #include <limits>
  9. #include <memory>
  10. #include <numeric>
  11. #include "base/guid.h"
  12. #include "base/rand_util.h"
  13. #include "base/strings/string_number_conversions.h"
  14. #include "base/test/scoped_feature_list.h"
  15. #include "components/variations/hashing.h"
  16. #include "testing/gtest/include/gtest/gtest.h"
  17. namespace variations {
  18. namespace {
  19. // Size of the low entropy source for testing.
  20. const size_t kMaxLowEntropySize = 8000;
  21. // Field trial names used in unit tests.
  22. const char* const kTestTrialNames[] = { "TestTrial", "AnotherTestTrial",
  23. "NewTabButton" };
  24. // Computes the Chi-Square statistic for |values| assuming they follow a uniform
  25. // distribution, where each entry has expected value |expected_value|.
  26. //
  27. // The Chi-Square statistic is defined as Sum((O-E)^2/E) where O is the observed
  28. // value and E is the expected value.
  29. double ComputeChiSquare(const std::vector<int>& values,
  30. double expected_value) {
  31. double sum = 0;
  32. for (size_t i = 0; i < values.size(); ++i) {
  33. const double delta = values[i] - expected_value;
  34. sum += (delta * delta) / expected_value;
  35. }
  36. return sum;
  37. }
  38. // Computes SHA1-based entropy for the given |trial_name| based on
  39. // |entropy_source|
  40. double GenerateSHA1Entropy(const std::string& entropy_source,
  41. const std::string& trial_name) {
  42. SHA1EntropyProvider sha1_provider(entropy_source);
  43. return sha1_provider.GetEntropyForTrial(trial_name, 0);
  44. }
  45. // Generates normalized MurmurHash-based entropy for the given |trial_name|
  46. // based on |entropy_source| which must be in the range [0, entropy_max).
  47. double GenerateNormalizedMurmurHashEntropy(uint16_t entropy_source,
  48. size_t entropy_max,
  49. const std::string& trial_name) {
  50. NormalizedMurmurHashEntropyProvider provider(entropy_source, entropy_max);
  51. return provider.GetEntropyForTrial(trial_name, 0);
  52. }
  53. // Helper interface for testing used to generate entropy values for a given
  54. // field trial. Unlike EntropyProvider, which keeps the low/high entropy source
  55. // value constant and generates entropy for different trial names, instances
  56. // of TrialEntropyGenerator keep the trial name constant and generate low/high
  57. // entropy source values internally to produce each output entropy value.
  58. class TrialEntropyGenerator {
  59. public:
  60. virtual ~TrialEntropyGenerator() {}
  61. virtual double GenerateEntropyValue() const = 0;
  62. };
  63. // An TrialEntropyGenerator that uses the SHA1EntropyProvider with the high
  64. // entropy source (random GUID with 128 bits of entropy + 13 additional bits of
  65. // entropy corresponding to a low entropy source).
  66. class SHA1EntropyGenerator : public TrialEntropyGenerator {
  67. public:
  68. explicit SHA1EntropyGenerator(const std::string& trial_name)
  69. : trial_name_(trial_name) {
  70. }
  71. SHA1EntropyGenerator(const SHA1EntropyGenerator&) = delete;
  72. SHA1EntropyGenerator& operator=(const SHA1EntropyGenerator&) = delete;
  73. ~SHA1EntropyGenerator() override {}
  74. double GenerateEntropyValue() const override {
  75. // Use a random GUID + 13 additional bits of entropy to match how the
  76. // SHA1EntropyProvider is used in metrics_service.cc.
  77. const int low_entropy_source =
  78. static_cast<uint16_t>(base::RandInt(0, kMaxLowEntropySize - 1));
  79. const std::string high_entropy_source =
  80. base::GenerateGUID() + base::NumberToString(low_entropy_source);
  81. return GenerateSHA1Entropy(high_entropy_source, trial_name_);
  82. }
  83. private:
  84. const std::string trial_name_;
  85. };
  86. // An TrialEntropyGenerator that uses the normalized MurmurHash entropy provider
  87. // algorithm, using 13-bit low entropy source values.
  88. class NormalizedMurmurHashEntropyGenerator : public TrialEntropyGenerator {
  89. public:
  90. explicit NormalizedMurmurHashEntropyGenerator(const std::string& trial_name)
  91. : trial_name_(trial_name) {}
  92. NormalizedMurmurHashEntropyGenerator(
  93. const NormalizedMurmurHashEntropyGenerator&) = delete;
  94. NormalizedMurmurHashEntropyGenerator& operator=(
  95. const NormalizedMurmurHashEntropyGenerator&) = delete;
  96. ~NormalizedMurmurHashEntropyGenerator() override {}
  97. double GenerateEntropyValue() const override {
  98. const int low_entropy_source =
  99. static_cast<uint16_t>(base::RandInt(0, kMaxLowEntropySize - 1));
  100. return GenerateNormalizedMurmurHashEntropy(low_entropy_source,
  101. kMaxLowEntropySize, trial_name_);
  102. }
  103. private:
  104. const std::string trial_name_;
  105. };
  106. // Tests uniformity of a given |entropy_generator| using the Chi-Square Goodness
  107. // of Fit Test.
  108. void PerformEntropyUniformityTest(
  109. const std::string& trial_name,
  110. const TrialEntropyGenerator& entropy_generator) {
  111. // Number of buckets in the simulated field trials.
  112. const size_t kBucketCount = 20;
  113. // Max number of iterations to perform before giving up and failing.
  114. const size_t kMaxIterationCount = 100000;
  115. // The number of iterations to perform before each time the statistical
  116. // significance of the results is checked.
  117. const size_t kCheckIterationCount = 10000;
  118. // This is the Chi-Square threshold from the Chi-Square statistic table for
  119. // 19 degrees of freedom (based on |kBucketCount|) with a 99.9% confidence
  120. // level. See: http://www.medcalc.org/manual/chi-square-table.php
  121. const double kChiSquareThreshold = 43.82;
  122. std::vector<int> distribution(kBucketCount);
  123. for (size_t i = 1; i <= kMaxIterationCount; ++i) {
  124. const double entropy_value = entropy_generator.GenerateEntropyValue();
  125. const size_t bucket = static_cast<size_t>(kBucketCount * entropy_value);
  126. ASSERT_LT(bucket, kBucketCount);
  127. distribution[bucket] += 1;
  128. // After |kCheckIterationCount| iterations, compute the Chi-Square
  129. // statistic of the distribution. If the resulting statistic is greater
  130. // than |kChiSquareThreshold|, we can conclude with 99.9% confidence
  131. // that the observed samples do not follow a uniform distribution.
  132. //
  133. // However, since 99.9% would still result in a false negative every
  134. // 1000 runs of the test, do not treat it as a failure (else the test
  135. // will be flaky). Instead, perform additional iterations to determine
  136. // if the distribution will converge, up to |kMaxIterationCount|.
  137. if ((i % kCheckIterationCount) == 0) {
  138. const double expected_value_per_bucket =
  139. static_cast<double>(i) / kBucketCount;
  140. const double chi_square =
  141. ComputeChiSquare(distribution, expected_value_per_bucket);
  142. if (chi_square < kChiSquareThreshold)
  143. break;
  144. // If |i == kMaxIterationCount|, the Chi-Square statistic did not
  145. // converge after |kMaxIterationCount|.
  146. EXPECT_NE(i, kMaxIterationCount) << "Failed for trial " <<
  147. trial_name << " with chi_square = " << chi_square <<
  148. " after " << kMaxIterationCount << " iterations.";
  149. }
  150. }
  151. }
  152. } // namespace
  153. TEST(EntropyProviderTest, UseOneTimeRandomizationSHA1) {
  154. base::test::ScopedFeatureList scoped_feature_list;
  155. scoped_feature_list.InitWithNullFeatureAndFieldTrialLists();
  156. // Simply asserts that two trials using one-time randomization
  157. // that have different names, normally generate different results.
  158. //
  159. // Note that depending on the one-time random initialization, they
  160. // _might_ actually give the same result, but we know that given the
  161. // particular client_id we use for unit tests they won't.
  162. base::FieldTrialList field_trial_list(
  163. std::make_unique<SHA1EntropyProvider>("client_id"));
  164. scoped_refptr<base::FieldTrial> trials[] = {
  165. base::FieldTrialList::FactoryGetFieldTrial(
  166. "one", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  167. nullptr),
  168. base::FieldTrialList::FactoryGetFieldTrial(
  169. "two", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  170. nullptr),
  171. };
  172. for (size_t i = 0; i < std::size(trials); ++i) {
  173. for (int j = 0; j < 100; ++j)
  174. trials[i]->AppendGroup(std::string(), 1);
  175. }
  176. // The trials are most likely to give different results since they have
  177. // different names.
  178. EXPECT_NE(trials[0]->group(), trials[1]->group());
  179. EXPECT_NE(trials[0]->group_name(), trials[1]->group_name());
  180. }
  181. TEST(EntropyProviderTest, UseOneTimeRandomizationNormalizedMurmurHash) {
  182. base::test::ScopedFeatureList scoped_feature_list;
  183. scoped_feature_list.InitWithNullFeatureAndFieldTrialLists();
  184. // Simply asserts that two trials using one-time randomization
  185. // that have different names, normally generate different results.
  186. //
  187. // Note that depending on the one-time random initialization, they
  188. // _might_ actually give the same result, but we know that given
  189. // the particular low_entropy_source we use for unit tests they won't.
  190. base::FieldTrialList field_trial_list(
  191. std::make_unique<NormalizedMurmurHashEntropyProvider>(
  192. 1234, kMaxLowEntropySize));
  193. scoped_refptr<base::FieldTrial> trials[] = {
  194. base::FieldTrialList::FactoryGetFieldTrial(
  195. "one", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  196. nullptr),
  197. base::FieldTrialList::FactoryGetFieldTrial(
  198. "two", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  199. nullptr),
  200. };
  201. for (size_t i = 0; i < std::size(trials); ++i) {
  202. for (int j = 0; j < 100; ++j)
  203. trials[i]->AppendGroup(std::string(), 1);
  204. }
  205. // The trials are most likely to give different results since they have
  206. // different names.
  207. EXPECT_NE(trials[0]->group(), trials[1]->group());
  208. EXPECT_NE(trials[0]->group_name(), trials[1]->group_name());
  209. }
  210. TEST(EntropyProviderTest, UseOneTimeRandomizationWithCustomSeedSHA1) {
  211. base::test::ScopedFeatureList scoped_feature_list;
  212. scoped_feature_list.InitWithNullFeatureAndFieldTrialLists();
  213. // Ensures that two trials with different names but the same custom seed used
  214. // for one time randomization produce the same group assignments.
  215. base::FieldTrialList field_trial_list(
  216. std::make_unique<SHA1EntropyProvider>("client_id"));
  217. const uint32_t kCustomSeed = 9001;
  218. scoped_refptr<base::FieldTrial> trials[] = {
  219. base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed(
  220. "one", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  221. kCustomSeed, nullptr, nullptr),
  222. base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed(
  223. "two", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  224. kCustomSeed, nullptr, nullptr),
  225. };
  226. for (size_t i = 0; i < std::size(trials); ++i) {
  227. for (int j = 0; j < 100; ++j)
  228. trials[i]->AppendGroup(std::string(), 1);
  229. }
  230. // Normally, these trials should produce different groups, but if the same
  231. // custom seed is used, they should produce the same group assignment.
  232. EXPECT_EQ(trials[0]->group(), trials[1]->group());
  233. EXPECT_EQ(trials[0]->group_name(), trials[1]->group_name());
  234. }
  235. TEST(EntropyProviderTest,
  236. UseOneTimeRandomizationWithCustomSeedNormalizedMurmurHash) {
  237. base::test::ScopedFeatureList scoped_feature_list;
  238. scoped_feature_list.InitWithNullFeatureAndFieldTrialLists();
  239. // Ensures that two trials with different names but the same custom seed used
  240. // for one time randomization produce the same group assignments.
  241. base::FieldTrialList field_trial_list(
  242. std::make_unique<NormalizedMurmurHashEntropyProvider>(
  243. 1234, kMaxLowEntropySize));
  244. const uint32_t kCustomSeed = 9001;
  245. scoped_refptr<base::FieldTrial> trials[] = {
  246. base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed(
  247. "one", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  248. kCustomSeed, nullptr, nullptr),
  249. base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed(
  250. "two", 100, "default", base::FieldTrial::ONE_TIME_RANDOMIZED,
  251. kCustomSeed, nullptr, nullptr),
  252. };
  253. for (size_t i = 0; i < std::size(trials); ++i) {
  254. for (int j = 0; j < 100; ++j)
  255. trials[i]->AppendGroup(std::string(), 1);
  256. }
  257. // Normally, these trials should produce different groups, but if the same
  258. // custom seed is used, they should produce the same group assignment.
  259. EXPECT_EQ(trials[0]->group(), trials[1]->group());
  260. EXPECT_EQ(trials[0]->group_name(), trials[1]->group_name());
  261. }
  262. TEST(EntropyProviderTest, SHA1Entropy) {
  263. const double results[] = { GenerateSHA1Entropy("hi", "1"),
  264. GenerateSHA1Entropy("there", "1") };
  265. EXPECT_NE(results[0], results[1]);
  266. for (size_t i = 0; i < std::size(results); ++i) {
  267. EXPECT_LE(0.0, results[i]);
  268. EXPECT_GT(1.0, results[i]);
  269. }
  270. EXPECT_EQ(GenerateSHA1Entropy("yo", "1"),
  271. GenerateSHA1Entropy("yo", "1"));
  272. EXPECT_NE(GenerateSHA1Entropy("yo", "something"),
  273. GenerateSHA1Entropy("yo", "else"));
  274. }
  275. TEST(EntropyProviderTest, NormalizedMurmurHashEntropy) {
  276. const double results[] = {
  277. GenerateNormalizedMurmurHashEntropy(1234, kMaxLowEntropySize, "1"),
  278. GenerateNormalizedMurmurHashEntropy(4321, kMaxLowEntropySize, "1")};
  279. EXPECT_NE(results[0], results[1]);
  280. for (size_t i = 0; i < std::size(results); ++i) {
  281. EXPECT_LE(0.0, results[i]);
  282. EXPECT_GT(1.0, results[i]);
  283. }
  284. EXPECT_EQ(GenerateNormalizedMurmurHashEntropy(1234, kMaxLowEntropySize, "1"),
  285. GenerateNormalizedMurmurHashEntropy(1234, kMaxLowEntropySize, "1"));
  286. EXPECT_NE(GenerateNormalizedMurmurHashEntropy(1234, kMaxLowEntropySize,
  287. "something"),
  288. GenerateNormalizedMurmurHashEntropy(1234, kMaxLowEntropySize,
  289. "else"));
  290. }
  291. TEST(EntropyProviderTest, NormalizedMurmurHashEntropyProviderResults) {
  292. // Verifies that NormalizedMurmurHashEntropyProvider produces expected
  293. // results. This ensures that the results are the same between platforms and
  294. // ensures that changes to the implementation do not regress this
  295. // accidentally.
  296. EXPECT_DOUBLE_EQ(
  297. 1612 / static_cast<double>(kMaxLowEntropySize),
  298. GenerateNormalizedMurmurHashEntropy(1234, kMaxLowEntropySize, "XYZ"));
  299. EXPECT_DOUBLE_EQ(
  300. 7066 / static_cast<double>(kMaxLowEntropySize),
  301. GenerateNormalizedMurmurHashEntropy(1, kMaxLowEntropySize, "Test"));
  302. EXPECT_DOUBLE_EQ(
  303. 5668 / static_cast<double>(kMaxLowEntropySize),
  304. GenerateNormalizedMurmurHashEntropy(5000, kMaxLowEntropySize, "Foo"));
  305. }
  306. TEST(EntropyProviderTest, SHA1EntropyIsUniform) {
  307. for (size_t i = 0; i < std::size(kTestTrialNames); ++i) {
  308. SHA1EntropyGenerator entropy_generator(kTestTrialNames[i]);
  309. PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator);
  310. }
  311. }
  312. TEST(EntropyProviderTest, NormalizedMurmurHashEntropyIsUniform) {
  313. for (size_t i = 0; i < std::size(kTestTrialNames); ++i) {
  314. NormalizedMurmurHashEntropyGenerator entropy_generator(kTestTrialNames[i]);
  315. PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator);
  316. }
  317. }
  318. } // namespace variations