hwasan: Use bits [3..11) of the ring buffer entry address as the base stack tag.

[pcc]

Summary

This saves roughly 32 bytes of instructions per function with stack objects
and causes us to preserve enough information that we can recover the original
tags of all stack variables.

Now that stack tags are deterministic, we no longer need to pass
-hwasan-generate-tags-with-calls during check-hwasan. This also means that the
new stack tag generation mechanism is exercised by check-hwasan.

Depends on D63119

[eugenis]

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

1007 ↗

(On Diff #204843)

We are losing a lot of entropy by allowing these zero bits in the base tag. Single-alloca functions, for example, will only have 32 different tags.

How about using bits 3 .. 11 ?

[pcc]

• Address review comments

[pcc]

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

1007 ↗

(On Diff #204843)

Done. Now tag 0 is as likely as any other tag.

To fix the tests that were assuming that they would never get tag 0, I've added a call to a helper function that bumps the base tag to 128 to the tests that would otherwise fail.

[eugenis]

We can make the tags undeterministic again by starting each ring buffer at a random index.

[pcc]

• Sort FastMasks by increasing probability of collisions

[eugenis]

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

30 ↗

(On Diff #205130)

why did you copy this line?

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

I don't understand this. How does a single additional call to FUNC help guarantee that property?

[pcc]

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

30 ↗

(On Diff #205130)

Because the additional call to GenerateRandomTag in InitRandomState causes the values that we assign to tail_magic in HwasanAllocatorInit to change in such a way that we catch the second bad access and not the first one. Without copying this line the CHECK?-NEXT lines fail to match because the failure doesn't happen on the line after the first message.

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

In the case where there are 2046 calls to FUNC we have:

• tag 1 for FUNC0
• tag 2..2047 (mod 256) for FUNC1
• tag 2048 (mod 256) for OOB (i.e. 0)

Adding the call to FUNC shifts all of the tags by 1 so that OOB gets tag 1.

[eugenis]

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

30 ↗

(On Diff #205130)

Wait, so the comment above the loop lies? We are testing for the bug on the first iteration, not an any iteration. Maybe remove -NEXT?

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

Could we call OOB twice instead? And weaken the test a bit so that it is ok with result being off by 1 or 2 in any direction?

[pcc]

• Address review comments

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

30 ↗

(On Diff #205130)

Yeah, looks like a mistake in the test. The intent here was apparently that we'd let any access fail, but the test actually only lets the first access fail (and because of determinism that is always what happens).

We can't just remove -NEXT because it would prevent the test from determining which access found the bug. So I've rewritten this test a bit so that we can do that.

compiler-rt/test/hwasan/TestCases/stack-history-length.c

20 ↗

(On Diff #205130)

Works for me, done.

[eugenis]

LGTM

compiler-rt/trunk/lib/hwasan/hwasan_thread.cpp

if (UNLIKELY(!GetRandom(reinterpret_cast<void *>(&seed), sizeof(seed),
           (reinterpret_cast<uptr>(__builtin_frame_address(0)) >> 4));
     }
   } while (!seed);
   return seed;
 }
 
 void Thread::InitRandomState() {
   random_state_ = flags()->random_tags ? RandomSeed() : unique_id_;
+
+  // Push a random number of zeros onto the ring buffer so that the first stack
+  // tag base will be random.
+  for (tag_t i = 0, e = GenerateRandomTag(); i != e; ++i)
+    stack_allocations_->push(0);
 }
 
 void Thread::Init(uptr stack_buffer_start, uptr stack_buffer_size) {
   static u64 unique_id;
   unique_id_ = unique_id++;
   if (auto sz = flags()->heap_history_size)
     heap_allocations_ = HeapAllocationsRingBuffer::New(sz);
 

compiler-rt/trunk/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
+// RUN: %run %t 20
+// RUN: %run %t 30
+// RUN: %env_hwasan_opts=malloc_align_right=1 not %run %t 20 2>&1 | FileCheck %s --check-prefix=CHECK20
+// RUN: %env_hwasan_opts=malloc_align_right=1 not %run %t 30 2>&1 | FileCheck %s --check-prefix=CHECK30
+// RUN: %env_hwasan_opts=malloc_align_right=8 not %run %t 30 2>&1 | FileCheck %s --check-prefix=CHECK30
 
 // 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();
+  int index = atoi(argv[1]);
 
   // 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
+    p[index] = 0;
+// index=20 requires malloc_align_right=1 to catch
+// CHECK20: HWAddressSanitizer: tag-mismatch
+// index=30 requires malloc_align_right={1,8} to catch
+// CHECK30: HWAddressSanitizer: tag-mismatch
   }
 }
 

compiler-rt/trunk/test/hwasan/TestCases/stack-history-length.c

 // RUN: %clang_hwasan -O1 %s -o %t
-// RUN: %env_hwasan_opts=stack_history_size=2048 not %run %t 2046 2>&1 | FileCheck %s --check-prefix=YES
+// RUN: %env_hwasan_opts=stack_history_size=2048 not %run %t 2045 2>&1 | FileCheck %s --check-prefix=YES
 // RUN: %env_hwasan_opts=stack_history_size=2048 not %run %t 2047 2>&1 | FileCheck %s --check-prefix=NO
 
 // REQUIRES: stable-runtime
 
 #include <stdlib.h>
 
 void USE(void *x) { // pretend_to_do_something(void *x)
   __asm__ __volatile__("" : : "r" (x) : "memory");
 }
 
 volatile int four = 4;
 __attribute__((noinline)) void FUNC0() { int x[4]; USE(&x[0]); }
 __attribute__((noinline)) void FUNC() { int x[4]; USE(&x[0]); }
 __attribute__((noinline)) void OOB() { int x[4]; x[four] = 0; USE(&x[0]); }
 
 int main(int argc, char **argv) {
   int X = argc == 2 ? atoi(argv[1]) : 10;
   // FUNC0 is X+2's element of the ring buffer.
   // If runtime buffer size is less than it, FUNC0 record will be lost.
   FUNC0();
   for (int i = 0; i < X; ++i)
     FUNC();
+  // Make at least one call to OOB where base tag != 0 so that the bug is caught
+  // at least once.
+  OOB();
   OOB();
 }
 
 // YES: Previously allocated frames
 // YES: OOB
 // YES: FUNC
 // YES: FUNC0
 
 // NO: Previously allocated frames
 // NO: OOB
 // NO: FUNC
 // NO-NOT: FUNC0

compiler-rt/trunk/test/hwasan/lit.cfg

 # -*- Python -*-
 
 import os
 
 # Setup config name.
 config.name = 'HWAddressSanitizer' + getattr(config, 'name_suffix', 'default')
 
 # Setup source root.
 config.test_source_root = os.path.dirname(__file__)
 
 # Setup default compiler flags used with -fsanitize=memory option.
 clang_cflags = [config.target_cflags] + config.debug_info_flags
 clang_cxxflags = config.cxx_mode_flags + clang_cflags
-clang_hwasan_cflags = ["-fsanitize=hwaddress", "-mllvm", "-hwasan-generate-tags-with-calls"] + clang_cflags
+clang_hwasan_cflags = ["-fsanitize=hwaddress"] + clang_cflags
 clang_hwasan_cxxflags = config.cxx_mode_flags + clang_hwasan_cflags
 
 def build_invocation(compile_flags):
   return " " + " ".join([config.clang] + compile_flags) + " "
 
 config.substitutions.append( ("%clangxx ", build_invocation(clang_cxxflags)) )
 config.substitutions.append( ("%clang_hwasan ", build_invocation(clang_hwasan_cflags)) )
 config.substitutions.append( ("%clangxx_hwasan ", build_invocation(clang_hwasan_cxxflags)) )

llvm/trunk/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

public:
   bool instrumentLandingPads(SmallVectorImpl<Instruction *> &RetVec);
   Value *getNextTagWithCall(IRBuilder<> &IRB);
   Value *getStackBaseTag(IRBuilder<> &IRB);
   Value *getAllocaTag(IRBuilder<> &IRB, Value *StackTag, AllocaInst *AI,
                      unsigned AllocaNo);
   Value *getUARTag(IRBuilder<> &IRB, Value *StackTag);
 
   Value *getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty);
-  Value *emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
+  void emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
 
 private:
   LLVMContext *C;
   std::string CurModuleUniqueId;
   Triple TargetTriple;
   FunctionCallee HWAsanMemmove, HWAsanMemcpy, HWAsanMemset;
   FunctionCallee HWAsanHandleVfork;
 
private:
 
   FunctionCallee HwasanTagMemoryFunc;
   FunctionCallee HwasanGenerateTagFunc;
   FunctionCallee HwasanThreadEnterFunc;
 
   Constant *ShadowGlobal;
 
   Value *LocalDynamicShadow = nullptr;
+  Value *StackBaseTag = nullptr;
   GlobalValue *ThreadPtrGlobal = nullptr;
 };
 
 class HWAddressSanitizerLegacyPass : public FunctionPass {
 public:
   // Pass identification, replacement for typeid.
   static char ID;
 
bool HWAddressSanitizer::tagAlloca(IRBuilder<> &IRB, AllocaInst *AI,
   return true;
 }
 
 static unsigned RetagMask(unsigned AllocaNo) {
   // A list of 8-bit numbers that have at most one run of non-zero bits.
   // x = x ^ (mask << 56) can be encoded as a single armv8 instruction for these
   // masks.
   // The list does not include the value 255, which is used for UAR.
-  static unsigned FastMasks[] = {
-      0,   1,   2,   3,   4,   6,   7,   8,   12,  14,  15, 16,  24,
-      28,  30,  31,  32,  48,  56,  60,  62,  63,  64,  96, 112, 120,
-      124, 126, 127, 128, 192, 224, 240, 248, 252, 254};
+  //
+  // Because we are more likely to use earlier elements of this list than later
+  // ones, it is sorted in increasing order of probability of collision with a
+  // mask allocated (temporally) nearby. The program that generated this list
+  // can be found at:
+  // https://github.com/google/sanitizers/blob/master/hwaddress-sanitizer/sort_masks.py
+  static unsigned FastMasks[] = {0,  128, 64,  192, 32,  96,  224, 112, 240,
+                                 48, 16,  120, 248, 56,  24,  8,   124, 252,
+                                 60, 28,  12,  4,   126, 254, 62,  30,  14,
+                                 6,  2,   127, 63,  31,  15,  7,   3,   1};
   return FastMasks[AllocaNo % (sizeof(FastMasks) / sizeof(FastMasks[0]))];
 }
 
 Value *HWAddressSanitizer::getNextTagWithCall(IRBuilder<> &IRB) {
   return IRB.CreateZExt(IRB.CreateCall(HwasanGenerateTagFunc), IntptrTy);
 }
 
 Value *HWAddressSanitizer::getStackBaseTag(IRBuilder<> &IRB) {
   if (ClGenerateTagsWithCalls)
     return getNextTagWithCall(IRB);
+  if (StackBaseTag)
+    return StackBaseTag;
   // FIXME: use addressofreturnaddress (but implement it in aarch64 backend
   // first).
   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
   auto GetStackPointerFn =
       Intrinsic::getDeclaration(M, Intrinsic::frameaddress);
   Value *StackPointer = IRB.CreateCall(
       GetStackPointerFn, {Constant::getNullValue(IRB.getInt32Ty())});
 
void HWAddressSanitizer::createFrameGlobal(Function &F,
   GV->setSection(getFrameSection());
   appendToCompilerUsed(M, GV);
   // Put GV into the F's Comadat so that if F is deleted GV can be deleted too.
   if (auto Comdat =
           GetOrCreateFunctionComdat(F, TargetTriple, CurModuleUniqueId))
     GV->setComdat(Comdat);
 }
 
-Value *HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB,
-                                        bool WithFrameRecord) {
-  if (!Mapping.InTls)
-    return getDynamicShadowNonTls(IRB);
+void HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord) {
+  if (!Mapping.InTls) {
+    LocalDynamicShadow = getDynamicShadowNonTls(IRB);
+    return;
+  }
 
-  if (!WithFrameRecord && TargetTriple.isAndroid())
-    return getDynamicShadowIfunc(IRB);
+  if (!WithFrameRecord && TargetTriple.isAndroid()) {
+    LocalDynamicShadow = getDynamicShadowIfunc(IRB);
+    return;
+  }
 
   Value *SlotPtr = getHwasanThreadSlotPtr(IRB, IntptrTy);
   assert(SlotPtr);
 
   Instruction *ThreadLong = IRB.CreateLoad(IntptrTy, SlotPtr);
 
   Function *F = IRB.GetInsertBlock()->getParent();
   if (F->getFnAttribute("hwasan-abi").getValueAsString() == "interceptor") {
if (F->getFnAttribute("hwasan-abi").getValueAsString() == "interceptor") {
     ThreadLong = ThreadLongPhi;
   }
 
   // Extract the address field from ThreadLong. Unnecessary on AArch64 with TBI.
   Value *ThreadLongMaybeUntagged =
       TargetTriple.isAArch64() ? ThreadLong : untagPointer(IRB, ThreadLong);
 
   if (WithFrameRecord) {
+    StackBaseTag = IRB.CreateAShr(ThreadLong, 3);
+
     // Prepare ring buffer data.
     auto PC = IRB.CreatePtrToInt(F, IntptrTy);
     auto GetStackPointerFn =
         Intrinsic::getDeclaration(F->getParent(), Intrinsic::frameaddress);
     Value *SP = IRB.CreatePtrToInt(
         IRB.CreateCall(GetStackPointerFn,
                        {Constant::getNullValue(IRB.getInt32Ty())}),
         IntptrTy);
-    // Mix SP and PC. TODO: also add the tag to the mix.
+    // Mix SP and PC.
     // Assumptions:
     // PC is 0x0000PPPPPPPPPPPP  (48 bits are meaningful, others are zero)
     // SP is 0xsssssssssssSSSS0  (4 lower bits are zero)
     // We only really need ~20 lower non-zero bits (SSSS), so we mix like this:
     //       0xSSSSPPPPPPPPPPPP
     SP = IRB.CreateShl(SP, 44);
 
     // Store data to ring buffer.
if (WithFrameRecord) {
     Value *ThreadLongNew = IRB.CreateAnd(
         IRB.CreateAdd(ThreadLong, ConstantInt::get(IntptrTy, 8)), WrapMask);
     IRB.CreateStore(ThreadLongNew, SlotPtr);
   }
 
   // Get shadow base address by aligning RecordPtr up.
   // Note: this is not correct if the pointer is already aligned.
   // Runtime library will make sure this never happens.
-  Value *ShadowBase = IRB.CreateAdd(
+  LocalDynamicShadow = IRB.CreateAdd(
       IRB.CreateOr(
           ThreadLongMaybeUntagged,
           ConstantInt::get(IntptrTy, (1ULL << kShadowBaseAlignment) - 1)),
       ConstantInt::get(IntptrTy, 1), "hwasan.shadow");
-  ShadowBase = IRB.CreateIntToPtr(ShadowBase, Int8PtrTy);
-  return ShadowBase;
+  LocalDynamicShadow = IRB.CreateIntToPtr(LocalDynamicShadow, Int8PtrTy);
 }
 
 bool HWAddressSanitizer::instrumentLandingPads(
     SmallVectorImpl<Instruction *> &LandingPadVec) {
   Module *M = LandingPadVec[0]->getModule();
   Function *ReadRegister =
       Intrinsic::getDeclaration(M, Intrinsic::read_register, IntptrTy);
   const char *RegName =
bool HWAddressSanitizer::sanitizeFunction(Function &F) {
   if (ClCreateFrameDescriptions && !AllocasToInstrument.empty())
     createFrameGlobal(F, createFrameString(AllocasToInstrument));
 
 
   assert(!LocalDynamicShadow);
 
   Instruction *InsertPt = &*F.getEntryBlock().begin();
   IRBuilder<> EntryIRB(InsertPt);
-  LocalDynamicShadow = emitPrologue(EntryIRB,
-                                    /*WithFrameRecord*/ ClRecordStackHistory &&
-                                        !AllocasToInstrument.empty());
+  emitPrologue(EntryIRB,
 
   bool Changed = false;
   if (!AllocasToInstrument.empty()) {
     Value *StackTag =
         ClGenerateTagsWithCalls ? nullptr : getStackBaseTag(EntryIRB);
     Changed |= instrumentStack(AllocasToInstrument, AllocaDeclareMap, RetVec,
                                StackTag);
   }
for (auto II = EntryIRB.GetInsertBlock()->begin(),
           I->moveBefore(InsertPt);
     }
   }
 
   for (auto Inst : ToInstrument)
     Changed |= instrumentMemAccess(Inst);
 
   LocalDynamicShadow = nullptr;
+  StackBaseTag = nullptr;
 
   return Changed;
 }
 
 void HWAddressSanitizer::ShadowMapping::init(Triple &TargetTriple) {
   Scale = kDefaultShadowScale;
   if (ClMappingOffset.getNumOccurrences() > 0) {
     InGlobal = false;

llvm/trunk/test/Instrumentation/HWAddressSanitizer/dbg-declare-tag-offset.ll

 ; RUN: opt -hwasan -S -o - %s | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-android"
 
 declare void @g(i8**, i8**, i8**, i8**, i8**, i8**)
 
 define void @f() sanitize_hwaddress !dbg !6 {
 entry:
   %nodebug0 = alloca i8*
   %nodebug1 = alloca i8*
   %nodebug2 = alloca i8*
   %nodebug3 = alloca i8*
   %a = alloca i8*
   %b = alloca i8*
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 4)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 32)
   call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 4)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 32)
   call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 6)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 96)
   call void @llvm.dbg.declare(metadata i8** %b, metadata !13, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 6)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 96)
   call void @llvm.dbg.declare(metadata i8** %b, metadata !13, metadata !DIExpression()), !dbg !14
   call void @g(i8** %nodebug0, i8** %nodebug1, i8** %nodebug2, i8** %nodebug3, i8** %a, i8** %b)
   ret void, !dbg !15
 }
 
 declare void @llvm.dbg.declare(metadata, metadata, metadata)
 
 !llvm.dbg.cu = !{!0}

llvm/trunk/test/Instrumentation/HWAddressSanitizer/prologue.ll

 ; CHECK-IFUNC:   getelementptr i8, i8* %[[A]]
 
 ; CHECK-GLOBAL: load i8*, i8** @__hwasan_shadow_memory_dynamic_address
 
 ; CHECK-TLS:   %[[A:[^ ]*]] = call i8* @llvm.thread.pointer()
 ; CHECK-TLS:   %[[B:[^ ]*]] = getelementptr i8, i8* %[[A]], i32 48
 ; CHECK-TLS:   %[[C:[^ ]*]] = bitcast i8* %[[B]] to i64*
 ; CHECK-TLS:   %[[D:[^ ]*]] = load i64, i64* %[[C]]
+; CHECK-TLS:   %[[E:[^ ]*]] = ashr i64 %[[D]], 3
 
 ; CHECK-NOHISTORY-NOT: store i64
 
 ; CHECK-HISTORY: %[[PTR:[^ ]*]] = inttoptr i64 %[[D]] to i64*
 ; CHECK-HISTORY: store i64 %{{.*}}, i64* %[[PTR]]
 ; CHECK-HISTORY: %[[D1:[^ ]*]] = ashr i64 %[[D]], 56
 ; CHECK-HISTORY: %[[D2:[^ ]*]] = shl nuw nsw i64 %[[D1]], 12
 ; CHECK-HISTORY: %[[D3:[^ ]*]] = xor i64 %[[D2]], -1
 ; CHECK-HISTORY: %[[D4:[^ ]*]] = add i64 %[[D]], 8
 ; CHECK-HISTORY: %[[D5:[^ ]*]] = and i64 %[[D4]], %[[D3]]
 ; CHECK-HISTORY: store i64 %[[D5]], i64* %[[C]]
 
-; CHECK-TLS:   %[[E:[^ ]*]] = or i64 %[[D]], 4294967295
-; CHECK-TLS:   = add i64 %[[E]], 1
+; CHECK-TLS:   %[[F:[^ ]*]] = or i64 %[[D]], 4294967295
+; CHECK-TLS:   = add i64 %[[F]], 1
+
+; CHECK-HISTORY: = xor i64 %[[E]], 0
 
 ; CHECK-NOHISTORY-NOT: store i64
 
 
 entry:
   %x = alloca i32, align 4
   call void @use(i32* %x)
   ret void
 }