[analyzer] support ignoring use-after-free checking with reference_counted attribute

[chrisdangelo]

Summary

This change adds a new attribute "reference_counted". This attribute is intended to annotate struct declarations that are known to use a reference counting pattern before being freed.

The long term intention is that "reference_counted" may grow additional affordances for describing the expected retain and release conventions that can be wired up to train the RetainCountChecker.

The short term intention is that "reference_counted" will be used to silence use-after-free and double-free checks that are indicating false positives when the pointer is being monitored by a reference counting system.

This change is being uploaded privately, first for review by Artem Dergachev and then later with Aaron Ballman.

[chrisdangelo]

clang/include/clang/Basic/Attr.td

1699

I've discussed a bit with Devin Coughlin yesterday. Devin would like to be sure that we have appropriate warnings showing if this attribute is misused.

Previously, when I have been testing the use of this attribute, I mistakenly added the attribute annotation after "typedef" and before "struct". This was causing the attribute to not be discovered when the analyzer attempts to inspect the declaration. I don't recall if a compiler warning was being emitted.

This note is being written as a reminder to be evaluate what warning support is already included or adding support if necessary.

[chrisdangelo]

These changes allow the analyzer to silence an issue discovered by MallocChecker if the SymRef or Statement in question is of a struct that has been declared with the compiler attribute annotation "reference_counted".

In the previous iteration of this diff, SymRef alone was used to determine the declared type, and if it was "reference_counted". Previously, if the SymRef was found to be "reference_counted" an analyzer warning would not be issued.

In the current changes, the static analyzer is more lenient and robust. Now, when a MallocChecker issue is discovered, each node in the bug path is visited, and any use of the pointer in question is checked for its type. If the type is found to be "reference_counted" the bug is marked invalid and ultimately not delivered to the developer. In the current changes, a pointer in question is checked for its type both by using the SymRef and using the type information in the AST.

[chrisdangelo]

This change adds support for reference_counted attribute in pragma-attribute-supported-attributes-list.

This change edits comments describing function signatures for isReferenceCountedAttributed[...].

[chrisdangelo]

Hi @aaron.ballman,

It's nice to meet you, virtually.

I've been working with @NoQ on this change. I've now removed the [wip] prefix. When you have some time, I'd appreciate your feedback.

This change adds a new attribute "reference_counted". This attribute is intended to annotate struct declarations that are known to use a reference counting pattern before being freed.

The long term intention is that "reference_counted" may grow additional affordances for describing the expected retain and release conventions that can be wired up to train the static analyzer RetainCountChecker.

The short term intention, executed in these changes, is that "reference_counted" will be used to silence static analyzer use-after-free and double-free checks that are indicating false positives when the pointer is being monitored by a reference counting system.

This change does not currently enable warnings when the "reference_counted" attribute is written before the "struct" keyword. There may be other cases where the programmer may incorrectly use "reference_counted".

I've successfully run the tests locally via ninja check-clang-analysis and ninja check-clang.

I've successfully exercised these changes against a large C / C++ project and studied the output with @NoQ.

These changes are expected to be used in conjunction with additional work with ownership compiler attributes (https://reviews.llvm.org/D113530).

Thank you,
Chris

[steakhal]

In D113622#3193319, @chrisdangelo wrote:

I've successfully exercised these changes against a large C / C++ project and studied the output with @NoQ.

Could you please share the results to have look? How can I reproduce and evaluate the effect of this change?

[NoQ]

In D113622#3194580, @steakhal wrote:

Could you please share the results to have look? How can I reproduce and evaluate the effect of this change?

You'll need a project that uses a lot of manual reference counting, typically in C code (in our case it's XNU which is technically open-source but probably not very interesting). I've definitely seen such code in the wild, typically around various interpreters (eg., C APIs for python or javascript interpreters where the interpreted language's values are reference counted and garbage collected by the language so they need to be manually retained during interop) but we don't have much real data on those.

In such projects you'll see code like this:

struct S {
  int ref_count;
};

...

void release(S *s) {
  if (--s->refcount == 0) {
    free(s);
  }
}

