[hwasan] Add heap tag randomization.

[eugenis]

Summary

Generate tags for heap allocations from a pseudo-random sequence
seeded with getrandom(), where available.

[alekseyshl]

compiler-rt/lib/hwasan/hwasan_thread.cc

100

GetRandom and xorshift can result in 0, right? Maybe this and drop CHECK:

if (!random_buffer_) {
  random_state_ = xorshift(random_state_);
  while (!random_state)
    random_state = RandomSeed();
  random_buffer_ = random_state_;
}

[eugenis]

avoid zero random seed

compiler-rt/lib/hwasan/hwasan_thread.cc

100

Good point, RandomSeed can be zero, but xorshift, as far as i can see, will never turn non-zero to zero. Fixed with a loop in RandomSeed.

compiler-rt/lib/hwasan/hwasan_allocator.cc

 typedef CombinedAllocator<PrimaryAllocator, AllocatorCache,
                           SecondaryAllocator> Allocator;
 
 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;
+
 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);
 }
 
 AllocatorCache *GetAllocatorCache(HwasanThreadLocalMallocStorage *ms) {
static void *HwasanAllocate(StackTrace *stack, uptr size, uptr alignment,
   Metadata *meta =
       reinterpret_cast<Metadata *>(allocator.GetMetaData(allocated));
   meta->state = CHUNK_ALLOCATED;
   meta->requested_size = size;
   meta->alloc_context_id = StackDepotPut(*stack);
   if (zeroise)
     internal_memset(allocated, 0, size);
 
-  void *user_ptr = (flags()->tag_in_malloc &&
-                    atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
-                       ? (void *)TagMemoryAligned((uptr)allocated, size, 0xBB)
-                       : allocated;
+  void *user_ptr = allocated;
+  if (flags()->tag_in_malloc &&
+    user_ptr = (void *)TagMemoryAligned(
+        (uptr)user_ptr, size, t ? t->GenerateRandomTag() : kFallbackAllocTag);
 
   HWASAN_MALLOC_HOOK(user_ptr, size);
   return user_ptr;
 }
 
 void HwasanDeallocate(StackTrace *stack, void *user_ptr) {
   CHECK(user_ptr);
   HWASAN_FREE_HOOK(user_ptr);
 
   void *p = GetAddressFromPointer(user_ptr);
   Metadata *meta = reinterpret_cast<Metadata *>(allocator.GetMetaData(p));
   uptr size = meta->requested_size;
   meta->state = CHUNK_FREE;
   meta->requested_size = 0;
   meta->free_context_id = StackDepotPut(*stack);
   // This memory will not be reused by anyone else, so we are free to keep it
   // poisoned.
+  HwasanThread *t = GetCurrentThread();
   if (flags()->tag_in_free &&
       atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
-    TagMemoryAligned((uptr)p, size, 0xBC);
-  HwasanThread *t = GetCurrentThread();
+    TagMemoryAligned((uptr)p, size,
+                     t ? t->GenerateRandomTag() : kFallbackFreeTag);
   if (t) {
     AllocatorCache *cache = GetAllocatorCache(&t->malloc_storage());
     allocator.Deallocate(cache, p);
   } else {
     SpinMutexLock l(&fallback_mutex);
     AllocatorCache *cache = &fallback_allocator_cache;
     allocator.Deallocate(cache, p);
   }
void *HwasanReallocate(StackTrace *stack, void *user_old_p, uptr new_size,
   uptr old_size = meta->requested_size;
   uptr actually_allocated_size = allocator.GetActuallyAllocatedSize(old_p);
   if (new_size <= actually_allocated_size) {
     // We are not reallocating here.
     // FIXME: update stack trace for the allocation?
     meta->requested_size = new_size;
     if (!atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
       return user_old_p;
-    if (flags()->retag_in_realloc)
-      return (void *)TagMemoryAligned((uptr)old_p, new_size, 0xCC);
+    if (flags()->retag_in_realloc) {
+      HwasanThread *t = GetCurrentThread();
+      return (void *)TagMemoryAligned(
+          (uptr)old_p, new_size,
+          t ? t->GenerateRandomTag() : kFallbackAllocTag);
+    }
     if (new_size > old_size) {
       tag_t tag = GetTagFromPointer((uptr)user_old_p);
       TagMemoryAligned((uptr)old_p + old_size, new_size - old_size, tag);
     }
     return user_old_p;
   }
   uptr memcpy_size = Min(new_size, old_size);
   void *new_p = HwasanAllocate(stack, new_size, alignment, false /*zeroise*/);

compiler-rt/lib/hwasan/hwasan_thread.h

public:
   void LeaveSymbolizer() { in_symbolizer_--; }
 
   bool InInterceptorScope() { return in_interceptor_scope_; }
   void EnterInterceptorScope() { in_interceptor_scope_++; }
   void LeaveInterceptorScope() { in_interceptor_scope_--; }
 
   HwasanThreadLocalMallocStorage &malloc_storage() { return malloc_storage_; }
 
+  tag_t GenerateRandomTag();
+
   int destructor_iterations_;
 
  private:
   // NOTE: There is no HwasanThread constructor. It is allocated
   // via mmap() and *must* be valid in zero-initialized state.
   void SetThreadStackAndTls();
   void ClearShadowForThreadStackAndTLS();
   thread_callback_t start_routine_;
   void *arg_;
   uptr stack_top_;
   uptr stack_bottom_;
   uptr tls_begin_;
   uptr tls_end_;
 
   unsigned in_signal_handler_;
   unsigned in_symbolizer_;
   unsigned in_interceptor_scope_;
 
+  u32 random_state_;
+  u32 random_buffer_;
+
   HwasanThreadLocalMallocStorage malloc_storage_;
 };
 
 HwasanThread *GetCurrentThread();
 void SetCurrentThread(HwasanThread *t);
 
 } // namespace __hwasan
 
 #endif // HWASAN_THREAD_H

compiler-rt/lib/hwasan/hwasan_thread.cc

 
 #include "hwasan.h"
 #include "hwasan_thread.h"
 #include "hwasan_poisoning.h"
 #include "hwasan_interface_internal.h"
 
 #include "sanitizer_common/sanitizer_tls_get_addr.h"
 
 namespace __hwasan {
 
+static u32 RandomSeed() {
+  u32 seed;
+  if (UNLIKELY(!GetRandom(reinterpret_cast<void *>(&seed), sizeof(seed),
+                          /*blocking=*/false))) {
+    seed = static_cast<u32>(
+        (NanoTime() >> 12) ^
+        (reinterpret_cast<uptr>(__builtin_frame_address(0)) >> 4));
+  }
+  return seed;
+}
+
 HwasanThread *HwasanThread::Create(thread_callback_t start_routine,
                                void *arg) {
   uptr PageSize = GetPageSizeCached();
   uptr size = RoundUpTo(sizeof(HwasanThread), PageSize);
   HwasanThread *thread = (HwasanThread*)MmapOrDie(size, __func__);
   thread->start_routine_ = start_routine;
   thread->arg_ = arg;
   thread->destructor_iterations_ = GetPthreadDestructorIterations();
+  thread->random_state_ = RandomSeed();
 
   return thread;
 }
 
 void HwasanThread::SetThreadStackAndTls() {
   uptr tls_size = 0;
   uptr stack_size = 0;
   GetThreadStackAndTls(IsMainThread(), &stack_bottom_, &stack_size,
if (!start_routine_) {
     return 0;
   }
 
   thread_return_t res = start_routine_(arg_);
 
   return res;
 }
 
+static u32 xorshift(u32 state) {
+  state ^= state << 13;
+  state ^= state >> 17;
+  state ^= state << 5;
+  return state;
+}
+
+// Generate a (pseudo-)random non-zero tag.
+tag_t HwasanThread::GenerateRandomTag() {
+  tag_t tag;
+  do {
+    if (!random_buffer_)
+      random_buffer_ = random_state_ = xorshift(random_state_);
+    CHECK(random_buffer_);
+    tag = random_buffer_ & 0xFF;
+    random_buffer_ >>= 8;
+  } while (!tag);
+  return tag;
+}
+
 } // namespace __hwasan