[sanitizer] Initial implementation of a Hardened Allocator

Summary:
This is an initial implementation of a Hardened Allocator based on Sanitizer Common's CombinedAllocator.
It aims at mitigating heap based vulnerabilities by adding several features to the base allocator, while staying relatively fast.
The following were implemented:
- additional consistency checks on the allocation function parameters and on the heap chunks;
- use of checksum protected chunk header, to detect corruption;
- randomness to the allocator base;
- delayed freelist (quarantine), to mitigate use after free and overall determinism.
Additional mitigations are in the works.

Reviewers: eugenis, aizatsky, pcc, krasin, vitalybuka, glider, dvyukov, kcc

Subscribers: kubabrecka, filcab, llvm-commits

Differential Revision: http://reviews.llvm.org/D20084

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@271968 91177308-0d34-0410-b5e6-96231b3b80d8

15 files changed, 550 insertions, 0 deletions

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index e85e0867c..03d4571e0 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -73,6 +73,9 @@ if(COMPILER_RT_CAN_EXECUTE_TESTS)
   if(COMPILER_RT_HAS_ESAN)
     add_subdirectory(esan)
   endif()
+  if(COMPILER_RT_HAS_SCUDO)
+    add_subdirectory(scudo)
+  endif()
 endif()
 
 if(COMPILER_RT_STANDALONE_BUILD)
