1 //== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines ArrayBoundCheckerV2, which is a path-sensitive check 11 // which looks for an out-of-bound array element access. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "ClangSACheckers.h" 16 #include "clang/AST/CharUnits.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/ExprEngine.h" 23 #include "llvm/ADT/SmallString.h" 24 #include "llvm/Support/raw_ostream.h" 25 26 using namespace clang; 27 using namespace ento; 28 29 namespace { 30 class ArrayBoundCheckerV2 : 31 public Checker<check::Location> { 32 mutable std::unique_ptr<BuiltinBug> BT; 33 34 enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted }; 35 36 void reportOOB(CheckerContext &C, ProgramStateRef errorState, OOB_Kind kind, 37 std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const; 38 39 public: 40 void checkLocation(SVal l, bool isLoad, const Stmt*S, 41 CheckerContext &C) const; 42 }; 43 44 // FIXME: Eventually replace RegionRawOffset with this class. 45 class RegionRawOffsetV2 { 46 private: 47 const SubRegion *baseRegion; 48 SVal byteOffset; 49 50 RegionRawOffsetV2() 51 : baseRegion(nullptr), byteOffset(UnknownVal()) {} 52 53 public: 54 RegionRawOffsetV2(const SubRegion* base, SVal offset) 55 : baseRegion(base), byteOffset(offset) {} 56 57 NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); } 58 const SubRegion *getRegion() const { return baseRegion; } 59 60 static RegionRawOffsetV2 computeOffset(ProgramStateRef state, 61 SValBuilder &svalBuilder, 62 SVal location); 63 64 void dump() const; 65 void dumpToStream(raw_ostream &os) const; 66 }; 67 } 68 69 static SVal computeExtentBegin(SValBuilder &svalBuilder, 70 const MemRegion *region) { 71 const MemSpaceRegion *SR = region->getMemorySpace(); 72 if (SR->getKind() == MemRegion::UnknownSpaceRegionKind) 73 return UnknownVal(); 74 else 75 return svalBuilder.makeZeroArrayIndex(); 76 } 77 78 // TODO: once the constraint manager is smart enough to handle non simplified 79 // symbolic expressions remove this function. Note that this can not be used in 80 // the constraint manager as is, since this does not handle overflows. It is 81 // safe to assume, however, that memory offsets will not overflow. 82 static std::pair<NonLoc, nonloc::ConcreteInt> 83 getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent, 84 SValBuilder &svalBuilder) { 85 Optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>(); 86 if (SymVal && SymVal->isExpression()) { 87 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) { 88 llvm::APSInt constant = 89 APSIntType(extent.getValue()).convert(SIE->getRHS()); 90 switch (SIE->getOpcode()) { 91 case BO_Mul: 92 // The constant should never be 0 here, since it the result of scaling 93 // based on the size of a type which is never 0. 94 if ((extent.getValue() % constant) != 0) 95 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent); 96 else 97 return getSimplifiedOffsets( 98 nonloc::SymbolVal(SIE->getLHS()), 99 svalBuilder.makeIntVal(extent.getValue() / constant), 100 svalBuilder); 101 case BO_Add: 102 return getSimplifiedOffsets( 103 nonloc::SymbolVal(SIE->getLHS()), 104 svalBuilder.makeIntVal(extent.getValue() - constant), svalBuilder); 105 default: 106 break; 107 } 108 } 109 } 110 111 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent); 112 } 113 114 void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad, 115 const Stmt* LoadS, 116 CheckerContext &checkerContext) const { 117 118 // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping 119 // some new logic here that reasons directly about memory region extents. 120 // Once that logic is more mature, we can bring it back to assumeInBound() 121 // for all clients to use. 122 // 123 // The algorithm we are using here for bounds checking is to see if the 124 // memory access is within the extent of the base region. Since we 125 // have some flexibility in defining the base region, we can achieve 126 // various levels of conservatism in our buffer overflow checking. 127 ProgramStateRef state = checkerContext.getState(); 128 129 SValBuilder &svalBuilder = checkerContext.getSValBuilder(); 130 const RegionRawOffsetV2 &rawOffset = 131 RegionRawOffsetV2::computeOffset(state, svalBuilder, location); 132 133 if (!rawOffset.getRegion()) 134 return; 135 136 NonLoc rawOffsetVal = rawOffset.getByteOffset(); 137 138 // CHECK LOWER BOUND: Is byteOffset < extent begin? 139 // If so, we are doing a load/store 140 // before the first valid offset in the memory region. 141 142 SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion()); 143 144 if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) { 145 if (NV->getAs<nonloc::ConcreteInt>()) { 146 std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets = 147 getSimplifiedOffsets(rawOffset.getByteOffset(), 148 NV->castAs<nonloc::ConcreteInt>(), 149 svalBuilder); 150 rawOffsetVal = simplifiedOffsets.first; 151 *NV = simplifiedOffsets.second; 152 } 153 154 SVal lowerBound = svalBuilder.evalBinOpNN(state, BO_LT, rawOffsetVal, *NV, 155 svalBuilder.getConditionType()); 156 157 Optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>(); 158 if (!lowerBoundToCheck) 159 return; 160 161 ProgramStateRef state_precedesLowerBound, state_withinLowerBound; 162 std::tie(state_precedesLowerBound, state_withinLowerBound) = 163 state->assume(*lowerBoundToCheck); 164 165 // Are we constrained enough to definitely precede the lower bound? 166 if (state_precedesLowerBound && !state_withinLowerBound) { 167 reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); 168 return; 169 } 170 171 // Otherwise, assume the constraint of the lower bound. 172 assert(state_withinLowerBound); 173 state = state_withinLowerBound; 174 } 175 176 do { 177 // CHECK UPPER BOUND: Is byteOffset >= extent(baseRegion)? If so, 178 // we are doing a load/store after the last valid offset. 179 DefinedOrUnknownSVal extentVal = 180 rawOffset.getRegion()->getExtent(svalBuilder); 181 if (!extentVal.getAs<NonLoc>()) 182 break; 183 184 if (extentVal.getAs<nonloc::ConcreteInt>()) { 185 std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets = 186 getSimplifiedOffsets(rawOffset.getByteOffset(), 187 extentVal.castAs<nonloc::ConcreteInt>(), 188 svalBuilder); 189 rawOffsetVal = simplifiedOffsets.first; 190 extentVal = simplifiedOffsets.second; 191 } 192 193 SVal upperbound = svalBuilder.evalBinOpNN(state, BO_GE, rawOffsetVal, 194 extentVal.castAs<NonLoc>(), 195 svalBuilder.getConditionType()); 196 197 Optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>(); 198 if (!upperboundToCheck) 199 break; 200 201 ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; 202 std::tie(state_exceedsUpperBound, state_withinUpperBound) = 203 state->assume(*upperboundToCheck); 204 205 // If we are under constrained and the index variables are tainted, report. 206 if (state_exceedsUpperBound && state_withinUpperBound) { 207 SVal ByteOffset = rawOffset.getByteOffset(); 208 if (state->isTainted(ByteOffset)) { 209 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted, 210 llvm::make_unique<TaintBugVisitor>(ByteOffset)); 211 return; 212 } 213 } else if (state_exceedsUpperBound) { 214 // If we are constrained enough to definitely exceed the upper bound, 215 // report. 216 assert(!state_withinUpperBound); 217 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); 218 return; 219 } 220 221 assert(state_withinUpperBound); 222 state = state_withinUpperBound; 223 } 224 while (false); 225 226 checkerContext.addTransition(state); 227 } 228 229 void ArrayBoundCheckerV2::reportOOB( 230 CheckerContext &checkerContext, ProgramStateRef errorState, OOB_Kind kind, 231 std::unique_ptr<BugReporterVisitor> Visitor) const { 232 233 ExplodedNode *errorNode = checkerContext.generateErrorNode(errorState); 234 if (!errorNode) 235 return; 236 237 if (!BT) 238 BT.reset(new BuiltinBug(this, "Out-of-bound access")); 239 240 // FIXME: This diagnostics are preliminary. We should get far better 241 // diagnostics for explaining buffer overruns. 242 243 SmallString<256> buf; 244 llvm::raw_svector_ostream os(buf); 245 os << "Out of bound memory access "; 246 switch (kind) { 247 case OOB_Precedes: 248 os << "(accessed memory precedes memory block)"; 249 break; 250 case OOB_Excedes: 251 os << "(access exceeds upper limit of memory block)"; 252 break; 253 case OOB_Tainted: 254 os << "(index is tainted)"; 255 break; 256 } 257 258 auto BR = llvm::make_unique<BugReport>(*BT, os.str(), errorNode); 259 BR->addVisitor(std::move(Visitor)); 260 checkerContext.emitReport(std::move(BR)); 261 } 262 263 #ifndef NDEBUG 264 LLVM_DUMP_METHOD void RegionRawOffsetV2::dump() const { 265 dumpToStream(llvm::errs()); 266 } 267 268 void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { 269 os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; 270 } 271 #endif 272 273 // Lazily computes a value to be used by 'computeOffset'. If 'val' 274 // is unknown or undefined, we lazily substitute '0'. Otherwise, 275 // return 'val'. 276 static inline SVal getValue(SVal val, SValBuilder &svalBuilder) { 277 return val.getAs<UndefinedVal>() ? svalBuilder.makeArrayIndex(0) : val; 278 } 279 280 // Scale a base value by a scaling factor, and return the scaled 281 // value as an SVal. Used by 'computeOffset'. 282 static inline SVal scaleValue(ProgramStateRef state, 283 NonLoc baseVal, CharUnits scaling, 284 SValBuilder &sb) { 285 return sb.evalBinOpNN(state, BO_Mul, baseVal, 286 sb.makeArrayIndex(scaling.getQuantity()), 287 sb.getArrayIndexType()); 288 } 289 290 // Add an SVal to another, treating unknown and undefined values as 291 // summing to UnknownVal. Used by 'computeOffset'. 292 static SVal addValue(ProgramStateRef state, SVal x, SVal y, 293 SValBuilder &svalBuilder) { 294 // We treat UnknownVals and UndefinedVals the same here because we 295 // only care about computing offsets. 296 if (x.isUnknownOrUndef() || y.isUnknownOrUndef()) 297 return UnknownVal(); 298 299 return svalBuilder.evalBinOpNN(state, BO_Add, x.castAs<NonLoc>(), 300 y.castAs<NonLoc>(), 301 svalBuilder.getArrayIndexType()); 302 } 303 304 /// Compute a raw byte offset from a base region. Used for array bounds 305 /// checking. 306 RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state, 307 SValBuilder &svalBuilder, 308 SVal location) 309 { 310 const MemRegion *region = location.getAsRegion(); 311 SVal offset = UndefinedVal(); 312 313 while (region) { 314 switch (region->getKind()) { 315 default: { 316 if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) { 317 offset = getValue(offset, svalBuilder); 318 if (!offset.isUnknownOrUndef()) 319 return RegionRawOffsetV2(subReg, offset); 320 } 321 return RegionRawOffsetV2(); 322 } 323 case MemRegion::ElementRegionKind: { 324 const ElementRegion *elemReg = cast<ElementRegion>(region); 325 SVal index = elemReg->getIndex(); 326 if (!index.getAs<NonLoc>()) 327 return RegionRawOffsetV2(); 328 QualType elemType = elemReg->getElementType(); 329 // If the element is an incomplete type, go no further. 330 ASTContext &astContext = svalBuilder.getContext(); 331 if (elemType->isIncompleteType()) 332 return RegionRawOffsetV2(); 333 334 // Update the offset. 335 offset = addValue(state, 336 getValue(offset, svalBuilder), 337 scaleValue(state, 338 index.castAs<NonLoc>(), 339 astContext.getTypeSizeInChars(elemType), 340 svalBuilder), 341 svalBuilder); 342 343 if (offset.isUnknownOrUndef()) 344 return RegionRawOffsetV2(); 345 346 region = elemReg->getSuperRegion(); 347 continue; 348 } 349 } 350 } 351 return RegionRawOffsetV2(); 352 } 353 354 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 355 mgr.registerChecker<ArrayBoundCheckerV2>(); 356 } 357