[analyzer] Wrong type cast occures during pointer dereferencing after type punning

[ASDenysPetrov]

Summary

During pointer dereferencing CastRetrievedVal uses wrong type from the Store after type punning. Namely, the pointer casts to another type and then assigns with a value of one more another type. It produces NonLoc value when Loc is expected.

Example for visibility:

void foo(char ***c, int *i) {
  *(unsigned**)c = (unsigned*)i; // type punning
  ***c; // uses 'unsigned**' from the Store instead of 'char***'
}

Fixes:
https://bugs.llvm.org/show_bug.cgi?id=37503
https://bugs.llvm.org/show_bug.cgi?id=49007

[NoQ]

This actually looks correct to me but i suggest a bit more investigation. Architecturally, it doesn't make sense to me that CastRetrievedVal() does anything beyond svalBuilder.dispatchCast(V, castTy). After all, there's only one way to cast a value from one type to another, and dispatchCast() was supposed to be the ultimate method to do so.

Can we collapse this function further towards this goal? Say, why not pump every region unconditionally through castRegion()? Does dispatchCast() use castRegion() internally - and if it does, why are there so many branches in this function?

[ASDenysPetrov]

@NoQ

Can we collapse this function further towards this goal? Say, why not pump every region unconditionally through castRegion()? Does dispatchCast() use castRegion() internally - and if it does, why are there so many branches in this function?

Thank you for raising such a good questions :)
Honestly, I spent a week debugging to undersand what's going on in the Store, I never had a chance to dig into it before. It was tough. I'll proceed this to try to make what you mentioned.

The thing I'm sure that the type of retrieved value should be the same as the type of which this value was declared? In other words we can unconditionally cast all the values, can't we? Is there any case that contradicts me?

[ASDenysPetrov]

@NoQ
BTW, what do you think we should do with D77062 and D88477 then?

[steakhal]

If you don't mind I would also request some credit in the summary since I've spent some time on this as well.
Besides that I don't have much objection about this patch. It's defenately not my expertiese.
Good job coming up with the fix though, I had to focus on other things.

clang/test/Analysis/string.c

367–373

I would prefer slightly more readbale names.
func_strcpy_no_assertion() -> get_void_ptr()
ptr_strcpy_no_assertion -> type_punned_ptr
no-assertion -> no-crash
You could also hoist the char a as a function parameter to spare a line :)

[ASDenysPetrov]

Updat patch due to suggestions and fixed formating.

Proceeding work on improving solution by moving the logic inside SimpleSValBuilder::dispatchCast.

[ASDenysPetrov]

Updated. Removed a new test file, moved the test to an existing file instead.

[ASDenysPetrov]

@NoQ

Can we collapse this function further towards this goal? Say, why not pump every region unconditionally through castRegion()? Does dispatchCast() use castRegion() internally - and if it does, why are there so many branches in this function?

I've made some investigations. castRegion() does not use inside dispatchCast(), it belongs to StoreManager. Moving it to SimpleSValBuilder will be hard at least for now, since it is quite complex, but we can try. What do you think. Should I go further or we can apply this patch as is?

[ASDenysPetrov]

Updated. Moved castRegion() from StoreManager to SValBuilder.

Actually it wasn't so hard as I thought :)
Would it be better to make this moving in a separate patch as [NFC]?

[NoQ]

Aha, great, sounds like all casting can be made more correct, not just casting on store retrieve! Maybe it's worth celebrating through extra unittests on evalCast(). Thank you for looking into this.

The new code should obviously be restricted into evalCastFromLoc() because if it's a region it's a Loc.

You didn't need to move castRegion(): StoreManager is available in SValBuilder through this->StateMgr. I don't have a strong preference on where castRegion() should live; the original idea was that StoreManager should be allowed to have an opinion on this matter because different store managers would handle that differently; however, as of now there's only one store manager and there doesn't seem to be an interest in introducing more of them whereas the abstraction has already leaked all over the place anyway.

I still have questions about the extra if-statements that you've added. Shouldn't we do castRegion() unconditionally, given that we're trying to cast a region and that function presumably does exactly that? I just want to avoid these situations:

In D89055#2320363, @NoQ wrote:

dispatchCast() was supposed to be the ultimate method to do so

Ugh, sorry, no, that's evalCast(). Like evalBinOp() etc. My bad. Can we also use evalCast()?

[ASDenysPetrov]

@NoQ

The new code should obviously be restricted into evalCastFromLoc() because if it's a region it's a Loc.

The first I tryed was evalCastFromLoc(), but it turned out that SVal which binds to a pointer can be NonLoc as well through violation of pointing levels.
Look here:

void foo(int** p) { // here is a two-level pointer
   *(int*)p = 42; // pretend as a one-level pointer, dereference it and assign a number
   *p; // dereferencing once gives a `nonloc::ConcreteInt`, though it actually should be a one-level pointer aka Loc.
}

P.S. I can have miscomprehension of this, due to a lack of experience, but this is what I observed.

Shouldn't we do castRegion() unconditionally,

