[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 ↗

(On Diff #209642)

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

2937–2942 ↗

(On Diff #209642)

[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 ↗

(On Diff #209642)

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 ↗

(On Diff #209642)

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 ↗

(On Diff #209642)

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 ↗

(On Diff #209642)

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

2547–2548 ↗

(On Diff #209849)

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

2549–2552 ↗

(On Diff #209849)

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.

2554–2559 ↗

(On Diff #209849)

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

2564–2566 ↗

(On Diff #209849)

C.getSVal(Arg).

2569 ↗

(On Diff #209849)

remove is unnecessary, we overwrite it anyway.

[Charusso]

• Fix.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2549–2552 ↗

(On Diff #209849)

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

2554–2559 ↗

(On Diff #209849)

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.

2569 ↗

(On Diff #209849)

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

2570 ↗

(On Diff #210347)

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.

2549–2552 ↗

(On Diff #209849)

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

2569 ↗

(On Diff #209849)

Yeah, and the official codebase is wrong :)

[Charusso]

• More fix.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2549–2552 ↗

(On Diff #209849)

Ugh, silly mistake, thanks!

[NoQ]

Great, thanks!

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

363–364 ↗

(On Diff #210458)

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.

cfe/trunk/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"
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;
 
+  /// 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;
+
   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
if (FD->getKind() == Decl::Function) {
     } else if (FunI == II_reallocf) {
       State = ReallocMemAux(C, CE, true, State);
       State = ProcessZeroAllocation(C, CE, 1, State);
     } else if (FunI == II_calloc) {
       State = CallocMem(C, CE, State);
       State = ProcessZeroAllocation(C, CE, 0, State);
       State = ProcessZeroAllocation(C, CE, 1, State);
     } else if (FunI == II_free || FunI == II_g_free || FunI == II_kfree) {
+      if (suppressDeallocationsInSuspiciousContexts(CE, C))
+        return;
+
       State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
     } else if (FunI == II_strdup || FunI == II_win_strdup ||
                FunI == II_wcsdup || FunI == II_win_wcsdup) {
       State = MallocUpdateRefState(C, CE, State);
     } else if (FunI == II_strndup) {
       State = MallocUpdateRefState(C, CE, State);
     } else if (FunI == II_alloca || FunI == II_win_alloca) {
       if (CE->getNumArgs() < 1)

 }
 
 bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const {
   assert(Sym);
   const RefState *RS = C.getState()->get<RegionState>(Sym);
   return (RS && RS->isReleased());
 }
 
+bool MallocChecker::suppressDeallocationsInSuspiciousContexts(
+    const CallExpr *CE, CheckerContext &C) const {
+  if (CE->getNumArgs() == 0)
+    return false;
+
+  StringRef FunctionStr = "";
+  if (const auto *FD = dyn_cast<FunctionDecl>(C.getStackFrame()->getDecl()))
+    if (const Stmt *Body = FD->getBody())
+      if (Body->getBeginLoc().isValid())
+        FunctionStr =
+            Lexer::getSourceText(CharSourceRange::getTokenRange(
+                                     {FD->getBeginLoc(), Body->getBeginLoc()}),
+                                 C.getSourceManager(), C.getLangOpts());
+
+  // We do not model the Integer Set Library's retain-count based allocation.
+  if (!FunctionStr.contains("__isl_"))
+    return false;
+
+  ProgramStateRef State = C.getState();
+
+  for (const Expr *Arg : CE->arguments())
+    if (SymbolRef Sym = C.getSVal(Arg).getAsSymbol())
+      if (const RefState *RS = State->get<RegionState>(Sym))
+        State = State->set<RegionState>(Sym, RefState::getEscaped(RS));
+
+  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;
   }
 
for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
     SymbolRef sym = *I;
 
     if (EscapingSymbol && EscapingSymbol != sym)
       continue;
 
     if (const RefState *RS = State->get<RegionState>(sym)) {
       if ((RS->isAllocated() || RS->isAllocatedOfSizeZero()) &&
           CheckRefState(RS)) {
-        State = State->remove<RegionState>(sym);
         State = State->set<RegionState>(sym, RefState::getEscaped(RS));
       }
     }
   }
   return State;
 }
 
 static SymbolRef findFailedReallocSymbol(ProgramStateRef currState,

cfe/trunk/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. If any of the parameters has an
+//                          '__isl_' prefixed macro definition we escape every
+//                          of them when we are about to 'free()' something.
+
+#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); // Here we notice that the parameter contains '__isl_', escape it.
+}
+
+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.
+}