[analyzer] Overwrite cast type in getBinding only if that was null originally

[steakhal]

Summary

When the analyzer loads a value through a given type which was previously stored with a different type, it will implicitly cast the associated value to the type in which we are trying to access it.
However, sometimes this implicit cast done by the CastRetrievedVal in RegionStoreManager::getBinding casted the value to a wrong type.
In this example, it cast to the unsigned char (which is the type of the stored value of **b, stored at #1) instead of the static type of the access (the type of **b is char*at #2).

If the analyzer wouldn't overwrite the already given non-null type, it would cast it to the correct one instead.
This patch simply modifies the code to overwrite the cast type to the underlying type of the pointee's region only if the type were null.

This also resolves a FIXME in the test suite.

---

This test case crashes the analyzer:

// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s
// expected-no-diagnostics

void test(int *a, char ***b, float *c) {
  *(unsigned char **)b = (unsigned char *)a; // #1
  if (**b == 0) // no-crash, #2
    ;

  *(unsigned char **)b = (unsigned char *)c;
  if (**b == 0) // no-crash
    ;
}

Thank you @ASDenysPetrov for raising this issue at D77062.

[martong]

In this example, it cast to the unsigned char (which is the type of the stored value of **b, stored at #1) instead of the static type of the access (the type of **b is charat #2).

Possible typo in the summary. At #2 the type should be char * shouldn't it?

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

1442

Nice catch!

[steakhal]

In D88477#2300687, @martong wrote:

In this example, it cast to the unsigned char (which is the type of the stored value of **b, stored at #1) instead of the static type of the access (the type of **b is charat #2).

Possible typo in the summary. At #2 the type should be char * shouldn't it?

Yup, thanks. Updated revision summary accordingly.

[NoQ]

A load from a region of type T should always yield a value of type T because that's what a load is.

I'd rather have it as an assertion: if the region is typed, the type shouldn't be specified. If such assertion is hard to satisfy, we could allow the same canonical type to be specified. But having a conflict between two sources of type information and resolving it by arbitrarily choosing one of them sounds scary and unreliable. This patch doesn't eliminate the source of the conflict, it simply changes the way we flip the coin to resolve it.

Normally then loading through a casted pointer the conflict is resolved by representing the casted pointer differently, so that the pointer appeared to be a TypedValueRegion of the correct type. Namely, it is achieved by wrapping it into an ElementRegion with index 0 and the correct type. Why didn't the same occur in this case? Do I understand correctly that L is just &b, not &ElementRegion{b, 0 S32b, unsigned char **}?

---

This is the current status quo and how the patch should probably go within it. In the long term I'd prefer to undo this entire concept of "region having a type". Most of the time memory regions in C are "kinda" typed and type punning is indeed largely problematic due to the Strict Aliasing rule (and object lifetime rules in C++) but there are always ways to bypass those rules and our idea of regions having types fails us every single time this happens. Types are at best a mutable property attached to a region (i.e., like a dynamic type map), definitely not part of its identity. Every access should be typed separately and explicitly.

[steakhal]

In D88477#2301641, @NoQ wrote:

A load from a region of type T should always yield a value of type T because that's what a load is.

I'd rather have it as an assertion: if the region is typed, the type shouldn't be specified. If such assertion is hard to satisfy, we could allow the same canonical type to be specified. But having a conflict between two sources of type information and resolving it by arbitrarily choosing one of them sounds scary and unreliable. This patch doesn't eliminate the source of the conflict, it simply changes the way we flip the coin to resolve it.

Oh, now I see. Thank you.

Normally then loading through a casted pointer the conflict is resolved by representing the casted pointer differently, so that the pointer appeared to be a TypedValueRegion of the correct type. Namely, it is achieved by wrapping it into an ElementRegion with index 0 and the correct type.

Yes, I have seen that many times, now it's clear why :)

Why didn't the same occur in this case? Do I understand correctly that L is just &b, not &ElementRegion{b, 0 S32b, unsigned char **}?

In the Summary's example, at location #2 the value of **p is &Element{SymRegion{reg_$0<int * a>},0 S64b,unsigned char} - which is exactly what we stored at line #1.

void test(int *a, char ***b, float *c) {
  *(unsigned char **)b = (unsigned char *)a; // #1
  if (**b == 0) // no-crash, #2
    ;
  // ...
}

Dereferencing this location **b would result in a typed region of type unsigned char.
I suspect that the analyzer thinks that following a type-punned pointer will point to an object of the static type - which seems reasonable to me.

However, breaks the invariant that you said. Since we have mismatching types, namely unsigned char and char* - the type of the TypedValueRegion and the explicitly specified LoadTy respectively.

[...] if the region is typed, the type shouldn't be specified.

IMO, we should relax this invariant in the following way:
If the region is typed and the type also explicitly specified, we will perform a cast to the explicitly stated type.
In other words, overwrite the LoadTy only if that was not given.

---

Another possibility could be to change the type of the region at the bind. By doing that, the Region's type would match the static type so any load afterward would use the correct static type as it should and we could assert your relaxed invariant requiring matching types when both are specified.

[NoQ]

In D88477#2303376, @steakhal wrote:

In the Summary's example, at location #2 the value of **p is &Element{SymRegion{reg_$0<int * a>},0 S64b,unsigned char} - which is exactly what we stored at line #1.

void test(int *a, char ***b, float *c) {
  *(unsigned char **)b = (unsigned char *)a; // #1
  if (**b == 0) // no-crash, #2
    ;
  // ...
}

And I believe that this part is already incorrect. Like, regardless of how we do the dereference (the implicit lvalue-to-rvalue cast), or *whether* we do it at all (nobody guarantees we'll ever do that!), the part of the static analyzer that computes the lvalue **b has to work correctly. As of now it computes an lvalue of incorrect type (currently it's unsigned char but it has to be char *).

In D88477#2303376, @steakhal wrote:

IMO, we should relax this invariant in the following way:
If the region is typed and the type also explicitly specified, we will perform a cast to the explicitly stated type.
In other words, overwrite the LoadTy only if that was not given.

This would teach the modeling of the load step for the pointee how to undo the damage done by the previous load step for the pointer. In the general case the load step for the pointee does not necessarily exist, therefore we cannot rely on it to undo the damage. This is why it's extremely important for every modeling step to be correct. You can't miss a detail on one step and account for it in another step because there's almost never a guarantee that the other step will actually have a chance to kick in.

[steakhal]

I'm getting lost :D

In D88477#2304230, @NoQ wrote:

And I believe that this part is already incorrect. Like, regardless of how we do the dereference (the implicit lvalue-to-rvalue cast), or *whether* we do it at all (nobody guarantees we'll ever do that!), the part of the static analyzer that computes the lvalue **b has to work correctly. As of now it computes an lvalue of incorrect type (currently it's unsigned char but it has to be char *).

Are you implying that when we evaluate the assignment to the lvalue (line #1), we should have cast the stored value to the static type before binding in the RegionStore?

Doesn't it contradict with your previous statement:

In D77062#2298748, @NoQ wrote:

The contract of RegionStore with respect to type punning is that it stores the value as written, even if its type doesn't match the storage type, but then it casts the value to the correct type upon reading by invoking CastRetrievedVal() on it. That's where the fix should probably be.

---

Or after evaluating the first dereference - but before evaluating the second - should we cast the lvalue to char** and only then do the LValueToRValue conversion?

[NoQ]

I'm trying to say that the value produced by the load should not be the same as the stored value, because these two values are of different types. When exactly does the first value change into the second value is a different story; the current grand vision around which the code is written says that it changes during load, therefore it's the load code (step #2) that's to blame.

[NoQ]

(in the latest message by "load" i mean the first load that produces a pointer (i.e., an ElementRegion) as the result)

[steakhal]

In D88477#2304708, @NoQ wrote:

I'm trying to say that the value produced by the load should not be the same as the stored value, because these two values are of different types. When exactly does the first value change into the second value is a different story; the current grand vision around which the code is written says that it changes during load, therefore it's the load code (step #2) that's to blame.

Are you implying that the second dereference of b should produce an lvalue of the type char *, instead of the type of the SVal &Element{SymRegion{reg_$0<int * a>},0 S64b,unsigned char}.
So, I should do this cast when we evaluate the dereference, and produce an lvalue of the static type, aka binding the SVal &Element{SymRegion{reg_$0<int * a>},0 S64b,char*} to it.
In the AST, it is the line @1:

`-IfStmt
  -BinaryOperator 'bool' '=='
   |-ImplicitCastExpr 'char *' <LValueToRValue>
@1:| `-UnaryOperator 'char *' lvalue prefix '*' cannot overflow
   |   `-ImplicitCastExpr 'char **' <LValueToRValue>
   |     `-UnaryOperator 'char **' lvalue prefix '*' cannot overflow
   |       `-ImplicitCastExpr 'char ***' <LValueToRValue>
   |         `-DeclRefExpr 'char ***' lvalue ParmVar 0x55e808fe8188 'b' 'char ***'
   | `-ImplicitCastExpr 'char *' <NullToPointer>
    `-IntegerLiteral 'int' 0

To do this, I would have to modify the ExprEngine::handleUOExtension to not just simply lookup the corresponding SVal of the Environment's ExprBindings, but also apply the cast if necessary.
Am I on the right track now?

PS: I tried to implement this, but I failed to reuse the other overloads of getSVal to accomplish this.

[NoQ]

No, you got it all wrong again. I don't want to explain this one more time so let's talk about some basics: A value of an expression should have the same type and value-kind as the expression. Can we get there? How?

[NoQ]

A value of an expression should have the same type and value-kind as the expression.

Unfortunately i'm pretty worried about our ability to actually achieve that in the near future; as of now we don't even oblige to a much simpler sanity-inducing contract that the value in the Environment never changes throughout its lifetime.

[NoQ]

i'm pretty worried about our ability to actually achieve that in the near future

This whole cast problem that you're looking into in D85528 is definitely a part of it.

[ASDenysPetrov]

@NoQ @steakhal

Hi, guys.

I've just uploaded a patch for solving this and related D77062. Welcome to review D89055.

[steakhal]

In D88477#2319959, @ASDenysPetrov wrote:

@NoQ @steakhal

Hi, guys.

I've just uploaded a patch for solving this and related D77062. Welcome to review D89055.

Abandoning in favor of D89055.
@ASDenysPetrov, please try to add the mentioned assertion into the RegionStoreManager::getBinding to make sure our invariant holds.

About the D77062, I think any NFC refactor is more then welcomed. Let's discuss about that after the fix landed.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

if (T.isNull()) {
         T = TR->getLocationType()->getPointeeType();
       else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
         T = SR->getSymbol()->getType()->getPointeeType();
     }
     assert(!T.isNull() && "Unable to auto-detect binding type!");
     assert(!T->isVoidType() && "Attempting to dereference a void pointer!");
     MR = GetElementZeroRegion(cast<SubRegion>(MR), T);
   } else {
+    if (T.isNull())
       T = cast<TypedValueRegion>(MR)->getValueType();
   }
 
   // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
   //  instead of 'Loc', and have the other Loc cases handled at a higher level.
   const TypedValueRegion *R = cast<TypedValueRegion>(MR);
   QualType RTy = R->getValueType();
 
   // FIXME: we do not yet model the parts of a complex type, so treat the

clang/test/Analysis/nonloc-as-loc-crash.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s
+// expected-no-diagnostics
+
+void test(int *a, char ***b, float *c) {
+  *(unsigned char **)b = (unsigned char *)a;
+  if (**b == 0) // no-crash
+    ;
+
+  *(unsigned char **)b = (unsigned char *)c;
+  if (**b == 0) // no-crash
+    ;
+}

clang/test/Analysis/svalbuilder-float-cast.c

 // RUN: %clang_analyze_cc1 -analyzer-checker debug.ExprInspection -verify %s
 void clang_analyzer_denote(int, const char *);
 void clang_analyzer_express(int);
 
 void SymbolCast_of_float_type_aux(int *p) {
   *p += 0;
-  // FIXME: Ideally, all unknown values should be symbolicated.
-  clang_analyzer_denote(*p, "$x"); // expected-warning{{Not a symbol}}
-
+  clang_analyzer_denote(*p, "$x");
   *p += 1;
-  // This should NOT be (float)$x + 1. Symbol $x was never casted to float.
-  // FIXME: Ideally, this should be $x + 1.
-  clang_analyzer_express(*p); // expected-warning{{Not a symbol}}
+  clang_analyzer_express(*p); // expected-warning{{$x + 1}}
 }
 
 void SymbolCast_of_float_type() {
   extern float x;
   void (*f)() = SymbolCast_of_float_type_aux;
   f(&x);
 }