[analyzer] ApiModeling: Add buffer size arg constraint

[martong]

Summary

Introducing a new argument constraint to confine buffer sizes. It is typical in
C APIs that a parameter represents a buffer and another param holds the size of
the buffer (or the size of the data we want to handle from the buffer).

[Charusso]

Please avoid to stuff in CheckerContext because this facility should be used by ExprEngine/Store as well.
Let us reword your API: getDynamicSizeWithOffset(ProgramStateRef, SVal, SValBuilder &). Of course we are trying to obtain some buffer-ish size, that is the purpose of the entire API.
I also could imagine something like getDynamicSizeMul(ProgramStateRef, const MemRegion &, const MemRegion &, SValBuilder &), as it is very common.

May it would make sense to use the API like:

getDynamicSizeWithOffset(State, MR, SVB) {
  Offset = State->getStoreManager().getStaticOffset(MR, SVB);
  ...
}

This idea is similar to MemRegionManager::getStaticSize(MR, SVB). Hopefully no-one needs dynamic offsets.

[Charusso]

In D77066#1953280, @Charusso wrote:

getDynamicSizeWithOffset(State, MR, SVB) {
  Offset = State->getStoreManager().getStaticOffset(MR, SVB);
  ...
}

Hm, the MemRegion's offset should be great. I was thinking about if we would store SVal offsets in the Store.

[martong]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

253

Use BinaryOperator::negateComparisonOp

[martong]

• Rebase to master
• Use BinaryOperator::negateComparisonOp
• getBufferDynamicSize -> getDynamicSizeWithOffset

[martong]

In D77066#1953280, @Charusso wrote:

Please avoid to stuff in CheckerContext because this facility should be used by ExprEngine/Store as well.
Let us reword your API: getDynamicSizeWithOffset(ProgramStateRef, SVal, SValBuilder &). Of course we are trying to obtain some buffer-ish size, that is the purpose of the entire API.
I also could imagine something like getDynamicSizeMul(ProgramStateRef, const MemRegion &, const MemRegion &, SValBuilder &), as it is very common.

May it would make sense to use the API like:

getDynamicSizeWithOffset(State, MR, SVB) {
  Offset = State->getStoreManager().getStaticOffset(MR, SVB);
  ...
}

This idea is similar to MemRegionManager::getStaticSize(MR, SVB). Hopefully no-one needs dynamic offsets.

Thanks for the review! I've update the API as you suggested.

[martong]

Ping

[martong]

• Rebase to master

[Szelethus]

I'm not familiar enough with DynamicSize.cpp to judge the changes there, but aside from a few nits, this LGTM.

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

246–247

Would an unreachable be appropriate here then?

1007

In most places, where we refer to an argument number, we use ArgNo. Is there a reason we don't do that here? Can we enforce greater type safety?

[martong]

• REBASE to master
• Add assert
• Create the BufferSize arg constraints in a more readable way

The rebase to master makes a bit hard to see the exact changes in this update. I should have done the rebase in a separate update, sorry about that.

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

246–247

Yes, good point, just added that. CallAndMessage is already a dependency, so this must not fire.

1007

Yeah, good point, I am going with this:

BufferSize(/*Buffer=*/ArgNo(0), /*BufSize=*/ArgNo(1))));

About type safety: I was thinking about a strong typedef, but we don't actually have a convenient template for that in LLVM. And most of the time here in LLVM people just apply the /*Arg=*/ pythonish form.

[Szelethus]

LGTM! I think you could remove the extra parameter, but I don't think this warrants another round of review on my end. However, the dynamic size change seems very unfamiliar to me. @baloghadamsoftware, @balazske, could you take a peek?

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

234

You can retrieve SValBuilder from ProgramState: State->getStateManager().getSValBuilder().

[martong]

• Remove SValBuilder param

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

234

Thanks!

[Szelethus]

In D77066#2062849, @martong wrote:

• Remove SValBuilder param

I failed to emphasize that the point was to remove the new CheckerContext parameters :)

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h

DefinedOrUnknownSVal getDynamicSize(ProgramStateRef State, const MemRegion *MR,
                                     SValBuilder &SVB);
 
 /// Get the stored element count of the region \p MR.
 DefinedOrUnknownSVal getDynamicElementCount(ProgramStateRef State,
                                             const MemRegion *MR,
                                             SValBuilder &SVB,
                                             QualType ElementTy);
 
