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