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