[ubsan] Teach the pointer overflow check that "p - <unsigned> <= p" (PR33430)

[vsk]

Summary

The pointer overflow check gives false negatives when dealing with
expressions in which an unsigned value is subtracted from a pointer.
This is summarized in PR33430 [1]: ubsan permits the result of the
subtraction to be greater than "p", but it should not.

To fix the issue, we should track whether or not the pointer expression
is a subtraction. If it is, and the indices are unsigned, we know to
expect "p - <unsigned> <= p".

I've tested this by running check-{llvm,clang} with a stage2 ubsan-enabled build. I've also added some tests to compiler-rt, which I'll upload in a separate patch.

[1] https://bugs.llvm.org/show_bug.cgi?id=33430

[efriedma]

Looks okay, but I haven't been reviewing this series of patches closely, so I could be missing something.

lib/CodeGen/CGExprScalar.cpp

3974 ↗

(On Diff #102250)

Please make this an "else" rather than an "else if" (you can assert the inside the else body if it's helpful).

[vsk]

Thanks for the review! I'll wait for another 'lgtm'.

[dtzWill]

Don't mean to block this, but just FYI I won't be able to look into this carefully until later this week (sorry!).

Kicked off a rebuild using these patches just now, though! O:)

[vsk]

In D34121#779347, @dtzWill wrote:

Don't mean to block this, but just FYI I won't be able to look into this carefully until later this week (sorry!).

Kicked off a rebuild using these patches just now, though! O:)

No problem, thanks for taking a look.

[aprantl]

lib/CodeGen/CGExpr.cpp

3010 ↗

