1 //=== VLASizeChecker.cpp - Undefined dereference checker --------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This defines VLASizeChecker, a builtin check in ExprEngine that
11 // performs checks for declaration of VLA of undefined or zero size.
12 // In addition, VLASizeChecker is responsible for defining the extent
13 // of the MemRegion that represents a VLA.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
18 #include "clang/AST/CharUnits.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 "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SmallString.h"
25 #include "llvm/Support/raw_ostream.h"
26 
27 using namespace clang;
28 using namespace ento;
29 
30 namespace {
31 class VLASizeChecker : public Checker< check::PreStmt<DeclStmt> > {
32   mutable std::unique_ptr<BugType> BT;
33   enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative };
34 
35   void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
36                  CheckerContext &C,
37                  std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
38 
39 public:
40   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
41 };
42 } // end anonymous namespace
43 
reportBug(VLASize_Kind Kind,const Expr * SizeE,ProgramStateRef State,CheckerContext & C,std::unique_ptr<BugReporterVisitor> Visitor) const44 void VLASizeChecker::reportBug(
45     VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
46     CheckerContext &C, std::unique_ptr<BugReporterVisitor> Visitor) const {
47   // Generate an error node.
48   ExplodedNode *N = C.generateErrorNode(State);
49   if (!N)
50     return;
51 
52   if (!BT)
53     BT.reset(new BuiltinBug(
54         this, "Dangerous variable-length array (VLA) declaration"));
55 
56   SmallString<256> buf;
57   llvm::raw_svector_ostream os(buf);
58   os << "Declared variable-length array (VLA) ";
59   switch (Kind) {
60   case VLA_Garbage:
61     os << "uses a garbage value as its size";
62     break;
63   case VLA_Zero:
64     os << "has zero size";
65     break;
66   case VLA_Tainted:
67     os << "has tainted size";
68     break;
69   case VLA_Negative:
70     os << "has negative size";
71     break;
72   }
73 
74   auto report = llvm::make_unique<BugReport>(*BT, os.str(), N);
75   report->addVisitor(std::move(Visitor));
76   report->addRange(SizeE->getSourceRange());
77   bugreporter::trackExpressionValue(N, SizeE, *report);
78   C.emitReport(std::move(report));
79 }
80 
checkPreStmt(const DeclStmt * DS,CheckerContext & C) const81 void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
82   if (!DS->isSingleDecl())
83     return;
84 
85   const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
86   if (!VD)
87     return;
88 
89   ASTContext &Ctx = C.getASTContext();
90   const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType());
91   if (!VLA)
92     return;
93 
94   // FIXME: Handle multi-dimensional VLAs.
95   const Expr *SE = VLA->getSizeExpr();
96   ProgramStateRef state = C.getState();
97   SVal sizeV = C.getSVal(SE);
98 
99   if (sizeV.isUndef()) {
100     reportBug(VLA_Garbage, SE, state, C);
101     return;
102   }
103 
104   // See if the size value is known. It can't be undefined because we would have
105   // warned about that already.
106   if (sizeV.isUnknown())
107     return;
108 
109   // Check if the size is tainted.
110   if (state->isTainted(sizeV)) {
111     reportBug(VLA_Tainted, SE, nullptr, C,
112               llvm::make_unique<TaintBugVisitor>(sizeV));
113     return;
114   }
115 
116   // Check if the size is zero.
117   DefinedSVal sizeD = sizeV.castAs<DefinedSVal>();
118 
119   ProgramStateRef stateNotZero, stateZero;
120   std::tie(stateNotZero, stateZero) = state->assume(sizeD);
121 
122   if (stateZero && !stateNotZero) {
123     reportBug(VLA_Zero, SE, stateZero, C);
124     return;
125   }
126 
127   // From this point on, assume that the size is not zero.
128   state = stateNotZero;
129 
130   // VLASizeChecker is responsible for defining the extent of the array being
131   // declared. We do this by multiplying the array length by the element size,
132   // then matching that with the array region's extent symbol.
133 
134   // Check if the size is negative.
135   SValBuilder &svalBuilder = C.getSValBuilder();
136 
137   QualType Ty = SE->getType();
138   DefinedOrUnknownSVal Zero = svalBuilder.makeZeroVal(Ty);
139 
140   SVal LessThanZeroVal = svalBuilder.evalBinOp(state, BO_LT, sizeD, Zero, Ty);
141   if (Optional<DefinedSVal> LessThanZeroDVal =
142         LessThanZeroVal.getAs<DefinedSVal>()) {
143     ConstraintManager &CM = C.getConstraintManager();
144     ProgramStateRef StatePos, StateNeg;
145 
146     std::tie(StateNeg, StatePos) = CM.assumeDual(state, *LessThanZeroDVal);
147     if (StateNeg && !StatePos) {
148       reportBug(VLA_Negative, SE, state, C);
149       return;
150     }
151     state = StatePos;
152   }
153 
154   // Convert the array length to size_t.
155   QualType SizeTy = Ctx.getSizeType();
156   NonLoc ArrayLength =
157       svalBuilder.evalCast(sizeD, SizeTy, SE->getType()).castAs<NonLoc>();
158 
159   // Get the element size.
160   CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType());
161   SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy);
162 
163   // Multiply the array length by the element size.
164   SVal ArraySizeVal = svalBuilder.evalBinOpNN(
165       state, BO_Mul, ArrayLength, EleSizeVal.castAs<NonLoc>(), SizeTy);
166 
167   // Finally, assume that the array's extent matches the given size.
168   const LocationContext *LC = C.getLocationContext();
169   DefinedOrUnknownSVal Extent =
170     state->getRegion(VD, LC)->getExtent(svalBuilder);
171   DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs<DefinedOrUnknownSVal>();
172   DefinedOrUnknownSVal sizeIsKnown =
173     svalBuilder.evalEQ(state, Extent, ArraySize);
174   state = state->assume(sizeIsKnown, true);
175 
176   // Assume should not fail at this point.
177   assert(state);
178 
179   // Remember our assumptions!
180   C.addTransition(state);
181 }
182 
registerVLASizeChecker(CheckerManager & mgr)183 void ento::registerVLASizeChecker(CheckerManager &mgr) {
184   mgr.registerChecker<VLASizeChecker>();
185 }
186