I've also tryed and got 10+ tests unpassed. Didn't dig deeper, just refused this idea.

Can we also use evalCast() ?

Do you mean to move castRegion() to evalCast() instead of dispatchCast(). I can investigate this.
Could you explain please what is a major difference between evalCast() and dispatchCast()?

[ASDenysPetrov]

In D89055#2336709, @NoQ wrote:

Ugh, sorry, no, that's evalCast(). Like evalBinOp() etc. My bad. Can we also use evalCast()?

I dived into evalCast(). Initially I had to figure it out and rework it to find the right place to put the fix in. You are welcome to review D90157 as a parent revision.

[ASDenysPetrov]

@NoQ

Ugh, sorry, no, that's evalCast(). Like evalBinOp() etc. My bad. Can we also use evalCast()?

Finally :-) Now we can use evalCast() instead of CastRetrievedVal(). It would be nice if you could look at D96090.

I made a stack of four patches to resolve bugs of this revision.

[ASDenysPetrov]

Updated. Rolled the fix over the evalCast refactoring.

[steakhal]

I'm looking forward to this patch.

clang/test/Analysis/string.c

367–373

I think this is 'done'. :)

[ASDenysPetrov]

@NoQ, @steakhal, @vsavchenko
I think we have met all the conditions with previous patchs to make this patch acceptable.
If you think it's OK, could you, please, approve it?

[NoQ]

This looks like the fix is in the right place and it looks more or less how I expected it to look. Our casting procedure hopefully became more correct and now we have more correct analysis everywhere. It's still hard to tell whether this ElementRegion should be there or not, given how nobody still knows why they're there and when exactly should they be there; the very representation of casted pointers still needs a major rework. But we get there when we get there. Thanks a lot for debugging and digging and refactoring along the way.

[bjope]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

765 ↗

(On Diff #341327)

This caused some problems with assertion failures, see https://bugs.llvm.org/show_bug.cgi?id=50179

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

765 ↗

(On Diff #341327)

Yes, you are right. Thanks for the catch. The fix has already been loaded. D101635

[chrish_ericsson_atx]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

763–765 ↗

(On Diff #341327)

This causes new false-positive static analysis warnings from core.CallAndMessage and core.UndefinedBinaryOperatorResult, (and possibly others?), possibly because of loss of array extent information. See https://bugs.llvm.org/show_bug.cgi?id=50604.

clang/lib/StaticAnalyzer/Core/Store.cpp

SVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R,
   // When retrieving symbolic pointer and expecting a non-void pointer,
   // wrap them into element regions of the expected type if necessary.
   // SValBuilder::dispatchCast() doesn't do that, but it is necessary to
   // make sure that the retrieved value makes sense, because there's no other
   // cast in the AST that would tell us to cast it to the correct pointer type.
   // We might need to do that for non-void pointers as well.
   // FIXME: We really need a single good function to perform casts for us
   // correctly every time we need it.
-  if (castTy->isPointerType() && !castTy->isVoidPointerType())
+  if (castTy->isPointerType() && !castTy->isVoidPointerType()) {
     if (const auto *SR = dyn_cast_or_null<SymbolicRegion>(V.getAsRegion())) {
       QualType sr = SR->getSymbol()->getType();
       if (!hasSameUnqualifiedPointeeType(sr, castTy))
-          return loc::MemRegionVal(castRegion(SR, castTy));
     }
+    // Next fixes pointer dereference using type different from its initial one.
+    // See PR37503 for details
+    if (const auto *SR = dyn_cast_or_null<ElementRegion>(V.getAsRegion()))
+      return loc::MemRegionVal(castRegion(SR, castTy));
+  }
 
   return svalBuilder.dispatchCast(V, castTy);
 }
 
 SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) {
   if (Base.isUnknownOrUndef())
     return Base;
 

clang/test/Analysis/casts.c

double no_crash_reinterpret_double_as_sym_int(double a, int b) {
   return a * a;
 }
 
 double no_crash_reinterpret_double_as_sym_ptr(double a, void * b) {
   *(void **)&a = b;
   return a * a;
 }
 
+void no_crash_reinterpret_char_as_uchar(char ***a, int *b) {
+  *(unsigned char **)a = (unsigned char *)b;
+  if (**a == 0) // no-crash
+    ;
+}

clang/test/Analysis/string.c

 #endif
 
 void strcpy_no_overflow(char *y) {
   char x[4];
   if (strlen(y) == 3)
     strcpy(x, y); // no-warning
 }
 
+// PR37503
+void *get_void_ptr();
+char ***type_punned_ptr;
+void strcpy_no_assertion(char c) {
+  *(unsigned char **)type_punned_ptr = (unsigned char *)(get_void_ptr());
+  strcpy(**type_punned_ptr, &c); // no-crash
+}
+
 //===----------------------------------------------------------------------===
 // stpcpy()
 //===----------------------------------------------------------------------===
 
 #ifdef VARIANT
 
 #define __stpcpy_chk BUILTIN(__stpcpy_chk)
 char *__stpcpy_chk(char *restrict s1, const char *restrict s2, size_t destlen);