(On Diff #102261)

Might want to define an

enum { NotSubtraction = false, IsSubtraction = true } in the header. We do this in other places.

[vsk]

Address Adrian's comment about using an enum to simplify some calls.

[vsk]

Fix a typo introduced in emitArraySubscriptGEP while refactoring /*isSubtraction=false*/ to CodeGenFunction::NotSubtraction, and add CHECK lines which catch the issue.

[vsk]

@dtzWill do you have any further comments on this one?

I'd like to get another 'lgtm' before committing, and it'd be nice to get this in before llvm 5.0 branches (7/19).

FWIW we've been living on this for a few weeks internally without any issues:
https://github.com/apple/swift-clang/commit/3ebe7d87b9d545aebdd80452d0b79695ff871bce

[dtzWill]

In D34121#806978, @vsk wrote:

@dtzWill do you have any further comments on this one?

I'd like to get another 'lgtm' before committing, and it'd be nice to get this in before llvm 5.0 branches (7/19).

FWIW we've been living on this for a few weeks internally without any issues:
https://github.com/apple/swift-clang/commit/3ebe7d87b9d545aebdd80452d0b79695ff871bce

@vsk sorry for the delay. Looks solid to me, seems to work well in my testing.

Unrelated to the suitability of the patch itself, but on the subject:
Interestingly there don''t seem to be any changes in observed errors, which on one hand is great (yay no breakage and earlier results were mostly correct) but on the other isn't what I expected.
Does this match your experiences?

[vsk]

In D34121#808486, @dtzWill wrote:

In D34121#806978, @vsk wrote:

@dtzWill do you have any further comments on this one?

I'd like to get another 'lgtm' before committing, and it'd be nice to get this in before llvm 5.0 branches (7/19).

FWIW we've been living on this for a few weeks internally without any issues:
https://github.com/apple/swift-clang/commit/3ebe7d87b9d545aebdd80452d0b79695ff871bce

@vsk sorry for the delay. Looks solid to me, seems to work well in my testing.

Unrelated to the suitability of the patch itself, but on the subject:
Interestingly there don''t seem to be any changes in observed errors, which on one hand is great (yay no breakage and earlier results were mostly correct) but on the other isn't what I expected.
Does this match your experiences?

Thanks for testing the patch out! Your results match my experiences with some Apple frameworks. The 'p - unsigned > p' case seems to be relatively uncommon.

cfe/trunk/lib/CodeGen/CGExpr.cpp

 static llvm::Value *emitArraySubscriptGEP(CodeGenFunction &CGF,
                                           llvm::Value *ptr,
                                           ArrayRef<llvm::Value*> indices,
                                           bool inbounds,
                                           bool signedIndices,
                                           SourceLocation loc,
                                     const llvm::Twine &name = "arrayidx") {
   if (inbounds) {
-    return CGF.EmitCheckedInBoundsGEP(ptr, indices, signedIndices, loc, name);
+    return CGF.EmitCheckedInBoundsGEP(ptr, indices, signedIndices,
+                                      CodeGenFunction::NotSubtraction, loc,
+                                      name);
   } else {
     return CGF.Builder.CreateGEP(ptr, indices, name);
   }
 }
 
 static CharUnits getArrayElementAlign(CharUnits arrayAlign,
                                       llvm::Value *idx,
                                       CharUnits eltSize) {

cfe/trunk/lib/CodeGen/CGExprScalar.cpp

ScalarExprEmitter::EmitScalarPrePostIncDec(const UnaryOperator *E, LValue LV,
                                            bool isInc, bool isPre) {
 
   QualType type = E->getSubExpr()->getType();
   llvm::PHINode *atomicPHI = nullptr;
   llvm::Value *value;
   llvm::Value *input;
 
   int amount = (isInc ? 1 : -1);
-  bool signedIndex = !isInc;
+  bool isSubtraction = !isInc;
 
   if (const AtomicType *atomicTy = type->getAs<AtomicType>()) {
     type = atomicTy->getValueType();
     if (isInc && type->isBooleanType()) {
       llvm::Value *True = CGF.EmitToMemory(Builder.getTrue(), type);
       if (isPre) {
         Builder.CreateStore(True, LV.getAddress(), LV.isVolatileQualified())
           ->setAtomic(llvm::AtomicOrdering::SequentiallyConsistent);
// Next most common: pointer increment.
     // VLA types don't have constant size.
     if (const VariableArrayType *vla
           = CGF.getContext().getAsVariableArrayType(type)) {
       llvm::Value *numElts = CGF.getVLASize(vla).first;
       if (!isInc) numElts = Builder.CreateNSWNeg(numElts, "vla.negsize");
       if (CGF.getLangOpts().isSignedOverflowDefined())
         value = Builder.CreateGEP(value, numElts, "vla.inc");
       else
-        value = CGF.EmitCheckedInBoundsGEP(value, numElts, signedIndex,
-                                           E->getExprLoc(), "vla.inc");
+        value = CGF.EmitCheckedInBoundsGEP(
+            value, numElts, /*SignedIndices=*/false, isSubtraction,
 
     // Arithmetic on function pointers (!) is just +-1.
     } else if (type->isFunctionType()) {
       llvm::Value *amt = Builder.getInt32(amount);
 
       value = CGF.EmitCastToVoidPtr(value);
       if (CGF.getLangOpts().isSignedOverflowDefined())
         value = Builder.CreateGEP(value, amt, "incdec.funcptr");
       else
-        value = CGF.EmitCheckedInBoundsGEP(value, amt, signedIndex,
-                                           E->getExprLoc(), "incdec.funcptr");
+        value = CGF.EmitCheckedInBoundsGEP(value, amt, /*SignedIndices=*/false,
+                                           isSubtraction, E->getExprLoc(),
+                                           "incdec.funcptr");
       value = Builder.CreateBitCast(value, input->getType());
 
     // For everything else, we can just do a simple increment.
     } else {
       llvm::Value *amt = Builder.getInt32(amount);
       if (CGF.getLangOpts().isSignedOverflowDefined())
         value = Builder.CreateGEP(value, amt, "incdec.ptr");
       else
-        value = CGF.EmitCheckedInBoundsGEP(value, amt, signedIndex,
-                                           E->getExprLoc(), "incdec.ptr");
+        value = CGF.EmitCheckedInBoundsGEP(value, amt, /*SignedIndices=*/false,
+                                           isSubtraction, E->getExprLoc(),
+                                           "incdec.ptr");
     }
 
   // Vector increment/decrement.
   } else if (type->isVectorType()) {
     if (type->hasIntegerRepresentation()) {
       llvm::Value *amt = llvm::ConstantInt::get(value->getType(), amount);
 
       value = Builder.CreateAdd(value, amt, isInc ? "inc" : "dec");
// Objective-C pointer types.
     CharUnits size = CGF.getContext().getTypeSizeInChars(OPT->getObjectType());
     if (!isInc) size = -size;
     llvm::Value *sizeValue =
       llvm::ConstantInt::get(CGF.SizeTy, size.getQuantity());
 
     if (CGF.getLangOpts().isSignedOverflowDefined())
       value = Builder.CreateGEP(value, sizeValue, "incdec.objptr");
     else
-      value = CGF.EmitCheckedInBoundsGEP(value, sizeValue, signedIndex,
+      value = CGF.EmitCheckedInBoundsGEP(value, sizeValue,
+                                         /*SignedIndices=*/false, isSubtraction,
                                          E->getExprLoc(), "incdec.objptr");
     value = Builder.CreateBitCast(value, input->getType());
   }
 
   if (atomicPHI) {
     llvm::BasicBlock *opBB = Builder.GetInsertBlock();
     llvm::BasicBlock *contBB = CGF.createBasicBlock("atomic_cont", CGF.CurFn);
     auto Pair = CGF.EmitAtomicCompareExchange(
static Value *emitPointerArithmetic(CodeGenFunction &CGF,
 
   // In a subtraction, the LHS is always the pointer.
   if (!isSubtraction && !pointer->getType()->isPointerTy()) {
     std::swap(pointer, index);
     std::swap(pointerOperand, indexOperand);
   }
 
   bool isSigned = indexOperand->getType()->isSignedIntegerOrEnumerationType();
-  bool mayHaveNegativeGEPIndex = isSigned || isSubtraction;
 
   unsigned width = cast<llvm::IntegerType>(index->getType())->getBitWidth();
   auto &DL = CGF.CGM.getDataLayout();
   auto PtrTy = cast<llvm::PointerType>(pointer->getType());
   if (width != DL.getTypeSizeInBits(PtrTy)) {
     // Zero-extend or sign-extend the pointer value according to
     // whether the index is signed or not.
     index = CGF.Builder.CreateIntCast(index, DL.getIntPtrType(PtrTy), isSigned,
if (const VariableArrayType *vla
     // signed-overflow, so we use the same semantics for our explicit
     // multiply.  We suppress this if overflow is not undefined behavior.
     if (CGF.getLangOpts().isSignedOverflowDefined()) {
       index = CGF.Builder.CreateMul(index, numElements, "vla.index");
       pointer = CGF.Builder.CreateGEP(pointer, index, "add.ptr");
     } else {
       index = CGF.Builder.CreateNSWMul(index, numElements, "vla.index");
       pointer =
-          CGF.EmitCheckedInBoundsGEP(pointer, index, mayHaveNegativeGEPIndex,
+          CGF.EmitCheckedInBoundsGEP(pointer, index, isSigned, isSubtraction,
                                      op.E->getExprLoc(), "add.ptr");
     }
     return pointer;
   }
 
   // Explicitly handle GNU void* and function pointer arithmetic extensions. The
   // GNU void* casts amount to no-ops since our void* type is i8*, but this is
   // future proof.
   if (elementType->isVoidType() || elementType->isFunctionType()) {
     Value *result = CGF.Builder.CreateBitCast(pointer, CGF.VoidPtrTy);
     result = CGF.Builder.CreateGEP(result, index, "add.ptr");
     return CGF.Builder.CreateBitCast(result, pointer->getType());
   }
 
   if (CGF.getLangOpts().isSignedOverflowDefined())
     return CGF.Builder.CreateGEP(pointer, index, "add.ptr");
 
-  return CGF.EmitCheckedInBoundsGEP(pointer, index, mayHaveNegativeGEPIndex,
+  return CGF.EmitCheckedInBoundsGEP(pointer, index, isSigned, isSubtraction,
                                     op.E->getExprLoc(), "add.ptr");
 }
 
 // Construct an fmuladd intrinsic to represent a fused mul-add of MulOp and
 // Addend. Use negMul and negAdd to negate the first operand of the Mul or
 // the add operand respectively. This allows fmuladd to represent a*b-c, or
 // c-a*b. Patterns in LLVM should catch the negated forms and translate them to
 // efficient operations.
static Value* tryEmitFMulAdd(const BinOpInfo &op,
   }
 
   return nullptr;
 }
 
 Value *ScalarExprEmitter::EmitAdd(const BinOpInfo &op) {
   if (op.LHS->getType()->isPointerTy() ||
       op.RHS->getType()->isPointerTy())
-    return emitPointerArithmetic(CGF, op, /*subtraction*/ false);
+    return emitPointerArithmetic(CGF, op, CodeGenFunction::NotSubtraction);
 
   if (op.Ty->isSignedIntegerOrEnumerationType()) {
     switch (CGF.getLangOpts().getSignedOverflowBehavior()) {
     case LangOptions::SOB_Defined:
       return Builder.CreateAdd(op.LHS, op.RHS, "add");
     case LangOptions::SOB_Undefined:
       if (!CGF.SanOpts.has(SanitizerKind::SignedIntegerOverflow))
         return Builder.CreateNSWAdd(op.LHS, op.RHS, "add");
if (!op.LHS->getType()->isPointerTy()) {
     }
 
     return Builder.CreateSub(op.LHS, op.RHS, "sub");
   }
 
   // If the RHS is not a pointer, then we have normal pointer
   // arithmetic.
   if (!op.RHS->getType()->isPointerTy())
-    return emitPointerArithmetic(CGF, op, /*subtraction*/ true);
+    return emitPointerArithmetic(CGF, op, CodeGenFunction::IsSubtraction);
 
   // Otherwise, this is a pointer subtraction.
 
   // Do the raw subtraction part.
   llvm::Value *LHS
     = Builder.CreatePtrToInt(op.LHS, CGF.PtrDiffTy, "sub.ptr.lhs.cast");
   llvm::Value *RHS
     = Builder.CreatePtrToInt(op.RHS, CGF.PtrDiffTy, "sub.ptr.rhs.cast");
#undef COMPOUND_OP
   }
 
   llvm_unreachable("Unhandled compound assignment operator");
 }
 
 Value *CodeGenFunction::EmitCheckedInBoundsGEP(Value *Ptr,
                                                ArrayRef<Value *> IdxList,
                                                bool SignedIndices,
+                                               bool IsSubtraction,
                                                SourceLocation Loc,
                                                const Twine &Name) {
   Value *GEPVal = Builder.CreateInBoundsGEP(Ptr, IdxList, Name);
 
   // If the pointer overflow sanitizer isn't enabled, do nothing.
   if (!SanOpts.has(SanitizerKind::PointerOverflow))
     return GEPVal;
 
Value *CodeGenFunction::EmitCheckedInBoundsGEP(Value *Ptr,
   auto *ComputedGEP = Builder.CreateAdd(IntPtr, TotalOffset);
 
   // The GEP is valid if:
   // 1) The total offset doesn't overflow, and
   // 2) The sign of the difference between the computed address and the base
   // pointer matches the sign of the total offset.
   llvm::Value *ValidGEP;
   auto *NoOffsetOverflow = Builder.CreateNot(OffsetOverflows);
-  auto *PosOrZeroValid = Builder.CreateICmpUGE(ComputedGEP, IntPtr);
   if (SignedIndices) {
+    auto *PosOrZeroValid = Builder.CreateICmpUGE(ComputedGEP, IntPtr);
     auto *PosOrZeroOffset = Builder.CreateICmpSGE(TotalOffset, Zero);
     llvm::Value *NegValid = Builder.CreateICmpULT(ComputedGEP, IntPtr);
     ValidGEP = Builder.CreateAnd(
         Builder.CreateSelect(PosOrZeroOffset, PosOrZeroValid, NegValid),
         NoOffsetOverflow);
-  } else {
+  } else if (!SignedIndices && !IsSubtraction) {
+    auto *PosOrZeroValid = Builder.CreateICmpUGE(ComputedGEP, IntPtr);
     ValidGEP = Builder.CreateAnd(PosOrZeroValid, NoOffsetOverflow);
+  } else {
+    auto *NegOrZeroValid = Builder.CreateICmpULE(ComputedGEP, IntPtr);
+    ValidGEP = Builder.CreateAnd(NegOrZeroValid, NoOffsetOverflow);
   }
 
   llvm::Constant *StaticArgs[] = {EmitCheckSourceLocation(Loc)};
   // Pass the computed GEP to the runtime to avoid emitting poisoned arguments.
   llvm::Value *DynamicArgs[] = {IntPtr, ComputedGEP};
   EmitCheck(std::make_pair(ValidGEP, SanitizerKind::PointerOverflow),
             SanitizerHandler::PointerOverflow, StaticArgs, DynamicArgs);
 
   return GEPVal;
 }

cfe/trunk/lib/CodeGen/CodeGenFunction.h

public:
   /// evaluate to true based on PGO data.
   void EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock,
                             llvm::BasicBlock *FalseBlock, uint64_t TrueCount);
 
   /// Given an assignment `*LHS = RHS`, emit a test that checks if \p RHS is
   /// nonnull, if \p LHS is marked _Nonnull.
   void EmitNullabilityCheck(LValue LHS, llvm::Value *RHS, SourceLocation Loc);
 
+  /// An enumeration which makes it easier to specify whether or not an
+  /// operation is a subtraction.
+  enum { NotSubtraction = false, IsSubtraction = true };
+
   /// Same as IRBuilder::CreateInBoundsGEP, but additionally emits a check to
   /// detect undefined behavior when the pointer overflow sanitizer is enabled.
   /// \p SignedIndices indicates whether any of the GEP indices are signed.
+  /// \p IsSubtraction indicates whether the expression used to form the GEP
+  /// is a subtraction.
   llvm::Value *EmitCheckedInBoundsGEP(llvm::Value *Ptr,
                                       ArrayRef<llvm::Value *> IdxList,
                                       bool SignedIndices,
+                                      bool IsSubtraction,
                                       SourceLocation Loc,
                                       const Twine &Name = "");
 
   /// \brief Emit a description of a type in a format suitable for passing to
   /// a runtime sanitizer handler.
   llvm::Constant *EmitCheckTypeDescriptor(QualType T);
 
   /// \brief Convert a value into a format suitable for passing to a runtime

cfe/trunk/test/CodeGen/ubsan-pointer-overflow.m

 // RUN: %clang_cc1 -triple x86_64-apple-darwin10 -w -emit-llvm -o - %s -fsanitize=pointer-overflow | FileCheck %s
 
 // CHECK-LABEL: define void @unary_arith
 void unary_arith(char *p) {
   // CHECK:  [[BASE:%.*]] = ptrtoint i8* {{.*}} to i64, !nosanitize
   // CHECK-NEXT: [[COMPGEP:%.*]] = add i64 [[BASE]], 1, !nosanitize
   // CHECK-NEXT: [[POSVALID:%.*]] = icmp uge i64 [[COMPGEP]], [[BASE]], !nosanitize
   // CHECK-NEXT: br i1 [[POSVALID]]{{.*}}, !nosanitize
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}, i64 [[BASE]], i64 [[COMPGEP]]){{.*}}, !nosanitize
   ++p;
 
   // CHECK: ptrtoint i8* {{.*}} to i64, !nosanitize
-  // CHECK-NEXT: add i64 {{.*}}, -1, !nosanitize
-  // CHECK: select i1 false{{.*}}, !nosanitize
+  // CHECK-NEXT: [[COMPGEP:%.*]] = add i64 {{.*}}, -1, !nosanitize
+  // CHECK: [[NEGVALID:%.*]] = icmp ule i64 [[COMPGEP]], {{.*}}, !nosanitize
+  // CHECK-NOT: select
+  // CHECK: br i1 [[NEGVALID]]{{.*}}, !nosanitize
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
   --p;
 
+  // CHECK: icmp uge i64
   // CHECK-NOT: select
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
   p++;
 
-  // CHECK: select
+  // CHECK: icmp ule i64
+  // CHECK-NOT: select
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
   p--;
 }
 
 // CHECK-LABEL: define void @binary_arith
 void binary_arith(char *p, int i) {
   // CHECK: [[SMUL:%.*]] = call { i64, i1 } @llvm.smul.with.overflow.i64(i64 1, i64 %{{.*}}), !nosanitize
   // CHECK-NEXT: [[SMULOFLOW:%.*]] = extractvalue { i64, i1 } [[SMUL]], 1, !nosanitize
void binary_arith_unsigned(char *p, unsigned i) {
   // CHECK-NEXT: [[POSVALID:%.*]] = icmp uge i64 [[COMPGEP]], [[BASE]], !nosanitize
   // CHECK: [[VALID:%.*]] = and i1 [[POSVALID]], [[OFFSETVALID]], !nosanitize
   // CHECK-NEXT: br i1 [[VALID]]{{.*}}, !nosanitize
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}, i64 [[BASE]], i64 [[COMPGEP]]){{.*}}, !nosanitize
   p + i;
 
   // CHECK: [[OFFSET:%.*]] = sub i64 0, {{.*}}
   // CHECK-NEXT: getelementptr inbounds {{.*}} [[OFFSET]]
-  // CHECK: select
+  // CHECK: icmp ule i64
+  // CHECK-NOT: select
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
   p - i;
 }
 
 // CHECK-LABEL: define void @fixed_len_array
 void fixed_len_array(int k) {
   // CHECK: getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* [[ARR:%.*]], i64 0, i64 [[IDXPROM:%.*]]
   // CHECK-NEXT: [[SMUL:%.*]] = call { i64, i1 } @llvm.smul.with.overflow.i64(i64 40, i64 [[IDXPROM]]), !nosanitize
void pointer_array(int **arr, int k) {
   // CHECK: @llvm.smul.with.overflow.i64(i64 4, i64 {{.*}}), !nosanitize
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
 
   arr[k][k];
 }
 
 // CHECK-LABEL: define void @pointer_array_unsigned_indices
 void pointer_array_unsigned_indices(int **arr, unsigned k) {
+  // CHECK: icmp uge
   // CHECK-NOT: select
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
+  // CHECK: icmp uge
   // CHECK-NOT: select
   // CHECK: call void @__ubsan_handle_pointer_overflow{{.*}}
   arr[k][k];
 }
 
 // CHECK-LABEL: define void @pointer_array_mixed_indices
 void pointer_array_mixed_indices(int **arr, int i, unsigned j) {
   // CHECK: select