[analyzer][UninitializedObjectChecker] Fixed dereferencing

[Szelethus]

Summary

This patch aims to fix derefencing, which has been debated for months now.

Instead of working with SVals, the function now relies on TypedValueRegion.

Since this has been discussed since the inception of the checker, I'd very much prefer finding a permanent solution for this before moving forward.

[Szelethus]

@NoQ, is this how you imagined derefercing to work? I'm still a little uncertain that I implemented this in a way that addresses all your concerns.

[NoQ]

Yup, this looks great and that's exactly how i imagined it.

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedObject.h

261–265

We have a fancy static Loc::isLocType().

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedPointee.cpp

126–127

Good catch.

It might still be possible to initialize a reference with an already-undefined pointer if core checkers are turned off, but we don't support turning them off, so i guess it's fine.

177

Just SVal. And you should be able to pass R directly into getSVal.

210

We usually just do .getAsRegion().

And then later dyn_cast it.

212–216

Ok, i have a new concern that i didn't think about before.

There's nothing special about symbolic regions. You can make a linked list entirely of concrete regions:

struct List {
  List *next;
  List(): next(this) {}
};

void foo() {
  List list;
}

In this case the finite-ness of the type system won't save us.

I guess we could also memoize base regions that we visit :/ This is guaranteed to terminate because all of our concrete regions are based either on AST nodes (eg. global variables) or on certain events that happened previously during analysis (eg. local variables or temporaries, as they depend on the stack frame which must have been previously entered). I don't immediately see a better solution.

223

We might have eliminated symbolic regions but we may still have concrete function pointers (which are TypedRegions that aren't TypedValueRegions, it's pretty weird), and i guess we might even encounter an AllocaRegion (which is completely untyped). I guess we should not try to dereference them either.

240–244

This code seems to be duplicated with the "0th iteration" before the loop. I guess you can put everything into the loop.

[Szelethus]

Addressed the inline comments.

• Added a llvm::SmallSet to further ensure the termination of the loop.
• Changed isLocType to isDereferencableType, block pointers are regarded as primitive objects.
• Added new tests.
• No longer using getDynamicTypeInfo, dynamic type is acquired from TypedValueRegion::getLocationType.

[Szelethus]

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedObject.h

259

I'm not sure this is correct -- do block pointers belong here? Since their region is not TypedValueRegion, I though they better fit here.

261–265

Oh, good to know! However, it also returns true for nullptr_t, which also happens to be a BuiltinType. I'd like to keep isPrimitiveType and (the now renamed) isDereferencableType categories disjunctive. Primitive types require no further analysis other then checking whether they are initialized or not, which is true for nullptr_t objects.

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedPointee.cpp

240–244

I moved some code into the loop, but I think that I really need a 0th iteration to make the code readable.

[Szelethus]

I managed to cause a bunch of crashes with this patch, so consider it as a work in progress for now :/

[Szelethus]

Fixed two crashes. Interesting how many much better this approach works, as I've never encountered FunctionTyped objects or only forward declared typed pointers after dereferencing.

[Szelethus]

Reuploaded with -U99999. Oops.

[Szelethus]

Fixed an assertation failure where a lambda field's this capture was a part of the fieldchain.

[Szelethus]

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedPointee.cpp

126–127

I removed it, because it did crash couple times on LLVM. Note that the assert checked whether the reference for undefined, not uninitialized :/.

It's no longer in the code, but this was it:

assert(!FR->getDecl()->getType()->isReferenceType() &&
       "References must be initialized!");

test/Analysis/cxx-uninitialized-object.cpp

879–902 ↗

