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/DynamicExtent.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SmallString.h"
26#include "llvm/Support/raw_ostream.h"
27
28using namespace clang;
29using namespace ento;
30using namespace taint;
31
32namespace {
33class 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
60public:
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
67ProgramStateRef 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      // 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
152ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C,
153                                                  ProgramStateRef State,
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
211void 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
251void 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
299void 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(
310      UETTE->getTypeOfArgument().getCanonicalType());
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
324void ento::registerVLASizeChecker(CheckerManager &mgr) {
325  mgr.registerChecker<VLASizeChecker>();
326}
327
328bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) {
329  return true;
330}
331