clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.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-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 "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/ADT/STLExtras.h"
  25 #include "llvm/ADT/SmallString.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include <optional>
  28
  29 using namespace clang;
  30 using namespace ento;
  31 using namespace taint;
  32
  33 namespace {
  34 class VLASizeChecker
  35     : public Checker<check::PreStmt<DeclStmt>,
  36                      check::PreStmt<UnaryExprOrTypeTraitExpr>> {
  37   mutable std::unique_ptr<BugType> BT;
  38   mutable std::unique_ptr<BugType> TaintBT;
  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
  58 public:
  59   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
  60   void checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
  61                     CheckerContext &C) const;
  62 };
  63 } // end anonymous namespace
  64
  65 ProgramStateRef 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) until
  76   // the most inner array that is variably modified.
  77   // Dimension sizes are collected into 'VLASizes'. 'VLALast' is set to the
  78   // innermost VLA that was encountered.
  79   // In "int vla[x][2][y][3]" this will be the array for index "y" (with type
  80   // 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   CanQualType 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     else
 119       // 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 a
 125       // overflow situation can not be detected easily.
 126       uint64_t IndexL = IndexLVal->getZExtValue();
 127       // FIXME: See https://reviews.llvm.org/D80903 for discussion of
 128       // some difference in assume and getKnownValue that leads to
 129       // 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
 150 ProgramStateRef 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 have
 161   // warned about that already.
 162   if (SizeV.isUnknown())
 163     return nullptr;
 164
 165   // Check if the size is tainted.
 166   if (isTainted(State, SizeV)) {
 167     reportTaintBug(SizeE, State, C, SizeV);
 168     return nullptr;
 169   }
 170
 171   // Check if the size is zero.
 172   DefinedSVal SizeD = SizeV.castAs<DefinedSVal>();
 173
 174   ProgramStateRef StateNotZero, StateZero;
 175   std::tie(StateNotZero, StateZero) = State->assume(SizeD);
 176
 177   if (StateZero && !StateNotZero) {
 178     reportBug(VLA_Zero, SizeE, StateZero, C);
 179     return nullptr;
 180   }
 181
 182   // From this point on, assume that the size is not zero.
 183   State = StateNotZero;
 184
 185   // Check if the size is negative.
 186   SValBuilder &SVB = C.getSValBuilder();
 187
 188   QualType SizeTy = SizeE->getType();
 189   DefinedOrUnknownSVal Zero = SVB.makeZeroVal(SizeTy);
 190
 191   SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy);
 192   if (std::optional<DefinedSVal> LessThanZeroDVal =
 193           LessThanZeroVal.getAs<DefinedSVal>()) {
 194     ConstraintManager &CM = C.getConstraintManager();
 195     ProgramStateRef StatePos, StateNeg;
 196
 197     std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal);
 198     if (StateNeg && !StatePos) {
 199       reportBug(VLA_Negative, SizeE, State, C);
 200       return nullptr;
 201     }
 202     State = StatePos;
 203   }
 204
 205   return State;
 206 }
 207
 208 void VLASizeChecker::reportTaintBug(const Expr *SizeE, ProgramStateRef State,
 209                                     CheckerContext &C, SVal TaintedSVal) const {
 210   // Generate an error node.
 211   ExplodedNode *N = C.generateErrorNode(State);
 212   if (!N)
 213     return;
 214
 215   if (!TaintBT)
 216     TaintBT.reset(
 217         new BugType(this, "Dangerous variable-length array (VLA) declaration",
 218                     categories::TaintedData));
 219
 220   SmallString<256> buf;
 221   llvm::raw_svector_ostream os(buf);
 222   os << "Declared variable-length array (VLA) ";
 223   os << "has tainted size";
 224
 225   auto report = std::make_unique<PathSensitiveBugReport>(*TaintBT, os.str(), N);
 226   report->addRange(SizeE->getSourceRange());
 227   bugreporter::trackExpressionValue(N, SizeE, *report);
 228   // The vla size may be a complex expression where multiple memory locations
 229   // are tainted.
 230   for (auto Sym : getTaintedSymbols(State, TaintedSVal))
 231     report->markInteresting(Sym);
 232   C.emitReport(std::move(report));
 233 }
 234
 235 void VLASizeChecker::reportBug(VLASize_Kind Kind, const Expr *SizeE,
 236                                ProgramStateRef State, CheckerContext &C) const {
 237   // Generate an error node.
 238   ExplodedNode *N = C.generateErrorNode(State);
 239   if (!N)
 240     return;
 241
 242   if (!BT)
 243     BT.reset(new BugType(this,
 244                          "Dangerous variable-length array (VLA) declaration",
 245                          categories::LogicError));
 246
 247   SmallString<256> buf;
 248   llvm::raw_svector_ostream os(buf);
 249   os << "Declared variable-length array (VLA) ";
 250   switch (Kind) {
 251   case VLA_Garbage:
 252     os << "uses a garbage value as its size";
 253     break;
 254   case VLA_Zero:
 255     os << "has zero size";
 256     break;
 257   case VLA_Negative:
 258     os << "has negative size";
 259     break;
 260   case VLA_Overflow:
 261     os << "has too large size";
 262     break;
 263   }
 264
 265   auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N);
 266   report->addRange(SizeE->getSourceRange());
 267   bugreporter::trackExpressionValue(N, SizeE, *report);
 268   C.emitReport(std::move(report));
 269 }
 270
 271 void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
 272   if (!DS->isSingleDecl())
 273     return;
 274
 275   ASTContext &Ctx = C.getASTContext();
 276   SValBuilder &SVB = C.getSValBuilder();
 277   ProgramStateRef State = C.getState();
 278   QualType TypeToCheck;
 279
 280   const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
 281
 282   if (VD)
 283     TypeToCheck = VD->getType().getCanonicalType();
 284   else if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl()))
 285     TypeToCheck = TND->getUnderlyingType().getCanonicalType();
 286   else
 287     return;
 288
 289   const VariableArrayType *VLA = Ctx.getAsVariableArrayType(TypeToCheck);
 290   if (!VLA)
 291     return;
 292
 293   // Check the VLA sizes for validity.
 294
 295   SVal ArraySize;
 296
 297   State = checkVLA(C, State, VLA, ArraySize);
 298   if (!State)
 299     return;
 300
 301   if (!isa<NonLoc>(ArraySize)) {
 302     // Array size could not be determined but state may contain new assumptions.
 303     C.addTransition(State);
 304     return;
 305   }
 306
 307   // VLASizeChecker is responsible for defining the extent of the array.
 308   if (VD) {
 309     State =
 310         setDynamicExtent(State, State->getRegion(VD, C.getLocationContext()),
 311                          ArraySize.castAs<NonLoc>(), SVB);
 312   }
 313
 314   // Remember our assumptions!
 315   C.addTransition(State);
 316 }
 317
 318 void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
 319                                   CheckerContext &C) const {
 320   // Want to check for sizeof.
 321   if (UETTE->getKind() != UETT_SizeOf)
 322     return;
 323
 324   // Ensure a type argument.
 325   if (!UETTE->isArgumentType())
 326     return;
 327
 328   const VariableArrayType *VLA = C.getASTContext().getAsVariableArrayType(
 329       UETTE->getTypeOfArgument().getCanonicalType());
 330   // Ensure that the type is a VLA.
 331   if (!VLA)
 332     return;
 333
 334   ProgramStateRef State = C.getState();
 335   SVal ArraySize;
 336   State = checkVLA(C, State, VLA, ArraySize);
 337   if (!State)
 338     return;
 339
 340   C.addTransition(State);
 341 }
 342
 343 void ento::registerVLASizeChecker(CheckerManager &mgr) {
 344   mgr.registerChecker<VLASizeChecker>();
 345 }
 346
 347 bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) {
 348   return true;
 349 }