1//=== PointerArithChecker.cpp - Pointer arithmetic checker -----*- 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 files defines PointerArithChecker, a builtin checker that checks for
10// pointer arithmetic on locations other than array elements.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
15#include "clang/AST/DeclCXX.h"
16#include "clang/AST/ExprCXX.h"
17#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
18#include "clang/StaticAnalyzer/Core/Checker.h"
19#include "clang/StaticAnalyzer/Core/CheckerManager.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
21
22using namespace clang;
23using namespace ento;
24
25namespace {
26enum class AllocKind {
27  SingleObject,
28  Array,
29  Unknown,
30  Reinterpreted // Single object interpreted as an array.
31};
32} // end namespace
33
34namespace llvm {
35template <> struct FoldingSetTrait<AllocKind> {
36  static inline void Profile(AllocKind X, FoldingSetNodeID &ID) {
37    ID.AddInteger(static_cast<int>(X));
38  }
39};
40} // end namespace llvm
41
42namespace {
43class PointerArithChecker
44    : public Checker<
45          check::PreStmt<BinaryOperator>, check::PreStmt<UnaryOperator>,
46          check::PreStmt<ArraySubscriptExpr>, check::PreStmt<CastExpr>,
47          check::PostStmt<CastExpr>, check::PostStmt<CXXNewExpr>,
48          check::PostStmt<CallExpr>, check::DeadSymbols> {
49  AllocKind getKindOfNewOp(const CXXNewExpr *NE, const FunctionDecl *FD) const;
50  const MemRegion *getArrayRegion(const MemRegion *Region, bool &Polymorphic,
51                                  AllocKind &AKind, CheckerContext &C) const;
52  const MemRegion *getPointedRegion(const MemRegion *Region,
53                                    CheckerContext &C) const;
54  void reportPointerArithMisuse(const Expr *E, CheckerContext &C,
55                                bool PointedNeeded = false) const;
56  void initAllocIdentifiers(ASTContext &C) const;
57
58  mutable std::unique_ptr<BuiltinBug> BT_pointerArith;
59  mutable std::unique_ptr<BuiltinBug> BT_polyArray;
60  mutable llvm::SmallSet<IdentifierInfo *, 8> AllocFunctions;
61
62public:
63  void checkPreStmt(const UnaryOperator *UOp, CheckerContext &C) const;
64  void checkPreStmt(const BinaryOperator *BOp, CheckerContext &C) const;
65  void checkPreStmt(const ArraySubscriptExpr *SubExpr, CheckerContext &C) const;
66  void checkPreStmt(const CastExpr *CE, CheckerContext &C) const;
67  void checkPostStmt(const CastExpr *CE, CheckerContext &C) const;
68  void checkPostStmt(const CXXNewExpr *NE, CheckerContext &C) const;
69  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
70  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
71};
72} // end namespace
73
74REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, const MemRegion *, AllocKind)
75
76void PointerArithChecker::checkDeadSymbols(SymbolReaper &SR,
77                                           CheckerContext &C) const {
78  // TODO: intentional leak. Some information is garbage collected too early,
79  // see http://reviews.llvm.org/D14203 for further information.
80  /*ProgramStateRef State = C.getState();
81  RegionStateTy RegionStates = State->get<RegionState>();
82  for (RegionStateTy::iterator I = RegionStates.begin(), E = RegionStates.end();
83       I != E; ++I) {
84    if (!SR.isLiveRegion(I->first))
85      State = State->remove<RegionState>(I->first);
86  }
87  C.addTransition(State);*/
88}
89
90AllocKind PointerArithChecker::getKindOfNewOp(const CXXNewExpr *NE,
91                                              const FunctionDecl *FD) const {
92  // This checker try not to assume anything about placement and overloaded
93  // new to avoid false positives.
94  if (isa<CXXMethodDecl>(FD))
95    return AllocKind::Unknown;
96  if (FD->getNumParams() != 1 || FD->isVariadic())
97    return AllocKind::Unknown;
98  if (NE->isArray())
99    return AllocKind::Array;
100
101  return AllocKind::SingleObject;
102}
103
104const MemRegion *
105PointerArithChecker::getPointedRegion(const MemRegion *Region,
106                                      CheckerContext &C) const {
107  assert(Region);
108  ProgramStateRef State = C.getState();
109  SVal S = State->getSVal(Region);
110  return S.getAsRegion();
111}
112
113/// Checks whether a region is the part of an array.
114/// In case there is a derived to base cast above the array element, the
115/// Polymorphic output value is set to true. AKind output value is set to the
116/// allocation kind of the inspected region.
117const MemRegion *PointerArithChecker::getArrayRegion(const MemRegion *Region,
118                                                     bool &Polymorphic,
119                                                     AllocKind &AKind,
120                                                     CheckerContext &C) const {
121  assert(Region);
122  while (const auto *BaseRegion = dyn_cast<CXXBaseObjectRegion>(Region)) {
123    Region = BaseRegion->getSuperRegion();
124    Polymorphic = true;
125  }
126  if (const auto *ElemRegion = dyn_cast<ElementRegion>(Region)) {
127    Region = ElemRegion->getSuperRegion();
128  }
129
130  ProgramStateRef State = C.getState();
131  if (const AllocKind *Kind = State->get<RegionState>(Region)) {
132    AKind = *Kind;
133    if (*Kind == AllocKind::Array)
134      return Region;
135    else
136      return nullptr;
137  }
138  // When the region is symbolic and we do not have any information about it,
139  // assume that this is an array to avoid false positives.
140  if (isa<SymbolicRegion>(Region))
141    return Region;
142
143  // No AllocKind stored and not symbolic, assume that it points to a single
144  // object.
145  return nullptr;
146}
147
148void PointerArithChecker::reportPointerArithMisuse(const Expr *E,
149                                                   CheckerContext &C,
150                                                   bool PointedNeeded) const {
151  SourceRange SR = E->getSourceRange();
152  if (SR.isInvalid())
153    return;
154
155  ProgramStateRef State = C.getState();
156  const MemRegion *Region = C.getSVal(E).getAsRegion();
157  if (!Region)
158    return;
159  if (PointedNeeded)
160    Region = getPointedRegion(Region, C);
161  if (!Region)
162    return;
163
164  bool IsPolymorphic = false;
165  AllocKind Kind = AllocKind::Unknown;
166  if (const MemRegion *ArrayRegion =
167          getArrayRegion(Region, IsPolymorphic, Kind, C)) {
168    if (!IsPolymorphic)
169      return;
170    if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
171      if (!BT_polyArray)
172        BT_polyArray.reset(new BuiltinBug(
173            this, "Dangerous pointer arithmetic",
174            "Pointer arithmetic on a pointer to base class is dangerous "
175            "because derived and base class may have different size."));
176      auto R = std::make_unique<PathSensitiveBugReport>(
177          *BT_polyArray, BT_polyArray->getDescription(), N);
178      R->addRange(E->getSourceRange());
179      R->markInteresting(ArrayRegion);
180      C.emitReport(std::move(R));
181    }
182    return;
183  }
184
185  if (Kind == AllocKind::Reinterpreted)
186    return;
187
188  // We might not have enough information about symbolic regions.
189  if (Kind != AllocKind::SingleObject &&
190      Region->getKind() == MemRegion::Kind::SymbolicRegionKind)
191    return;
192
193  if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
194    if (!BT_pointerArith)
195      BT_pointerArith.reset(new BuiltinBug(this, "Dangerous pointer arithmetic",
196                                           "Pointer arithmetic on non-array "
197                                           "variables relies on memory layout, "
198                                           "which is dangerous."));
199    auto R = std::make_unique<PathSensitiveBugReport>(
200        *BT_pointerArith, BT_pointerArith->getDescription(), N);
201    R->addRange(SR);
202    R->markInteresting(Region);
203    C.emitReport(std::move(R));
204  }
205}
206
207void PointerArithChecker::initAllocIdentifiers(ASTContext &C) const {
208  if (!AllocFunctions.empty())
209    return;
210  AllocFunctions.insert(&C.Idents.get("alloca"));
211  AllocFunctions.insert(&C.Idents.get("malloc"));
212  AllocFunctions.insert(&C.Idents.get("realloc"));
213  AllocFunctions.insert(&C.Idents.get("calloc"));
214  AllocFunctions.insert(&C.Idents.get("valloc"));
215}
216
217void PointerArithChecker::checkPostStmt(const CallExpr *CE,
218                                        CheckerContext &C) const {
219  ProgramStateRef State = C.getState();
220  const FunctionDecl *FD = C.getCalleeDecl(CE);
221  if (!FD)
222    return;
223  IdentifierInfo *FunI = FD->getIdentifier();
224  initAllocIdentifiers(C.getASTContext());
225  if (AllocFunctions.count(FunI) == 0)
226    return;
227
228  SVal SV = C.getSVal(CE);
229  const MemRegion *Region = SV.getAsRegion();
230  if (!Region)
231    return;
232  // Assume that C allocation functions allocate arrays to avoid false
233  // positives.
234  // TODO: Add heuristics to distinguish alloc calls that allocates single
235  // objecs.
236  State = State->set<RegionState>(Region, AllocKind::Array);
237  C.addTransition(State);
238}
239
240void PointerArithChecker::checkPostStmt(const CXXNewExpr *NE,
241                                        CheckerContext &C) const {
242  const FunctionDecl *FD = NE->getOperatorNew();
243  if (!FD)
244    return;
245
246  AllocKind Kind = getKindOfNewOp(NE, FD);
247
248  ProgramStateRef State = C.getState();
249  SVal AllocedVal = C.getSVal(NE);
250  const MemRegion *Region = AllocedVal.getAsRegion();
251  if (!Region)
252    return;
253  State = State->set<RegionState>(Region, Kind);
254  C.addTransition(State);
255}
256
257void PointerArithChecker::checkPostStmt(const CastExpr *CE,
258                                        CheckerContext &C) const {
259  if (CE->getCastKind() != CastKind::CK_BitCast)
260    return;
261
262  const Expr *CastedExpr = CE->getSubExpr();
263  ProgramStateRef State = C.getState();
264  SVal CastedVal = C.getSVal(CastedExpr);
265
266  const MemRegion *Region = CastedVal.getAsRegion();
267  if (!Region)
268    return;
269
270  // Suppress reinterpret casted hits.
271  State = State->set<RegionState>(Region, AllocKind::Reinterpreted);
272  C.addTransition(State);
273}
274
275void PointerArithChecker::checkPreStmt(const CastExpr *CE,
276                                       CheckerContext &C) const {
277  if (CE->getCastKind() != CastKind::CK_ArrayToPointerDecay)
278    return;
279
280  const Expr *CastedExpr = CE->getSubExpr();
281  ProgramStateRef State = C.getState();
282  SVal CastedVal = C.getSVal(CastedExpr);
283
284  const MemRegion *Region = CastedVal.getAsRegion();
285  if (!Region)
286    return;
287
288  if (const AllocKind *Kind = State->get<RegionState>(Region)) {
289    if (*Kind == AllocKind::Array || *Kind == AllocKind::Reinterpreted)
290      return;
291  }
292  State = State->set<RegionState>(Region, AllocKind::Array);
293  C.addTransition(State);
294}
295
296void PointerArithChecker::checkPreStmt(const UnaryOperator *UOp,
297                                       CheckerContext &C) const {
298  if (!UOp->isIncrementDecrementOp() || !UOp->getType()->isPointerType())
299    return;
300  reportPointerArithMisuse(UOp->getSubExpr(), C, true);
301}
302
303void PointerArithChecker::checkPreStmt(const ArraySubscriptExpr *SubsExpr,
304                                       CheckerContext &C) const {
305  SVal Idx = C.getSVal(SubsExpr->getIdx());
306
307  // Indexing with 0 is OK.
308  if (Idx.isZeroConstant())
309    return;
310
311  // Indexing vector-type expressions is also OK.
312  if (SubsExpr->getBase()->getType()->isVectorType())
313    return;
314  reportPointerArithMisuse(SubsExpr->getBase(), C);
315}
316
317void PointerArithChecker::checkPreStmt(const BinaryOperator *BOp,
318                                       CheckerContext &C) const {
319  BinaryOperatorKind OpKind = BOp->getOpcode();
320  if (!BOp->isAdditiveOp() && OpKind != BO_AddAssign && OpKind != BO_SubAssign)
321    return;
322
323  const Expr *Lhs = BOp->getLHS();
324  const Expr *Rhs = BOp->getRHS();
325  ProgramStateRef State = C.getState();
326
327  if (Rhs->getType()->isIntegerType() && Lhs->getType()->isPointerType()) {
328    SVal RHSVal = C.getSVal(Rhs);
329    if (State->isNull(RHSVal).isConstrainedTrue())
330      return;
331    reportPointerArithMisuse(Lhs, C, !BOp->isAdditiveOp());
332  }
333  // The int += ptr; case is not valid C++.
334  if (Lhs->getType()->isIntegerType() && Rhs->getType()->isPointerType()) {
335    SVal LHSVal = C.getSVal(Lhs);
336    if (State->isNull(LHSVal).isConstrainedTrue())
337      return;
338    reportPointerArithMisuse(Rhs, C);
339  }
340}
341
342void ento::registerPointerArithChecker(CheckerManager &mgr) {
343  mgr.registerChecker<PointerArithChecker>();
344}
345
346bool ento::shouldRegisterPointerArithChecker(const LangOptions &LO) {
347  return true;
348}
349