[hwasan] Do not instrument accesses to uninteresting allocas.

[fmayer]

Summary

This leads to a statistically significant improvement when using -hwasan-instrument-stack=0: https://bit.ly/3AZUIKI.
When enabling stack instrumentation, the data appears gets better but not statistically significantly so. This is consistent
with the very moderate improvements I have seen for stack safety otherwise, so I expect it to improve when the underlying
issue of that is resolved.

[fmayer]

better test.

[fmayer]

ignore all alloca access if stack not instrumented

[fmayer]

better variable naming.

[fmayer]

add test

[fmayer]

allow to control strictness of alloc matching

[fmayer]

format

[fmayer]

remove comment

[fmayer]

simplify code

[eugenis]

I don't like the new flag. If we want this as a mitigation, IMHO it's a bad idea to allow overflows from stack. Even constant sized ones. Well, maybe reasonably small constant overflows are ok.

Consider adopting AddressSanitizer::isSafeAccess instead.

[eugenis]

In face, isSafeAccess seems pretty limited. Surely ScalarEvolution (similar to how it is used in StackSafetyAnalysis) can capture more cases, including a non-constant offset that can be proven to be within range?

[fmayer]

rework to address comment

[fmayer]

In D108457#2963679, @eugenis wrote:

In face, isSafeAccess seems pretty limited. Surely ScalarEvolution (similar to how it is used in StackSafetyAnalysis) can capture more cases, including a non-constant offset that can be proven to be within range?

Done. PTAL.

What I do right now is not emit any checks when we can we disable stack instrumentation and we can trace back an operation to an alloca. While we could potentially overflow towards other regions, I think it is not unexpected that we do not catch this if stack instrumentation is disabled. What do you think?

[eugenis]

This is pretty cool, I thought it would be more complicated.

This change needs comprehensive tests in llvm/test/Analysis/StackSafetyAnalysis. Update the print() method to show safe/unsafe instructions (or maybe only list known safe instruction).

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

[fmayer]

handle stores that might or might not use an alloca

[fmayer]

In D108457#2983236, @eugenis wrote:

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

Ah yes, I did handle this but then accidentally lost that when I refactored around some stuff. Put that back and added an IR test.

[fmayer]

don't use argument in select test

[fmayer]

In D108457#2984855, @fmayer wrote:

In D108457#2983236, @eugenis wrote:

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

Ah yes, I did handle this but then accidentally lost that when I refactored around some stuff. Put that back and added an IR test.

Thinking again I remembered why I removed the explicit case for this during the refactoring: in this case, SCEV will not be able to calculate an in-range offset between the operant of the store and the alloca, so it will not be judged a safe access

[fmayer]

add tests for stack safety analysis

[fmayer]

format

[fmayer]

EDIT: I ran pdfium benchmarks and had some results here, but I spoke too early and need to run some more.

[eugenis]

@vitalybuka

Ideas for more analysis tests:

• unsafe alloca with a mix of safe and unsafe accesses
• memcpy that is safe on one side and unsafe on the other. Either between two allocas, or within the same (memmove?). Or between alloca and non-stack memory.

In D108457#2985198, @fmayer wrote:

In D108457#2984855, @fmayer wrote:

In D108457#2983236, @eugenis wrote:

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

Ah yes, I did handle this but then accidentally lost that when I refactored around some stuff. Put that back and added an IR test.

Thinking again I remembered why I removed the explicit case for this during the refactoring: in this case, SCEV will not be able to calculate an in-range offset between the operant of the store and the alloca, so it will not be judged a safe access

Right, of course. Any reachable instruction we would require to be *always* within the alloca range.

llvm/lib/Analysis/StackSafetyAnalysis.cpp

836 ↗

