ArrayBoundCheckerV2.cpp revision 04291a7c76e16a2dc5433c80c3d13c826bf372dc 
1//== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines ArrayBoundCheckerV2, which is a path-sensitive check
11// which looks for an out-of-bound array element access.
12//
13//===----------------------------------------------------------------------===//
14
15#include "InternalChecks.h"
16#include "clang/StaticAnalyzer/BugReporter/BugType.h"
17#include "clang/StaticAnalyzer/PathSensitive/CheckerVisitor.h"
18#include "clang/StaticAnalyzer/PathSensitive/ExprEngine.h"
19#include "clang/AST/CharUnits.h"
20
21using namespace clang;
22using namespace ento;
23
24namespace {
25class ArrayBoundCheckerV2 :
26    public CheckerVisitor<ArrayBoundCheckerV2> {
27  BuiltinBug *BT;
28
29  enum OOB_Kind { OOB_Precedes, OOB_Excedes };
30
31  void reportOOB(CheckerContext &C, const GRState *errorState,
32                 OOB_Kind kind);
33
34public:
35  ArrayBoundCheckerV2() : BT(0) {}
36  static void *getTag() { static int x = 0; return &x; }
37  void visitLocation(CheckerContext &C, const Stmt *S, SVal l, bool isLoad);
38};
39
40// FIXME: Eventually replace RegionRawOffset with this class.
41class RegionRawOffsetV2 {
42private:
43  const SubRegion *baseRegion;
44  SVal byteOffset;
45
46  RegionRawOffsetV2()
47    : baseRegion(0), byteOffset(UnknownVal()) {}
48
49public:
50  RegionRawOffsetV2(const SubRegion* base, SVal offset)
51    : baseRegion(base), byteOffset(offset) {}
52
53  NonLoc getByteOffset() const { return cast<NonLoc>(byteOffset); }
54  const SubRegion *getRegion() const { return baseRegion; }
55
56  static RegionRawOffsetV2 computeOffset(const GRState *state,
57                                         SValBuilder &svalBuilder,
58                                         SVal location);
59
60  void dump() const;
61  void dumpToStream(llvm::raw_ostream& os) const;
62};
63}
64
65void ento::RegisterArrayBoundCheckerV2(ExprEngine &Eng) {
66  Eng.registerCheck(new ArrayBoundCheckerV2());
67}
68
69void ArrayBoundCheckerV2::visitLocation(CheckerContext &checkerContext,
70                                        const Stmt *S,
71                                        SVal location, bool isLoad) {
72
73  // NOTE: Instead of using GRState::assumeInBound(), we are prototyping
74  // some new logic here that reasons directly about memory region extents.
75  // Once that logic is more mature, we can bring it back to assumeInBound()
76  // for all clients to use.
77  //
78  // The algorithm we are using here for bounds checking is to see if the
79  // memory access is within the extent of the base region.  Since we
80  // have some flexibility in defining the base region, we can achieve
81  // various levels of conservatism in our buffer overflow checking.
82  const GRState *state = checkerContext.getState();
83  const GRState *originalState = state;
84
85  SValBuilder &svalBuilder = checkerContext.getSValBuilder();
86  const RegionRawOffsetV2 &rawOffset =
87    RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
88
89  if (!rawOffset.getRegion())
90    return;
91
92  // CHECK LOWER BOUND: Is byteOffset < 0?  If so, we are doing a load/store
93  //  before the first valid offset in the memory region.
94
95  SVal lowerBound
96    = svalBuilder.evalBinOpNN(state, BO_LT, rawOffset.getByteOffset(),
97                              svalBuilder.makeZeroArrayIndex(),
98                              svalBuilder.getConditionType());
99
100  NonLoc *lowerBoundToCheck = dyn_cast<NonLoc>(&lowerBound);
101  if (!lowerBoundToCheck)
102    return;
103
104  const GRState *state_precedesLowerBound, *state_withinLowerBound;
105  llvm::tie(state_precedesLowerBound, state_withinLowerBound) =
106      state->assume(*lowerBoundToCheck);
107
108  // Are we constrained enough to definitely precede the lower bound?
109  if (state_precedesLowerBound && !state_withinLowerBound) {
110    reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes);
111    return;
112  }
113
114  // Otherwise, assume the constraint of the lower bound.
115  assert(state_withinLowerBound);
116  state = state_withinLowerBound;
117
118  do {
119    // CHECK UPPER BOUND: Is byteOffset >= extent(baseRegion)?  If so,
120    // we are doing a load/store after the last valid offset.
121    DefinedOrUnknownSVal extentVal =
122      rawOffset.getRegion()->getExtent(svalBuilder);
123    if (!isa<NonLoc>(extentVal))
124      break;
125
126    SVal upperbound
127      = svalBuilder.evalBinOpNN(state, BO_GE, rawOffset.getByteOffset(),
128                                cast<NonLoc>(extentVal),
129                                svalBuilder.getConditionType());
130
131    NonLoc *upperboundToCheck = dyn_cast<NonLoc>(&upperbound);
132    if (!upperboundToCheck)
133      break;
134
135    const GRState *state_exceedsUpperBound, *state_withinUpperBound;
136    llvm::tie(state_exceedsUpperBound, state_withinUpperBound) =
137      state->assume(*upperboundToCheck);
138
139    // Are we constrained enough to definitely exceed the upper bound?
140    if (state_exceedsUpperBound && !state_withinUpperBound) {
141      reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes);
142      return;
143    }
144
145    assert(state_withinUpperBound);
146    state = state_withinUpperBound;
147  }
148  while (false);
149
150  if (state != originalState)
151    checkerContext.generateNode(state);
152}
153
154void ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext,
155                                    const GRState *errorState,
156                                    OOB_Kind kind) {
157
158  ExplodedNode *errorNode = checkerContext.generateSink(errorState);
159  if (!errorNode)
160    return;
161
162  if (!BT)
163    BT = new BuiltinBug("Out-of-bound access");
164
165  // FIXME: This diagnostics are preliminary.  We should get far better
166  // diagnostics for explaining buffer overruns.
167
168  llvm::SmallString<256> buf;
169  llvm::raw_svector_ostream os(buf);
170  os << "Out of bound memory access "
171     << (kind == OOB_Precedes ? "(accessed memory precedes memory block)"
172                              : "(access exceeds upper limit of memory block)");
173
174  checkerContext.EmitReport(new RangedBugReport(*BT, os.str(), errorNode));
175}
176
177void RegionRawOffsetV2::dump() const {
178  dumpToStream(llvm::errs());
179}
180
181void RegionRawOffsetV2::dumpToStream(llvm::raw_ostream& os) const {
182  os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}';
183}
184
185// FIXME: Merge with the implementation of the same method in Store.cpp
186static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
187  if (const RecordType *RT = Ty->getAs<RecordType>()) {
188    const RecordDecl *D = RT->getDecl();
189    if (!D->getDefinition())
190      return false;
191  }
192
193  return true;
194}
195
196
197// Lazily computes a value to be used by 'computeOffset'.  If 'val'
198// is unknown or undefined, we lazily substitute '0'.  Otherwise,
199// return 'val'.
200static inline SVal getValue(SVal val, SValBuilder &svalBuilder) {
201  return isa<UndefinedVal>(val) ? svalBuilder.makeArrayIndex(0) : val;
202}
203
204// Scale a base value by a scaling factor, and return the scaled
205// value as an SVal.  Used by 'computeOffset'.
206static inline SVal scaleValue(const GRState *state,
207                              NonLoc baseVal, CharUnits scaling,
208                              SValBuilder &sb) {
209  return sb.evalBinOpNN(state, BO_Mul, baseVal,
210                        sb.makeArrayIndex(scaling.getQuantity()),
211                        sb.getArrayIndexType());
212}
213
214// Add an SVal to another, treating unknown and undefined values as
215// summing to UnknownVal.  Used by 'computeOffset'.
216static SVal addValue(const GRState *state, SVal x, SVal y,
217                     SValBuilder &svalBuilder) {
218  // We treat UnknownVals and UndefinedVals the same here because we
219  // only care about computing offsets.
220  if (x.isUnknownOrUndef() || y.isUnknownOrUndef())
221    return UnknownVal();
222
223  return svalBuilder.evalBinOpNN(state, BO_Add,
224                                 cast<NonLoc>(x), cast<NonLoc>(y),
225                                 svalBuilder.getArrayIndexType());
226}
227
228/// Compute a raw byte offset from a base region.  Used for array bounds
229/// checking.
230RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(const GRState *state,
231                                                   SValBuilder &svalBuilder,
232                                                   SVal location)
233{
234  const MemRegion *region = location.getAsRegion();
235  SVal offset = UndefinedVal();
236
237  while (region) {
238    switch (region->getKind()) {
239      default: {
240        if (const SubRegion *subReg = dyn_cast<SubRegion>(region))
241          if (!offset.isUnknownOrUndef())
242            return RegionRawOffsetV2(subReg, offset);
243        return RegionRawOffsetV2();
244      }
245      case MemRegion::ElementRegionKind: {
246        const ElementRegion *elemReg = cast<ElementRegion>(region);
247        SVal index = elemReg->getIndex();
248        if (!isa<NonLoc>(index))
249          return RegionRawOffsetV2();
250        QualType elemType = elemReg->getElementType();
251        // If the element is an incomplete type, go no further.
252        ASTContext &astContext = svalBuilder.getContext();
253        if (!IsCompleteType(astContext, elemType))
254          return RegionRawOffsetV2();
255
256        // Update the offset.
257        offset = addValue(state,
258                          getValue(offset, svalBuilder),
259                          scaleValue(state,
260                                     cast<NonLoc>(index),
261                                     astContext.getTypeSizeInChars(elemType),
262                                     svalBuilder),
263                          svalBuilder);
264
265        if (offset.isUnknownOrUndef())
266          return RegionRawOffsetV2();
267
268        region = elemReg->getSuperRegion();
269        continue;
270      }
271    }
272  }
273  return RegionRawOffsetV2();
274}
275
276
277
278