If the static analyzer doesn't know the original reference count, it'll have to assume that the retain count will drop to zero every time such check is made. In particular, it'll assume that even if it did see a prior increment of the reference count (what if the original reference count was equal to -1?). Any subsequent use of the pointer will cause a use-after-free warning. In practice, however, the whole point of having reference counts is to be protected against such situations; reference count is always positive and typically large enough to avoid such use-after-free problems, so these are usually false positives when emitted by MallocChecker.

We have a separate checker, RetainCountChecker, that's specifically designed to deal with such code, to understand the underlying reference counting conventions. Currently RetainCountChecker supports 3 different hardcoded reference counting conventions. However even in just XNU we've seen a lot more separate conventions that are so many that they become impractical to hardcode.

The new attribute currently suppresses MallocChecker warnings but in the future we plan to extend it to actively enable RetainCountChecker to learn the appropriate convention and emit warnings that are more appropriate. The patch doesn't have any effect if the attribute isn't already present so you'll have to actively add it in order to observe any effect.

clang/include/clang/Basic/Attr.td

1700

Hmm, I think it's a good idea to provide some documentation.

[steakhal]

In D113622#3195985, @NoQ wrote:

In D113622#3194580, @steakhal wrote:

Could you please share the results to have look? How can I reproduce and evaluate the effect of this change?

...

Ah, I see. Thank you for the detailed motivation, and future plans.

[aaron.ballman]

In D113622#3193319, @chrisdangelo wrote:

Hi @aaron.ballman,

It's nice to meet you, virtually.

Nice to meet you as well, and I'm very sorry that this review took so long for me to get to. It fell off my radar for a while. :-(

I've been working with @NoQ on this change. I've now removed the [wip] prefix. When you have some time, I'd appreciate your feedback.

This change adds a new attribute "reference_counted". This attribute is intended to annotate struct declarations that are known to use a reference counting pattern before being freed.

One thing to consider: analyzer_noreturn currently exists under the GNU spelling only. We may want to think about adding a [[]] spelling for Clang static analyzer attributes. I'm not certain whether we'd want that to be spelled [[clang::reference_counted]] or [[clang_analyzer::reference_counted]], etc. We've never really decided on a policy about analyzer-specific attributes before and we may want to consider what we'd like to do before/while adding this attribute.

The long term intention is that "reference_counted" may grow additional affordances for describing the expected retain and release conventions that can be wired up to train the static analyzer RetainCountChecker.

The short term intention, executed in these changes, is that "reference_counted" will be used to silence static analyzer use-after-free and double-free checks that are indicating false positives when the pointer is being monitored by a reference counting system.

Another possibility to consider is whether we want to introduce a generic suppression attribute to suppress static analyzer diagnostics in general, rather than having a per-use case attribute.

This change does not currently enable warnings when the "reference_counted" attribute is written before the "struct" keyword. There may be other cases where the programmer may incorrectly use "reference_counted".

I've successfully run the tests locally via ninja check-clang-analysis and ninja check-clang.

I've successfully exercised these changes against a large C / C++ project and studied the output with @NoQ.

That's great to hear! Can you speak to the results in more detail? (Did you have to use the attribute a large number of times? Did the false positive rate improve and if so, by how much? Were there any surprises you found? That sort of thing.)

I'd also be curious to know how this attribute interacts (if at all) with things like ARC (automatic reference counting) in ObjC and the NS retains-related attributes as those are also related to reference counting and also only impact the static analyzer. If we can avoid adding a new attribute (perhaps by adding a new attribute spelling to an existing attribute that covers the same needs), that'd be a really great thing.

