address_space_randomization_unittest.cc 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279
  1. // Copyright 2017 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/allocator/partition_allocator/address_space_randomization.h"
  5. #include <cstdint>
  6. #include <vector>
  7. #include "base/allocator/partition_allocator/page_allocator.h"
  8. #include "base/allocator/partition_allocator/partition_alloc_base/debug/debugging_buildflags.h"
  9. #include "base/allocator/partition_allocator/partition_alloc_check.h"
  10. #include "base/allocator/partition_allocator/random.h"
  11. #include "build/build_config.h"
  12. #include "testing/gtest/include/gtest/gtest.h"
  13. #if BUILDFLAG(IS_WIN)
  14. #include <windows.h>
  15. #include "base/win/windows_version.h"
  16. // versionhelpers.h must be included after windows.h.
  17. #include <versionhelpers.h>
  18. #endif
  19. namespace partition_alloc {
  20. namespace {
  21. uintptr_t GetMask() {
  22. uintptr_t mask = internal::ASLRMask();
  23. #if defined(ARCH_CPU_64_BITS)
  24. // Sanitizers use their own ASLR mask constant.
  25. #if BUILDFLAG(IS_WIN) && !defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
  26. if (!IsWindows8Point1OrGreater()) {
  27. mask = internal::ASLRMaskBefore8_10();
  28. }
  29. #endif // BUILDFLAG(IS_WIN) && !defined(MEMORY_TOOL_REPLACES_ALLOCATOR))
  30. #elif defined(ARCH_CPU_32_BITS)
  31. #if BUILDFLAG(IS_WIN)
  32. BOOL is_wow64 = FALSE;
  33. if (!IsWow64Process(GetCurrentProcess(), &is_wow64))
  34. is_wow64 = FALSE;
  35. if (!is_wow64) {
  36. mask = 0;
  37. }
  38. #endif // BUILDFLAG(IS_WIN)
  39. #endif // defined(ARCH_CPU_32_BITS)
  40. return mask;
  41. }
  42. const size_t kSamples = 100;
  43. uintptr_t GetAddressBits() {
  44. return GetRandomPageBase();
  45. }
  46. uintptr_t GetRandomBits() {
  47. return GetAddressBits() - internal::ASLROffset();
  48. }
  49. } // namespace
  50. // Configurations without ASLR are tested here.
  51. TEST(PartitionAllocAddressSpaceRandomizationTest, DisabledASLR) {
  52. uintptr_t mask = GetMask();
  53. if (!mask) {
  54. #if BUILDFLAG(IS_WIN) && defined(ARCH_CPU_32_BITS)
  55. // ASLR should be turned off on 32-bit Windows.
  56. EXPECT_EQ(0u, GetRandomPageBase());
  57. #else
  58. // Otherwise, 0 is very unexpected.
  59. EXPECT_NE(0u, GetRandomPageBase());
  60. #endif
  61. }
  62. }
  63. TEST(PartitionAllocAddressSpaceRandomizationTest, Alignment) {
  64. uintptr_t mask = GetMask();
  65. if (!mask)
  66. return;
  67. for (size_t i = 0; i < kSamples; ++i) {
  68. uintptr_t address = GetAddressBits();
  69. EXPECT_EQ(0ULL,
  70. (address & internal::PageAllocationGranularityOffsetMask()));
  71. }
  72. }
  73. TEST(PartitionAllocAddressSpaceRandomizationTest, Range) {
  74. uintptr_t mask = GetMask();
  75. if (!mask)
  76. return;
  77. uintptr_t min = internal::ASLROffset();
  78. uintptr_t max = internal::ASLROffset() + internal::ASLRMask();
  79. for (size_t i = 0; i < kSamples; ++i) {
  80. uintptr_t address = GetAddressBits();
  81. EXPECT_LE(min, address);
  82. EXPECT_GE(max + mask, address);
  83. }
  84. }
  85. TEST(PartitionAllocAddressSpaceRandomizationTest, Predictable) {
  86. uintptr_t mask = GetMask();
  87. if (!mask)
  88. return;
  89. const uint64_t kInitialSeed = 0xfeed5eedULL;
  90. SetMmapSeedForTesting(kInitialSeed);
  91. std::vector<uintptr_t> sequence;
  92. for (size_t i = 0; i < kSamples; ++i) {
  93. sequence.push_back(GetRandomPageBase());
  94. }
  95. SetMmapSeedForTesting(kInitialSeed);
  96. for (size_t i = 0; i < kSamples; ++i) {
  97. EXPECT_EQ(GetRandomPageBase(), sequence[i]);
  98. }
  99. }
  100. // This randomness test is adapted from V8's PRNG tests.
  101. // Chi squared for getting m 0s out of n bits.
  102. double ChiSquared(int m, int n) {
  103. double ys_minus_np1 = (m - n / 2.0);
  104. double chi_squared_1 = ys_minus_np1 * ys_minus_np1 * 2.0 / n;
  105. double ys_minus_np2 = ((n - m) - n / 2.0);
  106. double chi_squared_2 = ys_minus_np2 * ys_minus_np2 * 2.0 / n;
  107. return chi_squared_1 + chi_squared_2;
  108. }
  109. // Test for correlations between recent bits from the PRNG, or bits that are
  110. // biased.
  111. void RandomBitCorrelation(int random_bit) {
  112. uintptr_t mask = GetMask();
  113. if ((mask & (1ULL << random_bit)) == 0)
  114. return; // bit is always 0.
  115. #if BUILDFLAG(PA_DCHECK_IS_ON)
  116. // Do fewer checks when BUILDFLAG(PA_DCHECK_IS_ON). Exercized code only
  117. // changes when the random number generator does, which should be almost
  118. // never. However it's expensive to run all the tests. So keep iterations
  119. // faster for local development builds, while having the stricter version run
  120. // on official build testers.
  121. constexpr int kHistory = 2;
  122. constexpr int kRepeats = 1000;
  123. #else
  124. constexpr int kHistory = 8;
  125. constexpr int kRepeats = 10000;
  126. #endif
  127. constexpr int kPointerBits = 8 * sizeof(void*);
  128. uintptr_t history[kHistory];
  129. // The predictor bit is either constant 0 or 1, or one of the bits from the
  130. // history.
  131. for (int predictor_bit = -2; predictor_bit < kPointerBits; predictor_bit++) {
  132. // The predicted bit is one of the bits from the PRNG.
  133. for (int ago = 0; ago < kHistory; ago++) {
  134. // We don't want to check whether each bit predicts itself.
  135. if (ago == 0 && predictor_bit == random_bit)
  136. continue;
  137. // Enter the new random value into the history.
  138. for (int i = ago; i >= 0; i--) {
  139. history[i] = GetRandomBits();
  140. }
  141. // Find out how many of the bits are the same as the prediction bit.
  142. int m = 0;
  143. for (int i = 0; i < kRepeats; i++) {
  144. uintptr_t random = GetRandomBits();
  145. for (int j = ago - 1; j >= 0; j--)
  146. history[j + 1] = history[j];
  147. history[0] = random;
  148. int predicted;
  149. if (predictor_bit >= 0) {
  150. predicted = (history[ago] >> predictor_bit) & 1;
  151. } else {
  152. predicted = predictor_bit == -2 ? 0 : 1;
  153. }
  154. int bit = (random >> random_bit) & 1;
  155. if (bit == predicted)
  156. m++;
  157. }
  158. // Chi squared analysis for k = 2 (2, states: same/not-same) and one
  159. // degree of freedom (k - 1).
  160. double chi_squared = ChiSquared(m, kRepeats);
  161. // For k=2 probability of Chi^2 < 35 is p=3.338e-9. This condition is
  162. // tested ~19000 times, so probability of it failing randomly per one
  163. // base_unittests run is (1 - (1 - p) ^ 19000) ~= 6e-5.
  164. PA_CHECK(chi_squared <= 35.0);
  165. // If the predictor bit is a fixed 0 or 1 then it makes no sense to
  166. // repeat the test with a different age.
  167. if (predictor_bit < 0)
  168. break;
  169. }
  170. }
  171. }
  172. // Tests are fairly slow, so give each random bit its own test.
  173. #define TEST_RANDOM_BIT(BIT) \
  174. TEST(PartitionAllocAddressSpaceRandomizationTest, \
  175. RandomBitCorrelations##BIT) { \
  176. RandomBitCorrelation(BIT); \
  177. }
  178. // The first 12 bits on all platforms are always 0.
  179. TEST_RANDOM_BIT(12)
  180. TEST_RANDOM_BIT(13)
  181. TEST_RANDOM_BIT(14)
  182. TEST_RANDOM_BIT(15)
  183. TEST_RANDOM_BIT(16)
  184. TEST_RANDOM_BIT(17)
  185. TEST_RANDOM_BIT(18)
  186. TEST_RANDOM_BIT(19)
  187. TEST_RANDOM_BIT(20)
  188. TEST_RANDOM_BIT(21)
  189. TEST_RANDOM_BIT(22)
  190. TEST_RANDOM_BIT(23)
  191. TEST_RANDOM_BIT(24)
  192. TEST_RANDOM_BIT(25)
  193. TEST_RANDOM_BIT(26)
  194. TEST_RANDOM_BIT(27)
  195. TEST_RANDOM_BIT(28)
  196. TEST_RANDOM_BIT(29)
  197. TEST_RANDOM_BIT(30)
  198. TEST_RANDOM_BIT(31)
  199. #if defined(ARCH_CPU_64_BITS)
  200. TEST_RANDOM_BIT(32)
  201. TEST_RANDOM_BIT(33)
  202. TEST_RANDOM_BIT(34)
  203. TEST_RANDOM_BIT(35)
  204. TEST_RANDOM_BIT(36)
  205. TEST_RANDOM_BIT(37)
  206. TEST_RANDOM_BIT(38)
  207. TEST_RANDOM_BIT(39)
  208. TEST_RANDOM_BIT(40)
  209. TEST_RANDOM_BIT(41)
  210. TEST_RANDOM_BIT(42)
  211. TEST_RANDOM_BIT(43)
  212. TEST_RANDOM_BIT(44)
  213. TEST_RANDOM_BIT(45)
  214. TEST_RANDOM_BIT(46)
  215. TEST_RANDOM_BIT(47)
  216. TEST_RANDOM_BIT(48)
  217. // No platforms have more than 48 address bits.
  218. #endif // defined(ARCH_CPU_64_BITS)
  219. #undef TEST_RANDOM_BIT
  220. // Checks that we can actually map memory in the requested range.
  221. // TODO(crbug.com/1318466): Extend to all operating systems once they are fixed.
  222. #if BUILDFLAG(IS_MAC)
  223. TEST(PartitionAllocAddressSpaceRandomizationTest, CanMapInAslrRange) {
  224. int tries = 0;
  225. // This is overly generous, but we really don't want to make the test flaky.
  226. constexpr int kMaxTries = 1000;
  227. for (tries = 0; tries < kMaxTries; tries++) {
  228. uintptr_t requested_address = GetRandomPageBase();
  229. size_t size = internal::PageAllocationGranularity();
  230. uintptr_t address = AllocPages(
  231. requested_address, size, internal::PageAllocationGranularity(),
  232. PageAccessibilityConfiguration::kReadWrite, PageTag::kPartitionAlloc);
  233. ASSERT_NE(address, 0u);
  234. FreePages(address, size);
  235. if (address == requested_address)
  236. break;
  237. }
  238. EXPECT_LT(tries, kMaxTries);
  239. }
  240. #endif // BUILDFLAG(IS_MAC)
  241. } // namespace partition_alloc