[analyzer] Fix for the strdup family in unix.malloc checker

[baloghadamsoftware]

Summary

The strdup family was only partially handled in the original checker. As a consequence it did not recognize leaks where a variable which received a result of an strdup was later overwritten. (The unix.cstring checkers did not recognize this leak either, but their task is also different.) This patch fixes this issue by simulating the memory allocation of strdup functions. Some new functions where taken from the unix.cstring checkers but they were also simplified and adapted for the purpose of the checker. Some other tests had to be fixed as well since they contained strdup caused memory leaks. (The leak was not fixed but the warning is now expected.)

[NoQ]

This patch is doing a very good thing - modeling contents of the copied string as a lazy compound value of the original string. For that, i guess it's worth adding some tests (ExprInspection-based(?)) that show that, say, first few characters of the copied string are same as the original. It might also be a good idea to move this modeling to CStringChecker completely, because right now it's easier to assume a range on SymbolExtent of the strdupped region, than transfer correct string length into MallocChecker. But then you'd need to enable CStringChecker in your builds so that they could work together to model strdup().

The effect you observe, however - finding leaks on overwriting variables that hold leaked symbols - is in fact not because you modeled the copy better, but because you managed to accidentally work around the "zombie symbols" bug, described in http://lists.llvm.org/pipermail/cfe-dev/2016-March/047922.html and D18860 (there's still no certainty as of how exactly to fix it). Because you model contents of the copied string by binding a value to it, the Store is eager to reap the symbol as soon as possible, and hence detect a leak. Before, only the checker knew about the symbol of the copied string, and it wasn't eager to reap that symbol after it disappeared from the rest of the program state through overwriting. The problem could as well be fixed with code as simple and unobvious as:

void MallocChecker::checkLiveSymbols(ProgramStateRef State,
                                     SymbolReaper &SR) const {
  for (const auto &Item: State->get<RegionState>())
    SR.maybeDead(Item.first);
}

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

2134

I'm not sure if this is truly worth it. In CStringChecker, a lot of work is done in order to model the length of the string; however, currently MallocChecker does not have any access to that info, and a lot more code copy-paste'ing would be necessary to re-model all the stuff. And even if you do so, the symbol you create in that statement wouldn't be the same as the symbol used in CStringChecker, so you may never compare them to each other and see that they're equal - say, strlen() of a duplicated string, strlen() for the original string, and the value you produce on that statement, would still be three different symbols.

Ideally, we can leave this out for later, and wait until we allow checkers interact with each other and share such information. So that we could ask CStringChecker directly here, and obtain string length as CStringChecker sees it.

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

enum class MemoryOperationKind {
     MOK_Any
   };
 
   DefaultBool IsOptimistic;
 
   DefaultBool ChecksEnabled[CK_NumCheckKinds];
   CheckName CheckNames[CK_NumCheckKinds];
 
+  static void *getTag() { static int tag; return &tag; }
+
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
   void checkPostStmt(const CXXNewExpr *NE, CheckerContext &C) const;
   void checkPreStmt(const CXXDeleteExpr *DE, CheckerContext &C) const;
   void checkPostObjCMessage(const ObjCMethodCall &Call, CheckerContext &C) const;
   void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
   void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
ProgramStateRef FreeMemAux(CheckerContext &C, const Expr *Arg,
                              bool ReturnsNullOnFailure = false) const;
 
   ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE,
                              bool FreesMemOnFailure,
                              ProgramStateRef State) const;
   static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE,
                                    ProgramStateRef State);
 
+  static ProgramStateRef DuplicateString(CheckerContext &C, const CallExpr *CE,
+                                         ProgramStateRef State);
+  static ProgramStateRef DuplicateStringBounded(CheckerContext &C,
+                                                const CallExpr *CE,
+                                                ProgramStateRef State);
+  static SVal copyCString(CheckerContext &C, ProgramStateRef &State, SVal Buf);
+  static SVal getCStringLength(CheckerContext &C, ProgramStateRef &State,
+                               const Expr *Ex, SVal Buf);
+  static SVal getCStringLengthForRegion(CheckerContext &C,
+                                        ProgramStateRef &State, const Expr *Ex,
+                                        const MemRegion *MR);
+
   ///\brief Check if the memory associated with this symbol was released.
   bool isReleased(SymbolRef Sym, CheckerContext &C) const;
 
   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, const Stmt *S) const;
 
   void checkUseZeroAllocated(SymbolRef Sym, CheckerContext &C,
                              const Stmt *S) const;
 
