1af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks//== ObjCContainersChecker.cpp - Path sensitive checker for CFArray *- C++ -*=// 2af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// 3af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// The LLVM Compiler Infrastructure 4af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// 5af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// This file is distributed under the University of Illinois Open Source 6af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// License. See LICENSE.TXT for details. 7af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// 8af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks//===----------------------------------------------------------------------===// 9af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// 10af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// Performs path sensitive checks of Core Foundation static containers like 11af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// CFArray. 12af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// 1) Check for buffer overflows: 13af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// In CFArrayGetArrayAtIndex( myArray, index), if the index is outside the 14af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// index space of theArray (0 to N-1 inclusive (where N is the count of 15af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// theArray), the behavior is undefined. 16af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks// 17af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks//===----------------------------------------------------------------------===// 18af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 19af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks#include "ClangSACheckers.h" 2055fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/AST/ParentMap.h" 2155fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 22af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks#include "clang/StaticAnalyzer/Core/Checker.h" 23af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks#include "clang/StaticAnalyzer/Core/CheckerManager.h" 24af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 25af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 26af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 27af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksusing namespace clang; 28af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksusing namespace ento; 29af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 30af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksnamespace { 31af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksclass ObjCContainersChecker : public Checker< check::PreStmt<CallExpr>, 32b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar check::PostStmt<CallExpr>, 33b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar check::PointerEscape> { 34651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines mutable std::unique_ptr<BugType> BT; 35af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks inline void initBugType() const { 36af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (!BT) 37651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BT.reset(new BugType(this, "CFArray API", 386fd4505ad67a186da8cc26fdb493c93fe4937555Ted Kremenek categories::CoreFoundationObjectiveC)); 39af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks } 40af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 41af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks inline SymbolRef getArraySym(const Expr *E, CheckerContext &C) const { 42af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks SVal ArrayRef = C.getState()->getSVal(E, C.getLocationContext()); 43af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks SymbolRef ArraySym = ArrayRef.getAsSymbol(); 44af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return ArraySym; 45af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks } 46af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 47af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks void addSizeInfo(const Expr *Array, const Expr *Size, 48af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks CheckerContext &C) const; 49af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 50af5f550de34525b27f0ff31dafce792caf8158b6Anna Zakspublic: 51af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks /// A tag to id this checker. 52af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks static void *getTag() { static int Tag; return &Tag; } 53af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 54af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 55af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks void checkPreStmt(const CallExpr *CE, CheckerContext &C) const; 56b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar ProgramStateRef checkPointerEscape(ProgramStateRef State, 57b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar const InvalidatedSymbols &Escaped, 58b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar const CallEvent *Call, 59b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar PointerEscapeKind Kind) const; 60af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks}; 61af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks} // end anonymous namespace 62af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 63166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// ProgramState trait - a map from array symbol to its state. 64166d502d5367ceacd1313a33cac43b1048b8524dJordan RoseREGISTER_MAP_WITH_PROGRAMSTATE(ArraySizeMap, SymbolRef, DefinedSVal) 65af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 66af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksvoid ObjCContainersChecker::addSizeInfo(const Expr *Array, const Expr *Size, 67af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks CheckerContext &C) const { 68be4dc941030988c71e41303fc9116e0dc099b516Ted Kremenek ProgramStateRef State = C.getState(); 69af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks SVal SizeV = State->getSVal(Size, C.getLocationContext()); 70af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Undefined is reported by another checker. 71af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (SizeV.isUnknownOrUndef()) 72af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 73af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 74af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Get the ArrayRef symbol. 75af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks SVal ArrayRef = State->getSVal(Array, C.getLocationContext()); 76af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks SymbolRef ArraySym = ArrayRef.getAsSymbol(); 77af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (!ArraySym) 78af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 79af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 805251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie C.addTransition( 815251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie State->set<ArraySizeMap>(ArraySym, SizeV.castAs<DefinedSVal>())); 82af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks} 83af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 84af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksvoid ObjCContainersChecker::checkPostStmt(const CallExpr *CE, 85af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks CheckerContext &C) const { 86af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks StringRef Name = C.getCalleeName(CE); 87e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks if (Name.empty() || CE->getNumArgs() < 1) 88af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 89af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 90af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Add array size information to the state. 91af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (Name.equals("CFArrayCreate")) { 92e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks if (CE->getNumArgs() < 3) 93e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks return; 94af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Note, we can visit the Create method in the post-visit because 95af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // the CFIndex parameter is passed in by value and will not be invalidated 96af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // by the call. 97af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks addSizeInfo(CE, CE->getArg(2), C); 98af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 99af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks } 100af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 101af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (Name.equals("CFArrayGetCount")) { 102af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks addSizeInfo(CE->getArg(0), CE, C); 103af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 104af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks } 105af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks} 106af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 107af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksvoid ObjCContainersChecker::checkPreStmt(const CallExpr *CE, 108af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks CheckerContext &C) const { 109af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks StringRef Name = C.getCalleeName(CE); 110e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks if (Name.empty() || CE->getNumArgs() < 2) 111af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 112af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 113af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Check the array access. 114af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (Name.equals("CFArrayGetValueAtIndex")) { 115be4dc941030988c71e41303fc9116e0dc099b516Ted Kremenek ProgramStateRef State = C.getState(); 116af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Retrieve the size. 117b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // Find out if we saw this array symbol before and have information about 118b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // it. 119af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks const Expr *ArrayExpr = CE->getArg(0); 12004a18c9f42e91db1b2d2c7483723c1cd321c3d39Ted Kremenek SymbolRef ArraySym = getArraySym(ArrayExpr, C); 12104a18c9f42e91db1b2d2c7483723c1cd321c3d39Ted Kremenek if (!ArraySym) 12204a18c9f42e91db1b2d2c7483723c1cd321c3d39Ted Kremenek return; 12304a18c9f42e91db1b2d2c7483723c1cd321c3d39Ted Kremenek 12404a18c9f42e91db1b2d2c7483723c1cd321c3d39Ted Kremenek const DefinedSVal *Size = State->get<ArraySizeMap>(ArraySym); 12504a18c9f42e91db1b2d2c7483723c1cd321c3d39Ted Kremenek 126e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks if (!Size) 127af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 128af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 129af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Get the index. 130af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks const Expr *IdxExpr = CE->getArg(1); 131af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks SVal IdxVal = State->getSVal(IdxExpr, C.getLocationContext()); 132e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks if (IdxVal.isUnknownOrUndef()) 133e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks return; 1345251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie DefinedSVal Idx = IdxVal.castAs<DefinedSVal>(); 13587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 136af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks // Now, check if 'Idx in [0, Size-1]'. 137af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks const QualType T = IdxExpr->getType(); 138e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks ProgramStateRef StInBound = State->assumeInBound(Idx, *Size, true, T); 139e59ec3dfe17c1ceb648861b621a3890a9a56ab0cAnna Zaks ProgramStateRef StOutBound = State->assumeInBound(Idx, *Size, false, T); 140af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (StOutBound && !StInBound) { 14187d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar ExplodedNode *N = C.generateErrorNode(StOutBound); 142af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (!N) 143af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 144af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks initBugType(); 14587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar auto R = llvm::make_unique<BugReport>(*BT, "Index is out of bounds", N); 146af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks R->addRange(IdxExpr->getSourceRange()); 14787d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar C.emitReport(std::move(R)); 148af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks return; 149af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks } 150af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks } 151af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks} 152af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks 153b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga NainarProgramStateRef 154b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga NainarObjCContainersChecker::checkPointerEscape(ProgramStateRef State, 155b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar const InvalidatedSymbols &Escaped, 156b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar const CallEvent *Call, 157b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar PointerEscapeKind Kind) const { 1584967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar for (const auto &Sym : Escaped) { 159b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // When a symbol for a mutable array escapes, we can't reason precisely 160b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // about its size any more -- so remove it from the map. 161b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // Note that we aren't notified here when a CFMutableArrayRef escapes as a 162b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // CFArrayRef. This is because CFArrayRef is typedef'd as a pointer to a 163b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar // const-qualified type. 164b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar State = State->remove<ArraySizeMap>(Sym); 165b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar } 166b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar return State; 167b6d6993e6e6d3daf4d9876794254d20a134e37c2Pirama Arumuga Nainar} 1684967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar 169af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks/// Register checker. 170af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaksvoid ento::registerObjCContainersChecker(CheckerManager &mgr) { 171af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks mgr.registerChecker<ObjCContainersChecker>(); 172af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks} 173