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