[StackProtector] Catch direct out-of-bounds when checking address-takenness

[john.brawn]

Summary

With -fstack-protector-strong we check if a non-array variable has its address taken in a way that could cause a potential out-of-bounds access. However what we don't catch is when the address is directly used to create an out-of-bounds memory access.

Fix this by examining the offsets of GEPs that are ultimately derived from allocas and checking if the resulting address is out-of-bounds, and by checking that any memory operations using such addresses are not over-large.

Fixes PR43478.

[efriedma]

llvm/lib/CodeGen/StackProtector.cpp

202

I think AllocaInst has a getAllocatedType, or something like that?

Should use getTypeAllocSize, since that's what actually determines the number of bytes allocated.

[john.brawn]

llvm/lib/CodeGen/StackProtector.cpp

202

I think AllocaInst has a getAllocatedType, or something like that?

AI isn't necessarily an AllocaInst, e.g. we could be looking at a GEP of a GEP or a GEP of a PHI.

Should use getTypeAllocSize, since that's what actually determines the number of bytes allocated.

Will do.

[john.brawn]

Use getTypeAllocSize, apply clang-format.

[probinson]

I have to admit I didn't thoroughly look at the test, although I have to wonder if the loop cases in the test really provide any additional coverage? They're using phis as input, but you already have phi cases.

llvm/lib/CodeGen/StackProtector.cpp

194

potentially out-of-bounds

195

s/would also have to be/could also be/

llvm/test/CodeGen/Generic/stack-guard-oob.ll

7

REQUIRES: aarch64-registered-target
REQUIRES: arm-registered-target
REQUIRES: x86-registered-target

8

When CHECK-LABEL specifies an actual label, it's best to include the appropriate punctuation; so, CHECK-LABEL: in_bounds: and so on throughout.

[john.brawn]

llvm/test/CodeGen/Generic/stack-guard-oob.ll

7

I think it makes more sense instead to split this into three separate tests (which just use the same input file in test/Codegen/Inputs, like we do with stack-guard-reassign.ll), so we don't need to requiring all targets if we want to test any of them.

[john.brawn]

Update based on review comments.

[probinson]

Changes look good, but there's still the question about whether you really need the loop tests.

[john.brawn]

In D75695#1912905, @probinson wrote:

Changes look good, but there's still the question about whether you really need the loop tests.