These changes are expected to be used in conjunction with additional work with ownership compiler attributes (https://reviews.llvm.org/D113530).

Thank you,
Chris

clang/include/clang/Basic/Attr.td

1699

Agreed -- we're definitely missing test coverage for the attribute as it stands. We should have coverage testing applying it to the correct and incorrect subjects, diagnostics on being given arguments, tests that inheritance works, etc.

1700

+1, no new undocumented attributes please. (The docs also help us reviewer to ensure the behavior of the patch matches the intent.)

clang/test/Analysis/malloc-annotations.c

314

Please give all of the new test case functions a prototype (e.g., (void) instead of ()).

490

You should add a newline to the end of the file.

clang/include/clang/Basic/Attr.td

 
 def NoUniqueAddress : InheritableAttr, TargetSpecificAttr<TargetItaniumCXXABI> {
   let Spellings = [CXX11<"", "no_unique_address", 201803>];
   let Subjects = SubjectList<[NonBitField], ErrorDiag>;
   let Documentation = [NoUniqueAddressDocs];
   let SimpleHandler = 1;
 }
 
+def ReferenceCounted : InheritableAttr {
+  let Spellings = [Clang<"reference_counted">];
+  let Subjects = SubjectList<[Record]>;
+  let Documentation = [Undocumented];
+  let SimpleHandler = 1;
+}
+
 def ReturnsTwice : InheritableAttr {
   let Spellings = [GCC<"returns_twice">];
   let Subjects = SubjectList<[Function]>;
   let Documentation = [Undocumented];
   let SimpleHandler = 1;
 }
 
 def DisableTailCalls : InheritableAttr {

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

 
 } // end of anonymous namespace
 
 REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, SymbolRef, RefState)
 
 /// Check if the memory associated with this symbol was released.
 static bool isReleased(SymbolRef Sym, CheckerContext &C);
 
+/// Check if the if the qualified type is declared as reference counted
+static bool isReferenceCountedAttributedQualType(QualType QT);
+
+/// Check if the if the value or expression is declared as reference counted
+static bool isReferenceCountedAttributed(SymbolRef Sym, const Stmt *S);
+
+/// Check if the if the valueis declared as reference counted
+static bool isReferenceCountedAttributedSymRef(SymbolRef Sym);
+
+/// Check if the if the value or expression is declared as reference counted
+static bool isReferenceCountedAttributedExpr(const Stmt *S);
+
 /// Update the RefState to reflect the new memory allocation.
 /// The optional \p RetVal parameter specifies the newly allocated pointer
 /// value; if unspecified, the value of expression \p E is used.
 static ProgramStateRef MallocUpdateRefState(CheckerContext &C, const Expr *E,
                                             ProgramStateRef State,
                                             AllocationFamily Family,
                                             Optional<SVal> RetVal = None);
 

 }
 
 static bool isReleased(SymbolRef Sym, CheckerContext &C) {
   assert(Sym);
   const RefState *RS = C.getState()->get<RegionState>(Sym);
   return (RS && RS->isReleased());
 }
 
