[analyzer] Fix extraction of punned and known scalar SVals

[vabridgers]

Summary

This change addresses punning of scalar types in static analysis, and is
a precursor to handling the following two cases:

https://bugs.llvm.org/show_bug.cgi?id=39032
https://bugs.llvm.org/show_bug.cgi?id=44114

This patch was co-authored with Balazs Benics (steakhal), and debug
assistance from Gabor Marton (martong).

Region store is taught to recognize punned concrete integers and extract
the data in an endianess correct way for scalars.

Co-authored-by: Balazs Benics <[e-mail]>

[vabridgers]

Clean up a few typos

[vabridgers]

Update commit header.

[vabridgers]

This proposed change seems to address the referenced issues (https://bugs.llvm.org/show_bug.cgi?id=39032 and https://bugs.llvm.org/show_bug.cgi?id=44114). I believe the scalars test cases to be mostly complete, and the structures test cases to be at most a baseline (just based on covering specific cases mentioned in the bug reports). Please let me know how to improve through review comments and I'll work on that. Thanks to Balazs, Gabor, Artem and Denis for feedback in the email thread and help working through this.

[vabridgers]

Reduce scope of this initial change to just scalars

[vabridgers]

Based on a suggestion from Balazs, I reduced the scope of the initial change to just scalars. There is one issue I'd like to hear comments on, and that's how to handle the case of extracting a bit field outside of the represented APInt. Currently, I'm returning UnknownVal(), following the lead in RegionStore.cpp, line 1775, in method getBindingForElement. During development, I hit an assert in extractBits when encountering a "negative" case exposed by the LIT ptr-arith.cpp - the negative case being an index out of bounds of the punned scalar (see the LIT I added for the negative cases).

Based on this change, some of the basic structure cases are "working" (meaning not showing false results), but the change is probably not comprehensive enough, and definitely not covered well enough by tests, so focusing just on scalars for now. I'm willing to work on this collaboratively to solve these problems, since we encounter these analyzing our source code.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1657

I added this if to handle the case of something like this:

unsigned short sh = 0x1122;
unsigned char *p = (unsigned char *)&sh;

unsigned char aa = p[0]; // This is ok, and will yield 0x11 or 0x22 - depending on endianess.
unsigned char ch = p[3]; // This is an error and should be caught.

I opted with returning UnknownVal() following the lead in RegionStore.cpp:1775 (just below). The negative test cases I added assume this. The ptr-arith.cpp LIT exposed this issue. Otherwise, I hit an assert in extractBits that the bit field is outside of represented range in the APInt.

[NoQ]

I think you've found a very nice and compact 50% solution to the problem. I didn't think of this while i was looking for a proper fix. Very nice.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1629–1631

Let's write down the contract of this method. Do i understand correctly that for a given region R and offset O, you're trying to lookup an element of type elemT at offset O while knowing that R has binding V at offset zero?

1634

Please feel free to add this as a method on SVal, with a comment that this method does not take constraints in the current program state into account.

1648

This assignment can overflow. Both because the raw offset can be very large and because it can be negative.

Say, the following code compiles just fine (and may even run) so we need to be able to analyze it but you dodge that by always checking that the base type is a scalar type (if you intend to keep it that way i'd rather assert that; the other reason to assert that would be because endianness logic is screwed without it):

int main() {
  int x[5000000000]; // Over 2³² elements.
  x[0] = 1;
  char *y = &x;
  char c = y[19999999999];
}

The following code is valid but you seem to be protected from it because you dodge SymbolicRegions by checking that R is a TypedValueRegion:

void foo(int *x) {
  long *y = (long *)(x - 1);
  y = 1;
  char c = *(char *)y;
}

The following code has an obvious UB but it still compiles so you have to make sure the analyzer behaves sanely:

void foo() {
  int x;
  long *y = (long *)(x - 1);
  y = 1;
  char c = *(char *)y;
}

1653–1654

The ConcreteValue->getBitWidth() part is the only thing that you can't generalize to arbitrary values for now. Fundamentally, any symbolic value has an intrinsic width (and, moreover, almost an intrinsic type) that you should be able to compute by just looking at the value. For now we can't rely on that though, because our values for integral casts over symbols aren't represented correctly, and we can't represent them correctly without a proper constraint solver to solve the resulting constraints.

So a good temporary solution would be to proactively store widths together with bindings. I.e., instead of "In region R at offset O we have value X" we could write down "In region R from offset O to offset O' we have value X". That'd bulk up the RegionStore and make some operations more difficult but it will solve the problem entirely.

clang/test/Analysis/concrete-endian.cpp

49

I suspect that exactly one of pps[0] in the little endian case or pps[3] in the big endian case should be 0x7788 instead. Like, they're in the opposite order, right?

[NoQ]

clang/test/Analysis/concrete-endian.cpp

49

Wait, loads are also in the opposite order. Nvm. Your code is correct and looks like there's indeed a nice and succint way to do that.

[NoQ]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1648

(I see that you brought this up and tested it but overflows are still scary. If you're consciously relying on an overflow you should probably at least comment that.)

clang/test/Analysis/concrete-endian.cpp

56

Ideally no they shouldn't, they should yield Undefined. I'd rather mark it as FIXME: because ultimately we could have a warning here. It's ok if we miss these cases for now though.

[vabridgers]

Thanks for the comments, @NoQ . I'll carefully review and update. BTW, I found an old Bugzilla case that seems to relate to this change directly -> https://bugs.llvm.org/show_bug.cgi?id=2820. Once this change is evolved and accepted, I'll update that Bugzilla issue and close. Cheers!

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
     if (Result.second)
       Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
                                                             Result.second);
   }
 
   return Result;
 }
 
