ArrayBoundCheckerV2.cpp revision 3bfd6d701ee297bd062967e11400daae51b36eb2
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 23using namespace clang; 24using namespace ento; 25 26namespace { 27class 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, const ProgramState *errorState, 34 OOB_Kind kind) const; 35 36public: 37 void checkLocation(SVal l, bool isLoad, const Stmt*S, 38 CheckerContext &C) const; 39}; 40 41// FIXME: Eventually replace RegionRawOffset with this class. 42class RegionRawOffsetV2 { 43private: 44 const SubRegion *baseRegion; 45 SVal byteOffset; 46 47 RegionRawOffsetV2() 48 : baseRegion(0), byteOffset(UnknownVal()) {} 49 50public: 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(const ProgramState *state, 58 SValBuilder &svalBuilder, 59 SVal location); 60 61 void dump() const; 62 void dumpToStream(raw_ostream &os) const; 63}; 64} 65 66static 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 82void 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 const ProgramState *state = checkerContext.getState(); 96 const ProgramState *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 const ProgramState *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 const ProgramState *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 180void ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, 181 const ProgramState *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 212void RegionRawOffsetV2::dump() const { 213 dumpToStream(llvm::errs()); 214} 215 216void 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 221static 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'. 235static 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'. 241static inline SVal scaleValue(const ProgramState *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'. 251static SVal addValue(const ProgramState *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. 265RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(const ProgramState *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 314void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 315 mgr.registerChecker<ArrayBoundCheckerV2>(); 316} 317