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 |