if (FD->getKind() == Decl::Function) {
     } 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) {
       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);
+      if (CE->getNumArgs() < 1)
+        return;
+      State = DuplicateString(C, CE, State);
+      State = ProcessZeroAllocation(C, CE, 0, State);
     } else if (FunI == II_strndup) {
-      State = MallocUpdateRefState(C, CE, State);
+      if (CE->getNumArgs() < 2)
+        return;
+      State = DuplicateStringBounded(C, CE, State);
+      State = ProcessZeroAllocation(C, CE, 0, State);
     } else if (FunI == II_alloca || FunI == II_win_alloca) {
       State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
                            AF_Alloca);
       State = ProcessZeroAllocation(C, CE, 0, State);
     } else if (isStandardNewDelete(FD, C.getASTContext())) {
       // Process direct calls to operator new/new[]/delete/delete[] functions
       // as distinct from new/new[]/delete/delete[] expressions that are
       // processed by the checkPostStmt callbacks for CXXNewExpr and
ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE,
   SVal elementSize = State->getSVal(CE->getArg(1), LCtx);
   SVal TotalSize = svalBuilder.evalBinOp(State, BO_Mul, count, elementSize,
                                         svalBuilder.getContext().getSizeType());
   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
 
   return MallocMemAux(C, CE, TotalSize, zeroVal, State);
 }
 
