[analyzer] Handle false positives caused by funny addressing

[isuckatcs]

Summary

According to a FIXME in RegionStore.cpp the addressing below is referred to as
funny addressing.

int x = ...;
int *p = &x;
char *q = (char*) p;
char c = *q;  // returns the first byte of 'x'.

This addressing is a source of false positives at the moment. Look at the following
snippet:

struct S
{
    uint8_t x = 0;
    uint8_t arr[7];
};

int main()
{
    S P[1];

    memset(P->arr, 0, sizeof(P->arr));
    const uint8_t *p = (const uint8_t *)(P);
    auto v = p[2];                                               <-- uninitialized assign reported!

    return 0;
}

In this example p[2] points to the same place as P[0].arr[1], so it's value is 0,
however the analyzer cannot read that properly and reads it as Undefined instead.

This patch attempts do detect some cases of overlapping memory access, and fall back
to Unknown values in such cases even if we lose information, to reduce the amount of
false positives.

I also wonder if we want to create a checker to handle this instead.

[isuckatcs]

Added support for record types

[isuckatcs]

Added more detail to one of the testcases.

clang/test/Analysis/array-punned-region.c

23

This is also a false positive, look at https://godbolt.org/z/Go778dhza.

[steakhal]

This is indeed a problem. Strict aliasing violations are not well handled.
The 'assignment' should have never happened in the first place.

That being said, I believe we should focus on fixing the root cause, instead of suppressing the symptom.
In our case, the two pointers should refer to the same memory region, thus referring to the same bindings in the store.
@ASDenysPetrov had an early prototype (D114718) for detecting strict-aliasing issues, which seemed pretty good.

Strangely enough, the &q[2] == &s.arr[1] is true in the following example, yet we cannot recover the bindings.
https://godbolt.org/z/KqWK81P8K
This is the bug you are about I think.

[isuckatcs]

That being said, I believe we should focus on fixing the root cause, instead of suppressing the symptom.

I agree with fixing the root cause, though I think that means coming up with a new memory model, and a new store implementation.
The problem here is that we can't map one memory region to another. Let's stick to the original example with some modification:

struct S
{
    uint8_t x = 0;
    uint8_t arr[7];
};

int main()
{
    S P[1];

    memset(P->arr, 0, sizeof(P->arr));
    
    const uint8_t *p = (const uint8_t *)(P);

    auto x = p[0];
    auto y = p[1];
    auto z = p[2];

    return 0;
}

After memset the store looks like this:

{ "cluster": "P", "items": [
  { "kind": "Default", "offset": 8, "value": "conj_$1{uint8_t, LC1, S889556, #1}" },
  { "kind": "Direct", "offset": 0, "value": "0 U8b" }
]}

And the variables are:

{ "cluster": "x", "items": [
  { "kind": "Direct", "offset": 0, "value": "0 U8b" }
]},
{ "cluster": "y", "items": [
  { "kind": "Direct", "offset": 0, "value": "conj_$1{uint8_t, LC1, S889556, #1}" }
]}
{ "cluster": "z", "items": [
  { "kind": "Direct", "offset": 0, "value": "Undefined" }
]}

In case of p we basically treat the memory as if it was raw memory. We can't tell if p[2] is part of the array region or not, so we
also can't tell if it's value is the Default binding, or Undefined. Since we don't know where the end of the region is, there's no way
to solve this problem at the moment. For example, how can we come up with the conclusion that p[7] is still initialized, but p[8] is not?

If we read the values using array access, we still face the problem above, but at least we can tell the analyzer to use the Default binding,
instead of Undefined.

auto y = P[0].arr[0];
auto z = P[0].arr[1];

So the resulting values are:

{ "cluster": "y", "items": [
  { "kind": "Direct", "offset": 0, "value": "derived_$2{conj_$1{uint8_t, LC1, S889556, #1},Element{Element{P,0 S64b,struct S}.arr,0 S64b,unsigned char}}" }
]},
{ "cluster": "z", "items": [
  { "kind": "Direct", "offset": 0, "value": "derived_$3{conj_$1{uint8_t, LC1, S889556, #1},Element{Element{P,0 S64b,struct S}.arr,1 S64b,unsigned char}}" }
]}

