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