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/AST/CharUnits.h"
     17 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
     18 #include "clang/StaticAnalyzer/Core/Checker.h"
     19 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
     20 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
     21 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
     22 #include "llvm/ADT/SmallString.h"
     23 #include "llvm/Support/raw_ostream.h"
     24 
     25 using namespace clang;
     26 using namespace ento;
     27 
     28 namespace {
     29 class ArrayBoundCheckerV2 :
     30     public Checker<check::Location> {
     31   mutable OwningPtr<BuiltinBug> BT;
     32 
     33   enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted };
     34 
     35   void reportOOB(CheckerContext &C, ProgramStateRef errorState,
     36                  OOB_Kind kind) const;
     37 
     38 public:
     39   void checkLocation(SVal l, bool isLoad, const Stmt*S,
     40                      CheckerContext &C) const;
     41 };
     42 
     43 // FIXME: Eventually replace RegionRawOffset with this class.
     44 class RegionRawOffsetV2 {
     45 private:
     46   const SubRegion *baseRegion;
     47   SVal byteOffset;
     48 
     49   RegionRawOffsetV2()
     50     : baseRegion(0), byteOffset(UnknownVal()) {}
     51 
     52 public:
     53   RegionRawOffsetV2(const SubRegion* base, SVal offset)
     54     : baseRegion(base), byteOffset(offset) {}
     55 
     56   NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); }
     57   const SubRegion *getRegion() const { return baseRegion; }
     58 
     59   static RegionRawOffsetV2 computeOffset(ProgramStateRef state,
     60                                          SValBuilder &svalBuilder,
     61                                          SVal location);
     62 
     63   void dump() const;
     64   void dumpToStream(raw_ostream &os) const;
     65 };
     66 }
     67 
     68 static SVal computeExtentBegin(SValBuilder &svalBuilder,
     69                                const MemRegion *region) {
     70   while (true)
     71     switch (region->getKind()) {
     72       default:
     73         return svalBuilder.makeZeroArrayIndex();
     74       case MemRegion::SymbolicRegionKind:
     75         // FIXME: improve this later by tracking symbolic lower bounds
     76         // for symbolic regions.
     77         return UnknownVal();
     78       case MemRegion::ElementRegionKind:
     79         region = cast<SubRegion>(region)->getSuperRegion();
     80         continue;
     81     }
     82 }
     83 
     84 void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad,
     85                                         const Stmt* LoadS,
     86                                         CheckerContext &checkerContext) const {
     87 
     88   // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping
     89   // some new logic here that reasons directly about memory region extents.
     90   // Once that logic is more mature, we can bring it back to assumeInBound()
     91   // for all clients to use.
     92   //
     93   // The algorithm we are using here for bounds checking is to see if the
     94   // memory access is within the extent of the base region.  Since we
     95   // have some flexibility in defining the base region, we can achieve
     96   // various levels of conservatism in our buffer overflow checking.
     97   ProgramStateRef state = checkerContext.getState();
     98   ProgramStateRef originalState = state;
     99 
    100   SValBuilder &svalBuilder = checkerContext.getSValBuilder();
    101   const RegionRawOffsetV2 &rawOffset =
    102     RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
    103 
    104   if (!rawOffset.getRegion())
    105     return;
    106 
    107   // CHECK LOWER BOUND: Is byteOffset < extent begin?
    108   //  If so, we are doing a load/store
    109   //  before the first valid offset in the memory region.
    110 
    111   SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion());
    112 
    113   if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
    114     SVal lowerBound =
    115         svalBuilder.evalBinOpNN(state, BO_LT, rawOffset.getByteOffset(), *NV,
    116                                 svalBuilder.getConditionType());
    117 
    118     Optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>();
    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 (!extentVal.getAs<NonLoc>())
    143       break;
    144 
    145     SVal upperbound
    146       = svalBuilder.evalBinOpNN(state, BO_GE, rawOffset.getByteOffset(),
    147                                 extentVal.castAs<NonLoc>(),
    148                                 svalBuilder.getConditionType());
    149 
    150     Optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>();
    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 
    181 void 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   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 
    213 void RegionRawOffsetV2::dump() const {
    214   dumpToStream(llvm::errs());
    215 }
    216 
    217 void 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
    222 static 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'.
    236 static inline SVal getValue(SVal val, SValBuilder &svalBuilder) {
    237   return val.getAs<UndefinedVal>() ? 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'.
    242 static 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'.
    252 static 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, x.castAs<NonLoc>(),
    260                                  y.castAs<NonLoc>(),
    261                                  svalBuilder.getArrayIndexType());
    262 }
    263 
    264 /// Compute a raw byte offset from a base region.  Used for array bounds
    265 /// checking.
    266 RegionRawOffsetV2 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 (!index.getAs<NonLoc>())
    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                           index.castAs<NonLoc>(),
    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 
    315 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) {
    316   mgr.registerChecker<ArrayBoundCheckerV2>();
    317 }
    318