ArrayBoundChecker.cpp revision 018220c343c103b7dfaa117a7a474c7a7fd6d068
158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu//== ArrayBoundChecker.cpp ------------------------------*- C++ -*--==// 258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// 358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// The LLVM Compiler Infrastructure 458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// 558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// This file is distributed under the University of Illinois Open Source 658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// License. See LICENSE.TXT for details. 758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// 858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu//===----------------------------------------------------------------------===// 958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// 1058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// This file defines ArrayBoundChecker, which is a path-sensitive check 1158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// which looks for an out-of-bound array element access. 1258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu// 1358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu//===----------------------------------------------------------------------===// 1458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 1558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu#include "GRExprEngineInternalChecks.h" 165e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer#include "clang/Checker/BugReporter/BugType.h" 171309f9a3b225ea846e5822691c39a77423125505Ted Kremenek#include "clang/Checker/PathSensitive/CheckerVisitor.h" 185e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer#include "clang/Checker/PathSensitive/GRExprEngine.h" 1958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 2058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuusing namespace clang; 2158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 2258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xunamespace { 23ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass ArrayBoundChecker : 2458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu public CheckerVisitor<ArrayBoundChecker> { 2558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu BuiltinBug *BT; 2658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xupublic: 2758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu ArrayBoundChecker() : BT(0) {} 2858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu static void *getTag(); 2958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu void VisitLocation(CheckerContext &C, const Stmt *S, SVal l); 3058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu}; 3158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 3258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 3358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuvoid clang::RegisterArrayBoundChecker(GRExprEngine &Eng) { 3458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu Eng.registerCheck(new ArrayBoundChecker()); 3558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 3658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 3758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuvoid *ArrayBoundChecker::getTag() { 3858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu static int x = 0; return &x; 3958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 4058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuvoid ArrayBoundChecker::VisitLocation(CheckerContext &C, const Stmt *S, SVal l){ 4258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Check for out of bound array element access. 4358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const MemRegion *R = l.getAsRegion(); 4458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!R) 4558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 4658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu R = R->StripCasts(); 4858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const ElementRegion *ER = dyn_cast<ElementRegion>(R); 5058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!ER) 5158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 5258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 5358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Get the index of the accessed element. 5458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu DefinedOrUnknownSVal &Idx = cast<DefinedOrUnknownSVal>(ER->getIndex()); 5558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 5658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const GRState *state = C.getState(); 5758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 5858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Get the size of the array. 59e884ff88baa1bd61db273baf107862a2110058edZhongxing Xu DefinedOrUnknownSVal NumElements 603ed04d37573c566205d965d2e91d54ccae898d0aZhongxing Xu = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(), 61018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu ER->getValueType()); 6258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 6358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const GRState *StInBound = state->AssumeInBound(Idx, NumElements, true); 6458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const GRState *StOutBound = state->AssumeInBound(Idx, NumElements, false); 6558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (StOutBound && !StInBound) { 6619d67b52b73c04ef8eb663980330a1de2b47c845Ted Kremenek ExplodedNode *N = C.GenerateSink(StOutBound); 6758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!N) 6858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 6958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 7058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!BT) 7158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu BT = new BuiltinBug("Out-of-bound array access", 7258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu "Access out-of-bound array element (buffer overflow)"); 7358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 7458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // FIXME: It would be nice to eventually make this diagnostic more clear, 7558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // e.g., by referencing the original declaration or by saying *why* this 7658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // reference is outside the range. 7758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 7858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Generate a report for this bug. 7958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu RangedBugReport *report = 80d02e232c43b979758810794de24d3f5cde40fe93Benjamin Kramer new RangedBugReport(*BT, BT->getDescription(), N); 8158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 8258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu report->addRange(S->getSourceRange()); 8358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu C.EmitReport(report); 84c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek return; 8558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu } 86c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek 87c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek // Array bound check succeeded. From this point forward the array bound 88c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek // should always succeed. 89c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek assert(StInBound); 90c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek C.addTransition(StInBound); 9158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 92