blob: dccb9a295277cb13e53efa813ec5eda00a8270dd [file] [log] [blame]
Zhongxing Xu58e689f2009-11-11 12:33:27 +00001//== 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 "GRExprEngineInternalChecks.h"
Benjamin Kramer5e2d2c22010-03-27 21:19:47 +000016#include "clang/Checker/BugReporter/BugType.h"
Ted Kremenek1309f9a2010-01-25 04:41:41 +000017#include "clang/Checker/PathSensitive/CheckerVisitor.h"
Benjamin Kramer5e2d2c22010-03-27 21:19:47 +000018#include "clang/Checker/PathSensitive/GRExprEngine.h"
Zhongxing Xu58e689f2009-11-11 12:33:27 +000019
20using namespace clang;
21
22namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000023class ArrayBoundChecker :
Zhongxing Xu58e689f2009-11-11 12:33:27 +000024 public CheckerVisitor<ArrayBoundChecker> {
25 BuiltinBug *BT;
26public:
27 ArrayBoundChecker() : BT(0) {}
28 static void *getTag();
29 void VisitLocation(CheckerContext &C, const Stmt *S, SVal l);
30};
31}
32
33void clang::RegisterArrayBoundChecker(GRExprEngine &Eng) {
34 Eng.registerCheck(new ArrayBoundChecker());
35}
36
37void *ArrayBoundChecker::getTag() {
38 static int x = 0; return &x;
39}
40
41void ArrayBoundChecker::VisitLocation(CheckerContext &C, const Stmt *S, SVal l){
42 // Check for out of bound array element access.
43 const MemRegion *R = l.getAsRegion();
44 if (!R)
45 return;
46
Zhongxing Xu58e689f2009-11-11 12:33:27 +000047 const ElementRegion *ER = dyn_cast<ElementRegion>(R);
48 if (!ER)
49 return;
50
51 // Get the index of the accessed element.
Gabor Greif89b06582010-09-09 10:51:37 +000052 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
Zhongxing Xu58e689f2009-11-11 12:33:27 +000053
Zhongxing Xu110eaf12010-11-26 09:14:07 +000054 // Zero index is always in bound, this also passes ElementRegions created for
55 // pointer casts.
56 if (Idx.isZeroConstant())
57 return;
58
Zhongxing Xu58e689f2009-11-11 12:33:27 +000059 const GRState *state = C.getState();
60
61 // Get the size of the array.
Zhongxing Xue884ff82009-11-12 02:48:32 +000062 DefinedOrUnknownSVal NumElements
Zhongxing Xu3ed04d32010-01-18 08:54:31 +000063 = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(),
Zhongxing Xu018220c2010-08-11 06:10:55 +000064 ER->getValueType());
Zhongxing Xu58e689f2009-11-11 12:33:27 +000065
66 const GRState *StInBound = state->AssumeInBound(Idx, NumElements, true);
67 const GRState *StOutBound = state->AssumeInBound(Idx, NumElements, false);
68 if (StOutBound && !StInBound) {
Ted Kremenek19d67b52009-11-23 22:22:01 +000069 ExplodedNode *N = C.GenerateSink(StOutBound);
Zhongxing Xu58e689f2009-11-11 12:33:27 +000070 if (!N)
71 return;
72
73 if (!BT)
74 BT = new BuiltinBug("Out-of-bound array access",
75 "Access out-of-bound array element (buffer overflow)");
76
77 // FIXME: It would be nice to eventually make this diagnostic more clear,
78 // e.g., by referencing the original declaration or by saying *why* this
79 // reference is outside the range.
80
81 // Generate a report for this bug.
82 RangedBugReport *report =
Benjamin Kramerd02e2322009-11-14 12:08:24 +000083 new RangedBugReport(*BT, BT->getDescription(), N);
Zhongxing Xu58e689f2009-11-11 12:33:27 +000084
85 report->addRange(S->getSourceRange());
Zhongxing Xu58e689f2009-11-11 12:33:27 +000086 C.EmitReport(report);
Ted Kremenekc3120762009-11-23 23:23:26 +000087 return;
Zhongxing Xu58e689f2009-11-11 12:33:27 +000088 }
Ted Kremenekc3120762009-11-23 23:23:26 +000089
90 // Array bound check succeeded. From this point forward the array bound
91 // should always succeed.
92 assert(StInBound);
93 C.addTransition(StInBound);
Zhongxing Xu58e689f2009-11-11 12:33:27 +000094}