ArrayBoundCheckerV2.cpp revision 390909c89c98ab1807e15e033a72e975f866fb23
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 }; 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 // Are we constrained enough to definitely exceed the upper bound? 158 if (state_exceedsUpperBound && !state_withinUpperBound) { 159 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); 160 return; 161 } 162 163 assert(state_withinUpperBound); 164 state = state_withinUpperBound; 165 } 166 while (false); 167 168 if (state != originalState) 169 checkerContext.generateNode(state); 170} 171 172void ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, 173 const ProgramState *errorState, 174 OOB_Kind kind) const { 175 176 ExplodedNode *errorNode = checkerContext.generateSink(errorState); 177 if (!errorNode) 178 return; 179 180 if (!BT) 181 BT.reset(new BuiltinBug("Out-of-bound access")); 182 183 // FIXME: This diagnostics are preliminary. We should get far better 184 // diagnostics for explaining buffer overruns. 185 186 llvm::SmallString<256> buf; 187 llvm::raw_svector_ostream os(buf); 188 os << "Out of bound memory access " 189 << (kind == OOB_Precedes ? "(accessed memory precedes memory block)" 190 : "(access exceeds upper limit of memory block)"); 191 192 checkerContext.EmitReport(new BugReport(*BT, os.str(), errorNode)); 193} 194 195void RegionRawOffsetV2::dump() const { 196 dumpToStream(llvm::errs()); 197} 198 199void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { 200 os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; 201} 202 203// FIXME: Merge with the implementation of the same method in Store.cpp 204static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 205 if (const RecordType *RT = Ty->getAs<RecordType>()) { 206 const RecordDecl *D = RT->getDecl(); 207 if (!D->getDefinition()) 208 return false; 209 } 210 211 return true; 212} 213 214 215// Lazily computes a value to be used by 'computeOffset'. If 'val' 216// is unknown or undefined, we lazily substitute '0'. Otherwise, 217// return 'val'. 218static inline SVal getValue(SVal val, SValBuilder &svalBuilder) { 219 return isa<UndefinedVal>(val) ? svalBuilder.makeArrayIndex(0) : val; 220} 221 222// Scale a base value by a scaling factor, and return the scaled 223// value as an SVal. Used by 'computeOffset'. 224static inline SVal scaleValue(const ProgramState *state, 225 NonLoc baseVal, CharUnits scaling, 226 SValBuilder &sb) { 227 return sb.evalBinOpNN(state, BO_Mul, baseVal, 228 sb.makeArrayIndex(scaling.getQuantity()), 229 sb.getArrayIndexType()); 230} 231 232// Add an SVal to another, treating unknown and undefined values as 233// summing to UnknownVal. Used by 'computeOffset'. 234static SVal addValue(const ProgramState *state, SVal x, SVal y, 235 SValBuilder &svalBuilder) { 236 // We treat UnknownVals and UndefinedVals the same here because we 237 // only care about computing offsets. 238 if (x.isUnknownOrUndef() || y.isUnknownOrUndef()) 239 return UnknownVal(); 240 241 return svalBuilder.evalBinOpNN(state, BO_Add, 242 cast<NonLoc>(x), cast<NonLoc>(y), 243 svalBuilder.getArrayIndexType()); 244} 245 246/// Compute a raw byte offset from a base region. Used for array bounds 247/// checking. 248RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(const ProgramState *state, 249 SValBuilder &svalBuilder, 250 SVal location) 251{ 252 const MemRegion *region = location.getAsRegion(); 253 SVal offset = UndefinedVal(); 254 255 while (region) { 256 switch (region->getKind()) { 257 default: { 258 if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) { 259 offset = getValue(offset, svalBuilder); 260 if (!offset.isUnknownOrUndef()) 261 return RegionRawOffsetV2(subReg, offset); 262 } 263 return RegionRawOffsetV2(); 264 } 265 case MemRegion::ElementRegionKind: { 266 const ElementRegion *elemReg = cast<ElementRegion>(region); 267 SVal index = elemReg->getIndex(); 268 if (!isa<NonLoc>(index)) 269 return RegionRawOffsetV2(); 270 QualType elemType = elemReg->getElementType(); 271 // If the element is an incomplete type, go no further. 272 ASTContext &astContext = svalBuilder.getContext(); 273 if (!IsCompleteType(astContext, elemType)) 274 return RegionRawOffsetV2(); 275 276 // Update the offset. 277 offset = addValue(state, 278 getValue(offset, svalBuilder), 279 scaleValue(state, 280 cast<NonLoc>(index), 281 astContext.getTypeSizeInChars(elemType), 282 svalBuilder), 283 svalBuilder); 284 285 if (offset.isUnknownOrUndef()) 286 return RegionRawOffsetV2(); 287 288 region = elemReg->getSuperRegion(); 289 continue; 290 } 291 } 292 } 293 return RegionRawOffsetV2(); 294} 295 296 297void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 298 mgr.registerChecker<ArrayBoundCheckerV2>(); 299} 300