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 { 26a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainarclass ArrayBoundChecker : 27ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis public Checker<check::Location> { 28651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines mutable std::unique_ptr<BuiltinBug> BT; 29651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 3058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xupublic: 31390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks void checkLocation(SVal l, bool isLoad, const Stmt* S, 32390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks CheckerContext &C) const; 3358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu}; 3458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 3558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 36390909c89c98ab1807e15e033a72e975f866fb23Anna Zaksvoid ArrayBoundChecker::checkLocation(SVal l, bool isLoad, const Stmt* LoadS, 378be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis CheckerContext &C) const { 3858e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Check for out of bound array element access. 3958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const MemRegion *R = l.getAsRegion(); 4058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!R) 4158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 4258e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4358e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu const ElementRegion *ER = dyn_cast<ElementRegion>(R); 4458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!ER) 4558e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 4658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 4758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Get the index of the accessed element. 487a95de68c093991047ed8d339479ccad51b88663David Blaikie DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>(); 4958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 50110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu // Zero index is always in bound, this also passes ElementRegions created for 51110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu // pointer casts. 52110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu if (Idx.isZeroConstant()) 53110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu return; 54110eaf156121760073fe6af6b3b0ed09be0cc0ceZhongxing Xu 558bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 5658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 5758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu // Get the size of the array. 58a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar DefinedOrUnknownSVal NumElements 59a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(), 60018220c343c103b7dfaa117a7a474c7a7fd6d068Zhongxing Xu ER->getValueType()); 6158e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 628bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true); 638bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false); 6458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (StOutBound && !StInBound) { 65a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar ExplodedNode *N = C.generateErrorNode(StOutBound); 6658e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!N) 6758e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu return; 68a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar 6958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu if (!BT) 70651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BT.reset(new BuiltinBug( 71651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines this, "Out-of-bound array access", 72651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines "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. 79a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar auto report = llvm::make_unique<BugReport>(*BT, BT->getDescription(), N); 8058e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu 81390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks report->addRange(LoadS->getSourceRange()); 82a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar C.emitReport(std::move(report)); 83c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek return; 8458e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu } 85a4de17562d13d7a8188108243c4cfbd52f33229aPirama Arumuga Nainar 86c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek // Array bound check succeeded. From this point forward the array bound 87c3120769b3b5b3d86fd7bf83fbff8fb60369c213Ted Kremenek // should always succeed. 880bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(StInBound); 8958e689fead1490611bcd114fb707bfc08a12049eZhongxing Xu} 908be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis 918be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidisvoid ento::registerArrayBoundChecker(CheckerManager &mgr) { 928be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis mgr.registerChecker<ArrayBoundChecker>(); 938be5b3aced37e1c7728741c60d47011f11649a58Argyrios Kyrtzidis} 94