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 5 #include "components/variations/entropy_provider.h" 6 7 #include <cmath> 8 #include <limits> 9 #include <numeric> 10 11 #include "base/basictypes.h" 12 #include "base/guid.h" 13 #include "base/memory/scoped_ptr.h" 14 #include "base/rand_util.h" 15 #include "base/strings/string_number_conversions.h" 16 #include "components/variations/metrics_util.h" 17 #include "testing/gtest/include/gtest/gtest.h" 18 19 namespace metrics { 20 21 namespace { 22 23 // Size of the low entropy source to use for the permuted entropy provider 24 // in tests. 25 const size_t kMaxLowEntropySize = 8000; 26 27 // Field trial names used in unit tests. 28 const char* const kTestTrialNames[] = { "TestTrial", "AnotherTestTrial", 29 "NewTabButton" }; 30 31 // Computes the Chi-Square statistic for |values| assuming they follow a uniform 32 // distribution, where each entry has expected value |expected_value|. 33 // 34 // The Chi-Square statistic is defined as Sum((O-E)^2/E) where O is the observed 35 // value and E is the expected value. 36 double ComputeChiSquare(const std::vector<int>& values, 37 double expected_value) { 38 double sum = 0; 39 for (size_t i = 0; i < values.size(); ++i) { 40 const double delta = values[i] - expected_value; 41 sum += (delta * delta) / expected_value; 42 } 43 return sum; 44 } 45 46 // Computes SHA1-based entropy for the given |trial_name| based on 47 // |entropy_source| 48 double GenerateSHA1Entropy(const std::string& entropy_source, 49 const std::string& trial_name) { 50 SHA1EntropyProvider sha1_provider(entropy_source); 51 return sha1_provider.GetEntropyForTrial(trial_name, 0); 52 } 53 54 // Generates permutation-based entropy for the given |trial_name| based on 55 // |entropy_source| which must be in the range [0, entropy_max). 56 double GeneratePermutedEntropy(uint16 entropy_source, 57 size_t entropy_max, 58 const std::string& trial_name) { 59 PermutedEntropyProvider permuted_provider(entropy_source, entropy_max); 60 return permuted_provider.GetEntropyForTrial(trial_name, 0); 61 } 62 63 // Helper interface for testing used to generate entropy values for a given 64 // field trial. Unlike EntropyProvider, which keeps the low/high entropy source 65 // value constant and generates entropy for different trial names, instances 66 // of TrialEntropyGenerator keep the trial name constant and generate low/high 67 // entropy source values internally to produce each output entropy value. 68 class TrialEntropyGenerator { 69 public: 70 virtual ~TrialEntropyGenerator() {} 71 virtual double GenerateEntropyValue() const = 0; 72 }; 73 74 // An TrialEntropyGenerator that uses the SHA1EntropyProvider with the high 75 // entropy source (random GUID with 128 bits of entropy + 13 additional bits of 76 // entropy corresponding to a low entropy source). 77 class SHA1EntropyGenerator : public TrialEntropyGenerator { 78 public: 79 explicit SHA1EntropyGenerator(const std::string& trial_name) 80 : trial_name_(trial_name) { 81 } 82 83 virtual ~SHA1EntropyGenerator() { 84 } 85 86 virtual double GenerateEntropyValue() const OVERRIDE { 87 // Use a random GUID + 13 additional bits of entropy to match how the 88 // SHA1EntropyProvider is used in metrics_service.cc. 89 const int low_entropy_source = 90 static_cast<uint16>(base::RandInt(0, kMaxLowEntropySize - 1)); 91 const std::string high_entropy_source = 92 base::GenerateGUID() + base::IntToString(low_entropy_source); 93 return GenerateSHA1Entropy(high_entropy_source, trial_name_); 94 } 95 96 private: 97 std::string trial_name_; 98 99 DISALLOW_COPY_AND_ASSIGN(SHA1EntropyGenerator); 100 }; 101 102 // An TrialEntropyGenerator that uses the permuted entropy provider algorithm, 103 // using 13-bit low entropy source values. 104 class PermutedEntropyGenerator : public TrialEntropyGenerator { 105 public: 106 explicit PermutedEntropyGenerator(const std::string& trial_name) 107 : mapping_(kMaxLowEntropySize) { 108 // Note: Given a trial name, the computed mapping will be the same. 109 // As a performance optimization, pre-compute the mapping once per trial 110 // name and index into it for each entropy value. 111 const uint32 randomization_seed = HashName(trial_name); 112 internal::PermuteMappingUsingRandomizationSeed(randomization_seed, 113 &mapping_); 114 } 115 116 virtual ~PermutedEntropyGenerator() { 117 } 118 119 virtual double GenerateEntropyValue() const OVERRIDE { 120 const int low_entropy_source = 121 static_cast<uint16>(base::RandInt(0, kMaxLowEntropySize - 1)); 122 return mapping_[low_entropy_source] / 123 static_cast<double>(kMaxLowEntropySize); 124 } 125 126 private: 127 std::vector<uint16> mapping_; 128 129 DISALLOW_COPY_AND_ASSIGN(PermutedEntropyGenerator); 130 }; 131 132 // Tests uniformity of a given |entropy_generator| using the Chi-Square Goodness 133 // of Fit Test. 134 void PerformEntropyUniformityTest( 135 const std::string& trial_name, 136 const TrialEntropyGenerator& entropy_generator) { 137 // Number of buckets in the simulated field trials. 138 const size_t kBucketCount = 20; 139 // Max number of iterations to perform before giving up and failing. 140 const size_t kMaxIterationCount = 100000; 141 // The number of iterations to perform before each time the statistical 142 // significance of the results is checked. 143 const size_t kCheckIterationCount = 10000; 144 // This is the Chi-Square threshold from the Chi-Square statistic table for 145 // 19 degrees of freedom (based on |kBucketCount|) with a 99.9% confidence 146 // level. See: http://www.medcalc.org/manual/chi-square-table.php 147 const double kChiSquareThreshold = 43.82; 148 149 std::vector<int> distribution(kBucketCount); 150 151 for (size_t i = 1; i <= kMaxIterationCount; ++i) { 152 const double entropy_value = entropy_generator.GenerateEntropyValue(); 153 const size_t bucket = static_cast<size_t>(kBucketCount * entropy_value); 154 ASSERT_LT(bucket, kBucketCount); 155 distribution[bucket] += 1; 156 157 // After |kCheckIterationCount| iterations, compute the Chi-Square 158 // statistic of the distribution. If the resulting statistic is greater 159 // than |kChiSquareThreshold|, we can conclude with 99.9% confidence 160 // that the observed samples do not follow a uniform distribution. 161 // 162 // However, since 99.9% would still result in a false negative every 163 // 1000 runs of the test, do not treat it as a failure (else the test 164 // will be flaky). Instead, perform additional iterations to determine 165 // if the distribution will converge, up to |kMaxIterationCount|. 166 if ((i % kCheckIterationCount) == 0) { 167 const double expected_value_per_bucket = 168 static_cast<double>(i) / kBucketCount; 169 const double chi_square = 170 ComputeChiSquare(distribution, expected_value_per_bucket); 171 if (chi_square < kChiSquareThreshold) 172 break; 173 174 // If |i == kMaxIterationCount|, the Chi-Square statistic did not 175 // converge after |kMaxIterationCount|. 176 EXPECT_NE(i, kMaxIterationCount) << "Failed for trial " << 177 trial_name << " with chi_square = " << chi_square << 178 " after " << kMaxIterationCount << " iterations."; 179 } 180 } 181 } 182 183 } // namespace 184 185 TEST(EntropyProviderTest, UseOneTimeRandomizationSHA1) { 186 // Simply asserts that two trials using one-time randomization 187 // that have different names, normally generate different results. 188 // 189 // Note that depending on the one-time random initialization, they 190 // _might_ actually give the same result, but we know that given 191 // the particular client_id we use for unit tests they won't. 192 base::FieldTrialList field_trial_list(new SHA1EntropyProvider("client_id")); 193 const int kNoExpirationYear = base::FieldTrialList::kNoExpirationYear; 194 scoped_refptr<base::FieldTrial> trials[] = { 195 base::FieldTrialList::FactoryGetFieldTrial( 196 "one", 100, "default", kNoExpirationYear, 1, 1, 197 base::FieldTrial::ONE_TIME_RANDOMIZED, NULL), 198 base::FieldTrialList::FactoryGetFieldTrial( 199 "two", 100, "default", kNoExpirationYear, 1, 1, 200 base::FieldTrial::ONE_TIME_RANDOMIZED, NULL), 201 }; 202 203 for (size_t i = 0; i < arraysize(trials); ++i) { 204 for (int j = 0; j < 100; ++j) 205 trials[i]->AppendGroup(std::string(), 1); 206 } 207 208 // The trials are most likely to give different results since they have 209 // different names. 210 EXPECT_NE(trials[0]->group(), trials[1]->group()); 211 EXPECT_NE(trials[0]->group_name(), trials[1]->group_name()); 212 } 213 214 TEST(EntropyProviderTest, UseOneTimeRandomizationPermuted) { 215 // Simply asserts that two trials using one-time randomization 216 // that have different names, normally generate different results. 217 // 218 // Note that depending on the one-time random initialization, they 219 // _might_ actually give the same result, but we know that given 220 // the particular client_id we use for unit tests they won't. 221 base::FieldTrialList field_trial_list( 222 new PermutedEntropyProvider(1234, kMaxLowEntropySize)); 223 const int kNoExpirationYear = base::FieldTrialList::kNoExpirationYear; 224 scoped_refptr<base::FieldTrial> trials[] = { 225 base::FieldTrialList::FactoryGetFieldTrial( 226 "one", 100, "default", kNoExpirationYear, 1, 1, 227 base::FieldTrial::ONE_TIME_RANDOMIZED, NULL), 228 base::FieldTrialList::FactoryGetFieldTrial( 229 "two", 100, "default", kNoExpirationYear, 1, 1, 230 base::FieldTrial::ONE_TIME_RANDOMIZED, NULL), 231 }; 232 233 for (size_t i = 0; i < arraysize(trials); ++i) { 234 for (int j = 0; j < 100; ++j) 235 trials[i]->AppendGroup(std::string(), 1); 236 } 237 238 // The trials are most likely to give different results since they have 239 // different names. 240 EXPECT_NE(trials[0]->group(), trials[1]->group()); 241 EXPECT_NE(trials[0]->group_name(), trials[1]->group_name()); 242 } 243 244 TEST(EntropyProviderTest, UseOneTimeRandomizationWithCustomSeedPermuted) { 245 // Ensures that two trials with different names but the same custom seed used 246 // for one time randomization produce the same group assignments. 247 base::FieldTrialList field_trial_list( 248 new PermutedEntropyProvider(1234, kMaxLowEntropySize)); 249 const int kNoExpirationYear = base::FieldTrialList::kNoExpirationYear; 250 const uint32 kCustomSeed = 9001; 251 scoped_refptr<base::FieldTrial> trials[] = { 252 base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed( 253 "one", 100, "default", kNoExpirationYear, 1, 1, 254 base::FieldTrial::ONE_TIME_RANDOMIZED, kCustomSeed, NULL), 255 base::FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed( 256 "two", 100, "default", kNoExpirationYear, 1, 1, 257 base::FieldTrial::ONE_TIME_RANDOMIZED, kCustomSeed, NULL), 258 }; 259 260 for (size_t i = 0; i < arraysize(trials); ++i) { 261 for (int j = 0; j < 100; ++j) 262 trials[i]->AppendGroup(std::string(), 1); 263 } 264 265 // Normally, these trials should produce different groups, but if the same 266 // custom seed is used, they should produce the same group assignment. 267 EXPECT_EQ(trials[0]->group(), trials[1]->group()); 268 EXPECT_EQ(trials[0]->group_name(), trials[1]->group_name()); 269 } 270 271 TEST(EntropyProviderTest, SHA1Entropy) { 272 const double results[] = { GenerateSHA1Entropy("hi", "1"), 273 GenerateSHA1Entropy("there", "1") }; 274 275 EXPECT_NE(results[0], results[1]); 276 for (size_t i = 0; i < arraysize(results); ++i) { 277 EXPECT_LE(0.0, results[i]); 278 EXPECT_GT(1.0, results[i]); 279 } 280 281 EXPECT_EQ(GenerateSHA1Entropy("yo", "1"), 282 GenerateSHA1Entropy("yo", "1")); 283 EXPECT_NE(GenerateSHA1Entropy("yo", "something"), 284 GenerateSHA1Entropy("yo", "else")); 285 } 286 287 TEST(EntropyProviderTest, PermutedEntropy) { 288 const double results[] = { 289 GeneratePermutedEntropy(1234, kMaxLowEntropySize, "1"), 290 GeneratePermutedEntropy(4321, kMaxLowEntropySize, "1") }; 291 292 EXPECT_NE(results[0], results[1]); 293 for (size_t i = 0; i < arraysize(results); ++i) { 294 EXPECT_LE(0.0, results[i]); 295 EXPECT_GT(1.0, results[i]); 296 } 297 298 EXPECT_EQ(GeneratePermutedEntropy(1234, kMaxLowEntropySize, "1"), 299 GeneratePermutedEntropy(1234, kMaxLowEntropySize, "1")); 300 EXPECT_NE(GeneratePermutedEntropy(1234, kMaxLowEntropySize, "something"), 301 GeneratePermutedEntropy(1234, kMaxLowEntropySize, "else")); 302 } 303 304 TEST(EntropyProviderTest, PermutedEntropyProviderResults) { 305 // Verifies that PermutedEntropyProvider produces expected results. This 306 // ensures that the results are the same between platforms and ensures that 307 // changes to the implementation do not regress this accidentally. 308 309 EXPECT_DOUBLE_EQ(2194 / static_cast<double>(kMaxLowEntropySize), 310 GeneratePermutedEntropy(1234, kMaxLowEntropySize, "XYZ")); 311 EXPECT_DOUBLE_EQ(5676 / static_cast<double>(kMaxLowEntropySize), 312 GeneratePermutedEntropy(1, kMaxLowEntropySize, "Test")); 313 EXPECT_DOUBLE_EQ(1151 / static_cast<double>(kMaxLowEntropySize), 314 GeneratePermutedEntropy(5000, kMaxLowEntropySize, "Foo")); 315 } 316 317 TEST(EntropyProviderTest, SHA1EntropyIsUniform) { 318 for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { 319 SHA1EntropyGenerator entropy_generator(kTestTrialNames[i]); 320 PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator); 321 } 322 } 323 324 TEST(EntropyProviderTest, PermutedEntropyIsUniform) { 325 for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { 326 PermutedEntropyGenerator entropy_generator(kTestTrialNames[i]); 327 PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator); 328 } 329 } 330 331 TEST(EntropyProviderTest, SeededRandGeneratorIsUniform) { 332 // Verifies that SeededRandGenerator has a uniform distribution. 333 // 334 // Mirrors RandUtilTest.RandGeneratorIsUniform in base/rand_util_unittest.cc. 335 336 const uint32 kTopOfRange = (std::numeric_limits<uint32>::max() / 4ULL) * 3ULL; 337 const uint32 kExpectedAverage = kTopOfRange / 2ULL; 338 const uint32 kAllowedVariance = kExpectedAverage / 50ULL; // +/- 2% 339 const int kMinAttempts = 1000; 340 const int kMaxAttempts = 1000000; 341 342 for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { 343 const uint32 seed = HashName(kTestTrialNames[i]); 344 internal::SeededRandGenerator rand_generator(seed); 345 346 double cumulative_average = 0.0; 347 int count = 0; 348 while (count < kMaxAttempts) { 349 uint32 value = rand_generator(kTopOfRange); 350 cumulative_average = (count * cumulative_average + value) / (count + 1); 351 352 // Don't quit too quickly for things to start converging, or we may have 353 // a false positive. 354 if (count > kMinAttempts && 355 kExpectedAverage - kAllowedVariance < cumulative_average && 356 cumulative_average < kExpectedAverage + kAllowedVariance) { 357 break; 358 } 359 360 ++count; 361 } 362 363 ASSERT_LT(count, kMaxAttempts) << "Expected average was " << 364 kExpectedAverage << ", average ended at " << cumulative_average << 365 ", for trial " << kTestTrialNames[i]; 366 } 367 } 368 369 } // namespace metrics 370
