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