diff --git a/test/scudo/CMakeLists.txt b/test/scudo/CMakeLists.txt
new file mode 100644
index 000000000..8eae22f3f
--- /dev/null
+++ b/test/scudo/CMakeLists.txt
@@ -0,0 +1,28 @@
+set(SCUDO_LIT_SOURCE_DIR ${CMAKE_CURRENT_SOURCE_DIR})
+set(SCUDO_LIT_BINARY_DIR ${CMAKE_CURRENT_BINARY_DIR})
+
+
+set(SCUDO_TEST_DEPS ${SANITIZER_COMMON_LIT_TEST_DEPS})
+if(NOT COMPILER_RT_STANDALONE_BUILD)
+  list(APPEND SCUDO_TEST_DEPS scudo)
+endif()
+
+configure_lit_site_cfg(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.in
+  ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg
+  )
+
+if(CMAKE_SYSTEM_NAME MATCHES "Linux")
+   EXEC_PROGRAM(cat ARGS "/proc/cpuinfo" OUTPUT_VARIABLE CPUINFO)
+   STRING(REGEX REPLACE "^.*(sse4_2).*$" "\\1" SSE_THERE ${CPUINFO})
+   STRING(COMPARE EQUAL "sse4_2" "${SSE_THERE}" SSE42_TRUE)
+endif(CMAKE_SYSTEM_NAME MATCHES "Linux")
+
+if (SSE42_TRUE AND CMAKE_SIZEOF_VOID_P EQUAL 8)
+  add_lit_testsuite(check-scudo
+    "Running the Scudo Hardened Allocator tests"
+    ${CMAKE_CURRENT_BINARY_DIR}
+    DEPENDS ${SCUDO_TEST_DEPS})
+  set_target_properties(check-scudo PROPERTIES FOLDER
+    "Scudo Hardened Allocator tests")
+endif(SSE42_TRUE AND CMAKE_SIZEOF_VOID_P EQUAL 8)
diff --git a/test/scudo/alignment.cpp b/test/scudo/alignment.cpp
new file mode 100644
index 000000000..c5e57d179
--- /dev/null
+++ b/test/scudo/alignment.cpp
@@ -0,0 +1,25 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: not %run %t pointers 2>&1 | FileCheck %s
+
+// Tests that a non-16-byte aligned pointer will trigger the associated error
+// on deallocation.
+
+#include <assert.h>
+#include <malloc.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  assert(argc == 2);
+  if (!strcmp(argv[1], "pointers")) {
+    void *p = malloc(1U << 16);
+    if (!p)
+      return 1;
+    free(reinterpret_cast<void *>(reinterpret_cast<uintptr_t>(p) | 8));
+  }
+  return 0;
+}
+
+// CHECK: ERROR: attempted to deallocate a chunk not properly aligned
diff --git a/test/scudo/double-free.cpp b/test/scudo/double-free.cpp
new file mode 100644
index 000000000..4f5bf0cb8
--- /dev/null
+++ b/test/scudo/double-free.cpp
@@ -0,0 +1,49 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: not %run %t malloc   2>&1 | FileCheck %s
+// RUN: not %run %t new      2>&1 | FileCheck %s
+// RUN: not %run %t newarray 2>&1 | FileCheck %s
+// RUN: not %run %t memalign 2>&1 | FileCheck %s
+
+// Tests double-free error on pointers allocated with different allocation
+// functions.
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  assert(argc == 2);
+  if (!strcmp(argv[1], "malloc")) {
+    void *p = malloc(sizeof(int));
+    if (!p)
+      return 1;
+    free(p);
+    free(p);
+  }
+  if (!strcmp(argv[1], "new")) {
+    int *p = new int;
+    if (!p)
+      return 1;
+    delete p;
+    delete p;
+  }
+  if (!strcmp(argv[1], "newarray")) {
+    int *p = new int[8];
+    if (!p)
+      return 1;
+    delete[] p;
+    delete[] p;
+  }
+  if (!strcmp(argv[1], "memalign")) {
+    void *p = nullptr;
+    posix_memalign(&p, 0x100, sizeof(int));
+    if (!p)
+      return 1;
+    free(p);
+    free(p);
+  }
+  return 0;
+}
+
+// CHECK: ERROR: invalid chunk state when deallocating address
diff --git a/test/scudo/lit.cfg b/test/scudo/lit.cfg
new file mode 100644
index 000000000..e2a4997dd
--- /dev/null
+++ b/test/scudo/lit.cfg
@@ -0,0 +1,39 @@
+# -*- Python -*-
+
+import os
+
+# Setup config name.
+config.name = 'Scudo'
+
+# Setup source root.
+config.test_source_root = os.path.dirname(__file__)
+
+# Path to the static library
+base_lib = os.path.join(config.compiler_rt_libdir,
+                        "libclang_rt.scudo-%s.a" % config.target_arch)
+whole_archive = "-Wl,-whole-archive %s -Wl,-no-whole-archive " % base_lib
+
+# Test suffixes.
+config.suffixes = ['.c', '.cc', '.cpp', '.m', '.mm', '.ll', '.test']
+
+# C flags.
+c_flags = ["-std=c++11",
+           "-lstdc++",
+           "-ldl",
+           "-lrt",
+           "-pthread",
+           "-latomic",
+           "-fPIE",
+           "-pie",
+           "-O0"]
+
+def build_invocation(compile_flags):                                            
+  return " " + " ".join([config.clang] + compile_flags) + " "                   
+
+# Add clang substitutions.
+config.substitutions.append( ("%clang_scudo ",
+                              build_invocation(c_flags) + whole_archive) )
+
+# Hardened Allocator tests are currently supported on Linux only.
+if config.host_os not in ['Linux']:
+   config.unsupported = True
diff --git a/test/scudo/lit.site.cfg.in b/test/scudo/lit.site.cfg.in
new file mode 100644
index 000000000..64e2fb39e
--- /dev/null
+++ b/test/scudo/lit.site.cfg.in
@@ -0,0 +1,7 @@
+@LIT_SITE_CFG_IN_HEADER@
+
+# Load common config for all compiler-rt lit tests.
+lit_config.load_config(config, "@COMPILER_RT_BINARY_DIR@/test/lit.common.configured")
+
+# Load tool-specific config that would do the real work.
+lit_config.load_config(config, "@SCUDO_LIT_SOURCE_DIR@/lit.cfg")
diff --git a/test/scudo/malloc.cpp b/test/scudo/malloc.cpp
new file mode 100644
index 000000000..4507a5225
--- /dev/null
+++ b/test/scudo/malloc.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: %run %t 2>&1
+
+// Tests that a regular workflow of allocation, memory fill and free works as
+// intended. Also tests that a zero-sized allocation succeeds.
+
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  void *p;
+  size_t size = 1U << 8;
+
+  p = malloc(size);
+  if (!p)
+    return 1;
+  memset(p, 'A', size);
+  free(p);
+  p = malloc(0);
+  if (!p)
+    return 1;
+  free(p);
+
+  return 0;
+}
diff --git a/test/scudo/memalign.cpp b/test/scudo/memalign.cpp
new file mode 100644
index 000000000..01526ca3d
--- /dev/null
+++ b/test/scudo/memalign.cpp
@@ -0,0 +1,42 @@
+// RUN: %clang_scudo %s -o %t
+// RUN:     %run %t valid   2>&1
+// RUN: not %run %t invalid 2>&1 | FileCheck %s
+
+// Tests that the various aligned allocation functions work as intended. Also
+// tests for the condition where the alignment is not a power of 2.
+
+#include <assert.h>
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  void *p;
+  size_t alignment = 1U << 12;
+  size_t size = alignment;
+
+  assert(argc == 2);
+  if (!strcmp(argv[1], "valid")) {
+    p = memalign(alignment, size);
+    if (!p)
+      return 1;
+    free(p);
+    p = nullptr;
+    posix_memalign(&p, alignment, size);
+    if (!p)
+      return 1;
+    free(p);
+    p = aligned_alloc(alignment, size);
+    if (!p)
+      return 1;
+    free(p);
+  }
+  if (!strcmp(argv[1], "invalid")) {
+    p = memalign(alignment - 1, size);
+    free(p);
+  }
+  return 0;
+}
+
+// CHECK: ERROR: malloc alignment is not a power of 2
diff --git a/test/scudo/mismatch.cpp b/test/scudo/mismatch.cpp
new file mode 100644
index 000000000..2d3d198af
--- /dev/null
+++ b/test/scudo/mismatch.cpp
@@ -0,0 +1,41 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: SCUDO_OPTIONS=DeallocationTypeMismatch=1 not %run %t mallocdel   2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=DeallocationTypeMismatch=0     %run %t mallocdel   2>&1
+// RUN: SCUDO_OPTIONS=DeallocationTypeMismatch=1 not %run %t newfree     2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=DeallocationTypeMismatch=0     %run %t newfree     2>&1
+// RUN: SCUDO_OPTIONS=DeallocationTypeMismatch=1 not %run %t memaligndel 2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=DeallocationTypeMismatch=0     %run %t memaligndel 2>&1
+
+// Tests that type mismatches between allocation and deallocation functions are
+// caught when the related option is set.
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include <malloc.h>
+
+int main(int argc, char **argv)
+{
+  assert(argc == 2);
+  if (!strcmp(argv[1], "mallocdel")) {
+    int *p = (int *)malloc(16);
+    if (!p)
+      return 1;
+    delete p;
+  }
+  if (!strcmp(argv[1], "newfree")) {
+    int *p = new int;
+    if (!p)
+      return 1;
+    free((void *)p);
+  }
+  if (!strcmp(argv[1], "memaligndel")) {
+    int *p = (int *)memalign(0x10, 0x10);
+    if (!p)
+      return 1;
+    delete p;
+  }
+  return 0;
+}
+
+// CHECK: ERROR: allocation type mismatch on address
diff --git a/test/scudo/overflow.cpp b/test/scudo/overflow.cpp
new file mode 100644
index 000000000..5b2cb7560
--- /dev/null
+++ b/test/scudo/overflow.cpp
@@ -0,0 +1,38 @@
+// RUN: %clang_scudo %s -o %t
+// RUN:                                  not %run %t malloc     2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=QuarantineSizeMb=1 not %run %t quarantine 2>&1 | FileCheck %s
+
+// Tests that header corruption of an allocated or quarantined chunk is caught.
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  assert(argc == 2);
+  if (!strcmp(argv[1], "malloc")) {
+    // Simulate a header corruption of an allocated chunk (1-bit)
+    void *p = malloc(1U << 4);
+    if (!p)
+      return 1;
+    ((char *)p)[-1] ^= 1;
+    free(p);
+  }
+  if (!strcmp(argv[1], "quarantine")) {
+    void *p = malloc(1U << 4);
+    if (!p)
+      return 1;
+    free(p);
+    // Simulate a header corruption of a quarantined chunk
+    ((char *)p)[-2] ^= 1;
+    // Trigger the quarantine recycle
+    for (int i = 0; i < 0x100; i++) {
+      p = malloc(1U << 16);
+      free(p);
+    }
+  }
+  return 0;
+}
+
+// CHECK: ERROR: corrupted chunk header at address
diff --git a/test/scudo/preinit.cpp b/test/scudo/preinit.cpp
new file mode 100644
index 000000000..a280ae1d4
--- /dev/null
+++ b/test/scudo/preinit.cpp
@@ -0,0 +1,38 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: %run %t 2>&1
+
+// Verifies that calling malloc in a preinit_array function succeeds, and that
+// the resulting pointer can be freed at program termination.
+
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+static void *global_p = nullptr;
+
+void __init(void) {
+  global_p = malloc(1);
+  if (!global_p)
+    exit(1);
+}
+
+void __fini(void) {
+  if (global_p)
+    free(global_p);
+}
+
+int main(int argc, char **argv)
+{
+  void *p = malloc(1);
+  if (!p)
+    return 1;
+  free(p);
+
+  return 0;
+}
+
+__attribute__((section(".preinit_array"), used))
+  void (*__local_preinit)(void) = __init;
+__attribute__((section(".fini_array"), used))
+  void (*__local_fini)(void) = __fini;
+
diff --git a/test/scudo/quarantine.cpp b/test/scudo/quarantine.cpp
new file mode 100644
index 000000000..4ce0197ac
--- /dev/null
+++ b/test/scudo/quarantine.cpp
@@ -0,0 +1,43 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: SCUDO_OPTIONS=QuarantineSizeMb=1 %run %t 2>&1
+
+// Tests that the quarantine prevents a chunk from being reused right away.
+// Also tests that a chunk will eventually become available again for
+// allocation when the recycling criteria has been met.
+
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  void *p, *old_p;
+  size_t size = 1U << 16;
+
+  // The delayed freelist will prevent a chunk from being available right away
+  p = malloc(size);
+  if (!p)
+    return 1;
+  old_p = p;
+  free(p);
+  p = malloc(size);
+  if (!p)
+    return 1;
+  if (old_p == p)
+    return 1;
+  free(p);
+
+  // Eventually the chunk should become available again
+  bool found = false;
+  for (int i = 0; i < 0x100 && found == false; i++) {
+    p = malloc(size);
+    if (!p)
+      return 1;
+    found = (p == old_p);
+    free(p);
+  }
+  if (found == false)
+    return 1;
+
+  return 0;
+}
diff --git a/test/scudo/realloc.cpp b/test/scudo/realloc.cpp
new file mode 100644
index 000000000..2a7d5b69f
--- /dev/null
+++ b/test/scudo/realloc.cpp
@@ -0,0 +1,69 @@
+// RUN: %clang_scudo %s -o %t
+// RUN:     %run %t pointers 2>&1
+// RUN:     %run %t contents 2>&1
+// RUN: not %run %t memalign 2>&1 | FileCheck %s
+
+// Tests that our reallocation function returns the same pointer when the
+// requested size can fit into the previously allocated chunk. Also tests that
+// a new chunk is returned if the size is greater, and that the contents of the
+// chunk are left unchanged.
+// As a final test, make sure that a chunk allocated by memalign cannot be
+// reallocated.
+
+#include <assert.h>
+#include <malloc.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  void *p, *old_p;
+  size_t size = 32;
+
+  assert(argc == 2);
+  if (!strcmp(argv[1], "pointers")) {
+    old_p = p = realloc(nullptr, size);
+    if (!p)
+      return 1;
+    size = malloc_usable_size(p);
+    // Our realloc implementation will return the same pointer if the size
+    // requested is lower or equal to the usable size of the associated chunk.
+    p = realloc(p, size - 1);
+    if (p != old_p)
+      return 1;
+    p = realloc(p, size);
+    if (p != old_p)
+      return 1;
+    // And a new one if the size is greater.
+    p = realloc(p, size + 1);
+    if (p == old_p)
+      return 1;
+    // A size of 0 will free the chunk and return nullptr.
+    p = realloc(p, 0);
+    if (p)
+      return 1;
+    old_p = nullptr;
+  }
+  if (!strcmp(argv[1], "contents")) {
+    p = realloc(nullptr, size);
+    if (!p)
+      return 1;
+    for (int i = 0; i < size; i++)
+      reinterpret_cast<char *>(p)[i] = 'A';
+    p = realloc(p, size + 1);
+    // The contents of the reallocated chunk must match the original one.
+    for (int i = 0; i < size; i++)
+      if (reinterpret_cast<char *>(p)[i] != 'A')
+        return 1;
+  }
+  if (!strcmp(argv[1], "memalign")) {
+    // A chunk coming from memalign cannot be reallocated.
+    p = memalign(16, size);
+    if (!p)
+      return 1;
+    p = realloc(p, size);
+    free(p);
+  }
+  return 0;
+}
+
+// CHECK: ERROR: invalid chunk type when reallocating address
diff --git a/test/scudo/sized-delete.cpp b/test/scudo/sized-delete.cpp
new file mode 100644
index 000000000..5b1bf5fd4
--- /dev/null
+++ b/test/scudo/sized-delete.cpp
@@ -0,0 +1,40 @@
+// RUN: %clang_scudo -fsized-deallocation %s -o %t
+// RUN: SCUDO_OPTIONS=DeleteSizeMismatch=1     %run %t gooddel    2>&1
+// RUN: SCUDO_OPTIONS=DeleteSizeMismatch=1 not %run %t baddel     2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=DeleteSizeMismatch=0     %run %t baddel     2>&1
+// RUN: SCUDO_OPTIONS=DeleteSizeMismatch=1     %run %t gooddelarr 2>&1
+// RUN: SCUDO_OPTIONS=DeleteSizeMismatch=1 not %run %t baddelarr  2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=DeleteSizeMismatch=0     %run %t baddelarr  2>&1
+
+// Ensures that the sized delete operator errors out when the appropriate
+// option is passed and the sizes do not match between allocation and
+// deallocation functions.
+
+#include <new>
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+  assert(argc == 2);
+  if (!strcmp(argv[1], "gooddel")) {
+    long long *p = new long long;
+    operator delete(p, sizeof(long long));
+  }
+  if (!strcmp(argv[1], "baddel")) {
+    long long *p = new long long;
+    operator delete(p, 2);
+  }
+  if (!strcmp(argv[1], "gooddelarr")) {
+    char *p = new char[64];
+    operator delete[](p, 64);
+  }
+  if (!strcmp(argv[1], "baddelarr")) {
+    char *p = new char[63];
+    operator delete[](p, 64);
+  }
+  return 0;
+}
+
+// CHECK: ERROR: invalid sized delete on chunk at address
diff --git a/test/scudo/sizes.cpp b/test/scudo/sizes.cpp
new file mode 100644
index 000000000..7190cb64f
--- /dev/null
+++ b/test/scudo/sizes.cpp
@@ -0,0 +1,61 @@
+// RUN: %clang_scudo %s -o %t
+// RUN: SCUDO_OPTIONS=allocator_may_return_null=0 not %run %t malloc 2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=allocator_may_return_null=1     %run %t malloc 2>&1
+// RUN: SCUDO_OPTIONS=allocator_may_return_null=0 not %run %t calloc 2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=allocator_may_return_null=1     %run %t calloc 2>&1
+// RUN:                                               %run %t usable 2>&1
+
+// Tests for various edge cases related to sizes, notably the maximum size the
+// allocator can allocate. Tests that an integer overflow in the parameters of
+// calloc is caught.
+
+#include <assert.h>
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <limits>
+
+int main(int argc, char **argv)
+{
+  assert(argc == 2);
+  if (!strcmp(argv[1], "malloc")) {
+    // Currently the maximum size the allocator can allocate is 1ULL<<40 bytes.
+    size_t size = std::numeric_limits<size_t>::max();
+    void *p = malloc(size);
+    if (p)
+      return 1;
+    size = (1ULL << 40) - 16;
+    p = malloc(size);
+    if (p)
+      return 1;
+  }
+  if (!strcmp(argv[1], "calloc")) {
+    // Trigger an overflow in calloc.
+    size_t size = std::numeric_limits<size_t>::max();
+    void *p = calloc((size / 0x1000) + 1, 0x1000);
+    if (p)
+      return 1;
+  }
+  if (!strcmp(argv[1], "usable")) {
+    // Playing with the actual usable size of a chunk.
+    void *p = malloc(1007);
+    if (!p)
+      return 1;
+    size_t size = malloc_usable_size(p);
+    if (size < 1007)
+      return 1;
+    memset(p, 'A', size);
+    p = realloc(p, 2014);
+    if (!p)
+      return 1;
+    size = malloc_usable_size(p);
+    if (size < 2014)
+      return 1;
+    memset(p, 'B', size);
+    free(p);
+  }
+  return 0;
+}
+
+// CHECK: allocator is terminating the process