TCMalloc: support userland ASLR on Linux

base/security_unittest.cc

 // Copyright (c) 2013 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 <fcntl.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 
 #include <algorithm>
 #include <limits>
 
+#include "base/file_util.h"
 #include "base/logging.h"
 #include "base/memory/scoped_ptr.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 using std::nothrow;
 using std::numeric_limits;
 
 namespace {
 
 // Check that we can not allocate a memory range that cannot be indexed
@@ skipping 72 matching lines @@
   }
 }
 
 TEST(SecurityTest, ALLOC_TEST(MemoryAllocationRestrictionsNewArray)) {
   if (!IsTcMallocBypassed()) {
     scoped_ptr<char[]> ptr(new (nothrow) char[kTooBigAllocSize]);
     ASSERT_TRUE(ptr == NULL);
   }
 }
 
 // The tests bellow check for overflows in new[] and calloc().

[jln (very slow on Chromium), 2013/01/30 20:13:05]

Note: don't worry about this stuff disappearing in this revision, it's just due
to a git rebase and how our review tool works.

 
 #if defined(OS_IOS) || defined(OS_WIN)
   #define DISABLE_ON_IOS_AND_WIN(function) DISABLED_##function
 #else
   #define DISABLE_ON_IOS_AND_WIN(function) function
 #endif
 
 #if defined(ADDRESS_SANITIZER)
   #define DISABLE_ON_ASAN(function) DISABLED_##function
 #else
@@ skipping 70 matching lines @@
   {
     scoped_ptr<char> array_pointer(
         static_cast<char*>(calloc(kArraySize2, kArraySize)));
     // We need the call to HideValueFromCompiler(): we have seen LLVM
     // optimize away the call to calloc() entirely and assume
     // the pointer to not be NULL.
     EXPECT_TRUE(HideValueFromCompiler(array_pointer.get()) == NULL);
   }
 }
 
+#if (defined(OS_LINUX) || defined(OS_CHROMEOS)) && defined(__x86_64__)
+// Useful for debugging.
+void PrintProcSelfMaps() {
+  int fd = open("/proc/self/maps", O_RDONLY);
+  file_util::ScopedFD fd_closer(&fd);
+  ASSERT_GE(fd, 0);
+  char buffer[1<<13];
+  int ret;
+  ret = read(fd, buffer, sizeof(buffer) - 1);
+  ASSERT_GT(ret, 0);
+  buffer[ret - 1] = 0;
+  fprintf(stdout, "%s\n", buffer);
+}
+
+// Check if TCMalloc uses an underlying random memory allocator.
+TEST(SecurityTest, ALLOC_TEST(RandomMemoryAllocations)) {
+  if (IsTcMallocBypassed())
+    return;
+  // Two successive calls to mmap() have roughly one chance out of 2^6 to be
+  // detected as having the same order. With 32 allocations, we see ~16 that

[jar (doing other things), 2013/01/30 17:20:48]

I didn't understand the argument.

Down below, you define "order" to mean "same high order bits."  If that is what
you meant here, you should spell that out, otherwise "order" tends to mean
"sequentially related."

Down below, high order is the top 8 bits, so I'd expect a pair to have the same
"order" with probability 1 in 256, or as you might say, 1 in 2^8.

Where does the power of 6 come from?

[jln (very slow on Chromium), 2013/01/30 20:11:33]

6 comes from the smallest mask that we use in the implementation (0x3f...);

I've edited the comment.

+  // trigger a call to mmap, so the chances of this test flaking is roughly

[jar (doing other things), 2013/01/30 17:20:48]

I'm not sure why these calls would trigger mmap calls.  I suspect this test is
being run after tons of other tests and activities, and hence tons of
allocations and frees have been done in random order.  As a result, this would
appear to be querying the existing cache of allocations, so too if available
allocations have different high-order bytes.

Why do you think this will cause mmap to be called?

[jln (very slow on Chromium), 2013/01/30 20:11:33]

I did check the number of mmaps by adding some instrumentation.

I thought we were re-executing at every test (i.e. the threadsafe option of
gtest, which also looks more similar than Windows).

But your argument is valid, it's not reliable / defined behavior. I've changed
the comment to mention different buckets.

+  // 2^-(6*15), i.e. virtually impossible.
+  const int kAllocNumber = 32;
+  bool is_contiguous = true;
+  // Make kAllocNumber successive allocations of growing size and compare the
+  // successive pointers to detect adjacent mappings. We grow the size because
+  // TCMalloc can sometimes over-allocate.
+  scoped_ptr<char, base::FreeDeleter> ptr[kAllocNumber];
+  for (int i = 0; i < kAllocNumber; ++i) {
+    // Grow the Malloc size slightly sub-exponentially.
+    const size_t kMallocSize = 1 << (12 + (i>>1));
+    ptr[i].reset(static_cast<char*>(malloc(kMallocSize)));
+    ASSERT_TRUE(ptr[i] != NULL);
+    if (i > 0) {
+      // Without mmap randomization, the two high order nibbles
+      // of a 47 bits userland address address will be identical.
+      const uintptr_t kHighOrderMask = 0xff0000000000ULL;
+      bool pointer_have_same_high_order =
+          (reinterpret_cast<size_t>(ptr[i].get()) & kHighOrderMask) ==
+          (reinterpret_cast<size_t>(ptr[i - 1].get()) & kHighOrderMask);
+      if (!pointer_have_same_high_order) {
+        // PrintProcSelfMaps();
+        is_contiguous = false;

[jar (doing other things), 2013/01/30 17:20:48]

This test will break out of this loop (causing the test to pass) as soon as two
allocations have different high-order bits.  

Given the sparsity of random allocations, I would have expected something much
stricter would still be true.  With 32 allocations randomly out of a 256 bucket
(8 bit) mask, I'd be a tad surprised (for example) if more than 2 allocations
were from one bucket.   I wouldn't be as surprised if two allocations were from
different buckets.

Nicer might be to strengthen this test, to tally how many allocations came out
of any one bucket, and perchance fail if more than k (8 out of 32? 16 out of
32?) were in a single bucket.  The current test fails if *all* 32 out of 32 were
in a single bucket. 

I guess you're getting a nice low failure rate... but you currently don't
(probably) test to see if the PRNG has more than about two significantly
different outputs. 

[jln (very slow on Chromium), 2013/01/30 20:11:33]

You make good points, but I am quite happy with where we are in the
false-positives / false-negeatives trade-offs.

As-is:

- The test will never flake
- The chances of false positive are still very, very low:

We are looking at the the high 6 bits of a 46 bits address (we force bit 47 to
0). For a kernel allocator (brk() or mmap()) to cross such a zone is very
unlikely as this represents a 1TB zone. Moreover, what we worry about is
"sustained false positives".

The chances of someone breaking ASLR and landing a CL that will with very bad
luck pass on all Linux bots, repeatedly are tiny.

In a nutshell, I think what we want is to have almost no chances of flake and
small chances of false positives, and I think that's where we are.

+        break;

[jar (doing other things), 2013/01/30 17:35:29]

nit: if you keep this test as is, it is much more readable to replace the
"break;" with:

return;  // Test passes.

and not bother with the is_contiguous variable.

Line 246 would then be a failure point.

[jln (very slow on Chromium), 2013/01/30 20:11:33]

Done.

+      }
+    }
+  }
+  ASSERT_FALSE(is_contiguous);
+}
+
+#endif  // (defined(OS_LINUX) || defined(OS_CHROMEOS)) && defined(__x86_64__)
+
 }  // namespace