| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "components/variations/entropy_provider.h" | 5 #include "components/variations/entropy_provider.h" |
| 6 | 6 |
| 7 #include <stddef.h> |
| 8 #include <stdint.h> |
| 9 |
| 7 #include <cmath> | 10 #include <cmath> |
| 8 #include <limits> | 11 #include <limits> |
| 9 #include <numeric> | 12 #include <numeric> |
| 10 | 13 |
| 11 #include "base/basictypes.h" | |
| 12 #include "base/guid.h" | 14 #include "base/guid.h" |
| 15 #include "base/macros.h" |
| 13 #include "base/memory/scoped_ptr.h" | 16 #include "base/memory/scoped_ptr.h" |
| 14 #include "base/rand_util.h" | 17 #include "base/rand_util.h" |
| 15 #include "base/strings/string_number_conversions.h" | 18 #include "base/strings/string_number_conversions.h" |
| 16 #include "components/variations/metrics_util.h" | 19 #include "components/variations/metrics_util.h" |
| 17 #include "testing/gtest/include/gtest/gtest.h" | 20 #include "testing/gtest/include/gtest/gtest.h" |
| 18 | 21 |
| 19 namespace metrics { | 22 namespace metrics { |
| 20 | 23 |
| 21 namespace { | 24 namespace { |
| 22 | 25 |
| (...skipping 23 matching lines...) Expand all Loading... |
| 46 // Computes SHA1-based entropy for the given |trial_name| based on | 49 // Computes SHA1-based entropy for the given |trial_name| based on |
| 47 // |entropy_source| | 50 // |entropy_source| |
| 48 double GenerateSHA1Entropy(const std::string& entropy_source, | 51 double GenerateSHA1Entropy(const std::string& entropy_source, |
| 49 const std::string& trial_name) { | 52 const std::string& trial_name) { |
| 50 SHA1EntropyProvider sha1_provider(entropy_source); | 53 SHA1EntropyProvider sha1_provider(entropy_source); |
| 51 return sha1_provider.GetEntropyForTrial(trial_name, 0); | 54 return sha1_provider.GetEntropyForTrial(trial_name, 0); |
| 52 } | 55 } |
| 53 | 56 |
| 54 // Generates permutation-based entropy for the given |trial_name| based on | 57 // Generates permutation-based entropy for the given |trial_name| based on |
| 55 // |entropy_source| which must be in the range [0, entropy_max). | 58 // |entropy_source| which must be in the range [0, entropy_max). |
| 56 double GeneratePermutedEntropy(uint16 entropy_source, | 59 double GeneratePermutedEntropy(uint16_t entropy_source, |
| 57 size_t entropy_max, | 60 size_t entropy_max, |
| 58 const std::string& trial_name) { | 61 const std::string& trial_name) { |
| 59 PermutedEntropyProvider permuted_provider(entropy_source, entropy_max); | 62 PermutedEntropyProvider permuted_provider(entropy_source, entropy_max); |
| 60 return permuted_provider.GetEntropyForTrial(trial_name, 0); | 63 return permuted_provider.GetEntropyForTrial(trial_name, 0); |
| 61 } | 64 } |
| 62 | 65 |
| 63 // Helper interface for testing used to generate entropy values for a given | 66 // Helper interface for testing used to generate entropy values for a given |
| 64 // field trial. Unlike EntropyProvider, which keeps the low/high entropy source | 67 // field trial. Unlike EntropyProvider, which keeps the low/high entropy source |
| 65 // value constant and generates entropy for different trial names, instances | 68 // value constant and generates entropy for different trial names, instances |
| 66 // of TrialEntropyGenerator keep the trial name constant and generate low/high | 69 // of TrialEntropyGenerator keep the trial name constant and generate low/high |
| (...skipping 12 matching lines...) Expand all Loading... |
| 79 explicit SHA1EntropyGenerator(const std::string& trial_name) | 82 explicit SHA1EntropyGenerator(const std::string& trial_name) |
| 80 : trial_name_(trial_name) { | 83 : trial_name_(trial_name) { |
| 81 } | 84 } |
| 82 | 85 |
| 83 ~SHA1EntropyGenerator() override {} | 86 ~SHA1EntropyGenerator() override {} |
| 84 | 87 |
| 85 double GenerateEntropyValue() const override { | 88 double GenerateEntropyValue() const override { |
| 86 // Use a random GUID + 13 additional bits of entropy to match how the | 89 // Use a random GUID + 13 additional bits of entropy to match how the |
| 87 // SHA1EntropyProvider is used in metrics_service.cc. | 90 // SHA1EntropyProvider is used in metrics_service.cc. |
| 88 const int low_entropy_source = | 91 const int low_entropy_source = |
| 89 static_cast<uint16>(base::RandInt(0, kMaxLowEntropySize - 1)); | 92 static_cast<uint16_t>(base::RandInt(0, kMaxLowEntropySize - 1)); |
| 90 const std::string high_entropy_source = | 93 const std::string high_entropy_source = |
| 91 base::GenerateGUID() + base::IntToString(low_entropy_source); | 94 base::GenerateGUID() + base::IntToString(low_entropy_source); |
| 92 return GenerateSHA1Entropy(high_entropy_source, trial_name_); | 95 return GenerateSHA1Entropy(high_entropy_source, trial_name_); |
| 93 } | 96 } |
| 94 | 97 |
| 95 private: | 98 private: |
| 96 std::string trial_name_; | 99 std::string trial_name_; |
| 97 | 100 |
| 98 DISALLOW_COPY_AND_ASSIGN(SHA1EntropyGenerator); | 101 DISALLOW_COPY_AND_ASSIGN(SHA1EntropyGenerator); |
| 99 }; | 102 }; |
| 100 | 103 |
| 101 // An TrialEntropyGenerator that uses the permuted entropy provider algorithm, | 104 // An TrialEntropyGenerator that uses the permuted entropy provider algorithm, |
| 102 // using 13-bit low entropy source values. | 105 // using 13-bit low entropy source values. |
| 103 class PermutedEntropyGenerator : public TrialEntropyGenerator { | 106 class PermutedEntropyGenerator : public TrialEntropyGenerator { |
| 104 public: | 107 public: |
| 105 explicit PermutedEntropyGenerator(const std::string& trial_name) | 108 explicit PermutedEntropyGenerator(const std::string& trial_name) |
| 106 : mapping_(kMaxLowEntropySize) { | 109 : mapping_(kMaxLowEntropySize) { |
| 107 // Note: Given a trial name, the computed mapping will be the same. | 110 // Note: Given a trial name, the computed mapping will be the same. |
| 108 // As a performance optimization, pre-compute the mapping once per trial | 111 // As a performance optimization, pre-compute the mapping once per trial |
| 109 // name and index into it for each entropy value. | 112 // name and index into it for each entropy value. |
| 110 const uint32 randomization_seed = HashName(trial_name); | 113 const uint32_t randomization_seed = HashName(trial_name); |
| 111 internal::PermuteMappingUsingRandomizationSeed(randomization_seed, | 114 internal::PermuteMappingUsingRandomizationSeed(randomization_seed, |
| 112 &mapping_); | 115 &mapping_); |
| 113 } | 116 } |
| 114 | 117 |
| 115 ~PermutedEntropyGenerator() override {} | 118 ~PermutedEntropyGenerator() override {} |
| 116 | 119 |
| 117 double GenerateEntropyValue() const override { | 120 double GenerateEntropyValue() const override { |
| 118 const int low_entropy_source = | 121 const int low_entropy_source = |
| 119 static_cast<uint16>(base::RandInt(0, kMaxLowEntropySize - 1)); | 122 static_cast<uint16_t>(base::RandInt(0, kMaxLowEntropySize - 1)); |
| 120 return mapping_[low_entropy_source] / | 123 return mapping_[low_entropy_source] / |
| 121 static_cast<double>(kMaxLowEntropySize); | 124 static_cast<double>(kMaxLowEntropySize); |
| 122 } | 125 } |
| 123 | 126 |
| 124 private: | 127 private: |
| 125 std::vector<uint16> mapping_; | 128 std::vector<uint16_t> mapping_; |
| 126 | 129 |
| 127 DISALLOW_COPY_AND_ASSIGN(PermutedEntropyGenerator); | 130 DISALLOW_COPY_AND_ASSIGN(PermutedEntropyGenerator); |
| 128 }; | 131 }; |
| 129 | 132 |
| 130 // Tests uniformity of a given |entropy_generator| using the Chi-Square Goodness | 133 // Tests uniformity of a given |entropy_generator| using the Chi-Square Goodness |
| 131 // of Fit Test. | 134 // of Fit Test. |
| 132 void PerformEntropyUniformityTest( | 135 void PerformEntropyUniformityTest( |
| 133 const std::string& trial_name, | 136 const std::string& trial_name, |
| 134 const TrialEntropyGenerator& entropy_generator) { | 137 const TrialEntropyGenerator& entropy_generator) { |
| 135 // Number of buckets in the simulated field trials. | 138 // Number of buckets in the simulated field trials. |
| (...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 238 EXPECT_NE(trials[0]->group(), trials[1]->group()); | 241 EXPECT_NE(trials[0]->group(), trials[1]->group()); |
| 239 EXPECT_NE(trials[0]->group_name(), trials[1]->group_name()); | 242 EXPECT_NE(trials[0]->group_name(), trials[1]->group_name()); |
| 240 } | 243 } |
| 241 | 244 |
| 242 TEST(EntropyProviderTest, UseOneTimeRandomizationWithCustomSeedPermuted) { | 245 TEST(EntropyProviderTest, UseOneTimeRandomizationWithCustomSeedPermuted) { |
| 243 // Ensures that two trials with different names but the same custom seed used | 246 // Ensures that two trials with different names but the same custom seed used |
| 244 // for one time randomization produce the same group assignments. | 247 // for one time randomization produce the same group assignments. |
| 245 base::FieldTrialList field_trial_list( | 248 base::FieldTrialList field_trial_list( |
| 246 new PermutedEntropyProvider(1234, kMaxLowEntropySize)); | 249 new PermutedEntropyProvider(1234, kMaxLowEntropySize)); |
| 247 const int kNoExpirationYear = base::FieldTrialList::kNoExpirationYear; | 250 const int kNoExpirationYear = base::FieldTrialList::kNoExpirationYear; |
| 248 const uint32 kCustomSeed = 9001; | 251 const uint32_t kCustomSeed = 9001; |
| 249 scoped_refptr<base::FieldTrial> trials[] = { | 252 scoped_refptr<base::FieldTrial> trials[] = { |
| 250 base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed( | 253 base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed( |
| 251 "one", 100, "default", kNoExpirationYear, 1, 1, | 254 "one", 100, "default", kNoExpirationYear, 1, 1, |
| 252 base::FieldTrial::ONE_TIME_RANDOMIZED, kCustomSeed, NULL), | 255 base::FieldTrial::ONE_TIME_RANDOMIZED, kCustomSeed, NULL), |
| 253 base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed( | 256 base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed( |
| 254 "two", 100, "default", kNoExpirationYear, 1, 1, | 257 "two", 100, "default", kNoExpirationYear, 1, 1, |
| 255 base::FieldTrial::ONE_TIME_RANDOMIZED, kCustomSeed, NULL), | 258 base::FieldTrial::ONE_TIME_RANDOMIZED, kCustomSeed, NULL), |
| 256 }; | 259 }; |
| 257 | 260 |
| 258 for (size_t i = 0; i < arraysize(trials); ++i) { | 261 for (size_t i = 0; i < arraysize(trials); ++i) { |
| (...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 324 PermutedEntropyGenerator entropy_generator(kTestTrialNames[i]); | 327 PermutedEntropyGenerator entropy_generator(kTestTrialNames[i]); |
| 325 PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator); | 328 PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator); |
| 326 } | 329 } |
| 327 } | 330 } |
| 328 | 331 |
| 329 TEST(EntropyProviderTest, SeededRandGeneratorIsUniform) { | 332 TEST(EntropyProviderTest, SeededRandGeneratorIsUniform) { |
| 330 // Verifies that SeededRandGenerator has a uniform distribution. | 333 // Verifies that SeededRandGenerator has a uniform distribution. |
| 331 // | 334 // |
| 332 // Mirrors RandUtilTest.RandGeneratorIsUniform in base/rand_util_unittest.cc. | 335 // Mirrors RandUtilTest.RandGeneratorIsUniform in base/rand_util_unittest.cc. |
| 333 | 336 |
| 334 const uint32 kTopOfRange = (std::numeric_limits<uint32>::max() / 4ULL) * 3ULL; | 337 const uint32_t kTopOfRange = |
| 335 const uint32 kExpectedAverage = kTopOfRange / 2ULL; | 338 (std::numeric_limits<uint32_t>::max() / 4ULL) * 3ULL; |
| 336 const uint32 kAllowedVariance = kExpectedAverage / 50ULL; // +/- 2% | 339 const uint32_t kExpectedAverage = kTopOfRange / 2ULL; |
| 340 const uint32_t kAllowedVariance = kExpectedAverage / 50ULL; // +/- 2% |
| 337 const int kMinAttempts = 1000; | 341 const int kMinAttempts = 1000; |
| 338 const int kMaxAttempts = 1000000; | 342 const int kMaxAttempts = 1000000; |
| 339 | 343 |
| 340 for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { | 344 for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { |
| 341 const uint32 seed = HashName(kTestTrialNames[i]); | 345 const uint32_t seed = HashName(kTestTrialNames[i]); |
| 342 internal::SeededRandGenerator rand_generator(seed); | 346 internal::SeededRandGenerator rand_generator(seed); |
| 343 | 347 |
| 344 double cumulative_average = 0.0; | 348 double cumulative_average = 0.0; |
| 345 int count = 0; | 349 int count = 0; |
| 346 while (count < kMaxAttempts) { | 350 while (count < kMaxAttempts) { |
| 347 uint32 value = rand_generator(kTopOfRange); | 351 uint32_t value = rand_generator(kTopOfRange); |
| 348 cumulative_average = (count * cumulative_average + value) / (count + 1); | 352 cumulative_average = (count * cumulative_average + value) / (count + 1); |
| 349 | 353 |
| 350 // Don't quit too quickly for things to start converging, or we may have | 354 // Don't quit too quickly for things to start converging, or we may have |
| 351 // a false positive. | 355 // a false positive. |
| 352 if (count > kMinAttempts && | 356 if (count > kMinAttempts && |
| 353 kExpectedAverage - kAllowedVariance < cumulative_average && | 357 kExpectedAverage - kAllowedVariance < cumulative_average && |
| 354 cumulative_average < kExpectedAverage + kAllowedVariance) { | 358 cumulative_average < kExpectedAverage + kAllowedVariance) { |
| 355 break; | 359 break; |
| 356 } | 360 } |
| 357 | 361 |
| 358 ++count; | 362 ++count; |
| 359 } | 363 } |
| 360 | 364 |
| 361 ASSERT_LT(count, kMaxAttempts) << "Expected average was " << | 365 ASSERT_LT(count, kMaxAttempts) << "Expected average was " << |
| 362 kExpectedAverage << ", average ended at " << cumulative_average << | 366 kExpectedAverage << ", average ended at " << cumulative_average << |
| 363 ", for trial " << kTestTrialNames[i]; | 367 ", for trial " << kTestTrialNames[i]; |
| 364 } | 368 } |
| 365 } | 369 } |
| 366 | 370 |
| 367 } // namespace metrics | 371 } // namespace metrics |
| OLD | NEW |