base/rand_util_unittest.cc

   1 // Copyright 2011 The Chromium Authors
   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 "base/rand_util.h"
   6
   7 #include <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <algorithm>
  11 #include <cmath>
  12 #include <limits>
  13 #include <memory>
  14 #include <vector>
  15
  16 #include "base/logging.h"
  17 #include "base/time/time.h"
  18 #include "testing/gtest/include/gtest/gtest.h"
  19
  20 namespace base {
  21
  22 namespace {
  23
  24 const int kIntMin = std::numeric_limits<int>::min();
  25 const int kIntMax = std::numeric_limits<int>::max();
  26
  27 }  // namespace
  28
  29 TEST(RandUtilTest, RandInt) {
  30   EXPECT_EQ(base::RandInt(0, 0), 0);
  31   EXPECT_EQ(base::RandInt(kIntMin, kIntMin), kIntMin);
  32   EXPECT_EQ(base::RandInt(kIntMax, kIntMax), kIntMax);
  33
  34   // Check that the DCHECKS in RandInt() don't fire due to internal overflow.
  35   // There was a 50% chance of that happening, so calling it 40 times means
  36   // the chances of this passing by accident are tiny (9e-13).
  37   for (int i = 0; i < 40; ++i)
  38     base::RandInt(kIntMin, kIntMax);
  39 }
  40
  41 TEST(RandUtilTest, RandDouble) {
  42   // Force 64-bit precision, making sure we're not in a 80-bit FPU register.
  43   volatile double number = base::RandDouble();
  44   EXPECT_GT(1.0, number);
  45   EXPECT_LE(0.0, number);
  46 }
  47
  48 TEST(RandUtilTest, RandFloat) {
  49   // Force 32-bit precision, making sure we're not in an 80-bit FPU register.
  50   volatile float number = base::RandFloat();
  51   EXPECT_GT(1.f, number);
  52   EXPECT_LE(0.f, number);
  53 }
  54
  55 TEST(RandUtilTest, BitsToOpenEndedUnitInterval) {
  56   // Force 64-bit precision, making sure we're not in an 80-bit FPU register.
  57   volatile double all_zeros = BitsToOpenEndedUnitInterval(0x0);
  58   EXPECT_EQ(0.0, all_zeros);
  59
  60   // Force 64-bit precision, making sure we're not in an 80-bit FPU register.
  61   volatile double smallest_nonzero = BitsToOpenEndedUnitInterval(0x1);
  62   EXPECT_LT(0.0, smallest_nonzero);
  63
  64   for (uint64_t i = 0x2; i < 0x10; ++i) {
  65     // Force 64-bit precision, making sure we're not in an 80-bit FPU register.
  66     volatile double number = BitsToOpenEndedUnitInterval(i);
  67     EXPECT_EQ(i * smallest_nonzero, number);
  68   }
  69
  70   // Force 64-bit precision, making sure we're not in an 80-bit FPU register.
  71   volatile double all_ones = BitsToOpenEndedUnitInterval(UINT64_MAX);
  72   EXPECT_GT(1.0, all_ones);
  73 }
  74
  75 TEST(RandUtilTest, BitsToOpenEndedUnitIntervalF) {
  76   // Force 32-bit precision, making sure we're not in an 80-bit FPU register.
  77   volatile float all_zeros = BitsToOpenEndedUnitIntervalF(0x0);
  78   EXPECT_EQ(0.f, all_zeros);
  79
  80   // Force 32-bit precision, making sure we're not in an 80-bit FPU register.
  81   volatile float smallest_nonzero = BitsToOpenEndedUnitIntervalF(0x1);
  82   EXPECT_LT(0.f, smallest_nonzero);
  83
  84   for (uint64_t i = 0x2; i < 0x10; ++i) {
  85     // Force 32-bit precision, making sure we're not in an 80-bit FPU register.
  86     volatile float number = BitsToOpenEndedUnitIntervalF(i);
  87     EXPECT_EQ(i * smallest_nonzero, number);
  88   }
  89
  90   // Force 32-bit precision, making sure we're not in an 80-bit FPU register.
  91   volatile float all_ones = BitsToOpenEndedUnitIntervalF(UINT64_MAX);
  92   EXPECT_GT(1.f, all_ones);
  93 }
  94
  95 TEST(RandUtilTest, RandBytes) {
  96   const size_t buffer_size = 50;
  97   char buffer[buffer_size];
  98   memset(buffer, 0, buffer_size);
  99   base::RandBytes(buffer, buffer_size);
 100   std::sort(buffer, buffer + buffer_size);
 101   // Probability of occurrence of less than 25 unique bytes in 50 random bytes
 102   // is below 10^-25.
 103   EXPECT_GT(std::unique(buffer, buffer + buffer_size) - buffer, 25);
 104 }
 105
 106 // Verify that calling base::RandBytes with an empty buffer doesn't fail.
 107 TEST(RandUtilTest, RandBytes0) {
 108   base::RandBytes(nullptr, 0);
 109 }
 110
 111 TEST(RandUtilTest, RandBytesAsString) {
 112   std::string random_string = base::RandBytesAsString(1);
 113   EXPECT_EQ(1U, random_string.size());
 114   random_string = base::RandBytesAsString(145);
 115   EXPECT_EQ(145U, random_string.size());
 116   char accumulator = 0;
 117   for (auto i : random_string)
 118     accumulator |= i;
 119   // In theory this test can fail, but it won't before the universe dies of
 120   // heat death.
 121   EXPECT_NE(0, accumulator);
 122 }
 123
 124 // Make sure that it is still appropriate to use RandGenerator in conjunction
 125 // with std::random_shuffle().
 126 TEST(RandUtilTest, RandGeneratorForRandomShuffle) {
 127   EXPECT_EQ(base::RandGenerator(1), 0U);
 128   EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(),
 129             std::numeric_limits<int64_t>::max());
 130 }
 131
 132 TEST(RandUtilTest, RandGeneratorIsUniform) {
 133   // Verify that RandGenerator has a uniform distribution. This is a
 134   // regression test that consistently failed when RandGenerator was
 135   // implemented this way:
 136   //
 137   //   return base::RandUint64() % max;
 138   //
 139   // A degenerate case for such an implementation is e.g. a top of
 140   // range that is 2/3rds of the way to MAX_UINT64, in which case the
 141   // bottom half of the range would be twice as likely to occur as the
 142   // top half. A bit of calculus care of jar@ shows that the largest
 143   // measurable delta is when the top of the range is 3/4ths of the
 144   // way, so that's what we use in the test.
 145   constexpr uint64_t kTopOfRange =
 146       (std::numeric_limits<uint64_t>::max() / 4ULL) * 3ULL;
 147   constexpr double kExpectedAverage = static_cast<double>(kTopOfRange / 2);
 148   constexpr double kAllowedVariance = kExpectedAverage / 50.0;  // +/- 2%
 149   constexpr int kMinAttempts = 1000;
 150   constexpr int kMaxAttempts = 1000000;
 151
 152   double cumulative_average = 0.0;
 153   int count = 0;
 154   while (count < kMaxAttempts) {
 155     uint64_t value = base::RandGenerator(kTopOfRange);
 156     cumulative_average = (count * cumulative_average + value) / (count + 1);
 157
 158     // Don't quit too quickly for things to start converging, or we may have
 159     // a false positive.
 160     if (count > kMinAttempts &&
 161         kExpectedAverage - kAllowedVariance < cumulative_average &&
 162         cumulative_average < kExpectedAverage + kAllowedVariance) {
 163       break;
 164     }
 165
 166     ++count;
 167   }
 168
 169   ASSERT_LT(count, kMaxAttempts) << "Expected average was " << kExpectedAverage
 170                                  << ", average ended at " << cumulative_average;
 171 }
 172
 173 TEST(RandUtilTest, RandUint64ProducesBothValuesOfAllBits) {
 174   // This tests to see that our underlying random generator is good
 175   // enough, for some value of good enough.
 176   uint64_t kAllZeros = 0ULL;
 177   uint64_t kAllOnes = ~kAllZeros;
 178   uint64_t found_ones = kAllZeros;
 179   uint64_t found_zeros = kAllOnes;
 180
 181   for (size_t i = 0; i < 1000; ++i) {
 182     uint64_t value = base::RandUint64();
 183     found_ones |= value;
 184     found_zeros &= value;
 185
 186     if (found_zeros == kAllZeros && found_ones == kAllOnes)
 187       return;
 188   }
 189
 190   FAIL() << "Didn't achieve all bit values in maximum number of tries.";
 191 }
 192
 193 TEST(RandUtilTest, RandBytesLonger) {
 194   // Fuchsia can only retrieve 256 bytes of entropy at a time, so make sure we
 195   // handle longer requests than that.
 196   std::string random_string0 = base::RandBytesAsString(255);
 197   EXPECT_EQ(255u, random_string0.size());
 198   std::string random_string1 = base::RandBytesAsString(1023);
 199   EXPECT_EQ(1023u, random_string1.size());
 200   std::string random_string2 = base::RandBytesAsString(4097);
 201   EXPECT_EQ(4097u, random_string2.size());
 202 }
 203
 204 // Benchmark test for RandBytes().  Disabled since it's intentionally slow and
 205 // does not test anything that isn't already tested by the existing RandBytes()
 206 // tests.
 207 TEST(RandUtilTest, DISABLED_RandBytesPerf) {
 208   // Benchmark the performance of |kTestIterations| of RandBytes() using a
 209   // buffer size of |kTestBufferSize|.
 210   const int kTestIterations = 10;
 211   const size_t kTestBufferSize = 1 * 1024 * 1024;
 212
 213   std::unique_ptr<uint8_t[]> buffer(new uint8_t[kTestBufferSize]);
 214   const base::TimeTicks now = base::TimeTicks::Now();
 215   for (int i = 0; i < kTestIterations; ++i)
 216     base::RandBytes(buffer.get(), kTestBufferSize);
 217   const base::TimeTicks end = base::TimeTicks::Now();
 218
 219   LOG(INFO) << "RandBytes(" << kTestBufferSize
 220             << ") took: " << (end - now).InMicroseconds() << "µs";
 221 }
 222
 223 TEST(RandUtilTest, InsecureRandomGeneratorProducesBothValuesOfAllBits) {
 224   // This tests to see that our underlying random generator is good
 225   // enough, for some value of good enough.
 226   uint64_t kAllZeros = 0ULL;
 227   uint64_t kAllOnes = ~kAllZeros;
 228   uint64_t found_ones = kAllZeros;
 229   uint64_t found_zeros = kAllOnes;
 230
 231   InsecureRandomGenerator generator;
 232
 233   for (size_t i = 0; i < 1000; ++i) {
 234     uint64_t value = generator.RandUint64();
 235     found_ones |= value;
 236     found_zeros &= value;
 237
 238     if (found_zeros == kAllZeros && found_ones == kAllOnes)
 239       return;
 240   }
 241
 242   FAIL() << "Didn't achieve all bit values in maximum number of tries.";
 243 }
 244
 245 namespace {
 246
 247 constexpr double kXp1Percent = -2.33;
 248 constexpr double kXp99Percent = 2.33;
 249
 250 double ChiSquaredCriticalValue(double nu, double x_p) {
 251   // From "The Art Of Computer Programming" (TAOCP), Volume 2, Section 3.3.1,
 252   // Table 1. This is the asymptotic value for nu > 30, up to O(1 / sqrt(nu)).
 253   return nu + sqrt(2. * nu) * x_p + 2. / 3. * (x_p * x_p) - 2. / 3.;
 254 }
 255
 256 int ExtractBits(uint64_t value, int from_bit, int num_bits) {
 257   return (value >> from_bit) & ((1 << num_bits) - 1);
 258 }
 259
 260 // Performs a Chi-Squared test on a subset of |num_bits| extracted starting from
 261 // |from_bit| in the generated value.
 262 //
 263 // See TAOCP, Volume 2, Section 3.3.1, and
 264 // https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test for details.
 265 //
 266 // This is only one of the many, many random number generator test we could do,
 267 // but they are cumbersome, as they are typically very slow, and expected to
 268 // fail from time to time, due to their probabilistic nature.
 269 //
 270 // The generator we use has however been vetted with the BigCrush test suite
 271 // from Marsaglia, so this should suffice as a smoke test that our
 272 // implementation is wrong.
 273 bool ChiSquaredTest(InsecureRandomGenerator& gen,
 274                     size_t n,
 275                     int from_bit,
 276                     int num_bits) {
 277   const int range = 1 << num_bits;
 278   CHECK_EQ(static_cast<int>(n % range), 0) << "Makes computations simpler";
 279   std::vector<size_t> samples(range, 0);
 280
 281   // Count how many samples pf each value are found. All buckets should be
 282   // almost equal if the generator is suitably uniformly random.
 283   for (size_t i = 0; i < n; i++) {
 284     int sample = ExtractBits(gen.RandUint64(), from_bit, num_bits);
 285     samples[sample] += 1;
 286   }
 287
 288   // Compute the Chi-Squared statistic, which is:
 289   // \Sum_{k=0}^{range-1} \frac{(count - expected)^2}{expected}
 290   double chi_squared = 0.;
 291   double expected_count = n / range;
 292   for (size_t sample_count : samples) {
 293     double deviation = sample_count - expected_count;
 294     chi_squared += (deviation * deviation) / expected_count;
 295   }
 296
 297   // The generator should produce numbers that are not too far of (chi_squared
 298   // lower than a given quantile), but not too close to the ideal distribution
 299   // either (chi_squared is too low).
 300   //
 301   // See The Art Of Computer Programming, Volume 2, Section 3.3.1 for details.
 302   return chi_squared > ChiSquaredCriticalValue(range - 1, kXp1Percent) &&
 303          chi_squared < ChiSquaredCriticalValue(range - 1, kXp99Percent);
 304 }
 305
 306 }  // namespace
 307
 308 TEST(RandUtilTest, InsecureRandomGeneratorChiSquared) {
 309   constexpr int kIterations = 50;
 310
 311   // Specifically test the low bits, which are usually weaker in random number
 312   // generators. We don't use them for the 32 bit number generation, but let's
 313   // make sure they are still suitable.
 314   for (int start_bit : {1, 2, 3, 8, 12, 20, 32, 48, 54}) {
 315     int pass_count = 0;
 316     for (int i = 0; i < kIterations; i++) {
 317       size_t samples = 1 << 16;
 318       InsecureRandomGenerator gen;
 319       // Fix the seed to make the test non-flaky.
 320       gen.ReseedForTesting(kIterations + 1);
 321       bool pass = ChiSquaredTest(gen, samples, start_bit, 8);
 322       pass_count += pass;
 323     }
 324
 325     // We exclude 1% on each side, so we expect 98% of tests to pass, meaning 98
 326     // * kIterations / 100. However this is asymptotic, so add a bit of leeway.
 327     int expected_pass_count = (kIterations * 98) / 100;
 328     EXPECT_GE(pass_count, expected_pass_count - ((kIterations * 2) / 100))
 329         << "For start_bit = " << start_bit;
 330   }
 331 }
 332
 333 TEST(RandUtilTest, InsecureRandomGeneratorRandDouble) {
 334   InsecureRandomGenerator gen;
 335
 336   for (int i = 0; i < 1000; i++) {
 337     volatile double x = gen.RandDouble();
 338     EXPECT_GE(x, 0.);
 339     EXPECT_LT(x, 1.);
 340   }
 341 }
 342 }  // namespace base