[analyzer] MallocChecker: Prevent Integer Set Library false positives

[Charusso]

Summary

Integer Set Library using retain-count based allocation which is not
modeled in MallocChecker.

[NoQ]

Oh damn, i just realized that this way we track much more pointers than before, because we cannot restrict ourselves to pointers that have been explicitly malloc()ed during analysis. After all, we don't need to see the allocation site to diagnose use-after-free.

I'm afraid that it's going to be too many pointers.

Change of plans: let's suppress the warning when our free() is done within the function that has __isl_take in its definition. So, like, ascend the chain of location contexts and check your callers when you're about to mark the pointer as released. If any of the callers contain __isl_take, mark it as escaped instead.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

56–58

We already have Escaped, it's the same thing in practice.

2937–2942

[Charusso]

• Fix.
• Move the logic to free() for better matching.

[Charusso]

In D64680#1584076, @NoQ wrote:

Change of plans: let's suppress the warning when our free() is done within the function that has __isl_take in its definition. So, like, ascend the chain of location contexts and check your callers when you're about to mark the pointer as released. If any of the callers contain __isl_take, mark it as escaped instead.

I think if the __isl_* macro is in use it should be used in the immediate StackFrame. Btw: some magic happened and with the previous approach we did not suppress some reports, now we do. Thanks!

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

56–58

It is more strict than Escaped, also it made for the purpose of PSK_EscapeOther to force out we lost the entire pointer and do not make false warnings of use-after-free.

2937–2942

I wanted to make it bulletproof, but your meme-proof is way more better.

[Charusso]

Here is an example of the mentioned use-after-free by pointer-escaping as an argument:
https://llvm.org/reports/scan-build/report-DeclBase.cpp-getFromVoidPointer-0-1.html#EndPath

[NoQ]

In D64680#1584130, @Charusso wrote:

Here is an example of the mentioned use-after-free by pointer-escaping as an argument:
https://llvm.org/reports/scan-build/report-DeclBase.cpp-getFromVoidPointer-0-1.html#EndPath

Not sure how is this false positive related to that report, but this false positive looks super weird and i'd love to debug it more.

P.S. I think you should attach the report to Phabricator directly, as the link will expire as soon as these reports get regenerated.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

56–58

How exactly is it more strict? I.e., what warnings are getting suppressed by you that aren't going to be suppressed if you use Escaped instead?

[Charusso]

• Remove unnecessary DoNothing kind.

[Charusso]

In D64680#1584315, @NoQ wrote:

P.S. I think you should attach the report to Phabricator directly, as the link will expire as soon as these reports get regenerated.

Luckily the stable scan-build namings are stable, so that is why I picked that handy option.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

56–58

After some measurements the previously attached report has nothing to do with strictness, just we really miss some escaping. Reverted that.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2560–2561

const auto *FD = dyn_cast<FunctionDecl>(C.getStackFrame()->getDecl()).

2562–2565

I'm slightly worried that it'll crash when free() is being called from within a body farm.

For now it probably cannot happen because none of the bodyfarmed functions can call free() directly, but i'd anyway rather add a check that the source locations we're taking are valid.

2567–2572

If the string is empty, it clearly cannot contain __isl_, so the first check is redundant.

2577–2579

C.getSVal(Arg).

2582

remove is unnecessary, we overwrite it anyway.

[Charusso]

• Fix.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2562–2565

Oh, I missed that, thanks! I wanted to check for everything, yes.

2567–2572

The first check is: "We got a body and its decl?", the second check is: "We got an ISL macro?". Yea, it is kind of redundant, just I like to pack one check in one IfStmt, and now that two question merges. Also I like to make them one-liners so they are self-explanatory.

Here is an example why I like it:

// Escape pointers passed into the list, unless it's an ObjC boxed       
// expression which is not a boxable C structure.                        
if (!(isa<ObjCBoxedExpr>(Ex) &&                                          
      !cast<ObjCBoxedExpr>(Ex)->getSubExpr()                             
                              ->getType()->isRecordType()))

• from ExprEngine::Visit() - Expr::ObjCBoxedExprClass case.

