// Copyright 2017 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/allocator/partition_allocator/address_space_randomization.h"

#include <vector>

#include "starboard/types.h"

#include "base/allocator/partition_allocator/page_allocator.h"
#include "base/logging.h"
#include "build/build_config.h"
#include "testing/gtest/include/gtest/gtest.h"

#if defined(OS_WIN)
#include <windows.h>
#include "base/win/windows_version.h"
// VersionHelpers.h must be included after windows.h.
#include <VersionHelpers.h>
#endif

namespace base {

namespace {

uintptr_t GetMask() {
  uintptr_t mask = internal::kASLRMask;
#if defined(ARCH_CPU_64_BITS)
// Sanitizers use their own kASLRMask constant.
#if defined(OS_WIN) && !defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
  if (!IsWindows8Point1OrGreater()) {
    mask = internal::kASLRMaskBefore8_10;
  }
#endif  // defined(OS_WIN) && !defined(MEMORY_TOOL_REPLACES_ALLOCATOR))
#elif defined(ARCH_CPU_32_BITS)
#if defined(OS_WIN)
  BOOL is_wow64 = FALSE;
  if (!IsWow64Process(GetCurrentProcess(), &is_wow64))
    is_wow64 = FALSE;
  if (!is_wow64) {
    mask = 0;
  }
#endif  // defined(OS_WIN)
#endif  // defined(ARCH_CPU_32_BITS)
  return mask;
}

const size_t kSamples = 100;

uintptr_t GetAddressBits() {
  return reinterpret_cast<uintptr_t>(base::GetRandomPageBase());
}

uintptr_t GetRandomBits() {
  return GetAddressBits() - internal::kASLROffset;
}

}  // namespace

// Configurations without ASLR are tested here.
TEST(AddressSpaceRandomizationTest, DisabledASLR) {
  uintptr_t mask = GetMask();
  if (!mask) {
#if defined(OS_WIN) && defined(ARCH_CPU_32_BITS)
    // ASLR should be turned off on 32-bit Windows.
    EXPECT_EQ(nullptr, base::GetRandomPageBase());
#else
    // Otherwise, nullptr is very unexpected.
    EXPECT_NE(nullptr, base::GetRandomPageBase());
#endif
  }
}

TEST(AddressSpaceRandomizationTest, Alignment) {
  uintptr_t mask = GetMask();
  if (!mask)
    return;

  for (size_t i = 0; i < kSamples; ++i) {
    uintptr_t address = GetAddressBits();
    EXPECT_EQ(0ULL, (address & kPageAllocationGranularityOffsetMask));
  }
}

TEST(AddressSpaceRandomizationTest, Range) {
  uintptr_t mask = GetMask();
  if (!mask)
    return;

  uintptr_t min = internal::kASLROffset;
  uintptr_t max = internal::kASLROffset + internal::kASLRMask;
  for (size_t i = 0; i < kSamples; ++i) {
    uintptr_t address = GetAddressBits();
    EXPECT_LE(min, address);
    EXPECT_GE(max + mask, address);
  }
}

TEST(AddressSpaceRandomizationTest, Predictable) {
  uintptr_t mask = GetMask();
  if (!mask)
    return;

  const uintptr_t kInitialSeed = 0xfeed5eedULL;
  base::SetRandomPageBaseSeed(kInitialSeed);

  std::vector<uintptr_t> sequence;
  for (size_t i = 0; i < kSamples; ++i) {
    uintptr_t address = reinterpret_cast<uintptr_t>(base::GetRandomPageBase());
    sequence.push_back(address);
  }

  base::SetRandomPageBaseSeed(kInitialSeed);

  for (size_t i = 0; i < kSamples; ++i) {
    uintptr_t address = reinterpret_cast<uintptr_t>(base::GetRandomPageBase());
    EXPECT_EQ(address, sequence[i]);
  }
}

// This randomness test is adapted from V8's PRNG tests.

// Chi squared for getting m 0s out of n bits.
double ChiSquared(int m, int n) {
  double ys_minus_np1 = (m - n / 2.0);
  double chi_squared_1 = ys_minus_np1 * ys_minus_np1 * 2.0 / n;
  double ys_minus_np2 = ((n - m) - n / 2.0);
  double chi_squared_2 = ys_minus_np2 * ys_minus_np2 * 2.0 / n;
  return chi_squared_1 + chi_squared_2;
}

// Test for correlations between recent bits from the PRNG, or bits that are
// biased.
void RandomBitCorrelation(int random_bit) {
  uintptr_t mask = GetMask();
  if ((mask & (1ULL << random_bit)) == 0)
    return;  // bit is always 0.

#ifdef DEBUG
  constexpr int kHistory = 2;
  constexpr int kRepeats = 1000;
#else
  constexpr int kHistory = 8;
  constexpr int kRepeats = 10000;
#endif
  constexpr int kPointerBits = 8 * sizeof(void*);
  uintptr_t history[kHistory];
  // The predictor bit is either constant 0 or 1, or one of the bits from the
  // history.
  for (int predictor_bit = -2; predictor_bit < kPointerBits; predictor_bit++) {
    // The predicted bit is one of the bits from the PRNG.
    for (int ago = 0; ago < kHistory; ago++) {
      // We don't want to check whether each bit predicts itself.
      if (ago == 0 && predictor_bit == random_bit)
        continue;

      // Enter the new random value into the history.
      for (int i = ago; i >= 0; i--) {
        history[i] = GetRandomBits();
      }

      // Find out how many of the bits are the same as the prediction bit.
      int m = 0;
      for (int i = 0; i < kRepeats; i++) {
        uintptr_t random = GetRandomBits();
        for (int j = ago - 1; j >= 0; j--)
          history[j + 1] = history[j];
        history[0] = random;

        int predicted;
        if (predictor_bit >= 0) {
          predicted = (history[ago] >> predictor_bit) & 1;
        } else {
          predicted = predictor_bit == -2 ? 0 : 1;
        }
        int bit = (random >> random_bit) & 1;
        if (bit == predicted)
          m++;
      }

      // Chi squared analysis for k = 2 (2, states: same/not-same) and one
      // degree of freedom (k - 1).
      double chi_squared = ChiSquared(m, kRepeats);
      // For 1 degree of freedom this corresponds to 1 in a million.  We are
      // running ~8000 tests, so that would be surprising.
      CHECK_GE(24, chi_squared);
      // If the predictor bit is a fixed 0 or 1 then it makes no sense to
      // repeat the test with a different age.
      if (predictor_bit < 0)
        break;
    }
  }
}

// TODO(crbug.com/811881): These are flaky on Fuchsia
#if !defined(OS_FUCHSIA)

// Tests are fairly slow, so give each random bit its own test.
#define TEST_RANDOM_BIT(BIT)                                        \
  TEST(AddressSpaceRandomizationTest, RandomBitCorrelations##BIT) { \
    RandomBitCorrelation(BIT);                                      \
  }

// The first 12 bits on all platforms are always 0.
TEST_RANDOM_BIT(12)
TEST_RANDOM_BIT(13)
TEST_RANDOM_BIT(14)
TEST_RANDOM_BIT(15)
TEST_RANDOM_BIT(16)
TEST_RANDOM_BIT(17)
TEST_RANDOM_BIT(18)
TEST_RANDOM_BIT(19)
TEST_RANDOM_BIT(20)
TEST_RANDOM_BIT(21)
TEST_RANDOM_BIT(22)
TEST_RANDOM_BIT(23)
TEST_RANDOM_BIT(24)
TEST_RANDOM_BIT(25)
TEST_RANDOM_BIT(26)
TEST_RANDOM_BIT(27)
TEST_RANDOM_BIT(28)
TEST_RANDOM_BIT(29)
TEST_RANDOM_BIT(30)
TEST_RANDOM_BIT(31)
#if defined(ARCH_CPU_64_BITS)
TEST_RANDOM_BIT(32)
TEST_RANDOM_BIT(33)
TEST_RANDOM_BIT(34)
TEST_RANDOM_BIT(35)
TEST_RANDOM_BIT(36)
TEST_RANDOM_BIT(37)
TEST_RANDOM_BIT(38)
TEST_RANDOM_BIT(39)
TEST_RANDOM_BIT(40)
TEST_RANDOM_BIT(41)
TEST_RANDOM_BIT(42)
TEST_RANDOM_BIT(43)
TEST_RANDOM_BIT(44)
TEST_RANDOM_BIT(45)
TEST_RANDOM_BIT(46)
TEST_RANDOM_BIT(47)
TEST_RANDOM_BIT(48)
// No platforms have more than 48 address bits.
#endif  // defined(ARCH_CPU_64_BITS)

#endif  // defined(OS_FUCHSIA)

#undef TEST_RANDOM_BIT

}  // namespace base