[analyzer][StdLibraryFunctionsChecker] Fix a BufferSize constraint crash

[martong]

Summary

It could happen that both the satisfied and unsatisfied constraints gave
a NULL state. This happened probably because the negate() functionality
was not perfect. The solution is to return both states from the assume
calls where it makes sense.
This way the code becomes cleaner, there is no need anymore for the
controversial negate().

Note that this causes a regression in our CTU builds.
http://codechecker-buildbot.eastus.cloudapp.azure.com:8080/job/ctu_pipeline_clang-master-monorepo/1720/
The error itself is not CTU related, however, the coverage and thus the path is different in that mode.

[martong]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

725

This is where we crashed before this fix.

[steakhal]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

235–247

I suggest the same simpler version for the similar code segments as well.

By the same token, why do you return {State, State}?
Shouldn't you return {State, nullptr} there?
In general, one would not expect the same State being returned, IMO it's advised to avoid doing that.
Same applies for the other cases.

339–340

Why don't you castAs? That also has the corresponding assert inside.

[martong]

• apply -> assume, Add isApplicable

[martong]

Alright, I refactored the change a bit. A Constraint::assume works similarly to an engine DualAssume. Plus I added isApplicable to check if it is meaningful to call the assume at all.

[martong]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

725

assert(SuccessSt); should not ever fail. Seems like the logic is not flawed in negate rather there is an issue in the underlying RangeConstraintManager: the analyzer goes on with an unfeasible path.

See the post-commit comments here: https://reviews.llvm.org/D82445

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

