[hwasan] optionally right-align heap allocations

[kcc]

Summary

... so that we can find intra-granule buffer overflows.
The default is still to always align left.
It remains to be seen wether we can enable this mode at scale.

[dvyukov]

lib/hwasan/hwasan_allocator.cc

168

Shouldn't we also look at user-requested alignment here? It looks like we only satisfy natural alignment.

test/hwasan/TestCases/heap-buffer-overflow.c

30–31

This won't catch regressions as it will be happy with 8 in all cases.

36–37

Ditto.

42

Ditto.

[eugenis]

lib/hwasan/hwasan_allocator.cc

168

Yeah, at least for calls like posix_memalign.

This mode will break some things anyway, ex.:
struct S {

int count;
char name[0];

};

When allocated with malloc(sizeof(S) + count) the size will not be a multiple of alignment, so "count" will be misaligned. That's why this mode can not be on by default. Let's hope it is not a common case.

171

Use named constants, like kHandleSignalYes.

172

This is not very random - entire region will have the same bit, so long running programs are likely to be stuck in either direction.

Use HwasanThread::random_buffer_ instead?

[dvyukov]

lib/hwasan/hwasan_allocator.cc

168

Why will not respecting alignment argument help? That's the alignment that we ensure in normal mode.

[kcc]

use the pointer tag's bit as a source of randmness.
split the test lines for right and left alignment.

[kcc]

use a named constant (kRightAlignAlways) instead of just '2' when checking the malloc_align_right flag.

[kcc]

lib/hwasan/hwasan_allocator.cc

168

I've changed the code so that it respects alignment > 16.
Respecting smaller alignment is harder because the implecit alignment requirement for malloc is 16
(it's a bit more complicated than that, actually, I don't think the standard actually tells what the alignment is,
it just tells that it should be sufficient for any builtin type)

This mode is unlikely to be enabled by default in its current form.
For we can only tell what modifications will be needed once we try.

171

done

172

Changed to use a bit of the tag, that is random (unless, of course, we disable random tags via a flag)

test/hwasan/TestCases/heap-buffer-overflow.c

30–31

done

36–37

done

42

done

[kcc]

BTW, electric fence has EF_ALIGNMENT=1 (to set alignment to 1) and people have been using it for decades,
so this approach is not entirely unheard of.

[dvyukov]

lib/hwasan/hwasan_allocator.cc

168

Strictly saying this can be handled in standard-conforming way for C++.
We need to enable -faligned-allocation to get C++17 alignment-aware operator new:
https://en.cppreference.com/w/cpp/memory/new/operator_new
And then pass -fnew-alignment=1 which will force compiler to call operator new with explicit alignment always.
This results in:

      int *volatile p1 = new int;
400614:       bf 04 00 00 00          mov    $0x4,%edi
400619:       be 04 00 00 00          mov    $0x4,%esi
40061e:       e8 ed fe ff ff          callq  400510 <operator new(unsigned long, std::align_val_t)@plt>
400623:       48 89 44 24 08          mov    %rax,0x8(%rsp)
      short *volatile p2 = new short[2];
400628:       bf 04 00 00 00          mov    $0x4,%edi
40062d:       be 02 00 00 00          mov    $0x2,%esi
400632:       e8 c9 fe ff ff          callq  400500 <operator new[](unsigned long, std::align_val_t)@plt>
400637:       48 89 44 24 10          mov    %rax,0x10(%rsp)

[kcc]