+class CheckerContext;
+/// Get the dynamic size for a symbolic value that represents a buffer. If
+/// there is an offsetting to the underlying buffer we consider that too.
+/// Returns with an SVal that represents the size, this is Unknown if the
+/// engine cannot deduce the size.
+/// E.g.
+///   char buf[3];
+///   (buf); // size is 3
+///   (buf + 1); // size is 2
+///   (buf + 3); // size is 0
+///   (buf + 4); // size is -1
+///
+///   char *bufptr;
+///   (bufptr) // size is unknown
+SVal getBufferDynamicSize(const SVal &BufV, ProgramStateRef State,
+                        CheckerContext &C);
+
 } // namespace ento
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICSIZE_H

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

private:
   BugType BT{this, "Insufficient storage for placement new",
              categories::MemoryError};
 };
 } // namespace
 
 SVal PlacementNewChecker::getExtentSizeOfPlace(const Expr *Place,
                                                ProgramStateRef State,
                                                CheckerContext &C) const {
-  const MemRegion *MRegion = C.getSVal(Place).getAsRegion();
-  if (!MRegion)
-    return UnknownVal();
-  RegionOffset Offset = MRegion->getAsOffset();
-  if (Offset.hasSymbolicOffset())
-    return UnknownVal();
-  const MemRegion *BaseRegion = MRegion->getBaseRegion();
-  if (!BaseRegion)
-    return UnknownVal();
-
-  SValBuilder &SvalBuilder = C.getSValBuilder();
-  NonLoc OffsetInBytes = SvalBuilder.makeArrayIndex(
-      Offset.getOffset() / C.getASTContext().getCharWidth());
-  DefinedOrUnknownSVal ExtentInBytes =
-      getDynamicSize(State, BaseRegion, SvalBuilder);
-
-  return SvalBuilder.evalBinOp(State, BinaryOperator::Opcode::BO_Sub,
-                               ExtentInBytes, OffsetInBytes,
-                               SvalBuilder.getArrayIndexType());
+  return getBufferDynamicSize(C.getSVal(Place), State, C);
 }
 
 SVal PlacementNewChecker::getExtentSizeOfNewTarget(const CXXNewExpr *NE,
                                                    ProgramStateRef State,
                                                    CheckerContext &C) const {
   SValBuilder &SvalBuilder = C.getSValBuilder();
   QualType ElementType = NE->getAllocatedType();
   ASTContext &AstContext = C.getASTContext();

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

 
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.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/CheckerHelpers.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 
 using namespace clang;
 using namespace clang::ento;
 
 namespace {
 class StdLibraryFunctionsChecker
     : public Checker<check::PreCall, check::PostCall, eval::Call> {
   /// Below is a series of typedefs necessary to define function specs.
class StdLibraryFunctionsChecker
   /// 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) const = 0;
+                                  const Summary &Summary,
+                                  CheckerContext &C) const = 0;
     virtual ValueConstraintPtr negate() const {
       llvm_unreachable("Not implemented");
     };
     ArgNo getArgNo() const { return ArgN; }
 
   protected:
     ArgNo ArgN; // Argument to which we apply the constraint.
   };
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) const override {
+                          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!");
     }
class StdLibraryFunctionsChecker
 
   public:
     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) const override;
+                          const Summary &Summary,
+                          CheckerContext &C) const override;
   };
 
   class NotNullConstraint : public ValueConstraint {
     using ValueConstraint::ValueConstraint;
     // This variable has a role when we negate the constraint.
     bool CannotBeNull = true;
 
   public:
     ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
-                          const Summary &Summary) const override {
+                          const Summary &Summary,
+                          CheckerContext &C) const override {
       SVal V = getArgSVal(Call, getArgNo());
       DefinedOrUnknownSVal L = V.castAs<DefinedOrUnknownSVal>();
       if (!L.getAs<Loc>())
         return State;
 
       return State->assume(L, CannotBeNull);
     }
 
     ValueConstraintPtr negate() const override {
       NotNullConstraint Tmp(*this);
       Tmp.CannotBeNull = !this->CannotBeNull;
       return std::make_shared<NotNullConstraint>(Tmp);
     }
   };
 
