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