(On Diff #370961)

This affect compilation time and memory. Ideally we would not do it if the client can not use this info (ex. MTE).

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

778

if (findAllocaForValue(Ptr)) return true;

[fmayer]

address comment

[fmayer]

remove unnecessary check

[fmayer]

only calculate address information when needed.

[fmayer]

revert unneeded change

[fmayer]

clang format

[eugenis]

still missing test cases for combinations of mixed safe/unsafe accesses

llvm/include/llvm/Analysis/StackSafetyAnalysis.h

69 ↗

(On Diff #371382)

you want either DenseMap or SmallPtrSet here. std::map is unnecessarily ordered, logarithmic, and wastes memory

[vitalybuka]

llvm/include/llvm/Analysis/StackSafetyAnalysis.h

67 ↗

(On Diff #371382)

why do we need bool if missing instruction is equivalent to false?
std::set?

67 ↗

(On Diff #371382)

just std::map<const Instruction *, bool>Accesses;

InfoTy in unique_ptr to avoid exposing it into the header.

69 ↗

(On Diff #371382)

std set/map seems fine
class is movable, DenseMap or SmallPtrSet don't support efficient move.

69 ↗

(On Diff #371382)

I don't see value in ::getAccesses when accessIsSafe can access the field.

llvm/lib/Analysis/StackSafetyAnalysis.cpp

136–139 ↗

(On Diff #371382)

Less boilerplate this way:
auto Ins = Accesses.emplace(I, R);
Then use Ins.first and Ins.second where needed.

141–143 ↗

(On Diff #371382)

the point of <it, bool> result that you can update if insert failed and avoid the second lookup

455 ↗

(On Diff #371382)

may I ask you to extract two NFC patches which you can land without review:

1. break -> return !US.Range.isFullSet(); I assume no tests need updates.
2. Wrap updateRange into trivial:

void addRange(I, R) {
   // the rest you will add in D108457
   updateRange(R);
 }

I assume also not tests should be affected.

813 ↗

(On Diff #371382)

this is a separate NFC patch

826 ↗

(On Diff #371382)

so we lazily construct this on the request
if so I am pretty sure we can have sorted std::vector<Instruction*> Accesses for free;
and accessIsSafe can use std::binary_search and it will be faster then map/set lookups.

836 ↗

(On Diff #370961)

I am a little bit skeptical that we can measure a difference. I'd rather keep it simple.

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

283

HWAsan and related tests should be in a separate patch

[fmayer]

split change

[fmayer]

I split the stack safety change to D109503 and added more tests to that.

llvm/include/llvm/Analysis/StackSafetyAnalysis.h

67 ↗

(On Diff #371382)

While I build this up, there are two cases:

the instruction hadn't been considered yet
the instruction was considered but wasn't safe.
This allows to conveniently keep them apart.

67 ↗

(On Diff #371382)

I reverted to calculating this in getInfo and putting it into the InfoTy.

@eugenis is that okay?

llvm/lib/Analysis/StackSafetyAnalysis.cpp

141–143 ↗

(On Diff #371382)

That doesn't work, because it's not move constructible (I think, I don't fully remember what exactly it complained about when I did that).

455 ↗

(On Diff #371382)

Actually no one looks at the return value, so I just made it void.

836 ↗

(On Diff #370961)

I reverted it to what it was before for simplicity. We can change it again later if it becomes a problem.

[fmayer]

remove unnecessary check (again)

[fmayer]

style

[eugenis]

LGTM

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

777

I'm still on the fence about this. A stack pointer can be used to access heap if the offset is attacker controlled, but that sounds a bit exotic.

But let's land it like this for now.

One thing I'd like to explore is applying the same SCEV computation as in StackSafetyAnalysis and excluding instrumentation for anything with offset provably within 32 bits or less - that should be reasonably common (indices are often int, not long) and safe (heap is unlikely to be within 4Gb from stack on 64-bit).

[fmayer]

rebase

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

public:
 
   void untagPointerOperand(Instruction *I, Value *Addr);
   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
   void instrumentMemAccessInline(Value *Ptr, bool IsWrite,
                                  unsigned AccessSizeIndex,
                                  Instruction *InsertBefore);
   void instrumentMemIntrinsic(MemIntrinsic *MI);
   bool instrumentMemAccess(InterestingMemoryOperand &O);
   bool ignoreAccess(Value *Ptr);
   void getInterestingMemoryOperands(
       Instruction *I, SmallVectorImpl<InterestingMemoryOperand> &Interesting);
 
   bool isInterestingAlloca(const AllocaInst &AI);
   void tagAlloca(IRBuilder<> &IRB, AllocaInst *AI, Value *Tag, size_t Size);
   Value *tagPointer(IRBuilder<> &IRB, Type *Ty, Value *PtrLong, Value *Tag);
   Value *untagPointer(IRBuilder<> &IRB, Value *PtrLong);
   bool instrumentStack(
bool HWAddressSanitizer::ignoreAccess(Value *Ptr) {
 
   // Ignore swifterror addresses.
   // swifterror memory addresses are mem2reg promoted by instruction
   // selection. As such they cannot have regular uses like an instrumentation
   // function and it makes no sense to track them as memory.
   if (Ptr->isSwiftError())
     return true;
 
+  auto *MaybeAlloca = findAllocaForValue(Ptr);
+  if (MaybeAlloca && !isInterestingAlloca(*MaybeAlloca))
+    return true;
   return false;
 }
 
 void HWAddressSanitizer::getInterestingMemoryOperands(
     Instruction *I, SmallVectorImpl<InterestingMemoryOperand> &Interesting) {
   // Skip memory accesses inserted by another instrumentation.
   if (I->hasMetadata("nosanitize"))
     return;

llvm/test/Instrumentation/HWAddressSanitizer/stack-safety-analysis.ll

-; RUN: opt -hwasan -hwasan-use-stack-safety=1 -hwasan-generate-tags-with-calls -S < %s | FileCheck %s --check-prefixes=SAFETY
-; RUN: opt -hwasan -hwasan-use-stack-safety=0 -hwasan-generate-tags-with-calls -S < %s | FileCheck %s --check-prefixes=NOSAFETY
-; RUN: opt -hwasan -hwasan-generate-tags-with-calls -S < %s | FileCheck %s --check-prefixes=SAFETY
+; RUN: opt -hwasan -hwasan-instrument-with-calls -hwasan-use-stack-safety=1 -hwasan-generate-tags-with-calls -S < %s | FileCheck %s --check-prefixes=SAFETY
+; RUN: opt -hwasan -hwasan-instrument-with-calls -hwasan-use-stack-safety=0 -hwasan-generate-tags-with-calls -S < %s | FileCheck %s --check-prefixes=NOSAFETY
+; RUN: opt -hwasan -hwasan-instrument-with-calls -hwasan-generate-tags-with-calls -S < %s | FileCheck %s --check-prefixes=SAFETY
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-gnu"
 
 ; Check a safe alloca to ensure it does not get a tag.
 define i32 @test_load(i32* %a) sanitize_hwaddress {
 entry:
   ; NOSAFETY: call {{.*}}__hwasan_generate_tag
+  ; NOSAFETY: call {{.*}}__hwasan_store
   ; SAFETY-NOT: call {{.*}}__hwasan_generate_tag
+  ; SAFETY-NOT: call {{.*}}__hwasan_store
   %buf.sroa.0 = alloca i8, align 4
   call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull %buf.sroa.0)
   store volatile i8 0, i8* %buf.sroa.0, align 4, !tbaa !8
   call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull %buf.sroa.0)
   ret i32 0
 }
 
 ; Check a non-safe alloca to ensure it gets a tag.
 define i32 @test_use(i32* %a) sanitize_hwaddress {
 entry:
   ; NOSAFETY: call {{.*}}__hwasan_generate_tag
+  ; NOSAFETY: call {{.*}}__hwasan_store
   ; SAFETY: call {{.*}}__hwasan_generate_tag
+  ; SAFETY: call {{.*}}__hwasan_store
   %buf.sroa.0 = alloca i8, align 4
   call void @use(i8* nonnull %buf.sroa.0)
   call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull %buf.sroa.0)
   store volatile i8 0, i8* %buf.sroa.0, align 4, !tbaa !8
   call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull %buf.sroa.0)
   ret i32 0
 }