+static SVal getSValAsConcreteInt(SValBuilder &SVB, SVal V, QualType baseT,
+                                 QualType elemT,
+                                 const RegionRawOffset &ORegionRawOffs) {
+  ASTContext &Ctx = SVB.getContext();
+
+  const llvm::APSInt *ConcreteValue = [&V](SVal Val) {
+    if (auto Int = V.getAs<nonloc::ConcreteInt>())
+      return &Int->getValue();
+    return &V.getAs<loc::ConcreteInt>()->getValue();
+  }(V);
+  assert(ConcreteValue);
+
+  const unsigned bitPosition = [&]() {
+    unsigned bitPos;
+    if (Ctx.getTargetInfo().isBigEndian())
+      bitPos = (Ctx.getTypeSizeInChars(baseT).getQuantity() -
+                Ctx.getTypeSizeInChars(elemT).getQuantity()) -
+               ORegionRawOffs.getOffset().getQuantity();
+    else
+      bitPos = ORegionRawOffs.getOffset().getQuantity();
+    return bitPos * Ctx.getCharWidth();
+  }();
+  const unsigned numBits =
+      Ctx.getCharWidth() * Ctx.getTypeSizeInChars(elemT).getQuantity();
+  if (bitPosition < ConcreteValue->getBitWidth() &&
+      (numBits + bitPosition) <= ConcreteValue->getBitWidth()) {
+    llvm::APInt bits = ConcreteValue->extractBits(numBits, bitPosition);
+    return SVB.makeIntVal(bits, true);
+  }
+  return UnknownVal();
+}
+
 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
                                               const ElementRegion* R) {
   // Check if the region has a binding.
-  if (const Optional<SVal> &V = B.getDirectBinding(R))
+  if (const Optional<SVal> &V = B.getDirectBinding(R)) {
+    if (V->isConstant()) {
+      const RegionRawOffset &O = R->getAsArrayOffset();
+      if (const TypedValueRegion *baseR =
+              dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
+        QualType baseT = baseR->getValueType();
+        if (baseT->isScalarType()) {
+          QualType elemT = R->getElementType();
+          if (elemT->isScalarType())
+            return getSValAsConcreteInt(svalBuilder, *V, baseT, elemT, O);
+        }
+      }
+    }
     return *V;
+  }
 
   const MemRegion* superR = R->getSuperRegion();
 
   // Check if the region is an element region of a string literal.
   if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
     // FIXME: Handle loads from strings where the literal is treated as
     // an integer, e.g., *((unsigned int*)"hello")
     QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
if (baseT->isScalarType()) {
       if (elemT->isScalarType()) {
         if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
           if (const Optional<SVal> &V = B.getDirectBinding(superR)) {
             if (SymbolRef parentSym = V->getAsSymbol())
               return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
 
             if (V->isUnknownOrUndef())
               return *V;
+
+            if (V->isConstant())
+              return getSValAsConcreteInt(svalBuilder, *V, baseT, elemT, O);
+
             // Other cases: give up.  We are indexing into a larger object
             // that has some value, but we don't know how to handle that yet.
             return UnknownVal();
           }
         }
       }
     }
   }

