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
5#include "base/allocator/partition_allocator/address_space_randomization.h"
6
7#include <vector>
8
9#include "base/allocator/partition_allocator/page_allocator.h"
10#include "base/logging.h"
11#include "build/build_config.h"
12#include "testing/gtest/include/gtest/gtest.h"
13
14#if defined(OS_WIN)
15#include <windows.h>
16#include "base/win/windows_version.h"
17// VersionHelpers.h must be included after windows.h.
18#include <VersionHelpers.h>
19#endif
20
21namespace base {
22
23namespace {
24
25uintptr_t GetMask() {
26 uintptr_t mask = internal::kASLRMask;
27#if defined(ARCH_CPU_64_BITS)
28// Sanitizers use their own kASLRMask constant.
29#if defined(OS_WIN) && !defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
30 if (!IsWindows8Point1OrGreater()) {
31 mask = internal::kASLRMaskBefore8_10;
32 }
33#endif // defined(OS_WIN) && !defined(MEMORY_TOOL_REPLACES_ALLOCATOR))
34#elif defined(ARCH_CPU_32_BITS)
35#if defined(OS_WIN)
36 BOOL is_wow64 = FALSE;
37 if (!IsWow64Process(GetCurrentProcess(), &is_wow64))
38 is_wow64 = FALSE;
39 if (!is_wow64) {
40 mask = 0;
41 }
42#endif // defined(OS_WIN)
43#endif // defined(ARCH_CPU_32_BITS)
44 return mask;
45}
46
47const size_t kSamples = 100;
48
49uintptr_t GetAddressBits() {
50 return reinterpret_cast<uintptr_t>(base::GetRandomPageBase());
51}
52
53uintptr_t GetRandomBits() {
54 return GetAddressBits() - internal::kASLROffset;
55}
56
57} // namespace
58
59// Configurations without ASLR are tested here.
60TEST(AddressSpaceRandomizationTest, DisabledASLR) {
61 uintptr_t mask = GetMask();
62 if (!mask) {
63#if defined(OS_WIN) && defined(ARCH_CPU_32_BITS)
64 // ASLR should be turned off on 32-bit Windows.
65 EXPECT_EQ(nullptr, base::GetRandomPageBase());
66#else
67 // Otherwise, nullptr is very unexpected.
68 EXPECT_NE(nullptr, base::GetRandomPageBase());
69#endif
70 }
71}
72
73TEST(AddressSpaceRandomizationTest, Alignment) {
74 uintptr_t mask = GetMask();
75 if (!mask)
76 return;
77
78 for (size_t i = 0; i < kSamples; ++i) {
79 uintptr_t address = GetAddressBits();
80 EXPECT_EQ(0ULL, (address & kPageAllocationGranularityOffsetMask));
81 }
82}
83
84TEST(AddressSpaceRandomizationTest, Range) {
85 uintptr_t mask = GetMask();
86 if (!mask)
87 return;
88
89 uintptr_t min = internal::kASLROffset;
90 uintptr_t max = internal::kASLROffset + internal::kASLRMask;
91 for (size_t i = 0; i < kSamples; ++i) {
92 uintptr_t address = GetAddressBits();
93 EXPECT_LE(min, address);
94 EXPECT_GE(max + mask, address);
95 }
96}
97
98TEST(AddressSpaceRandomizationTest, Predictable) {
99 uintptr_t mask = GetMask();
100 if (!mask)
101 return;
102
103 const uintptr_t kInitialSeed = 0xfeed5eedULL;
104 base::SetRandomPageBaseSeed(kInitialSeed);
105
106 std::vector<uintptr_t> sequence;
107 for (size_t i = 0; i < kSamples; ++i) {
108 uintptr_t address = reinterpret_cast<uintptr_t>(base::GetRandomPageBase());
109 sequence.push_back(address);
110 }
111
112 base::SetRandomPageBaseSeed(kInitialSeed);
113
114 for (size_t i = 0; i < kSamples; ++i) {
115 uintptr_t address = reinterpret_cast<uintptr_t>(base::GetRandomPageBase());
116 EXPECT_EQ(address, sequence[i]);
117 }
118}
119
120// This randomness test is adapted from V8's PRNG tests.
121
122// Chi squared for getting m 0s out of n bits.
123double ChiSquared(int m, int n) {
124 double ys_minus_np1 = (m - n / 2.0);
125 double chi_squared_1 = ys_minus_np1 * ys_minus_np1 * 2.0 / n;
126 double ys_minus_np2 = ((n - m) - n / 2.0);
127 double chi_squared_2 = ys_minus_np2 * ys_minus_np2 * 2.0 / n;
128 return chi_squared_1 + chi_squared_2;
129}
130
131// Test for correlations between recent bits from the PRNG, or bits that are
132// biased.
133void RandomBitCorrelation(int random_bit) {
134 uintptr_t mask = GetMask();
135 if ((mask & (1ULL << random_bit)) == 0)
136 return; // bit is always 0.
137
138#ifdef DEBUG
139 constexpr int kHistory = 2;
140 constexpr int kRepeats = 1000;
141#else
142 constexpr int kHistory = 8;
143 constexpr int kRepeats = 10000;
144#endif
145 constexpr int kPointerBits = 8 * sizeof(void*);
146 uintptr_t history[kHistory];
147 // The predictor bit is either constant 0 or 1, or one of the bits from the
148 // history.
149 for (int predictor_bit = -2; predictor_bit < kPointerBits; predictor_bit++) {
150 // The predicted bit is one of the bits from the PRNG.
151 for (int ago = 0; ago < kHistory; ago++) {
152 // We don't want to check whether each bit predicts itself.
153 if (ago == 0 && predictor_bit == random_bit)
154 continue;
155
156 // Enter the new random value into the history.
157 for (int i = ago; i >= 0; i--) {
158 history[i] = GetRandomBits();
159 }
160
161 // Find out how many of the bits are the same as the prediction bit.
162 int m = 0;
163 for (int i = 0; i < kRepeats; i++) {
164 uintptr_t random = GetRandomBits();
165 for (int j = ago - 1; j >= 0; j--)
166 history[j + 1] = history[j];
167 history[0] = random;
168
169 int predicted;
170 if (predictor_bit >= 0) {
171 predicted = (history[ago] >> predictor_bit) & 1;
172 } else {
173 predicted = predictor_bit == -2 ? 0 : 1;
174 }
175 int bit = (random >> random_bit) & 1;
176 if (bit == predicted)
177 m++;
178 }
179
180 // Chi squared analysis for k = 2 (2, states: same/not-same) and one
181 // degree of freedom (k - 1).
182 double chi_squared = ChiSquared(m, kRepeats);
183 // For 1 degree of freedom this corresponds to 1 in a million. We are
184 // running ~8000 tests, so that would be surprising.
185 CHECK_GE(24, chi_squared);
186 // If the predictor bit is a fixed 0 or 1 then it makes no sense to
187 // repeat the test with a different age.
188 if (predictor_bit < 0)
189 break;
190 }
191 }
192}
193
194// TODO(crbug.com/811881): These are flaky on Fuchsia
195#if !defined(OS_FUCHSIA)
196
197// Tests are fairly slow, so give each random bit its own test.
198#define TEST_RANDOM_BIT(BIT) \
199 TEST(AddressSpaceRandomizationTest, RandomBitCorrelations##BIT) { \
200 RandomBitCorrelation(BIT); \
201 }
202
203// The first 12 bits on all platforms are always 0.
204TEST_RANDOM_BIT(12)
205TEST_RANDOM_BIT(13)
206TEST_RANDOM_BIT(14)
207TEST_RANDOM_BIT(15)
208TEST_RANDOM_BIT(16)
209TEST_RANDOM_BIT(17)
210TEST_RANDOM_BIT(18)
211TEST_RANDOM_BIT(19)
212TEST_RANDOM_BIT(20)
213TEST_RANDOM_BIT(21)
214TEST_RANDOM_BIT(22)
215TEST_RANDOM_BIT(23)
216TEST_RANDOM_BIT(24)
217TEST_RANDOM_BIT(25)
218TEST_RANDOM_BIT(26)
219TEST_RANDOM_BIT(27)
220TEST_RANDOM_BIT(28)
221TEST_RANDOM_BIT(29)
222TEST_RANDOM_BIT(30)
223TEST_RANDOM_BIT(31)
224#if defined(ARCH_CPU_64_BITS)
225TEST_RANDOM_BIT(32)
226TEST_RANDOM_BIT(33)
227TEST_RANDOM_BIT(34)
228TEST_RANDOM_BIT(35)
229TEST_RANDOM_BIT(36)
230TEST_RANDOM_BIT(37)
231TEST_RANDOM_BIT(38)
232TEST_RANDOM_BIT(39)
233TEST_RANDOM_BIT(40)
234TEST_RANDOM_BIT(41)
235TEST_RANDOM_BIT(42)
236TEST_RANDOM_BIT(43)
237TEST_RANDOM_BIT(44)
238TEST_RANDOM_BIT(45)
239TEST_RANDOM_BIT(46)
240TEST_RANDOM_BIT(47)
241TEST_RANDOM_BIT(48)
242// No platforms have more than 48 address bits.
243#endif // defined(ARCH_CPU_64_BITS)
244
245#endif // defined(OS_FUCHSIA)
246
247#undef TEST_RANDOM_BIT
248
249} // namespace base
250