[UBSan][clang][compiler-rt] Applying non-zero offset to nullptr is undefined behaviour

Summary:
Quote from http://eel.is/c++draft/expr.add#4:
```
4     When an expression J that has integral type is added to or subtracted
      from an expression P of pointer type, the result has the type of P.
(4.1) If P evaluates to a null pointer value and J evaluates to 0,
      the result is a null pointer value.
(4.2) Otherwise, if P points to an array element i of an array object x with n
      elements ([dcl.array]), the expressions P + J and J + P
      (where J has the value j) point to the (possibly-hypothetical) array
      element i+j of x if 0≤i+j≤n and the expression P - J points to the
      (possibly-hypothetical) array element i−j of x if 0≤i−j≤n.
(4.3) Otherwise, the behavior is undefined.
```

Therefore, as per the standard, applying non-zero offset to `nullptr`
(or making non-`nullptr` a `nullptr`, by subtracting pointer's integral value
from the pointer itself) is undefined behavior. (*if* `nullptr` is not defined,
i.e. e.g. `-fno-delete-null-pointer-checks` was *not* specified.)

To make things more fun, in C (6.5.6p8), applying *any* offset to null pointer
is undefined, although Clang front-end pessimizes the code by not lowering
that info, so this UB is "harmless".

Since rL369789 (D66608 `[InstCombine] icmp eq/ne (gep inbounds P, Idx..), null -> icmp eq/ne P, null`)
LLVM middle-end uses those guarantees for transformations.
If the source contains such UB's, said code may now be miscompiled.
Such miscompilations were already observed:
* https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190826/687838.html
* https://github.com/google/filament/pull/1566

Surprisingly, UBSan does not catch those issues
... until now. This diff teaches UBSan about these UB's.