+static bool isReferenceCountedAttributedQualType(QualType QT) {
+  if (QT.isNull())
+    return false;
+
+  QualType PT = QT->getPointeeType();
+  if (PT.isNull())
+    return false;
+
+  Decl *RD = PT->getAsRecordDecl();
+  if (!RD)
+    return false;
+
+  return RD->hasAttr<ReferenceCountedAttr>();
+}
+
+static bool isReferenceCountedAttributedSymRef(SymbolRef Sym) {
+  QualType QT = Sym->getType();
+  if (QT.isNull())
+    return false;
+
+  return isReferenceCountedAttributedQualType(QT);
+}
+
+static bool isReferenceCountedAttributedExpr(const Stmt *S) {
+  const Expr *E = dyn_cast_or_null<Expr>(S);
+  if (!E)
+    return false;
+
+  QualType QT = E->getType();
+  return isReferenceCountedAttributedQualType(QT);
+}
+
+static bool isReferenceCountedAttributed(SymbolRef Sym, const Stmt *S) {
+  bool result = isReferenceCountedAttributedSymRef(Sym) ||
+                isReferenceCountedAttributedExpr(S);
+
+  return result;
+}
+
 bool MallocChecker::suppressDeallocationsInSuspiciousContexts(
     const CallEvent &Call, CheckerContext &C) const {
   if (Call.getNumArgs() == 0)
     return false;
 
   StringRef FunctionStr = "";
   if (const auto *FD = dyn_cast<FunctionDecl>(C.getStackFrame()->getDecl()))
     if (const Stmt *Body = FD->getBody())
PathDiagnosticPieceRef MallocBugVisitor::VisitNode(const ExplodedNode *N,
                                                    PathSensitiveBugReport &BR) {
   ProgramStateRef state = N->getState();
   ProgramStateRef statePrev = N->getFirstPred()->getState();
 
   const RefState *RSCurr = state->get<RegionState>(Sym);
   const RefState *RSPrev = statePrev->get<RegionState>(Sym);
 
   const Stmt *S = N->getStmtForDiagnostics();
+
+  SymbolRef SR = nullptr;
+  const Expr *E = dyn_cast_or_null<Expr>(S);
+  if (E && E->isPRValue())
+    SR = N->getSVal(E).getAsSymbol();
+
+  if (SR == Sym)
+    if (isReferenceCountedAttributed(SR, S))
+      BR.markInvalid(getTag(), S);
+
   // When dealing with containers, we sometimes want to give a note
   // even if the statement is missing.
   if (!S && (!RSCurr || RSCurr->getAllocationFamily() != AF_InnerBuffer))
     return nullptr;
 
   const LocationContext *CurrentLC = N->getLocationContext();
 
   // If we find an atomic fetch_add or fetch_sub within the destructor in which

clang/test/Analysis/malloc-annotations.c

 __attribute((ownership_holds(malloc, 3))) my_hold2(void *, void *, void *);
 void *my_malloc3(size_t);
 void *myglobalpointer;
 struct stuff {
   void *somefield;
 };
 struct stuff myglobalstuff;
 
+struct BMockStruct {
+  int number;
+};
+
+struct AMockStruct {
+  struct BMockStruct bMockStruct;
+};
+
+struct __attribute__((reference_counted)) AnnotatedRefCountedStruct {
+  int mockRefCount;
+  struct AnnotatedRefCountedStruct *mockNext;
+  struct StructContainingAnnotatedRefCountedStruct *unannotatedStructPtr;
+  struct AMockStruct aMockStruct;
+};
+
+struct StructContainingAnnotatedRefCountedStruct {
+  struct AnnotatedRefCountedStruct *refCountedStructPtr;
+  void *opaquePtr;
+  struct AMockStruct aMockStruct;
+};
+
+void my_use_after_free_internal(void *p);
+
+void my_use_after_free_external(void *p) {
+  my_use_after_free_internal(p);
+}
+
+typedef struct AnnotatedRefCountedStruct TypeDefAnnotatedRefCountedStruct;
+struct AnnotatedRefCountedStruct *CreateAnnotatedRefCountedStruct(void);
+TypeDefAnnotatedRefCountedStruct *CreateTypeDefAnnotatedRefCountedStruct(void);
+struct StructContainingAnnotatedRefCountedStruct *CreateStructContainingAnnotatedRefCountedStruct(void);
+typedef struct __attribute__((reference_counted)) UnknownStruct TypeDefUnknownStruct;
+TypeDefUnknownStruct *CreateTypeDefUnknownStruct(void);
+typedef struct __attribute__((reference_counted)) UnknownStruct *TypeDefUnknownStructRef;
+TypeDefUnknownStructRef CreateTypeDefUnknownStructRef(void);
+void *CreateUntypedPointer(void);
+void __attribute__((ownership_takes(malloc, 1))) my_typed_free(struct AnnotatedRefCountedStruct *);
+
 void f1() {
   int *p = malloc(12);
   return; // expected-warning{{Potential leak of memory pointed to by}}
 }
 
 void f2() {
   int *p = malloc(12);
   free(p);

 }
 
 void testMultipleFreeAnnotations() {
   int *p = malloc(12);
   int *q = malloc(12);
   my_freeBoth(p, q);
 }
 
+struct AnnotatedRefCountedStruct *testAnnotatedRefCountedStructIgnoresUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateAnnotatedRefCountedStruct();
+  my_free(p);
+
+  return p;
+}
+
+TypeDefAnnotatedRefCountedStruct *testTypeDefAnnotatedRefCountedStructIgnoresUseAfterFree() {
+  TypeDefAnnotatedRefCountedStruct *p = CreateTypeDefAnnotatedRefCountedStruct();
+  my_free(p);
+
+  return p;
+}
+
+void testTypeDefAnnotatedRefCountedStructIgnoresDoubleFree() {
+  TypeDefAnnotatedRefCountedStruct *p = CreateTypeDefAnnotatedRefCountedStruct();
+
+  my_free(p);
+  my_free(p);
+}
+
+void testCompileTimeAnnotatedTypeIsSufficientToIgnoreDoubleFree() {
+  TypeDefAnnotatedRefCountedStruct *p = CreateUntypedPointer();
+
+  my_free(p);
+  my_free(p);
+}
+
+void testCompileTimeAnnotatedTypeAtUseSiteIsSufficientToIgnoreDoubleFree() {
+  void *p = CreateUntypedPointer();
+
+  my_free(p);
+  my_typed_free(p);
+}
+
+void testCompileTimeDoubleCastTypeCheckingIgnoresUseAfterFree() {
+  TypeDefAnnotatedRefCountedStruct *p = CreateUntypedPointer();
+
+  my_free(p);
+  my_use_after_free_external(p);
+}
+
+TypeDefUnknownStruct *testTypeDefUnkownStructIgnoresUseAfterFree() {
+  TypeDefUnknownStruct *p = CreateTypeDefUnknownStruct();
+
+  my_free(p);
+  return p;
+}
+
+TypeDefUnknownStructRef testTypeDefUnkownStructRefIgnoresUseAfterFree() {
+  TypeDefUnknownStructRef ref = CreateTypeDefUnknownStructRef();
+
+  my_free(ref);
+  return ref;
+}
+
+TypeDefUnknownStruct *testTypeDefUnkownStructFromArrayIgnoresUseAfterFree() {
+  TypeDefUnknownStruct *p[1] = {};
+  p[0] = CreateTypeDefUnknownStruct();
+
+  my_free(p[0]);
+  return p[0];
+}
+
+struct AnnotatedRefCountedStruct *testCreateUntypedPointerWhereCallsiteKnowsIgnoreUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  my_free(p);
+
+  return p;
+}
+
+struct AnnotatedRefCountedStruct *testCreateUntypedPointerWhereReturnTypeKnowsIgnoreUseAfterFree() {
+  void *p = CreateUntypedPointer();
+  my_typed_free(p);
+
+  return p;
+}
+
+TypeDefUnknownStructRef testCreateUntypedPointerWhereReturnTypeIsRefAndKnowsIgnoreUseAfterFree() {
+  void *p = CreateUntypedPointer();
+  my_free(p);
+
+  return p;
+}
+
+int testMemberExpressionTypedBaseIsUsedAsTypeToIgnoreUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateAnnotatedRefCountedStruct();
+  my_free(p);
+
+  return p->mockRefCount;
+}
+
+struct AnnotatedRefCountedStruct *testUseAfterFreeIsIgnoredWhenEmbedded() {
+  struct StructContainingAnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  p->refCountedStructPtr = CreateUntypedPointer();
+  my_free(p->refCountedStructPtr);
+  my_free(p);
+
+  return p->refCountedStructPtr; // expected-warning{{Use of memory after it is freed}}
+}
+
+int testMemberExpressionUntypedBaseIsUsedAsTypeToIgnoreUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  my_free(p);
+
+  return p->mockRefCount;
+}
+
+int testMemberExpressionTypedInitiatedMemberIsUsedAsTypeToIgnoreUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateAnnotatedRefCountedStruct();
+  p->mockNext = CreateAnnotatedRefCountedStruct();
+  my_free(p->mockNext);
+
+  return p->mockNext->mockRefCount;
+}
+
+int testMemberExpressionUnTypedInitiedMemberIsUsedAsTypeToIgnoreUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  p->mockNext = CreateUntypedPointer();
+  my_free(p->mockNext);
+
+  return p->mockNext->mockRefCount;
+}
+
+struct StructContainingAnnotatedRefCountedStruct *testMemberExpressionIsUsedAsTypeToShowUseAfterFree() {
+  struct StructContainingAnnotatedRefCountedStruct *s = CreateStructContainingAnnotatedRefCountedStruct();
+  my_free(s);
+
+  return s; // expected-warning{{Use of memory after it is freed}}
+}
+
+void *testMemberExpressionIndicatesUseAfterFree() {
+  struct StructContainingAnnotatedRefCountedStruct *s = CreateStructContainingAnnotatedRefCountedStruct();
+  my_free(s);
+
+  return s->opaquePtr; // expected-warning{{Use of memory after it is freed}}
+}
+
+void *testUseAfterFreeIsIgnoredFromRootMemberExprBase() {
+  struct AnnotatedRefCountedStruct *p = CreateAnnotatedRefCountedStruct();
+  my_free(p);
+
+  return p->unannotatedStructPtr->opaquePtr;
+}
+
+int testUseAfterFreeIsDiscoveredFromRootMemberExprBaseWhenChainContainsRefCountedDereference() {
+  struct StructContainingAnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  p->refCountedStructPtr = CreateUntypedPointer();
+  my_free(p->refCountedStructPtr);
+  my_free(p);
+
+  return p->refCountedStructPtr->mockRefCount; // expected-warning{{Use of memory after it is freed}}
+}
+
+void *testEmbeddedUseAfterFreeIsDiscovered() {
+  struct AnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  p->mockNext = CreateUntypedPointer();
+  p->unannotatedStructPtr = CreateStructContainingAnnotatedRefCountedStruct();
+  my_free(p->mockNext->unannotatedStructPtr);
+
+  return p->mockNext->unannotatedStructPtr->opaquePtr; // expected-warning{{Use of memory after it is freed}}
+}
+
+int testChainedMemberExpressionsWithDotsDiscoversUseAfterFree() {
+  struct StructContainingAnnotatedRefCountedStruct *p = CreateStructContainingAnnotatedRefCountedStruct();
+  my_free(p);
+
+  return p->aMockStruct.bMockStruct.number; // expected-warning{{Use of memory after it is freed}}
+}
+
+int testChainedMemberExpressionsToReferenceCountedUntypedWithDotsIgnoresUseAfterFree() {
+  struct AnnotatedRefCountedStruct *p = CreateUntypedPointer();
+  my_free(p);
+
+  return p->aMockStruct.bMockStruct.number;
+}
 No newline at end of file

