clang  14.0.0git
VLASizeChecker.cpp
Go to the documentation of this file.
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"
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,
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;
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  // FIXME: See https://reviews.llvm.org/D80903 for discussion of
130  // some difference in assume and getKnownValue that leads to
131  // unexpected behavior. Just bail on IndexL == 0 at this point.
132  if (IndexL == 0)
133  return nullptr;
134 
135  if (KnownSize <= SizeMax / IndexL) {
136  KnownSize *= IndexL;
137  } else {
138  // Array size does not fit into size_t.
139  reportBug(VLA_Overflow, SizeE, State, C);
140  return nullptr;
141  }
142  } else {
143  KnownSize = 0;
144  }
145  }
146 
147  ArraySize = ArrSize;
148 
149  return State;
150 }
151 
152 ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C,
154  const Expr *SizeE) const {
155  SVal SizeV = C.getSVal(SizeE);
156 
157  if (SizeV.isUndef()) {
158  reportBug(VLA_Garbage, SizeE, State, C);
159  return nullptr;
160  }
161 
162  // See if the size value is known. It can't be undefined because we would have
163  // warned about that already.
164  if (SizeV.isUnknown())
165  return nullptr;
166 
167  // Check if the size is tainted.
168  if (isTainted(State, SizeV)) {
169  reportBug(VLA_Tainted, SizeE, nullptr, C,
170  std::make_unique<TaintBugVisitor>(SizeV));
171  return nullptr;
172  }
173 
174  // Check if the size is zero.
175  DefinedSVal SizeD = SizeV.castAs<DefinedSVal>();
176 
177  ProgramStateRef StateNotZero, StateZero;
178  std::tie(StateNotZero, StateZero) = State->assume(SizeD);
179 
180  if (StateZero && !StateNotZero) {
181  reportBug(VLA_Zero, SizeE, StateZero, C);
182  return nullptr;
183  }
184 
185  // From this point on, assume that the size is not zero.
186  State = StateNotZero;
187 
188  // Check if the size is negative.
189  SValBuilder &SVB = C.getSValBuilder();
190 
191  QualType SizeTy = SizeE->getType();
192  DefinedOrUnknownSVal Zero = SVB.makeZeroVal(SizeTy);
193 
194  SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy);
195  if (Optional<DefinedSVal> LessThanZeroDVal =
196  LessThanZeroVal.getAs<DefinedSVal>()) {
197  ConstraintManager &CM = C.getConstraintManager();
198  ProgramStateRef StatePos, StateNeg;
199 
200  std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal);
201  if (StateNeg && !StatePos) {
202  reportBug(VLA_Negative, SizeE, State, C);
203  return nullptr;
204  }
205  State = StatePos;
206  }
207 
208  return State;
209 }
210 
211 void VLASizeChecker::reportBug(
212  VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
213  CheckerContext &C, std::unique_ptr<BugReporterVisitor> Visitor) const {
214  // Generate an error node.
215  ExplodedNode *N = C.generateErrorNode(State);
216  if (!N)
217  return;
218 
219  if (!BT)
220  BT.reset(new BuiltinBug(
221  this, "Dangerous variable-length array (VLA) declaration"));
222 
223  SmallString<256> buf;
224  llvm::raw_svector_ostream os(buf);
225  os << "Declared variable-length array (VLA) ";
226  switch (Kind) {
227  case VLA_Garbage:
228  os << "uses a garbage value as its size";
229  break;
230  case VLA_Zero:
231  os << "has zero size";
232  break;
233  case VLA_Tainted:
234  os << "has tainted size";
235  break;
236  case VLA_Negative:
237  os << "has negative size";
238  break;
239  case VLA_Overflow:
240  os << "has too large size";
241  break;
242  }
243 
244  auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N);
245  report->addVisitor(std::move(Visitor));
246  report->addRange(SizeE->getSourceRange());
247  bugreporter::trackExpressionValue(N, SizeE, *report);
248  C.emitReport(std::move(report));
249 }
250 
251 void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
252  if (!DS->isSingleDecl())
253  return;
254 
255  ASTContext &Ctx = C.getASTContext();
256  SValBuilder &SVB = C.getSValBuilder();
257  ProgramStateRef State = C.getState();
258  QualType TypeToCheck;
259 
260  const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
261 
262  if (VD)
263  TypeToCheck = VD->getType().getCanonicalType();
264  else if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl()))
265  TypeToCheck = TND->getUnderlyingType().getCanonicalType();
266  else
267  return;
268 
269  const VariableArrayType *VLA = Ctx.getAsVariableArrayType(TypeToCheck);
270  if (!VLA)
271  return;
272 
273  // Check the VLA sizes for validity.
274 
275  SVal ArraySize;
276 
277  State = checkVLA(C, State, VLA, ArraySize);
278  if (!State)
279  return;
280 
281  auto ArraySizeNL = ArraySize.getAs<NonLoc>();
282  if (!ArraySizeNL) {
283  // Array size could not be determined but state may contain new assumptions.
284  C.addTransition(State);
285  return;
286  }
287 
288  // VLASizeChecker is responsible for defining the extent of the array.
289  if (VD) {
290  State =
291  setDynamicExtent(State, State->getRegion(VD, C.getLocationContext()),
292  ArraySize.castAs<DefinedOrUnknownSVal>(), SVB);
293  }
294 
295  // Remember our assumptions!
296  C.addTransition(State);
297 }
298 
299 void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
300  CheckerContext &C) const {
301  // Want to check for sizeof.
302  if (UETTE->getKind() != UETT_SizeOf)
303  return;
304 
305  // Ensure a type argument.
306  if (!UETTE->isArgumentType())
307  return;
308 
309  const VariableArrayType *VLA = C.getASTContext().getAsVariableArrayType(
311  // Ensure that the type is a VLA.
312  if (!VLA)
313  return;
314 
315  ProgramStateRef State = C.getState();
316  SVal ArraySize;
317  State = checkVLA(C, State, VLA, ArraySize);
318  if (!State)
319  return;
320 
321  C.addTransition(State);
322 }
323 
324 void ento::registerVLASizeChecker(CheckerManager &mgr) {
325  mgr.registerChecker<VLASizeChecker>();
326 }
327 
328 bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) {
329  return true;
330 }
clang::ASTContext::getTypeSizeInChars
CharUnits getTypeSizeInChars(QualType T) const
Return the size of the specified (complete) type T, in characters.
Definition: ASTContext.cpp:2450
DynamicExtent.h
llvm::SmallVector
Definition: LLVM.h:38
clang::Stmt::getSourceRange
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:324
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:673
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
clang::QualType::getCanonicalType
QualType getCanonicalType() const
Definition: Type.h:6463
llvm::Optional
Definition: LLVM.h:40
clang::ento::taint::isTainted
bool isTainted(ProgramStateRef State, const Stmt *S, const LocationContext *LCtx, TaintTagType Kind=TaintTagGeneric)
Check if the statement has a tainted value in the given state.
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
clang::UnaryExprOrTypeTraitExpr
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand.
Definition: Expr.h:2543
BuiltinCheckerRegistration.h
clang::interp::Mul
bool Mul(InterpState &S, CodePtr OpPC)
Definition: Interp.h:150
CheckerManager.h
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:212
clang::ASTContext::getSizeType
CanQualType getSizeType() const
Return the unique type for "size_t" (C99 7.17), defined in <stddef.h>.
Definition: ASTContext.cpp:5709
clang::ASTContext::getAsVariableArrayType
const VariableArrayType * getAsVariableArrayType(QualType T) const
Definition: ASTContext.h:2632
clang::VariableArrayType::getSizeExpr
Expr * getSizeExpr() const
Definition: Type.h:3052
llvm::SmallString
Definition: LLVM.h:37
clang::interp::Zero
bool Zero(InterpState &S, CodePtr OpPC)
Definition: Interp.h:814
clang::VarDecl
Represents a variable declaration or definition.
Definition: Decl.h:876
clang::CanQual< Type >
CharUnits.h
clang::ento::bugreporter::trackExpressionValue
bool trackExpressionValue(const ExplodedNode *N, const Expr *E, PathSensitiveBugReport &R, TrackingOptions Opts={})
Attempts to add visitors to track expression value back to its point of origin.
clang::UnaryExprOrTypeTraitExpr::isArgumentType
bool isArgumentType() const
Definition: Expr.h:2585
clang::DeclStmt::getSingleDecl
const Decl * getSingleDecl() const
Definition: Stmt.h:1307
clang::DeclStmt::isSingleDecl
bool isSingleDecl() const
isSingleDecl - This method returns true if this DeclStmt refers to a single Decl.
Definition: Stmt.h:1305
clang::VariableArrayType
Represents a C array with a specified size that is not an integer-constant-expression.
Definition: Type.h:3033
Taint.h
BugType.h
clang::UnaryExprOrTypeTraitExpr::getTypeOfArgument
QualType getTypeOfArgument() const
Gets the argument type, or the type of the argument expression, whichever is appropriate.
Definition: Expr.h:2612
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
CheckerContext.h
clang::ObjCPropertyAttribute::Kind
Kind
Definition: DeclObjCCommon.h:22
clang::DeclStmt
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1292
Checker.h
clang::UnaryExprOrTypeTraitExpr::getKind
UnaryExprOrTypeTrait getKind() const
Definition: Expr.h:2575
clang
Definition: CalledOnceCheck.h:17
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::ento::setDynamicExtent
ProgramStateRef setDynamicExtent(ProgramStateRef State, const MemRegion *MR, DefinedOrUnknownSVal Extent, SValBuilder &SVB)
Set the dynamic extent Extent of the region MR.
clang::CharUnits
CharUnits - This is an opaque type for sizes expressed in character units.
Definition: CharUnits.h:38
clang::ValueDecl::getType
QualType getType() const
Definition: Decl.h:687
clang::ArrayType::getElementType
QualType getElementType() const
Definition: Type.h:2904
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::CharUnits::getQuantity
QuantityType getQuantity() const
getQuantity - Get the raw integer representation of this quantity.
Definition: CharUnits.h:179