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 158be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis#include "ClangSACheckers.h" 1655fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 188be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 198be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 209b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 2158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 2258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xuusing namespace clang; 239ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 2458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 2558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xunamespace { 26ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass ArrayBoundChecker : 27ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis public Checker<check::Location> { 286f42b62b6194f53bcbc349f5d17388e1936535d7Dylan Noblesmith mutable OwningPtr<BuiltinBug> BT; 2958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xupublic: 30390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks void checkLocation(SVal l, bool isLoad, const Stmt* S, 31390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks CheckerContext &C) const; 3258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu}; 3358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 3458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 35390909c89c98ab1807e15e033a72e975f866fb23Anna Zaksvoid ArrayBoundChecker::checkLocation(SVal l, bool isLoad, const Stmt* LoadS, 368be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis CheckerContext &C) const { 3758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Check for out of bound array element access. 3858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const MemRegion *R = l.getAsRegion(); 3958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!R) 4058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 4158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const ElementRegion *ER = dyn_cast<ElementRegion>(R); 4358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!ER) 4458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 4558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Get the index of the accessed element. 477a95de68c093991047ed8d339479ccad51b88663David Blaikie DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>(); 4858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 49110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu // Zero index is always in bound, this also passes ElementRegions created for 50110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu // pointer casts. 51110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu if (Idx.isZeroConstant()) 52110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu return; 53110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu 548bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 5558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 5658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Get the size of the array. 57e884ff88baa1bd61db273baf107862a2110058edZhongxing Xu DefinedOrUnknownSVal NumElements 583ed04d37573c566205d965d2e91d54ccae898d0aZhongxing Xu = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(), 59018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu ER->getValueType()); 6058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 618bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true); 628bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false); 6358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (StOutBound && !StInBound) { 64d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek ExplodedNode *N = C.generateSink(StOutBound); 6558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!N) 6658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 6758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 6858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!BT) 698be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis BT.reset(new BuiltinBug("Out-of-bound array access", 708be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis "Access out-of-bound array element (buffer overflow)")); 7158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 7258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // FIXME: It would be nice to eventually make this diagnostic more clear, 7358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // e.g., by referencing the original declaration or by saying *why* this 7458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // reference is outside the range. 7558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 7658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Generate a report for this bug. 77e172e8b9e7fc67d7d03589af7e92fe777afcf33aAnna Zaks BugReport *report = 78e172e8b9e7fc67d7d03589af7e92fe777afcf33aAnna Zaks new BugReport(*BT, BT->getDescription(), N); 7958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 80390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks report->addRange(LoadS->getSourceRange()); 81785950e59424dca7ce0081bebf13c0acd2c4fff6Jordan Rose C.emitReport(report); 82c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek return; 8358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu } 84c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek 85c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek // Array bound check succeeded. From this point forward the array bound 86c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek // should always succeed. 870bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(StInBound); 8858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 898be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis 908be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidisvoid ento::registerArrayBoundChecker(CheckerManager &mgr) { 918be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis mgr.registerChecker<ArrayBoundChecker>(); 928be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis} 93