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