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, bool isLoad);
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                                       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