lib/StaticAnalyzer/EntoSA/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 "ExprEngineInternalChecks.h"
  16 #include "clang/StaticAnalyzer/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/PathSensitive/CheckerVisitor.h"
  18 #include "clang/StaticAnalyzer/PathSensitive/ExprEngine.h"
  19 #include "clang/AST/CharUnits.h"
  20
  21 using namespace clang;
  22 using namespace ento;
  23
  24 namespace {
  25 class 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
  34 public:
  35   ArrayBoundCheckerV2() : BT(0) {}
  36   static void *getTag() { static int x = 0; return &x; }
  37   void visitLocation(CheckerContext &C, const Stmt *S, SVal l);
  38 };
  39
  40 // FIXME: Eventually replace RegionRawOffset with this class.
  41 class RegionRawOffsetV2 {
  42 private:
  43   const SubRegion *baseRegion;
  44   SVal byteOffset;
  45
  46   RegionRawOffsetV2()
  47     : baseRegion(0), byteOffset(UnknownVal()) {}
  48
  49 public:
  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
  65 void ento::RegisterArrayBoundCheckerV2(ExprEngine &Eng) {
  66   Eng.registerCheck(new ArrayBoundCheckerV2());
  67 }
  68
  69 void ArrayBoundCheckerV2::visitLocation(CheckerContext &checkerContext,
  70                                         const Stmt *S,
  71                                         SVal location) {
  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
 154 void 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
 177 void RegionRawOffsetV2::dump() const {
 178   dumpToStream(llvm::errs());
 179 }
 180
 181 void 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
 186 static 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'.
 200 static 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'.
 206 static 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'.
 216 static 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.
 230 RegionRawOffsetV2 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