(On Diff #163992)

I'm 99% sure this is a FP, but it doesn't originate from the checker. Shouldn't *ptr be undef after the end of the code block as lambda's lifetime ends?

Nevertheless, it did cause a crash, so here's a quick fix for it.

[NoQ]

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedPointee.cpp

126–127

Hmm, indeed, it seems that we don't have a checker for garbage references, only for null references(?).

I guess it's a good idea for a checker.

test/Analysis/cxx-uninitialized-object.cpp

879–902 ↗

(On Diff #163992)

I'm pretty sure that all sorts of contents of lambda aka *ptr are undefined once it goes out of scope. Moreover, ptr is now a dangling pointer, and reading from it would cause undefined behavior. I'm not sure if the analyzer actually models this though.

But on the other hand, even if it didn't go out of scope, i don't really see where field a was initialized here.

Soo what makes you think it's a false positive?

[Szelethus]

test/Analysis/cxx-uninitialized-object.cpp

879–902 ↗

(On Diff #163992)

Soo what makes you think it's a false positive?

Poor choice of words I guess. Its not a false positive (as the entire region of that lambda is undefined), but rather a false negative, as the analyzer doesn't pick up that *ptr is a dangling pointer.

[Szelethus]

I ran the checker on LLVM/Clang and grpc, and saw no crashes at all! Quite confident about the current diff. However, I'm not 100% sure it doesn't break on Objective C++ codes. Can you recommend a project like that?

[NoQ]

Looks good i guess. I'm glad this is sorted out^^

[isuckatcs]

cfe/trunk/lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedPointee.cpp

222 ↗

(On Diff #165445)

@Szelethus @NoQ @xazax.hun I ran into an issue related to this line.

Consider this test case:

struct CyclicPointerTest1 {
  int *ptr; // expected-note{{object references itself 'this->ptr'}}
  int dontGetFilteredByNonPedanticMode = 0;

  CyclicPointerTest1() : ptr(reinterpret_cast<int *>(&ptr)) {} // expected-warning{{1 uninitialized field}}
};

At this point, with the example above, the store looks like this:

{"kind": "Direct", "offset": 0, "extent": 64, value: &Element{temp_object{CyclicPointerTest1, S915}.ptr,0 S64b,int}}
{"kind": "Direct", "offset": 64, "extent": 32, value: 0 S32b}

which means the values are the following:

V = &Element{temp_object{CyclicPointerTest1, S915}.ptr,0 S64b,int}
R = Element{temp_object{CyclicPointerTest1, S915}.ptr,0 S64b,int}
DynT = PointerType ... 'int *'

when State->getSVal(R, DynT) is called, eventually RegionStoreManager::getBinding() will also be invoked, where because R is an ElementRegion we reach these lines:

if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
  // FIXME: Here we actually perform an implicit conversion from the loaded
  // value to the element type.  Eventually we want to compose these values
  // more intelligently.  For example, an 'element' can encompass multiple
  // bound regions (e.g., several bound bytes), or could be a subset of
  // a larger value.
  return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{});
}

What happens here is that we call getBindingForElement(B, ER) and whatever value it returns, we cast to T, which is int * in this example. The type of the element inside the ER however is an int, so the following lookup will be performed:

Binding being looked up: 
  {"kind": "Direct", "offset": 0, "extent": 32}
------------------------------------------------------------------------------------------------------------------------
Store:
  {"kind": "Direct", "offset": 0, "extent": 64 value: &Element{temp_object{CyclicPointerTest1, S915}.ptr,0 S64b,int}}
  {"kind": "Direct", "offset": 64, "extent": 32 value: 0 S32b}

Since extents are ignored by default, the returned value will be &Element{temp_object{CyclicPointerTest1, S915}.ptr,0 S64b,int}}, which is indeed a pointer, however I'm not sure that the lookup here is actually correct.

As far as I understand, we want to lookup an int element based on it's region and we receive a pointer value. Is it because I misunderstand something, or it's an actual issue that is hid by how region store works right now?

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedObject.h

 /// ease. This also helps ensuring that every special field type is handled
 /// correctly.
 inline bool isPrimitiveType(const QualType &T) {
-  return T->isBuiltinType() || T->isEnumeralType() || T->isMemberPointerType();
+  return T->isBuiltinType() || T->isEnumeralType() ||
+         T->isMemberPointerType() || T->isBlockPointerType() ||
+         T->isFunctionType();
+}
+
+inline bool isDereferencableType(const QualType &T) {
+  return T->isAnyPointerType() || T->isReferenceType();
 }
 
 // Template method definitions.

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedObjectChecker.cpp

          !R->getValueType()->isUnionType() &&
          "This method only checks non-union record objects!");
 