clang/test/Analysis/concrete-endian.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -triple x86_64-unknown-linux-gnu -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -triple powerpc64-unknown-linux-gnu  -verify %s
+
+void clang_analyzer_dump(int);
+void clang_analyzer_eval(int);
+
+int testLocConcreteInts() {
+  static_assert(sizeof(char) == 1, "test assumes sizeof(char) is 1");
+  static_assert(sizeof(short) == 2, "test assumes sizeof(short) is 2");
+  static_assert(sizeof(int) == 4, "test assumes sizeof(int) is 4");
+  static_assert(sizeof(long) == 8, "test assumes sizeof(long) is 8");
+  static_assert(sizeof(long *) == 8, "test assumes sizeof(long *) is 8");
+  long *p = (long *)0x11223344AA998877ULL;
+  unsigned char *ppb = (unsigned char *)&p;
+  unsigned short *pps = (unsigned short *)&p;
+  unsigned int *ppi = (unsigned int *)&p;
+
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(ppb[0] == 0x77); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[1] == 0x88); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[2] == 0x99); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[3] == 0xaa); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[4] == 0x44); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[5] == 0x33); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[6] == 0x22); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[7] == 0x11); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(ppb[7] == 0x77);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[6] == 0x88);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[5] == 0x99);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[4] == 0xaa);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[3] == 0x44);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[2] == 0x33);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[1] == 0x22);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppb[0] == 0x11);        // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(ppb[8]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(ppb[-1]); // expected-warning{{UNKNOWN}}
+
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(pps[0] == 0x8877); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pps[1] == 0xaa99); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pps[2] == 0x3344); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pps[3] == 0x1122); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(pps[3] == 0x8877);      // expected-warning{{TRUE}}
+  clang_analyzer_eval(pps[2] == 0xaa99);      // expected-warning{{TRUE}}
+  clang_analyzer_eval(pps[1] == 0x3344);      // expected-warning{{TRUE}}
+  clang_analyzer_eval(pps[0] == 0x1122);      // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(pps[4]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(pps[-1]); // expected-warning{{UNKNOWN}}
+
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(ppi[0] == 0xaa998877); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppi[1] == 0x11223344); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(ppi[0] == 0x11223344);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(ppi[1] == 0xaa998877);  // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(ppi[2]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(ppi[-1]); // expected-warning{{UNKNOWN}}
+
+  return 0;
+}
+
+int testNonlocConcreteInts() {
+  static_assert(sizeof(char) == 1, "test assumes sizeof(char) is 1");
+  static_assert(sizeof(short) == 2, "test assumes sizeof(short) is 2");
+  static_assert(sizeof(int) == 4, "test assumes sizeof(int) is 4");
+  static_assert(sizeof(long) == 8, "test assumes sizeof(long) is 8");
+  static_assert(sizeof(long *) == 8, "test assumes sizeof(long *) is 8");
+
+  unsigned short sh = 0x1122;
+  unsigned char *pbsh = (unsigned char *)&sh;
+
+  unsigned int i = 0x11223344;
+  unsigned char *pbi = (unsigned char *)&i;
+  unsigned short *psi = (unsigned short *)&i;
+
+  unsigned long ll = 0x11223344AA998877ULL;
+  unsigned char *pbll = (unsigned char *)≪
+  unsigned short *psll = (unsigned short *)≪
+  unsigned int *pill = (unsigned int *)≪
+
+  // Uses built macro to determine endianess.
+  // Use "clang -dM -E -x c /dev/null" to dump macros.
+  // This test uses __LITTLE_ENDIAN__ and __BIG_ENDIAN__
+
+  // First, the short endianess test section
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(pbsh[0] == 0x22); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbsh[1] == 0x11); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(pbsh[0] == 0x11);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbsh[1] == 0x22);       // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(pbsh[2]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(pbsh[-1]); // expected-warning{{UNKNOWN}}
+
+  // The "int" endianess test section
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(pbi[0] == 0x44); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbi[1] == 0x33); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbi[2] == 0x22); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbi[3] == 0x11); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(pbi[3] == 0x44);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbi[2] == 0x33);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbi[1] == 0x22);        // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbi[0] == 0x11);        // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(pbi[4]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(pbi[-1]); // expected-warning{{UNKNOWN}}
+
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(psi[0] == 0x3344); // expected-warning{{TRUE}}
+  clang_analyzer_eval(psi[1] == 0x1122); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(psi[1] == 0x3344);      // expected-warning{{TRUE}}
+  clang_analyzer_eval(psi[0] == 0x1122);      // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(psi[2]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(psi[-1]); // expected-warning{{UNKNOWN}}
+
+  // The "long" endianess test section
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(pbll[0] == 0x77); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[1] == 0x88); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[2] == 0x99); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[3] == 0xaa); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[4] == 0x44); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[5] == 0x33); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[6] == 0x22); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[7] == 0x11); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(pbll[7] == 0x77);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[6] == 0x88);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[5] == 0x99);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[4] == 0xaa);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[3] == 0x44);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[2] == 0x33);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[1] == 0x22);       // expected-warning{{TRUE}}
+  clang_analyzer_eval(pbll[0] == 0x11);       // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(pbll[8]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(pbll[-1]); // expected-warning{{UNKNOWN}}
+
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(psll[0] == 0x8877); // expected-warning{{TRUE}}
+  clang_analyzer_eval(psll[1] == 0xaa99); // expected-warning{{TRUE}}
+  clang_analyzer_eval(psll[2] == 0x3344); // expected-warning{{TRUE}}
+  clang_analyzer_eval(psll[3] == 0x1122); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(psll[3] == 0x8877);     // expected-warning{{TRUE}}
+  clang_analyzer_eval(psll[2] == 0xaa99);     // expected-warning{{TRUE}}
+  clang_analyzer_eval(psll[1] == 0x3344);     // expected-warning{{TRUE}}
+  clang_analyzer_eval(psll[0] == 0x1122);     // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(psll[4]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(psll[-1]); // expected-warning{{UNKNOWN}}
+
+#if defined(__LITTLE_ENDIAN__)
+  clang_analyzer_eval(pill[0] == 0xaa998877); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pill[1] == 0x11223344); // expected-warning{{TRUE}}
+#elif defined(__BIG_ENDIAN__)
+  clang_analyzer_eval(pill[0] == 0x11223344); // expected-warning{{TRUE}}
+  clang_analyzer_eval(pill[1] == 0xaa998877); // expected-warning{{TRUE}}
+#else
+#error "Don't recognize the endianess of this target!"
+#endif
+  // Array out of bounds should yield UNKNOWN
+  clang_analyzer_eval(pill[2]);  // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(pill[-1]); // expected-warning{{UNKNOWN}}
+
+  return 0;
+}