[ubsan] Handle undef values in the integer overflow diagnostic

[vsk]

Summary

The compiler may optimize away the values passed into ubsan's integer
overflow handlers. This can lead to confusing reports. E.g, the runtime
reports overflows in nonsensical expressions such as "0 + 0":

struct Undef { int I; }

int getUndefInt() { Undef U; return U.I; }

int main() { return getUndefInt() + getUndefInt(); }

Improve the situation by checking for an actual overflow in the handler.
If we can't detect an overflow, explain what happened to the user.

Depends on D25294.

[vsk]

• Fix -Winvalid-noreturn warnings.

[vsk]

Ping. @filcab, would you mind taking a look?

In particular, I'd be interested in any alternative implementations of hasIntegerOverflow, since the current version can't handle overflows in 128-bit integers.

[filcab]

In D25295#568734, @vsk wrote:

In particular, I'd be interested in any alternative implementations of hasIntegerOverflow, since the current version can't handle overflows in 128-bit integers.

You can use #if HAVE_INT128_T (and UIntMax) to get 128 bit integers if available.

Why is the test a bc file instead of the plain ll file?
Better yet: Can you get a reproducible for this bug in C/C++? (I can't get your original example to trigger the bug) Would be better, and closer to UBSan uses.

Thank you,
Filipe

lib/ubsan/ubsan_handlers.cc

115

Don't make errors disappear like this. Add an UNREACHABLE() to the default case.

123

Won't you overflow if the values would overflow (for the case where your values are the same type as SIntMax)?

128

return V > UpperLimit || V < LowerLimit;
Then remove the indentation level for the else, make the same transformation, and remove the return false; at the end.

[vsk]

Why is the test a bc file instead of the plain ll file?

llvm has a bitcode backwards compatibility policy. Checking in bitcode means that people can change the textual IR without breaking this test (e.g when the typeless pointer work lands). We should also check in the textual IR used to produce the bitcode so that people have an easy time updating the test in the future.

Better yet: Can you get a reproducible for this bug in C/C++?

I can reproduce this issue several ways with my system compiler. The problem is that we can't guarantee that all versions of all compilers which compile a test case in C will treat overflow UB in the same way. That's why I thought it'd be better to check in a bitcode test which unambiguously demonstrates the issue.

Fwiw, here is the original program I tried:

// Compile at -fsanitize=integer -O2

struct Undef {
  int I;
}

int getUndefInt() {
  Undef U;
  return U.I; //< Read of uninitialized memory.
}

int main() { return getUndefInt() + getUndefInt(); }

lib/ubsan/ubsan_handlers.cc

115

I will try and think of a better way to do this. As it stands, the problem is that the default case isn't unreachable. If e.g the optimizer decides to pass in (0, 0) into the overflow handler instead of (INT_MAX, INT_MAX), we would hit it.

123

Yes, I brought this up in my last comment as something I didn't have a good solution for. I think I have a better approach now that doesn't actually necessitate evaluating the arithmetic op. I'll update the patch soon!

128

Good point; but I'd rather rework the overflow check.

[vsk]

• Don't depend on sizeof(SIntMax) being greater than sizeof(ValueHandle). I.e, get a bit smarter about doing overflow checks.

lib/ubsan/ubsan_handlers.cc

115

D'oh, what a silly thinko! Sorry, of course this is unreachable.

[vsk]

• Get rid of the IR/bitcode test and re-write in C. This makes the test a bit easier to understand, and more portable.

[filcab]

I really don't like that the test is reimplementing part of the instrumentation.
I know a test like this will probably be a bit fragile, as we will be relying on some optimizations (to make the undefs appear).

The original test (the one in the phab summary) works, and gets reduced to a call to the reported function on -O2 -fsanitize=undefined. It looks safe enough to use tests like that (With some comments so people understand what we're doing there if the tests break for some reason).
@kcc might have a different opinion, so I'd like him to chime in.

lib/ubsan/ubsan_handlers.cc

105

No need for \brief

111

Signed integer overflow triggers undefined behavior.

112

What do these comments mean? You seem to want to "name" some of the variables, but if I got that correctly, you ended up with two variables which you refer to as L.
Having names depend on the values (Ln vs Lp) doesn't seem to help either.

135

Won't LowerLimit / -1 overflow?

[vsk]

In D25295#582541, @filcab wrote:

I really don't like that the test is reimplementing part of the instrumentation.

OK. Then we should see if we can do anything about llvm.sadd.with.overflow() returning different values at -O0/-O3 when its operands are %undef. I'll ask around.

I know a test like this will probably be a bit fragile, as we will be relying on some optimizations (to make the undefs appear).

Right. I have tried changing together e.g multiple calls to getUndef() in one program, but the optimizer throws it away. We may be able to play some tricks with noinline to make this work.

The original test (the one in the phab summary) works, and gets reduced to a call to the reported function on -O2 -fsanitize=undefined. It looks safe enough to use tests like that (With some comments so people understand what we're doing there if the tests break for some reason).
@kcc might have a different opinion, so I'd like him to chime in.

Right, I can try this approach again.

lib/ubsan/ubsan_handlers.cc

111

Is your concern that getIntegerBitWidth() could return something that exceeds the bit-width of SIntMax?

112

I'm trying to attach labels to "LHS" and "RHS" based on whether or not they are negative. Would it help to state explicitly that the 'n' suffix denotes that the variable is negative, or should the comments just be dropped?

135

Yes, this is a bug. The check should be for RHS < LowerLimit/LHS.

[vsk]

In D25295#582574, @vsk wrote:

In D25295#582541, @filcab wrote:

I really don't like that the test is reimplementing part of the instrumentation.

OK. Then we should see if we can do anything about llvm.sadd.with.overflow() returning different values at -O0/-O3 when its operands are %undef. I'll ask around.

I've asked around and haven't found a way around this. Part of the nature of undef is that two uses of a single undef may assume different values: "an ‘undef‘ “variable” can arbitrarily change its value over its “live range”" (http://llvm.org/docs/LangRef.html#undefined-values).

I know a test like this will probably be a bit fragile, as we will be relying on some optimizations (to make the undefs appear).

I tried again to write a plain-C test which gets compiled down to unconditional branches into the ubsan diagnostic routines, but haven't managed to do it. Here is my latest attempt: https://ghostbin.com/paste/wy2g2. The compiler just decides not to codegen the branch-on-undef in the way I like.

Do you have other suggestions for how to test this?

I've taken the rest of your suggestions into account in a local patch.

lib/ubsan/ubsan_handlers.cc

112

It seems like these comments aren't adding anything, so I've removed them locally.

[vsk]

• Fix two overflow issues Filipe pointed out in inline comments.
• Remove the tests for undef values in diagnostic handlers. Instead, we are just testing the corner cases for the overflow checking logic. The rationale is that we don't want to mock up ubsan instrumentation in a test, and we also can't rely on the compiler treating UB in a consistent/testable way.

lib/ubsan/ubsan_diag.h

union {
       UIntMax UInt;
       SIntMax SInt;
       FloatMax Float;
       const void *Pointer;
     };
   };
 
 private:
-  static const unsigned MaxArgs = 5;
+  static const unsigned MaxArgs = 7;
   static const unsigned MaxRanges = 1;
 
   /// The arguments which have been added to this diagnostic so far.
   Arg Args[MaxArgs];
   unsigned NumArgs;
 
   /// The ranges which have been added to this diagnostic so far.
   Range Ranges[MaxRanges];

lib/ubsan/ubsan_handlers.cc

 }
 void __ubsan::__ubsan_handle_type_mismatch_abort(TypeMismatchData *Data,
                                                  ValueHandle Pointer) {
   GET_REPORT_OPTIONS(true);
   handleTypeMismatchImpl(Data, Pointer, Opts);
   Die();
 }
 
+/// \brief Check if a signed integer arithmetic operation will overflow.
+static bool checkForSignedOverflow(const Value &L, const char *Operator,
+                                   const Value &R) {
+  SIntMax LHS = L.getSIntValue(); //< Ln = LHS if LHS < 0, otherwise Lp = LHS
+  SIntMax RHS = R.getSIntValue(); //< Rn = RHS if RHS < 0, otherwise Rp = RHS
+  SIntMax UpperLimit =
+      (SIntMax(1) << (L.getType().getIntegerBitWidth() - 1)) - 1; //< U
+  SIntMax LowerLimit = -UpperLimit - 1;                           //< L
+
+  switch (Operator[0]) {
+  case '+': {
+    if (LHS > 0 && RHS > 0)
+      return RHS > (UpperLimit - LHS); // Lp + Rp > U => Rp > U - Lp
+    else if (LHS < 0 && RHS < 0)
+      return RHS < (LowerLimit - LHS); // Ln + Rn < L => Rn < L - Ln
+    return false; // (Lp + Rn) and (Ln + Rp) can't overflow.
+  }
+  case '-': {
+    if (LHS > 0 && RHS < 0)
+      return LHS > (UpperLimit + RHS); // Lp - Rn > U => Lp > U + Rn
+    else if (LHS < 0 && RHS > 0)
+      return LHS < (LowerLimit + RHS); // Ln - Rp < L => Ln < L + Rp
+    return false; // (Lp - Rp) and (Ln - Rn) can't overflow.
+  }
+  case '*': {
+    if (LHS > 0 && RHS > 0)
+      return LHS > (UpperLimit / RHS); // Lp * Rp > U => Lp > U/Rp
+    else if (LHS < 0 && RHS < 0)
+      return LHS < (UpperLimit / RHS); // Ln * Rn > U => Ln < U/Rn
+    else if (LHS > 0 && RHS < 0)
+      return LHS > (LowerLimit / RHS); // Lp * Rn < L => Lp > L/Rn
+    else if (LHS < 0 && RHS > 0)
+      return LHS < (LowerLimit / RHS); // Ln * Rp < L => Ln < L/Rp
+    return false; // Multiplication by zero can't overflow.
+  }
+  default:
+    UNREACHABLE("unexpected arithmetic operator!");
+  }
+}
+
+/// \brief Check if an unsigned integer arithmetic operation will overflow.
+static bool checkForUnsignedOverflow(const Value &L, const char *Operator,
+                                     const Value &R) {
+  UIntMax LHS = L.getUIntValue(); //< L
+  UIntMax RHS = R.getUIntValue(); //< R
+  UIntMax UpperLimit = ~UIntMax(0) >> (8 * sizeof(UIntMax) -
+                                       L.getType().getIntegerBitWidth()); //< U
+
+  switch (Operator[0]) {
+  case '+':
+    return LHS > (UpperLimit - RHS); // L + R > U => L > U - R
+  case '-':
+    return LHS < RHS; // L - R < 0 => L < R
+  case '*':
+    return (RHS == 0) ? false
+                      : (LHS > UpperLimit / RHS); // L * R > U => L > U/R
+  default:
+    UNREACHABLE("unexpected arithmetic operator!");
+  }
+}
+
+/// \brief Check if an integer arithmetic operation will overflow.
+static bool hasIntegerOverflow(bool IsSigned, const Value &L,
+                               const char *Operator, const Value &R) {
+  if (IsSigned)
+    return checkForSignedOverflow(L, Operator, R);
+  return checkForUnsignedOverflow(L, Operator, R);
+}
+
 /// \brief Common diagnostic emission for various forms of integer overflow.
 static void handleIntegerOverflowImpl(OverflowData *Data, ValueHandle LHS,
                                       const char *Operator, const Value &RHSVal,
                                       ReportOptions Opts) {
   SourceLocation Loc = Data->Loc.acquire();
   bool IsSigned = Data->Type.isSignedIntegerTy();
   ErrorType ET = IsSigned ? ErrorType::SignedIntegerOverflow
                           : ErrorType::UnsignedIntegerOverflow;
 
   if (ignoreReport(Loc, Opts, ET))
     return;
 
   ScopedReport R(Opts, Loc, ET);
 
-  Diag(Loc, DL_Error, "%0 integer overflow: "
-                      "%1 %2 %3 cannot be represented in type %4")
-    << (IsSigned ? "signed" : "unsigned")
-    << Value(Data->Type, LHS) << Operator << RHSVal << Data->Type;
+  Value LHSVal{Data->Type, LHS};
+  bool WouldOverflow = hasIntegerOverflow(IsSigned, LHSVal, Operator, RHSVal);
+
+  Diag(Loc, DL_Error, "%0%1 integer overflow: "
+                      "%2 %3 %4 cannot be represented in type %5%6")
+      << (WouldOverflow ? "" : "possible ")
+      << (IsSigned ? "signed" : "unsigned") << LHSVal << Operator << RHSVal
+      << Data->Type << (WouldOverflow ? "" : " (values optimized away)");
 }
 
 #define UBSAN_OVERFLOW_HANDLER(handler_name, op, unrecoverable)                \
   void __ubsan::handler_name(OverflowData *Data, ValueHandle LHS,              \
                              ValueHandle RHS) {                                \
     GET_REPORT_OPTIONS(unrecoverable);                                         \
     handleIntegerOverflowImpl(Data, LHS, op, Value(Data->Type, RHS), Opts);    \
     if (unrecoverable)                                                         \

test/ubsan/TestCases/Integer/undef-overflow.cpp

+// RUN: %clangxx -Wno-override-module -fsanitize=signed-integer-overflow,unsigned-integer-overflow %s -o %t && %run %t 2>&1 | FileCheck %s
+
+#include <cstdint>
+
+extern "C" {
+  struct SourceLocation {
+    const char *Filename;
+    uint32_t Line;
+    uint32_t Column;
+  };
+
+  struct TypeDescriptor {
+    uint16_t TypeKind;
+    uint16_t TypeInfo;
+    char TypeName[5]; //< Use 2-letter type names to simplify the descriptors.
+  };
+
+  struct OverflowData {
+    SourceLocation Loc;
+    TypeDescriptor *Type;
+  };
+
+  void __ubsan_handle_add_overflow(OverflowData *, uintptr_t, uintptr_t);
+  void __ubsan_handle_sub_overflow(OverflowData *, uintptr_t, uintptr_t);
+  void __ubsan_handle_mul_overflow(OverflowData *, uintptr_t, uintptr_t);
+}
+
+SourceLocation getFreshSourceLoc() {
+  SourceLocation Loc;
+  Loc.Filename = "undef.c";
+  Loc.Line = 1;
+  Loc.Column = 1;
+  return Loc;
+}
+
+OverflowData getFreshOverflowData(TypeDescriptor *TD) {
+  OverflowData OD;
+  OD.Loc = getFreshSourceLoc();
+  OD.Type = TD;
+  return OD;
+}
+
+TypeDescriptor i8 = {0, 7, {'\'', 'i', '8', '\'', '\0'}};
+
+TypeDescriptor u8 = {0, 6, {'\'', 'u', '8', '\'', '\0'}};
+
+// A non-reproducible overflow can occur when the optimizer decides that an
+// overflow must occur, but passes undef values into the handler. E.g:
+//
+//   struct Undef { int I; }
+//   int getUndef() { Undef U; return U.I; }
+//   int foo() { getUndef() + getUndef(); }
+void test_non_reproducible_overflows() {
+  OverflowData OD;
+
+  OD = getFreshOverflowData(&i8);
+  __ubsan_handle_add_overflow(&OD, 0, 0);
+// CHECK: possible signed integer overflow: 0 + 0 cannot be represented in type 'i8' (values optimized away)
+
+  OD = getFreshOverflowData(&i8);
+  __ubsan_handle_sub_overflow(&OD, 0, 0);
+// CHECK: possible signed integer overflow: 0 - 0 cannot be represented in type 'i8' (values optimized away)
+
+  OD = getFreshOverflowData(&i8);
+  __ubsan_handle_mul_overflow(&OD, 0, 0);
+// CHECK: possible signed integer overflow: 0 * 0 cannot be represented in type 'i8' (values optimized away)
+
+  OD = getFreshOverflowData(&u8);
+  __ubsan_handle_add_overflow(&OD, 0, 0);
+// CHECK: possible unsigned integer overflow: 0 + 0 cannot be represented in type 'u8' (values optimized away)
+
+  OD = getFreshOverflowData(&u8);
+  __ubsan_handle_sub_overflow(&OD, 0, 0);
+// CHECK: possible unsigned integer overflow: 0 - 0 cannot be represented in type 'u8' (values optimized away)
+
+  OD = getFreshOverflowData(&u8);
+  __ubsan_handle_mul_overflow(&OD, 0, 0);
+// CHECK: possible unsigned integer overflow: 0 * 0 cannot be represented in type 'u8' (values optimized away)
+}
+
+void test_reproducible_overflows() {
+  int32_t s_max = INT32_MAX;
+  int32_t s_one = 1;
+  int32_t s_min = INT32_MIN;
+  int32_t s_neg_one = -1;
+  int32_t s_two = 2;
+  int32_t s_neg_two = -2;
+
+  (void)(s_max + 1);
+// CHECK: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
+
+  (void)(s_min + s_neg_one);
+// CHECK: signed integer overflow: -2147483648 + -1 cannot be represented in type 'int'
+
+  (void)(s_max - s_neg_one);
+// CHECK: signed integer overflow: 2147483647 - -1 cannot be represented in type 'int'
+
+  (void)(s_min - s_one);
+// CHECK: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'
+
+  (void)(s_max * s_two);
+// CHECK: signed integer overflow: 2147483647 * 2 cannot be represented in type 'int'
+
+  (void)(s_max * s_neg_two);
+// CHECK: signed integer overflow: 2147483647 * -2 cannot be represented in type 'int'
+
+  (void)(s_neg_two * s_max);
+// CHECK: signed integer overflow: -2 * 2147483647 cannot be represented in type 'int'
+
+  (void)(s_neg_two * s_min);
+// CHECK: signed integer overflow: -2 * -2147483648 cannot be represented in type 'int'
+
+  uint32_t u_max = UINT32_MAX;
+  uint32_t u_one = 1;
+  uint32_t u_two = 2;
+  uint32_t u_halfmax = (UINT32_MAX / 2) + 1;
+
+  (void)(u_max + u_one);
+// CHECK: unsigned integer overflow: 4294967295 + 1 cannot be represented in type 'unsigned int'
+
+  (void)(u_one - u_two);
+// CHECK: unsigned integer overflow: 1 - 2 cannot be represented in type 'unsigned int'
+
+  (void)(u_halfmax * u_two);
+// CHECK: unsigned integer overflow: 2147483648 * 2 cannot be represented in type 'unsigned int'
+}
+
+int main() {
+  test_non_reproducible_overflows();
+  test_reproducible_overflows();
+  return 0;
+}