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 34 : public Checker<check::PreStmt<DeclStmt>, 35 check::PreStmt<UnaryExprOrTypeTraitExpr>> { 36 mutable std::unique_ptr<BugType> BT; 37 enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative }; 38 39 /// Check a VLA for validity. 40 /// Every dimension of the array is checked for validity, and 41 /// dimension sizes are collected into 'VLASizes'. 'VLALast' is set to the 42 /// innermost VLA that was encountered. 43 /// In "int vla[x][2][y][3]" this will be the array for index "y" (with type 44 /// int[3]). 'VLASizes' contains 'x', '2', and 'y'. Returns null or a new 45 /// state where the size is validated for every dimension. 46 ProgramStateRef checkVLA(CheckerContext &C, ProgramStateRef State, 47 const VariableArrayType *VLA, 48 const VariableArrayType *&VLALast, 49 llvm::SmallVector<const Expr *, 2> &VLASizes) const; 50 51 /// Check one VLA dimension for validity. 52 /// Returns null or a new state where the size is validated. 53 ProgramStateRef checkVLASize(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 67 ProgramStateRef 68 VLASizeChecker::checkVLA(CheckerContext &C, ProgramStateRef State, 69 const VariableArrayType *VLA, 70 const VariableArrayType *&VLALast, 71 llvm::SmallVector<const Expr *, 2> &VLASizes) const { 72 assert(VLA && "Function should be called with non-null VLA argument."); 73 74 VLALast = nullptr; 75 // Walk over the VLAs for every dimension until a non-VLA is found. 76 // There is a VariableArrayType for every dimension (fixed or variable) until 77 // the most inner array that is variably modified. 78 while (VLA) { 79 const Expr *SizeE = VLA->getSizeExpr(); 80 State = checkVLASize(C, State, SizeE); 81 if (!State) 82 return nullptr; 83 VLASizes.push_back(SizeE); 84 VLALast = VLA; 85 VLA = C.getASTContext().getAsVariableArrayType(VLA->getElementType()); 86 }; 87 assert(VLALast && 88 "Array should have at least one variably-modified dimension."); 89 90 return State; 91 } 92 93 ProgramStateRef VLASizeChecker::checkVLASize(CheckerContext &C, 94 ProgramStateRef State, 95 const Expr *SizeE) const { 96 SVal SizeV = C.getSVal(SizeE); 97 98 if (SizeV.isUndef()) { 99 reportBug(VLA_Garbage, SizeE, State, C); 100 return nullptr; 101 } 102 103 // See if the size value is known. It can't be undefined because we would have 104 // warned about that already. 105 if (SizeV.isUnknown()) 106 return nullptr; 107 108 // Check if the size is tainted. 109 if (isTainted(State, SizeV)) { 110 reportBug(VLA_Tainted, SizeE, nullptr, C, 111 std::make_unique<TaintBugVisitor>(SizeV)); 112 return nullptr; 113 } 114 115 // Check if the size is zero. 116 DefinedSVal SizeD = SizeV.castAs<DefinedSVal>(); 117 118 ProgramStateRef StateNotZero, StateZero; 119 std::tie(StateNotZero, StateZero) = State->assume(SizeD); 120 121 if (StateZero && !StateNotZero) { 122 reportBug(VLA_Zero, SizeE, StateZero, C); 123 return nullptr; 124 } 125 126 // From this point on, assume that the size is not zero. 127 State = StateNotZero; 128 129 // Check if the size is negative. 130 SValBuilder &SVB = C.getSValBuilder(); 131 132 QualType SizeTy = SizeE->getType(); 133 DefinedOrUnknownSVal Zero = SVB.makeZeroVal(SizeTy); 134 135 SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy); 136 if (Optional<DefinedSVal> LessThanZeroDVal = 137 LessThanZeroVal.getAs<DefinedSVal>()) { 138 ConstraintManager &CM = C.getConstraintManager(); 139 ProgramStateRef StatePos, StateNeg; 140 141 std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal); 142 if (StateNeg && !StatePos) { 143 reportBug(VLA_Negative, SizeE, State, C); // FIXME: StateNeg ? 144 return nullptr; 145 } 146 State = StatePos; 147 } 148 149 return State; 150 } 151 152 void VLASizeChecker::reportBug( 153 VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State, 154 CheckerContext &C, std::unique_ptr<BugReporterVisitor> Visitor) const { 155 // Generate an error node. 156 ExplodedNode *N = C.generateErrorNode(State); 157 if (!N) 158 return; 159 160 if (!BT) 161 BT.reset(new BuiltinBug( 162 this, "Dangerous variable-length array (VLA) declaration")); 163 164 SmallString<256> buf; 165 llvm::raw_svector_ostream os(buf); 166 os << "Declared variable-length array (VLA) "; 167 switch (Kind) { 168 case VLA_Garbage: 169 os << "uses a garbage value as its size"; 170 break; 171 case VLA_Zero: 172 os << "has zero size"; 173 break; 174 case VLA_Tainted: 175 os << "has tainted size"; 176 break; 177 case VLA_Negative: 178 os << "has negative size"; 179 break; 180 } 181 182 auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N); 183 report->addVisitor(std::move(Visitor)); 184 report->addRange(SizeE->getSourceRange()); 185 bugreporter::trackExpressionValue(N, SizeE, *report); 186 C.emitReport(std::move(report)); 187 } 188 189 void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 190 if (!DS->isSingleDecl()) 191 return; 192 193 ASTContext &Ctx = C.getASTContext(); 194 SValBuilder &SVB = C.getSValBuilder(); 195 ProgramStateRef State = C.getState(); 196 QualType TypeToCheck; 197 198 const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 199 200 if (VD) 201 TypeToCheck = VD->getType().getCanonicalType(); 202 else if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl())) 203 TypeToCheck = TND->getUnderlyingType().getCanonicalType(); 204 else 205 return; 206 207 const VariableArrayType *VLA = Ctx.getAsVariableArrayType(TypeToCheck); 208 if (!VLA) 209 return; 210 211 // Check the VLA sizes for validity. 212 llvm::SmallVector<const Expr *, 2> VLASizes; 213 const VariableArrayType *VLALast = nullptr; 214 215 State = checkVLA(C, State, VLA, VLALast, VLASizes); 216 if (!State) 217 return; 218 219 if (!VD) 220 return; 221 222 // VLASizeChecker is responsible for defining the extent of the array being 223 // declared. We do this by multiplying the array length by the element size, 224 // then matching that with the array region's extent symbol. 225 226 CanQualType SizeTy = Ctx.getSizeType(); 227 // Get the element size. 228 CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType()); 229 NonLoc ArraySize = 230 SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs<NonLoc>(); 231 232 for (const Expr *SizeE : VLASizes) { 233 auto SizeD = C.getSVal(SizeE).castAs<DefinedSVal>(); 234 // Convert the array length to size_t. 235 NonLoc IndexLength = 236 SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs<NonLoc>(); 237 // Multiply the array length by the element size. 238 SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArraySize, IndexLength, SizeTy); 239 if (auto MulNonLoc = Mul.getAs<NonLoc>()) { 240 ArraySize = *MulNonLoc; 241 } else { 242 // Extent could not be determined. 243 // The state was probably still updated by the validation checks. 244 C.addTransition(State); 245 return; 246 } 247 } 248 249 // Finally, assume that the array's size matches the given size. 250 const LocationContext *LC = C.getLocationContext(); 251 DefinedOrUnknownSVal DynSize = 252 getDynamicSize(State, State->getRegion(VD, LC), SVB); 253 254 DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, ArraySize); 255 State = State->assume(SizeIsKnown, true); 256 257 // Assume should not fail at this point. 258 assert(State); 259 260 // Remember our assumptions! 261 C.addTransition(State); 262 } 263 264 void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE, 265 CheckerContext &C) const { 266 // Want to check for sizeof. 267 if (UETTE->getKind() != UETT_SizeOf) 268 return; 269 270 // Ensure a type argument. 271 if (!UETTE->isArgumentType()) 272 return; 273 274 const VariableArrayType *VLA = 275 C.getASTContext().getAsVariableArrayType(UETTE->getTypeOfArgument()); 276 // Ensure that the type is a VLA. 277 if (!VLA) 278 return; 279 280 ProgramStateRef State = C.getState(); 281 282 llvm::SmallVector<const Expr *, 2> VLASizes; 283 const VariableArrayType *VLALast = nullptr; 284 State = checkVLA(C, State, VLA, VLALast, VLASizes); 285 if (!State) 286 return; 287 288 C.addTransition(State); 289 } 290 291 void ento::registerVLASizeChecker(CheckerManager &mgr) { 292 mgr.registerChecker<VLASizeChecker>(); 293 } 294 295 bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) { 296 return true; 297 } 298