2582

I believe in so as well, just the official code base has this semantic. I have rewritten that, see below in checkPointerEscapeAux().

[NoQ]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2562–2565

I think this is not fixed yet. I'm thinking of something like if (!Body->getBeginLoc().isValid()) { ... }.

2582

Yeah, and the official codebase is wrong :)

2583

The check is unnecessary. addTransition automatically takes care of the "no changes have happened" case and throws away the transition.

Moreover, in the current patch you aren't really checking if any changes have happened: the symbol may already be escaped, so in this case the flag is set to true but the state remains the same.

[Charusso]

• More fix.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2562–2565

Ugh, silly mistake, thanks!

[NoQ]

Great, thanks!

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

372–373

One last thing: let's make it obvious what does the function do.

• It not only checks and returns a boolean value, it also adds transitions. It is very important to know that the function adds transitions so that to avoid accidental state splits.
• In this case we're talking about a deallocation rather than allocation.
• Technically, "not modeled" is not quite correct, as we *are* modeling it, just differently.

I suggest something like this:

/// See if deallocation happens in a suspicious context. If so, escape the pointers
/// that otherwise would have been deallocated and return true.
bool suppressDeallocationsInSuspiciousContexts(const CallExpr *CE, CheckerContext &C) const;

[Charusso]

In D64680#1590619, @NoQ wrote:

Great, thanks!

Thanks for the review! I like that new name.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "InterCheckerAPI.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/ParentMap.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
+#include "clang/Lex/Lexer.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "AllocationState.h"
 #include <climits>
 #include <utility>
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
 // Used to check correspondence between allocators and deallocators.
 enum AllocationFamily {
   AF_None,
+  AF_NotModeled,
   AF_Malloc,
   AF_CXXNew,
   AF_CXXNewArray,
   AF_IfNameIndex,
   AF_Alloca,
   AF_InnerBuffer
 };
 
 class RefState {
-  enum Kind { // Reference to allocated memory.
-              Allocated,
-              // Reference to zero-allocated memory.
-              AllocatedOfSizeZero,
-              // Reference to released/freed memory.
-              Released,
-              // The responsibility for freeing resources has transferred from
-              // this reference. A relinquished symbol should not be freed.
-              Relinquished,
-              // We are no longer guaranteed to have observed all manipulations
-              // of this pointer/memory. For example, it could have been
-              // passed as a parameter to an opaque function.
-              Escaped
+  enum Kind {
+    // If this checker does not model the allocation.
+    DoNothing,
+    // Reference to allocated memory.
   };
 
   const Stmt *S;
   unsigned K : 3; // Kind enum, but stored as a bitfield.
   unsigned Family : 29; // Rest of 32-bit word, currently just an allocation
                         // family.
 
   RefState(Kind k, const Stmt *s, unsigned family)
     : S(s), K(k), Family(family) {
     assert(family != AF_None);
   }
 public:
+  bool isDoNothing() const { return K == DoNothing; }
   bool isAllocated() const { return K == Allocated; }
   bool isAllocatedOfSizeZero() const { return K == AllocatedOfSizeZero; }
   bool isReleased() const { return K == Released; }
   bool isRelinquished() const { return K == Relinquished; }
   bool isEscaped() const { return K == Escaped; }
   AllocationFamily getAllocationFamily() const {
     return (AllocationFamily)Family;
   }
static RefState getReleased(unsigned family, const Stmt *s) {
     return RefState(Released, s, family);
   }
   static RefState getRelinquished(unsigned family, const Stmt *s) {
     return RefState(Relinquished, s, family);
   }
   static RefState getEscaped(const RefState *RS) {
     return RefState(Escaped, RS->getStmt(), RS->getAllocationFamily());
   }
+  static RefState getDoNothing(const Stmt *S) {
+    return RefState(DoNothing, S, AF_NotModeled);
+  }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddInteger(K);
     ID.AddPointer(S);
     ID.AddInteger(Family);
   }
 
   void dump(raw_ostream &OS) const {
     switch (static_cast<Kind>(K)) {
 #define CASE(ID) case ID: OS << #ID; break;
+    CASE(DoNothing)
     CASE(Allocated)
     CASE(AllocatedOfSizeZero)
     CASE(Released)
     CASE(Relinquished)
     CASE(Escaped)
     }
   }
 
private:
   static SVal evalMulForBufferSize(CheckerContext &C, const Expr *Blocks,
                                    const Expr *BlockBytes);
   static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE,
                                    ProgramStateRef State);
 
   /// Check if the memory associated with this symbol was released.
   bool isReleased(SymbolRef Sym, CheckerContext &C) const;
 
