1 //== ArrayBoundCheckerV2.cpp ------------------------------------*- 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 file defines ArrayBoundCheckerV2, which is a path-sensitive check 10 // which looks for an out-of-bound array element access. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/AST/CharUnits.h" 15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" 16 #include "clang/StaticAnalyzer/Checkers/Taint.h" 17 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 18 #include "clang/StaticAnalyzer/Core/Checker.h" 19 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 20 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 22 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 24 #include "llvm/ADT/SmallString.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include <optional> 27 28 using namespace clang; 29 using namespace ento; 30 using namespace taint; 31 32 namespace { 33 class ArrayBoundCheckerV2 : 34 public Checker<check::Location> { 35 mutable std::unique_ptr<BuiltinBug> BT; 36 mutable std::unique_ptr<BugType> TaintBT; 37 38 enum OOB_Kind { OOB_Precedes, OOB_Excedes }; 39 40 void reportOOB(CheckerContext &C, ProgramStateRef errorState, 41 OOB_Kind kind) const; 42 void reportTaintOOB(CheckerContext &C, ProgramStateRef errorState, 43 SVal TaintedSVal) const; 44 45 static bool isFromCtypeMacro(const Stmt *S, ASTContext &AC); 46 47 public: 48 void checkLocation(SVal l, bool isLoad, const Stmt *S, 49 CheckerContext &C) const; 50 }; 51 52 // FIXME: Eventually replace RegionRawOffset with this class. 53 class RegionRawOffsetV2 { 54 private: 55 const SubRegion *baseRegion; 56 NonLoc byteOffset; 57 58 public: 59 RegionRawOffsetV2(const SubRegion *base, NonLoc offset) 60 : baseRegion(base), byteOffset(offset) { assert(base); } 61 62 NonLoc getByteOffset() const { return byteOffset; } 63 const SubRegion *getRegion() const { return baseRegion; } 64 65 static std::optional<RegionRawOffsetV2> 66 computeOffset(ProgramStateRef State, SValBuilder &SVB, SVal Location); 67 68 void dump() const; 69 void dumpToStream(raw_ostream &os) const; 70 }; 71 } 72 73 // TODO: once the constraint manager is smart enough to handle non simplified 74 // symbolic expressions remove this function. Note that this can not be used in 75 // the constraint manager as is, since this does not handle overflows. It is 76 // safe to assume, however, that memory offsets will not overflow. 77 // NOTE: callers of this function need to be aware of the effects of overflows 78 // and signed<->unsigned conversions! 79 static std::pair<NonLoc, nonloc::ConcreteInt> 80 getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent, 81 SValBuilder &svalBuilder) { 82 std::optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>(); 83 if (SymVal && SymVal->isExpression()) { 84 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) { 85 llvm::APSInt constant = 86 APSIntType(extent.getValue()).convert(SIE->getRHS()); 87 switch (SIE->getOpcode()) { 88 case BO_Mul: 89 // The constant should never be 0 here, since it the result of scaling 90 // based on the size of a type which is never 0. 91 if ((extent.getValue() % constant) != 0) 92 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent); 93 else 94 return getSimplifiedOffsets( 95 nonloc::SymbolVal(SIE->getLHS()), 96 svalBuilder.makeIntVal(extent.getValue() / constant), 97 svalBuilder); 98 case BO_Add: 99 return getSimplifiedOffsets( 100 nonloc::SymbolVal(SIE->getLHS()), 101 svalBuilder.makeIntVal(extent.getValue() - constant), svalBuilder); 102 default: 103 break; 104 } 105 } 106 } 107 108 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent); 109 } 110 111 // Evaluate the comparison Value < Threshold with the help of the custom 112 // simplification algorithm defined for this checker. Return a pair of states, 113 // where the first one corresponds to "value below threshold" and the second 114 // corresponds to "value at or above threshold". Returns {nullptr, nullptr} in 115 // the case when the evaluation fails. 116 static std::pair<ProgramStateRef, ProgramStateRef> 117 compareValueToThreshold(ProgramStateRef State, NonLoc Value, NonLoc Threshold, 118 SValBuilder &SVB) { 119 if (auto ConcreteThreshold = Threshold.getAs<nonloc::ConcreteInt>()) { 120 std::tie(Value, Threshold) = getSimplifiedOffsets(Value, *ConcreteThreshold, SVB); 121 } 122 if (auto ConcreteThreshold = Threshold.getAs<nonloc::ConcreteInt>()) { 123 QualType T = Value.getType(SVB.getContext()); 124 if (T->isUnsignedIntegerType() && ConcreteThreshold->getValue().isNegative()) { 125 // In this case we reduced the bound check to a comparison of the form 126 // (symbol or value with unsigned type) < (negative number) 127 // which is always false. We are handling these cases separately because 128 // evalBinOpNN can perform a signed->unsigned conversion that turns the 129 // negative number into a huge positive value and leads to wildly 130 // inaccurate conclusions. 131 return {nullptr, State}; 132 } 133 } 134 auto BelowThreshold = 135 SVB.evalBinOpNN(State, BO_LT, Value, Threshold, SVB.getConditionType()).getAs<NonLoc>(); 136 137 if (BelowThreshold) 138 return State->assume(*BelowThreshold); 139 140 return {nullptr, nullptr}; 141 } 142 143 void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad, 144 const Stmt* LoadS, 145 CheckerContext &checkerContext) const { 146 147 // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping 148 // some new logic here that reasons directly about memory region extents. 149 // Once that logic is more mature, we can bring it back to assumeInBound() 150 // for all clients to use. 151 // 152 // The algorithm we are using here for bounds checking is to see if the 153 // memory access is within the extent of the base region. Since we 154 // have some flexibility in defining the base region, we can achieve 155 // various levels of conservatism in our buffer overflow checking. 156 157 // The header ctype.h (from e.g. glibc) implements the isXXXXX() macros as 158 // #define isXXXXX(arg) (LOOKUP_TABLE[arg] & BITMASK_FOR_XXXXX) 159 // and incomplete analysis of these leads to false positives. As even 160 // accurate reports would be confusing for the users, just disable reports 161 // from these macros: 162 if (isFromCtypeMacro(LoadS, checkerContext.getASTContext())) 163 return; 164 165 ProgramStateRef state = checkerContext.getState(); 166 167 SValBuilder &svalBuilder = checkerContext.getSValBuilder(); 168 const std::optional<RegionRawOffsetV2> &RawOffset = 169 RegionRawOffsetV2::computeOffset(state, svalBuilder, location); 170 171 if (!RawOffset) 172 return; 173 174 NonLoc ByteOffset = RawOffset->getByteOffset(); 175 const SubRegion *Reg = RawOffset->getRegion(); 176 177 // CHECK LOWER BOUND 178 const MemSpaceRegion *Space = Reg->getMemorySpace(); 179 if (!(isa<SymbolicRegion>(Reg) && isa<UnknownSpaceRegion>(Space))) { 180 // A symbolic region in unknown space represents an unknown pointer that 181 // may point into the middle of an array, so we don't look for underflows. 182 // Both conditions are significant because we want to check underflows in 183 // symbolic regions on the heap (which may be introduced by checkers like 184 // MallocChecker that call SValBuilder::getConjuredHeapSymbolVal()) and 185 // non-symbolic regions (e.g. a field subregion of a symbolic region) in 186 // unknown space. 187 auto [state_precedesLowerBound, state_withinLowerBound] = 188 compareValueToThreshold(state, ByteOffset, 189 svalBuilder.makeZeroArrayIndex(), svalBuilder); 190 191 if (state_precedesLowerBound && !state_withinLowerBound) { 192 // We know that the index definitely precedes the lower bound. 193 reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); 194 return; 195 } 196 197 if (state_withinLowerBound) 198 state = state_withinLowerBound; 199 } 200 201 // CHECK UPPER BOUND 202 DefinedOrUnknownSVal Size = getDynamicExtent(state, Reg, svalBuilder); 203 if (auto KnownSize = Size.getAs<NonLoc>()) { 204 auto [state_withinUpperBound, state_exceedsUpperBound] = 205 compareValueToThreshold(state, ByteOffset, *KnownSize, svalBuilder); 206 207 if (state_exceedsUpperBound) { 208 if (!state_withinUpperBound) { 209 // We know that the index definitely exceeds the upper bound. 210 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); 211 return; 212 } 213 if (isTainted(state, ByteOffset)) { 214 // Both cases are possible, but the index is tainted, so report. 215 reportTaintOOB(checkerContext, state_exceedsUpperBound, ByteOffset); 216 return; 217 } 218 } 219 220 if (state_withinUpperBound) 221 state = state_withinUpperBound; 222 } 223 224 checkerContext.addTransition(state); 225 } 226 227 void ArrayBoundCheckerV2::reportTaintOOB(CheckerContext &checkerContext, 228 ProgramStateRef errorState, 229 SVal TaintedSVal) const { 230 ExplodedNode *errorNode = checkerContext.generateErrorNode(errorState); 231 if (!errorNode) 232 return; 233 234 if (!TaintBT) 235 TaintBT.reset( 236 new BugType(this, "Out-of-bound access", categories::TaintedData)); 237 238 SmallString<256> buf; 239 llvm::raw_svector_ostream os(buf); 240 os << "Out of bound memory access (index is tainted)"; 241 auto BR = 242 std::make_unique<PathSensitiveBugReport>(*TaintBT, os.str(), errorNode); 243 244 // Track back the propagation of taintedness. 245 for (SymbolRef Sym : getTaintedSymbols(errorState, TaintedSVal)) { 246 BR->markInteresting(Sym); 247 } 248 249 checkerContext.emitReport(std::move(BR)); 250 } 251 252 void ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, 253 ProgramStateRef errorState, 254 OOB_Kind kind) const { 255 256 ExplodedNode *errorNode = checkerContext.generateErrorNode(errorState); 257 if (!errorNode) 258 return; 259 260 if (!BT) 261 BT.reset(new BuiltinBug(this, "Out-of-bound access")); 262 263 // FIXME: This diagnostics are preliminary. We should get far better 264 // diagnostics for explaining buffer overruns. 265 266 SmallString<256> buf; 267 llvm::raw_svector_ostream os(buf); 268 os << "Out of bound memory access "; 269 switch (kind) { 270 case OOB_Precedes: 271 os << "(accessed memory precedes memory block)"; 272 break; 273 case OOB_Excedes: 274 os << "(access exceeds upper limit of memory block)"; 275 break; 276 } 277 auto BR = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), errorNode); 278 checkerContext.emitReport(std::move(BR)); 279 } 280 281 bool ArrayBoundCheckerV2::isFromCtypeMacro(const Stmt *S, ASTContext &ACtx) { 282 SourceLocation Loc = S->getBeginLoc(); 283 if (!Loc.isMacroID()) 284 return false; 285 286 StringRef MacroName = Lexer::getImmediateMacroName( 287 Loc, ACtx.getSourceManager(), ACtx.getLangOpts()); 288 289 if (MacroName.size() < 7 || MacroName[0] != 'i' || MacroName[1] != 's') 290 return false; 291 292 return ((MacroName == "isalnum") || (MacroName == "isalpha") || 293 (MacroName == "isblank") || (MacroName == "isdigit") || 294 (MacroName == "isgraph") || (MacroName == "islower") || 295 (MacroName == "isnctrl") || (MacroName == "isprint") || 296 (MacroName == "ispunct") || (MacroName == "isspace") || 297 (MacroName == "isupper") || (MacroName == "isxdigit")); 298 } 299 300 #ifndef NDEBUG 301 LLVM_DUMP_METHOD void RegionRawOffsetV2::dump() const { 302 dumpToStream(llvm::errs()); 303 } 304 305 void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { 306 os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; 307 } 308 #endif 309 310 /// For a given Location that can be represented as a symbolic expression 311 /// Arr[Idx] (or perhaps Arr[Idx1][Idx2] etc.), return the parent memory block 312 /// Arr and the distance of Location from the beginning of Arr (expressed in a 313 /// NonLoc that specifies the number of CharUnits). Returns nullopt when these 314 /// cannot be determined. 315 std::optional<RegionRawOffsetV2> 316 RegionRawOffsetV2::computeOffset(ProgramStateRef State, SValBuilder &SVB, 317 SVal Location) { 318 QualType T = SVB.getArrayIndexType(); 319 auto Calc = [&SVB, State, T](BinaryOperatorKind Op, NonLoc LHS, NonLoc RHS) { 320 // We will use this utility to add and multiply values. 321 return SVB.evalBinOpNN(State, Op, LHS, RHS, T).getAs<NonLoc>(); 322 }; 323 324 const MemRegion *Region = Location.getAsRegion(); 325 NonLoc Offset = SVB.makeZeroArrayIndex(); 326 327 while (Region) { 328 if (const auto *ERegion = dyn_cast<ElementRegion>(Region)) { 329 if (const auto Index = ERegion->getIndex().getAs<NonLoc>()) { 330 QualType ElemType = ERegion->getElementType(); 331 // If the element is an incomplete type, go no further. 332 if (ElemType->isIncompleteType()) 333 return std::nullopt; 334 335 // Perform Offset += Index * sizeof(ElemType); then continue the offset 336 // calculations with SuperRegion: 337 NonLoc Size = SVB.makeArrayIndex( 338 SVB.getContext().getTypeSizeInChars(ElemType).getQuantity()); 339 if (auto Delta = Calc(BO_Mul, *Index, Size)) { 340 if (auto NewOffset = Calc(BO_Add, Offset, *Delta)) { 341 Offset = *NewOffset; 342 Region = ERegion->getSuperRegion(); 343 continue; 344 } 345 } 346 } 347 } else if (const auto *SRegion = dyn_cast<SubRegion>(Region)) { 348 // NOTE: The dyn_cast<>() is expected to succeed, it'd be very surprising 349 // to see a MemSpaceRegion at this point. 350 // FIXME: We may return with {<Region>, 0} even if we didn't handle any 351 // ElementRegion layers. I think that this behavior was introduced 352 // accidentally by 8a4c760c204546aba566e302f299f7ed2e00e287 in 2011, so 353 // it may be useful to review it in the future. 354 return RegionRawOffsetV2(SRegion, Offset); 355 } 356 return std::nullopt; 357 } 358 return std::nullopt; 359 } 360 361 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 362 mgr.registerChecker<ArrayBoundCheckerV2>(); 363 } 364 365 bool ento::shouldRegisterArrayBoundCheckerV2(const CheckerManager &mgr) { 366 return true; 367 } 368