ArrayBoundChecker.cpp revision 04291a7c76e16a2dc5433c80c3d13c826bf372dc 
1//== ArrayBoundChecker.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 ArrayBoundChecker, 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
20using namespace clang;
21using namespace ento;
22
23namespace {
24class ArrayBoundChecker :
25    public CheckerVisitor<ArrayBoundChecker> {
26  BuiltinBug *BT;
27public:
28  ArrayBoundChecker() : BT(0) {}
29  static void *getTag() { static int x = 0; return &x; }
30  void visitLocation(CheckerContext &C, const Stmt *S, SVal l, bool isLoad);
31};
32}
33
34void ento::RegisterArrayBoundChecker(ExprEngine &Eng) {
35  Eng.registerCheck(new ArrayBoundChecker());
36}
37
38void ArrayBoundChecker::visitLocation(CheckerContext &C, const Stmt *S, SVal l,
39                                      bool isLoad) {
40  // Check for out of bound array element access.
41  const MemRegion *R = l.getAsRegion();
42  if (!R)
43    return;
44
45  const ElementRegion *ER = dyn_cast<ElementRegion>(R);
46  if (!ER)
47    return;
48
49  // Get the index of the accessed element.
50  DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
51
52  // Zero index is always in bound, this also passes ElementRegions created for
53  // pointer casts.
54  if (Idx.isZeroConstant())
55    return;
56
57  const GRState *state = C.getState();
58
59  // Get the size of the array.
60  DefinedOrUnknownSVal NumElements
61    = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(),
62                                            ER->getValueType());
63
64  const GRState *StInBound = state->assumeInBound(Idx, NumElements, true);
65  const GRState *StOutBound = state->assumeInBound(Idx, NumElements, false);
66  if (StOutBound && !StInBound) {
67    ExplodedNode *N = C.generateSink(StOutBound);
68    if (!N)
69      return;
70
71    if (!BT)
72      BT = new BuiltinBug("Out-of-bound array access",
73                       "Access out-of-bound array element (buffer overflow)");
74
75    // FIXME: It would be nice to eventually make this diagnostic more clear,
76    // e.g., by referencing the original declaration or by saying *why* this
77    // reference is outside the range.
78
79    // Generate a report for this bug.
80    RangedBugReport *report =
81      new RangedBugReport(*BT, BT->getDescription(), N);
82
83    report->addRange(S->getSourceRange());
84    C.EmitReport(report);
85    return;
86  }
87
88  // Array bound check succeeded.  From this point forward the array bound
89  // should always succeed.
90  assert(StInBound);
91  C.addTransition(StInBound);
92}
93