(I think these values aren't necessarily correct either.)

@ASDenysPetrov had an early prototype (D114718) for detecting strict-aliasing issues, which seemed pretty good.

I can think of something similar instead of this patch. It would detect if a C-style cast changes the type, and set the result to Unknown in such cases.
Though that would lead to more information loss as we have know. For example p would be Unknown and we couldn't read p[0].

[steakhal]

In D130491#3679321, @isuckatcs wrote:

That being said, I believe we should focus on fixing the root cause, instead of suppressing the symptom.

I agree with fixing the root cause, though I think that means coming up with a new memory model, and a new store implementation.
The problem here is that we can't map one memory region to another. Let's stick to the original example with some modification:

struct S
{
    uint8_t x = 0;
    uint8_t arr[7];
};

int main()
{
    S P[1];

    memset(P->arr, 0, sizeof(P->arr));
    
    const uint8_t *p = (const uint8_t *)(P);

    auto x = p[0];
    auto y = p[1];
    auto z = p[2];

    return 0;
}

After memset the store looks like this:

{ "cluster": "P", "items": [
  { "kind": "Default", "offset": 8, "value": "conj_$1{uint8_t, LC1, S889556, #1}" },
  { "kind": "Direct", "offset": 0, "value": "0 U8b" }
]}

And the variables are:

{ "cluster": "x", "items": [
  { "kind": "Direct", "offset": 0, "value": "0 U8b" }
]},
{ "cluster": "y", "items": [
  { "kind": "Direct", "offset": 0, "value": "conj_$1{uint8_t, LC1, S889556, #1}" }
]}
{ "cluster": "z", "items": [
  { "kind": "Direct", "offset": 0, "value": "Undefined" }
]}

x is correct, y is not. It should have been a derived region of conj1. That being said, the type of conj1 is uint8_t, which is also bad. It should have been utin8_t[7] I think.
Consequently, z should have been a derived symbol, just like for y, but with a different offset.

In case of p we basically treat the memory as if it was raw memory. We can't tell if p[2] is part of the array region or not, so we
also can't tell if it's value is the Default binding, or Undefined. Since we don't know where the end of the region is, there's no way
to solve this problem at the moment.

We track the origin of the memory regions as you do; hence there are no limitations there.
p is &Element{P,0 S64b,unsigned char}, which basically encodes that we are looking at the memregion of P, but as an uint8_t type.

For example, how can we come up with the conclusion that p[7] is still initialized, but p[8] is not?

p + 7 is represented as &Element{P,7 S64b,unsigned char}, thus p[7] would access the 7th byte of the memregion P - which is aliasing with the P[0].arr[6].
At this point we should look at the store and look for bindings.

{ "cluster": "P", "pointer": "0x557b6037eb40", "items": [
  { "kind": "Default", "offset": 8, "value": "conj_$0{unsigned char, LC1, S1266, #1}" },
  { "kind": "Direct", "offset": 0, "value": "0 U8b" }
]}

Given that we associate the right type with the default binding there, we could infer that p[7] is affected by that default binding, and p[8] is not.
I agree that this approach might not look the best, since it needs to look at the value associated with the default binding to determine the length of the covered bytes.
I don't expect this to be much of an issue on the implementations side, as such conjured symbols regularly appear due to invalidation, where we have the region which gets invalidated (hence their sizes).

Alternatively, we could embed this length metadata into the default binding - without any indirection.

If we read the values using array access, we still face the problem above, but at least we can tell the analyzer to use the Default binding,
instead of Undefined.

auto y = P[0].arr[0];
auto z = P[0].arr[1];

So the resulting values are:

{ "cluster": "y", "items": [
  { "kind": "Direct", "offset": 0, "value": "derived_$2{conj_$1{uint8_t, LC1, S889556, #1},Element{Element{P,0 S64b,struct S}.arr,0 S64b,unsigned char}}" }
]},
{ "cluster": "z", "items": [
  { "kind": "Direct", "offset": 0, "value": "derived_$3{conj_$1{uint8_t, LC1, S889556, #1},Element{Element{P,0 S64b,struct S}.arr,1 S64b,unsigned char}}" }
]}

(I think these values aren't necessarily correct either.)

They seem to be correct at first glance. At least they have the 'wished' derived symbols I was referring to.

@ASDenysPetrov had an early prototype (D114718) for detecting strict-aliasing issues, which seemed pretty good.

I can think of something similar instead of this patch. It would detect if a C-style cast changes the type, and set the result to Unknown in such cases.
Though that would lead to more information loss as we have know. For example p would be Unknown and we couldn't read p[0].

We should avoid introducing unknown as much as we can.

[martong]

I am inclined to produce Unknown values or even sink nodes when the strict aliasing rules are violated. This is perfectly aligned how we handle other kind of undefined behavior. Why should we complicate our memory model to be able to handle already flawed C++ code? I think we should push https://reviews.llvm.org/D114718 as much as possible.

[isuckatcs]

Abandoning the revision, because D114718 is already addressing the same problem and more.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) {
   NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
   return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));
 }
 
 //===----------------------------------------------------------------------===//
 // Loading values from regions.
 //===----------------------------------------------------------------------===//
 
