1218887Sdim//=== VLASizeChecker.cpp - Undefined dereference checker --------*- C++ -*-===//
2218887Sdim//
3218887Sdim//                     The LLVM Compiler Infrastructure
4218887Sdim//
5218887Sdim// This file is distributed under the University of Illinois Open Source
6218887Sdim// License. See LICENSE.TXT for details.
7218887Sdim//
8218887Sdim//===----------------------------------------------------------------------===//
9218887Sdim//
10218887Sdim// This defines VLASizeChecker, a builtin check in ExprEngine that
11218887Sdim// performs checks for declaration of VLA of undefined or zero size.
12218887Sdim// In addition, VLASizeChecker is responsible for defining the extent
13218887Sdim// of the MemRegion that represents a VLA.
14218887Sdim//
15218887Sdim//===----------------------------------------------------------------------===//
16218887Sdim
17221345Sdim#include "ClangSACheckers.h"
18249423Sdim#include "clang/AST/CharUnits.h"
19249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
20221345Sdim#include "clang/StaticAnalyzer/Core/Checker.h"
21221345Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h"
22221345Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
23249423Sdim#include "llvm/ADT/STLExtras.h"
24234353Sdim#include "llvm/ADT/SmallString.h"
25249423Sdim#include "llvm/Support/raw_ostream.h"
26218887Sdim
27218887Sdimusing namespace clang;
28218887Sdimusing namespace ento;
29218887Sdim
30218887Sdimnamespace {
31221345Sdimclass VLASizeChecker : public Checker< check::PreStmt<DeclStmt> > {
32234353Sdim  mutable OwningPtr<BugType> BT;
33234353Sdim  enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted };
34234353Sdim
35234353Sdim  void reportBug(VLASize_Kind Kind,
36234353Sdim                 const Expr *SizeE,
37234353Sdim                 ProgramStateRef State,
38234353Sdim                 CheckerContext &C) const;
39218887Sdimpublic:
40221345Sdim  void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
41218887Sdim};
42218887Sdim} // end anonymous namespace
43218887Sdim
44234353Sdimvoid VLASizeChecker::reportBug(VLASize_Kind Kind,
45234353Sdim                               const Expr *SizeE,
46234353Sdim                               ProgramStateRef State,
47234353Sdim                               CheckerContext &C) const {
48234353Sdim  // Generate an error node.
49234353Sdim  ExplodedNode *N = C.generateSink(State);
50234353Sdim  if (!N)
51234353Sdim    return;
52234353Sdim
53234353Sdim  if (!BT)
54234353Sdim    BT.reset(new BuiltinBug("Dangerous variable-length array (VLA) declaration"));
55234353Sdim
56234353Sdim  SmallString<256> buf;
57234353Sdim  llvm::raw_svector_ostream os(buf);
58234353Sdim  os << "Declared variable-length array (VLA) ";
59234353Sdim  switch (Kind) {
60234353Sdim  case VLA_Garbage:
61234353Sdim    os << "uses a garbage value as its size";
62234353Sdim    break;
63234353Sdim  case VLA_Zero:
64234353Sdim    os << "has zero size";
65234353Sdim    break;
66234353Sdim  case VLA_Tainted:
67234353Sdim    os << "has tainted size";
68234353Sdim    break;
69234353Sdim  }
70234353Sdim
71234353Sdim  BugReport *report = new BugReport(*BT, os.str(), N);
72234353Sdim  report->addRange(SizeE->getSourceRange());
73243830Sdim  bugreporter::trackNullOrUndefValue(N, SizeE, *report);
74243830Sdim  C.emitReport(report);
75234353Sdim  return;
76234353Sdim}
77234353Sdim
78221345Sdimvoid VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
79218887Sdim  if (!DS->isSingleDecl())
80218887Sdim    return;
81218887Sdim
82218887Sdim  const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
83218887Sdim  if (!VD)
84218887Sdim    return;
85218887Sdim
86218887Sdim  ASTContext &Ctx = C.getASTContext();
87218887Sdim  const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType());
88218887Sdim  if (!VLA)
89218887Sdim    return;
90218887Sdim
91218887Sdim  // FIXME: Handle multi-dimensional VLAs.
92226633Sdim  const Expr *SE = VLA->getSizeExpr();
93234353Sdim  ProgramStateRef state = C.getState();
94234353Sdim  SVal sizeV = state->getSVal(SE, C.getLocationContext());
95218887Sdim
96218887Sdim  if (sizeV.isUndef()) {
97234353Sdim    reportBug(VLA_Garbage, SE, state, C);
98218887Sdim    return;
99218887Sdim  }
100218887Sdim
101218887Sdim  // See if the size value is known. It can't be undefined because we would have
102218887Sdim  // warned about that already.
103218887Sdim  if (sizeV.isUnknown())
104218887Sdim    return;
105218887Sdim
106234353Sdim  // Check if the size is tainted.
107234353Sdim  if (state->isTainted(sizeV)) {
108234353Sdim    reportBug(VLA_Tainted, SE, 0, C);
109234353Sdim    return;
110234353Sdim  }
111234353Sdim
112218887Sdim  // Check if the size is zero.
113249423Sdim  DefinedSVal sizeD = sizeV.castAs<DefinedSVal>();
114218887Sdim
115234353Sdim  ProgramStateRef stateNotZero, stateZero;
116218887Sdim  llvm::tie(stateNotZero, stateZero) = state->assume(sizeD);
117218887Sdim
118218887Sdim  if (stateZero && !stateNotZero) {
119234353Sdim    reportBug(VLA_Zero, SE, stateZero, C);
120218887Sdim    return;
121218887Sdim  }
122218887Sdim
123218887Sdim  // From this point on, assume that the size is not zero.
124218887Sdim  state = stateNotZero;
125218887Sdim
126218887Sdim  // VLASizeChecker is responsible for defining the extent of the array being
127218887Sdim  // declared. We do this by multiplying the array length by the element size,
128218887Sdim  // then matching that with the array region's extent symbol.
129218887Sdim
130218887Sdim  // Convert the array length to size_t.
131218887Sdim  SValBuilder &svalBuilder = C.getSValBuilder();
132218887Sdim  QualType SizeTy = Ctx.getSizeType();
133249423Sdim  NonLoc ArrayLength =
134249423Sdim      svalBuilder.evalCast(sizeD, SizeTy, SE->getType()).castAs<NonLoc>();
135218887Sdim
136218887Sdim  // Get the element size.
137218887Sdim  CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType());
138218887Sdim  SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy);
139218887Sdim
140218887Sdim  // Multiply the array length by the element size.
141249423Sdim  SVal ArraySizeVal = svalBuilder.evalBinOpNN(
142249423Sdim      state, BO_Mul, ArrayLength, EleSizeVal.castAs<NonLoc>(), SizeTy);
143218887Sdim
144218887Sdim  // Finally, assume that the array's extent matches the given size.
145234353Sdim  const LocationContext *LC = C.getLocationContext();
146218887Sdim  DefinedOrUnknownSVal Extent =
147218887Sdim    state->getRegion(VD, LC)->getExtent(svalBuilder);
148249423Sdim  DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs<DefinedOrUnknownSVal>();
149218887Sdim  DefinedOrUnknownSVal sizeIsKnown =
150218887Sdim    svalBuilder.evalEQ(state, Extent, ArraySize);
151218887Sdim  state = state->assume(sizeIsKnown, true);
152218887Sdim
153218887Sdim  // Assume should not fail at this point.
154218887Sdim  assert(state);
155218887Sdim
156218887Sdim  // Remember our assumptions!
157218887Sdim  C.addTransition(state);
158218887Sdim}
159221345Sdim
160221345Sdimvoid ento::registerVLASizeChecker(CheckerManager &mgr) {
161221345Sdim  mgr.registerChecker<VLASizeChecker>();
162221345Sdim}
163