From 585dc5db136c656cd4a0b81d652d554d39aeae30 Mon Sep 17 00:00:00 2001
From: George Karpenkov <ekarpenkov@apple.com>
Date: Mon, 26 Feb 2018 21:03:06 +0000
Subject: [PATCH] [analyzer] Quickfix: do not overflow in calculating offset in
 RegionManager

Addresses https://bugs.llvm.org/show_bug.cgi?id=36206

rdar://37159026

A proper fix would be much harder, and would involve changing the
appropriate code in ExprEngine to be aware of the size limitations of
the type used for addressing.

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

llvm-svn: 326122
---
 clang/lib/StaticAnalyzer/Core/MemRegion.cpp | 46 +++++++++++++++++++++++++++++
 clang/test/Analysis/region-store.cpp        |  2 +-
 clang/test/Analysis/region_store_overflow.c | 13 ++++++++
 3 files changed, 60 insertions(+), 1 deletion(-)
 create mode 100644 clang/test/Analysis/region_store_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp
index aa54544..2f77524 100644
--- a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp
+++ b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp
@@ -23,6 +23,11 @@
 #include "clang/Basic/SourceManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Debug.h"
+
+#include<functional>
+
+#define DEBUG_TYPE "MemRegion"
 
 using namespace clang;
 using namespace ento;
@@ -1149,6 +1154,36 @@ const SymbolicRegion *MemRegion::getSymbolicBase() const {
   return nullptr;
 }
 
+/// Perform a given operation on two integers, return whether it overflows.
+/// Optionally write the resulting output into \p Res.
+static bool checkedOp(
+    int64_t LHS,
+    int64_t RHS,
+    std::function<llvm::APInt(llvm::APInt *, const llvm::APInt &, bool &)> Op,
+    int64_t *Res = nullptr) {
+  llvm::APInt ALHS(/*BitSize=*/64, LHS, /*Signed=*/true);
+  llvm::APInt ARHS(/*BitSize=*/64, RHS, /*Signed=*/true);
+  bool Overflow;
+  llvm::APInt Out = Op(&ALHS, ARHS, Overflow);
+  if (!Overflow && Res)
+    *Res = Out.getSExtValue();
+  return Overflow;
+}
+
+static bool checkedAdd(
+    int64_t LHS,
+    int64_t RHS,
+    int64_t *Res=nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::sadd_ov, Res);
+}
+
+static bool checkedMul(
+    int64_t LHS,
+    int64_t RHS,
+    int64_t *Res=nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::smul_ov, Res);
+}
+
 RegionRawOffset ElementRegion::getAsArrayOffset() const {
   CharUnits offset = CharUnits::Zero();
   const ElementRegion *ER = this;
@@ -1176,6 +1211,17 @@ RegionRawOffset ElementRegion::getAsArrayOffset() const {
         }
 
         CharUnits size = C.getTypeSizeInChars(elemType);
+
+        int64_t Mult;
+        bool Overflow = checkedAdd(i, size.getQuantity(), &Mult);
+        Overflow |= checkedMul(Mult, offset.getQuantity());
+        if (Overflow) {
+          DEBUG(llvm::dbgs() << "MemRegion::getAsArrayOffset: "
+                             << "offset overflowing, returning unknown\n");
+
+          return nullptr;
+        }
+
         offset += (i * size);
       }
 
diff --git a/clang/test/Analysis/region-store.cpp b/clang/test/Analysis/region-store.cpp
index cb49f48..ab179ce 100644
--- a/clang/test/Analysis/region-store.cpp
+++ b/clang/test/Analysis/region-store.cpp
@@ -25,4 +25,4 @@ int radar13445834(Derived *Builder, Loc l) {
   Builder->setLoc(l);
   return Builder->accessBase();
   
-}
\ No newline at end of file
+}
diff --git a/clang/test/Analysis/region_store_overflow.c b/clang/test/Analysis/region_store_overflow.c
new file mode 100644
index 0000000..81acd41
--- /dev/null
+++ b/clang/test/Analysis/region_store_overflow.c
@@ -0,0 +1,13 @@
+// REQUIRES: asserts
+// RUN: %clang_analyze_cc1 -analyze -analyzer-checker=core -mllvm -debug %s 2>&1 | FileCheck %s
+
+int **h;
+int overflow_in_memregion(long j) {
+  for (int l = 0;; ++l) {
+    if (j - l > 0)
+      return h[j - l][0]; // no-crash
+  }
+  return 0;
+}
+// CHECK: {{.*}}
+// CHECK: MemRegion::getAsArrayOffset: offset overflowing, returning unknown
-- 
2.7.4