123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259 |
- // Copyright 2022 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "components/browsing_topics/util.h"
- #include "base/bits.h"
- #include "base/callback.h"
- #include "base/logging.h"
- #include "base/rand_util.h"
- #include "base/test/bind.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace browsing_topics {
- namespace {
- std::string GenerateRandomUniformString(int min_length, int max_length) {
- DCHECK_GT(min_length, 0);
- DCHECK_LT(max_length, 30);
- DCHECK_LE(min_length, max_length);
- int min_bound = (1 << min_length);
- int max_bound = (1 << (max_length + 1)) - 1;
- int random_length =
- base::bits::Log2Floor(base::RandInt(min_bound, max_bound));
- return base::RandBytesAsString(random_length);
- }
- std::string GenerateRandomDomainOrHost() {
- return GenerateRandomUniformString(/*min_length=*/3, /*max_length=*/20);
- }
- // Check for some properties of uniform random distribution:
- // - The average of values is 0.5 * UINT64_MAX.
- // - 5% of values mod 100 is less than 5.
- // - Chances of each bit to be 0 and 1 are equally likely.
- void CheckUniformRandom(base::RepeatingCallback<uint64_t()> uint64_generator) {
- constexpr double kExpectedAverage =
- static_cast<double>(std::numeric_limits<uint64_t>::max()) * 0.5;
- constexpr int kRepeatTimes = 1000000;
- constexpr double kExpectedBitSum = kRepeatTimes * 0.5;
- constexpr double kExpectedCountModHundredBelowFive = kRepeatTimes * 0.05;
- constexpr double kToleranceMultipler = 0.02;
- int bit_sum[64] = {0};
- int count_mod_hundred_below_five = 0;
- double cumulative_average = 0.0;
- for (int i = 0; i < kRepeatTimes; ++i) {
- uint64_t random_value = uint64_generator.Run();
- cumulative_average = (i * cumulative_average + random_value) / (i + 1);
- count_mod_hundred_below_five += (random_value % 100 < 5);
- for (int j = 0; j < 64; ++j) {
- bit_sum[j] += (random_value >> j) & 1;
- }
- }
- ASSERT_LT(kExpectedAverage * (1 - kToleranceMultipler), cumulative_average);
- ASSERT_GT(kExpectedAverage * (1 + kToleranceMultipler), cumulative_average);
- ASSERT_LT(kExpectedCountModHundredBelowFive * (1 - kToleranceMultipler),
- count_mod_hundred_below_five);
- ASSERT_GT(kExpectedCountModHundredBelowFive * (1 + kToleranceMultipler),
- count_mod_hundred_below_five);
- for (int i = 0; i < 64; ++i) {
- ASSERT_LT(kExpectedBitSum * (1 - kToleranceMultipler), bit_sum[i]);
- ASSERT_GT(kExpectedBitSum * (1 + kToleranceMultipler), bit_sum[i]);
- }
- }
- } // namespace
- class BrowsingTopicsUtilTest : public testing::Test {};
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForRandomOrTopTopicDecision_VariableHmacKey) {
- std::string top_domain = GenerateRandomDomainOrHost();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- HmacKey hmac_key = GenerateRandomHmacKey();
- return HashTopDomainForRandomOrTopTopicDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForRandomOrTopTopicDecision_VariableEpochCalculationTime) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- std::string top_domain = GenerateRandomDomainOrHost();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- epoch_calculation_time += base::Days(7);
- return HashTopDomainForRandomOrTopTopicDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForRandomOrTopTopicDecision_VariableTopDomain) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- std::string top_domain = GenerateRandomDomainOrHost();
- return HashTopDomainForRandomOrTopTopicDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForTopTopicIndexDecision_VariableHmacKey) {
- std::string top_domain = GenerateRandomDomainOrHost();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- HmacKey hmac_key = GenerateRandomHmacKey();
- return HashTopDomainForTopTopicIndexDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForRandomTopicIndexDecision_VariableEpochCalculationTime) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- std::string top_domain = GenerateRandomDomainOrHost();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- epoch_calculation_time += base::Days(7);
- return HashTopDomainForRandomTopicIndexDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForRandomTopicIndexDecision_VariableTopDomain) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- std::string top_domain = GenerateRandomDomainOrHost();
- return HashTopDomainForRandomTopicIndexDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForRandomTopicIndexDecision_VariableHmacKey) {
- std::string top_domain = GenerateRandomDomainOrHost();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- HmacKey hmac_key = GenerateRandomHmacKey();
- return HashTopDomainForRandomTopicIndexDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForTopTopicIndexDecision_VariableEpochCalculationTime) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- std::string top_domain = GenerateRandomDomainOrHost();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- epoch_calculation_time += base::Days(7);
- return HashTopDomainForTopTopicIndexDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForTopTopicIndexDecision_VariableTopDomain) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- base::Time epoch_calculation_time = base::Time::Now();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- std::string top_domain = GenerateRandomDomainOrHost();
- return HashTopDomainForTopTopicIndexDecision(
- hmac_key, epoch_calculation_time, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForEpochSwitchTimeDecision_VariableHmacKey) {
- std::string top_domain = GenerateRandomDomainOrHost();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- HmacKey hmac_key = GenerateRandomHmacKey();
- return HashTopDomainForEpochSwitchTimeDecision(hmac_key, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashTopDomainForEpochSwitchTimeDecision_VariableContextDomain) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- std::string top_domain = GenerateRandomDomainOrHost();
- return HashTopDomainForEpochSwitchTimeDecision(hmac_key, top_domain);
- }));
- }
- TEST_F(BrowsingTopicsUtilTest, HashContextDomainForStorage_VariableHmacKey) {
- std::string context_domain = GenerateRandomDomainOrHost();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- HmacKey hmac_key = GenerateRandomHmacKey();
- return static_cast<uint64_t>(
- HashContextDomainForStorage(hmac_key, context_domain).value());
- }));
- }
- TEST_F(BrowsingTopicsUtilTest,
- HashContextDomainForStorage_VariableContextDomain) {
- HmacKey hmac_key = GenerateRandomHmacKey();
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- std::string context_domain = GenerateRandomDomainOrHost();
- return static_cast<uint64_t>(
- HashContextDomainForStorage(hmac_key, context_domain).value());
- }));
- }
- TEST_F(BrowsingTopicsUtilTest, HashMainFrameHostForStorage) {
- CheckUniformRandom(base::BindLambdaForTesting([&]() {
- std::string main_frame_host = GenerateRandomDomainOrHost();
- return static_cast<uint64_t>(
- HashMainFrameHostForStorage(main_frame_host).value());
- }));
- }
- } // namespace browsing_topics
|