Home | History | Annotate | Download | only in Checkers 
      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 }
    300