clang/test/Misc/pragma-attribute-supported-attributes-list.test

 // CHECK-NEXT: OpenCLNoSVM (SubjectMatchRule_variable)
 // CHECK-NEXT: OptimizeNone (SubjectMatchRule_function, SubjectMatchRule_objc_method)
 // CHECK-NEXT: Overloadable (SubjectMatchRule_function)
 // CHECK-NEXT: Owner (SubjectMatchRule_record_not_is_union)
 // CHECK-NEXT: ParamTypestate (SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: PassObjectSize (SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: PatchableFunctionEntry (SubjectMatchRule_function, SubjectMatchRule_objc_method)
 // CHECK-NEXT: Pointer (SubjectMatchRule_record_not_is_union)
+// CHECK-NEXT: ReferenceCounted (SubjectMatchRule_record)
 // CHECK-NEXT: ReleaseHandle (SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: RenderScriptKernel (SubjectMatchRule_function)
 // CHECK-NEXT: ReqdWorkGroupSize (SubjectMatchRule_function)
 // CHECK-NEXT: Restrict (SubjectMatchRule_function)
 // CHECK-NEXT: ReturnTypestate (SubjectMatchRule_function, SubjectMatchRule_variable_is_parameter)
 // CHECK-NEXT: ReturnsNonNull (SubjectMatchRule_objc_method, SubjectMatchRule_function)
 // CHECK-NEXT: ReturnsTwice (SubjectMatchRule_function)
 // CHECK-NEXT: ScopedLockable (SubjectMatchRule_record)