[analyzer] Quickfix: do not overflow in calculating offset in RegionManager

[george.karpenkov]

Summary

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.

[dcoughlin]

lib/StaticAnalyzer/Core/MemRegion.cpp

1219

I'd really like to minimize this kind of debug logging. The comment is sufficient here.

[george.karpenkov]

lib/StaticAnalyzer/Core/MemRegion.cpp

1219

@dcoughlin it would help the next person to debug a weird issue, as analyzer does many relaxing assertions in many places. If anything, we almost never use it as the enabling flag is quite bizarre.

[dcoughlin]

We have a comment documenting the decision. Adding a printf doesn't seem like it would help very much here and adds untested code. I don't think we should have a policy of adding these printfs on every early return. Since these printfs make it harder to read the code and are duplicated with the comments, I think we should avoid adding one until we know it is actually generally useful.

Here is what I propose:

• When you are debugging an issue and found a printf helpful, only commit the DEBUG printf the *second* time you found it helpful. This will avoid prematurely littering the code with printfs and ensure that the ones that are committed are generally useful rather only helpful for debugging one specific issue.
• Add lit FileCheck tests that exercise the debug configuration and test the output. This will make sure that future refactorings and changes in behavior don't unexpectedly break the DEBUG code.

[george.karpenkov]

@dcoughlin OK.

[NoQ]

Dunno, it'd be great to come up with some systematic approach to those debug prints. Having some of them is really nice sometimes.

I also wish the informal // no-crash thingy was specifically saying that it's about not causing a UBSan error, not just a simple assertion failure or segfault that the reader would expect. Because we don't have many such tests, so the reader doesn't expect that, and a quick glimpse at the differential revision may not be enough to figure this out.

[NoQ]

LGTM otherwise!

[george.karpenkov]

...turns out the previous version had a bug. Re-introduced logging, as I've needed that for the second time for debugging.

This version is more robust, and is more obvious, but function is considerably more generic, except I don't know a good place to put it (and it can't be MathExtras, since APInt depends on that).

[george.karpenkov]

@vsk on the other hand if circular dependency between MathExtras and APInt is OK, I guess the code could be moved there.

[vsk]

In D43218#1018103, @george.karpenkov wrote:

@vsk on the other hand if circular dependency between MathExtras and APInt is OK, I guess the code could be moved there.

Sure. As I mentioned off-list, I think it would be cleaner to implement these checked operations as overloads of SaturatingAdd, SaturatingMultiply, etc. I don't anticipate a build dependency issue there.

[vsk]

lib/StaticAnalyzer/Core/MemRegion.cpp

1216

Oh, aren't sizes non-negative? Why not just cast to unsigned and use SaturatingMultiplyAdd, or something?

[george.karpenkov]

lib/StaticAnalyzer/Core/MemRegion.cpp

1216

IIRC array offsets can be negative (yay, C), and in this case i can be negative. I suppose two calls can also do, but then if it fits in unsigned it doesn't mean it fits in signed, since the underlying type is signed.

[dcoughlin]

In D43218#1018101, @george.karpenkov wrote:

...turns out the previous version had a bug. Re-introduced logging, as I've needed that for the second time for debugging.

Please make sure to add a test for the debugging output so it doesn't regress.

lib/StaticAnalyzer/Core/MemRegion.cpp

 #include "clang/AST/CharUnits.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/Support/BumpVector.h"
 #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;
 
 //===----------------------------------------------------------------------===//
 // MemRegion Construction.
 //===----------------------------------------------------------------------===//
 
const SymbolicRegion *MemRegion::getSymbolicBase() const {
   while (SubR) {
     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SubR))
       return SymR;
     SubR = dyn_cast<SubRegion>(SubR->getSuperRegion());
   }
   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;
   const MemRegion *superR = nullptr;
   ASTContext &C = getContext();
 
   // FIXME: Handle multi-dimensional arrays.
 
if (Optional<nonloc::ConcreteInt> CI = index.getAs<nonloc::ConcreteInt>()) {
 
         // If we are pointing to an incomplete type, go no further.
         if (elemType->isIncompleteType()) {
           superR = ER;
           break;
         }
 
         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);
       }
 
       // Go to the next ElementRegion (if any).
       ER = dyn_cast<ElementRegion>(superR);
       continue;
     }
 

test/Analysis/region-store.cpp

public:
   }
 };
 class Derived: public P1, public P2 {
 };
 int radar13445834(Derived *Builder, Loc l) {
   Builder->setLoc(l);
   return Builder->accessBase();
   
-}
+}
 

test/Analysis/region_store_overflow.c

+// 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