[analyzer] Avoid checking addrspace pointers in cstring checker

[vabridgers]

Summary

This change fixes an assert that occurs in the SMT layer when refuting a
finding that uses pointers of two different sizes. This was found in a
downstream build that supports two different pointer sizes, The CString
Checker was attempting to compute an overlap for the 'to' and 'from'
pointers, where the pointers were of different sizes.

In the downstream case where this was found, a specialized memcpy
routine patterned after memcpy_special is used. The analyzer core hits
on this builtin because it matches the 'memcpy' portion of that builtin.
This cannot be duplicated in the upstream test since there are no
specialized builtins that match that pattern, but the case does
reproduce in the accompanying LIT test case. The amdgcn target was used
for this reproducer. See the documentation for AMDGPU address spaces here
https://llvm.org/docs/AMDGPUUsage.html#address-spaces.

The assert seen is:

`*Solver->getSort(LHS) == *Solver->getSort(RHS) && "AST's must have the same sort!"'

Ack to steakhal for reviewing the fix, and creating the test case.

[steakhal]

I'm wondering if we should have an assertion within the SValBuilder::evalBinOpLL() asserting that the pointers should have the same bitwidths.
That's better than having nothing, waiting for a bugreport containing such a constraint on the bugpath to get a crash with Z3 refutation.

That way we could have a chance to fix these issues for once and all.
WDYT @NoQ @martong?

clang/test/Analysis/cstring-checker-addressspace.c

14 ↗

(On Diff #402553)

Please try to trigger the test using some suffix for the memcpy.
E.g.: memcpy_host2device or something similar.

[vabridgers]

Good thoughts, I will try those things and get back to you.

[vabridgers]

• update test case
• add initial Loc bitwidth check for evalBinOpLL for review

[vabridgers]

I updated the test case after verifying I can reproduce the crash without the fix. I also experimented with adding a bitwidth check for the lhs and rhs loc parameters to evalBinOpLL, and verified this assert catches the negative (crash) case.

I explored adding a 'memcpy_special' case, but this memcpy function must be a builtin for the checker to hit on it, so I could not repro.

I realize the bitwidth check may not be ideal, but it's a start. Thanks in advance for comments. Best!

[vabridgers]

clang/test/Analysis/cstring-checker-addressspace.c

14 ↗

(On Diff #402553)

Please see latest comment. I tried this, but found a memcpy name with some suffix must be builtin. I could not find a way to repro this, but I was able to repro the negative case with the changes I just uploaded amending this review.

[steakhal]

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

718

Why don't you simply call loc->getType() end delegate the heavy lifting to that?
If you have a meaningful type, you could acquire the size of that using the ASTContext exactly how you did.

After doing so, this would reduce the complexity of checking this, so the assertion could be placed into the body of evalBinOpLL().

723–725

Remove this default case. Simply return 0; from the end of the function.
Also, I would recommend return-ing from the handled cases instead of mutating a variable.

738

What if Loc is a void*. What would be the size of that one?

744

Please have something like this in the assertion. That way we could immediately see why this is an issue.

746

assertEqualBitwidths would be probably more appropriate - even if this is a best-effort assertion.

clang/test/Analysis/cstring-checker-addressspace.c

17 ↗

(On Diff #403276)

Remove this line, it's redundant.

[NoQ]

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

728

That's a pretty big "if".

The natural way to handle the opposite case is TypedRegion::getLocationType().

You can probably go with SVal::getType() here as it happens to do the right thing (treat Loc values as if they were pointers). But, again, it's speculative.

750–751

I think this is a good, correct assertion. It is up to the AST to insert implicit casts when bit widths don't match (or outright reject the code, I've no idea what really happens in such cases, but it's up to the compiler in any case).

[vabridgers]

Thanks for the comments, I'll address. Best

[vabridgers]

I took a run at the improvements, and the rabbit hole keeps getting deeper :/ @steakhal, I'll contact you offline to work out the problems. Best

[vabridgers]

Simplify assertion per comments.
Add a "temp" fix in SValBuilder that permits the additional
test cases to pass without crash

[vabridgers]

I think @steakhal will have a more comprehensive change to back out the makeNull() calls to makeNullWithWidth() calls. I'll back out the change to SValBuilder.cpp once that change is pushed. For now, this is my update. Thanks

[vabridgers]

I think the comments have been addressed for now. Please let me know if I missed something, or anything else needs to be done (besides back out the change to SValBuilder.cpp when ready). Thanks for the comments. Best

[vabridgers]

Update after makeNull fixes

[steakhal]

Besides a couple of nits, it's ready for landing.
Thanks for the hard work @vabridgers!

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

726–727

You should probably ignore references.
Ah, but we already lost that information. Well, that's bad.
Anyway. You probably don't need to check the subkinds. Do you?

745

You don't use the return value of this call.
Can we have a void return type instead?

[vabridgers]

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

726–727

There was a case I hit in my testing where the subkinds were different and a crash occurred. I cannot recall the details at the moment, but it made sense at the time to also check subkkinds. I'll check this again so I can describe the rationale for this.

745

Yes, will do.

[vabridgers]

rebase, check ci

[vabridgers]

add NDEBUG around assert

[vabridgers]

I added #ifndef NDEBUG around the assert since I'm not sure if downstream consumers that use different pointer sizes by address space will hit this assert. Our downstream target causes this assert to fire, so I will be continuing to find and fix these issues, submitting test cases as I can. Heck, we may even have to submit a mock target to properly suss these out :)

Thanks for the support for sorting these out. Best

[vabridgers]

I need to make a few changes. Please hold off any comments until the next patch, coming soon.

[vabridgers]

make assert function void, update summary

[steakhal]

Looks great!

clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,
   // or vice versa.
 
   // If a previous check has failed, propagate the failure.
   if (!state)
     return nullptr;
 
   ProgramStateRef stateTrue, stateFalse;
 
+  // Assume different address spaces cannot overlap.
+  if (First.Expression->getType()->getPointeeType().getAddressSpace() !=
+      Second.Expression->getType()->getPointeeType().getAddressSpace())
+    return state;
+
   // Get the buffer values and make sure they're known locations.
   const LocationContext *LCtx = C.getLocationContext();
   SVal firstVal = state->getSVal(First.Expression, LCtx);
   SVal secondVal = state->getSVal(Second.Expression, LCtx);
 
   Optional<Loc> firstLoc = firstVal.getAs<Loc>();
   if (!firstLoc)
     return state;

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

if (I == LeftFD)
       return SVB.makeTruthVal(leftFirst, resultTy);
     if (I == RightFD)
       return SVB.makeTruthVal(!leftFirst, resultTy);
   }
 
   llvm_unreachable("Fields not found in parent record's definition");
 }
 
+static bool assertEqualBitWidths(ProgramStateRef State, Loc RhsLoc,
+                                 Loc LhsLoc) {
+  // Implements a "best effort" check for RhsLoc and LhsLoc bit widths
+  ASTContext &Ctx = State->getStateManager().getContext();
+  uint64_t RhsBitwidth =
+      RhsLoc.getType(Ctx).isNull() ? 0 : Ctx.getTypeSize(RhsLoc.getType(Ctx));
+  uint64_t LhsBitwidth =
+      LhsLoc.getType(Ctx).isNull() ? 0 : Ctx.getTypeSize(LhsLoc.getType(Ctx));
+  if (RhsBitwidth && LhsBitwidth &&
+      (LhsLoc.getSubKind() == RhsLoc.getSubKind())) {
+    assert(RhsBitwidth == LhsBitwidth &&
+           "RhsLoc and LhsLoc bitwidth must be same!");
+    return RhsBitwidth == LhsBitwidth;
+  }
+  return false;
+}
+
 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
                                   BinaryOperator::Opcode op,
                                   Loc lhs, Loc rhs,
                                   QualType resultTy) {
+
+  // Assert that bitwidth of lhs and rhs are the same.
+  // This can happen if two different address spaces are used,
+  // and the bitwidths of the address spaces are different.
+  // See LIT case clang/test/Analysis/cstring-checker-addressspace.c
+  assertEqualBitWidths(state, rhs, lhs);
+
   // Only comparisons and subtractions are valid operations on two pointers.
   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
   // However, if a pointer is casted to an integer, evalBinOpNN may end up
   // calling this function with another operation (PR7527). We don't attempt to
   // model this for now, but it could be useful, particularly when the
   // "location" is actually an integer value that's been passed through a void*.
   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
     return UnknownVal();
 
   // Special cases for when both sides are identical.
   if (lhs == rhs) {
     switch (op) {
     default:

clang/test/Analysis/cstring-addrspace.c

+// RUN: %clang_analyze_cc1 -triple amdgcn-unknown-unknown \
+// RUN: -analyze -analyzer-checker=core,alpha.unix.cstring \
+// RUN: -analyze -analyzer-checker=debug.ExprInspection \
+// RUN: -analyzer-config crosscheck-with-z3=true -verify %s \
+// RUN: -Wno-incompatible-library-redeclaration
+// REQUIRES: z3
+
+void clang_analyzer_warnIfReached();
+
+// From https://llvm.org/docs/AMDGPUUsage.html#address-spaces,
+// select address space 3 (local), since the pointer size is
+// different than Generic.
+#define DEVICE __attribute__((address_space(3)))
+_Static_assert(sizeof(int *) == 8, "");
+_Static_assert(sizeof(DEVICE int *) == 4, "");
+_Static_assert(sizeof(void *) == 8, "");
+_Static_assert(sizeof(DEVICE void *) == 4, "");
+
+// Copy from host to device memory. Note this is specialized
+// since one of the parameters is assigned an address space such
+// that the sizeof the the pointer is different than the other.
+//
+// Some downstream implementations may have specialized memcpy
+// routines that copy from one address space to another. In cases
+// like that, the address spaces are assumed to not overlap, so the
+// cstring overlap check is not needed. When a static analysis report
+// is generated in as case like this, SMTConv may attempt to create
+// a refutation to Z3 with different bitwidth pointers which lead to
+// a crash. This is not common in directly used upstream compiler builds,
+// but can be seen in specialized downstrean implementations. This case
+// covers those specific instances found and debugged.
+//
+// Since memcpy is a builtin, a specialized builtin instance named like
+// 'memcpy_special' will hit in cstring, triggering this behavior. The
+// best we can do for an upstream test is use the same memcpy function name.
+DEVICE void *memcpy(DEVICE void *dst, const void *src, unsigned long len);
+
+void top1(DEVICE void *dst, void *src, int len) {
+  memcpy(dst, src, len);
+
+  // Create a bugreport for triggering Z3 refutation.
+  clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void top2(DEVICE int *dst, void *src, int len) {
+  memcpy(dst, src, len);
+
+  // Create a bugreport for triggering Z3 refutation.
+  clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void top3(DEVICE int *dst, int *src, int len) {
+  memcpy(dst, src, len);
+
+  // Create a bugreport for triggering Z3 refutation.
+  clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void top4() {
+  memcpy((DEVICE void *)1, (const void *)1, 1);
+
+  // Create a bugreport for triggering Z3 refutation.
+  clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}