contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

   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 };
  32
  33   void reportOOB(CheckerContext &C, const ProgramState *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(const ProgramState *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   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
 172 void 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
 195 void RegionRawOffsetV2::dump() const {
 196   dumpToStream(llvm::errs());
 197 }
 198
 199 void 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
 204 static 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'.
 218 static 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'.
 224 static 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'.
 234 static 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.
 248 RegionRawOffsetV2 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
 297 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) {
 298   mgr.registerChecker<ArrayBoundCheckerV2>();
 299 }