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 { 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 67 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 assert(IndexL > 0 && "Index length should have been checked for zero."); 130 if (KnownSize <= SizeMax / IndexL) { 131 KnownSize *= IndexL; 132 } else { 133 // Array size does not fit into size_t. 134 reportBug(VLA_Overflow, SizeE, State, C); 135 return nullptr; 136 } 137 } else { 138 KnownSize = 0; 139 } 140 } 141 142 ArraySize = ArrSize; 143 144 return State; 145 } 146 147 ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C, 148 ProgramStateRef State, 149 const Expr *SizeE) const { 150 SVal SizeV = C.getSVal(SizeE); 151 152 if (SizeV.isUndef()) { 153 reportBug(VLA_Garbage, SizeE, State, C); 154 return nullptr; 155 } 156 157 // See if the size value is known. It can't be undefined because we would have 158 // warned about that already. 159 if (SizeV.isUnknown()) 160 return nullptr; 161 162 // Check if the size is tainted. 163 if (isTainted(State, SizeV)) { 164 reportBug(VLA_Tainted, SizeE, nullptr, C, 165 std::make_unique<TaintBugVisitor>(SizeV)); 166 return nullptr; 167 } 168 169 // Check if the size is zero. 170 DefinedSVal SizeD = SizeV.castAs<DefinedSVal>(); 171 172 ProgramStateRef StateNotZero, StateZero; 173 std::tie(StateNotZero, StateZero) = State->assume(SizeD); 174 175 if (StateZero && !StateNotZero) { 176 reportBug(VLA_Zero, SizeE, StateZero, C); 177 return nullptr; 178 } 179 180 // From this point on, assume that the size is not zero. 181 State = StateNotZero; 182 183 // Check if the size is negative. 184 SValBuilder &SVB = C.getSValBuilder(); 185 186 QualType SizeTy = SizeE->getType(); 187 DefinedOrUnknownSVal Zero = SVB.makeZeroVal(SizeTy); 188 189 SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy); 190 if (Optional<DefinedSVal> LessThanZeroDVal = 191 LessThanZeroVal.getAs<DefinedSVal>()) { 192 ConstraintManager &CM = C.getConstraintManager(); 193 ProgramStateRef StatePos, StateNeg; 194 195 std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal); 196 if (StateNeg && !StatePos) { 197 reportBug(VLA_Negative, SizeE, State, C); 198 return nullptr; 199 } 200 State = StatePos; 201 } 202 203 return State; 204 } 205 206 void VLASizeChecker::reportBug( 207 VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State, 208 CheckerContext &C, std::unique_ptr<BugReporterVisitor> Visitor) const { 209 // Generate an error node. 210 ExplodedNode *N = C.generateErrorNode(State); 211 if (!N) 212 return; 213 214 if (!BT) 215 BT.reset(new BuiltinBug( 216 this, "Dangerous variable-length array (VLA) declaration")); 217 218 SmallString<256> buf; 219 llvm::raw_svector_ostream os(buf); 220 os << "Declared variable-length array (VLA) "; 221 switch (Kind) { 222 case VLA_Garbage: 223 os << "uses a garbage value as its size"; 224 break; 225 case VLA_Zero: 226 os << "has zero size"; 227 break; 228 case VLA_Tainted: 229 os << "has tainted size"; 230 break; 231 case VLA_Negative: 232 os << "has negative size"; 233 break; 234 case VLA_Overflow: 235 os << "has too large size"; 236 break; 237 } 238 239 auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N); 240 report->addVisitor(std::move(Visitor)); 241 report->addRange(SizeE->getSourceRange()); 242 bugreporter::trackExpressionValue(N, SizeE, *report); 243 C.emitReport(std::move(report)); 244 } 245 246 void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 247 if (!DS->isSingleDecl()) 248 return; 249 250 ASTContext &Ctx = C.getASTContext(); 251 SValBuilder &SVB = C.getSValBuilder(); 252 ProgramStateRef State = C.getState(); 253 QualType TypeToCheck; 254 255 const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 256 257 if (VD) 258 TypeToCheck = VD->getType().getCanonicalType(); 259 else if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl())) 260 TypeToCheck = TND->getUnderlyingType().getCanonicalType(); 261 else 262 return; 263 264 const VariableArrayType *VLA = Ctx.getAsVariableArrayType(TypeToCheck); 265 if (!VLA) 266 return; 267 268 // Check the VLA sizes for validity. 269 270 SVal ArraySize; 271 272 State = checkVLA(C, State, VLA, ArraySize); 273 if (!State) 274 return; 275 276 auto ArraySizeNL = ArraySize.getAs<NonLoc>(); 277 if (!ArraySizeNL) { 278 // Array size could not be determined but state may contain new assumptions. 279 C.addTransition(State); 280 return; 281 } 282 283 // VLASizeChecker is responsible for defining the extent of the array being 284 // declared. We do this by multiplying the array length by the element size, 285 // then matching that with the array region's extent symbol. 286 287 if (VD) { 288 // Assume that the array's size matches the region size. 289 const LocationContext *LC = C.getLocationContext(); 290 DefinedOrUnknownSVal DynSize = 291 getDynamicSize(State, State->getRegion(VD, LC), SVB); 292 293 DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, *ArraySizeNL); 294 State = State->assume(SizeIsKnown, true); 295 296 // Assume should not fail at this point. 297 assert(State); 298 } 299 300 // Remember our assumptions! 301 C.addTransition(State); 302 } 303 304 void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE, 305 CheckerContext &C) const { 306 // Want to check for sizeof. 307 if (UETTE->getKind() != UETT_SizeOf) 308 return; 309 310 // Ensure a type argument. 311 if (!UETTE->isArgumentType()) 312 return; 313 314 const VariableArrayType *VLA = C.getASTContext().getAsVariableArrayType( 315 UETTE->getTypeOfArgument().getCanonicalType()); 316 // Ensure that the type is a VLA. 317 if (!VLA) 318 return; 319 320 ProgramStateRef State = C.getState(); 321 SVal ArraySize; 322 State = checkVLA(C, State, VLA, ArraySize); 323 if (!State) 324 return; 325 326 C.addTransition(State); 327 } 328 329 void ento::registerVLASizeChecker(CheckerManager &mgr) { 330 mgr.registerChecker<VLASizeChecker>(); 331 } 332 333 bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) { 334 return true; 335 } 336