123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295 |
- // Copyright (c) 2011 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 "base/rand_util.h"
- #include <stddef.h>
- #include <stdint.h>
- #include <algorithm>
- #include <cmath>
- #include <limits>
- #include <memory>
- #include <vector>
- #include "base/logging.h"
- #include "base/time/time.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace base {
- namespace {
- const int kIntMin = std::numeric_limits<int>::min();
- const int kIntMax = std::numeric_limits<int>::max();
- } // namespace
- TEST(RandUtilTest, RandInt) {
- EXPECT_EQ(base::RandInt(0, 0), 0);
- EXPECT_EQ(base::RandInt(kIntMin, kIntMin), kIntMin);
- EXPECT_EQ(base::RandInt(kIntMax, kIntMax), kIntMax);
- // Check that the DCHECKS in RandInt() don't fire due to internal overflow.
- // There was a 50% chance of that happening, so calling it 40 times means
- // the chances of this passing by accident are tiny (9e-13).
- for (int i = 0; i < 40; ++i)
- base::RandInt(kIntMin, kIntMax);
- }
- TEST(RandUtilTest, RandDouble) {
- // Force 64-bit precision, making sure we're not in a 80-bit FPU register.
- volatile double number = base::RandDouble();
- EXPECT_GT(1.0, number);
- EXPECT_LE(0.0, number);
- }
- TEST(RandUtilTest, RandBytes) {
- const size_t buffer_size = 50;
- char buffer[buffer_size];
- memset(buffer, 0, buffer_size);
- base::RandBytes(buffer, buffer_size);
- std::sort(buffer, buffer + buffer_size);
- // Probability of occurrence of less than 25 unique bytes in 50 random bytes
- // is below 10^-25.
- EXPECT_GT(std::unique(buffer, buffer + buffer_size) - buffer, 25);
- }
- // Verify that calling base::RandBytes with an empty buffer doesn't fail.
- TEST(RandUtilTest, RandBytes0) {
- base::RandBytes(nullptr, 0);
- }
- TEST(RandUtilTest, RandBytesAsString) {
- std::string random_string = base::RandBytesAsString(1);
- EXPECT_EQ(1U, random_string.size());
- random_string = base::RandBytesAsString(145);
- EXPECT_EQ(145U, random_string.size());
- char accumulator = 0;
- for (auto i : random_string)
- accumulator |= i;
- // In theory this test can fail, but it won't before the universe dies of
- // heat death.
- EXPECT_NE(0, accumulator);
- }
- // Make sure that it is still appropriate to use RandGenerator in conjunction
- // with std::random_shuffle().
- TEST(RandUtilTest, RandGeneratorForRandomShuffle) {
- EXPECT_EQ(base::RandGenerator(1), 0U);
- EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(),
- std::numeric_limits<int64_t>::max());
- }
- TEST(RandUtilTest, RandGeneratorIsUniform) {
- // Verify that RandGenerator has a uniform distribution. This is a
- // regression test that consistently failed when RandGenerator was
- // implemented this way:
- //
- // return base::RandUint64() % max;
- //
- // A degenerate case for such an implementation is e.g. a top of
- // range that is 2/3rds of the way to MAX_UINT64, in which case the
- // bottom half of the range would be twice as likely to occur as the
- // top half. A bit of calculus care of jar@ shows that the largest
- // measurable delta is when the top of the range is 3/4ths of the
- // way, so that's what we use in the test.
- constexpr uint64_t kTopOfRange =
- (std::numeric_limits<uint64_t>::max() / 4ULL) * 3ULL;
- constexpr double kExpectedAverage = static_cast<double>(kTopOfRange / 2);
- constexpr double kAllowedVariance = kExpectedAverage / 50.0; // +/- 2%
- constexpr int kMinAttempts = 1000;
- constexpr int kMaxAttempts = 1000000;
- double cumulative_average = 0.0;
- int count = 0;
- while (count < kMaxAttempts) {
- uint64_t value = base::RandGenerator(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;
- }
- TEST(RandUtilTest, RandUint64ProducesBothValuesOfAllBits) {
- // This tests to see that our underlying random generator is good
- // enough, for some value of good enough.
- uint64_t kAllZeros = 0ULL;
- uint64_t kAllOnes = ~kAllZeros;
- uint64_t found_ones = kAllZeros;
- uint64_t found_zeros = kAllOnes;
- for (size_t i = 0; i < 1000; ++i) {
- uint64_t value = base::RandUint64();
- found_ones |= value;
- found_zeros &= value;
- if (found_zeros == kAllZeros && found_ones == kAllOnes)
- return;
- }
- FAIL() << "Didn't achieve all bit values in maximum number of tries.";
- }
- TEST(RandUtilTest, RandBytesLonger) {
- // Fuchsia can only retrieve 256 bytes of entropy at a time, so make sure we
- // handle longer requests than that.
- std::string random_string0 = base::RandBytesAsString(255);
- EXPECT_EQ(255u, random_string0.size());
- std::string random_string1 = base::RandBytesAsString(1023);
- EXPECT_EQ(1023u, random_string1.size());
- std::string random_string2 = base::RandBytesAsString(4097);
- EXPECT_EQ(4097u, random_string2.size());
- }
- // Benchmark test for RandBytes(). Disabled since it's intentionally slow and
- // does not test anything that isn't already tested by the existing RandBytes()
- // tests.
- TEST(RandUtilTest, DISABLED_RandBytesPerf) {
- // Benchmark the performance of |kTestIterations| of RandBytes() using a
- // buffer size of |kTestBufferSize|.
- const int kTestIterations = 10;
- const size_t kTestBufferSize = 1 * 1024 * 1024;
- std::unique_ptr<uint8_t[]> buffer(new uint8_t[kTestBufferSize]);
- const base::TimeTicks now = base::TimeTicks::Now();
- for (int i = 0; i < kTestIterations; ++i)
- base::RandBytes(buffer.get(), kTestBufferSize);
- const base::TimeTicks end = base::TimeTicks::Now();
- LOG(INFO) << "RandBytes(" << kTestBufferSize
- << ") took: " << (end - now).InMicroseconds() << "µs";
- }
- TEST(RandUtilTest, InsecureRandomGeneratorProducesBothValuesOfAllBits) {
- // This tests to see that our underlying random generator is good
- // enough, for some value of good enough.
- uint64_t kAllZeros = 0ULL;
- uint64_t kAllOnes = ~kAllZeros;
- uint64_t found_ones = kAllZeros;
- uint64_t found_zeros = kAllOnes;
- InsecureRandomGenerator generator;
- for (size_t i = 0; i < 1000; ++i) {
- uint64_t value = generator.RandUint64();
- found_ones |= value;
- found_zeros &= value;
- if (found_zeros == kAllZeros && found_ones == kAllOnes)
- return;
- }
- FAIL() << "Didn't achieve all bit values in maximum number of tries.";
- }
- namespace {
- constexpr double kXp1Percent = -2.33;
- constexpr double kXp99Percent = 2.33;
- double ChiSquaredCriticalValue(double nu, double x_p) {
- // From "The Art Of Computer Programming" (TAOCP), Volume 2, Section 3.3.1,
- // Table 1. This is the asymptotic value for nu > 30, up to O(1 / sqrt(nu)).
- return nu + sqrt(2. * nu) * x_p + 2. / 3. * (x_p * x_p) - 2. / 3.;
- }
- int ExtractBits(uint64_t value, int from_bit, int num_bits) {
- return (value >> from_bit) & ((1 << num_bits) - 1);
- }
- // Performs a Chi-Squared test on a subset of |num_bits| extracted starting from
- // |from_bit| in the generated value.
- //
- // See TAOCP, Volume 2, Section 3.3.1, and
- // https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test for details.
- //
- // This is only one of the many, many random number generator test we could do,
- // but they are cumbersome, as they are typically very slow, and expected to
- // fail from time to time, due to their probabilistic nature.
- //
- // The generator we use has however been vetted with the BigCrush test suite
- // from Marsaglia, so this should suffice as a smoke test that our
- // implementation is wrong.
- bool ChiSquaredTest(InsecureRandomGenerator& gen,
- size_t n,
- int from_bit,
- int num_bits) {
- const int range = 1 << num_bits;
- CHECK_EQ(static_cast<int>(n % range), 0) << "Makes computations simpler";
- std::vector<size_t> samples(range, 0);
- // Count how many samples pf each value are found. All buckets should be
- // almost equal if the generator is suitably uniformly random.
- for (size_t i = 0; i < n; i++) {
- int sample = ExtractBits(gen.RandUint64(), from_bit, num_bits);
- samples[sample] += 1;
- }
- // Compute the Chi-Squared statistic, which is:
- // \Sum_{k=0}^{range-1} \frac{(count - expected)^2}{expected}
- double chi_squared = 0.;
- double expected_count = n / range;
- for (size_t sample_count : samples) {
- double deviation = sample_count - expected_count;
- chi_squared += (deviation * deviation) / expected_count;
- }
- // The generator should produce numbers that are not too far of (chi_squared
- // lower than a given quantile), but not too close to the ideal distribution
- // either (chi_squared is too low).
- //
- // See The Art Of Computer Programming, Volume 2, Section 3.3.1 for details.
- return chi_squared > ChiSquaredCriticalValue(range - 1, kXp1Percent) &&
- chi_squared < ChiSquaredCriticalValue(range - 1, kXp99Percent);
- }
- } // namespace
- TEST(RandUtilTest, InsecureRandomGeneratorChiSquared) {
- constexpr int kIterations = 50;
- // Specifically test the low bits, which are usually weaker in random number
- // generators. We don't use them for the 32 bit number generation, but let's
- // make sure they are still suitable.
- for (int start_bit : {1, 2, 3, 8, 12, 20, 32, 48, 54}) {
- int pass_count = 0;
- for (int i = 0; i < kIterations; i++) {
- size_t samples = 1 << 16;
- InsecureRandomGenerator gen;
- // Fix the seed to make the test non-flaky.
- gen.ReseedForTesting(kIterations + 1);
- bool pass = ChiSquaredTest(gen, samples, start_bit, 8);
- pass_count += pass;
- }
- // We exclude 1% on each side, so we expect 98% of tests to pass, meaning 98
- // * kIterations / 100. However this is asymptotic, so add a bit of leeway.
- int expected_pass_count = (kIterations * 98) / 100;
- EXPECT_GE(pass_count, expected_pass_count - ((kIterations * 2) / 100))
- << "For start_bit = " << start_bit;
- }
- }
- TEST(RandUtilTest, InsecureRandomGeneratorRandDouble) {
- InsecureRandomGenerator gen;
- for (int i = 0; i < 1000; i++) {
- volatile double x = gen.RandDouble();
- EXPECT_GE(x, 0.);
- EXPECT_LT(x, 1.);
- }
- }
- } // namespace base
|