+  // Represents a buffer argument with an additional size argument.
+  // E.g. the first two arguments here:
+  //   ctime_s(char *buffer, rsize_t bufsz, const time_t *time);
+  class BufferSizeConstraint : public ValueConstraint {
+    // The argument which holds the size of the buffer.
+    ArgNo SizeArgN;
+    // The operator we use in apply. This is negated in negate().
+    BinaryOperator::Opcode Op = BO_LE;
+
+  public:
+    BufferSizeConstraint(ArgNo BufArgN, ArgNo SizeArgN)
+        : ValueConstraint(BufArgN), SizeArgN(SizeArgN) {}
+
+    ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call,
+                          const Summary &Summary,
+                          CheckerContext &C) const override {
+      // The buffer argument.
+      SVal BufV = getArgSVal(Call, getArgNo());
+      // The size argument.
+      SVal SizeV = getArgSVal(Call, SizeArgN);
+      // The dynamic size of the buffer argument, got from the analyzer engine.
+      SVal BufDynSize = getBufferDynamicSize(BufV, State, C);
+
+      SValBuilder &SvalBuilder = C.getSValBuilder();
+      SVal Feasible = SvalBuilder.evalBinOp(State, Op, 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.
+      return nullptr;
+    }
+
+    ValueConstraintPtr negate() const override {
+      BufferSizeConstraint Tmp(*this);
+
+      // FIXME Implement a generic negate for all BO values.
+      assert(Tmp.Op == BO_LE && "Op should be <=");
+      Tmp.Op = BO_GT;
+
+      return std::make_shared<BufferSizeConstraint>(Tmp);
+    }
+  };
+
   /// The complete list of constraints that defines a single branch.
   typedef std::vector<ValueConstraintPtr> ConstraintSet;
 
   using ArgTypes = std::vector<QualType>;
   using Cases = std::vector<ConstraintSet>;
 
   /// Includes information about
   ///   * function prototype (which is necessary to
