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