contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/InnerPointerChecker.cpp

   1 //=== InnerPointerChecker.cpp -------------------------------------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a check that marks a raw pointer to a C++ container's
  11 // inner buffer released when the object is destroyed. This information can
  12 // be used by MallocChecker to detect use-after-free problems.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "AllocationState.h"
  17 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  18 #include "InterCheckerAPI.h"
  19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  20 #include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"
  21 #include "clang/StaticAnalyzer/Core/Checker.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  24
  25 using namespace clang;
  26 using namespace ento;
  27
  28 // Associate container objects with a set of raw pointer symbols.
  29 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(PtrSet, SymbolRef)
  30 REGISTER_MAP_WITH_PROGRAMSTATE(RawPtrMap, const MemRegion *, PtrSet)
  31
  32
  33 namespace {
  34
  35 class InnerPointerChecker
  36     : public Checker<check::DeadSymbols, check::PostCall> {
  37
  38   CallDescription AppendFn, AssignFn, ClearFn, CStrFn, DataFn, EraseFn,
  39       InsertFn, PopBackFn, PushBackFn, ReplaceFn, ReserveFn, ResizeFn,
  40       ShrinkToFitFn, SwapFn;
  41
  42 public:
  43   class InnerPointerBRVisitor : public BugReporterVisitor {
  44     SymbolRef PtrToBuf;
  45
  46   public:
  47     InnerPointerBRVisitor(SymbolRef Sym) : PtrToBuf(Sym) {}
  48
  49     static void *getTag() {
  50       static int Tag = 0;
  51       return &Tag;
  52     }
  53
  54     void Profile(llvm::FoldingSetNodeID &ID) const override {
  55       ID.AddPointer(getTag());
  56     }
  57
  58     virtual std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
  59                                                    BugReporterContext &BRC,
  60                                                    BugReport &BR) override;
  61
  62     // FIXME: Scan the map once in the visitor's constructor and do a direct
  63     // lookup by region.
  64     bool isSymbolTracked(ProgramStateRef State, SymbolRef Sym) {
  65       RawPtrMapTy Map = State->get<RawPtrMap>();
  66       for (const auto Entry : Map) {
  67         if (Entry.second.contains(Sym))
  68           return true;
  69       }
  70       return false;
  71     }
  72   };
  73
  74   InnerPointerChecker()
  75       : AppendFn({"std", "basic_string", "append"}),
  76         AssignFn({"std", "basic_string", "assign"}),
  77         ClearFn({"std", "basic_string", "clear"}),
  78         CStrFn({"std", "basic_string", "c_str"}),
  79         DataFn({"std", "basic_string", "data"}),
  80         EraseFn({"std", "basic_string", "erase"}),
  81         InsertFn({"std", "basic_string", "insert"}),
  82         PopBackFn({"std", "basic_string", "pop_back"}),
  83         PushBackFn({"std", "basic_string", "push_back"}),
  84         ReplaceFn({"std", "basic_string", "replace"}),
  85         ReserveFn({"std", "basic_string", "reserve"}),
  86         ResizeFn({"std", "basic_string", "resize"}),
  87         ShrinkToFitFn({"std", "basic_string", "shrink_to_fit"}),
  88         SwapFn({"std", "basic_string", "swap"}) {}
  89
  90   /// Check whether the called member function potentially invalidates
  91   /// pointers referring to the container object's inner buffer.
  92   bool isInvalidatingMemberFunction(const CallEvent &Call) const;
  93
  94   /// Mark pointer symbols associated with the given memory region released
  95   /// in the program state.
  96   void markPtrSymbolsReleased(const CallEvent &Call, ProgramStateRef State,
  97                               const MemRegion *ObjRegion,
  98                               CheckerContext &C) const;
  99
 100   /// Standard library functions that take a non-const `basic_string` argument by
 101   /// reference may invalidate its inner pointers. Check for these cases and
 102   /// mark the pointers released.
 103   void checkFunctionArguments(const CallEvent &Call, ProgramStateRef State,
 104                               CheckerContext &C) const;
 105
 106   /// Record the connection between raw pointers referring to a container
 107   /// object's inner buffer and the object's memory region in the program state.
 108   /// Mark potentially invalidated pointers released.
 109   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 110
 111   /// Clean up the program state map.
 112   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
 113 };
 114
 115 } // end anonymous namespace
 116
 117 bool InnerPointerChecker::isInvalidatingMemberFunction(
 118         const CallEvent &Call) const {
 119   if (const auto *MemOpCall = dyn_cast<CXXMemberOperatorCall>(&Call)) {
 120     OverloadedOperatorKind Opc = MemOpCall->getOriginExpr()->getOperator();
 121     if (Opc == OO_Equal || Opc == OO_PlusEqual)
 122       return true;
 123     return false;
 124   }
 125   return (isa<CXXDestructorCall>(Call) || Call.isCalled(AppendFn) ||
 126           Call.isCalled(AssignFn) || Call.isCalled(ClearFn) ||
 127           Call.isCalled(EraseFn) || Call.isCalled(InsertFn) ||
 128           Call.isCalled(PopBackFn) || Call.isCalled(PushBackFn) ||
 129           Call.isCalled(ReplaceFn) || Call.isCalled(ReserveFn) ||
 130           Call.isCalled(ResizeFn) || Call.isCalled(ShrinkToFitFn) ||
 131           Call.isCalled(SwapFn));
 132 }
 133
 134 void InnerPointerChecker::markPtrSymbolsReleased(const CallEvent &Call,
 135                                                  ProgramStateRef State,
 136                                                  const MemRegion *MR,
 137                                                  CheckerContext &C) const {
 138   if (const PtrSet *PS = State->get<RawPtrMap>(MR)) {
 139     const Expr *Origin = Call.getOriginExpr();
 140     for (const auto Symbol : *PS) {
 141       // NOTE: `Origin` may be null, and will be stored so in the symbol's
 142       // `RefState` in MallocChecker's `RegionState` program state map.
 143       State = allocation_state::markReleased(State, Symbol, Origin);
 144     }
 145     State = State->remove<RawPtrMap>(MR);
 146     C.addTransition(State);
 147     return;
 148   }
 149 }
 150
 151 void InnerPointerChecker::checkFunctionArguments(const CallEvent &Call,
 152                                                  ProgramStateRef State,
 153                                                  CheckerContext &C) const {
 154   if (const auto *FC = dyn_cast<AnyFunctionCall>(&Call)) {
 155     const FunctionDecl *FD = FC->getDecl();
 156     if (!FD || !FD->isInStdNamespace())
 157       return;
 158
 159     for (unsigned I = 0, E = FD->getNumParams(); I != E; ++I) {
 160       QualType ParamTy = FD->getParamDecl(I)->getType();
 161       if (!ParamTy->isReferenceType() ||
 162           ParamTy->getPointeeType().isConstQualified())
 163         continue;
 164
 165       // In case of member operator calls, `this` is counted as an
 166       // argument but not as a parameter.
 167       bool isaMemberOpCall = isa<CXXMemberOperatorCall>(FC);
 168       unsigned ArgI = isaMemberOpCall ? I+1 : I;
 169
 170       SVal Arg = FC->getArgSVal(ArgI);
 171       const auto *ArgRegion =
 172           dyn_cast_or_null<TypedValueRegion>(Arg.getAsRegion());
 173       if (!ArgRegion)
 174         continue;
 175
 176       markPtrSymbolsReleased(Call, State, ArgRegion, C);
 177     }
 178   }
 179 }
 180
 181 // [string.require]
 182 //
 183 // "References, pointers, and iterators referring to the elements of a
 184 // basic_string sequence may be invalidated by the following uses of that
 185 // basic_string object:
 186 //
 187 // -- As an argument to any standard library function taking a reference
 188 // to non-const basic_string as an argument. For example, as an argument to
 189 // non-member functions swap(), operator>>(), and getline(), or as an argument
 190 // to basic_string::swap().
 191 //
 192 // -- Calling non-const member functions, except operator[], at, front, back,
 193 // begin, rbegin, end, and rend."
 194
 195 void InnerPointerChecker::checkPostCall(const CallEvent &Call,
 196                                         CheckerContext &C) const {
 197   ProgramStateRef State = C.getState();
 198
 199   if (const auto *ICall = dyn_cast<CXXInstanceCall>(&Call)) {
 200     // TODO: Do we need these to be typed?
 201     const auto *ObjRegion = dyn_cast_or_null<TypedValueRegion>(
 202         ICall->getCXXThisVal().getAsRegion());
 203     if (!ObjRegion)
 204       return;
 205
 206     if (Call.isCalled(CStrFn) || Call.isCalled(DataFn)) {
 207       SVal RawPtr = Call.getReturnValue();
 208       if (SymbolRef Sym = RawPtr.getAsSymbol(/*IncludeBaseRegions=*/true)) {
 209         // Start tracking this raw pointer by adding it to the set of symbols
 210         // associated with this container object in the program state map.
 211
 212         PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
 213         const PtrSet *SetPtr = State->get<RawPtrMap>(ObjRegion);
 214         PtrSet Set = SetPtr ? *SetPtr : F.getEmptySet();
 215         assert(C.wasInlined || !Set.contains(Sym));
 216         Set = F.add(Set, Sym);
 217
 218         State = State->set<RawPtrMap>(ObjRegion, Set);
 219         C.addTransition(State);
 220       }
 221       return;
 222     }
 223
 224     // Check [string.require] / second point.
 225     if (isInvalidatingMemberFunction(Call)) {
 226       markPtrSymbolsReleased(Call, State, ObjRegion, C);
 227       return;
 228     }
 229   }
 230
 231   // Check [string.require] / first point.
 232   checkFunctionArguments(Call, State, C);
 233 }
 234
 235 void InnerPointerChecker::checkDeadSymbols(SymbolReaper &SymReaper,
 236                                            CheckerContext &C) const {
 237   ProgramStateRef State = C.getState();
 238   PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
 239   RawPtrMapTy RPM = State->get<RawPtrMap>();
 240   for (const auto Entry : RPM) {
 241     if (!SymReaper.isLiveRegion(Entry.first)) {
 242       // Due to incomplete destructor support, some dead regions might
 243       // remain in the program state map. Clean them up.
 244       State = State->remove<RawPtrMap>(Entry.first);
 245     }
 246     if (const PtrSet *OldSet = State->get<RawPtrMap>(Entry.first)) {
 247       PtrSet CleanedUpSet = *OldSet;
 248       for (const auto Symbol : Entry.second) {
 249         if (!SymReaper.isLive(Symbol))
 250           CleanedUpSet = F.remove(CleanedUpSet, Symbol);
 251       }
 252       State = CleanedUpSet.isEmpty()
 253                   ? State->remove<RawPtrMap>(Entry.first)
 254                   : State->set<RawPtrMap>(Entry.first, CleanedUpSet);
 255     }
 256   }
 257   C.addTransition(State);
 258 }
 259
 260 namespace clang {
 261 namespace ento {
 262 namespace allocation_state {
 263
 264 std::unique_ptr<BugReporterVisitor> getInnerPointerBRVisitor(SymbolRef Sym) {
 265   return llvm::make_unique<InnerPointerChecker::InnerPointerBRVisitor>(Sym);
 266 }
 267
 268 const MemRegion *getContainerObjRegion(ProgramStateRef State, SymbolRef Sym) {
 269   RawPtrMapTy Map = State->get<RawPtrMap>();
 270   for (const auto Entry : Map) {
 271     if (Entry.second.contains(Sym)) {
 272       return Entry.first;
 273     }
 274   }
 275   return nullptr;
 276 }
 277
 278 } // end namespace allocation_state
 279 } // end namespace ento
 280 } // end namespace clang
 281
 282 std::shared_ptr<PathDiagnosticPiece>
 283 InnerPointerChecker::InnerPointerBRVisitor::VisitNode(const ExplodedNode *N,
 284                                                       BugReporterContext &BRC,
 285                                                       BugReport &) {
 286   if (!isSymbolTracked(N->getState(), PtrToBuf) ||
 287       isSymbolTracked(N->getFirstPred()->getState(), PtrToBuf))
 288     return nullptr;
 289
 290   const Stmt *S = PathDiagnosticLocation::getStmt(N);
 291   if (!S)
 292     return nullptr;
 293
 294   const MemRegion *ObjRegion =
 295       allocation_state::getContainerObjRegion(N->getState(), PtrToBuf);
 296   const auto *TypedRegion = cast<TypedValueRegion>(ObjRegion);
 297   QualType ObjTy = TypedRegion->getValueType();
 298
 299   SmallString<256> Buf;
 300   llvm::raw_svector_ostream OS(Buf);
 301   OS << "Pointer to inner buffer of '" << ObjTy.getAsString()
 302      << "' obtained here";
 303   PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
 304                              N->getLocationContext());
 305   return std::make_shared<PathDiagnosticEventPiece>(Pos, OS.str(), true,
 306                                                     nullptr);
 307 }
 308
 309 void ento::registerInnerPointerChecker(CheckerManager &Mgr) {
 310   registerInnerPointerCheckerAux(Mgr);
 311   Mgr.registerChecker<InnerPointerChecker>();
 312 }