Atomic operations on aarch64 require alignment, so this approach will break whenever the code does something like
struct Foo{

AtomiWord a;  // used by atomic instructions 
char vla[0];

}
all other loads/stores seem to work (see "B2.5.2 Alignment of data accesses" in https://static.docs.arm.com/ddi0487/da/DDI0487D_a_armv8_arm.pdf)

so far I've found one such place (std::string implementation in libstdc++, which uses a ref counting string).
I've also tried several benchmarks from fuzzer-test-suite with hwasan and right-alignment.
Those that don't use std::string just work, so I think we still have a chance to get away with this on aarch64,
although we may require some code modifications to avoid the situation above.

[kcc]

One more case: https://github.com/google/re2/blob/master/re2/dfa.cc#L758
Here, again, we have a 8-byte object accessed atomically
and the size of the allocation is not necessary divisible by 8 (68 in my this case)

const int kStateCacheOverhead = 40;

int nnext = prog_->bytemap_range() + 1;  // + 1 for kByteEndText slot
int mem = sizeof(State) + nnext*sizeof(std::atomic<State*>) +
          ninst*sizeof(int);
if (mem_budget_ < mem + kStateCacheOverhead) {
  mem_budget_ = -1;
  return NULL;
}
mem_budget_ -= mem + kStateCacheOverhead;

This particular case is easy to fix by aligning mem by sizeof(void*)

[kcc]

Added two more modes for malloc_align_right to allow 8-byte alignment
(randomly or always).
Extended comments, added one more test.

PTAL

[eugenis]

lib/hwasan/hwasan_allocator.cc

92

CHECK that the flag has a valid value

272

if right_aligned, check that it is not more than one granule apart

[kcc]

addressed comments.

PTAL

[kcc]

lib/hwasan/hwasan_allocator.cc

92

done

272

done

[eugenis]

LGTM

lib/hwasan/hwasan_allocator.h

 
 #if !defined(__aarch64__) && !defined(__x86_64__)
 #error Unsupported platform
 #endif
 
 namespace __hwasan {
 
 struct Metadata {
-  u32 requested_size;  // sizes are < 4G.
+  u32 requested_size : 31;  // sizes are < 2G.
+  u32 right_aligned  : 1;
   u32 alloc_context_id;
 };
 
 struct HwasanMapUnmapCallback {
   void OnMap(uptr p, uptr size) const { UpdateMemoryUsage(); }
   void OnUnmap(uptr p, uptr size) const {
     // We are about to unmap a chunk of user memory.
     // It can return as user-requested mmap() or another thread stack.

lib/hwasan/hwasan_allocator.cc

 static Allocator allocator;
 static AllocatorCache fallback_allocator_cache;
 static SpinMutex fallback_mutex;
 static atomic_uint8_t hwasan_allocator_tagging_enabled;
 
 static const tag_t kFallbackAllocTag = 0xBB;
 static const tag_t kFallbackFreeTag = 0xBC;
 
+enum RightAlignMode {
+  kRightAlignNever,
+  kRightAlignSometimes,
+  kRightAlignAlways
+};
+
+// These two variables are initialized from flags()->malloc_align_right
+// in HwasanAllocatorInit and are never changed afterwards.
+static RightAlignMode right_align_mode = kRightAlignNever;
+static bool right_align_8 = false;
+
+
 bool HwasanChunkView::IsAllocated() const {
   return metadata_ && metadata_->alloc_context_id && metadata_->requested_size;
 }
 
+// Aligns the 'addr' right to the granule boundary.
+static uptr AlignRight(uptr addr, uptr requested_size) {
+  uptr tail_size = requested_size % kShadowAlignment;
+  if (!tail_size) return addr;
+  if (right_align_8)
+    return tail_size > 8 ? addr : addr + 8;
+  return addr + kShadowAlignment - tail_size;
+}
+
 uptr HwasanChunkView::Beg() const {
+  if (metadata_ && metadata_->right_aligned)
+    return AlignRight(block_, metadata_->requested_size);
   return block_;
 }
 uptr HwasanChunkView::End() const {
   return Beg() + UsedSize();
 }
 uptr HwasanChunkView::UsedSize() const {
   return metadata_->requested_size;
 }
void GetAllocatorStats(AllocatorStatCounters s) {
   allocator.GetStats(s);
 }
 
 void HwasanAllocatorInit() {
   atomic_store_relaxed(&hwasan_allocator_tagging_enabled,
                        !flags()->disable_allocator_tagging);
   SetAllocatorMayReturnNull(common_flags()->allocator_may_return_null);
   allocator.Init(common_flags()->allocator_release_to_os_interval_ms);
+  switch (flags()->malloc_align_right) {
+    case 1:
+            right_align_mode = kRightAlignSometimes;
+            right_align_8 = false;
+            break;
+    case 2:
+            right_align_mode = kRightAlignAlways;
+            right_align_8 = false;
+            break;
+    case 8:
+            right_align_mode = kRightAlignSometimes;
+            right_align_8 = true;
+            break;
+    case 9:
+            right_align_mode = kRightAlignAlways;
+            right_align_8 = true;
+            break;
+  }
 }
 
 void AllocatorSwallowThreadLocalCache(AllocatorCache *cache) {
   allocator.SwallowCache(cache);
 }
 
 static uptr TaggedSize(uptr size) {
   if (!size) size = 1;
if (UNLIKELY(!allocated)) {
     if (AllocatorMayReturnNull())
       return nullptr;
     ReportOutOfMemory(size, stack);
   }
   Metadata *meta =
       reinterpret_cast<Metadata *>(allocator.GetMetaData(allocated));
   meta->requested_size = static_cast<u32>(orig_size);
   meta->alloc_context_id = StackDepotPut(*stack);
+  meta->right_aligned = false;
   if (zeroise) {
     internal_memset(allocated, 0, size);
   } else if (flags()->max_malloc_fill_size > 0) {
     uptr fill_size = Min(size, (uptr)flags()->max_malloc_fill_size);
     internal_memset(allocated, flags()->malloc_fill_byte, fill_size);
   }
 
   void *user_ptr = allocated;
   if (flags()->tag_in_malloc &&
       atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
     user_ptr = (void *)TagMemoryAligned(
         (uptr)user_ptr, size, t ? t->GenerateRandomTag() : kFallbackAllocTag);
 
+  if ((orig_size % kShadowAlignment) && (alignment <= kShadowAlignment) &&
+      right_align_mode) {
+    uptr as_uptr = reinterpret_cast<uptr>(user_ptr);
+    if (right_align_mode == kRightAlignAlways ||
+        GetTagFromPointer(as_uptr) & 1) {  // use a tag bit as a random bit.
+      user_ptr = reinterpret_cast<void *>(AlignRight(as_uptr, orig_size));
+      meta->right_aligned = 1;
+    }
+  }
+
   HWASAN_MALLOC_HOOK(user_ptr, size);
   return user_ptr;
 }
 
 static bool PointerAndMemoryTagsMatch(void *tagged_ptr) {
   CHECK(tagged_ptr);
   tag_t ptr_tag = GetTagFromPointer(reinterpret_cast<uptr>(tagged_ptr));
   tag_t mem_tag = *reinterpret_cast<tag_t *>(
       MemToShadow(reinterpret_cast<uptr>(UntagPtr(tagged_ptr))));
   return ptr_tag == mem_tag;
 }
 
 void HwasanDeallocate(StackTrace *stack, void *tagged_ptr) {
   CHECK(tagged_ptr);
   HWASAN_FREE_HOOK(tagged_ptr);
 
   if (!PointerAndMemoryTagsMatch(tagged_ptr))
     ReportInvalidFree(stack, reinterpret_cast<uptr>(tagged_ptr));
 
   void *untagged_ptr = UntagPtr(tagged_ptr);
+  void *aligned_ptr = reinterpret_cast<void *>(
+      RoundDownTo(reinterpret_cast<uptr>(untagged_ptr), kShadowAlignment));
   Metadata *meta =
-      reinterpret_cast<Metadata *>(allocator.GetMetaData(untagged_ptr));
+      reinterpret_cast<Metadata *>(allocator.GetMetaData(aligned_ptr));
   uptr orig_size = meta->requested_size;
   u32 free_context_id = StackDepotPut(*stack);
   u32 alloc_context_id = meta->alloc_context_id;
   meta->requested_size = 0;
   meta->alloc_context_id = 0;
   // This memory will not be reused by anyone else, so we are free to keep it
   // poisoned.
   Thread *t = GetCurrentThread();
   if (flags()->max_free_fill_size > 0) {
-    uptr fill_size = Min(orig_size, (uptr)flags()->max_free_fill_size);
-    internal_memset(untagged_ptr, flags()->free_fill_byte, fill_size);
+    uptr fill_size =
+        Min(TaggedSize(orig_size), (uptr)flags()->max_free_fill_size);
+    internal_memset(aligned_ptr, flags()->free_fill_byte, fill_size);
   }
   if (flags()->tag_in_free &&
       atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
-    TagMemoryAligned((uptr)untagged_ptr, TaggedSize(orig_size),
+    TagMemoryAligned(reinterpret_cast<uptr>(aligned_ptr), TaggedSize(orig_size),
                      t ? t->GenerateRandomTag() : kFallbackFreeTag);
   if (t) {
-    allocator.Deallocate(t->allocator_cache(), untagged_ptr);
+    allocator.Deallocate(t->allocator_cache(), aligned_ptr);
     if (auto *ha = t->heap_allocations())
       ha->push({reinterpret_cast<uptr>(tagged_ptr), alloc_context_id,
                 free_context_id, static_cast<u32>(orig_size)});
   } else {
     SpinMutexLock l(&fallback_mutex);
     AllocatorCache *cache = &fallback_allocator_cache;
-    allocator.Deallocate(cache, untagged_ptr);
+    allocator.Deallocate(cache, aligned_ptr);
   }
 }
 
 void *HwasanReallocate(StackTrace *stack, void *tagged_ptr_old, uptr new_size,
                      uptr alignment) {
   if (!PointerAndMemoryTagsMatch(tagged_ptr_old))
     ReportInvalidFree(stack, reinterpret_cast<uptr>(tagged_ptr_old));
 
Metadata *metadata =
       reinterpret_cast<Metadata*>(allocator.GetMetaData(block));
   return HwasanChunkView(reinterpret_cast<uptr>(block), metadata);
 }
 
 static uptr AllocationSize(const void *tagged_ptr) {
   const void *untagged_ptr = UntagPtr(tagged_ptr);
   if (!untagged_ptr) return 0;
   const void *beg = allocator.GetBlockBegin(untagged_ptr);
-  if (beg != untagged_ptr) return 0;
   Metadata *b = (Metadata *)allocator.GetMetaData(untagged_ptr);
+  if (beg != untagged_ptr && !b->right_aligned) return 0;
   return b->requested_size;
 }
 
 void *hwasan_malloc(uptr size, StackTrace *stack) {
   return SetErrnoOnNull(HwasanAllocate(stack, size, sizeof(u64), false));
 }
 
 void *hwasan_calloc(uptr nmemb, uptr size, StackTrace *stack) {

lib/hwasan/hwasan_flags.inc

 // If false, use simple increment of a thread local counter to generate new
 // tags.
 HWASAN_FLAG(bool, random_tags, true, "")
 
 HWASAN_FLAG(
     int, max_malloc_fill_size, 0x1000,  // By default, fill only the first 4K.
     "HWASan allocator flag. max_malloc_fill_size is the maximal amount of "
     "bytes that will be filled with malloc_fill_byte on malloc.")
+
+// Rules for malloc alignment on aarch64:
+//   * If the size is 16-aligned, then malloc should return 16-aligned memory.
+//   * Otherwise, malloc should return 8-alignment memory.
+// So,
+//   * If the size is 16-aligned, we don't need to do anything.
+//   * Otherwise we don't have to obey 16-alignment, just the 8-alignment.
+//   * We may want to break the 8-alignment rule to catch more buffer overflows
+//     but this will break valid code in some rare cases, like this:
+//     struct Foo {
+//       // accessed via atomic instructions that require 8-alignment.
+//       std::atomic<int64_t> atomic_stuff;
+//       ...
+//       char vla[1];  // the actual size of vla could be anything.
+//     }
+// Which means that the safe values for malloc_align_right are 0, 8, 9,
+// and the values 1 and 2 may require changes in otherwise valid code.
+
+HWASAN_FLAG(
+    int, malloc_align_right, 0,  // off by default
+    "HWASan allocator flag. "
+    "0 (default): allocations are always aligned left to 16-byte boundary; "
+    "1: allocations are sometimes aligned right to 1-byte boundary (risky); "
+    "2: allocations are always aligned right to 1-byte boundary (risky); "
+    "8: allocations are sometimes aligned right to 8-byte boundary; "
+    "9: allocations are always aligned right to 8-byte boundary."
+  )
 HWASAN_FLAG(
     int, max_free_fill_size, 0,
     "HWASan allocator flag. max_free_fill_size is the maximal amount of "
     "bytes that will be filled with free_fill_byte during free.")
 HWASAN_FLAG(int, malloc_fill_byte, 0xbe,
           "Value used to fill the newly allocated memory.")
 HWASAN_FLAG(int, free_fill_byte, 0x55,
           "Value used to fill deallocated memory.")

test/hwasan/TestCases/heap-buffer-overflow.c

 // RUN: %clang_hwasan  %s -o %t
-// RUN: not %run %t 40 2>&1 | FileCheck %s --check-prefix=CHECK40
-// RUN: not %run %t 80 2>&1 | FileCheck %s --check-prefix=CHECK80
+// RUN:                                       not %run %t 40 2>&1 | FileCheck %s --check-prefix=CHECK40-LEFT
+// RUN: %env_hwasan_opts=malloc_align_right=2 not %run %t 40 2>&1 | FileCheck %s --check-prefix=CHECK40-RIGHT
+// RUN:                                       not %run %t 80 2>&1 | FileCheck %s --check-prefix=CHECK80-LEFT
+// RUN: %env_hwasan_opts=malloc_align_right=2 not %run %t 80 2>&1 | FileCheck %s --check-prefix=CHECK80-RIGHT
 // RUN: not %run %t -30 2>&1 | FileCheck %s --check-prefix=CHECKm30
 // RUN: not %run %t -30 1000000 2>&1 | FileCheck %s --check-prefix=CHECKMm30
 // RUN: not %run %t 1000000 1000000 2>&1 | FileCheck %s --check-prefix=CHECKM
 
+// Test OOB within the granule.
+// Misses the bug when malloc is left-aligned, catches it otherwise.
+// RUN:                                           %run %t 31
+// RUN: %env_hwasan_opts=malloc_align_right=2 not %run %t 31 2>&1 | FileCheck %s --check-prefix=CHECK31
+
+// RUN:                                           %run %t 30 20
+// RUN: %env_hwasan_opts=malloc_align_right=9 not %run %t 30 20 2>&1 | FileCheck %s --check-prefix=CHECK20-RIGHT8
+
 // REQUIRES: stable-runtime
 
 #include <stdlib.h>
 #include <stdio.h>
 #include <sanitizer/hwasan_interface.h>
 
 int main(int argc, char **argv) {
   __hwasan_enable_allocator_tagging();
   int offset = argc < 2 ? 40 : atoi(argv[1]);
   int size = argc < 3 ? 30 : atoi(argv[2]);
   char * volatile x = (char*)malloc(size);
+  fprintf(stderr, "base: %p access: %p\n", x, &x[offset]);
   x[offset] = 42;
-// CHECK40: allocated heap chunk; size: 32 offset: 8
-// CHECK40: is located 10 bytes to the right of 30-byte region
+
+// CHECK40-LEFT: allocated heap chunk; size: 32 offset: 8
+// CHECK40-LEFT: is located 10 bytes to the right of 30-byte region
+// CHECK40-RIGHT: allocated heap chunk; size: 32 offset: 10
+// CHECK40-RIGHT: is located 10 bytes to the right of 30-byte region
 //
-// CHECK80: allocated heap chunk; size: 32 offset: 16
-// CHECK80: is located 50 bytes to the right of 30-byte region
+// CHECK80-LEFT: allocated heap chunk; size: 32 offset: 16
+// CHECK80-LEFT: is located 50 bytes to the right of 30-byte region
+// CHECK80-RIGHT: allocated heap chunk; size: 32 offset: 18
+// CHECK80-RIGHT: is located 50 bytes to the right of 30-byte region
 //
 // CHECKm30: allocated heap chunk; size: 32 offset: 2
 // CHECKm30: is located 30 bytes to the left of 30-byte region
 //
 // CHECKMm30: is a large allocated heap chunk; size: 1003520 offset: -30
 // CHECKMm30: is located 30 bytes to the left of 1000000-byte region
 //
 // CHECKM: is a large allocated heap chunk; size: 1003520 offset: 1000000
 // CHECKM: is located 0 bytes to the right of 1000000-byte region
+//
+// CHECK31: is located 1 bytes to the right of 30-byte region
+//
+// CHECK20-RIGHT8: is located 10 bytes to the right of 20-byte region [0x{{.*}}8,0x{{.*}}c)
   free(x);
 }

test/hwasan/TestCases/random-align-right.c

+// Tests malloc_align_right=1 and 8 (randomly aligning right).
+// RUN: %clang_hwasan  %s -o %t
+//
+// RUN: %run %t
+// RUN: %env_hwasan_opts=malloc_align_right=1 not %run %t 2>&1 | FileCheck %s --check-prefix=CHECK1
+// RUN: %env_hwasan_opts=malloc_align_right=8 not %run %t 2>&1 | FileCheck %s --check-prefix=CHECK8
+
+// REQUIRES: stable-runtime
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <sanitizer/hwasan_interface.h>
+
+static volatile void *sink;
+
+int main(int argc, char **argv) {
+  __hwasan_enable_allocator_tagging();
+
+  // Perform 1000 buffer overflows within the 16-byte granule,
+  // so that random right-alignment has a very high chance of
+  // catching at least one of them.
+  for (int i = 0; i < 1000; i++) {
+    char *p = (char*)malloc(20);
+    sink = p;
+    fprintf(stderr, "[%d] p: %p; accessing p[20]:\n", i, p);
+    p[20 * argc] = 0;  // requires malloc_align_right=1 to catch
+    fprintf(stderr, "[%d] p: %p; accessing p[30]:\n", i, p);
+    p[30 * argc] = 0;  // requires malloc_align_right={1,8} to catch
+// CHECK1: accessing p[20]
+// CHECK1-NEXT: HWAddressSanitizer: tag-mismatch
+// CHECK8: accessing p[30]:
+// CHECK8-NEXT: HWAddressSanitizer: tag-mismatch
+  }
+}
+

test/hwasan/TestCases/use-after-free.c

int main() {
   free(x);
   __hwasan_disable_allocator_tagging();
   fprintf(stderr, "Going to do a %s\n", ISREAD ? "READ" : "WRITE");
   // CHECK: Going to do a [[TYPE:[A-Z]*]]
   int r = 0;
   if (ISREAD) r = x[5]; else x[5] = 42;  // should be on the same line.
   // CHECK: [[TYPE]] of size 1 at {{.*}} tags: [[PTR_TAG:[0-9a-f][0-9a-f]]]/[[MEM_TAG:[0-9a-f][0-9a-f]]] (ptr/mem)
   // CHECK: #0 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-2]]
-
-  // CHECK: is a small unallocated heap chunk; size: 16 offset: 5
+  // Offset is 5 or 11 depending on left/right alignment.
+  // CHECK: is a small unallocated heap chunk; size: 16 offset: {{5|11}}
   // CHECK: is located 5 bytes inside of 10-byte region
   //
   // CHECK: freed by thread {{.*}} here:
   // CHECK: #0 {{.*}} in {{.*}}free{{.*}} {{.*}}hwasan_interceptors.cc
   // CHECK: #1 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-14]]
 
   // CHECK: previously allocated here:
   // CHECK: #0 {{.*}} in {{.*}}malloc{{.*}} {{.*}}hwasan_interceptors.cc
   // CHECK: #1 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-19]]
   // CHECK: Memory tags around the buggy address (one tag corresponds to 16 bytes):
   // CHECK: =>{{.*}}[[MEM_TAG]]
   // CHECK: SUMMARY: HWAddressSanitizer: tag-mismatch {{.*}} in main
   return r;
 }