rand_util_unittest.cc 10 KB

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