| 1 |
// MallocOverflowSecurityChecker.cpp - Check for malloc overflows -*- C++ -*-=// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// This checker detects a common memory allocation security flaw. |
| 10 |
// Suppose 'unsigned int n' comes from an untrusted source. If the |
| 11 |
// code looks like 'malloc (n * 4)', and an attacker can make 'n' be |
| 12 |
// say MAX_UINT/4+2, then instead of allocating the correct 'n' 4-byte |
| 13 |
// elements, this will actually allocate only two because of overflow. |
| 14 |
// Then when the rest of the program attempts to store values past the |
| 15 |
// second element, these values will actually overwrite other items in |
| 16 |
// the heap, probably allowing the attacker to execute arbitrary code. |
| 17 |
// |
| 18 |
//===----------------------------------------------------------------------===// |
| 19 |
|
| 20 |
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" |
| 21 |
#include "clang/AST/EvaluatedExprVisitor.h" |
| 22 |
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" |
| 23 |
#include "clang/StaticAnalyzer/Core/Checker.h" |
| 24 |
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" |
| 25 |
#include "llvm/ADT/APSInt.h" |
| 26 |
#include "llvm/ADT/SmallVector.h" |
| 27 |
#include <optional> |
| 28 |
#include <utility> |
| 29 |
|
| 30 |
using namespace clang; |
| 31 |
using namespace ento; |
| 32 |
using llvm::APSInt; |
| 33 |
|
| 34 |
namespace { |
| 35 |
struct MallocOverflowCheck { |
| 36 |
const CallExpr *call; |
| 37 |
const BinaryOperator *mulop; |
| 38 |
const Expr *variable; |
| 39 |
APSInt maxVal; |
| 40 |
|
| 41 |
MallocOverflowCheck(const CallExpr *call, const BinaryOperator *m, |
| 42 |
const Expr *v, APSInt val) |
| 43 |
: call(call), mulop(m), variable(v), maxVal(std::move(val)) {} |
| 44 |
}; |
| 45 |
|
| 46 |
class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> { |
| 47 |
public: |
| 48 |
void checkASTCodeBody(const Decl *D, AnalysisManager &mgr, |
| 49 |
BugReporter &BR) const; |
| 50 |
|
| 51 |
void CheckMallocArgument( |
| 52 |
SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, |
| 53 |
const CallExpr *TheCall, ASTContext &Context) const; |
| 54 |
|
| 55 |
void OutputPossibleOverflows( |
| 56 |
SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, |
| 57 |
const Decl *D, BugReporter &BR, AnalysisManager &mgr) const; |
| 58 |
|
| 59 |
}; |
| 60 |
} // end anonymous namespace |
| 61 |
|
| 62 |
// Return true for computations which evaluate to zero: e.g., mult by 0. |
| 63 |
static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) { |
| 64 |
return (op == BO_Mul) && (Val == 0); |
| 65 |
} |
| 66 |
|
| 67 |
void MallocOverflowSecurityChecker::CheckMallocArgument( |
| 68 |
SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, |
| 69 |
const CallExpr *TheCall, ASTContext &Context) const { |
| 70 |
|
| 71 |
/* Look for a linear combination with a single variable, and at least |
| 72 |
one multiplication. |
| 73 |
Reject anything that applies to the variable: an explicit cast, |
| 74 |
conditional expression, an operation that could reduce the range |
| 75 |
of the result, or anything too complicated :-). */ |
| 76 |
const Expr *e = TheCall->getArg(0); |
| 77 |
const BinaryOperator * mulop = nullptr; |
| 78 |
APSInt maxVal; |
| 79 |
|
| 80 |
for (;;) { |
| 81 |
maxVal = 0; |
| 82 |
e = e->IgnoreParenImpCasts(); |
| 83 |
if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) { |
| 84 |
BinaryOperatorKind opc = binop->getOpcode(); |
| 85 |
// TODO: ignore multiplications by 1, reject if multiplied by 0. |
| 86 |
if (mulop == nullptr && opc == BO_Mul) |
| 87 |
mulop = binop; |
| 88 |
if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl) |
| 89 |
return; |
| 90 |
|
| 91 |
const Expr *lhs = binop->getLHS(); |
| 92 |
const Expr *rhs = binop->getRHS(); |
| 93 |
if (rhs->isEvaluatable(Context)) { |
| 94 |
e = lhs; |
| 95 |
maxVal = rhs->EvaluateKnownConstInt(Context); |
| 96 |
if (EvaluatesToZero(maxVal, opc)) |
| 97 |
return; |
| 98 |
} else if ((opc == BO_Add || opc == BO_Mul) && |
| 99 |
lhs->isEvaluatable(Context)) { |
| 100 |
maxVal = lhs->EvaluateKnownConstInt(Context); |
| 101 |
if (EvaluatesToZero(maxVal, opc)) |
| 102 |
return; |
| 103 |
e = rhs; |
| 104 |
} else |
| 105 |
return; |
| 106 |
} else if (isa<DeclRefExpr, MemberExpr>(e)) |
| 107 |
break; |
| 108 |
else |
| 109 |
return; |
| 110 |
} |
| 111 |
|
| 112 |
if (mulop == nullptr) |
| 113 |
return; |
| 114 |
|
| 115 |
// We've found the right structure of malloc argument, now save |
| 116 |
// the data so when the body of the function is completely available |
| 117 |
// we can check for comparisons. |
| 118 |
|
| 119 |
PossibleMallocOverflows.push_back( |
| 120 |
MallocOverflowCheck(TheCall, mulop, e, maxVal)); |
| 121 |
} |
| 122 |
|
| 123 |
namespace { |
| 124 |
// A worker class for OutputPossibleOverflows. |
| 125 |
class CheckOverflowOps : |
| 126 |
public EvaluatedExprVisitor<CheckOverflowOps> { |
| 127 |
public: |
| 128 |
typedef SmallVectorImpl<MallocOverflowCheck> theVecType; |
| 129 |
|
| 130 |
private: |
| 131 |
theVecType &toScanFor; |
| 132 |
ASTContext &Context; |
| 133 |
|
| 134 |
bool isIntZeroExpr(const Expr *E) const { |
| 135 |
if (!E->getType()->isIntegralOrEnumerationType()) |
| 136 |
return false; |
| 137 |
Expr::EvalResult Result; |
| 138 |
if (E->EvaluateAsInt(Result, Context)) |
| 139 |
return Result.Val.getInt() == 0; |
| 140 |
return false; |
| 141 |
} |
| 142 |
|
| 143 |
static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); } |
| 144 |
static const Decl *getDecl(const MemberExpr *ME) { |
| 145 |
return ME->getMemberDecl(); |
| 146 |
} |
| 147 |
|
| 148 |
template <typename T1> |
| 149 |
void Erase(const T1 *DR, |
| 150 |
llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) { |
| 151 |
auto P = [DR, Pred](const MallocOverflowCheck &Check) { |
| 152 |
if (const auto *CheckDR = dyn_cast<T1>(Check.variable)) |
| 153 |
return getDecl(CheckDR) == getDecl(DR) && Pred(Check); |
| 154 |
return false; |
| 155 |
}; |
| 156 |
llvm::erase_if(toScanFor, P); |
| 157 |
} |
| 158 |
|
| 159 |
void CheckExpr(const Expr *E_p) { |
| 160 |
const Expr *E = E_p->IgnoreParenImpCasts(); |
| 161 |
const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) { |
| 162 |
return Context.getSourceManager().isBeforeInTranslationUnit( |
| 163 |
E->getExprLoc(), c.call->getExprLoc()); |
| 164 |
}; |
| 165 |
if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) |
| 166 |
Erase<DeclRefExpr>(DR, PrecedesMalloc); |
| 167 |
else if (const auto *ME = dyn_cast<MemberExpr>(E)) { |
| 168 |
Erase<MemberExpr>(ME, PrecedesMalloc); |
| 169 |
} |
| 170 |
} |
| 171 |
|
| 172 |
// Check if the argument to malloc is assigned a value |
| 173 |
// which cannot cause an overflow. |
| 174 |
// e.g., malloc (mul * x) and, |
| 175 |
// case 1: mul = <constant value> |
| 176 |
// case 2: mul = a/b, where b > x |
| 177 |
void CheckAssignmentExpr(BinaryOperator *AssignEx) { |
| 178 |
bool assignKnown = false; |
| 179 |
bool numeratorKnown = false, denomKnown = false; |
| 180 |
APSInt denomVal; |
| 181 |
denomVal = 0; |
| 182 |
|
| 183 |
// Erase if the multiplicand was assigned a constant value. |
| 184 |
const Expr *rhs = AssignEx->getRHS(); |
| 185 |
if (rhs->isEvaluatable(Context)) |
| 186 |
assignKnown = true; |
| 187 |
|
| 188 |
// Discard the report if the multiplicand was assigned a value, |
| 189 |
// that can never overflow after multiplication. e.g., the assignment |
| 190 |
// is a division operator and the denominator is > other multiplicand. |
| 191 |
const Expr *rhse = rhs->IgnoreParenImpCasts(); |
| 192 |
if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) { |
| 193 |
if (BOp->getOpcode() == BO_Div) { |
| 194 |
const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts(); |
| 195 |
Expr::EvalResult Result; |
| 196 |
if (denom->EvaluateAsInt(Result, Context)) { |
| 197 |
denomVal = Result.Val.getInt(); |
| 198 |
denomKnown = true; |
| 199 |
} |
| 200 |
const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts(); |
| 201 |
if (numerator->isEvaluatable(Context)) |
| 202 |
numeratorKnown = true; |
| 203 |
} |
| 204 |
} |
| 205 |
if (!assignKnown && !denomKnown) |
| 206 |
return; |
| 207 |
auto denomExtVal = denomVal.getExtValue(); |
| 208 |
|
| 209 |
// Ignore negative denominator. |
| 210 |
if (denomExtVal < 0) |
| 211 |
return; |
| 212 |
|
| 213 |
const Expr *lhs = AssignEx->getLHS(); |
| 214 |
const Expr *E = lhs->IgnoreParenImpCasts(); |
| 215 |
|
| 216 |
auto pred = [assignKnown, numeratorKnown, |
| 217 |
denomExtVal](const MallocOverflowCheck &Check) { |
| 218 |
return assignKnown || |
| 219 |
(numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue())); |
| 220 |
}; |
| 221 |
|
| 222 |
if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) |
| 223 |
Erase<DeclRefExpr>(DR, pred); |
| 224 |
else if (const auto *ME = dyn_cast<MemberExpr>(E)) |
| 225 |
Erase<MemberExpr>(ME, pred); |
| 226 |
} |
| 227 |
|
| 228 |
public: |
| 229 |
void VisitBinaryOperator(BinaryOperator *E) { |
| 230 |
if (E->isComparisonOp()) { |
| 231 |
const Expr * lhs = E->getLHS(); |
| 232 |
const Expr * rhs = E->getRHS(); |
| 233 |
// Ignore comparisons against zero, since they generally don't |
| 234 |
// protect against an overflow. |
| 235 |
if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) { |
| 236 |
CheckExpr(lhs); |
| 237 |
CheckExpr(rhs); |
| 238 |
} |
| 239 |
} |
| 240 |
if (E->isAssignmentOp()) |
| 241 |
CheckAssignmentExpr(E); |
| 242 |
EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E); |
| 243 |
} |
| 244 |
|
| 245 |
/* We specifically ignore loop conditions, because they're typically |
| 246 |
not error checks. */ |
| 247 |
void VisitWhileStmt(WhileStmt *S) { |
| 248 |
return this->Visit(S->getBody()); |
| 249 |
} |
| 250 |
void VisitForStmt(ForStmt *S) { |
| 251 |
return this->Visit(S->getBody()); |
| 252 |
} |
| 253 |
void VisitDoStmt(DoStmt *S) { |
| 254 |
return this->Visit(S->getBody()); |
| 255 |
} |
| 256 |
|
| 257 |
CheckOverflowOps(theVecType &v, ASTContext &ctx) |
| 258 |
: EvaluatedExprVisitor<CheckOverflowOps>(ctx), |
| 259 |
toScanFor(v), Context(ctx) |
| 260 |
{ } |
| 261 |
}; |
| 262 |
} |
| 263 |
|
| 264 |
// OutputPossibleOverflows - We've found a possible overflow earlier, |
| 265 |
// now check whether Body might contain a comparison which might be |
| 266 |
// preventing the overflow. |
| 267 |
// This doesn't do flow analysis, range analysis, or points-to analysis; it's |
| 268 |
// just a dumb "is there a comparison" scan. The aim here is to |
| 269 |
// detect the most blatent cases of overflow and educate the |
| 270 |
// programmer. |
| 271 |
void MallocOverflowSecurityChecker::OutputPossibleOverflows( |
| 272 |
SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows, |
| 273 |
const Decl *D, BugReporter &BR, AnalysisManager &mgr) const { |
| 274 |
// By far the most common case: nothing to check. |
| 275 |
if (PossibleMallocOverflows.empty()) |
| 276 |
return; |
| 277 |
|
| 278 |
// Delete any possible overflows which have a comparison. |
| 279 |
CheckOverflowOps c(PossibleMallocOverflows, BR.getContext()); |
| 280 |
c.Visit(mgr.getAnalysisDeclContext(D)->getBody()); |
| 281 |
|
| 282 |
// Output warnings for all overflows that are left. |
| 283 |
for (CheckOverflowOps::theVecType::iterator |
| 284 |
i = PossibleMallocOverflows.begin(), |
| 285 |
e = PossibleMallocOverflows.end(); |
| 286 |
i != e; |
| 287 |
++i) { |
| 288 |
BR.EmitBasicReport( |
| 289 |
D, this, "malloc() size overflow", categories::UnixAPI, |
| 290 |
"the computation of the size of the memory allocation may overflow", |
| 291 |
PathDiagnosticLocation::createOperatorLoc(i->mulop, |
| 292 |
BR.getSourceManager()), |
| 293 |
i->mulop->getSourceRange()); |
| 294 |
} |
| 295 |
} |
| 296 |
|
| 297 |
void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D, |
| 298 |
AnalysisManager &mgr, |
| 299 |
BugReporter &BR) const { |
| 300 |
|
| 301 |
CFG *cfg = mgr.getCFG(D); |
| 302 |
if (!cfg) |
| 303 |
return; |
| 304 |
|
| 305 |
// A list of variables referenced in possibly overflowing malloc operands. |
| 306 |
SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows; |
| 307 |
|
| 308 |
for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { |
| 309 |
CFGBlock *block = *it; |
| 310 |
for (CFGBlock::iterator bi = block->begin(), be = block->end(); |
| 311 |
bi != be; ++bi) { |
| 312 |
if (std::optional<CFGStmt> CS = bi->getAs<CFGStmt>()) { |
| 313 |
if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) { |
| 314 |
// Get the callee. |
| 315 |
const FunctionDecl *FD = TheCall->getDirectCallee(); |
| 316 |
|
| 317 |
if (!FD) |
| 318 |
continue; |
| 319 |
|
| 320 |
// Get the name of the callee. If it's a builtin, strip off the |
| 321 |
// prefix. |
| 322 |
IdentifierInfo *FnInfo = FD->getIdentifier(); |
| 323 |
if (!FnInfo) |
| 324 |
continue; |
| 325 |
|
| 326 |
if (FnInfo->isStr("malloc") || FnInfo->isStr("_MALLOC")) { |
| 327 |
if (TheCall->getNumArgs() == 1) |
| 328 |
CheckMallocArgument(PossibleMallocOverflows, TheCall, |
| 329 |
mgr.getASTContext()); |
| 330 |
} |
| 331 |
} |
| 332 |
} |
| 333 |
} |
| 334 |
} |
| 335 |
|
| 336 |
OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr); |
| 337 |
} |
| 338 |
|
| 339 |
void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) { |
| 340 |
mgr.registerChecker<MallocOverflowSecurityChecker>(); |
| 341 |
} |
| 342 |
|
| 343 |
bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) { |
| 344 |
return true; |
| 345 |
} |