1//=== VLASizeChecker.cpp - Undefined dereference 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 defines VLASizeChecker, a builtin check in ExprEngine that
10// performs checks for declaration of VLA of undefined or zero size.
11// In addition, VLASizeChecker is responsible for defining the extent
12// of the MemRegion that represents a VLA.
13//
14//===----------------------------------------------------------------------===//
15
16#include "clang/AST/CharUnits.h"
17#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
18#include "clang/StaticAnalyzer/Checkers/Taint.h"
19#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
20#include "clang/StaticAnalyzer/Core/Checker.h"
21#include "clang/StaticAnalyzer/Core/CheckerManager.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
24#include "llvm/Support/raw_ostream.h"
25#include <optional>
26
27using namespace clang;
28using namespace ento;
29using namespace taint;
30
31namespace {
32class VLASizeChecker
33 : public Checker<check::PreStmt<DeclStmt>,
34 check::PreStmt<UnaryExprOrTypeTraitExpr>> {
35 const BugType BT{this, "Dangerous variable-length array (VLA) declaration"};
36 const BugType TaintBT{this,
37 "Dangerous variable-length array (VLA) declaration",
38 categories::TaintedData};
39 enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Negative, VLA_Overflow };
40
41 /// Check a VLA for validity.
42 /// Every dimension of the array and the total size is checked for validity.
43 /// Returns null or a new state where the size is validated.
44 /// 'ArraySize' will contain SVal that refers to the total size (in char)
45 /// of the array.
46 ProgramStateRef checkVLA(CheckerContext &C, ProgramStateRef State,
47 const VariableArrayType *VLA, SVal &ArraySize) const;
48 /// Check a single VLA index size expression for validity.
49 ProgramStateRef checkVLAIndexSize(CheckerContext &C, ProgramStateRef State,
50 const Expr *SizeE) const;
51
52 void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
53 CheckerContext &C) const;
54
55 void reportTaintBug(const Expr *SizeE, ProgramStateRef State,
56 CheckerContext &C, SVal TaintedSVal) const;
57
58public:
59 void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
60 void checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
61 CheckerContext &C) const;
62};
63} // end anonymous namespace
64
65ProgramStateRef VLASizeChecker::checkVLA(CheckerContext &C,
66 ProgramStateRef State,
67 const VariableArrayType *VLA,
68 SVal &ArraySize) const {
69 assert(VLA && "Function should be called with non-null VLA argument.");
70
71 const VariableArrayType *VLALast = nullptr;
72 llvm::SmallVector<const Expr *, 2> VLASizes;
73
74 // Walk over the VLAs for every dimension until a non-VLA is found.
75 // There is a VariableArrayType for every dimension (fixed or variable) until
76 // the most inner array that is variably modified.
77 // Dimension sizes are collected into 'VLASizes'. 'VLALast' is set to the
78 // innermost VLA that was encountered.
79 // In "int vla[x][2][y][3]" this will be the array for index "y" (with type
80 // int[3]). 'VLASizes' contains 'x', '2', and 'y'.
81 while (VLA) {
82 const Expr *SizeE = VLA->getSizeExpr();
83 State = checkVLAIndexSize(C, State, SizeE);
84 if (!State)
85 return nullptr;
86 VLASizes.push_back(Elt: SizeE);
87 VLALast = VLA;
88 VLA = C.getASTContext().getAsVariableArrayType(T: VLA->getElementType());
89 };
90 assert(VLALast &&
91 "Array should have at least one variably-modified dimension.");
92
93 ASTContext &Ctx = C.getASTContext();
94 SValBuilder &SVB = C.getSValBuilder();
95 CanQualType SizeTy = Ctx.getSizeType();
96 uint64_t SizeMax =
97 SVB.getBasicValueFactory().getMaxValue(T: SizeTy)->getZExtValue();
98
99 // Get the element size.
100 CharUnits EleSize = Ctx.getTypeSizeInChars(T: VLALast->getElementType());
101 NonLoc ArrSize =
102 SVB.makeIntVal(integer: EleSize.getQuantity(), type: SizeTy).castAs<NonLoc>();
103
104 // Try to calculate the known real size of the array in KnownSize.
105 uint64_t KnownSize = 0;
106 if (const llvm::APSInt *KV = SVB.getKnownValue(state: State, val: ArrSize))
107 KnownSize = KV->getZExtValue();
108
109 for (const Expr *SizeE : VLASizes) {
110 auto SizeD = C.getSVal(S: SizeE).castAs<DefinedSVal>();
111 // Convert the array length to size_t.
112 NonLoc IndexLength =
113 SVB.evalCast(V: SizeD, CastTy: SizeTy, OriginalTy: SizeE->getType()).castAs<NonLoc>();
114 // Multiply the array length by the element size.
115 SVal Mul = SVB.evalBinOpNN(state: State, op: BO_Mul, lhs: ArrSize, rhs: IndexLength, resultTy: SizeTy);
116 if (auto MulNonLoc = Mul.getAs<NonLoc>())
117 ArrSize = *MulNonLoc;
118 else
119 // Extent could not be determined.
120 return State;
121
122 if (const llvm::APSInt *IndexLVal = SVB.getKnownValue(state: State, val: IndexLength)) {
123 // Check if the array size will overflow.
124 // Size overflow check does not work with symbolic expressions because a
125 // overflow situation can not be detected easily.
126 uint64_t IndexL = IndexLVal->getZExtValue();
127 // FIXME: See https://reviews.llvm.org/D80903 for discussion of
128 // some difference in assume and getKnownValue that leads to
129 // unexpected behavior. Just bail on IndexL == 0 at this point.
130 if (IndexL == 0)
131 return nullptr;
132
133 if (KnownSize <= SizeMax / IndexL) {
134 KnownSize *= IndexL;
135 } else {
136 // Array size does not fit into size_t.
137 reportBug(Kind: VLA_Overflow, SizeE, State, C);
138 return nullptr;
139 }
140 } else {
141 KnownSize = 0;
142 }
143 }
144
145 ArraySize = ArrSize;
146
147 return State;
148}
149
150ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C,
151 ProgramStateRef State,
152 const Expr *SizeE) const {
153 SVal SizeV = C.getSVal(S: SizeE);
154
155 if (SizeV.isUndef()) {
156 reportBug(Kind: VLA_Garbage, SizeE, State, C);
157 return nullptr;
158 }
159
160 // See if the size value is known. It can't be undefined because we would have
161 // warned about that already.
162 if (SizeV.isUnknown())
163 return nullptr;
164
165 // Check if the size is zero.
166 DefinedSVal SizeD = SizeV.castAs<DefinedSVal>();
167
168 ProgramStateRef StateNotZero, StateZero;
169 std::tie(args&: StateNotZero, args&: StateZero) = State->assume(Cond: SizeD);
170
171 if (StateZero && !StateNotZero) {
172 reportBug(Kind: VLA_Zero, SizeE, State: StateZero, C);
173 return nullptr;
174 }
175
176 // From this point on, assume that the size is not zero.
177 State = StateNotZero;
178
179 // Check if the size is negative.
180 SValBuilder &SVB = C.getSValBuilder();
181
182 QualType SizeTy = SizeE->getType();
183 DefinedOrUnknownSVal Zero = SVB.makeZeroVal(type: SizeTy);
184
185 SVal LessThanZeroVal =
186 SVB.evalBinOp(state: State, op: BO_LT, lhs: SizeD, rhs: Zero, type: SVB.getConditionType());
187 ProgramStateRef StatePos, StateNeg;
188 if (std::optional<DefinedSVal> LessThanZeroDVal =
189 LessThanZeroVal.getAs<DefinedSVal>()) {
190 ConstraintManager &CM = C.getConstraintManager();
191
192 std::tie(args&: StateNeg, args&: StatePos) = CM.assumeDual(State, Cond: *LessThanZeroDVal);
193 if (StateNeg && !StatePos) {
194 reportBug(Kind: VLA_Negative, SizeE, State, C);
195 return nullptr;
196 }
197 State = StatePos;
198 }
199
200 // Check if the size is tainted.
201 if ((StateNeg || StateZero) && isTainted(State, V: SizeV)) {
202 reportTaintBug(SizeE, State, C, TaintedSVal: SizeV);
203 return nullptr;
204 }
205
206 return State;
207}
208
209void VLASizeChecker::reportTaintBug(const Expr *SizeE, ProgramStateRef State,
210 CheckerContext &C, SVal TaintedSVal) const {
211 // Generate an error node.
212 ExplodedNode *N = C.generateErrorNode(State);
213 if (!N)
214 return;
215
216 SmallString<256> buf;
217 llvm::raw_svector_ostream os(buf);
218 os << "Declared variable-length array (VLA) ";
219 os << "has tainted (attacker controlled) size that can be 0 or negative";
220
221 auto report = std::make_unique<PathSensitiveBugReport>(args: TaintBT, args: os.str(), args&: N);
222 report->addRange(R: SizeE->getSourceRange());
223 bugreporter::trackExpressionValue(N, E: SizeE, R&: *report);
224 // The vla size may be a complex expression where multiple memory locations
225 // are tainted.
226 for (auto Sym : getTaintedSymbols(State, V: TaintedSVal))
227 report->markInteresting(sym: Sym);
228 C.emitReport(R: std::move(report));
229}
230
231void VLASizeChecker::reportBug(VLASize_Kind Kind, const Expr *SizeE,
232 ProgramStateRef State, CheckerContext &C) const {
233 // Generate an error node.
234 ExplodedNode *N = C.generateErrorNode(State);
235 if (!N)
236 return;
237
238 SmallString<256> buf;
239 llvm::raw_svector_ostream os(buf);
240 os << "Declared variable-length array (VLA) ";
241 switch (Kind) {
242 case VLA_Garbage:
243 os << "uses a garbage value as its size";
244 break;
245 case VLA_Zero:
246 os << "has zero size";
247 break;
248 case VLA_Negative:
249 os << "has negative size";
250 break;
251 case VLA_Overflow:
252 os << "has too large size";
253 break;
254 }
255
256 auto report = std::make_unique<PathSensitiveBugReport>(args: BT, args: os.str(), args&: N);
257 report->addRange(R: SizeE->getSourceRange());
258 bugreporter::trackExpressionValue(N, E: SizeE, R&: *report);
259 C.emitReport(R: std::move(report));
260}
261
262void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
263 if (!DS->isSingleDecl())
264 return;
265
266 ASTContext &Ctx = C.getASTContext();
267 ProgramStateRef State = C.getState();
268 QualType TypeToCheck;
269
270 const VarDecl *VD = dyn_cast<VarDecl>(Val: DS->getSingleDecl());
271
272 if (VD)
273 TypeToCheck = VD->getType().getCanonicalType();
274 else if (const auto *TND = dyn_cast<TypedefNameDecl>(Val: DS->getSingleDecl()))
275 TypeToCheck = TND->getUnderlyingType().getCanonicalType();
276 else
277 return;
278
279 const VariableArrayType *VLA = Ctx.getAsVariableArrayType(T: TypeToCheck);
280 if (!VLA)
281 return;
282
283 // Check the VLA sizes for validity.
284
285 SVal ArraySize;
286
287 State = checkVLA(C, State, VLA, ArraySize);
288 if (!State)
289 return;
290
291 if (!isa<NonLoc>(Val: ArraySize)) {
292 // Array size could not be determined but state may contain new assumptions.
293 C.addTransition(State);
294 return;
295 }
296
297 // VLASizeChecker is responsible for defining the extent of the array.
298 if (VD) {
299 State =
300 setDynamicExtent(State, MR: State->getRegion(D: VD, LC: C.getLocationContext()),
301 Extent: ArraySize.castAs<NonLoc>());
302 }
303
304 // Remember our assumptions!
305 C.addTransition(State);
306}
307
308void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
309 CheckerContext &C) const {
310 // Want to check for sizeof.
311 if (UETTE->getKind() != UETT_SizeOf)
312 return;
313
314 // Ensure a type argument.
315 if (!UETTE->isArgumentType())
316 return;
317
318 const VariableArrayType *VLA = C.getASTContext().getAsVariableArrayType(
319 T: UETTE->getTypeOfArgument().getCanonicalType());
320 // Ensure that the type is a VLA.
321 if (!VLA)
322 return;
323
324 ProgramStateRef State = C.getState();
325 SVal ArraySize;
326 State = checkVLA(C, State, VLA, ArraySize);
327 if (!State)
328 return;
329
330 C.addTransition(State);
331}
332
333void ento::registerVLASizeChecker(CheckerManager &mgr) {
334 mgr.registerChecker<VLASizeChecker>();
335}
336
337bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) {
338 return true;
339}
340