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