1226586Sdim// MallocOverflowSecurityChecker.cpp - Check for malloc overflows -*- C++ -*-=// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This checker detects a common memory allocation security flaw. 11226586Sdim// Suppose 'unsigned int n' comes from an untrusted source. If the 12226586Sdim// code looks like 'malloc (n * 4)', and an attacker can make 'n' be 13226586Sdim// say MAX_UINT/4+2, then instead of allocating the correct 'n' 4-byte 14226586Sdim// elements, this will actually allocate only two because of overflow. 15226586Sdim// Then when the rest of the program attempts to store values past the 16226586Sdim// second element, these values will actually overwrite other items in 17226586Sdim// the heap, probably allowing the attacker to execute arbitrary code. 18226586Sdim// 19226586Sdim//===----------------------------------------------------------------------===// 20226586Sdim 21226586Sdim#include "ClangSACheckers.h" 22226586Sdim#include "clang/AST/EvaluatedExprVisitor.h" 23252723Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 24252723Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 25226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 26226586Sdim#include "llvm/ADT/SmallVector.h" 27226586Sdim 28226586Sdimusing namespace clang; 29226586Sdimusing namespace ento; 30226586Sdim 31226586Sdimnamespace { 32226586Sdimstruct MallocOverflowCheck { 33226586Sdim const BinaryOperator *mulop; 34226586Sdim const Expr *variable; 35226586Sdim 36226586Sdim MallocOverflowCheck (const BinaryOperator *m, const Expr *v) 37226586Sdim : mulop(m), variable (v) 38226586Sdim {} 39226586Sdim}; 40226586Sdim 41226586Sdimclass MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> { 42226586Sdimpublic: 43226586Sdim void checkASTCodeBody(const Decl *D, AnalysisManager &mgr, 44226586Sdim BugReporter &BR) const; 45226586Sdim 46226586Sdim void CheckMallocArgument( 47252723Sdim SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, 48226586Sdim const Expr *TheArgument, ASTContext &Context) const; 49226586Sdim 50226586Sdim void OutputPossibleOverflows( 51252723Sdim SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, 52226586Sdim const Decl *D, BugReporter &BR, AnalysisManager &mgr) const; 53226586Sdim 54226586Sdim}; 55226586Sdim} // end anonymous namespace 56226586Sdim 57226586Sdimvoid MallocOverflowSecurityChecker::CheckMallocArgument( 58252723Sdim SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, 59226586Sdim const Expr *TheArgument, 60226586Sdim ASTContext &Context) const { 61226586Sdim 62226586Sdim /* Look for a linear combination with a single variable, and at least 63226586Sdim one multiplication. 64226586Sdim Reject anything that applies to the variable: an explicit cast, 65226586Sdim conditional expression, an operation that could reduce the range 66226586Sdim of the result, or anything too complicated :-). */ 67226586Sdim const Expr * e = TheArgument; 68226586Sdim const BinaryOperator * mulop = NULL; 69226586Sdim 70226586Sdim for (;;) { 71226586Sdim e = e->IgnoreParenImpCasts(); 72226586Sdim if (isa<BinaryOperator>(e)) { 73226586Sdim const BinaryOperator * binop = dyn_cast<BinaryOperator>(e); 74226586Sdim BinaryOperatorKind opc = binop->getOpcode(); 75226586Sdim // TODO: ignore multiplications by 1, reject if multiplied by 0. 76226586Sdim if (mulop == NULL && opc == BO_Mul) 77226586Sdim mulop = binop; 78226586Sdim if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl) 79226586Sdim return; 80226586Sdim 81226586Sdim const Expr *lhs = binop->getLHS(); 82226586Sdim const Expr *rhs = binop->getRHS(); 83226586Sdim if (rhs->isEvaluatable(Context)) 84226586Sdim e = lhs; 85226586Sdim else if ((opc == BO_Add || opc == BO_Mul) 86226586Sdim && lhs->isEvaluatable(Context)) 87226586Sdim e = rhs; 88226586Sdim else 89226586Sdim return; 90226586Sdim } 91226586Sdim else if (isa<DeclRefExpr>(e) || isa<MemberExpr>(e)) 92226586Sdim break; 93226586Sdim else 94226586Sdim return; 95226586Sdim } 96226586Sdim 97226586Sdim if (mulop == NULL) 98226586Sdim return; 99226586Sdim 100226586Sdim // We've found the right structure of malloc argument, now save 101226586Sdim // the data so when the body of the function is completely available 102226586Sdim // we can check for comparisons. 103226586Sdim 104226586Sdim // TODO: Could push this into the innermost scope where 'e' is 105226586Sdim // defined, rather than the whole function. 106226586Sdim PossibleMallocOverflows.push_back(MallocOverflowCheck(mulop, e)); 107226586Sdim} 108226586Sdim 109226586Sdimnamespace { 110226586Sdim// A worker class for OutputPossibleOverflows. 111226586Sdimclass CheckOverflowOps : 112226586Sdim public EvaluatedExprVisitor<CheckOverflowOps> { 113226586Sdimpublic: 114252723Sdim typedef SmallVectorImpl<MallocOverflowCheck> theVecType; 115226586Sdim 116226586Sdimprivate: 117226586Sdim theVecType &toScanFor; 118226586Sdim ASTContext &Context; 119226586Sdim 120226586Sdim bool isIntZeroExpr(const Expr *E) const { 121226586Sdim if (!E->getType()->isIntegralOrEnumerationType()) 122226586Sdim return false; 123226586Sdim llvm::APSInt Result; 124226586Sdim if (E->EvaluateAsInt(Result, Context)) 125226586Sdim return Result == 0; 126226586Sdim return false; 127226586Sdim } 128226586Sdim 129226586Sdim void CheckExpr(const Expr *E_p) { 130226586Sdim const Expr *E = E_p->IgnoreParenImpCasts(); 131226586Sdim 132226586Sdim theVecType::iterator i = toScanFor.end(); 133226586Sdim theVecType::iterator e = toScanFor.begin(); 134226586Sdim 135226586Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) { 136226586Sdim const Decl * EdreD = DR->getDecl(); 137226586Sdim while (i != e) { 138226586Sdim --i; 139226586Sdim if (const DeclRefExpr *DR_i = dyn_cast<DeclRefExpr>(i->variable)) { 140226586Sdim if (DR_i->getDecl() == EdreD) 141226586Sdim i = toScanFor.erase(i); 142226586Sdim } 143226586Sdim } 144226586Sdim } 145226586Sdim else if (isa<MemberExpr>(E)) { 146226586Sdim // No points-to analysis, just look at the member 147226586Sdim const Decl * EmeMD = dyn_cast<MemberExpr>(E)->getMemberDecl(); 148226586Sdim while (i != e) { 149226586Sdim --i; 150226586Sdim if (isa<MemberExpr>(i->variable)) { 151226586Sdim if (dyn_cast<MemberExpr>(i->variable)->getMemberDecl() == EmeMD) 152226586Sdim i = toScanFor.erase (i); 153226586Sdim } 154226586Sdim } 155226586Sdim } 156226586Sdim } 157226586Sdim 158226586Sdim public: 159226586Sdim void VisitBinaryOperator(BinaryOperator *E) { 160226586Sdim if (E->isComparisonOp()) { 161226586Sdim const Expr * lhs = E->getLHS(); 162226586Sdim const Expr * rhs = E->getRHS(); 163226586Sdim // Ignore comparisons against zero, since they generally don't 164226586Sdim // protect against an overflow. 165226586Sdim if (!isIntZeroExpr(lhs) && ! isIntZeroExpr(rhs)) { 166226586Sdim CheckExpr(lhs); 167226586Sdim CheckExpr(rhs); 168226586Sdim } 169226586Sdim } 170226586Sdim EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E); 171226586Sdim } 172226586Sdim 173226586Sdim /* We specifically ignore loop conditions, because they're typically 174226586Sdim not error checks. */ 175226586Sdim void VisitWhileStmt(WhileStmt *S) { 176226586Sdim return this->Visit(S->getBody()); 177226586Sdim } 178226586Sdim void VisitForStmt(ForStmt *S) { 179226586Sdim return this->Visit(S->getBody()); 180226586Sdim } 181226586Sdim void VisitDoStmt(DoStmt *S) { 182226586Sdim return this->Visit(S->getBody()); 183226586Sdim } 184226586Sdim 185226586Sdim CheckOverflowOps(theVecType &v, ASTContext &ctx) 186226586Sdim : EvaluatedExprVisitor<CheckOverflowOps>(ctx), 187226586Sdim toScanFor(v), Context(ctx) 188226586Sdim { } 189226586Sdim }; 190226586Sdim} 191226586Sdim 192226586Sdim// OutputPossibleOverflows - We've found a possible overflow earlier, 193226586Sdim// now check whether Body might contain a comparison which might be 194226586Sdim// preventing the overflow. 195226586Sdim// This doesn't do flow analysis, range analysis, or points-to analysis; it's 196226586Sdim// just a dumb "is there a comparison" scan. The aim here is to 197226586Sdim// detect the most blatent cases of overflow and educate the 198226586Sdim// programmer. 199226586Sdimvoid MallocOverflowSecurityChecker::OutputPossibleOverflows( 200252723Sdim SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, 201226586Sdim const Decl *D, BugReporter &BR, AnalysisManager &mgr) const { 202226586Sdim // By far the most common case: nothing to check. 203226586Sdim if (PossibleMallocOverflows.empty()) 204226586Sdim return; 205226586Sdim 206226586Sdim // Delete any possible overflows which have a comparison. 207226586Sdim CheckOverflowOps c(PossibleMallocOverflows, BR.getContext()); 208235633Sdim c.Visit(mgr.getAnalysisDeclContext(D)->getBody()); 209226586Sdim 210226586Sdim // Output warnings for all overflows that are left. 211226586Sdim for (CheckOverflowOps::theVecType::iterator 212226586Sdim i = PossibleMallocOverflows.begin(), 213226586Sdim e = PossibleMallocOverflows.end(); 214226586Sdim i != e; 215226586Sdim ++i) { 216235633Sdim BR.EmitBasicReport(D, "malloc() size overflow", categories::UnixAPI, 217226586Sdim "the computation of the size of the memory allocation may overflow", 218226586Sdim PathDiagnosticLocation::createOperatorLoc(i->mulop, 219263509Sdim BR.getSourceManager()), 220263509Sdim i->mulop->getSourceRange()); 221226586Sdim } 222226586Sdim} 223226586Sdim 224226586Sdimvoid MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D, 225226586Sdim AnalysisManager &mgr, 226226586Sdim BugReporter &BR) const { 227226586Sdim 228226586Sdim CFG *cfg = mgr.getCFG(D); 229226586Sdim if (!cfg) 230226586Sdim return; 231226586Sdim 232226586Sdim // A list of variables referenced in possibly overflowing malloc operands. 233252723Sdim SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows; 234226586Sdim 235226586Sdim for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 236226586Sdim CFGBlock *block = *it; 237226586Sdim for (CFGBlock::iterator bi = block->begin(), be = block->end(); 238226586Sdim bi != be; ++bi) { 239252723Sdim if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) { 240226586Sdim if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) { 241226586Sdim // Get the callee. 242226586Sdim const FunctionDecl *FD = TheCall->getDirectCallee(); 243226586Sdim 244226586Sdim if (!FD) 245226586Sdim return; 246226586Sdim 247226586Sdim // Get the name of the callee. If it's a builtin, strip off the prefix. 248226586Sdim IdentifierInfo *FnInfo = FD->getIdentifier(); 249226586Sdim if (!FnInfo) 250226586Sdim return; 251226586Sdim 252226586Sdim if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) { 253226586Sdim if (TheCall->getNumArgs() == 1) 254226586Sdim CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0), 255226586Sdim mgr.getASTContext()); 256226586Sdim } 257226586Sdim } 258226586Sdim } 259226586Sdim } 260226586Sdim } 261226586Sdim 262226586Sdim OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr); 263226586Sdim} 264226586Sdim 265226586Sdimvoid ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) { 266226586Sdim mgr.registerChecker<MallocOverflowSecurityChecker>(); 267226586Sdim} 268