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