-  const RecordDecl *RD =
-      R->getValueType()->getAs<RecordType>()->getDecl()->getDefinition();
-  assert(RD && "Referred record has no definition");
+  const RecordDecl *RD = R->getValueType()->getAsRecordDecl()->getDefinition();
+
+  if (!RD) {
+    IsAnyFieldInitialized = true;
+    return true;
+  }
 
   bool ContainsUninitField = false;
 

       continue;
     }
 
-    if (T->isAnyPointerType() || T->isReferenceType() ||
-        T->isBlockPointerType()) {
+    if (isDereferencableType(T)) {
       if (isPointerOrReferenceUninit(FR, LocalChain))
         ContainsUninitField = true;
       continue;

lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedPointee.cpp

 /// known, and thus FD can not be analyzed.
 static bool isVoidPointer(QualType T);
 
-/// Dereferences \p V and returns the value and dynamic type of the pointee, as
-/// well as whether \p FR needs to be casted back to that type. If for whatever
-/// reason dereferencing fails, returns with None.
-static llvm::Optional<std::tuple<SVal, QualType, bool>>
-dereference(ProgramStateRef State, const FieldRegion *FR);
+using DereferenceInfo = std::pair<const TypedValueRegion *, bool>;
+
+/// Dereferences \p FR and returns with the pointee's region, and whether it
+/// needs to be casted back to it's location type. If for whatever reason
+/// dereferencing fails, returns with None.
+static llvm::Optional<DereferenceInfo> dereference(ProgramStateRef State,
+                                                   const FieldRegion *FR);
 
 //===----------------------------------------------------------------------===//
 //                   Methods for FindUninitializedFields.

 bool FindUninitializedFields::isPointerOrReferenceUninit(
     const FieldRegion *FR, FieldChainInfo LocalChain) {
 
-  assert((FR->getDecl()->getType()->isAnyPointerType() ||
-          FR->getDecl()->getType()->isReferenceType() ||
-          FR->getDecl()->getType()->isBlockPointerType()) &&
-         "This method only checks pointer/reference objects!");
+  assert(isDereferencableType(FR->getDecl()->getType()) &&
+         "This method only checks dereferencable objects!");
 
   SVal V = State->getSVal(FR);
 

   }
 
   if (V.isUndef()) {
+    assert(!FR->getDecl()->getType()->isReferenceType() &&
+           "References must be initialized!");
     return addFieldToUninits(
         LocalChain.add(LocField(FR, /*IsDereferenced*/ false)));
   }

 
   // At this point the pointer itself is initialized and points to a valid
   // location, we'll now check the pointee.
-  llvm::Optional<std::tuple<SVal, QualType, bool>> DerefInfo =
-      dereference(State, FR);
+  llvm::Optional<DereferenceInfo> DerefInfo = dereference(State, FR);
   if (!DerefInfo) {
     IsAnyFieldInitialized = true;
     return false;
   }
 
-  V = std::get<0>(*DerefInfo);
-  QualType DynT = std::get<1>(*DerefInfo);
-  bool NeedsCastBack = std::get<2>(*DerefInfo);
+  const TypedValueRegion *R = DerefInfo->first;
+  const bool NeedsCastBack = DerefInfo->second;
 
-  // If FR is a pointer pointing to a non-primitive type.
-  if (Optional<nonloc::LazyCompoundVal> RecordV =
-          V.getAs<nonloc::LazyCompoundVal>()) {
+  QualType DynT = R->getLocationType();
+  QualType PointeeT = DynT->getPointeeType();
 
-    const TypedValueRegion *R = RecordV->getRegion();
+  if (PointeeT->isStructureOrClassType()) {
+    if (NeedsCastBack)
+      return isNonUnionUninit(R, LocalChain.add(NeedsCastLocField(FR, DynT)));
+    return isNonUnionUninit(R, LocalChain.add(LocField(FR)));
+  }
 
-    if (DynT->getPointeeType()->isStructureOrClassType()) {
+  if (PointeeT->isUnionType()) {
+    if (isUnionUninit(R)) {
       if (NeedsCastBack)
-        return isNonUnionUninit(R, LocalChain.add(NeedsCastLocField(FR, DynT)));
-      return isNonUnionUninit(R, LocalChain.add(LocField(FR)));
-    }
-
-    if (DynT->getPointeeType()->isUnionType()) {
-      if (isUnionUninit(R)) {
-        if (NeedsCastBack)
-          return addFieldToUninits(LocalChain.add(NeedsCastLocField(FR, DynT)));
-        return addFieldToUninits(LocalChain.add(LocField(FR)));
-      } else {
-        IsAnyFieldInitialized = true;
-        return false;
-      }
-    }
-
-    if (DynT->getPointeeType()->isArrayType()) {
+        return addFieldToUninits(LocalChain.add(NeedsCastLocField(FR, DynT)));
+      return addFieldToUninits(LocalChain.add(LocField(FR)));
+    } else {
       IsAnyFieldInitialized = true;
       return false;
     }
+  }
 
-    llvm_unreachable("All cases are handled!");
+  if (PointeeT->isArrayType()) {
+    IsAnyFieldInitialized = true;
+    return false;
   }
 
-  assert((isPrimitiveType(DynT->getPointeeType()) || DynT->isAnyPointerType() ||
-          DynT->isReferenceType()) &&
+  assert((isPrimitiveType(PointeeT) || isDereferencableType(PointeeT)) &&
          "At this point FR must either have a primitive dynamic type, or it "
          "must be a null, undefined, unknown or concrete pointer!");
 
-  if (isPrimitiveUninit(V)) {
+  SVal PointeeV = State->getSVal(R);
+
+  if (isPrimitiveUninit(PointeeV)) {
     if (NeedsCastBack)
       return addFieldToUninits(LocalChain.add(NeedsCastLocField(FR, DynT)));
     return addFieldToUninits(LocalChain.add(LocField(FR)));

   return false;
 }
 
-static llvm::Optional<std::tuple<SVal, QualType, bool>>
-dereference(ProgramStateRef State, const FieldRegion *FR) {
+static llvm::Optional<DereferenceInfo> dereference(ProgramStateRef State,
+                                                   const FieldRegion *FR) {
 
-  DynamicTypeInfo DynTInfo;
-  QualType DynT;
+  llvm::SmallSet<const TypedValueRegion *, 5> VisitedRegions;
 
   // If the static type of the field is a void pointer, we need to cast it back
   // to the dynamic type before dereferencing.
   bool NeedsCastBack = isVoidPointer(FR->getDecl()->getType());
 
   SVal V = State->getSVal(FR);
-  assert(V.getAs<loc::MemRegionVal>() && "V must be loc::MemRegionVal!");
-
-  // If V is multiple pointer value, we'll dereference it again (e.g.: int** ->
-  // int*).
-  // TODO: Dereference according to the dynamic type to avoid infinite loop for
-  // these kind of fields:
-  //   int **ptr = reinterpret_cast<int **>(&ptr);
-  while (auto Tmp = V.getAs<loc::MemRegionVal>()) {
-    // We can't reason about symbolic regions, assume its initialized.
-    // Note that this also avoids a potential infinite recursion, because
-    // constructors for list-like classes are checked without being called, and
-    // the Static Analyzer will construct a symbolic region for Node *next; or
-    // similar code snippets.
-    if (Tmp->getRegion()->getSymbolicBase()) {
-      return None;
-    }
+  assert(V.getAsRegion() && "V must have an underlying region!");
 
-    DynTInfo = getDynamicTypeInfo(State, Tmp->getRegion());
-    if (!DynTInfo.isValid()) {
-      return None;
-    }
+  // The region we'd like to acquire.
+  const auto *R = V.getAsRegion()->getAs<TypedValueRegion>();
+  if (!R)
+    return None;
+
+  VisitedRegions.insert(R);
 
-    DynT = DynTInfo.getType();
+  // We acquire the dynamic type of R,
+  QualType DynT = R->getLocationType();
 
-    if (isVoidPointer(DynT)) {
+  while (const MemRegion *Tmp = State->getSVal(R, DynT).getAsRegion()) {
+
+    R = Tmp->getAs<TypedValueRegion>();
+
+    if (!R)
+      return None;
+
+    // We found a cyclic pointer, like int *ptr = (int *)&ptr.
+    // TODO: Report these fields too.
+    if (!VisitedRegions.insert(R).second)
       return None;
-    }
 
-    V = State->getSVal(*Tmp, DynT);
+    DynT = R->getLocationType();
+    // In order to ensure that this loop terminates, we're also checking the
+    // dynamic type of R, since type hierarchy is finite.
+    if (isDereferencableType(DynT->getPointeeType()))
+      break;
   }
 
-  return std::make_tuple(V, DynT, NeedsCastBack);
+  return std::make_pair(R, NeedsCastBack);
 }

test/Analysis/cxx-uninitialized-object-ptr-ref.cpp

 }
 
 //===----------------------------------------------------------------------===//
+// Alloca tests.
+//===----------------------------------------------------------------------===//
+
+struct UntypedAllocaTest {
+  void *allocaPtr;
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  UntypedAllocaTest() : allocaPtr(__builtin_alloca(sizeof(int))) {
+    // All good!
+  }
+};
+
+void fUntypedAllocaTest() {
+  UntypedAllocaTest();
+}
+
+struct TypedAllocaTest1 {
+  int *allocaPtr; // expected-note{{uninitialized pointee 'this->allocaPtr'}}
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  TypedAllocaTest1() // expected-warning{{1 uninitialized field}}
+      : allocaPtr(static_cast<int *>(__builtin_alloca(sizeof(int)))) {}
+};
+
+void fTypedAllocaTest1() {
+  TypedAllocaTest1();
+}
+
+struct TypedAllocaTest2 {
+  int *allocaPtr;
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  TypedAllocaTest2()
+      : allocaPtr(static_cast<int *>(__builtin_alloca(sizeof(int)))) {
+    *allocaPtr = 55555;
+    // All good!
+  }
+};
+
+void fTypedAllocaTest2() {
+  TypedAllocaTest2();
+}
+
+//===----------------------------------------------------------------------===//
 // Heap pointer tests.
 //===----------------------------------------------------------------------===//
 

   CyclicPointerTest1();
 }
 
-// TODO: Currently, the checker ends up in an infinite loop for the following
-// test case.
-/*
 struct CyclicPointerTest2 {
-  int **pptr;
+  int **pptr; // no-crash
   CyclicPointerTest2() : pptr(reinterpret_cast<int **>(&pptr)) {}
 };
 
 void fCyclicPointerTest2() {
   CyclicPointerTest2();
 }
-*/
 
 //===----------------------------------------------------------------------===//
 // Void pointer tests.

 }
 
 //===----------------------------------------------------------------------===//
+// Incomplete pointee tests.
+//===----------------------------------------------------------------------===//
+
+class IncompleteType;
+
+struct IncompletePointeeTypeTest {
+  IncompleteType *pImpl; //no-crash
+  int dontGetFilteredByNonPedanticMode = 0;
+
+  IncompletePointeeTypeTest(IncompleteType *A) : pImpl(A) {}
+};
+
+void fIncompletePointeeTypeTest(void *ptr) {
+  IncompletePointeeTypeTest(reinterpret_cast<IncompleteType *>(ptr));
+}
+
+//===----------------------------------------------------------------------===//
+// Function pointer tests.
+//===----------------------------------------------------------------------===//
+
+struct FunctionPointerWithDifferentDynTypeTest {
+  using Func1 = void *(*)();
+  using Func2 = int *(*)();
+
+  Func1 f; // no-crash
+  FunctionPointerWithDifferentDynTypeTest(Func2 f) : f((Func1)f) {}
+};
+
+// Note that there isn't a function calling the constructor of
+// FunctionPointerWithDifferentDynTypeTest, because a crash could only be
+// reproduced without it.
+
+//===----------------------------------------------------------------------===//
 // Member pointer tests.
 //===----------------------------------------------------------------------===//
 

   CyclicList(&n1, int());
 }
 
+struct RingListTest {
+  RingListTest *next; // no-crash
+  RingListTest() : next(this) {}
+};
+
+void fRingListTest() {
+  RingListTest();
+}
+
 //===----------------------------------------------------------------------===//
 // Tests for classes containing references.
 //===----------------------------------------------------------------------===//

test/Analysis/objcpp-uninitialized-object.mm

 
 struct StructWithBlock {
   int a;
-  myBlock z; // expected-note{{uninitialized pointer 'this->z'}}
+  myBlock z; // expected-note{{uninitialized field 'this->z'}}
 
   StructWithBlock() : a(0), z(^{}) {}