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