+ProgramStateRef MallocChecker::DuplicateString(CheckerContext &C,
+                                               const CallExpr *CE,
+                                               ProgramStateRef State) {
+  const auto *sourceEx = CE->getArg(0);
+  auto sourceVal = State->getSVal(sourceEx, C.getLocationContext());
+  return MallocMemAux(C, CE, getCStringLength(C, State, sourceEx, sourceVal),
+                      copyCString(C, State, sourceVal), State);
+}
+
+ProgramStateRef MallocChecker::DuplicateStringBounded(CheckerContext &C,
+                                                      const CallExpr *CE,
+                                                      ProgramStateRef State) {
+  const auto *sourceEx = CE->getArg(0);
+  auto sourceVal = State->getSVal(sourceEx, C.getLocationContext());
+  auto strLen = getCStringLength(C, State, sourceEx, sourceVal);
+
+  SValBuilder &svalBuilder = C.getSValBuilder();
+  QualType cmpTy = svalBuilder.getConditionType();
+  QualType sizeTy = svalBuilder.getContext().getSizeType();
+
+  const auto *lenEx = CE->getArg(1);
+  auto lenVal = State->getSVal(lenEx, C.getLocationContext());
+  lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenEx->getType());
+
+  Optional<NonLoc> strLenNL = strLen.getAs<NonLoc>();
+  Optional<NonLoc> lenValNL = lenVal.getAs<NonLoc>();
+
+  SVal destLength = UnknownVal();
+
+  if (strLenNL && lenValNL) {
+    ProgramStateRef stateLenVal, stateStrLen;
+
+    std::tie(stateLenVal, stateStrLen) = State->assume(
+        svalBuilder.evalBinOpNN(State, BO_GE, *strLenNL, *lenValNL, cmpTy)
+            .castAs<DefinedOrUnknownSVal>());
+
+    if (stateLenVal && !stateStrLen) {
+      State = stateLenVal;
+      destLength = lenVal;
+    } else if (!stateLenVal && stateStrLen) {
+      State = stateStrLen;
+      destLength = strLen;
+    }
+  }
+  return MallocMemAux(C, CE, destLength, copyCString(C, State, sourceVal),
+                      State);
+}
+
+SVal MallocChecker::copyCString(CheckerContext &C, ProgramStateRef &State,
+                                SVal Buf) {
+  const auto *MR = Buf.getAsRegion();
+  if (!MR)
+    return UnknownVal();
+
+  MR = MR->StripCasts();
+
+  if (const auto *TVR = MR->getAs<TypedValueRegion>()) {
+    auto &svalBuilder = C.getSValBuilder();
+    const auto store = State->getStore();
+    auto &storeMgr = State->getStateManager().getStoreManager();
+    return svalBuilder.makeLazyCompoundVal(StoreRef(store, storeMgr), TVR);
+  } else {
+    return UnknownVal();
+  }
+}
+
+SVal MallocChecker::getCStringLength(CheckerContext &C, ProgramStateRef &State,
+                                     const Expr *Ex, SVal Buf) {
+  const auto *MR = Buf.getAsRegion();
+  if (!MR)
+    return UnknownVal();
+
+  MR = MR->StripCasts();
+
+  switch (MR->getKind()) {
+  case MemRegion::StringRegionKind: {
+    auto &svalBuilder = C.getSValBuilder();
+    auto sizeTy = svalBuilder.getContext().getSizeType();
+    const auto *strLit = cast<StringRegion>(MR)->getStringLiteral();
+    return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
+  }
+  case MemRegion::SymbolicRegionKind:
+  case MemRegion::AllocaRegionKind:
+  case MemRegion::VarRegionKind:
+  case MemRegion::FieldRegionKind:
+  case MemRegion::ObjCIvarRegionKind:
+    return getCStringLengthForRegion(C, State, Ex, MR);
+  default:
+    return UnknownVal();
+  }
+}
+
+SVal MallocChecker::getCStringLengthForRegion(CheckerContext &C,
+                                              ProgramStateRef &State,
+                                              const Expr *Ex,
+                                              const MemRegion *MR) {
+  auto &svalBuilder = C.getSValBuilder();
+  auto sizeTy = svalBuilder.getContext().getSizeType();
+  auto strLength = svalBuilder.getMetadataSymbolVal(MallocChecker::getTag(), MR,
+                                                    Ex, sizeTy, C.blockCount());
+  if (auto strLn = strLength.getAs<NonLoc>()) {
+    // In case of unbounded calls strlen etc bound the range to SIZE_MAX/4
+    auto &BVF = svalBuilder.getBasicValueFactory();
+    const auto &maxValInt = BVF.getMaxValue(sizeTy);
+    auto fourInt = APSIntType(maxValInt).getValue(4);
+    const auto *maxLengthInt = BVF.evalAPSInt(BO_Div, maxValInt, fourInt);
+    auto maxLength = svalBuilder.makeIntVal(*maxLengthInt);
+    auto evalLength =
+        svalBuilder.evalBinOpNN(State, BO_LE, *strLn, maxLength, sizeTy);
+    State = State->assume(evalLength.castAs<DefinedOrUnknownSVal>(), true);
+  }
+
+  return strLength;
+}
+
 LeakInfo
 MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
                                  CheckerContext &C) const {
   const LocationContext *LeakContext = N->getLocationContext();
   // Walk the ExplodedGraph backwards and find the first node that referred to
   // the tracked symbol.
   const ExplodedNode *AllocNode = N;
   const MemRegion *ReferenceRegion = nullptr;

test/Analysis/malloc.c

 // Potentially, the user could free the struct by performing pointer arithmetic on the return value.
 // This is a variation of the specialMalloc issue, though probably would be more rare in correct code.
 int *specialMallocWithStruct() {
   struct StructWithInt *px= malloc(sizeof(struct StructWithInt));
   return &(px->g);
 }
 
 // Test various allocation/deallocation functions.
-void testStrdup(const char *s, unsigned validIndex) {
+void testStrdup(const char *s) {
   char *s2 = strdup(s);
-  s2[validIndex + 1] = 'b';
 } // expected-warning {{Potential leak of memory pointed to by}}
 
-void testWinStrdup(const char *s, unsigned validIndex) {
+void testWinStrdup(const char *s) {
   char *s2 = _strdup(s);
-  s2[validIndex + 1] = 'b';
 } // expected-warning {{Potential leak of memory pointed to by}}
 
-void testWcsdup(const wchar_t *s, unsigned validIndex) {
+void testWcsdup(const wchar_t *s) {
   wchar_t *s2 = wcsdup(s);
-  s2[validIndex + 1] = 'b';
 } // expected-warning {{Potential leak of memory pointed to by}}
 
-void testWinWcsdup(const wchar_t *s, unsigned validIndex) {
+void testWinWcsdup(const wchar_t *s) {
   wchar_t *s2 = _wcsdup(s);
-  s2[validIndex + 1] = 'b';
 } // expected-warning {{Potential leak of memory pointed to by}}
 
-int testStrndup(const char *s, unsigned validIndex, unsigned size) {
+void testStrndup(const char *s, unsigned size) {
   char *s2 = strndup(s, size);
-  s2 [validIndex + 1] = 'b';
-  if (s2[validIndex] != 'a')
-    return 0;
-  else
-    return 1;// expected-warning {{Potential leak of memory pointed to by}}
-}
+} // expected-warning {{Potential leak of memory pointed to by}}
+
+void testStrdupOverwritten(const char *s) {
+  char *s2 = strdup(s);
+  s2 = 0;
+} // expected-warning {{Potential leak of memory pointed to by}}
+
+void testWinStrdupOverwritten(const char *s) {
+  char *s2 = _strdup(s);
+  s2 = 0;
+} // expected-warning {{Potential leak of memory pointed to by}}
+
+void testWcsdupOverwritten(const wchar_t *s) {
+  wchar_t *s2 = wcsdup(s);
+  s2 = 0;
+} // expected-warning {{Potential leak of memory pointed to by}}
+
+void testWinWcsdupOverwritten(const wchar_t *s) {
+  wchar_t *s2 = _wcsdup(s);
+  s2 = 0;
+} // expected-warning {{Potential leak of memory pointed to by}}
+
+void testStrndupOverwritten(const char *s, unsigned size) {
+  char *s2 = strndup(s, size);
+  s2 = 0;
+} // expected-warning {{Potential leak of memory pointed to by}}
 
-void testStrdupContentIsDefined(const char *s, unsigned validIndex) {
+void testStrdupContentIsDefined(const char *s) {
   char *s2 = strdup(s);
   char result = s2[1];// no warning
   free(s2);
 }
 
-void testWinStrdupContentIsDefined(const char *s, unsigned validIndex) {
+void testWinStrdupContentIsDefined(const char *s) {
   char *s2 = _strdup(s);
   char result = s2[1];// no warning
   free(s2);
 }
 
-void testWcsdupContentIsDefined(const wchar_t *s, unsigned validIndex) {
+void testWcsdupContentIsDefined(const wchar_t *s) {
   wchar_t *s2 = wcsdup(s);
   wchar_t result = s2[1];// no warning
   free(s2);
 }
 
-void testWinWcsdupContentIsDefined(const wchar_t *s, unsigned validIndex) {
+void testWinWcsdupContentIsDefined(const wchar_t *s) {
   wchar_t *s2 = _wcsdup(s);
   wchar_t result = s2[1];// no warning
   free(s2);
 }
 
 // ----------------------------------------------------------------------------
 // Test the system library functions to which the pointer can escape.
 // This tests false positive suppression.

test/Analysis/pr22954.c

 }
 
 int f28(int i, int j, int k, int l) {
   struct mm m28[2];
   m28[i].s4 = strdup("hello");
   m28[j].s3[k] = 1;
   struct ll * l28 = (struct ll*)(&m28[1]);
   l28->s1[l] = 2;
-  char input[] = {'a', 'b', 'c', 'd'};
+  char input[] = {'a', 'b', 'c', 'd'}; // \
+  expected-warning{{Potential leak of memory pointed to by field 's4'}}
   memcpy(l28->s1, input, 4);
   clang_analyzer_eval(m28[0].s3[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[0].s3[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[0].s3[2] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[0].s3[3] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[1].s3[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[1].s3[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[1].s3[2] == 1); // expected-warning{{UNKNOWN}}

test/Analysis/unions.cpp

void testInvalidation() {
     uu.s = strdup("");
 
     IntOrString vv;
     char str[] = "abc";
     vv.s = str;
 
     // FIXME: This is a leak of uu.s.
     uu = vv;
-  }
+  } // expected-warning{{leak}}
 
   void testIndirectInvalidation() {
     IntOrString uu;
     char str[] = "abc";
     uu.s = str;
 
     clang_analyzer_eval(uu.s[0] == 'a'); // expected-warning{{TRUE}}
 
     process(uu);
     clang_analyzer_eval(uu.s[0] == 'a'); // expected-warning{{UNKNOWN}}
   }
 }