+  /// Check whether we do not model the memory allocation.
+  bool isNotModeled(const CallExpr *CE, CheckerContext &C) const;
+
   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, const Stmt *S) const;
 
   void checkUseZeroAllocated(SymbolRef Sym, CheckerContext &C,
                              const Stmt *S) const;
 
   bool checkDoubleDelete(SymbolRef Sym, CheckerContext &C) const;
 
   /// Check if the function is known free memory, or if it is
SVal MallocChecker::evalMulForBufferSize(CheckerContext &C, const Expr *Blocks,
   SVal BlockBytesVal = C.getSVal(BlockBytes);
   ProgramStateRef State = C.getState();
   SVal TotalSize = SB.evalBinOp(State, BO_Mul, BlocksVal, BlockBytesVal,
                                 SB.getContext().getSizeType());
   return TotalSize;
 }
 
 void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
-  if (C.wasInlined)
-    return;
-
   const FunctionDecl *FD = C.getCalleeDecl(CE);
   if (!FD)
     return;
 
+  if (isNotModeled(CE, C))
+    return;
+
+  if (C.wasInlined)
+    return;
+
   ProgramStateRef State = C.getState();
   bool ReleasedAllocatedMemory = false;
 
   if (FD->getKind() == Decl::Function) {
     initIdentifierInfo(C.getASTContext());
     IdentifierInfo *FunI = FD->getIdentifier();
 
     if (FunI == II_malloc || FunI == II_g_malloc || FunI == II_g_try_malloc) {
void MallocChecker::printExpectedAllocName(raw_ostream &os, CheckerContext &C,
   AllocationFamily Family = getAllocationFamily(C, E);
 
   switch(Family) {
     case AF_Malloc: os << "malloc()"; return;
     case AF_CXXNew: os << "'new'"; return;
     case AF_CXXNewArray: os << "'new[]'"; return;
     case AF_IfNameIndex: os << "'if_nameindex()'"; return;
     case AF_InnerBuffer: os << "container-specific allocator"; return;
+    case AF_NotModeled: os << "not modeled allocator"; return;
     case AF_Alloca:
     case AF_None: llvm_unreachable("not a deallocation expression");
   }
 }
 
 void MallocChecker::printExpectedDeallocName(raw_ostream &os,
                                              AllocationFamily Family) const {
   switch(Family) {
     case AF_Malloc: os << "free()"; return;
     case AF_CXXNew: os << "'delete'"; return;
     case AF_CXXNewArray: os << "'delete[]'"; return;
     case AF_IfNameIndex: os << "'if_freenameindex()'"; return;
     case AF_InnerBuffer: os << "container-specific deallocator"; return;
+    case AF_NotModeled: os << "not modeled deallocator"; return;
     case AF_Alloca:
     case AF_None: llvm_unreachable("suspicious argument");
   }
 }
 
 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
                                           const Expr *ArgExpr,
                                           const Expr *ParentExpr,
case AF_CXXNewArray: {
     }
     return None;
   }
   case AF_InnerBuffer: {
     if (ChecksEnabled[CK_InnerPointerChecker])
       return CK_InnerPointerChecker;
     return None;
   }
+  case AF_NotModeled:
+    return None;
   case AF_None: {
     llvm_unreachable("no family");
   }
   }
   llvm_unreachable("unhandled family");
 }
 
 Optional<MallocChecker::CheckKind>

 }
 
 bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const {
   assert(Sym);
   const RefState *RS = C.getState()->get<RegionState>(Sym);
   return (RS && RS->isReleased());
 }
 
