util_unittest.cc 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259
  1. // Copyright 2022 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/browsing_topics/util.h"
  5. #include "base/bits.h"
  6. #include "base/callback.h"
  7. #include "base/logging.h"
  8. #include "base/rand_util.h"
  9. #include "base/test/bind.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. namespace browsing_topics {
  12. namespace {
  13. std::string GenerateRandomUniformString(int min_length, int max_length) {
  14. DCHECK_GT(min_length, 0);
  15. DCHECK_LT(max_length, 30);
  16. DCHECK_LE(min_length, max_length);
  17. int min_bound = (1 << min_length);
  18. int max_bound = (1 << (max_length + 1)) - 1;
  19. int random_length =
  20. base::bits::Log2Floor(base::RandInt(min_bound, max_bound));
  21. return base::RandBytesAsString(random_length);
  22. }
  23. std::string GenerateRandomDomainOrHost() {
  24. return GenerateRandomUniformString(/*min_length=*/3, /*max_length=*/20);
  25. }
  26. // Check for some properties of uniform random distribution:
  27. // - The average of values is 0.5 * UINT64_MAX.
  28. // - 5% of values mod 100 is less than 5.
  29. // - Chances of each bit to be 0 and 1 are equally likely.
  30. void CheckUniformRandom(base::RepeatingCallback<uint64_t()> uint64_generator) {
  31. constexpr double kExpectedAverage =
  32. static_cast<double>(std::numeric_limits<uint64_t>::max()) * 0.5;
  33. constexpr int kRepeatTimes = 1000000;
  34. constexpr double kExpectedBitSum = kRepeatTimes * 0.5;
  35. constexpr double kExpectedCountModHundredBelowFive = kRepeatTimes * 0.05;
  36. constexpr double kToleranceMultipler = 0.02;
  37. int bit_sum[64] = {0};
  38. int count_mod_hundred_below_five = 0;
  39. double cumulative_average = 0.0;
  40. for (int i = 0; i < kRepeatTimes; ++i) {
  41. uint64_t random_value = uint64_generator.Run();
  42. cumulative_average = (i * cumulative_average + random_value) / (i + 1);
  43. count_mod_hundred_below_five += (random_value % 100 < 5);
  44. for (int j = 0; j < 64; ++j) {
  45. bit_sum[j] += (random_value >> j) & 1;
  46. }
  47. }
  48. ASSERT_LT(kExpectedAverage * (1 - kToleranceMultipler), cumulative_average);
  49. ASSERT_GT(kExpectedAverage * (1 + kToleranceMultipler), cumulative_average);
  50. ASSERT_LT(kExpectedCountModHundredBelowFive * (1 - kToleranceMultipler),
  51. count_mod_hundred_below_five);
  52. ASSERT_GT(kExpectedCountModHundredBelowFive * (1 + kToleranceMultipler),
  53. count_mod_hundred_below_five);
  54. for (int i = 0; i < 64; ++i) {
  55. ASSERT_LT(kExpectedBitSum * (1 - kToleranceMultipler), bit_sum[i]);
  56. ASSERT_GT(kExpectedBitSum * (1 + kToleranceMultipler), bit_sum[i]);
  57. }
  58. }
  59. } // namespace
  60. class BrowsingTopicsUtilTest : public testing::Test {};
  61. TEST_F(BrowsingTopicsUtilTest,
  62. HashTopDomainForRandomOrTopTopicDecision_VariableHmacKey) {
  63. std::string top_domain = GenerateRandomDomainOrHost();
  64. base::Time epoch_calculation_time = base::Time::Now();
  65. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  66. HmacKey hmac_key = GenerateRandomHmacKey();
  67. return HashTopDomainForRandomOrTopTopicDecision(
  68. hmac_key, epoch_calculation_time, top_domain);
  69. }));
  70. }
  71. TEST_F(BrowsingTopicsUtilTest,
  72. HashTopDomainForRandomOrTopTopicDecision_VariableEpochCalculationTime) {
  73. HmacKey hmac_key = GenerateRandomHmacKey();
  74. std::string top_domain = GenerateRandomDomainOrHost();
  75. base::Time epoch_calculation_time = base::Time::Now();
  76. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  77. epoch_calculation_time += base::Days(7);
  78. return HashTopDomainForRandomOrTopTopicDecision(
  79. hmac_key, epoch_calculation_time, top_domain);
  80. }));
  81. }
  82. TEST_F(BrowsingTopicsUtilTest,
  83. HashTopDomainForRandomOrTopTopicDecision_VariableTopDomain) {
  84. HmacKey hmac_key = GenerateRandomHmacKey();
  85. base::Time epoch_calculation_time = base::Time::Now();
  86. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  87. std::string top_domain = GenerateRandomDomainOrHost();
  88. return HashTopDomainForRandomOrTopTopicDecision(
  89. hmac_key, epoch_calculation_time, top_domain);
  90. }));
  91. }
  92. TEST_F(BrowsingTopicsUtilTest,
  93. HashTopDomainForTopTopicIndexDecision_VariableHmacKey) {
  94. std::string top_domain = GenerateRandomDomainOrHost();
  95. base::Time epoch_calculation_time = base::Time::Now();
  96. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  97. HmacKey hmac_key = GenerateRandomHmacKey();
  98. return HashTopDomainForTopTopicIndexDecision(
  99. hmac_key, epoch_calculation_time, top_domain);
  100. }));
  101. }
  102. TEST_F(BrowsingTopicsUtilTest,
  103. HashTopDomainForRandomTopicIndexDecision_VariableEpochCalculationTime) {
  104. HmacKey hmac_key = GenerateRandomHmacKey();
  105. std::string top_domain = GenerateRandomDomainOrHost();
  106. base::Time epoch_calculation_time = base::Time::Now();
  107. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  108. epoch_calculation_time += base::Days(7);
  109. return HashTopDomainForRandomTopicIndexDecision(
  110. hmac_key, epoch_calculation_time, top_domain);
  111. }));
  112. }
  113. TEST_F(BrowsingTopicsUtilTest,
  114. HashTopDomainForRandomTopicIndexDecision_VariableTopDomain) {
  115. HmacKey hmac_key = GenerateRandomHmacKey();
  116. base::Time epoch_calculation_time = base::Time::Now();
  117. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  118. std::string top_domain = GenerateRandomDomainOrHost();
  119. return HashTopDomainForRandomTopicIndexDecision(
  120. hmac_key, epoch_calculation_time, top_domain);
  121. }));
  122. }
  123. TEST_F(BrowsingTopicsUtilTest,
  124. HashTopDomainForRandomTopicIndexDecision_VariableHmacKey) {
  125. std::string top_domain = GenerateRandomDomainOrHost();
  126. base::Time epoch_calculation_time = base::Time::Now();
  127. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  128. HmacKey hmac_key = GenerateRandomHmacKey();
  129. return HashTopDomainForRandomTopicIndexDecision(
  130. hmac_key, epoch_calculation_time, top_domain);
  131. }));
  132. }
  133. TEST_F(BrowsingTopicsUtilTest,
  134. HashTopDomainForTopTopicIndexDecision_VariableEpochCalculationTime) {
  135. HmacKey hmac_key = GenerateRandomHmacKey();
  136. std::string top_domain = GenerateRandomDomainOrHost();
  137. base::Time epoch_calculation_time = base::Time::Now();
  138. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  139. epoch_calculation_time += base::Days(7);
  140. return HashTopDomainForTopTopicIndexDecision(
  141. hmac_key, epoch_calculation_time, top_domain);
  142. }));
  143. }
  144. TEST_F(BrowsingTopicsUtilTest,
  145. HashTopDomainForTopTopicIndexDecision_VariableTopDomain) {
  146. HmacKey hmac_key = GenerateRandomHmacKey();
  147. base::Time epoch_calculation_time = base::Time::Now();
  148. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  149. std::string top_domain = GenerateRandomDomainOrHost();
  150. return HashTopDomainForTopTopicIndexDecision(
  151. hmac_key, epoch_calculation_time, top_domain);
  152. }));
  153. }
  154. TEST_F(BrowsingTopicsUtilTest,
  155. HashTopDomainForEpochSwitchTimeDecision_VariableHmacKey) {
  156. std::string top_domain = GenerateRandomDomainOrHost();
  157. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  158. HmacKey hmac_key = GenerateRandomHmacKey();
  159. return HashTopDomainForEpochSwitchTimeDecision(hmac_key, top_domain);
  160. }));
  161. }
  162. TEST_F(BrowsingTopicsUtilTest,
  163. HashTopDomainForEpochSwitchTimeDecision_VariableContextDomain) {
  164. HmacKey hmac_key = GenerateRandomHmacKey();
  165. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  166. std::string top_domain = GenerateRandomDomainOrHost();
  167. return HashTopDomainForEpochSwitchTimeDecision(hmac_key, top_domain);
  168. }));
  169. }
  170. TEST_F(BrowsingTopicsUtilTest, HashContextDomainForStorage_VariableHmacKey) {
  171. std::string context_domain = GenerateRandomDomainOrHost();
  172. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  173. HmacKey hmac_key = GenerateRandomHmacKey();
  174. return static_cast<uint64_t>(
  175. HashContextDomainForStorage(hmac_key, context_domain).value());
  176. }));
  177. }
  178. TEST_F(BrowsingTopicsUtilTest,
  179. HashContextDomainForStorage_VariableContextDomain) {
  180. HmacKey hmac_key = GenerateRandomHmacKey();
  181. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  182. std::string context_domain = GenerateRandomDomainOrHost();
  183. return static_cast<uint64_t>(
  184. HashContextDomainForStorage(hmac_key, context_domain).value());
  185. }));
  186. }
  187. TEST_F(BrowsingTopicsUtilTest, HashMainFrameHostForStorage) {
  188. CheckUniformRandom(base::BindLambdaForTesting([&]() {
  189. std::string main_frame_host = GenerateRandomDomainOrHost();
  190. return static_cast<uint64_t>(
  191. HashMainFrameHostForStorage(main_frame_host).value());
  192. }));
  193. }
  194. } // namespace browsing_topics