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 whether the function called on the container object is a
  95   /// member function that potentially invalidates pointers referring
  96   /// to the objects's internal buffer.
  97   bool mayInvalidateBuffer(const CallEvent &Call) const;
  98
  99   /// Record the connection between the symbol returned by c_str() and the
 100   /// corresponding string object region in the ProgramState. Mark the symbol
 101   /// released if the string object is destroyed.
 102   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 103
 104   /// Clean up the ProgramState map.
 105   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
 106 };
 107
 108 } // end anonymous namespace
 109
 110 // [string.require]
 111 //
 112 // "References, pointers, and iterators referring to the elements of a
 113 // basic_string sequence may be invalidated by the following uses of that
 114 // basic_string object:
 115 //
 116 // -- TODO: As an argument to any standard library function taking a reference
 117 // to non-const basic_string as an argument. For example, as an argument to
 118 // non-member functions swap(), operator>>(), and getline(), or as an argument
 119 // to basic_string::swap().
 120 //
 121 // -- Calling non-const member functions, except operator[], at, front, back,
 122 // begin, rbegin, end, and rend."
 123 //
 124 bool InnerPointerChecker::mayInvalidateBuffer(const CallEvent &Call) const {
 125   if (const auto *MemOpCall = dyn_cast<CXXMemberOperatorCall>(&Call)) {
 126     OverloadedOperatorKind Opc = MemOpCall->getOriginExpr()->getOperator();
 127     if (Opc == OO_Equal || Opc == OO_PlusEqual)
 128       return true;
 129     return false;
 130   }
 131   return (isa<CXXDestructorCall>(Call) || Call.isCalled(AppendFn) ||
 132           Call.isCalled(AssignFn) || Call.isCalled(ClearFn) ||
 133           Call.isCalled(EraseFn) || Call.isCalled(InsertFn) ||
 134           Call.isCalled(PopBackFn) || Call.isCalled(PushBackFn) ||
 135           Call.isCalled(ReplaceFn) || Call.isCalled(ReserveFn) ||
 136           Call.isCalled(ResizeFn) || Call.isCalled(ShrinkToFitFn) ||
 137           Call.isCalled(SwapFn));
 138 }
 139
 140 void InnerPointerChecker::checkPostCall(const CallEvent &Call,
 141                                         CheckerContext &C) const {
 142   const auto *ICall = dyn_cast<CXXInstanceCall>(&Call);
 143   if (!ICall)
 144     return;
 145
 146   SVal Obj = ICall->getCXXThisVal();
 147   const auto *ObjRegion = dyn_cast_or_null<TypedValueRegion>(Obj.getAsRegion());
 148   if (!ObjRegion)
 149     return;
 150
 151   auto *TypeDecl = ObjRegion->getValueType()->getAsCXXRecordDecl();
 152   if (TypeDecl->getName() != "basic_string")
 153     return;
 154
 155   ProgramStateRef State = C.getState();
 156
 157   if (Call.isCalled(CStrFn) || Call.isCalled(DataFn)) {
 158     SVal RawPtr = Call.getReturnValue();
 159     if (SymbolRef Sym = RawPtr.getAsSymbol(/*IncludeBaseRegions=*/true)) {
 160       // Start tracking this raw pointer by adding it to the set of symbols
 161       // associated with this container object in the program state map.
 162       PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
 163       const PtrSet *SetPtr = State->get<RawPtrMap>(ObjRegion);
 164       PtrSet Set = SetPtr ? *SetPtr : F.getEmptySet();
 165       assert(C.wasInlined || !Set.contains(Sym));
 166       Set = F.add(Set, Sym);
 167       State = State->set<RawPtrMap>(ObjRegion, Set);
 168       C.addTransition(State);
 169     }
 170     return;
 171   }
 172
 173   if (mayInvalidateBuffer(Call)) {
 174     if (const PtrSet *PS = State->get<RawPtrMap>(ObjRegion)) {
 175       // Mark all pointer symbols associated with the deleted object released.
 176       const Expr *Origin = Call.getOriginExpr();
 177       for (const auto Symbol : *PS) {
 178         // NOTE: `Origin` may be null, and will be stored so in the symbol's
 179         // `RefState` in MallocChecker's `RegionState` program state map.
 180         State = allocation_state::markReleased(State, Symbol, Origin);
 181       }
 182       State = State->remove<RawPtrMap>(ObjRegion);
 183       C.addTransition(State);
 184       return;
 185     }
 186   }
 187 }
 188
 189 void InnerPointerChecker::checkDeadSymbols(SymbolReaper &SymReaper,
 190                                            CheckerContext &C) const {
 191   ProgramStateRef State = C.getState();
 192   PtrSet::Factory &F = State->getStateManager().get_context<PtrSet>();
 193   RawPtrMapTy RPM = State->get<RawPtrMap>();
 194   for (const auto Entry : RPM) {
 195     if (!SymReaper.isLiveRegion(Entry.first)) {
 196       // Due to incomplete destructor support, some dead regions might
 197       // remain in the program state map. Clean them up.
 198       State = State->remove<RawPtrMap>(Entry.first);
 199     }
 200     if (const PtrSet *OldSet = State->get<RawPtrMap>(Entry.first)) {
 201       PtrSet CleanedUpSet = *OldSet;
 202       for (const auto Symbol : Entry.second) {
 203         if (!SymReaper.isLive(Symbol))
 204           CleanedUpSet = F.remove(CleanedUpSet, Symbol);
 205       }
 206       State = CleanedUpSet.isEmpty()
 207                   ? State->remove<RawPtrMap>(Entry.first)
 208                   : State->set<RawPtrMap>(Entry.first, CleanedUpSet);
 209     }
 210   }
 211   C.addTransition(State);
 212 }
 213
 214 std::shared_ptr<PathDiagnosticPiece>
 215 InnerPointerChecker::InnerPointerBRVisitor::VisitNode(const ExplodedNode *N,
 216                                                       const ExplodedNode *PrevN,
 217                                                       BugReporterContext &BRC,
 218                                                       BugReport &BR) {
 219
 220   if (!isSymbolTracked(N->getState(), PtrToBuf) ||
 221       isSymbolTracked(PrevN->getState(), PtrToBuf))
 222     return nullptr;
 223
 224   const Stmt *S = PathDiagnosticLocation::getStmt(N);
 225   if (!S)
 226     return nullptr;
 227
 228   SmallString<256> Buf;
 229   llvm::raw_svector_ostream OS(Buf);
 230   OS << "Dangling inner pointer obtained here";
 231   PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
 232                              N->getLocationContext());
 233   return std::make_shared<PathDiagnosticEventPiece>(Pos, OS.str(), true,
 234                                                     nullptr);
 235 }
 236
 237 namespace clang {
 238 namespace ento {
 239 namespace allocation_state {
 240
 241 std::unique_ptr<BugReporterVisitor> getInnerPointerBRVisitor(SymbolRef Sym) {
 242   return llvm::make_unique<InnerPointerChecker::InnerPointerBRVisitor>(Sym);
 243 }
 244
 245 } // end namespace allocation_state
 246 } // end namespace ento
 247 } // end namespace clang
 248
 249 void ento::registerInnerPointerChecker(CheckerManager &Mgr) {
 250   registerNewDeleteChecker(Mgr);
 251   Mgr.registerChecker<InnerPointerChecker>();
 252 }