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