Use a different algorithm with the low entropy source for field trials.

chrome/common/metrics/entropy_provider_unittest.cc

Index: chrome/common/metrics/entropy_provider_unittest.cc
===================================================================
--- chrome/common/metrics/entropy_provider_unittest.cc	(revision 0)
+++ chrome/common/metrics/entropy_provider_unittest.cc	(revision 0)
@@ -0,0 +1,263 @@
+// Copyright (c) 2012 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 <limits>
+
+#include "base/basictypes.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/rand_util.h"
+#include "base/string_number_conversions.h"
+#include "chrome/common/metrics/entropy_provider.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+class EntropyProviderTest : public testing::Test {
+ public:
+  // Computes SHA1-based entropy for the given |trial_name| based on
+  // |entropy_source|
+  double GenerateSHA1Entropy(const std::string& entropy_source,
+                             const std::string& trial_name) {
+    scoped_ptr<SHA1EntropyProvider> sha1_provider(
+        new SHA1EntropyProvider(entropy_source));
+    return sha1_provider->GetEntropyForTrial(trial_name);
+  }
+
+  // Generates permutation-based entropy for the given |trial_name| based on
+  // |entropy_source| which must be in the range [0, entropy_max).
+  double GeneratePermutedEntropy(uint16 entropy_source,
+                                 size_t entropy_max,
+                                 const std::string& trial_name) {
+    scoped_ptr<PermutedEntropyProvider> permuted_provider(
+        new PermutedEntropyProvider(entropy_source, entropy_max));

[Ilya Sherman, 2012/08/17 07:34:28]

nit: Why not just stack-allocate this guy?

[Alexei Svitkine (slow), 2012/08/17 14:08:59]

Good point. Done.

+    return permuted_provider->GetEntropyForTrial(trial_name);
+  }
+};
+
+
+TEST_F(EntropyProviderTest, UseOneTimeRandomizationSHA1) {
+  // Simply asserts that two trials using one-time randomization
+  // that have different names, normally generate different results.
+  //
+  // Note that depending on the one-time random initialization, they
+  // _might_ actually give the same result, but we know that given
+  // the particular client_id we use for unit tests they won't.
+  base::FieldTrialList field_trial_list(new SHA1EntropyProvider("client_id"));
+  scoped_refptr<base::FieldTrial> trials[] = {
+    base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default",
+        base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL),
+    base::FieldTrialList::FactoryGetFieldTrial("two", 100, "default",
+        base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL),
+  };
+
+  for (size_t i = 0; i < arraysize(trials); ++i) {
+    trials[i]->UseOneTimeRandomization();
+
+    for (int j = 0; j < 100; ++j)
+      trials[i]->AppendGroup("", 1);
+  }
+
+  // The trials are most likely to give different results since they have
+  // different names.
+  ASSERT_NE(trials[0]->group(), trials[1]->group());
+  ASSERT_NE(trials[0]->group_name(), trials[1]->group_name());
+}
+
+TEST_F(EntropyProviderTest, UseOneTimeRandomizationPermuted) {
+  // Simply asserts that two trials using one-time randomization
+  // that have different names, normally generate different results.
+  //
+  // Note that depending on the one-time random initialization, they
+  // _might_ actually give the same result, but we know that given
+  // the particular client_id we use for unit tests they won't.
+  const size_t kMaxEntropySize = (1 << 13);
+  base::FieldTrialList field_trial_list(
+      new PermutedEntropyProvider(1234, kMaxEntropySize));
+  scoped_refptr<base::FieldTrial> trials[] = {
+    base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default",
+        base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL),
+    base::FieldTrialList::FactoryGetFieldTrial("two", 100, "default",
+        base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL),
+  };
+
+  for (size_t i = 0; i < arraysize(trials); ++i) {
+    trials[i]->UseOneTimeRandomization();
+
+    for (int j = 0; j < 100; ++j)
+      trials[i]->AppendGroup("", 1);
+  }
+
+  // The trials are most likely to give different results since they have
+  // different names.
+  ASSERT_NE(trials[0]->group(), trials[1]->group());
+  ASSERT_NE(trials[0]->group_name(), trials[1]->group_name());
+}
+
+TEST_F(EntropyProviderTest, SHA1Entropy) {
+  double results[] = {
+    GenerateSHA1Entropy("hi", "1"),
+    GenerateSHA1Entropy("there", "1"),
+  };
+  ASSERT_NE(results[0], results[1]);
+  for (size_t i = 0; i < arraysize(results); ++i) {
+    ASSERT_LE(0.0, results[i]);
+    ASSERT_GT(1.0, results[i]);
+  }
+
+  ASSERT_EQ(GenerateSHA1Entropy("yo", "1"),
+            GenerateSHA1Entropy("yo", "1"));
+  ASSERT_NE(GenerateSHA1Entropy("yo", "something"),
+            GenerateSHA1Entropy("yo", "else"));
+}
+
+TEST_F(EntropyProviderTest, PermutedEntropy) {
+  const size_t kMaxEntropySize = (1 << 13);
+  double results[] = {
+    GeneratePermutedEntropy(1234, kMaxEntropySize, "1"),
+    GeneratePermutedEntropy(4321, kMaxEntropySize, "1"),
+  };
+  ASSERT_NE(results[0], results[1]);
+  for (size_t i = 0; i < arraysize(results); ++i) {
+    ASSERT_LE(0.0, results[i]);
+    ASSERT_GT(1.0, results[i]);
+  }
+
+  ASSERT_EQ(GeneratePermutedEntropy(1234, kMaxEntropySize, "1"),
+            GeneratePermutedEntropy(1234, kMaxEntropySize, "1"));
+  ASSERT_NE(GeneratePermutedEntropy(1234, kMaxEntropySize, "something"),
+            GeneratePermutedEntropy(1234, kMaxEntropySize, "else"));
+}
+
+TEST_F(EntropyProviderTest, SHA1EntropyIsUniform) {
+  // Choose a random start number but go sequentially from there, so
+  // that each test tries a different range but we never provide uniformly
+  // distributed input data.
+  int current_number = base::RandInt(0, std::numeric_limits<int>::max());

[Ilya Sherman, 2012/08/17 07:34:28]

We should print the seed on failure, so that failures are reproducible.

+
+  // The expected value of a random distribution is the average over all
+  // samples as the number of samples approaches infinity.  For a uniform
+  // distribution from [0.0, 1.0) this would be 0.5.
+  //
+  // We do kSamplesBetweenChecks at a time and check if the value has converged
+  // to a narrow interval around 0.5.  A non-uniform distribution would likely
+  // converge at something different, or not converge consistently within this
+  // range (i.e. the test would start timing out occasionally).

[Ilya Sherman, 2012/08/17 07:34:28]

Hmm, this sounds like it's just checking that the distribution is symmetric, not
that it's uniform.  Why not do something like have 20 buckets and check their
counts?

[Alexei Svitkine (slow), 2012/08/20 16:02:55]

I've now replaces this test with one that distributes 100000 samples between 20
buckets and checks the min and max sizes of the buckets and the standard
deviation of the counts per bucket.

The results seem more or less consistent between the high entropy source using
SHA1 and the low entropy source using the permuted method, although still having
more variance than I expected.

For example, here's the output from a run of both:

[ RUN      ] EntropyProviderTest.SHA1EntropyIsUniform
min = 4871, max = 5107, stddev = 63.812225
min = 4850, max = 5129, stddev = 70.342022
min = 4875, max = 5185, stddev = 86.602540
[       OK ] EntropyProviderTest.SHA1EntropyIsUniform (2950 ms)
[ RUN      ] EntropyProviderTest.PermutedEntropyIsUniform
min = 4933, max = 5071, stddev = 44.294469
min = 4817, max = 5194, stddev = 74.188948
min = 4894, max = 5109, stddev = 58.932164
[       OK ] EntropyProviderTest.PermutedEntropyIsUniform (515 ms)


I am not sure what's a good way to choose the success / failure criteria for
such a test without introducing flakiness. For example, I've seen the standard
deviation go to as far as 105. So unless we make it really high (like 200), it
seems like the test would be prone to be flaky. Any suggestions?

+  int kSamplesBetweenChecks = 300;
+  int num_samples = 0;
+  double total_value = 0.0;
+  while (true) {

[Ilya Sherman, 2012/08/17 07:34:28]

Rather than having a while (true) loop, let's figure out how many iterations we
need to gain 99.999999% confidence for convergence, and iterate that many times.

+    for (int i = 0; i < kSamplesBetweenChecks; ++i) {
+      total_value += GenerateSHA1Entropy(
+          base::IntToString(current_number++), "salt");
+      num_samples++;
+    }
+
+    double average = total_value / num_samples;
+    double kExpectedMin = 0.48;
+    double kExpectedMax = 0.52;

[Ilya Sherman, 2012/08/17 07:34:28]

This is a pretty big range for the high-entropy source.  Do we really expect so
much variance?

+
+    if (num_samples > 1000 &&
+        (average < kExpectedMin || average > kExpectedMax)) {
+      // Only printed once we have enough samples that it's very unlikely
+      // things haven't converged.
+      printf("After %d samples, the average was %f, outside the expected\n"
+             "range (%f, %f). We will add more samples and check after every\n"
+             "%d samples. If the average does not converge, something\n"
+             "is broken. If it does converge, the test will pass.\n",
+             num_samples, average,
+             kExpectedMin, kExpectedMax, kSamplesBetweenChecks);
+    } else {
+      // Success.
+      break;
+    }
+  }
+}
+
+TEST_F(EntropyProviderTest, PermutedEntropyIsUniform) {
+  // Choose a random start number but go sequentially from there, so
+  // that each test tries a different range but we never provide uniformly
+  // distributed input data.
+  const size_t kMaxEntropySize = (1 << 13);
+  int current_number = base::RandInt(0, kMaxEntropySize - 1);
+
+  // The expected value of a random distribution is the average over all
+  // samples as the number of samples approaches infinity.  For a uniform
+  // distribution from [0.0, 1.0) this would be 0.5.
+  //
+  // We do kSamplesBetweenChecks at a time and check if the value has converged
+  // to a narrow interval around 0.5.  A non-uniform distribution would likely
+  // converge at something different, or not converge consistently within this
+  // range (i.e. the test would start timing out occasionally).
+  int kSamplesBetweenChecks = 300;
+  int num_samples = 0;
+  double total_value = 0.0;
+  while (true) {
+    for (int i = 0; i < kSamplesBetweenChecks; ++i) {
+      total_value += GeneratePermutedEntropy(current_number++ % kMaxEntropySize,
+                                             kMaxEntropySize, "salt");
+      num_samples++;
+    }
+
+    double average = total_value / num_samples;
+    double kExpectedMin = 0.48;
+    double kExpectedMax = 0.52;
+
+    if (num_samples > 1000 &&
+        (average < kExpectedMin || average > kExpectedMax)) {
+      // Only printed once we have enough samples that it's very unlikely
+      // things haven't converged.
+      printf("After %d samples, the average was %f, outside the expected\n"
+             "range (%f, %f). We will add more samples and check after every\n"
+             "%d samples. If the average does not converge, something\n"
+             "is broken. If it does converge, the test will pass.\n",
+             num_samples, average,
+             kExpectedMin, kExpectedMax, kSamplesBetweenChecks);
+    } else {
+      // Success.
+      break;
+    }
+  }
+}
+
+TEST_F(EntropyProviderTest, SeededRandGeneratorIsUniform) {
+  // Verifies. that SeededRandGenerator has a uniform distribution.
+  //
+  // Mirrors RandUtilTest.RandGeneratorIsUniform in base/rand_util_unittest.cc.
+
+  const uint32 kTopOfRange = (std::numeric_limits<uint32>::max() / 4ULL) * 3ULL;
+  const uint32 kExpectedAverage = kTopOfRange / 2ULL;
+  const uint32 kAllowedVariance = kExpectedAverage / 50ULL;  // +/- 2%
+  const int kMinAttempts = 1000;
+  const int kMaxAttempts = 1000000;
+
+  const std::string trial_names[] = {
+    "TestTrial",
+    "AnotherTestTrial",
+    "NewTabButton",
+  };
+
+  for (size_t i = 0; i < arraysize(trial_names); ++i) {
+    const uint32 seed = internal::HashName(trial_names[i]);
+    internal::SeededRandGenerator rand_generator(seed);
+
+    double cumulative_average = 0.0;
+    int count = 0;
+    while (count < kMaxAttempts) {
+      uint32 value = rand_generator(kTopOfRange);
+      cumulative_average = (count * cumulative_average + value) / (count + 1);
+
+      // Don't quit too quickly for things to start converging, or we may have
+      // a false positive.
+      if (count > kMinAttempts &&
+          kExpectedAverage - kAllowedVariance < cumulative_average &&
+          cumulative_average < kExpectedAverage + kAllowedVariance) {
+        break;
+      }
+
+      ++count;
+    }
+
+    ASSERT_LT(count, kMaxAttempts) << "Expected average was " <<
+        kExpectedAverage << ", average ended at " << cumulative_average;
+  }
+}
+