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