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 "Taint.h"
17 #include "clang/AST/CharUnits.h"
18 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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/DynamicSize.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 : public Checker< check::PreStmt<DeclStmt> > {
34   mutable std::unique_ptr<BugType> BT;
35   enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative };
36 
37   ProgramStateRef checkVLASize(CheckerContext &C, ProgramStateRef State,
38                                const Expr *SizeE) const;
39 
40   void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
41                  CheckerContext &C,
42                  std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
43 
44 public:
45   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
46 };
47 } // end anonymous namespace
48 
49 ProgramStateRef VLASizeChecker::checkVLASize(CheckerContext &C,
50                                              ProgramStateRef State,
51                                              const Expr *SizeE) const {
52   SVal SizeV = C.getSVal(SizeE);
53 
54   if (SizeV.isUndef()) {
55     reportBug(VLA_Garbage, SizeE, State, C);
56     return nullptr;
57   }
58 
59   // See if the size value is known. It can't be undefined because we would have
60   // warned about that already.
61   if (SizeV.isUnknown())
62     return nullptr;
63 
64   // Check if the size is tainted.
65   if (isTainted(State, SizeV)) {
66     reportBug(VLA_Tainted, SizeE, nullptr, C,
67               std::make_unique<TaintBugVisitor>(SizeV));
68     return nullptr;
69   }
70 
71   // Check if the size is zero.
72   DefinedSVal SizeD = SizeV.castAs<DefinedSVal>();
73 
74   ProgramStateRef StateNotZero, StateZero;
75   std::tie(StateNotZero, StateZero) = State->assume(SizeD);
76 
77   if (StateZero && !StateNotZero) {
78     reportBug(VLA_Zero, SizeE, StateZero, C);
79     return nullptr;
80   }
81 
82   // From this point on, assume that the size is not zero.
83   State = StateNotZero;
84 
85   // Check if the size is negative.
86   SValBuilder &SVB = C.getSValBuilder();
87 
88   QualType SizeTy = SizeE->getType();
89   DefinedOrUnknownSVal Zero = SVB.makeZeroVal(SizeTy);
90 
91   SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy);
92   if (Optional<DefinedSVal> LessThanZeroDVal =
93           LessThanZeroVal.getAs<DefinedSVal>()) {
94     ConstraintManager &CM = C.getConstraintManager();
95     ProgramStateRef StatePos, StateNeg;
96 
97     std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal);
98     if (StateNeg && !StatePos) {
99       reportBug(VLA_Negative, SizeE, State, C); // FIXME: StateNeg ?
100       return nullptr;
101     }
102     State = StatePos;
103   }
104 
105   return State;
106 }
107 
108 void VLASizeChecker::reportBug(
109     VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
110     CheckerContext &C, std::unique_ptr<BugReporterVisitor> Visitor) const {
111   // Generate an error node.
112   ExplodedNode *N = C.generateErrorNode(State);
113   if (!N)
114     return;
115 
116   if (!BT)
117     BT.reset(new BuiltinBug(
118         this, "Dangerous variable-length array (VLA) declaration"));
119 
120   SmallString<256> buf;
121   llvm::raw_svector_ostream os(buf);
122   os << "Declared variable-length array (VLA) ";
123   switch (Kind) {
124   case VLA_Garbage:
125     os << "uses a garbage value as its size";
126     break;
127   case VLA_Zero:
128     os << "has zero size";
129     break;
130   case VLA_Tainted:
131     os << "has tainted size";
132     break;
133   case VLA_Negative:
134     os << "has negative size";
135     break;
136   }
137 
138   auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N);
139   report->addVisitor(std::move(Visitor));
140   report->addRange(SizeE->getSourceRange());
141   bugreporter::trackExpressionValue(N, SizeE, *report);
142   C.emitReport(std::move(report));
143 }
144 
145 void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
146   if (!DS->isSingleDecl())
147     return;
148 
149   const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
150   if (!VD)
151     return;
152 
153   ASTContext &Ctx = C.getASTContext();
154   SValBuilder &SVB = C.getSValBuilder();
155   ProgramStateRef State = C.getState();
156 
157   const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType());
158   if (!VLA)
159     return;
160 
161   llvm::SmallVector<const Expr *, 2> VLASizes;
162   const VariableArrayType *VLALast = nullptr;
163   // Walk over the VLAs for every dimension until a non-VLA is found.
164   // Collect the sizes in VLASizes, put the most inner VLA to `VLALast`.
165   // In "vla[x][2][y][3]" this will be the array for index "y".
166   // There is a VariableArrayType for every dimension (here "x", "2", "y")
167   // until a non-vla is found.
168   while (VLA) {
169     const Expr *SizeE = VLA->getSizeExpr();
170     State = checkVLASize(C, State, SizeE);
171     if (!State)
172       return;
173     VLASizes.push_back(SizeE);
174     VLALast = VLA;
175     VLA = Ctx.getAsVariableArrayType(VLA->getElementType());
176   };
177   assert(VLALast &&
178          "Array should have at least one variably-modified dimension.");
179 
180   // VLASizeChecker is responsible for defining the extent of the array being
181   // declared. We do this by multiplying the array length by the element size,
182   // then matching that with the array region's extent symbol.
183 
184   CanQualType SizeTy = Ctx.getSizeType();
185   // Get the element size.
186   CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType());
187   NonLoc ArraySize =
188       SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs<NonLoc>();
189 
190   for (const Expr *SizeE : VLASizes) {
191     auto SizeD = C.getSVal(SizeE).castAs<DefinedSVal>();
192     // Convert the array length to size_t.
193     NonLoc IndexLength =
194         SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs<NonLoc>();
195     // Multiply the array length by the element size.
196     SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArraySize, IndexLength, SizeTy);
197     if (auto MulNonLoc = Mul.getAs<NonLoc>()) {
198       ArraySize = *MulNonLoc;
199     } else {
200       // Extent could not be determined.
201       // The state was probably still updated by the validation checks.
202       C.addTransition(State);
203       return;
204     }
205   }
206 
207   // Finally, assume that the array's size matches the given size.
208   const LocationContext *LC = C.getLocationContext();
209   DefinedOrUnknownSVal DynSize =
210       getDynamicSize(State, State->getRegion(VD, LC), SVB);
211 
212   DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, ArraySize);
213   State = State->assume(SizeIsKnown, true);
214 
215   // Assume should not fail at this point.
216   assert(State);
217 
218   // Remember our assumptions!
219   C.addTransition(State);
220 }
221 
222 void ento::registerVLASizeChecker(CheckerManager &mgr) {
223   mgr.registerChecker<VLASizeChecker>();
224 }
225 
226 bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) {
227   return true;
228 }
229