+bool MallocChecker::isNotModeled(const CallExpr *CE, CheckerContext &C) const {
+  if (CE->getNumArgs() == 0)
+    return false;
+
+  const FunctionDecl *FD = C.getCalleeDecl(CE);
+  const Stmt *Body = FD->getBody();
+  if (!Body)
+    return false;
+
+  StringRef FunctionStr = Lexer::getSourceText(
+      CharSourceRange::getTokenRange({FD->getBeginLoc(), Body->getBeginLoc()}),
+      C.getSourceManager(), C.getLangOpts());
+
+  // We do not model Integer Set Library's retain-count based allocation.
+  if (!FunctionStr.contains("__isl_"))
+    return false;
+
+  ProgramStateRef State = C.getState();
+  const LocationContext *LCtx = C.getLocationContext();
+
+  for (const auto &Arg : CE->arguments()) {
+    if (const auto *DRE = dyn_cast<DeclRefExpr>(Arg->IgnoreImpCasts())) {
+      if (const auto *VD = dyn_cast<ParmVarDecl>(DRE->getDecl())) {
+        SVal V = State->getSVal(State->getLValue(VD, LCtx));
+        if (SymbolRef Sym = V.getAsSymbol()) {
+          const RefState *RS = State->get<RegionState>(Sym);
+          if (!RS) {
+            State = State->set<RegionState>(Sym, RefState::getDoNothing(Arg));
+            C.addTransition(State);
+          }
+        }
+      }
+    }
+  }
+
+  return true;
+}
+
 bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
                                       const Stmt *S) const {
 
   if (isReleased(Sym, C)) {
     ReportUseAfterFree(C, S->getSourceRange(), Sym);
     return true;
   }
 

 
 std::shared_ptr<PathDiagnosticPiece> MallocChecker::MallocBugVisitor::VisitNode(
     const ExplodedNode *N, BugReporterContext &BRC, BugReport &BR) {
 
   ProgramStateRef state = N->getState();
   ProgramStateRef statePrev = N->getFirstPred()->getState();
 
   const RefState *RS = state->get<RegionState>(Sym);
+  const Stmt *S = PathDiagnosticLocation::getStmt(N);
+
+  if (RS && RS->isDoNothing()) {
+    BR.markInvalid(getTag(), S);
+    return nullptr;
+  }
+
   const RefState *RSPrev = statePrev->get<RegionState>(Sym);
 
-  const Stmt *S = PathDiagnosticLocation::getStmt(N);
   // When dealing with containers, we sometimes want to give a note
   // even if the statement is missing.
   if (!S && (!RS || RS->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
if (isAllocated(RS, RSPrev, S)) {
             }
             OS << "'";
             StackHint = new StackHintGeneratorForSymbol(Sym,
                                       "Returning; inner buffer was reallocated");
           }
           Msg = OS.str();
           break;
         }
+        case AF_NotModeled:
+          llvm_unreachable("The report should be invalidated at this point.");
         case AF_None:
           llvm_unreachable("Unhandled allocation family!");
       }
 
       // See if we're releasing memory while inlining a destructor
       // (or one of its callees). This turns on various common
       // false positive suppressions.
       bool FoundAnyDestructor = false;

clang/test/Analysis/retain-count-alloc.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,unix.Malloc \
+// RUN:  -verify %s
+
+// expected-no-diagnostics: We do not model Integer Set Library's retain-count
+//                          based allocation.
+
+#define __isl_take
+#define __isl_keep
+
+struct Object { int Ref; };
+void free(void *);
+
+Object *copyObj(__isl_keep Object *O) {
+  O->Ref++;
+  return O;
+}
+
+void freeObj(__isl_take Object *O) {
+  if (--O->Ref > 0)
+    return;
+
+  free(O);
+}
+
+void useAfterFree(__isl_take Object *A) {
+  if (!A)
+    return;
+
+  Object *B = copyObj(A);
+  freeObj(B);
+
+  A->Ref = 13;
+  // no-warning: 'Use of memory after it is freed' was here.
+}