ArrayBoundChecker.cpp revision e884ff88baa1bd61db273baf107862a2110058ed
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" 1658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu#include "clang/Analysis/PathSensitive/GRExprEngine.h" 1758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu#include "clang/Analysis/PathSensitive/BugReporter.h" 1858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu#include "clang/Analysis/PathSensitive/CheckerVisitor.h" 1958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 2058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuusing namespace clang; 2158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 2258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xunamespace { 2358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuclass VISIBILITY_HIDDEN 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 60e884ff88baa1bd61db273baf107862a2110058edZhongxing Xu = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion()); 6158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 6258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const GRState *StInBound = state->AssumeInBound(Idx, NumElements, true); 6358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const GRState *StOutBound = state->AssumeInBound(Idx, NumElements, false); 6458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (StOutBound && !StInBound) { 6558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu ExplodedNode *N = C.GenerateNode(S, StOutBound, true); 6658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 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 = 8058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu new RangedBugReport(*BT, BT->getDescription().c_str(), N); 8158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 8258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu report->addRange(S->getSourceRange()); 8358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 8458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu C.EmitReport(report); 8558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu } 8658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 87