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