`getelementpointer inbounds` is a pretty frequent instruction,
so this does have a measurable impact on performance;
I've addressed most of the obvious missing folds (and thus decreased the performance impact by ~5%),
and then re-performed some performance measurements using my [[ https://github.com/darktable-org/rawspeed | RawSpeed ]] benchmark:
(all measurements done with LLVM ToT, the sanitizer never fired.)
* no sanitization vs. existing check: average `+21.62%` slowdown
* existing check vs. check after this patch: average `22.04%` slowdown
* no sanitization vs. this patch: average `48.42%` slowdown

Reviewers: vsk, filcab, rsmith, aaron.ballman, vitalybuka, rjmccall, #sanitizers

Reviewed By: rsmith

Subscribers: kristof.beyls, nickdesaulniers, nikic, ychen, dtzWill, xbolva00, dberris, arphaman, rupprecht, reames, regehr, llvm-commits, cfe-commits

Tags: #clang, #sanitizers, #llvm

Differential Revision: https://reviews.llvm.org/D67122

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@374293 91177308-0d34-0410-b5e6-96231b3b80d8

9 files changed, 177 insertions, 9 deletions

diff --git a/lib/sanitizer_common/sanitizer_suppressions.h b/lib/sanitizer_common/sanitizer_suppressions.h
index f9da7af7e..2d88b1f72 100644
--- a/lib/sanitizer_common/sanitizer_suppressions.h
+++ b/lib/sanitizer_common/sanitizer_suppressions.h
@@ -42,7 +42,7 @@ class SuppressionContext {
   void GetMatched(InternalMmapVector<Suppression *> *matched);
 
  private:
-  static const int kMaxSuppressionTypes = 32;
+  static const int kMaxSuppressionTypes = 64;
   const char **const suppression_types_;
   const int suppression_types_num_;
 
diff --git a/lib/ubsan/ubsan_checks.inc b/lib/ubsan/ubsan_checks.inc
index 7e7216c5b..7de14ec2d 100644
--- a/lib/ubsan/ubsan_checks.inc
+++ b/lib/ubsan/ubsan_checks.inc
@@ -18,6 +18,9 @@
 
 UBSAN_CHECK(GenericUB, "undefined-behavior", "undefined")
 UBSAN_CHECK(NullPointerUse, "null-pointer-use", "null")
+UBSAN_CHECK(NullptrWithOffset, "nullptr-with-offset", "pointer-overflow")
+UBSAN_CHECK(NullptrWithNonZeroOffset, "nullptr-with-nonzero-offset", "pointer-overflow")
+UBSAN_CHECK(NullptrAfterNonZeroOffset, "nullptr-after-nonzero-offset", "pointer-overflow")
 UBSAN_CHECK(PointerOverflow, "pointer-overflow", "pointer-overflow")
 UBSAN_CHECK(MisalignedPointerUse, "misaligned-pointer-use", "alignment")
 UBSAN_CHECK(AlignmentAssumption, "alignment-assumption", "alignment")
diff --git a/lib/ubsan/ubsan_handlers.cpp b/lib/ubsan/ubsan_handlers.cpp
index e832581f9..3f9da75a1 100644
--- a/lib/ubsan/ubsan_handlers.cpp
+++ b/lib/ubsan/ubsan_handlers.cpp
@@ -691,14 +691,33 @@ static void handlePointerOverflowImpl(PointerOverflowData *Data,
                                       ValueHandle Result,
                                       ReportOptions Opts) {
   SourceLocation Loc = Data->Loc.acquire();
-  ErrorType ET = ErrorType::PointerOverflow;
+  ErrorType ET;
+
+  if (Base == 0 && Result == 0)
+    ET = ErrorType::NullptrWithOffset;
+  else if (Base == 0 && Result != 0)
+    ET = ErrorType::NullptrWithNonZeroOffset;
+  else if (Base != 0 && Result == 0)
+    ET = ErrorType::NullptrAfterNonZeroOffset;
+  else
+    ET = ErrorType::PointerOverflow;
 
   if (ignoreReport(Loc, Opts, ET))
     return;
 
   ScopedReport R(Opts, Loc, ET);
 
-  if ((sptr(Base) >= 0) == (sptr(Result) >= 0)) {
+  if (ET == ErrorType::NullptrWithOffset) {
+    Diag(Loc, DL_Error, ET, "applying zero offset to null pointer");
+  } else if (ET == ErrorType::NullptrWithNonZeroOffset) {
+    Diag(Loc, DL_Error, ET, "applying non-zero offset %0 to null pointer")
+        << Result;
+  } else if (ET == ErrorType::NullptrAfterNonZeroOffset) {
+    Diag(
+        Loc, DL_Error, ET,
+        "applying non-zero offset to non-null pointer %0 produced null pointer")
+        << (void *)Base;
+  } else if ((sptr(Base) >= 0) == (sptr(Result) >= 0)) {
     if (Base > Result)
       Diag(Loc, DL_Error, ET,
            "addition of unsigned offset to %0 overflowed to %1")
diff --git a/test/ubsan/TestCases/Pointer/index-overflow.cpp b/test/ubsan/TestCases/Pointer/index-overflow.cpp
index f9b1fea08..0c082ddd4 100644
--- a/test/ubsan/TestCases/Pointer/index-overflow.cpp
+++ b/test/ubsan/TestCases/Pointer/index-overflow.cpp
@@ -1,7 +1,9 @@
 // RUN: %clangxx -fsanitize=pointer-overflow %s -o %t
-// RUN: %run %t 1 2>&1 | FileCheck %s --check-prefix=ERR
-// RUN: %run %t 0 2>&1 | FileCheck %s --check-prefix=SAFE
-// RUN: %run %t -1 2>&1 | FileCheck %s --check-prefix=SAFE
+// RUN: %run %t 2 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=ERR2
+// RUN: %run %t 1 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=ERR1
+// RUN: %run %t 0 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=SAFE
+// RUN: %run %t -1 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=SAFE
+// RUN: %run %t -2 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=SAFE
 
 #include <stdio.h>
 #include <stdint.h>
@@ -9,11 +11,18 @@
 
 int main(int argc, char *argv[]) {
   // SAFE-NOT: runtime error
-  // ERR: runtime error: pointer index expression with base {{.*}} overflowed to
+  // ERR2: runtime error: pointer index expression with base {{.*}} overflowed to
+  // ERR2: runtime error: pointer index expression with base {{.*}} overflowed to
+  // ERR1: runtime error: applying non-zero offset to non-null pointer 0x{{.*}} produced null pointer
+  // ERR1: runtime error: applying non-zero offset to non-null pointer 0x{{.*}} produced null pointer
 
   char *p = (char *)(UINTPTR_MAX);
 
   printf("%p\n", p + atoi(argv[1]));
 
+  char *q = (char *)(UINTPTR_MAX);
+
+  printf("%p\n", p - (-atoi(argv[1])));
+
   return 0;
 }
diff --git a/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-constants.cpp b/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-constants.cpp
new file mode 100644
index 000000000..2c3c15659
--- /dev/null
+++ b/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-constants.cpp
@@ -0,0 +1,29 @@
+// RUN: %clang -x c -fsanitize=pointer-overflow -O0 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-C --implicit-check-not="error:"
+// RUN: %clang -x c -fsanitize=pointer-overflow -O1 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-C --implicit-check-not="error:"
+// RUN: %clang -x c -fsanitize=pointer-overflow -O2 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-C --implicit-check-not="error:"
+// RUN: %clang -x c -fsanitize=pointer-overflow -O3 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-C --implicit-check-not="error:"
+
+// RUN: %clangxx    -fsanitize=pointer-overflow -O0 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-CPP --implicit-check-not="error:"
+// RUN: %clangxx    -fsanitize=pointer-overflow -O1 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-CPP --implicit-check-not="error:"
+// RUN: %clangxx    -fsanitize=pointer-overflow -O2 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-CPP --implicit-check-not="error:"
+// RUN: %clangxx    -fsanitize=pointer-overflow -O3 %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-CPP --implicit-check-not="error:"
+
+#include <stdlib.h>
+
+int main(int argc, char *argv[]) {
+  char *base, *result;
+
+  base = (char *)0;
+  result = base + 0;
+  // CHECK-C: {{.*}}.cpp:[[@LINE-1]]:17: runtime error: applying zero offset to null pointer
+
+  base = (char *)0;
+  result = base + 1;
+  // CHECK: {{.*}}.cpp:[[@LINE-1]]:17: runtime error: applying non-zero offset 1 to null pointer
+
+  base = (char *)1;
+  result = base - 1;
+  // CHECK: {{.*}}.cpp:[[@LINE-1]]:17: runtime error: applying non-zero offset to non-null pointer 0x{{.*}} produced null pointer
+
+  return 0;
+}
diff --git a/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-summary.cpp b/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-summary.cpp
new file mode 100644
index 000000000..1f8197472
--- /dev/null
+++ b/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-summary.cpp
@@ -0,0 +1,32 @@
+// RUN: %clang -x c -fsanitize=pointer-overflow %s -o %t
+// RUN: %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK-NOTYPE,CHECK-NOTYPE-C
+// RUN: %env_ubsan_opts=report_error_type=1 %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK-TYPE,CHECK-TYPE-C
+
+// RUN: %clangxx -fsanitize=pointer-overflow %s -o %t
+// RUN: %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK-NOTYPE,CHECK-NOTYPE-CPP
+// RUN: %env_ubsan_opts=report_error_type=1 %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK-TYPE,CHECK-TYPE-CPP
+
+// REQUIRES: !ubsan-standalone && !ubsan-standalone-static
+
+#include <stdlib.h>
+
+int main(int argc, char *argv[]) {
+  char *base, *result;
+
+  base = (char *)0;
+  result = base + 0;
+  // CHECK-NOTYPE-C: SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior {{.*}}summary.cpp:[[@LINE-1]]:17
+  // CHECK-TYPE-C: SUMMARY: UndefinedBehaviorSanitizer: nullptr-with-offset {{.*}}summary.cpp:[[@LINE-2]]:17
+
+  base = (char *)0;
+  result = base + 1;
+  // CHECK-NOTYPE: SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior {{.*}}summary.cpp:[[@LINE-1]]:17
+  // CHECK-TYPE: SUMMARY: UndefinedBehaviorSanitizer: nullptr-with-nonzero-offset {{.*}}summary.cpp:[[@LINE-2]]:17
+
+  base = (char *)1;
+  result = base - 1;
+  // CHECK-NOTYPE: SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior {{.*}}summary.cpp:[[@LINE-1]]:17
+  // CHECK-TYPE: SUMMARY: UndefinedBehaviorSanitizer: nullptr-after-nonzero-offset {{.*}}summary.cpp:[[@LINE-2]]:17
+
+  return 0;
+}
diff --git a/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-variable.cpp b/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-variable.cpp
new file mode 100644
index 000000000..33fe836c5
--- /dev/null
+++ b/test/ubsan/TestCases/Pointer/nullptr-and-nonzero-offset-variable.cpp
@@ -0,0 +1,54 @@
+// R1UN: %clang -x c   -fsanitize=pointer-overflow -O0 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB-C
+// R1UN: %clang -x c   -fsanitize=pointer-overflow -O1 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB-C
+// R1UN: %clang -x c   -fsanitize=pointer-overflow -O2 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB-C
+// R1UN: %clang -x c   -fsanitize=pointer-overflow -O3 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB-C
+
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O0 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O1 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O2 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O3 %s -o %t && %run %t 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK
+
+// RUN: %clang -x c   -fsanitize=pointer-overflow -O0 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+// RUN: %clang -x c   -fsanitize=pointer-overflow -O1 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+// RUN: %clang -x c   -fsanitize=pointer-overflow -O2 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+// RUN: %clang -x c   -fsanitize=pointer-overflow -O3 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O0 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O1 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O2 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+// RUN: %clang -x c++ -fsanitize=pointer-overflow -O3 %s -o %t && %run %t I_AM_UB 2>&1 | FileCheck %s --implicit-check-not="error:" --check-prefix=CHECK-UB
+
+#include <stdint.h>
+#include <stdio.h>
+
+// Just so deduplication doesn't do anything.
+static char *getelementpointer_inbounds_v0(char *base, unsigned long offset) {
+  // Potentially UB.
+  return base + offset;
+}
+static char *getelementpointer_inbounds_v1(char *base, unsigned long offset) {
+  // Potentially UB.
+  return base + offset;
+}
+
+int main(int argc, char *argv[]) {
+  char *base;
+  unsigned long offset;
+
+  printf("Dummy\n");
+  // CHECK: Dummy
+
+  base = (char *)0;
+  offset = argc - 1;
+  (void)getelementpointer_inbounds_v0(base, offset);
+  // CHECK-UB: {{.*}}.cpp:[[@LINE-17]]:15: runtime error: applying non-zero offset 1 to null pointer
+  // CHECK-UB-C: {{.*}}.cpp:[[@LINE-17]]:15: runtime error: applying offset to null pointer
+
+  base = (char *)(intptr_t)(argc - 1);
+  offset = argc == 1 ? 0 : -(argc - 1);
+  (void)getelementpointer_inbounds_v1(base, offset);
+  // CHECK-UB: {{.*}}.cpp:[[@LINE-19]]:15: runtime error: applying non-zero offset to non-null pointer 0x{{.*}} produced null pointer
+  // CHECK-UB-C: {{.*}}.cpp:[[@LINE-20]]:15: runtime error: applying offset to null pointer
+
+  return 0;
+}
diff --git a/test/ubsan/TestCases/Pointer/unsigned-index-expression.cpp b/test/ubsan/TestCases/Pointer/unsigned-index-expression.cpp
index 5a1432625..e4494f334 100644
--- a/test/ubsan/TestCases/Pointer/unsigned-index-expression.cpp
+++ b/test/ubsan/TestCases/Pointer/unsigned-index-expression.cpp
@@ -1,5 +1,5 @@
 // RUN: %clangxx -std=c++11 -fsanitize=pointer-overflow %s -o %t
-// RUN: %run %t 2>&1 | FileCheck %s
+// RUN: %run %t 2>&1 | FileCheck %s --implicit-check-not="error:"
 
 int main(int argc, char *argv[]) {
   char c;
@@ -12,7 +12,7 @@ int main(int argc, char *argv[]) {
   // CHECK: unsigned-index-expression.cpp:[[@LINE+1]]:16: runtime error: subtraction of unsigned offset from 0x{{.*}} overflowed to 0x{{.*}}
   char *q1 = p - neg_1;
 
-  // CHECK: unsigned-index-expression.cpp:[[@LINE+2]]:16: runtime error: pointer index expression with base 0x{{0*}} overflowed to 0x{{.*}}
+  // CHECK: unsigned-index-expression.cpp:[[@LINE+2]]:16: runtime error: applying non-zero offset {{.*}} to null pointer
   char *n = nullptr;
   char *q2 = n - 1ULL;
 
diff --git a/test/ubsan_minimal/TestCases/nullptr-and-nonzero-offset.c b/test/ubsan_minimal/TestCases/nullptr-and-nonzero-offset.c
new file mode 100644
index 000000000..ba930341b
--- /dev/null
+++ b/test/ubsan_minimal/TestCases/nullptr-and-nonzero-offset.c
@@ -0,0 +1,22 @@
+// RUN: %clang   -fsanitize=pointer-overflow %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-C --implicit-check-not="pointer-overflow"
+// RUN: %clangxx -fsanitize=pointer-overflow %s -o %t && %run %t 2>&1 | FileCheck %s --check-prefixes=CHECK,CHECK-CPP --implicit-check-not="pointer-overflow"
+
+#include <stdlib.h>
+
+int main(int argc, char *argv[]) {
+  char *base, *result;
+
+  base = (char *)0;
+  result = base + 0;
+  // CHECK-C: pointer-overflow
+
+  base = (char *)0;
+  result = base + 1;
+  // CHECK: pointer-overflow
+
+  base = (char *)1;
+  result = base - 1;
+  // CHECK: pointer-overflow
+
+  return 0;
+}