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