[hwasan] implement free_checks_tail_magic=1

[kcc]

Summary

With free_checks_tail_magic=1 (default) HWASAN
writes magic bytes to the tail of every heap allocation
(last bytes of the last granule, if the last granule is not fully used)
and checks these bytes on free().

This feature will detect buffer overwires within the last granule
at the time of free().

This is an alternative to malloc_align_right=[1289] that should have
fewer compatibility issues. It is also weaker since it doesn't
detect read overflows and reports bugs at free() instead of at access.

[eugenis]

Users will hate these reports.
LGTM with comments

lib/hwasan/hwasan_allocator.cc

220 ↗

(On Diff #174467)

There is a check like this in TaggedSize.
Maybe check that tail_size is <= shadow granule instead.

lib/hwasan/hwasan_report.cc

350 ↗

(On Diff #174467)

This will break output into multiple lines in syslog. Needs buffering, same as shadow map printing.

[kcc]

addressed comments.

[kcc]

Yep. We ourselves will hate these reports. Still, better than nothing.

lib/hwasan/hwasan_allocator.cc

220 ↗

(On Diff #174467)

done

lib/hwasan/hwasan_report.cc

350 ↗

(On Diff #174467)

done

[eugenis]

lib/hwasan/hwasan_allocator.cc

46 ↗

(On Diff #174476)

I don't think ALIGNED(16) is necessary.

222 ↗

(On Diff #174476)

less-or-equals
When size is 0, tagged_size is 16.

[eugenis]

lib/hwasan/hwasan_allocator.cc

222 ↗

(On Diff #174476)

oh right, tail is 0 in that case

compiler-rt/trunk/lib/hwasan/hwasan_allocator.cc

enum RightAlignMode {
   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;
 
+// Initialized in HwasanAllocatorInit, an never changed.
+static ALIGNED(16) u8 tail_magic[kShadowAlignment];
 
 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;
case 9:
       right_align_mode = kRightAlignAlways;
       right_align_8 = true;
       break;
     default:
       Report("ERROR: unsupported value of malloc_align_right flag: %d\n",
              flags()->malloc_align_right);
       Die();
   }
-
+  for (uptr i = 0; i < kShadowAlignment; i++)
+    tail_magic[i] = GetCurrentThread()->GenerateRandomTag();
 }
 
 void AllocatorSwallowThreadLocalCache(AllocatorCache *cache) {
   allocator.SwallowCache(cache);
 }
 
 static uptr TaggedSize(uptr size) {
   if (!size) size = 1;
static void *HwasanAllocate(StackTrace *stack, uptr orig_size, uptr alignment,
   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);
   }
+  if (!right_align_mode)
+    internal_memcpy(reinterpret_cast<u8 *>(allocated) + orig_size, tail_magic,
+                    size - orig_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) &&
void HwasanDeallocate(StackTrace *stack, void *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(aligned_ptr));
   uptr orig_size = meta->requested_size;
   u32 free_context_id = StackDepotPut(*stack);
   u32 alloc_context_id = meta->alloc_context_id;
+
+  // Check tail magic.
+  uptr tagged_size = TaggedSize(orig_size);
+  if (flags()->free_checks_tail_magic && !meta->right_aligned && orig_size) {
+    uptr tail_size = tagged_size - orig_size;
+    CHECK_LT(tail_size, kShadowAlignment);
+    void *tail_beg = reinterpret_cast<void *>(
+        reinterpret_cast<uptr>(aligned_ptr) + orig_size);
+    if (tail_size && internal_memcmp(tail_beg, tail_magic, tail_size))
+      ReportTailOverwritten(stack, reinterpret_cast<uptr>(tagged_ptr),
+                            orig_size, tail_size, tail_magic);
+  }
+
   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(TaggedSize(orig_size), (uptr)flags()->max_free_fill_size);

compiler-rt/trunk/lib/hwasan/hwasan_flags.inc

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(bool, free_checks_tail_magic, 1,
+    "If set, free() will check the magic values "
+    "to the right of the allocated object "
+    "if the allocation size is not a divident of the granule size")
 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.")

compiler-rt/trunk/lib/hwasan/hwasan_report.h

 #include "sanitizer_common/sanitizer_stacktrace.h"
 
 namespace __hwasan {
 
 void ReportStats();
 void ReportTagMismatch(StackTrace *stack, uptr addr, uptr access_size,
                        bool is_store, bool fatal);
 void ReportInvalidFree(StackTrace *stack, uptr addr);
+void ReportTailOverwritten(StackTrace *stack, uptr addr, uptr orig_size,
+                           uptr tail_size, const u8 *expected);
 
 void ReportAtExitStatistics();
 
 
 }  // namespace __hwasan
 
 #endif  // HWASAN_REPORT_H

compiler-rt/trunk/lib/hwasan/hwasan_report.cc

void ReportInvalidFree(StackTrace *stack, uptr tagged_addr) {
 
   PrintAddressDescription(tagged_addr, 0, nullptr);
 
   PrintTagsAroundAddr(tag_ptr);
 
   ReportErrorSummary(bug_type, stack);
 }
 
+void ReportTailOverwritten(StackTrace *stack, uptr tagged_addr, uptr orig_size,
+                           uptr tail_size, const u8 *expected) {
+  ScopedReport R(flags()->halt_on_error);
+  Decorator d;
+  uptr untagged_addr = UntagAddr(tagged_addr);
+  Printf("%s", d.Error());
+  const char *bug_type = "alocation-tail-overwritten";
+  Report("ERROR: %s: %s; heap object [%p,%p) of size %zd\n", SanitizerToolName,
+         bug_type, untagged_addr, untagged_addr + orig_size, orig_size);
+  Printf("\n%s", d.Default());
+  stack->Print();
+  HwasanChunkView chunk = FindHeapChunkByAddress(untagged_addr);
+  if (chunk.Beg()) {
+    Printf("%s", d.Allocation());
+    Printf("allocated here:\n");
+    Printf("%s", d.Default());
+    GetStackTraceFromId(chunk.GetAllocStackId()).Print();
+  }
+
+  InternalScopedString s(GetPageSizeCached() * 8);
+  CHECK_GT(tail_size, 0U);
+  CHECK_LT(tail_size, kShadowAlignment);
+  u8 *tail = reinterpret_cast<u8*>(untagged_addr + orig_size);
+  s.append("Tail contains: ");
+  for (uptr i = 0; i < kShadowAlignment - tail_size; i++)
+    s.append(".. ");
+  for (uptr i = 0; i < tail_size; i++)
+    s.append("%02x ", tail[i]);
+  s.append("\n");
+  s.append("Expected:      ");
+  for (uptr i = 0; i < kShadowAlignment - tail_size; i++)
+    s.append(".. ");
+  for (uptr i = 0; i < tail_size; i++)
+    s.append("%02x ", expected[i]);
+  s.append("\n");
+  s.append("               ");
+  for (uptr i = 0; i < kShadowAlignment - tail_size; i++)
+    s.append("   ");
+  for (uptr i = 0; i < tail_size; i++)
+    s.append("%s ", expected[i] != tail[i] ? "^^" : "  ");
+
+  s.append("\nThis error occurs when a buffer overflow overwrites memory\n"
+    "to the right of a heap object, but within the %zd-byte granule, e.g.\n"
+    "   char *x = new char[20];\n"
+    "   x[25] = 42;\n"
+    "By default %s does not detect such bugs at the time of write,\n"
+    "but can detect them at the time of free/delete.\n"
+    "To disable this feature set HWASAN_OPTIONS=free_checks_tail_magic=0;\n"
+    "To enable checking at the time of access, set "
+    "HWASAN_OPTIONS=malloc_align_right to non-zero\n\n",
+    kShadowAlignment, SanitizerToolName);
+  Printf("%s", s.data());
+  GetCurrentThread()->Announce();
+
+  tag_t *tag_ptr = reinterpret_cast<tag_t*>(MemToShadow(untagged_addr));
+  PrintTagsAroundAddr(tag_ptr);
+
+  ReportErrorSummary(bug_type, stack);
+}
+
 void ReportTagMismatch(StackTrace *stack, uptr tagged_addr, uptr access_size,
                        bool is_store, bool fatal) {
   ScopedReport R(fatal);
   SavedStackAllocations current_stack_allocations(
       GetCurrentThread()->stack_allocations());
 
   Decorator d;
   Printf("%s", d.Error());

compiler-rt/trunk/test/hwasan/TestCases/tail-magic.c

+// Tests free_checks_tail_magic=1.
+// RUN: %clang_hwasan  %s -o %t
+// RUN: %env_hwasan_opts=free_checks_tail_magic=0     %run %t
+// RUN: %env_hwasan_opts=free_checks_tail_magic=1 not %run %t 2>&1 | FileCheck %s
+// RUN:                                           not %run %t 2>&1 | FileCheck %s
+
+// 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();
+
+  char *p = (char*)malloc(20);
+  sink = p;
+  p[20] = 0x42;
+  p[24] = 0x66;
+  free(p);
+// CHECK: ERROR: HWAddressSanitizer: alocation-tail-overwritten; heap object [{{.*}}) of size 20
+// CHECK: in main {{.*}}tail-magic.c:[[@LINE-2]]
+// CHECK: allocated here:
+// CHECK: in main {{.*}}tail-magic.c:[[@LINE-8]]
+// CHECK: Tail contains: .. .. .. .. 42 {{.. .. ..}} 66
+}