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