I think I originally added these because of a previous attempt at a fix, which was more complicated (in a way that didn't improve anything) and did at one point have a problem with loops. I could remove them, though I don't see much reason to. I will if you really want though.

[probinson]

In D75695#1914314, @john.brawn wrote:

In D75695#1912905, @probinson wrote:

Changes look good, but there's still the question about whether you really need the loop tests.

I think I originally added these because of a previous attempt at a fix, which was more complicated (in a way that didn't improve anything) and did at one point have a problem with loops. I could remove them, though I don't see much reason to. I will if you really want though.

Project practice is to try to have regression tests that are fairly focused, and don't contain any extraneous or redundant cases. This helps future devs trying to read and understand your test. It also reduces testing time by an admittedly small increment, but when you add up those increments across 10s of Ks of tests and N-hundred developers running them many many times per day, it adds up.
There's a place for more thorough testing, IMO, but that place is not the lit tests.

[john.brawn]

Removed loop tests.

[efriedma]

llvm/lib/CodeGen/StackProtector.cpp

202

Oh, I see, the function recurses.

I don't think the recursion works correctly in general. The values that actually matter are the current offset, determined recursively, the size of the original alloca, and the size of any memory operations using the result of the GEP. Using the size of the GEP's operand type doesn't work correctly in general; in particular, if there's another GEP or bitcast in the recursive chain of uses, you can come up with the wrong result.

[john.brawn]

llvm/lib/CodeGen/StackProtector.cpp

202

I think adding a check that bitcast doesn't bitcast to a larger type should be enough to handle this. If we have a GEP of a GEP then each one will make sure that the offset is within the bounds of the specific type it's handling. Doing it like this does mean that for something like

int fn() {
  int arr[4][4];
  return arr[0][5];
}

we say it's an out-of-bounds access when it doesn't actually access outside of the underlying object, but I don't think handling this kind of case is worth the added complexity.

[john.brawn]

Added bitcast handling.

[arsenm]

llvm/lib/CodeGen/StackProtector.cpp

211–212

This is introducing new dependences on the deprecated pointee type. No decisions should be made based on this

[john.brawn]

llvm/lib/CodeGen/StackProtector.cpp

211–212

I don't see anything in Type.h about getPointerElementType being deprecated, but looking at Instructions.h I see mention of "opaque pointer types", is this what you're talking about? Looking at http://lists.llvm.org/pipermail/llvm-dev/2019-December/137684.html (which is the best I could find for what it means) it looks like instead of

%var = alloca i32, align 4
%bitcast = i32* %var to %i64
store i64 0, i32* %bitcast

we'll have

%var = alloca i32, align 4
store i64 0, p0 %var

So it looks like I should be checking the type at the load/store instead?

[arsenm]

llvm/lib/CodeGen/StackProtector.cpp

211–212

Yes, pointer types should be assumed to be opaque now. Only the type on the use instruction is meaningful

[efriedma]

llvm/lib/CodeGen/StackProtector.cpp

202

That's still not enough given the way you're doing the check. Consider if someone writes something like

struct X { int a[10][10]; int b; };
struct X x;
int (*p)[10] = &x.a[10];
int z = a[5];

This lowers to two GEPs; neither is "out-of-bounds" in the sense you're checking.

You could try to enforce that each index of each GEP is in the valid range, I guess.

[john.brawn]

Adjusted to avoid looking through pointer types by passing around the allocated type and checking it against the size of memory accesses. Also correctly handle GEPs where the addressed member is partially outside of the allocated object.

[efriedma]

I think it would be more straightforward to reason about the behavior here if you just pass down the number of bytes that are known safe to dereference, instead of "AllocType".

[john.brawn]

Use the allocation size instead of the allocation type.

[efriedma]

llvm/lib/CodeGen/StackProtector.cpp

201

Can we just compute ResultSize as "AllocSize - Offset"? (That's obviously correct, and I'm not convinced that using the size of getResultElementType() does the right thing here.)

[john.brawn]

llvm/lib/CodeGen/StackProtector.cpp

201

I think we can. Currently the offset check is done in a way that also checks if the end of the addressed member is past the end of the allocation, but just checking that the start is within the allocation and then reducing the remaining size by the offset will mean we check at the time we see a memory access that it's not too large for the remaining space.

[john.brawn]

Adjust GEP handling to reduce AllocSize by Offset instead of using the result size.

[efriedma]

I don't think we're really getting much benefit out of testing this on multiple targets; as long as we have coverage for 32-bit and 64-bit targets, none of the relevant logic is actually target-specific. So I'd just get rid of the ARM/AArch64 tests, I think, since x86 conveniently has 32-bit and 64-bit targets.

Otherwise LGTM

llvm/lib/CodeGen/StackProtector.cpp

case Instruction::Call: {
       // TODO: Narrow this to intrinsics that have store-like effects.
       const auto *CI = cast<CallInst>(I);
       if (!isa<DbgInfoIntrinsic>(CI) && !CI->isLifetimeStartOrEnd())
         return true;
       break;
     }
     case Instruction::Invoke:
       return true;
+    case Instruction::GetElementPtr: {
+      // If the GEP offset is out-of-bounds, or is non-constant and so has to be
+      // assumed to be out-of-bounds, then any memory access that would use it
+      // would also have to be out-of-bounds meaning stack protection is
+      // required.
+      const GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
+      const DataLayout &DL = M->getDataLayout();
+      unsigned TypeSize = DL.getIndexTypeSizeInBits(I->getType());
+      APInt Offset(TypeSize, 0);
+      APInt MaxOffset(TypeSize, DL.getTypeStoreSize(
+                        AI->getType()->getPointerElementType()));
+      if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.uge(MaxOffset))
+        return true;
+    }
+      LLVM_FALLTHROUGH;
     case Instruction::BitCast:
-    case Instruction::GetElementPtr:
     case Instruction::Select:
     case Instruction::AddrSpaceCast:
       if (HasAddressTaken(I))
         return true;
       break;
     case Instruction::PHI: {
       // Keep track of what PHI nodes we have already visited to ensure
       // they are only visited once.
       const auto *PN = cast<PHINode>(I);
       if (VisitedPHIs.insert(PN).second)
         if (HasAddressTaken(PN))
           return true;
       break;

llvm/test/CodeGen/Generic/stack-guard-oob.ll

+; RUN: llc -mtriple=aarch64 -O0 < %s | FileCheck %s
+; RUN: llc -mtriple=armv7a -O0 < %s | FileCheck %s
+; RUN: llc -mtriple=thumbv7m -O0 < %s | FileCheck %s
+; RUN: llc -mtriple=i686 -O0 < %s | FileCheck %s
+; RUN: llc -mtriple=x86_64 -O0 < %s | FileCheck %s
+
+; CHECK-LABEL: in_bounds
+; CHECK-NOT: __stack_chk_guard
+define i32 @in_bounds() #0 {
+  %var = alloca i32, align 4
+  store i32 0, i32* %var, align 4
+  %gep = getelementptr inbounds i32, i32* %var, i32 0
+  %ret = load i32, i32* %gep, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: constant_out_of_bounds
+; CHECK: __stack_chk_guard
+define i32 @constant_out_of_bounds() #0 {
+  %var = alloca i32, align 4
+  store i32 0, i32* %var, align 4
+  %gep = getelementptr inbounds i32, i32* %var, i32 1
+  %ret = load i32, i32* %gep, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: nonconstant_out_of_bounds
+; CHECK: __stack_chk_guard
+define i32 @nonconstant_out_of_bounds(i32 %n) #0 {
+  %var = alloca i32, align 4
+  store i32 0, i32* %var, align 4
+  %gep = getelementptr inbounds i32, i32* %var, i32 %n
+  %ret = load i32, i32* %gep, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_before_gep_in_bounds
+; CHECK-NOT: __stack_chk_guard
+define i32 @phi_before_gep_in_bounds(i32 %k) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %then
+
+if:
+  br label %then
+
+then:
+  %ptr = phi i32* [ %var1, %entry ], [ %var2, %if ]
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 0
+  %ret = load i32, i32* %gep, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_before_gep_constant_out_of_bounds
+; CHECK: __stack_chk_guard
+define i32 @phi_before_gep_constant_out_of_bounds(i32 %k) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %then
+
+if:
+  br label %then
+
+then:
+  %ptr = phi i32* [ %var1, %entry ], [ %var2, %if ]
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 1
+  %ret = load i32, i32* %gep, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_before_gep_nonconstant_out_of_bounds
+; CHECK: __stack_chk_guard
+define i32 @phi_before_gep_nonconstant_out_of_bounds(i32 %k, i32 %n) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %then
+
+if:
+  br label %then
+
+then:
+  %ptr = phi i32* [ %var1, %entry ], [ %var2, %if ]
+  %gep = getelementptr inbounds i32, i32* %ptr, i32 %n
+  %ret = load i32, i32* %gep, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_after_gep_in_bounds
+; CHECK-NOT: __stack_chk_guard
+define i32 @phi_after_gep_in_bounds(i32 %k) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %else
+
+if:
+  %gep1 = getelementptr inbounds i32, i32* %var1, i32 0
+  br label %then
+
+else:
+  %gep2 = getelementptr inbounds i32, i32* %var2, i32 0
+  br label %then
+
+then:
+  %ptr = phi i32* [ %gep1, %if ], [ %gep2, %else ]
+  %ret = load i32, i32* %ptr, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_after_gep_constant_out_of_bounds_a
+; CHECK: __stack_chk_guard
+define i32 @phi_after_gep_constant_out_of_bounds_a(i32 %k) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %else
+
+if:
+  %gep1 = getelementptr inbounds i32, i32* %var1, i32 0
+  br label %then
+
+else:
+  %gep2 = getelementptr inbounds i32, i32* %var2, i32 1
+  br label %then
+
+then:
+  %ptr = phi i32* [ %gep1, %if ], [ %gep2, %else ]
+  %ret = load i32, i32* %ptr, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_after_gep_constant_out_of_bounds_b
+; CHECK: __stack_chk_guard
+define i32 @phi_after_gep_constant_out_of_bounds_b(i32 %k) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %else
+
+if:
+  %gep1 = getelementptr inbounds i32, i32* %var1, i32 1
+  br label %then
+
+else:
+  %gep2 = getelementptr inbounds i32, i32* %var2, i32 0
+  br label %then
+
+then:
+  %ptr = phi i32* [ %gep1, %if ], [ %gep2, %else ]
+  %ret = load i32, i32* %ptr, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_after_gep_nonconstant_out_of_bounds_a
+; CHECK: __stack_chk_guard
+define i32 @phi_after_gep_nonconstant_out_of_bounds_a(i32 %k, i32 %n) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %else
+
+if:
+  %gep1 = getelementptr inbounds i32, i32* %var1, i32 0
+  br label %then
+
+else:
+  %gep2 = getelementptr inbounds i32, i32* %var2, i32 %n
+  br label %then
+
+then:
+  %ptr = phi i32* [ %gep1, %if ], [ %gep2, %else ]
+  %ret = load i32, i32* %ptr, align 4
+  ret i32 %ret
+}
+
+; CHECK-LABEL: phi_after_gep_nonconstant_out_of_bounds_b
+; CHECK: __stack_chk_guard
+define i32 @phi_after_gep_nonconstant_out_of_bounds_b(i32 %k, i32 %n) #0 {
+entry:
+  %var1 = alloca i32, align 4
+  %var2 = alloca i32, align 4
+  store i32 0, i32* %var1, align 4
+  store i32 0, i32* %var2, align 4
+  %cmp = icmp ne i32 %k, 0
+  br i1 %cmp, label %if, label %else
+
+if:
+  %gep1 = getelementptr inbounds i32, i32* %var1, i32 %n
+  br label %then
+
+else:
+  %gep2 = getelementptr inbounds i32, i32* %var2, i32 0
+  br label %then
+
+then:
+  %ptr = phi i32* [ %gep1, %if ], [ %gep2, %else ]
+  %ret = load i32, i32* %ptr, align 4
+  ret i32 %ret
+}
+
+%struct.outer = type { %struct.inner, %struct.inner }
+%struct.inner = type { i32, i32 }
+
+; CHECK-LABEL: struct_in_bounds
+; CHECK-NOT: __stack_chk_guard
+define void @struct_in_bounds() #0 {
+  %var = alloca %struct.outer, align 4
+  %outergep = getelementptr inbounds %struct.outer, %struct.outer* %var, i32 0, i32 1
+  %innergep = getelementptr inbounds %struct.inner, %struct.inner* %outergep, i32 0, i32 1
+  store i32 0, i32* %innergep, align 4
+  ret void
+}
+
+; CHECK-LABEL: struct_constant_out_of_bounds_a
+; CHECK: __stack_chk_guard
+define void @struct_constant_out_of_bounds_a() #0 {
+  %var = alloca %struct.outer, align 4
+  %outergep = getelementptr inbounds %struct.outer, %struct.outer* %var, i32 1, i32 0
+  %innergep = getelementptr inbounds %struct.inner, %struct.inner* %outergep, i32 0, i32 0
+  store i32 0, i32* %innergep, align 4
+  ret void
+}
+
+; CHECK-LABEL: struct_constant_out_of_bounds_b
+; CHECK: __stack_chk_guard
+define void @struct_constant_out_of_bounds_b() #0 {
+  %var = alloca %struct.outer, align 4
+  %outergep = getelementptr inbounds %struct.outer, %struct.outer* %var, i32 0, i32 0
+  %innergep = getelementptr inbounds %struct.inner, %struct.inner* %outergep, i32 1, i32 0
+  store i32 0, i32* %innergep, align 4
+  ret void
+}
+
+; CHECK-LABEL: struct_nonconstant_out_of_bounds_a
+; CHECK: __stack_chk_guard
+define void @struct_nonconstant_out_of_bounds_a(i32 %n) #0 {
+  %var = alloca %struct.outer, align 4
+  %outergep = getelementptr inbounds %struct.outer, %struct.outer* %var, i32 %n, i32 0
+  %innergep = getelementptr inbounds %struct.inner, %struct.inner* %outergep, i32 0, i32 0
+  store i32 0, i32* %innergep, align 4
+  ret void
+}
+
+; CHECK-LABEL: struct_nonconstant_out_of_bounds_b
+; CHECK: __stack_chk_guard
+define void @struct_nonconstant_out_of_bounds_b(i32 %n) #0 {
+  %var = alloca %struct.outer, align 4
+  %outergep = getelementptr inbounds %struct.outer, %struct.outer* %var, i32 0, i32 0
+  %innergep = getelementptr inbounds %struct.inner, %struct.inner* %outergep, i32 %n, i32 0
+  store i32 0, i32* %innergep, align 4
+  ret void
+}
+
+; CHECK-LABEL: loop_inbounds
+; CHECK-NOT: __stack_chk_guard
+define void @loop_inbounds(i32 %k) #0 {
+entry:
+  %var = alloca i32, align 4
+  br label %loop
+
+loop:
+  %idx = phi i32 [ %k, %entry ], [ %idx.next, %loop ]
+  %ptr = phi i32* [ %var, %entry ], [ %ptr.next, %loop ]
+  store i32 %idx, i32* %ptr, align 4
+  %ptr.next = getelementptr inbounds i32, i32* %ptr, i64 0
+  %idx.next = add nsw i32 %idx, -1
+  %cond = icmp eq i32 %idx.next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: loop_constant_out_of_bounds
+; CHECK: __stack_chk_guard
+define void @loop_constant_out_of_bounds(i32 %k) #0 {
+entry:
+  %var = alloca i32, align 4
+  br label %loop
+
+loop:
+  %idx = phi i32 [ %k, %entry ], [ %idx.next, %loop ]
+  %ptr = phi i32* [ %var, %entry ], [ %ptr.next, %loop ]
+  store i32 %idx, i32* %ptr, align 4
+  %ptr.next = getelementptr inbounds i32, i32* %ptr, i32 1
+  %idx.next = add nsw i32 %idx, -1
+  %cond = icmp eq i32 %idx.next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: loop_nonconstant_out_of_bounds
+; CHECK: __stack_chk_guard
+define void @loop_nonconstant_out_of_bounds(i32 %k, i32 %n) #0 {
+entry:
+  %var = alloca i32, align 4
+  br label %loop
+
+loop:
+  %idx = phi i32 [ %k, %entry ], [ %idx.next, %loop ]
+  %ptr = phi i32* [ %var, %entry ], [ %ptr.next, %loop ]
+  store i32 %idx, i32* %ptr, align 4
+  %ptr.next = getelementptr inbounds i32, i32* %ptr, i32 %n
+  %idx.next = add nsw i32 %idx, -1
+  %cond = icmp eq i32 %idx.next, 0
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+attributes #0 = { sspstrong }