+static bool isFunny(const MemRegion *MR, const ASTContext &C) {
+  const auto *EL = dyn_cast_or_null<ElementRegion>(MR);
+  if (!EL)
+    return false;
+
+  if (const auto *Base =
+          dyn_cast_or_null<TypedValueRegion>(EL->getSuperRegion())) {
+    const auto BTy = Base->getValueType()
+                         .getDesugaredType(C)
+                         .getUnqualifiedType()
+                         .getCanonicalType();
+
+    const auto Ty = EL->getValueType()
+                        .getDesugaredType(C)
+                        .getUnqualifiedType()
+                        .getCanonicalType();
+
+    // Handle array types.
+    if (const auto *AT = dyn_cast<ArrayType>(BTy)) {
+      QualType ETy;
+      while (AT) {
+        ETy = AT->getElementType()
+                  .getDesugaredType(C)
+                  .getUnqualifiedType()
+                  .getCanonicalType();
+        AT = dyn_cast<ArrayType>(ETy);
+      }
+
+      return ETy != Ty;
+    }
+
+    // Handle fundamental types.
+    if (BTy->isFundamentalType() || BTy->isRecordType())
+      return BTy != Ty;
+
+    // FIXME: Handle other types as well
+  };
+
+  return false;
+}
+
 SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) {
   assert(!isa<UnknownVal>(L) && "location unknown");
   assert(!isa<UndefinedVal>(L) && "location undefined");
 
   // For access to concrete addresses, return UnknownVal.  Checks
   // for null dereferences (and similar errors) are done by checkers, not
   // the Store.
   // FIXME: We can consider lazily symbolicating such memory, but we really
SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) {
   // FIXME: We should eventually handle funny addressing.  e.g.:
   //
   //   int x = ...;
   //   int *p = &x;
   //   char *q = (char*) p;
   //   char c = *q;  // returns the first byte of 'x'.
   //
   // Such funny addressing will occur due to layering of regions.
+  // For now let's just prevent false positives. If the region has a direct
+  // binding, ignore if it's funny.
+  if (isFunny(R, svalBuilder.getContext()) && !B.lookup(R, BindingKey::Direct))
+    return UnknownVal();
+
   if (RTy->isStructureOrClassType())
     return getBindingForStruct(B, R);
 
   // FIXME: Handle unions.
   if (RTy->isUnionType())
     return createLazyBinding(B, R);
 
   if (RTy->isArrayType()) {

clang/test/Analysis/array-punned-region.c

 // RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.core,debug.ExprInspection -verify -analyzer-config eagerly-assume=false -triple x86_64-pc-linux-gnu %s
 
 // RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.core,debug.ExprInspection -verify -analyzer-config eagerly-assume=false -triple i386-pc-linux-gnu  %s
 
 int clang_analyzer_eval(int);
 
 typedef struct {
   int a : 1;
   int b[2];
 } BITFIELD_CAST;
 
 void array_struct_bitfield_1() {
   BITFIELD_CAST ff = {0};
   BITFIELD_CAST *pff = &ff;
-  clang_analyzer_eval(*((int *)pff + 1) == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(*((int *)pff + 1) == 0); // expected-warning{{UNKNOWN}}
   ff.b[0] = 3;
   clang_analyzer_eval(*((int *)pff + 1) == 3); // expected-warning{{TRUE}}
 }
 
 int array_struct_bitfield_2() {
   BITFIELD_CAST ff = {0};
   BITFIELD_CAST *pff = &ff;
-  int a = *((int *)pff + 2); // expected-warning{{Assigned value is garbage or undefined [core.uninitialized.Assign]}}
+  int a = *((int *)pff + 2); // no-warning
+
+  clang_analyzer_eval(((int *)pff + 2) == &ff.b[1]); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ff.b[1] == 0);                 // expected-warning{{TRUE}}
+  // FIXME: this should be TRUE
+  clang_analyzer_eval(a == 0); // expected-warning{{UNKNOWN}}
+
   return a;
 }
 
 typedef struct {
   unsigned int a : 1;
   unsigned int x : 31;
   unsigned int c : 1;
   int b[2];
 } mystruct;
 
 void array_struct_bitfield_3() {
   mystruct ff;
   mystruct *pff = &ff;
   ff.b[0] = 3;
   clang_analyzer_eval(*((int *)pff + 2) == 3); // expected-warning{{TRUE}}
 }

clang/test/Analysis/bstring_UninitRead.c

 // RUN: %clang_analyze_cc1 -verify %s \
-// RUN: -analyzer-checker=core,alpha.unix.cstring
-
+// RUN: -analyzer-checker=core,alpha.unix.cstring,debug.ExprInspection
 
 // This file is generally for the alpha.unix.cstring.UninitializedRead Checker, the reason for putting it into
 // the separate file because the checker is break the some existing test cases in bstring.c file , so we don't 
 // wanna mess up with some existing test case so it's better to create separate file for it, this file also include 
 // the broken test for the reference in future about the broken tests.
 
 
 typedef typeof(sizeof(int)) size_t;

 
 void *mempcpy(void *restrict s1, const void *restrict s2, size_t n);
 
 void mempcpy14() {
   int src[] = {1, 2, 3, 4};
   int dst[5] = {0};
   int *p;
 
-  p = mempcpy(dst, src, 4 * sizeof(int)); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
-   // FIXME: This behaviour is actually surprising and needs to be fixed, 
-   // mempcpy seems to consider the very last byte of the src buffer uninitialized
-   // and returning undef unfortunately. It should have returned unknown or a conjured value instead.
+  p = mempcpy(dst, src, 4 * sizeof(int));
 
-  clang_analyzer_eval(p == &dst[4]); // no-warning (above is fatal)
+  clang_analyzer_eval(p == &dst[4]); // expected-warning{{TRUE}}
 }
 
 struct st {
   int i;
   int j;
 };
 
 
 void mempcpy15() {
   struct st s1 = {0};
   struct st s2;
   struct st *p1;
   struct st *p2;
 
   p1 = (&s2) + 1;
-  p2 = mempcpy(&s2, &s1, sizeof(struct st)); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
-  // FIXME: It seems same as mempcpy14() case.
-  
-  clang_analyzer_eval(p1 == p2); // no-warning (above is fatal)
+  p2 = mempcpy(&s2, &s1, sizeof(struct st));
+  clang_analyzer_eval(p1 == p2); // expected-warning{{TRUE}}
 }

clang/test/Analysis/casts.c

void multiDimensionalArrayPointerCasts(void) {
 
   clang_analyzer_eval(y1 == y2); // expected-warning{{TRUE}}
 
   // FIXME: should be FALSE (i.e. equal pointers).
   clang_analyzer_eval(y1 - y2); // expected-warning{{UNKNOWN}}
   // FIXME: should be TRUE (i.e. same symbol).
   clang_analyzer_eval(*y1 == *y2); // expected-warning{{UNKNOWN}}
 
-  clang_analyzer_eval(*((char *)y1) == *((char *) y2)); // expected-warning{{TRUE}}
+  // FIXME: should be TRUE
+  clang_analyzer_eval(*((char *)y1) == *((char *)y2)); // expected-warning{{UNKNOWN}}
 
   clang_analyzer_eval(y1 == y3); // expected-warning{{TRUE}}
 
   // FIXME: should be FALSE (i.e. equal pointers).
   clang_analyzer_eval(y1 - y3); // expected-warning{{UNKNOWN}}
   // FIXME: should be TRUE (i.e. same symbol).
   clang_analyzer_eval(*y1 == *y3); // expected-warning{{UNKNOWN}}
 
-  clang_analyzer_eval(*((char *)y1) == *((char *) y3)); // expected-warning{{TRUE}}
+  // FIXME: should be TRUE
+  clang_analyzer_eval(*((char *)y1) == *((char *)y3)); // expected-warning{{UNKNOWN}}
 }
 
 void *getVoidPtr(void);
 
 void testCastVoidPtrToIntPtrThroughIntTypedAssignment(void) {
   int *x;
   (*((int *)(&x))) = (int)getVoidPtr();
   *x = 1; // no-crash