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/StaticAnalyzer/Core/Checker.h" 17 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 21 #include "clang/AST/CharUnits.h" 22 23 using namespace clang; 24 using namespace ento; 25 26 namespace { 27 class ArrayBoundCheckerV2 : 28 public Checker<check::Location> { 29 mutable llvm::OwningPtr<BuiltinBug> BT; 30 31 enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted }; 32 33 void reportOOB(CheckerContext &C, ProgramStateRef errorState, 34 OOB_Kind kind) const; 35 36 public: 37 void checkLocation(SVal l, bool isLoad, const Stmt*S, 38 CheckerContext &C) const; 39 }; 40 41 // FIXME: Eventually replace RegionRawOffset with this class. 42 class RegionRawOffsetV2 { 43 private: 44 const SubRegion *baseRegion; 45 SVal byteOffset; 46 47 RegionRawOffsetV2() 48 : baseRegion(0), byteOffset(UnknownVal()) {} 49 50 public: 51 RegionRawOffsetV2(const SubRegion* base, SVal offset) 52 : baseRegion(base), byteOffset(offset) {} 53 54 NonLoc getByteOffset() const { return cast<NonLoc>(byteOffset); } 55 const SubRegion *getRegion() const { return baseRegion; } 56 57 static RegionRawOffsetV2 computeOffset(ProgramStateRef state, 58 SValBuilder &svalBuilder, 59 SVal location); 60 61 void dump() const; 62 void dumpToStream(raw_ostream &os) const; 63 }; 64 } 65 66 static SVal computeExtentBegin(SValBuilder &svalBuilder, 67 const MemRegion *region) { 68 while (true) 69 switch (region->getKind()) { 70 default: 71 return svalBuilder.makeZeroArrayIndex(); 72 case MemRegion::SymbolicRegionKind: 73 // FIXME: improve this later by tracking symbolic lower bounds 74 // for symbolic regions. 75 return UnknownVal(); 76 case MemRegion::ElementRegionKind: 77 region = cast<SubRegion>(region)->getSuperRegion(); 78 continue; 79 } 80 } 81 82 void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad, 83 const Stmt* LoadS, 84 CheckerContext &checkerContext) const { 85 86 // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping 87 // some new logic here that reasons directly about memory region extents. 88 // Once that logic is more mature, we can bring it back to assumeInBound() 89 // for all clients to use. 90 // 91 // The algorithm we are using here for bounds checking is to see if the 92 // memory access is within the extent of the base region. Since we 93 // have some flexibility in defining the base region, we can achieve 94 // various levels of conservatism in our buffer overflow checking. 95 ProgramStateRef state = checkerContext.getState(); 96 ProgramStateRef originalState = state; 97 98 SValBuilder &svalBuilder = checkerContext.getSValBuilder(); 99 const RegionRawOffsetV2 &rawOffset = 100 RegionRawOffsetV2::computeOffset(state, svalBuilder, location); 101 102 if (!rawOffset.getRegion()) 103 return; 104 105 // CHECK LOWER BOUND: Is byteOffset < extent begin? 106 // If so, we are doing a load/store 107 // before the first valid offset in the memory region. 108 109 SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion()); 110 111 if (isa<NonLoc>(extentBegin)) { 112 SVal lowerBound 113 = svalBuilder.evalBinOpNN(state, BO_LT, rawOffset.getByteOffset(), 114 cast<NonLoc>(extentBegin), 115 svalBuilder.getConditionType()); 116 117 NonLoc *lowerBoundToCheck = dyn_cast<NonLoc>(&lowerBound); 118 if (!lowerBoundToCheck) 119 return; 120 121 ProgramStateRef state_precedesLowerBound, state_withinLowerBound; 122 llvm::tie(state_precedesLowerBound, state_withinLowerBound) = 123 state->assume(*lowerBoundToCheck); 124 125 // Are we constrained enough to definitely precede the lower bound? 126 if (state_precedesLowerBound && !state_withinLowerBound) { 127 reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); 128 return; 129 } 130 131 // Otherwise, assume the constraint of the lower bound. 132 assert(state_withinLowerBound); 133 state = state_withinLowerBound; 134 } 135 136 do { 137 // CHECK UPPER BOUND: Is byteOffset >= extent(baseRegion)? If so, 138 // we are doing a load/store after the last valid offset. 139 DefinedOrUnknownSVal extentVal = 140 rawOffset.getRegion()->getExtent(svalBuilder); 141 if (!isa<NonLoc>(extentVal)) 142 break; 143 144 SVal upperbound 145 = svalBuilder.evalBinOpNN(state, BO_GE, rawOffset.getByteOffset(), 146 cast<NonLoc>(extentVal), 147 svalBuilder.getConditionType()); 148 149 NonLoc *upperboundToCheck = dyn_cast<NonLoc>(&upperbound); 150 if (!upperboundToCheck) 151 break; 152 153 ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; 154 llvm::tie(state_exceedsUpperBound, state_withinUpperBound) = 155 state->assume(*upperboundToCheck); 156 157 // If we are under constrained and the index variables are tainted, report. 158 if (state_exceedsUpperBound && state_withinUpperBound) { 159 if (state->isTainted(rawOffset.getByteOffset())) 160 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted); 161 return; 162 } 163 164 // If we are constrained enough to definitely exceed the upper bound, report. 165 if (state_exceedsUpperBound) { 166 assert(!state_withinUpperBound); 167 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); 168 return; 169 } 170 171 assert(state_withinUpperBound); 172 state = state_withinUpperBound; 173 } 174 while (false); 175 176 if (state != originalState) 177 checkerContext.addTransition(state); 178 } 179 180 void ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, 181 ProgramStateRef errorState, 182 OOB_Kind kind) const { 183 184 ExplodedNode *errorNode = checkerContext.generateSink(errorState); 185 if (!errorNode) 186 return; 187 188 if (!BT) 189 BT.reset(new BuiltinBug("Out-of-bound access")); 190 191 // FIXME: This diagnostics are preliminary. We should get far better 192 // diagnostics for explaining buffer overruns. 193 194 llvm::SmallString<256> buf; 195 llvm::raw_svector_ostream os(buf); 196 os << "Out of bound memory access "; 197 switch (kind) { 198 case OOB_Precedes: 199 os << "(accessed memory precedes memory block)"; 200 break; 201 case OOB_Excedes: 202 os << "(access exceeds upper limit of memory block)"; 203 break; 204 case OOB_Tainted: 205 os << "(index is tainted)"; 206 break; 207 } 208 209 checkerContext.EmitReport(new BugReport(*BT, os.str(), errorNode)); 210 } 211 212 void RegionRawOffsetV2::dump() const { 213 dumpToStream(llvm::errs()); 214 } 215 216 void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { 217 os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; 218 } 219 220 // FIXME: Merge with the implementation of the same method in Store.cpp 221 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 222 if (const RecordType *RT = Ty->getAs<RecordType>()) { 223 const RecordDecl *D = RT->getDecl(); 224 if (!D->getDefinition()) 225 return false; 226 } 227 228 return true; 229 } 230 231 232 // Lazily computes a value to be used by 'computeOffset'. If 'val' 233 // is unknown or undefined, we lazily substitute '0'. Otherwise, 234 // return 'val'. 235 static inline SVal getValue(SVal val, SValBuilder &svalBuilder) { 236 return isa<UndefinedVal>(val) ? svalBuilder.makeArrayIndex(0) : val; 237 } 238 239 // Scale a base value by a scaling factor, and return the scaled 240 // value as an SVal. Used by 'computeOffset'. 241 static inline SVal scaleValue(ProgramStateRef state, 242 NonLoc baseVal, CharUnits scaling, 243 SValBuilder &sb) { 244 return sb.evalBinOpNN(state, BO_Mul, baseVal, 245 sb.makeArrayIndex(scaling.getQuantity()), 246 sb.getArrayIndexType()); 247 } 248 249 // Add an SVal to another, treating unknown and undefined values as 250 // summing to UnknownVal. Used by 'computeOffset'. 251 static SVal addValue(ProgramStateRef state, SVal x, SVal y, 252 SValBuilder &svalBuilder) { 253 // We treat UnknownVals and UndefinedVals the same here because we 254 // only care about computing offsets. 255 if (x.isUnknownOrUndef() || y.isUnknownOrUndef()) 256 return UnknownVal(); 257 258 return svalBuilder.evalBinOpNN(state, BO_Add, 259 cast<NonLoc>(x), cast<NonLoc>(y), 260 svalBuilder.getArrayIndexType()); 261 } 262 263 /// Compute a raw byte offset from a base region. Used for array bounds 264 /// checking. 265 RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state, 266 SValBuilder &svalBuilder, 267 SVal location) 268 { 269 const MemRegion *region = location.getAsRegion(); 270 SVal offset = UndefinedVal(); 271 272 while (region) { 273 switch (region->getKind()) { 274 default: { 275 if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) { 276 offset = getValue(offset, svalBuilder); 277 if (!offset.isUnknownOrUndef()) 278 return RegionRawOffsetV2(subReg, offset); 279 } 280 return RegionRawOffsetV2(); 281 } 282 case MemRegion::ElementRegionKind: { 283 const ElementRegion *elemReg = cast<ElementRegion>(region); 284 SVal index = elemReg->getIndex(); 285 if (!isa<NonLoc>(index)) 286 return RegionRawOffsetV2(); 287 QualType elemType = elemReg->getElementType(); 288 // If the element is an incomplete type, go no further. 289 ASTContext &astContext = svalBuilder.getContext(); 290 if (!IsCompleteType(astContext, elemType)) 291 return RegionRawOffsetV2(); 292 293 // Update the offset. 294 offset = addValue(state, 295 getValue(offset, svalBuilder), 296 scaleValue(state, 297 cast<NonLoc>(index), 298 astContext.getTypeSizeInChars(elemType), 299 svalBuilder), 300 svalBuilder); 301 302 if (offset.isUnknownOrUndef()) 303 return RegionRawOffsetV2(); 304 305 region = elemReg->getSuperRegion(); 306 continue; 307 } 308 } 309 } 310 return RegionRawOffsetV2(); 311 } 312 313 314 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 315 mgr.registerChecker<ArrayBoundCheckerV2>(); 316 } 317