for (size_t I = 1; I != E; ++I) {
       }
     }
   }
 
   return State;
 }
 
 ProgramStateRef StdLibraryFunctionsChecker::ComparisonConstraint::apply(
-    ProgramStateRef State, const CallEvent &Call,
-    const Summary &Summary) const {
+    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 = getArgType(Summary, getArgNo());
   SVal V = getArgSVal(Call, getArgNo());
 
   BinaryOperator::Opcode Op = getOpcode();
void StdLibraryFunctionsChecker::checkPreCall(const CallEvent &Call,
   if (!FoundSummary)
     return;
 
   const Summary &Summary = *FoundSummary;
   ProgramStateRef State = C.getState();
 
   ProgramStateRef NewState = State;
   for (const ValueConstraintPtr& VC : Summary.ArgConstraints) {
-    ProgramStateRef SuccessSt = VC->apply(NewState, Call, Summary);
-    ProgramStateRef FailureSt = VC->negate()->apply(NewState, Call, Summary);
+    ProgramStateRef SuccessSt = VC->apply(NewState, Call, Summary, C);
+    ProgramStateRef FailureSt = VC->negate()->apply(NewState, Call, Summary, C);
     // The argument constraint is not satisfied.
     if (FailureSt && !SuccessSt) {
       if (ExplodedNode *N = C.generateErrorNode(NewState))
         reportBug(Call, N, 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
void StdLibraryFunctionsChecker::checkPostCall(const CallEvent &Call,
   // Now apply the constraints.
   const Summary &Summary = *FoundSummary;
   ProgramStateRef State = C.getState();
 
   // Apply case/branch specifications.
   for (const auto &VRS : Summary.CaseConstraints) {
     ProgramStateRef NewState = State;
     for (const auto &VR: VRS) {
-      NewState = VR->apply(NewState, Call, Summary);
+      NewState = VR->apply(NewState, Call, Summary, C);
       if (!NewState)
         break;
     }
 
     if (NewState && NewState != State)
       C.addTransition(NewState);
   }
 }
void StdLibraryFunctionsChecker::initFunctionSummaries(
   // Please update the list of functions in the header after editing!
   //
 
   // Below are helpers functions to create the summaries.
   auto ArgumentCondition = [](ArgNo ArgN, RangeKind Kind,
                               IntRangeVector Ranges) {
     return std::make_shared<RangeConstraint>(ArgN, Kind, Ranges);
   };
+  auto BufferSize = [](ArgNo BufArgN, ArgNo SizeArgN) {
+    return std::make_shared<BufferSizeConstraint>(BufArgN, SizeArgN);
+  };
   struct {
     auto operator()(RangeKind Kind, IntRangeVector Ranges) {
       return std::make_shared<RangeConstraint>(Ret, Kind, Ranges);
     }
     auto operator()(BinaryOperator::Opcode Op, ArgNo OtherArgN) {
       return std::make_shared<ComparisonConstraint>(Ret, Op, OtherArgN);
     }
   } ReturnValueCondition;
void StdLibraryFunctionsChecker::initFunctionSummaries(
   };
 
   // Functions for testing.
   if (ChecksEnabled[CK_StdCLibraryFunctionsTesterChecker]) {
     llvm::StringMap<Summaries> TestFunctionSummaryMap = {
         {"__two_constrained_args",
          Summaries{
              Summary(ArgTypes{IntTy, IntTy}, RetType{IntTy}, EvalCallAsPure)
                  .ArgConstraint(
                      ArgumentCondition(0U, WithinRange, SingleValue(1)))
                  .ArgConstraint(
                      ArgumentCondition(1U, WithinRange, SingleValue(1)))}},
         {"__arg_constrained_twice",
          Summaries{Summary(ArgTypes{IntTy}, RetType{IntTy}, EvalCallAsPure)
                        .ArgConstraint(
                            ArgumentCondition(0U, OutOfRange, SingleValue(1)))
                        .ArgConstraint(
                            ArgumentCondition(0U, OutOfRange, SingleValue(2)))}},
+        {"__buf_size_arg_constraint",
+         Summaries{Summary(ArgTypes{ConstVoidPtrTy, SizeTy}, RetType{IntTy},
+                           EvalCallAsPure)
+                       .ArgConstraint(BufferSize(0, 1))}},
     };
     for (auto &E : TestFunctionSummaryMap) {
       auto InsertRes =
           FunctionSummaryMap.insert({std::string(E.getKey()), E.getValue()});
       assert(InsertRes.second &&
              "Test functions must not clash with modeled functions");
       (void)InsertRes;
     }

clang/lib/StaticAnalyzer/Core/DynamicSize.cpp

 //===- DynamicSize.cpp - Dynamic size related APIs --------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines APIs that track and query dynamic size information.
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 #include "clang/AST/Expr.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
SVal ElementSizeV = SVB.makeIntVal(
       Ctx.getTypeSizeInChars(ElementTy).getQuantity(), SVB.getArrayIndexType());
 
   SVal DivisionV =
       SVB.evalBinOp(State, BO_Div, Size, ElementSizeV, SVB.getArrayIndexType());
 
   return DivisionV.castAs<DefinedOrUnknownSVal>();
 }
 
+SVal getBufferDynamicSize(const SVal &BufV, ProgramStateRef State,
+                        CheckerContext &C) {
+  const MemRegion *MRegion = BufV.getAsRegion();
+  if (!MRegion)
+    return UnknownVal();
+  RegionOffset Offset = MRegion->getAsOffset();
+  if (Offset.hasSymbolicOffset())
+    return UnknownVal();
+  const MemRegion *BaseRegion = MRegion->getBaseRegion();
+  if (!BaseRegion)
+    return UnknownVal();
+
+  SValBuilder &SvalBuilder = C.getSValBuilder();
+  NonLoc OffsetInBytes = SvalBuilder.makeArrayIndex(
+      Offset.getOffset() / C.getASTContext().getCharWidth());
+  DefinedOrUnknownSVal ExtentInBytes =
+      getDynamicSize(State, BaseRegion, SvalBuilder);
+
+  return SvalBuilder.evalBinOp(State, BinaryOperator::Opcode::BO_Sub,
+                               ExtentInBytes, OffsetInBytes,
+                               SvalBuilder.getArrayIndexType());
+}
+
 } // namespace ento
 } // namespace clang

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

void test_multiple_constraints_on_same_arg(int x) {
   // Check that both constraints are applied and only one branch is there.
   clang_analyzer_eval(x < 1 || x > 2); // \
   // report-warning{{TRUE}} \
   // bugpath-warning{{TRUE}} \
   // bugpath-note{{TRUE}} \
   // bugpath-note{{Assuming 'x' is < 1}} \
   // bugpath-note{{Left side of '||' is true}}
 }
+
+int __buf_size_arg_constraint(const void *, size_t);
+void test_buf_size_concrete() {
+  char buf[3];         // bugpath-note{{'buf' initialized here}}
+  __buf_size_arg_constraint(buf, 4); // \
+  // report-warning{{Function argument constraint is not satisfied}} \
+  // bugpath-warning{{Function argument constraint is not satisfied}} \
+  // bugpath-note{{Function argument constraint is not satisfied}}
+}
+void test_buf_size_symbolic(int s) {
+  char buf[3];
+  __buf_size_arg_constraint(buf, s);
+  clang_analyzer_eval(s <= 3); // \
+  // report-warning{{TRUE}} \
+  // bugpath-warning{{TRUE}} \
+  // bugpath-note{{TRUE}} \
+  // bugpath-note{{'s' is <= 3}}
+}
+void test_buf_size_symbolic_and_offset(int s) {
+  char buf[3];
+  __buf_size_arg_constraint(buf + 1, s);
+  clang_analyzer_eval(s <= 2); // \
+  // report-warning{{TRUE}} \
+  // bugpath-warning{{TRUE}} \
+  // bugpath-note{{TRUE}} \
+  // bugpath-note{{'s' is <= 2}}
+}