class StdLibraryFunctionsChecker
   /// Polymorphic base class that represents a constraint on a given argument
   /// (or return value) of a function. Derived classes implement different kind
   /// of constraints, e.g range constraints or correlation between two
   /// arguments.
   class ValueConstraint {
   public:
     ValueConstraint(ArgNo ArgN) : ArgN(ArgN) {}
     virtual ~ValueConstraint() {}
-    /// Apply the effects of the constraint on the given program state. If null
-    /// is returned then the constraint is not feasible.
-    virtual ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
-                                  const Summary &Summary,
-                                  CheckerContext &C) const = 0;
-    virtual ValueConstraintPtr negate() const {
-      llvm_unreachable("Not implemented");
-    };
+
+    /// Returns true if we can do any assumption on the constraint, i.e. if it
+    /// is meaningful to call an Engine `assume` function.
+    virtual bool isApplicable(ProgramStateRef State, const CallEvent &Call,
+
+    /// Returns the program states for the cases when the constraint is
+    /// satisfiable and non satisfiable.
+    virtual std::pair<ProgramStateRef, ProgramStateRef>
+    assume(ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
+           CheckerContext &C) const = 0;
 
     // Check whether the constraint is malformed or not. It is malformed if the
     // specified argument has a mismatch with the given FunctionDecl (e.g. the
     // arg number is out-of-range of the function's argument list).
     bool checkValidity(const FunctionDecl *FD) const {
       const bool ValidArg = ArgN == Ret || ArgN < FD->getNumParams();
       assert(ValidArg && "Arg out of range!");
       if (!ValidArg)
private:
     ProgramStateRef applyAsOutOfRange(ProgramStateRef State,
                                       const CallEvent &Call,
                                       const Summary &Summary) const;
     ProgramStateRef applyAsWithinRange(ProgramStateRef State,
                                        const CallEvent &Call,
                                        const Summary &Summary) const;
 
   public:
-    ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
-                          const Summary &Summary,
-                          CheckerContext &C) const override {
-      switch (Kind) {
-      case OutOfRange:
-        return applyAsOutOfRange(State, Call, Summary);
-      case WithinRange:
-        return applyAsWithinRange(State, Call, Summary);
-      }
-      llvm_unreachable("Unknown range kind!");
+    bool isApplicable(ProgramStateRef State, const CallEvent &Call,
+      SVal V = getArgSVal(Call, getArgNo());
+      return V.getAs<NonLoc>().hasValue();
     }
 
-    ValueConstraintPtr negate() const override {
-      RangeConstraint Tmp(*this);
+    std::pair<ProgramStateRef, ProgramStateRef>
+    assume(ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
+           CheckerContext &C) const override {
       switch (Kind) {
       case OutOfRange:
-        Tmp.Kind = WithinRange;
-        break;
+        return {applyAsOutOfRange(State, Call, Summary),
+                applyAsWithinRange(State, Call, Summary)};
       case WithinRange:
-        Tmp.Kind = OutOfRange;
-        break;
+        return {applyAsWithinRange(State, Call, Summary),
+                applyAsOutOfRange(State, Call, Summary)};
       }
-      return std::make_shared<RangeConstraint>(Tmp);
+      llvm_unreachable("Unknown range kind!");
     }
 
     bool checkSpecificValidity(const FunctionDecl *FD) const override {
       const bool ValidArg =
           getArgType(FD, ArgN)->isIntegralType(FD->getASTContext());
       assert(ValidArg &&
              "This constraint should be applied on an integral type");
       return ValidArg;
     }
   };
 
   class ComparisonConstraint : public ValueConstraint {
     BinaryOperator::Opcode Opcode;
     ArgNo OtherArgN;
 
   public:
     virtual StringRef getName() const override { return "Comparison"; };
     ComparisonConstraint(ArgNo ArgN, BinaryOperator::Opcode Opcode,
                          ArgNo OtherArgN)
         : ValueConstraint(ArgN), Opcode(Opcode), OtherArgN(OtherArgN) {}
     ArgNo getOtherArgNo() const { return OtherArgN; }
     BinaryOperator::Opcode getOpcode() const { return Opcode; }
-    ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
-                          const Summary &Summary,
-                          CheckerContext &C) const override;
+
+    bool isApplicable(ProgramStateRef State, const CallEvent &Call,
+                      CheckerContext &C) const override {
+      SVal V = getArgSVal(Call, getArgNo());
+      SVal OtherV = getArgSVal(Call, getOtherArgNo());
+      return !(V.isUndef() || OtherV.isUndef());
+    }
+
+    std::pair<ProgramStateRef, ProgramStateRef>
+    assume(ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
   };
 
   class NotNullConstraint : public ValueConstraint {
     using ValueConstraint::ValueConstraint;
-    // This variable has a role when we negate the constraint.
-    bool CannotBeNull = true;
 
   public:
     StringRef getName() const override { return "NonNull"; }
-    ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
-                          const Summary &Summary,
-                          CheckerContext &C) const override {
+
+    bool isApplicable(ProgramStateRef State, const CallEvent &Call,
       SVal V = getArgSVal(Call, getArgNo());
-      if (V.isUndef())
-        return State;
-
-      DefinedOrUnknownSVal L = V.castAs<DefinedOrUnknownSVal>();
-      if (!L.getAs<Loc>())
-        return State;
-
-      return State->assume(L, CannotBeNull);
+      return V.getAs<Loc>().hasValue();
     }
 
-    ValueConstraintPtr negate() const override {
-      NotNullConstraint Tmp(*this);
-      Tmp.CannotBeNull = !this->CannotBeNull;
-      return std::make_shared<NotNullConstraint>(Tmp);
+    std::pair<ProgramStateRef, ProgramStateRef>
+    assume(ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
+           CheckerContext &C) const override {
+      return State->assume(getArgSVal(Call, getArgNo()).castAs<Loc>());
     }
 
     bool checkSpecificValidity(const FunctionDecl *FD) const override {
       const bool ValidArg = getArgType(FD, ArgN)->isPointerType();
       assert(ValidArg &&
              "This constraint should be applied only on a pointer type");
       return ValidArg;
     }
class BufferSizeConstraint : public ValueConstraint {
     // The concrete value which is the minimum size for the buffer.
     llvm::Optional<llvm::APSInt> ConcreteSize;
     // The argument which holds the size of the buffer.
     llvm::Optional<ArgNo> SizeArgN;
     // The argument which is a multiplier to size. This is set in case of
     // `fread` like functions where the size is computed as a multiplication of
     // two arguments.
     llvm::Optional<ArgNo> SizeMultiplierArgN;
-    // The operator we use in apply. This is negated in negate().
-    BinaryOperator::Opcode Op = BO_LE;
 
   public:
     StringRef getName() const override { return "BufferSize"; }
     BufferSizeConstraint(ArgNo Buffer, llvm::APSInt BufMinSize)
         : ValueConstraint(Buffer), ConcreteSize(BufMinSize) {}
     BufferSizeConstraint(ArgNo Buffer, ArgNo BufSize)
         : ValueConstraint(Buffer), SizeArgN(BufSize) {}
     BufferSizeConstraint(ArgNo Buffer, ArgNo BufSize, ArgNo BufSizeMultiplier)
         : ValueConstraint(Buffer), SizeArgN(BufSize),
           SizeMultiplierArgN(BufSizeMultiplier) {}
 
-    ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
-                          const Summary &Summary,
-                          CheckerContext &C) const override {
+    bool isApplicable(ProgramStateRef State, const CallEvent &Call,
+      SVal BufV = getArgSVal(Call, getArgNo());
+      if (BufV.isUndef())
+        return false;
+      if (SizeArgN) {
+        // The size argument.
+        SVal SizeV = getArgSVal(Call, *SizeArgN);
+        if (SizeV.isUndef())
+          return false;
+        if (SizeMultiplierArgN) {
+          SVal SizeMulV = getArgSVal(Call, *SizeMultiplierArgN);
+          if (SizeMulV.isUndef())
+            return false;
+        }
+      }
+      return true;
+    }
+
+    std::pair<ProgramStateRef, ProgramStateRef>
+    assume(ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
+           CheckerContext &C) const override {
       SValBuilder &SvalBuilder = C.getSValBuilder();
       // The buffer argument.
       SVal BufV = getArgSVal(Call, getArgNo());
 
       // Get the size constraint.
       const SVal SizeV = [this, &State, &Call, &Summary, &SvalBuilder]() {
         if (ConcreteSize) {
           return SVal(SvalBuilder.makeIntVal(*ConcreteSize));
assume(ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
           llvm_unreachable("The constraint must be either a concrete value or "
                            "encoded in an arguement.");
         }
       }();
 
       // The dynamic size of the buffer argument, got from the analyzer engine.
       SVal BufDynSize = getDynamicSizeWithOffset(State, BufV);
 
-      SVal Feasible = SvalBuilder.evalBinOp(State, Op, SizeV, BufDynSize,
+      SVal Feasible = SvalBuilder.evalBinOp(State, BO_LE, SizeV, BufDynSize,
                                             SvalBuilder.getContext().BoolTy);
-      if (auto F = Feasible.getAs<DefinedOrUnknownSVal>())
-        return State->assume(*F, true);
-
-      // We can get here only if the size argument or the dynamic size is
-      // undefined. But the dynamic size should never be undefined, only
-      // unknown. So, here, the size of the argument is undefined, i.e. we
-      // cannot apply the constraint. Actually, other checkers like
-      // CallAndMessage should catch this situation earlier, because we call a
-      // function with an uninitialized argument.
-      llvm_unreachable("Size argument or the dynamic size is Undefined");
-    }
-
-    ValueConstraintPtr negate() const override {
-      BufferSizeConstraint Tmp(*this);
-      Tmp.Op = BinaryOperator::negateComparisonOp(Op);
-      return std::make_shared<BufferSizeConstraint>(Tmp);
+      return State->assume(Feasible.castAs<DefinedOrUnknownSVal>());
     }
 
     bool checkSpecificValidity(const FunctionDecl *FD) const override {
       const bool ValidArg = getArgType(FD, ArgN)->isPointerType();
       assert(ValidArg &&
              "This constraint should be applied only on a pointer type");
       return ValidArg;
     }
ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsOutOfRange(
 
   ProgramStateManager &Mgr = State->getStateManager();
   SValBuilder &SVB = Mgr.getSValBuilder();
   BasicValueFactory &BVF = SVB.getBasicValueFactory();
   ConstraintManager &CM = Mgr.getConstraintManager();
   QualType T = Summary.getArgType(getArgNo());
   SVal V = getArgSVal(Call, getArgNo());
 
-  if (auto N = V.getAs<NonLoc>()) {
-    const IntRangeVector &R = getRanges();
-    size_t E = R.size();
-    for (size_t I = 0; I != E; ++I) {
-      const llvm::APSInt &Min = BVF.getValue(R[I].first, T);
-      const llvm::APSInt &Max = BVF.getValue(R[I].second, T);
-      assert(Min <= Max);
-      State = CM.assumeInclusiveRange(State, *N, Min, Max, false);
-      if (!State)
-        break;
-    }
-  }
+  auto N = V.castAs<NonLoc>();
+    State = CM.assumeInclusiveRange(State, N, Min, Max, false);
 
   return State;
 }
 
 ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsWithinRange(
     ProgramStateRef State, const CallEvent &Call,
     const Summary &Summary) const {
   if (Ranges.empty())
ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsWithinRange(
   // We cut off [T_MIN, min(R) - 1] and [max(R) + 1, T_MAX] if necessary,
   // and then cut away all holes in R one by one.
   //
   // E.g. consider a range list R as [A, B] and [C, D]
   // -------+--------+------------------+------------+----------->
   //        A        B                  C            D
   // Then we assume that the value is not in [-inf, A - 1],
   // then not in [D + 1, +inf], then not in [B + 1, C - 1]
-  if (auto N = V.getAs<NonLoc>()) {
-    const IntRangeVector &R = getRanges();
-    size_t E = R.size();
+  auto N = V.castAs<NonLoc>();
 
-    const llvm::APSInt &MinusInf = BVF.getMinValue(T);
-    const llvm::APSInt &PlusInf = BVF.getMaxValue(T);
 
-    const llvm::APSInt &Left = BVF.getValue(R[0].first - 1ULL, T);
-    if (Left != PlusInf) {
-      assert(MinusInf <= Left);
-      State = CM.assumeInclusiveRange(State, *N, MinusInf, Left, false);
-      if (!State)
-        return nullptr;
-    }
+    State = CM.assumeInclusiveRange(State, N, MinusInf, Left, false);
 
-    const llvm::APSInt &Right = BVF.getValue(R[E - 1].second + 1ULL, T);
-    if (Right != MinusInf) {
-      assert(Right <= PlusInf);
-      State = CM.assumeInclusiveRange(State, *N, Right, PlusInf, false);
-      if (!State)
-        return nullptr;
-    }
+    State = CM.assumeInclusiveRange(State, N, Right, PlusInf, false);
 
-    for (size_t I = 1; I != E; ++I) {
-      const llvm::APSInt &Min = BVF.getValue(R[I - 1].second + 1ULL, T);
-      const llvm::APSInt &Max = BVF.getValue(R[I].first - 1ULL, T);
-      if (Min <= Max) {
-        State = CM.assumeInclusiveRange(State, *N, Min, Max, false);
-        if (!State)
-          return nullptr;
-      }
-    }
-  }
+      State = CM.assumeInclusiveRange(State, N, Min, Max, false);
 
   return State;
 }
 
-ProgramStateRef StdLibraryFunctionsChecker::ComparisonConstraint::apply(
+std::pair<ProgramStateRef, ProgramStateRef>
+StdLibraryFunctionsChecker::ComparisonConstraint::assume(
     ProgramStateRef State, const CallEvent &Call, const Summary &Summary,
     CheckerContext &C) const {
 
   ProgramStateManager &Mgr = State->getStateManager();
   SValBuilder &SVB = Mgr.getSValBuilder();
   QualType CondT = SVB.getConditionType();
   QualType T = Summary.getArgType(getArgNo());
   SVal V = getArgSVal(Call, getArgNo());
 
   BinaryOperator::Opcode Op = getOpcode();
   ArgNo OtherArg = getOtherArgNo();
   SVal OtherV = getArgSVal(Call, OtherArg);
   QualType OtherT = Summary.getArgType(OtherArg);
   // Note: we avoid integral promotion for comparison.
   OtherV = SVB.evalCast(OtherV, T, OtherT);
-  if (auto CompV = SVB.evalBinOp(State, Op, V, OtherV, CondT)
-                       .getAs<DefinedOrUnknownSVal>())
-    State = State->assume(*CompV, true);
-  return State;
+  auto CompV =
+      SVB.evalBinOp(State, Op, V, OtherV, CondT).castAs<DefinedOrUnknownSVal>();
+  return State->assume(CompV);
 }
 
 void StdLibraryFunctionsChecker::checkPreCall(const CallEvent &Call,
                                               CheckerContext &C) const {
   Optional<Summary> FoundSummary = findFunctionSummary(Call, C);
   if (!FoundSummary)
     return;
 
   const Summary &Summary = *FoundSummary;
   ProgramStateRef State = C.getState();
 
   ProgramStateRef NewState = State;
   for (const ValueConstraintPtr &Constraint : Summary.getArgConstraints()) {
-    ProgramStateRef SuccessSt = Constraint->apply(NewState, Call, Summary, C);
-    ProgramStateRef FailureSt =
-        Constraint->negate()->apply(NewState, Call, Summary, C);
+    if (!Constraint->isApplicable(NewState, Call, Summary, C))
+      continue;
+    ProgramStateRef SuccessSt, FailureSt;
+    std::tie(SuccessSt, FailureSt) =
+        Constraint->assume(NewState, Call, Summary, C);
     // The argument constraint is not satisfied.
     if (FailureSt && !SuccessSt) {
       if (ExplodedNode *N = C.generateErrorNode(NewState))
         reportBug(Call, N, Constraint.get(), C);
       break;
     } else {
       // We will apply the constraint even if we cannot reason about the
       // argument. This means both SuccessSt and FailureSt can be true. If we
       // weren't applying the constraint that would mean that symbolic
       // execution continues on a code whose behaviour is undefined.
       assert(SuccessSt);
       NewState = SuccessSt;
     }
   }
   if (NewState && NewState != State)
     C.addTransition(NewState);
 }
 
 void StdLibraryFunctionsChecker::checkPostCall(const CallEvent &Call,
                                                CheckerContext &C) const {
   Optional<Summary> FoundSummary = findFunctionSummary(Call, C);
   if (!FoundSummary)
     return;
 
   // Now apply the constraints.
   const Summary &Summary = *FoundSummary;
   ProgramStateRef State = C.getState();
 
   // Apply case/branch specifications.
   for (const ConstraintSet &Case : Summary.getCaseConstraints()) {
     ProgramStateRef NewState = State;
     for (const ValueConstraintPtr &Constraint : Case) {
-      NewState = Constraint->apply(NewState, Call, Summary, C);
+      std::tie(NewState, std::ignore) =
+          Constraint->assume(NewState, Call, Summary, C);
       if (!NewState)
         break;
     }
 
     if (NewState && NewState != State)
       C.addTransition(NewState);
   }
 }

clang/test/Analysis/std-c-library-functions.c

 void test_fread_uninitialized(void) {
   void *ptr;
   size_t sz;
   size_t nmem;
   FILE *fp;
   (void)fread(ptr, sz, nmem, fp); // expected-warning {{1st function call argument is an uninitialized value}}
 }
 
+static void test_fread_buffer_size_constraint_no_crash(FILE *f, size_t n) {
+  size_t rlen; /* how much to read */
+  size_t nr;   /* number of chars actually read */
+  char b[8192];
+  rlen = 8192;
+  do {
+    char *p = b;
+    if (rlen > n)
+      rlen = n; /* cannot read more than asked */
+    nr = fread(p, sizeof(char), rlen, f);
+    n -= nr;                     /* still have to read `n' chars */
+  } while (n > 0 && nr == rlen); /* until end of count or eof */
+}
+// Test that we do not crash here.
+void test_fread_buffer_size_constraint_no_crash_caller(FILE *f) {
+  /* read MAX_SIZE_T chars */
+  test_fread_buffer_size_constraint_no_crash(f, ~((size_t)0));
+}
+
 ssize_t getline(char **, size_t *, FILE *);
 void test_getline(FILE *fp) {
   char *line = 0;
   size_t n = 0;
   ssize_t len;
   while ((len = getline(&line, &n, fp)) != -1) {
     clang_analyzer_eval(len == 0); // expected-warning{{FALSE}}
   }